# A Novel Search Technique of Motion Estimation for Video Compression Pranob K Charles ? Dr. Habibulla Khan ? & Dr. K.S. Rao ? Abstract-Video Compression is highly demanded now a days as due to the fact that in the field of entertainment, medicine and communication there is high demand for digital video technology. For the effective removal of temporal redundancy between the frames for better video compression Motion estimation techniques plays a major role. Block based motion estimation has been widely used for video coding. One such method is the Hierarchical Search Technique for BMA. By amalgamating the three different search algorithms like New three step search, New Full search and New Cross diamond search a novel hierarchical search methodology is proposed. Subsampling the original image into additional two levels is done and thereby the New Diamond search algorithm and a new three-step search algorithm are used in the bottom two levels and the Full Search is performed on the highest level where the complexity is relatively low. In terms of PSNR with reduced complexity this new proposed algorithm showed better performance. Keywords: hierarchical search, motion estimation, PSNR, new cross diamond search, new three step search, BMA. # I. Introduction ideo compression is the process of representing the video data using fewer bits than the original representation. Motion estimation plays a major role in Video Compression. As video requires much more space to store than still image, video compression is very much useful in reducing the storage space and which will eventually lead to lesser cost. It is carried out mainly by using BMA. In BMA both the reference frame and current frame are divided into blocks and for each block in the current frame the algorithm searches for a best match block in the reference frame. The search in the reference frame is conducted within a search window defined by parameter p. The displacement of the macro block in the reference frame with respect to macro block in the current frame is represented by a vector known as motion vector. The most suitable matching criteria that are used are mean square error (MSE), sum of absolute difference (SAD) etc. Several BMA's have been developed over the years. The most basic is the FSA [1], where all the blocks are searched for a best match (255 efficiency but the most computationally expensive and it is very time consuming. The TSS in comparison to FSA requires only 25 comparisons. Since it follows a fixed pattern, it works inefficiently on slow motion video sequences. The NTSS [2] enhances the TSS by using a half way stop technique. NTSS is more complex than TSS. The FSS [3] uses a centre biased checking point pattern with a half way stop technique being more complex. The CDS [4] uses a cross and diamond shape pattern. They are very complex. In Neighborhood Elimination approach [5] we use a spatial correlation property and a half way stop technique. This approach however has low PSNR for medium and fast motion sequences. The ABC Algorithm [6] has a low PSNR compared to FSA. The Modified PSO [7] offers reduced number of computations and high PSNR for large motion, but not for slow and medium motion sequences. The Octagon Square BMA [8] uses an octagon and square shape pattern and can identify both large and small motion. It has the disadvantage of being a fixed pattern algorithm. The BBGDS [9] Algorithm works better in small motion but it has very large motion vector for large motion video sequences. Most of these BMA perform well in terms of estimating slow, medium and fast motion video sequences. The performance of the proposed hierarchical search technique unlike the other algorithms is close to the Full Search with reduction in complexity. # II. Motion Estimation Algorithms for Hierarchichal Search a) Full Search Algorithm (FS) FS Algorithm searches all the search points within the search window for a best match. Therefore it is very simple to implement and is highly efficient but it has very high computational time. # b) New Cross Diamond Search Algorithm (NCDS) The NCDS [10] Algorithm follows a pattern. The first step stop involves a search of only 5 search points while the second step stop required 8 search points. An unrestricted large diamond search (DS) pattern was employed in the subsequent steps followed by a final small diamond search. # c) New Three Step Search Algorithm (NTSS) The NTSS Algorithm is an improvement on the TSS Algorithm so as to find small motions. It has a half way stop for first and second steps. # III. Proposed Method IV. Proposed HSBMA Algorithm Step 1: Level-1 is the lowest level and consists of the original frame at its full resolution. This level is subsampled by a factor of 2 in vertical and horizontal directions to produce Level-2. Step 3: In this step, the search starts from the highest level (Level-3) using 4 X 4 block sizes, where a FS algorithm will be performed to get the initial coarse motion vector and the best match position will be passed to the lower level (Level-2). Step 4: This step involves searching Level-2 by using the new proposed cross-diamond search pattern (using 8 X 8 block sizes) to get a new motion vector, and the best match position will be passed to Level-1 (Lowest level). Step 5: In this step, the New Three-Step-Search algorithm is used on Level-1 utilizing 16 X 16 block sizes. Hence the final motion vector is obtained and that will be added to the previous image to get the next predicted image frame. # V. Implementation and Results The section presents the results of applying the various algorithms included in the proposed Hierarchical Search Motion Estimation technique. Simulations have been performed over the standard Video Sequence "Sample Video.avi" has moderately complex motion getting medium content regarding its motion content. By using the matlab the The video is extracted into frames. Here the video is initially run in MATLAB using the "VideoReader" command. It is then extracted into frames as shown in Fig 2. # F In the proposed hierarchical search technique, an input and reference frame are subsampled into three levels. Level 1 is subsampled both horizontally and vertically by a factor of 2 to get Level 2. This level in turn is subsampled both horizontally and vertically by a factor of 2 to get Level 3 as shown in Fig 1 .The three different algorithms such as Full Search Algorithm, New Cross Diamond Search Algorithm and New Three Step Search Algorithm are applied to the various Levels .The best match motion vector obtained from Level 3 is passed on to Level 2 and the best match motion vector obtained from Level 2 is passed on to Level 1.The motion vector so obtained from Level 1 is considered the final motion vector of the motion estimation process. Step 2: This step involves sub -sampling Level-2 in the same way to produce Level-3 (highest level).The subsampling process ends, by getting Level-1, Level-2 and Level-3. # Table I: No of Computations The value of the No of computations for the HS Technique which is the sum of all the computations by the three algorithms in the three levels of the frame is lesser than that of the Full Search algorithm. # Table II: No of Computations Also the value of PSNR for the HS Technique is approaching that of the most efficient FS Algorithm. 3![Fig 3 shows the lowest level (Level-1) consists of the original frame at its full resolution. The next Level-2 consists of Level-1 image sub-sampled by a factor of 2 in vertical and horizontal directions as in Fig (b).And again sub-sampling Level-2 in the same way produces Level-3 image (highest level) as in Fig (c).](image-2.png "Fig 3") 1456789![Fig.1: Different Levels in a HS algorithm Fig. 2: Video Played in MATLAB](image-3.png "Fig. 1 :Fig. 4 :Fig. 5 :Fig. 6 :Fig. 7 :Fig. 8 :Fig. 9 :") 10![Fig.10: Search Points per Macro Block vs Frame Number in NCDS Algorithm](image-4.png "Fig. 10 :") IIIHIERARCHICHAL SEARCHAlgorithmNo of ComputationsFULL SEARCH181.444NEW CROSS DIAMOND5.1708NEW THREESTEP22.3485SEARCHALGORITHMPSNRMSEFULL SEARCH32.343637.9074HIERARCHICHAL SEARCH TECHNIQUE29.241722.3485FAlgorithmNo of ComputationsFULL SEARCH213.382. R Li, Bing Zeng, Ming L. Liou, AUGUST 1994, "New Three-Step Search Algorithm For Block Motion Estimation", Transactions On Circuits And Systems For Video Technology, Vol. 4, No. 4. 3. Lai-Man Po, Wing-Chung Ma," A Novel Four-Step Search Algorithm for Fast Block Motion Estimation" IEEE Transactions On Circuits And Systems For Video Technology, Vol. 6, No. 3, June 1996. © 2017 Global Journals Inc. (US) ## Acknowledgment The author would like to thank Dr. Habibulla Khan and Dr. K.S.Rao for their valuable suggestions and thorough checking the paper with necessary enhancements incorporated where ever required. * Block matching algorithms for motion estimation ABarjatya IEEE Transactions Evolution Computation 8 2004 * A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimation Chun-HoCheung Lai-ManPo IEEE, Circuits And Systems For Video Technology 2002 12 * A neighborhood elimination approach for block matching in motion estimation AvishekSaha JayantaMukherjee Shamiksural Signal Processing: Image Communication 26 June 2011 * Block matching algorithm for motion estimation based on Artificial Bee Colony (ABC) ErikCuevasa DanielZaldívara MarcoPérez-Cisnerosa HumbertoSossab ValentínOsunab Applied Soft Computing 13 2013 * On fast and accurate block-based motion estimation algorithms using particle swarm optimization JingCai WDavidPan Information Sciences 197 August, 2012 * Block based Motion Estimation using Octagon and Square Pattern SSowmyayani PArockia Jansi Rani International Journal of Signal Processing 7 4 2014 Image Processing and Pattern Recognition * Novel Directional Gradient Descent Searches for Fast Block Motion Estimation Lai-ManPo Ka-HoNg IEEE Transactions on Circuits and Systems for Video Technology 2009 * A new crossdiamond search algorithm for fast block motion estimation Xiaodong[jun Tian Shen KBelloulata IEEE, Image Processing (ICIP) 2009