Subscribe Now Subscribe Today
Abstract
Fulltext PDF
References
Research Article
 

Research on the Motion Estimation Algorithm in Video Coding



QuanFei and Wei Wei
 
ABSTRACT

This study proposed two algorithms, an adaptive motion estimation algorithm based on Bayesian decision and an improved Motion Vector Field Adaptive Search Technique (MVFAST) algorithm. The first algorithm proposed in this paper, firstly, statistic the current frame and the before frame coded macro block information, Then, using the Bayesian theory, combined with the consistency characteristics of macro block MV space, to get an accurate and fast prediction motion vector. The second algorithm proposed in this paper with better early termination strategy, that is to set up a dynamic threshold of the threshold and take full advantage of the spatial and temporal correlation of video sequences, the use of the adjacent macro block motion vector to block movement by type starting point for prediction using different search strategies on the macro block.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

QuanFei and Wei Wei, 2012. Research on the Motion Estimation Algorithm in Video Coding. Information Technology Journal, 11: 1660-1663.

DOI: 10.3923/itj.2012.1660.1663

URL: https://scialert.net/abstract/?doi=itj.2012.1660.1663
 
Received: April 16, 2012; Accepted: June 15, 2012; Published: August 28, 2012

INTRODUCTION

Motion estimation in video compression efficiency of the system is mainly reflected in image quality, compression rate and search speed. The basic principle is the use of adjacent frames in video sequences, the temporal correlation and spatial correlation. Establish the relationship between the sequence adjacent to the inter-frame expression, thereby reducing the temporal redundancy and spatial redundancy, improve the efficiency of video coding.

In a video solution, the motion estimation computation is generally 60-80% of the total computation, the results directly affect the quality of the video image coding efficiency and recovery. Therefore, efficient motion estimation algorithm has a very important significance to improve the video data compression coding efficiency. Improve image quality, speed up the estimated speed and reduce the bit rate is the goal of motion estimation algorithm.

There are a lot of motion estimation algorithm, in general there are four categories: block matching motion estimation algorithm, recursive algorithm, wide flow method and the Bayesian estimation method. Many existing video coding standards using a block matching motion estimation algorithm. In order to improve video compression performance of the coding, to rely heavily on the improvement of the motion estimation algorithm. In this study, a Bayesian decision-based adaptive motion estimation algorithm, as well as on the basis of the MVFAST algorithm to study and propose an improved fast search algorithm.

AN ADAPTIVE MOTION ESTIMATION ALGORITHM BASED ON BAYESIAN DECISION

The basic idea of algorithm: ARPS-3 (Unequal-armed the adaptive mod pattern search) generally use the median forecast for the motion vector prediction (Zhu et al., 2002). ARPS-3 algorithm for use of the space adjacent macroblocks to predict the target macroblock motion vector but there are inadequacies in the domain.

For the problems of the ARPS, -3 algorithm, proposed an adaptive motion estimation algorithm based on Bayesian decision, its main uses the following technologies: (1) Bayesian decision-based motion vector prediction. Based on the principle of minimum space distance, traverse the before frame and then statistics the probability of neighboring macroblock MV predict the target macroblock MV as their priori probability. And also statistics the above probability in the encoded macroblock of current frame as the conditional probability. Then adjacent macro block of the posterior probability calculated according to the Bayesian formula to determine which neighboring macroblock MV to predict the target macroblock MV. (2) Adaptive search patterns. Firstly, search for the origin location and the predicted position of MV, then use SDSP (small diamond search pattern) to search and set the elasticity coefficient K to decide whether to enter LDSP (large diamond search pattern) (Nie and Ma, 2002; Ma and Qiu, 2003).

Steps of the algorithm: All macroblocks in a video frame are processed in raster scan order in the space domain (Tourapis et al., 2001), so the adjacent macro blocks in the upper left, upper right and the left up can be well used as a reference macroblock. Use this algorithm to support regional as shown in Fig. 1, prediction MV of the target macroblock D is decided by A, B, C, three macro blocks of the MV. A, B, C, macroblock MV in one to predict the MV of the target macroblock D, constitute a Bayesian event group so that you can use the Bayesian decision-making to get the D macro block MV predictive value.

The specific steps of Bayesian decision-based adaptive motion estimation algorithm are as follows:

