978-1-4673-0964-6/12/$31.00 ©2012 IEEE 104
2012 5th International Congress on Image and Signal Processing (CISP 2012)
Motion Estimation Based On H.264 Video Coding
Yufeng Li, Jufei Xiao, Wei Wu
College of Electronic information engineering
Shenyang Aerospace University
Shenyang, China
Abstract—Motion estimation is the most important and time
consuming part of H.264 video coding standard. It takes
about 60%-80% of the encoding time. Nowadays, study on
high performance fast motion estimation in video
compression technology is an important research topic. Based
on the H.264 video coding standard, this article selects X264
as the test code and analysis the X264 four kinds of
movement estimate algorithm. By the adding of the
asymmetrical small diamond search, it reduces the search
points, optimizes partial algorithms, makes the improvement
to asymmetrical cruciform multi-level hexagon grid point
search algorithm (UMHexagonS), and enhances the
movement estimate algorithm efficiency. Propose the
asymmetrical cruciform multi-level octagon grid point
searches algorithm (X264_ME_UMO). Testing with a variety
of video sequences it proves that the improved algorithm can
make the coding speeds increasing an average of about 17%
in the case of little effect on image quality and bit rate. It
effectively reduces the computational complexity to better
meet the needs of practical application.
Keywords-H.264; X264; motion estimation; UMHexagonS;
X264_ME_UMO
I. INTRODUCTION
Motion estimation and motion compensation is the most
critical part in video coding technology. The pros and cons of
their algorithm have a direct impact on the encoding speed,
quality and bit rate. However, its computational complexity is
also the highest in the entire system for taking about 60%-80%
of encoding time [1]. Therefore, improving the efficiency of
motion estimation algorithm is particularly important. In this
regard, the scholars have proposed a lot of fast algorithms to
reduce the computational complexity of motion estimation.
Compared with the full search algorithm, UMHexagonS [2]
algorithm can save more than 90% of the computation and
maintain a better rate distortion performance. Currently, it
already used by H.264 standard. However, the algorithm still
exist a high degree of complexity and large computational
problems. In order to better meet the needs of practical
applications, scholars have also actively invested in the
optimization of the algorithm. Such as in literature [3, 4],
UMHexagonS algorithm has been optimized with using the
dynamic search window, adaptive large hexagonal and small
hexagonal search pattern. Literature [5] has used the idea of
early termination and added early termination conditions in
multi-layer hexagonal spiral searching and searching phases,
which effectively reducing motion estimation time. Literature
[6,7], have proposed an adaptive cross template fast block
matching methods to solve the disadvantage of single template
in searching vertical moving objects. This can add the number
of searching points more efficiently, so as to improve the
searching speed. However, the majority of existing researches
were based on the Join Video Team reference encoder JM. Its
usefulness has been somewhat limited.
This article selects the X264 encoder, which is one of the
three open source code (JM, X264, T264) in H.264. X264
focus on practical and abandoned some of the H.264 encoding
performance which have small contribution while have high
computational complexity. Under the premise of maintaining
the original coding performance, it reduces the complexity of
the encoding.
X264 provides four optional integer pixel motion
estimation algorithms: full search method (X264_ME_ESA),
asymmetrical cross method of multi-layer hexagonal lattice
point search (X264_ME_UMH), diamond search method
(X264_ME_DIA) and hexagon search (X264_ME_HEX).
X264_ME_ESA is search full point within the search area.
The minimum SAD (Sum of Absolute Difference, SAD) value
of these points is the global optimum search point. However,
the computation of this algorithm is very large. It is the most
time-consuming in the X264's four motion estimation
algorithms. X264_ME_UMH is a search algorithm in the
H.264 standard algorithm model JM. Currently, it is the best
fast search algorithm. In contrast, X264_ME_DIA and
X264_ME_HEX algorithms have faster search speed.
This article focuses on the X264_ME_UMH algorithm of
X264 and makes the improvement to the 5x5 quadrangle
algorithm, the asymmetrical cruciform algorithm and the multi-
level hexagon algorithm, then proposes the new
X264_ME_UMO algorithm. It effectively improves the coding
rate and the practicality of the algorithm under the conditions
that the image quality has no significant change.
II. U
MHEXAGONS ALGORITHM ANALYSIS
A. Start point search
In X264, the index point initial location of motion
estimation is obtained through the x264_mb_predict_
mv_16x16 function. According to the spatial correlation, by
using the left, top, top-left coded macro block’s motion vector
(mv) to get the current macro block (mb) motion vector’s
predictive value (MVP), and predictive vector endpoint as the
initial point of the MVP (codenamed X0) to integer pixel
National Natural Science Fund project (No.61171081)
资源评论
