 Open Access
 Total Downloads : 162
 Authors : V K Govindan, Richa Bali
 Paper ID : IJERTV3IS050604
 Volume & Issue : Volume 03, Issue 05 (May 2014)
 Published (First Online): 16052014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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.

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 threestep search (TSS) is a simple and effective approach but it cannot find the small motions So, a new threestep search (NTSS) algorithm was proposed in the paper, in which a centerbiased checking point pattern is included in the first step, and halfwaystop 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 threestep search (TSS) algorithm. TSS for blockmatching 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.

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.


BLOCK MATCHING ALGORITHMS
In BMA, the current image frame is divided into fixedsize 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.

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

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.


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:

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

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

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

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

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.

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.

REFERENCES



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

Renxiang Li, Bing Zeng, and Ming L. Liou, A New ThreeStep Search Algorithm for Block Motion Estimation, IEEE Trans. Circuits And Systems For Video Technology, 4(4),August 1994,438442

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, 13961401

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

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

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

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, 123128