Step 1: If the current frame is the first frame or the first line of macroblock column, then use the ARPS, -macroblock prior to traverse to get the final MV and A, B, C, macroblock MV, respectively, to predict a priori probability of D macroblock MV; otherwise transferred to step 2
Step 2: Bayesian formula and the current A, B, C three macroblock MV predict the conditional probability of D macroblock MV, then calculate the posterior probability of A, B, C, three macro block, use the bigger posteriori probability of the macroblock MV to be the prediction MV of D macroblock. And then predict the MV location and origin
Step 3: Using DSP to search, When DSP continuous search for the number more than twice, transferred to step 4, otherwise go to step 5
Step 4: Using LDAP to search until the best match point in the center position and then transferred using the SDSP search for the final MV
Step 5: If all macro block traversal is completed, the current frame is completed, the value of MV record and update the a priori probability value; otherwise, update the conditional probability values and transferred to step 2

Fig. 1(a-b): Statistical predictive value, (a) Supported region and (b) Statistical process

AN IMPROVED MOTION VECTOR FIELD ADAPTIVE SEARCH ALGORITHM

The basic idea of algorithm: Generally speaking, in the sequence of video images, spatial correlation exists between the image within the adjacent blocks (Shen et al., 2005). In addition, there will still be relatively static block. For these blocks, the zero vector (0, 0) is the best motion vector (Chen et al., 2006). These two points is the guiding ideology of the MVFAST algorithm. Firstly, to determine the starting point to predict whether the current block of the initial motion vector is the best motion vector; Secondly, the video sequence classification is divided into different levels of exercise intensity based on video sequences of different, using a different search template to search for different types of video sequences; coupled with efficient early termination strategy enables the rapid, accurate and need to get the motion vector.

Algorithm analysis: In all block-matching algorithm, the full search algorithm is the simplest block matching motion estimation algorithm, in order to find the best match, it must traverse the search area within the frame of all possible points (Illgner et al., 1996; Wiegand et al., 2003). However, the FS search method complexity is quite high, it will use throughout the compression coding 70-90% of the time, such a large time overhead resulting algorithm simply can not be used to timely develop applications (Richardson, 2003). MVFAST algorithm is a fast search algorithm much faster than the full search algorithm but it is not the best fast search algorithm. Based on the basis of the analysis of MVFAST algorithm, the basic idea is to improve the algorithm: The better of the early termination of the policy is adopted, a fixed threshold of the MVFAST algorithms is changed into the state threshold, so that the algorithm to judge more flexibility; In addition, when predict the current block motion vectors, the airspace adjacent motion vectors and macroblock motion vector in the time domain to the front a the same position should be considered; when macroblock exercise intensity is identified, the macroblock which has the strongest exercise intensity use the big diamond template to search, and the other macroblock use the small diamond template to search. In the search process, using dynamic threshold to a premature end search, in the case of image restoration quality changed little, the improved algorithm improve search speed (Zhu and Ma, 2000).

Improved analysis of algorithm: When the quality of video images has little change, in order to make the search process to a premature end and reduce block matching computation, early termination strategy can be used in the search process. The current SAD value comparison with a threshold T, If the SAD<T, it reach our requirements, then end the search process in advance so that we can improve the searching speed.

At the same time, the prediction of search center is very important, if projections are accurate, can effectively improve the speed of video coding. But usually in the video sequence, there are some static macroblocks or exercise intensity is low macroblock (0, 0) is often the best motion vector, Therefore continue to forecast on the center point does not make sense and also waste coding time, adding unnecessary computation. In improved algorithm, using MVFAST algorithm to predict the central point, that is to judge according the intensity of macroblock (Wenger et al., 2005). If macroblock exercise intensity is low or the general, then determine the (0, 0) as the search center; If the exercise intensity is strong, then you need to calculation the 0, 1, 2, 3 and 4 macroblock motion vector corresponding to the point of the SAD value, the size of the comparison of their value and finally select the SAD minimum value corresponds to the point as a search center. MV FAST algorithm only consider the spatial domain on the adjacent block, while the improved algorithm put the block of time domain into account, that is, the options shown in Fig. 2 corresponds to the point of 1, 2, 3 and 4 motion vectors as the search center point, The specific approach is to calculate the motion vector corresponding SAD value, set SAD1, SAD2, SAD3 and SAD4, compare the size of their value, the motion vector corresponding to the minimum SAD value is the best motion vector.

Algorithm improvement description:

