An Efficient Block Matching Algorithm For Fast Motion Estimation Using Combined Simple And Efficient Search (SES) And Three Step Search(TSS) Algorithm

An Efficient Block Matching Algorithm For Fast Motion Estimation Using Combined Simple And Efficient Search (SES) And Three Step Search(TSS) Algorithm

Richa Bali

Department of Computer Science and Engineering, National Institute of Technology Calicut, India

V K Govindan

Department of Computer Science and Engineering, National Institute of Technology Calicut, India

Abstract- Motion Estimation is one of the most sought areas of research due to increasing demands of low computation complexity and better PSNR in video compression. There are several basic block matching algorithms like three step search and diamond search for faster and better motion estimation. This paper proposes a new algorithm which makes use of the benefits of three step search and simple and efficient search algorithms to achieve better PSNR and faster computation. The simulation results based on video frames were compared with the basic algorithms to demonstrate the advantages of proposed hybrid motion estimation algorithm. Results show that with the help of the new proposed algorithm, cost of computations has been reduced to 6.70, and the PSNR obtained is equivalent that of exhaustive search.

1. INTRODUCTION

   Motion estimation determine the motion vectors between two or more frames of video by finding the best similar block in previous frame for the block in current frame. The temporal prediction technique used in MPEG video is based on motion estimation. The basic premise of motion estimation is that in most cases, consecutive video frames will be similar except for changes induced by objects moving within the frames. In the trivial case of zero motion between frames (and no other differences caused by noise, etc.), it is easy for the encoder to efficiently predict the current frame as a duplicate of the prediction frame. When this is done, the only information necessary to transmit to the decoder becomes the syntactic overhead necessary to reconstruct the picture from the original reference frame. When there is motion in the images, the situation is not as simple and it requires computation to find the motion vectors of the moved block. To reduce the computational complexity of Motion Estimation algorithms, a variety of methods such as block matching algorithm (BMA) have been proposed in the literature. There are many basic algorithms for block matching out of which Three Step Search (TSS) and Simple and Efficient Search(SES) are the most efficient algorithms. The following example will explain this further. Frame 1 is

   the previous frame and Frame 2 is the current frame. Now, to estimate the motion we need to take a macroblock in current frame and find its best match(where MAD is negligible or very less) in the previous frame. Then we can return the coordinate values for how much the macroblock moved.

   In video editing motion estimation is a type of video compression scheme. The motion estimation process is done by the coder to find the motion vector pointing to the best predicted macroblock in a reference frame. For compression redundancy between adjacent frames can be exploited where a frame is selected as a reference and subsequent frames are predicted from the reference using motion estimation. The motion estimation process analyzes previous or future frames to identify blocks that have not changed, and motion vectors are stored in place of blocks. The process of video compression using motion estimation is also known as interframe coding.

   Motion estimation has tremendous applications like studying plant root growth , hand posture analysis, human posture analysis, lip movement for user authentication, studying plant root growth etc.

   1.1. LITERATURE SURVEY

   Aroh Barjatya [1] reviewed various block matching algorithms. The paper described the advantages and disadvantages of various block matching algorithms and compared the seven different types of block matching algorithms including the very basic Exhaustive Search to the recent well known algorithms like Adaptive Rood Pattern Search. The motive of the research was to find the best and fastest Block Matching Algorithm. The algorithms are compared on the basis of their speed, efficiency and PSNR Value. The author concludes that ARPS takes less computations and hence is the best of the fast block matching algorithms studied in this paper.

   Renxiang Li et al. [2] states that three-step search (TSS) is a simple and effective approach but it cannot find the small motions So, a new three-step search (NTSS) algorithm was proposed in the paper, in which a center-biased checking point pattern is included in the first step, and halfway-stop technique is used to reduce the computation cost. It has been proved by simulation results that, NTSS is better than TSS.

   The paper by Darshna and Jagiwala [3] is an analysis of the block matching algorithms used for motion Estimation. It implements and compares five different types of block matching algorithms which are Exhaustive Search, Three Step Search, Diamond Search, Four Step Search and Adaptive Road Pattern Search on H.264 Video codec. The authors concluded that if the temporal redundancy is reduced, then high performance of video compression may be achieved.

   Jianhua Lu and Ming L. Liou [4] proposed a new search algorithm for further reduction of computational complexity for motion estimation as compared to The three-step search (TSS) algorithm. TSS for block-matching motion estimation is widely used due to its simplicity, significant computational reduction, and good performance. A new algorithm is proposed in the paper whch is claimed to be more simple and efficient and requires only about one half of the computation for TSS while keeping the same regularity and good performance.

   new algorithm proposed by Santosh et al.[5] which is the hybrid algorithm produced by combining Diamond Search and Three Step Search. It is observed that the algorithm of Santosh et al. provides better results than all of the seven basic algorithms in terms of PSNR and Computation Complexity.

   1. Vijendra Babu et al. [6] reviewed and compared seven different types of Block Matching algorithms and proved that Adaptive Rood Pattern Search is the best of all.

      Shilpa et al. [7] presented a new method named as Modified Orthogonal Search Algorithm (MOSA) for the block matching motion estimation. In this algorithm, the author has introduced a center biased search point pattern for the estimation of small motions. A half way stop technique is also incorporated with the orthogonal search to reduce computation. The author stated that the proposed algorithm reduces the computational complexity in the existing Orthogonal Search. It also improved the speed of the algorithm by 2% than the OSA.

