Comparative Study on Diamond Search Algorithm for Motion Estimation

Comparative Study on Diamond Search Algorithm for Motion Estimation

Ankita P. Chauhan1, Rohit R. Parmar2, Shahida G. Chauhan3

1. Research Scholar, Dept. of Computer Engg., A.I.T.S, Rajkot

2. Asst. Prof, Dept. of Ele. & Comm. Dept., GCET, V.V.Nagar

3. Asst. Prof, Dept. of Computer Engg., A.I.T.S, Rajkot

Abstract

Due to limited channel bandwidth, small amount of storage space and demanding requirements of real- time video playback, video compression is an essential process in a digital video communication. It requires a very high compression ratio. Motion estimation is the essential step in video compression to remove the temporal redundancy between adjacent frames. There are several algorithms proposed for motion estimation wherein block matching algorithms (BMA) are widely used for computing Motion Vectors (MV). But the most efficient block matching motion estimation (BMME) is Diamond Search (DS). This paper is a comparative study of motion estimation algorithm like DS, DLTS, DHS, MDSS and MDS.

Keywords – Motion Estimation, Block matching algorithm, Diamond Search, Video Compression

1. Introduction

   With the advent of communication media demand for multimedia is rapidly increasing. Digital media is being adopted in various range of application like Video telephony, Streaming media delivery on internet, CD, DVD Cellular media etc. In multimedia communication, the basic requirement for communication with moving video picture is growing rapidly. It is not practically possible to store and transmit full length of video without processing. A major problem in video is the huge storage space and high requirement for bandwidth. Thus video compression plays a major role for efficient storage and transmission of digital video signal in multimedia. Video compression contains tradeoffs between desired image quality and requirement of application.

   .

2. Motion Estimation

   Motion Estimation is one of the computationally expensive and most important element in video compression. In Figure 1 the basic

   block diagram for modern video compression is shown. In Video compression, Motion estimation and compensation plays an efficient role in inter-frame predictive coding system. Motion estimation is the process of determining the best motion vector that describes the displacement of the coordinate of the best similar block in reference frame for the block in current frame. The large amount of temporal correlation or, so called temporal redundancy between adjacent frames in a video sequence. So, the aim of motion estimation is to reduce temporal redundancy between adjacent frames in a video sequence. The most commonly & popular used ME method is the block matching motion estimation algorithm, has adopted by many compression standard as MPEG1, MPEG2, MPEG4, H.261, H.262, H.264 [5] [3] [12] [1].

   Figure 1: The Basis of Modern Video Compression

   In block matching technique, frames are divided into equally sized rectangular blocks. For each block in the current frame, the ME algorithm will find out the displacement of the best matched block as Motion vector with reference frame. In BMA, a variety of methods have been presented to reduce the computational complexity of ME algorithms. A number of block matching algorithms

   have been developed for example, Exhaustive Search (ES), 2-D logarithmic search (LOGS), Three Step Search (TSS), conjugate direction search (CDS), New Three step Search (NTSS),Four Step Search (4SS), block-based gradient descent search (BBGDS), diamond Search (DS), etc. Among all these fast BMAs, the DS algorithm is most famous because of its good performance. But it requires more number of search points which we should consider. It will reduce the search speed. To overcome this, a new method has been developed based on the diamond search. This paper have presented the comparative analysis of some popular existing motion estimation algorithms based on diamond search algorithm such as A Fast ME Algorithm Based on Diamond and Line/Triangle Search Patterns(DLTS), A Fast ME Algorithm Based on Diamond and Hexagon Search (DHS) Patterns, Modified Diamond-Square Search Algorithm (MDSS) and Modified Diamond Search Algorithm (MDS).

