21-03-2011, 04:50 PM
presented by:
K.Geetha,K.
Divya Charitha
[attachment=10693]
Abstract :
In video coding, block-based motion estimation plays a vital role for video compression. There are few block matching algorithms existing for motion estimation and motion compensation. In this paper a three step diamond search algorithm is proposed. The performance of this algorithm is compared with other algorithms by means of error metrics and number of search points. This algorithm achieves close performance with that of TSS. It uses less number of search points than TSS. When compared with original DS algorithm, this algorithm requires less computation time and gives an improved performance.
Key words-
Block based motion estimation, Block matching algorithm, search pattern, Diamond search.
I. INTRODUCTION
Video coding is an important process in many multimedia applications. In addition to spatial redundancy, temporal redundancy plays a vital role in the transmission of video frames [1]. Motion estimation is a technique used to reduce the temporal redundancy. It uses the correlation between the successive frames to predict the content of frames. In the motion estimation process the frame is divided into number of non overlapping areas known as blocks. Each block can be with a standard size of 16×16.The difference between the current frame and the predicted frame contents is calculated in motion estimation .In addition to motion estimation, some additional information’s are also needed to indicate any changes in the prediction process. This is known as motion compensation. Motion estimation and motion compensation algorithms are used to obtain strong temporal redundancy. Full search block matching algorithm is an algorithm which provides a better performance with more number of search points. But, there is a tradeoff between the efficiency of an algorithm and the quality of the prediction image. The suboptimal algorithms are used for this purpose. These algorithms are computationally more efficient but they do not give a good quality as in FSBMA. The suboptimal algorithms used in video transmission are Three step search (TSS) [2], New three step search (NTSS) [5], Diamond search (DS) ([3], [4]) and the like.
The search speed and the performance of an algorithm are determined by the shape and size of the search patterns. The TSS and NTSS algorithms are using a squared shape pattern, whereas the diamond search algorithm uses a Diamond shape. This DS algorithm uses an unrestricted center-biased searching concept and so it is computationally inefficient. In this paper, a three step diamond search algorithm is proposed to attain a computationally efficient search with a reasonable distortion performance.
The following section deals with the existing DS algorithm and its advantages and disadvantages. Section III explains about the modified DS algorithm. The experimental results and the performance will be presented in section IV and finally section V concludes the paper.
II. DIAMOND SEARCH ALGORITHM.
The shape of the search pattern has an impact on the performance of the algorithm. Fast block matching algorithms such as TSS, NTSS are having a square shape search pattern and provide reasonable performance. The distribution of global minimum points is centered at the center of the search window. A center biased NTSS is used to achieve better performance than TSS. But it losses the regularity and simplicity. The diamond search algorithm provides a better performance than the TSS, NTSS algorithms.
The DS algorithm uses a diamond shape pattern with nine search points, four points located at the corners and another four points located at the midpoint of the edges of the diamond shape. This algorithm uses an unrestricted center biased searching process .The diamond search employs a large diamond search pattern (LDSP) [fig 1(a)] and a small diamond search pattern (SDSP)
As some of the search points in the newly formed LDSP are overlapping, only the non-overlapping points need
to be evaluated. This greatly reduces the number of search points compared to other existing fast search algorithms. Therefore the search pattern uses five search points in the new LDSP if the MBD point is the corner point [fig2(a)] and three search points if the MBD point is at the edge of the pattern [fig 2(b)]. The LDSP pattern is used until the center point becomes the Minimum Block Distortion (MBD) point. Once the MBD point is at the center, the search is switched to SDSP which uses four checking points [fig 2©].
The MBD points thus obtained will give the motion vector. The DS algorithm reduces the susceptibility of getting stuck at local minima due to its compact shape and relatively large step size in the horizontal and vertical direction. Thus the DS algorithm gives a faster processing and similar distortion performance with the other fast searching algorithms. The increase in number of steps leads to more number of search points which has an effect on the speed of the algorithm. This makes the algorithm computationally inefficient. A three step diamond search (TSDS) is proposed to overcome this disadvantage.
III. THREE STEP DIAMOND SEARCH ALGORITHM.
The proposed TSDS algorithm uses the same type of patterns used in DS algorithm with a reduction in step size. Based on the location of the MBD point, the number of checking points to be used in the successive steps varies.
The number of searching steps is reduced to three and the SDSP search is reached at the third step regardless of the location of the MBD point. The LDSP pattern is repeatedly used until the center point becomes the MBD point. Thus the compact configuration and reduced number of search points provide an improved performance than the other existing algorithms. An example of this algorithm is given in fig3. The algorithm for this TSDS algorithm is summarized as follows.
Algorithm:
Step1: Initial LDSP is centered at the origin of the search window. Now, test each points in the search pattern .If the MBD point is the center point go to step3.Otherwise go to step2.
Step2: Form a new LDSP with the MBD point as the center point. If the new MBD point is at the center position, go to step3.Otherwise repeat this step for one more time.
Step3: Form the SDSP pattern with the previous MBD point as the center point. The new MBD point obtained in this step becomes the final solution i.e., the motion vector (x, y).
The number of search points depends on the location of MBD point. The MBD point also determines the search direction.
IV. SIMULATION RESULTS.
A window size of 15×15 is used for the experimentation of this algorithm and the center point of initial LDSP is at the origin of the search window. The performance of the algorithm is evaluated by error metrics such as the mean square error and signal to noise ratio. The performance analysis has been done for an “officer” sequence and it is shown
Simulation results show that, it gives a better performance compared with the existing TSS and DS algorithms with a reduction in step size also. The search is confined within the search window and the reduction in number of steps results in reduction in computational complexity. Simplicity and regularity of this algorithm provides an efficient implementation. The criterion used for the distortion measurement is Sum of Absolute Difference (SAD), which gives the MBD point for the motion vector calculation.
The pels are arranged in such a way that two in horizontal direction and in vertical direction, and one in each diagonal direction. This makes the algorithm to reach a global minimum point. The maximum number of search points used is 23 whereas the TSS uses 25 search points. It achieves a close MSE performance with the DS, TSS, NTSS algorithms for the image sequences with small motion as well as large motion contents.
V. CONCLUSION
In this paper we proposed a Three Step Diamond Search algorithm for computationally efficient block motion estimation. Because of the compact shape of the search pattern and step size it outperforms other existing algorithms such as TSS, NTSS, and DS in terms of computational efficiency with a better performance. This algorithm can be used in video coding standards such as MPEG-4, H.264 AVC because of its ease of implementation, better performance and reduced computational complexity.