2. BLOCK MATCHING ALGORITHMS

   In BMA, the current image frame is divided into fixed-size rectangular blocks. In these algorithms, best matching Block is found in previous frame for a particular macro block in current frame. Although Full Search algorithm (FSA) finds the best match for a macroblock but it cannot be used in practical applications because of its high computational complexity. There are many BMAs used so far for fast

   motion estimation. Here, before presenting the proposed hybrid algorithm, a brief description of 3SS algorithm and Simple and Efficient Search algorithm, which are being used in the proposed algorithm, is given.

   1. Three Step Search (3SS)

      This algorithms is one of very old, simple but efficient algorithm . It starts with the search location at the center and sets the step size S = 4, for a usul search parameter value of 7. It then searches at eight locations +/- S pixels around location (0,0). From these nine locations searched so far it picks the one giving least cost and makes it the new search origin. It then sets the new step size S = S/2, and repeats similar search for two more iterations until S = 1.At that point it finds the location with the least cost function and the macro block at that location is the best match.

      Fig 1

   2. Simple and Efficient Search (SES)

   SES [7] is an extension to TSS and exploits the assumption of unimodal error surface. The main idea behind the algorithm is that for a unimodal surface there cannot be two minimums in opposite directions. In this Algorithm, the search area is divided into four quadrants and the algorithm checks three locations A,B and C as shown in Figure 3. A is at the origin and B and C are at S = 4 locations away from A in orthogonal directions.

   Check two arbitrary but orthogonal directions

   • Direction 1 and 7 in Fig. 2

   • Restrict the search area of each step in certain quadrant which contains only three search directions

     In the first phase, we compute the mean absolute difference (MAD) of A, B, and C as shown in Fig. 3

     Furthermore, we label four quadrants I, II, III, and IV as shown

     Fig 3

     The rules for determining a search quadrant are be described as follows :

   • If MAD(A) MAD(B) and MAD(A) MAD(C), I is selected

   • If MAD(A) MAD(B) and MAD(A) < MAD(C), II is selected

   • If MAD(A) < MAD(B) and MAD(A) < MAD(C), III is selected

   • If MAD(A) < MAD(B) and MAD(A) MAD(C), IV is selected

   Fig 2

   Fig. 4. Search patterns corresponding to each selected quadrant: (a) quadrant I, (b) quadrant II, (c) quadrant III, and

   (d) quadrant IV

   IV. PROPOSED ALGORITHM

   i.

   ii.

   Fig5. The SES procedure. The motion vector is (3, 7) in this example.

