
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.





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 interframe 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 6080% 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 decisionbased 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: ARPS3 (Unequalarmed the adaptive mod
pattern search) generally use the median forecast for the motion vector prediction
(Zhu et al., 2002). ARPS3 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 decisionbased 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 decisionmaking to get
the D macro block MV predictive value.
The specific steps of Bayesian decisionbased 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(ab): 
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 blockmatching 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 7090% 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 ARPS3, 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 
Zhu, C., X. Lin and L.P. Chau, 2002. Hexagonbased search pattern for fast block motion estimation. IEEE Trans. Circuits Syst. Video Technol., 12: 349355. CrossRef 
Nie, Y. and K.K. Ma, 2002. Adaptive rood pattern search for fast blockmatching motion estimation. IEEE Trans. Image Proces., 11: 14421449. CrossRef 
Ma, K.K. and G. Qiu, 2003. Unequalarm adaptive rood pattern search for fast blockmatching motion estimation in the JVT/H.26L. Proc. IEEE Int. Conf. Image Process., 1: 901904. CrossRef 
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 2426, 2001, San Jose, CA., USA., pp: 883892 CrossRef 
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 58, 2005, Versailles, France, pp: 188196 CrossRef 
Chen, Z., J. Xu, Y. He and J. Zheng, 2006. Fast integerpel and fractionalpel motion estimation for H.264/AVC. J. Visual Commun. Image Represent., 17: 264290.
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: 154162 CrossRef 
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: 560576. CrossRef  Direct Link 
Richardson, I.E.G., 2003. H.264 and MPEG4 Video Compression. John Wiley and Sons, New York, ISBN: 0470848375
Zhu, S. and K.K. Ma, 2000. A new diamond search algorithm for fast blockmatching motion estimation. IEEE Trans. Image Process., 9: 287290. CrossRef  PubMed 
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.