3. Existing Motion Estimation Algorithm

   In this section, we have described some popular motion estimation algorithms such as DS, DLTS, DHS, MDSS and MDS.

   1. Diamond Search Algorithm

      The New diamond search algorithm (DS) has been proposed by S. Zhu and K. K. Ma in 2000. DS algorithm is similar as 4SS [3], but the search point pattern is changed from a square to a diamond, and there is no limit on the number of steps that the algorithm can take. The DS algorithm utilizes two different types of fixed search patterns. The first pattern called large diamond search pattern (LDSP) shown in Figure 2(a) and the second pattern called small diamond search pattern (SDSP) shown in Figure 2(b). The LDSP consisting of nine checking points from which eight points surround the center one to compose a diamond shape. The SDSP consisting of five checking points forms a smaller diamond shape. [6]

      The searching procedure for the DS algorithm is shown in Figure 3. The first step uses LDSP and if the minimum block distortion (MBD) occurs at the center point we jump to last step. The next step, except the last step, use LDSP, is repeatedly used until the step in which the minimum block distortion (MBD) occurs at the center point.

      Figure 1: (a) Large Diamond Search Pattern (LDSP),

      (b) Small Diamond Search Pattern (SDSP)

      In the last step search pattern is then switched from LDSP to SDSP so as to find out MBD point. Among the five checking points in SDSP, The MBD point found in this step provides the final solution motion vector of the best matching block. DS is one of the most famous fast motion estimation algorithm consistently performs well for the image sequence with wide range of motion content. It also exceeds the well-known TSS algorithm and achieves close MSE performance compared to NTSS while reducing computation by 22% approximately.

      Figure 2: Search path example to the motion vector (-4,-

      2) in five search stepsfour times of LDSP and one time SDSP. There are 24 search points in totaltaking nine, five, three, three, and four search points at each step, sequentially.

   2. FME Algorithm Based on Diamond and Line/Triangle Search Patterns

      A fast Motion Estimation(FME) Algorithm Based on Diamond and Line/Triangle Search Patterns (DLTS) has been proposed by Yun Cheng and Min Wu in 2008 [9]. The DLTS employs three search patterns as illustrated in Figure 4. The first pattern called Diamond Search Pattern as shown in Figure 4(a). The second pattern called Line search Pattern (LP) as shown in Figure 4(b). The third pattern consisting of three checking points (including the

      MBD point) forms a triangle shape, called Triangle search Pattern (TP) as shown in Figure 4(c).

      (a)

      (b)

      (c)

      Center Point MBD Point SMBD point

      Figure 4: (a) Diamond Search Pattern (DP),

      (b) Line search Pattern (LP), (c) Triangle search Pattern (TP)

      The searching procedure for the DLTS algorithm is shown in Figure 5. In the searching process, DP is used to refine the motion vectors, while LP/TP is used to locate the best matching block with large motion approximately and it can be discarded if the motion vector is zero. The DLTS algorithm mainly comprises 4 stages. The first stage uses Eq. (1) to predict the initial motion vector of the current block, and the initial serch center point is set according to the predicted value.

      pred_mv = median ( mv_A, mv_B, mv_C ) (1)

      In the second stage, DP is used as the search pattern to find the best matching block with zero or small motion vector efficiently. If the MBD point is located at the search center position, then the searching process will terminate immediately and the best matching motion vector is equal to the predicted one. The searching pattern for the next search step can be decided by using Eq. (2). Here P1P0 are the distance between MBD and SMBD (Second MBD) points found in the current search step respectively.

      P1P0 = (X1, Y1) = (X0 X1, Y0 – Y1) (2)

      In the third stage, DLTS algorithm selects a search pattern from LP and TP adaptively according to the distance between P1 and P0. If the MBD and the SMBD points obtained in the previous search step are located in the same direction then TP is used at the new search center, otherwise LP is used at the new search center.

      In the fourth stage, the DLTS algorithm uses DP repeatedly until the new MBD point occurs at the center of DP or DP and LP/TP alternately according to the position of the new MBD point found in the previous search step. If the MBD point calculated is located at the center position that is the final solution of the motion vector which points to the best matching block, then Stop searching.[9]

      Figure 5: Search path example to the motion vector (-4,-

      2) in five search steps one time of LP, one time of TP, and three times of DP. There are 15 search points in total taking five, one, four, two, and three search points at each step, sequentially.

   3. A FME Algorithm Based on Diamond and Hexagon Search (DHS) Patterns

      A Fast Motion Estimation Algorithm Based on Diamond and Hexagon Search Patterns (DHS) has been proposed by Yun Cheng, Lin Yang, Zhiwen Fang, Hailiang Hou and Ganxin Chen in 2009 [10]. DHS (Diamond Hexagon Search) is also based on the directional characteristic of SAD distribution and the center-biased characteristic of motion vectors. The DHS uses two search patterns as illustrated in Figure 6(a) and Figure 6(b). The first pattern called Diamond Search Pattern (DP) as shown in Figure 6(a). The second pattern called Hexagon Search Pattern (HP) as shown in Figure 6(b).

      1. (b)

         Figure 6: (a) DP (Diamond Search Pattern) (b) HP (Hexagon Search Pattern)

         In the searching process, DP is used to refine the motion vectors, while HP is used to locate the best matching block with large motion approximately and it can be discarded if the motion vector is zero. The DHS algorithm mainly consists of two stages. The first stage uses the median motion value of the adjacent blocks to predict the motion vector of the current block by using an equation (3), in order to reduce the search points for the best matching block with large motion.

         pred_mv = median ( mv_A, mv_B, mv_C ) (3)

         The second stage uses HP and DP adaptively according to a video sequence with different motion vectors. In the second stage, The DHS algorithm uses DP at the first and second search step. If the best matching point locates at the center position, the process of searching will stop immediately. Otherwise, in order to judge whether the best matching block with large motion vector, the algorithm employs HP at the next search step. If the new MBD point is located at one of the four vertexes of DP, which indicates that the best matching motion vector would be small. Then DP is repeatedly used until the step in which the MBD occurs at the search center point. Otherwise, do the same as the beginning.

   4. A Modified Diamond-Square Search (MDSS) Algorithm

      The Modified diamond search algorithm (MDSS) has been developed by A.Anusooya Devi et.al in 2011 [1]. The Modified diamond search algorithm uses two search patterns as illustrated in Figure 7 and figure 8.The first pattern called Modified Large Search Pattern (MLSP) is a modification of Large Diamond search Pattern (LDSP) as shown in Figure 7. The second pattern called Modified Small Search Pattern (MSSP) is a modification of Small Diamond search Pattern (SDSP) shown in Figure 8.

      Figure 7: LDSP to MLSP

      Figure 8: SDSP to MSSP

      Steps of MDSS algorithm are shown in Figure 9. In the initial step, MLSP is centered at the origin of the search window, and the four vertexes and the origin point are tested. If the MBD point computed occurs at the center position, then go to the last step. The next step, except the last step, use MLSP, is repeatedly used until the step in which the minimum block distortion (MBD) found at the center point. In The last step, the search pattern Switch from MLSP to MSSP and the MBD point found in this step provides the final solution motion vector of the best matching block.

      MLSP Candidate Point MSSP Candidate Point MBD Point

      Figure 9: Search path example of the MDSS algorithmic process which leads to the MV(-4,-2) in five search stagesfour times of MLSP and one time MSSP at the final step. There are 17 search points in totaltaking five, three, three, two, and four search points

   5. A Modified Diamond Search Algorithm

      The Modified diamond search algorithm (MDS) has been proposed by Yun Cheng, Xine You and Minlian Xiao Minlei Xiao in 2011. MDS algorithm is the improvement of the DS algorithm by analyzing the characteristic of DS. The MDS algorithm utilizes two different types of search patterns. The first pattern called small diamond search pattern (SDSP) shown in Figure 2(b) and second pattern called simplified large diamond search pattern (SLDSP) shown in Figure 10. In SDSP minimum block distortion (MBD) point finding within the circular area with a radius of one pixel at the center point, whereas in SLDSP MBD point finding within the circular area with a radius of two pixels at the center point.

      Figure 10: Simplified Large Diamond Search Pattern employed in the MDS algorithm

      In the searching process, SDSP is used to refine the motion vectors and SLDSP is used to locate the best matching block with large motion approximately. The searching procedure of the MDS algorithm is shown in Figure 11. The MDS algorithm mainly consists of two stages. The first stage uses the median motion value of the adjacent blocks to predict the motion vector of the current block by using a formula (4), in order to reduce the search points for the best matching block with large motion. [11]

      pred_mv = median ( mv_A, mv_B, mv_C ) (4)

      The second stage uses SDSP and SLDSP according to a video sequence with different motion vectors. The first step uses SDSP and if the best matching point locates at the search center, the process of searching will terminate immediately. Otherwise, in order to find the best matching block with large motion vector, the MDS algorithm employs SLDSP at the next search step. SLDSP is repeatedly used to locate the best matching block until the search center becomes the MBD point. If the new Minimum Block Distortion (MBD) point located in SDSP that indicates that the best matching motion vector would be small. Then SDSP is repeatedly used until the step in which the search center becomes the MBD point. Otherwise, do the same as the beginning.

