Search by item HOME > Access full text > Search by item

JBE, vol. 23, no. 5, pp.628-635, September, 2018


Fast Motion Estimation Algorithm using Selection of Candidates and Stability of Optimal Candidates

Jong Nam Kim

C.A E-mail:


In this paper, we propose a fast motion estimation algorithm which is important in video encoding. So many fast motion estimation algorithms have been published for improving prediction quality and computational reduction. In the paper, we propose an algorithm that reduces unnecessary computation, while almost keeping prediction quality compared with the full search algorithm. The proposed algorithm calculates the sum of partial block matching error for each candidate, selects the candidates for the next step, compares the stability of optimal candidates with minimum error, and finds optimal motion vectors by determining the progress of the next step. By doing that, we can find the minimum error point as soon as possible and obtain fast compu- tational speed by reducing unnecessary computations. Additionally, the proposed algorithm can be used with conventional fast mo- tion estimation algorithms and prove it in the experimental results.

Keyword: Motion estimation, full search, selection of candidates, stability of optimal candidates, partial distortion elimination

[1] T. Tan, R. Weerakkody, and G. Sullivan, “Video quality evaluation methodology and verification testing of HEVC compression performance,” IEEE Transactions on Circuits System & Video Technology, Vol. 26, No. 1, pp. 76-90, 2016.
[2] T. Lee, Y. Chan, and W. Siu, “Adaptive search range by neighbouring depth intensity weighted sum for HEVC texture coding,” IEE Electron. Letters, Vol. 52 No. 12, pp. 1018-1020, 2016.
[3] H. Choi, J. Kim, S. Jung, “Fast Motion Estimation Algorithm using Importance of Search Range and Adaptive Matching Criterion,” The Journal of Korea Institute of Signal Processing and Systems, Vol. 16, No. 4, pp. 129-133, 2015.
[4] Z. Pan, j. Lei, Y. Zhang, X. Sun, and S. Kwong, “Fast motion estimation based on content property for low-complexity H.265/HEVC encoder,” IEEE Transactions on Broadcasting, Vol. 63, No. 3, pp. 675-684, 2016.
[5] P. Bhalge and S. Amdani, “Modified hexagonal search for motion estimation”, Proceeding of International Conference on Intelligent Compuuting and Control Systems, pp. 94-96, 2017.
[6] N. Alnajdawi, M , Alnajdawi, and S. Tedmori, “Employing a novel cross-diamond search in a modified hierarchical search motion estimation algorithm for video compression,” Elsevier Information Sciences, Vol. 268, pp. 425-435, 2014.
[7] A. Paramkusam, “Efficient motion estimation algorithm on the layers,” IEE Electron. Letters, pp. 467-468, 2017.
[8] N. Vayalil, M. Paul, and Y. Kong, “ A novel angle-restricted test zone search algorithm for performance improvement of HEVC”, Proceeding of IEEE International Conference on Image Processing, pp. 6-10, 2017.
[9] X.Q. Gao, C.J. Duanmu, and C.R. Zou, “A Multilevel Successive Elimination Algorithm for Block Matching Motion Estimation,” IEEE Transactions on Image Processing, Vol. 9, No. 3, pp. 501-504, 2000.
[10] J. Kim, S. Byun, Y. Kim, and B. Ahn, “Fast Full Search Motion Estimation Algorithm Using Early Detection of Impossible Candidate Vectors,” IEEE Transactions on Signal Processing, Vol. 50, No. 9, pp. 2355-2365, 2002.
[11] H.264/AVC reference software, download/old_jm/
[12] S. Jin and H. Lee, "Fast Partial Distortion Elimination Algorithm based on Hadamard Probability Model," IEE Electron. Letters, Vol. 44, No. 1, pp. 17-19, 2008.


Editorial Office
1108, New building, 22, Teheran-ro 7-gil, Gangnam-gu, Seoul, Korea
Homepage: TEL: +82-2-568-3556 FAX: +82-2-568-3557
Copyrightⓒ 2012 The Korean Institute of Broadcast and Media Engineers
All Rights Reserved