Detection of static macroblocks. Firstly calculate the SAD value of the motion vector (0, 0), if the SAD (0, 0) is less than the threshold T, then terminate the search (0, 0) is the motion vector we need to find. Otherwise, skip to (2)
Detected the SAD value in V5. Calculate the SAD value of the location pointed by V5 (denoted SAD5), If SAD5 less than the threshold T0, then end the search, V5 is the current macroblock motion vector; Otherwise, skip to (3)
Detected the SAD value in V1, V2, V3 and V4. Calculate the SAD value of the location pointed by V1, V2, V3 and V4 (denoted SAD1, SAD2, SAD3 and SAD4), If the minimum SAD value is less than the threshold the T0, then end the search; Otherwise, skip to (4)
Determine the type of movement. Using adjacent macroblock motion vector to determine the current macroblock motion type. If L1<L<L2, the macroblock motion intensity is in general, so using a small diamond pattern search; If L>L2, the macroblock motion intensity is strong, so using a large diamond pattern search; If the most advantages in the center, using a small diamond search, otherwise continue using the diamond template search
Initial search point prediction. The initial search point prediction is set based on the current macroblock motion type, If the current macroblock of the exercise intensity is weak or in general, select the center point (0, 0) as the search starting point


Fig. 2: Predict the location of block

CONCLUSION

The first algorithm proposed in this paper, firstly, statistic the current frame and the before frame coded macroblock information, Then, using the Bayesian theory, combined with the consistency characteristics of macroblock MV space, to get an accurate and fast prediction motion vector. The experiments show that, compared to the DS, ARPS and ARPS-3, the algorithm reduces the average search points for motion estimation, in order to save coding time, while good results in the search quality.

At the same time, this study presents an improved motion estimation algorithm. The improved algorithm with better early termination strategy, that is to set up a dynamic threshold of the threshold and take full advantage of the spatial and temporal correlation of video sequences, the use of the adjacent macroblock motion vector to block movement by type starting point for prediction using different search strategies on the macro block. The results show that, in the case of the image quality is slightly improved, compared with original MVFAST algorithm, the improved algorithm can effectively improve the encoding speed.

REFERENCES
Chen, Z., J. Xu, Y. He and J. Zheng, 2006. Fast integer-pel and fractional-pel motion estimation for H.264/AVC. J. Visual Commun. Image Represent., 17: 264-290.

Illgner, K., W. Praefcke and F. Muller, 1996. Multiresolution motion estimation. Proceeding of the SPIE Image and Video Processing IV, February 1, 1996, San Jose, CA., USA., pp: 154-162.

Ma, K.K. and G. Qiu, 2003. Unequal-arm adaptive rood pattern search for fast block-matching motion estimation in the JVT/H.26L. Proc. IEEE Int. Conf. Image Process., 1: 901-904.
CrossRef  |  

Nie, Y. and K.K. Ma, 2002. Adaptive rood pattern search for fast block-matching motion estimation. IEEE Trans. Image Proces., 11: 1442-1449.
CrossRef  |  

Richardson, I.E.G., 2003. H.264 and MPEG-4 Video Compression. John Wiley and Sons, New York, ISBN: 0-470-84837-5.

Shen, C.D., T.J. Li and S.K. Li, 2005. A predictive direction guided fast motion estimation algorithm. Proceedings of the 11th International Conference on Computer Analysis of Images and Patterns, September 5-8, 2005, Versailles, France, pp: 188-196.

Tourapis, A.M., O.C. Au and M.L. Liou, 2001. Predictive Motion Vector Field Adaptive Search Technique (PMVFAST)-enhancing block based motion estimation. Proceedings of the SPIE Visual Communications and Image Processing, January 24-26, 2001, San Jose, CA., USA., pp: 883-892.

Wenger, S., M.M. Hannuksela, T. Stockhammer, M. Westerlund and D. Singer, 2005. RTP payload format for H.264 video. http://mail.tools.ietf.org/pdf/rfc3984.pdf.

Wiegand, T., G.J. Sullivan, G. Bjontegaard and A. Luthra, 2003. Overview of the H.264/AVC video coding standard. IEEE Trans. Circuits Syst. Video Technol., 13: 560-576.
CrossRef  |  Direct Link  |  

Zhu, C., X. Lin and L.P. Chau, 2002. Hexagon-based search pattern for fast block motion estimation. IEEE Trans. Circuits Syst. Video Technol., 12: 349-355.
CrossRef  |  

Zhu, S. and K.K. Ma, 2000. A new diamond search algorithm for fast block-matching motion estimation. IEEE Trans. Image Process., 9: 287-290.
CrossRef  |  PubMed  |  

©  2019 Science Alert. All Rights Reserved
Fulltext PDF References Abstract