4. Conclusion

   In all type of motion estimation algorithm diamond search algorithm is best compared to other algorithm. In this paper we have presented a comparative study for variation in diamond search motion estimation algorithm like Diamond Search Algorithm (DS), FME Algorithm Based on Diamond and Line/Triangle Search Patterns (DLTS), FME Algorithm Based on Diamond and Hexagon Search Patterns (DHS), Modified Diamond-Square Search Algorithm (MDSS) and Modified Diamond Search Algorithm (MDS). Here we have described the searching process for each algorithm in detail with essential steps.

   Figure 11: Search path example to the motion vector (- 4,-2) in six search steps- four times of SLDSP and two time SDSP. There are 21 search points in total takng five, four, three, three, two, and four search points at each step, sequentially.

5. References

1. A.Anusooya Devi, M.R.Sumalatha, N.Mohana Priya, B.Sukruthi, and M.Minisha, Modified Diamond- Square Search Technique for Efficient Motion Estimation, IEEE-International Conference on Recent Trends in Information Technology, ICRTIT 2011,pp. 1149 1153, June 2011

2. L. Po and W. Ma, A novel four-step search algorithm for fast block motion estimation. IEEE Transaction on Circuits and system for Video Technology, Vol. 6, No.3, June 1996, pp 313-317.