3. PERFORMANCE METRICS AND COST FUNCTIONS

   Matching of macroblocks from previous frame to the current frame is determined by Cost Function. The matching of one macro block with another is based on the output of a cost function. The macro block that results in the least cost is the one that matches the best to current block. There are various cost functions, of which the most popular and less computationally expensive is Mean Absolute Difference (MAD) given by equation (i). Another cost function is Mean Squared Error(MSE) given by equation (ii).

   where N is the side of the macro bock, Cij and Rij are the pixels being compared in current macroblock and reference macro block, respectively.

   The factor which determines the quality and characterizes the motion compensated image is PSNR given by equation (iii)

   (PeakValueOfOriginalData)2

   The proposed algorithm is obtained by combining 3SS and SES. The SES is used for locating one of the four the quadrants of the motion vector and the location of match within a quadrant is done based on 3SS. The algorithm is as given below:

   Algorithm

   {

   1 : Read the previous frame. 2 : Read the current frame

   3: Divide the current and previous frame into macro blocks (Each macro block means 16×16 pixel matrix)

   4 : Take the first macro block from current frame and match it with the previous frame using SES algorithm and find the quadrant in which macro block lies. This is done using MAD ( mean absolute difference) values of three orthogonal points A, B, and C ( Fig. 3) as follows:

   1. If MAD(A) MAD(B) and MAD(A) MAD(C),

      Quadrant I is selected

   2. If MAD(A) MAD(B) and MAD(A) < MAD(C),

      Quadrant II is selected

   3. If MAD(A) < MAD(B) and MAD(A) < MAD(C),

      Quadrant III is selected

   4. If MAD(A) < MAD(B) and MAD(A) MAD(C), Quadrant IV is selected

      At the same time we will check whether that macro block does not lie on A,B,C. If the required macroblock matches with either A, B or C, then no further steps are required. Else go to Step 5.

      5: The previous Step gives us the quadrant in which that macro block lies. Now we will find the macroblock in this quadrant by using Three Step Search:

      We took nine points (with centre [4,4] and eight neighbours of it at step size=2) in the middle of the search quadrant. And compare the MAD of these nine points (denoted in light green in Fig. 6) with the required macroblock

      6: If match is found for that macroblock (MAD<=, where is very small number nearly equal to Zero) at any one point

      PSNR 10 log10[

      Where

      MSE=Mean Squared Error

      MSE

      ] (iii)

      out of these nine points, then calculate the motion vector of the macro block at that point, else go to next step

      7: Now, apply Three step search algorithm with the least MAD point as centre.( as shown in fig 6)

      Figure 6: Proposed Algorithm

      1. SIMULATION RESULTS

         Algorithm	Computation	PSNR
         DS	20.2121	41.7401
         ES	195.2323	41.7613
         NTSS	23.6667	41.6818
         Proposed Algorithm	6.7323	40.2977
         SES	15.5581	40.0784
         SS4	20.3030	41.5945
         TSS	22.8939	41.5851

         Table 1: Results for Miss America Frame

         Algorithm	Computation	PSNR
         DS	12.6970	40.0479
         ES	195.2323	40.0722
         NTSS	17.4495	40.0536
         Proposed Algorithm	6.7045	38.7933
         SES	16.9040	38.7941
         SS4	15.9747	40.0445
         TSS	22.5909	40.0473

         Table 2 : Results for Mother Daughter Frames

         The proposed algorithm was tested for two different frames, viz., Miss America Frame, Mother Daughter Frame. It is observed that the new hybrid algorithm produced better results than TSS and SES. The no of computations have been reduced to 6.70 which is even less than Diamond Search Algorithm. The PSNR obtained is equivalent to other algorithms. It clearly shows that the proposed algorithm saves time and computations which is the demand of the day.

      2. CONCLUSION

         In this paper, we experimentally proved that the proposed algorithm works better than individual algorithms to reduce computation and achieve better PSNR. The strength of the algorithm lies in giving acceptable results (with improvement) in terms of Quality (PSNR) and the drastic reduction in the no. computations. The results of computations are better than that of other well known algorithms proposed in the literature. Hence, we can conclude that the new proposed algorithm superceded the application of TSS and SES for small motions.

      3. REFERENCES

1. Aroh Barjatya, Block matching algorithms for motion estimation ACM Transactions on Programming Languages and Systems, 2004.

2. Renxiang Li, Bing Zeng, and Ming L. Liou, A New Three-Step Search Algorithm for Block Motion Estimation, IEEE Trans. Circuits And Systems For Video Technology, 4(4),August 1994,438-442

3. Prof S.N. Shah, and Darshna D.Jagiwala, Analysis of block matching algorithms for motion estimation in h.264 video codec, International Journal of Engineering Research and Applications(IJERA), 2(6),

   December 2012, 1396-1401

5. Jianhua Lu, and Ming L. Liou, A Simple and Efficient Search Algorithm for Block-Matching Motion Estimation. IEEE Transactions On Circuits And Systems For Video Technology, 7(2), APRIL 1997.

6. Santosh Ku. Chhotray, Dheeraj Kannoujia & Samir Ku Jha, An Efficient Block Matching Algorithm For Fast Motion Estimation Using Combined Three Step Search And Diamond Search Algorithm, International Journal of Computer & Communication Technology ISSN,3(6), 2012

7. D.Vijendra Babu, P.Subramanian, and C.Karthikey AN Performnace Analysis of Block Matching Alogorithms for Highly Scalable Video Compression. IEEE,2006

8. Shilpa P. Metkar, and Sanjay N. Talbar; Fast motion estimation using modified orthogonal search algorithm for video compression, Springer- Verlag London Limited,4(1), January 2009, 123-128