Research on the Motion Estimation Algorithm in Video Coding
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
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:
||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
||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
||Using DSP to search, When DSP continuous search for the number more than
twice, transferred to step 4, otherwise go to step 5
||Using LDAP to search until the best match point in the center position
and then transferred using the SDSP search for the final MV
||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
||Statistical predictive value, (a) Supported region and (b)
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
||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
|| Predict the location of block
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.
1: 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.
2: Nie, Y. and K.K. Ma, 2002. Adaptive rood pattern search for fast block-matching motion estimation. IEEE Trans. Image Proces., 11: 1442-1449.
3: 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.
4: 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
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
6: 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.
7: 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
8: 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 |
9: Richardson, I.E.G., 2003. H.264 and MPEG-4 Video Compression. John Wiley and Sons, New York, ISBN: 0-470-84837-5
10: 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 |
11: 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.