3. Lai-Man Po, and Wing-Chung Ma, A Novel Four- Step Search Algorithm for Fast Block Motion Estimation, IEEE Trans. Circuits And Systems For

   Video Technology, vol 6, no. 3, pp. 313-317, June

   1996.

4. R. Li, B. Zeng, and M. L. Liou, A new three-step search algorithm for block motion estimation, IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 438 442, Aug. 1994.

5. R. A. Manap S. S. S. Ranjit A. A. Basari and B. H. Ahmad, Performance Analysis of Hexagon-Diamond Search Algorithm for Motion Estimation, 2nd International Conference on Computer Engineering and Technology 978-1-4244-6349-7/10/$26.00 _c 2010 IEEE.

6. Shan Zhu, and Kai-Kuang Ma, A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation, IEEE Trans. Image Processing, vol 9, no. 2, pp. 287-290, February 2000.

7. T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro,Motion compensated interframe coding for video conferencing, in Proc. Nat. Telecommun. Conf. New Orleans, LA, Nov. 29Dec. 3 1981, pp. G5.3.1 5.3.5.

8. Yasser Ismail, Jason Mcneelly, Mohsen Shaaban, And Magdy A. Bayoumi, Enhanced efficient Diamond Search Algorithm for Fast Block Motion Estimation 978-1-4244-3828-0/09/$25.00 ©2009 IEEE

9. Yun Cheng and Min Wu,A fast Motion estimation Algorithm Based on Diamond and Line/Triangle Search Patterns, Pervasive Computing and Applications, 2008. ICPCA-2008.Third International Conference on, vol.1, pp.537-542, Oct. 2008

10. Yun Cheng, Lin Yang, Zhiwen Fang, Hailiang Hou and Ganxin Chen, A Fast Motion Estimation Algorithm Based on Diamond and Hexagon Search Patterns (DHS), Pervasive Computing (JCPC), 2009 Joint Conferences on,pp. 595-598, Dec. 2009

11. Yun Cheng, Xine You and Minlian Xiao Minlei Xiao, A Modified Diamond Search Algorithm, IT in Medicine and Education (ITME), 2011 International Symposium on,vol.2,pp. 481 485, Dec. 2011

12. Haihua Liu, Yi Lei, and changsheng Xie, Fast Block- Matching Motion Estimation Based On An Improved Cross-Diamond Search Algorithm, ICECS 2005. 12th IEEE International Conference.