Modified Adaptive Predict Hexagon Based Search Motion Estimation Algorithm

I. Ali, M. Muzammil, A. Basit, I. Haq


Motion Estimation (ME) is a very critical part of any video encoder and different fast ME algorithms are proposed to reduce the overhead of computational cost that was available in encoding system. This paper proposes a Modified Adaptive Predict Hexagon Based Search (MAPHS) algorithm to cope the computational requirements. The proposed algorithm predicts the direction of motion by using adaptive rood shaped predictor and then Hexagonal based Search is applied to refine the search process. The adaptive predictor changes own size predetermined motion vector for each macro block. The ME process is speedup by incorporating thresholding technique, which is primarily beneficial for the videos having low motion activities. Moreover, the proposed algorithm has improved the peak signal to noise ratio (PSNR) by adaptively changing the threshold value according to the motion contents of different videos. The experimental results show that the proposed algorithm performs well on both high definition and common intermediate format videos with respect to ME time and number of search points with acceptable PSNR.

Full Text:



K. R. Rao and J.J. Hwang, “Techniques and standards for image, video and audio coding”, Prentice Hall PTR, 1996.

K. Rijkse, "H.263: video coding for low-bit-rate communication", Communications Magazine, IEEE, vol. 34, no. 12, pp. 42-45, Dec 1996

H.264, “Draft ITU-T recommendation and final draft inter-national standard”, Pattaya, Thailand, 2003. [4] G.J. Sullivan, J. Ohm, Woo-Jin Han and T. Wiegand , "Overview of the high efficiency video coding (HEVC) standard", IEEE Transactions on Circuits and Systems for Video Technology, vol. 22, no. 12 , pp. 1649 -1668 , 2012.

R. Takada, S. Orihashi, Y. Matsuo, J. Katto, "Improvement of 8K UHDTV picture quality for H.265/HEVC by global zoom estimation", IEEE International Conference on Consumer Electronics, pp. 58-59, Jan. 2015.

I. Ali, M. Muzammil and G. Raja, “Performance analysis of motion estimation algorithms based on motion activity in video sequences”, Pakistan Journal of Science, vol. 64, pp. 39-45, March, 2012.

S.D. Kamble, S.T. Khawase, N.V. Thakur and A.V. Patharkar, "An improved approach of block matching algorithm for motion vector estimation", Int. J. Inf. Retrieval Res. (IJIRR) vol. 8, no. 1, 38-56, 2018.

Y. Li, G. Yang, Y. Zhu, X. Ding and X. Sun, "Unimodal stopping model-based early SKIP mode decision for high-Efficiency video coding," IEEE Transactions on Multimedia, vol. 19, no. 7, pp. 1431-1441, 2017.

P. Nguyen; H. Tran; H. Nguyen, X-N. Nguyen, C. Vo, B. Nguyen, V-D. Ngo and V-T. Nguyen, "Asymmetric diamond search pattern for motion estimation in HEVC", IEEE Fifth Int. Conf. on Communications and Electronics, pp. 434-439, July 30, August 1, 2014.

L. Renxiang, B. Zeng and M. L. Liou, “A new three-step search algorithm for block motion estimation”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 4, no. 4, 1994.

L. Jianhua and M. L. Liou, “A simple and efficient search algorithm for block-matching motion estimation”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 7, no. 2, 1997, pp. 429-433.

L-M. Po and W-C. Ma, “A novel four-step search algorithm for fast block motion estimation”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 3, pp. 313-317, June 1996.

Z. Pan, R. Zhang, W. Ku, and Y. Wang, “Adaptive pattern selection strategy for diamond search algorithm in fast motion estimation”, Multimedia Tools and Applications, 1-18, 2018, 1007/s11042-018-6353-2.

C. Zhu, X. Lin, L-P. Chau, K-P. Lim, H-A. Ang, C-Y. Ong, “A novel hexagon-based search algorithm for fast block motion estimation”, IEEE Conference on Acoustics, Speech, and Signal Processing, vol. 3 pp. 1593-1596, 2001.

C. Zhu, X. Lin and L-P. Chau, “Hexagon-based search pattern for fast block motion estimation”, ieee transactions on circuits and systems for video technology, vol. 12, no. 5, pp. 340-355, 2002.

Yavuz, Seda, A. Celebi, M. Aslam and O. Urhan, "Selective gray-coded bit-plane based low-complexity motion estimation and its hardware architecture", IEEE Transactions on Consumer Electronics, vol. 62, no. 1, pp.76-84, 2016.

T-H. Tsai; Y-N. Pan, "A novel predict hexagon search algorithm for fast block motion estimation on H.264 video coding," Circuits and Systems, Proceedings of IEEE Asia-Pacific Conference on, pp. 609-612, vol. 1, 6-9 Dec. 2004.

A. Basit et al. /The Nucleus 55, No. 4 (2018) 163-169

T-H. Chen; Y-F. Li, "A novel flatted hexagon search pattern for fast block motion estimation", International Conference on Image Processing, vol. 3, no., pp. 1477-1480, 24-27 Oct. 2004.

F.H. Jamil, A. Chekima, R. R. Porle, O. Ahmad, N. Parimon, “BMA performance of video coding for motion estimation” IEEE Third International Conference on Intelligent Systems, Modelling and Simulation (ISMS), pp. 287 – 290, 2012.

Z. Cuanfeng, L. Guizhong and S. Rui, “A modifed hexagon-based search algorithm for block motion estimation”, IEEE Int. Conf. Neural Networks & Signal Processing Nanjing. China, pp. 1205-1208, December 14-17, 2003.

D. VijendraBabu, P. Subramanian, C. Karthikeyan, “Performance Analysis of block matching algorithms for highly scalable video compression”, IEEE Conf. Ad Hoc and Ubiquitous Computing, pp. 179-182, 2006.

R.A. Manap, S.S.S. Ranjit, A.A. Basari and B.H. Ahmad, “Performance analysis of hexagon-diamond search algorithm for motion estimation”, IEEE Int. Conf. Computer Engineering and Technology (ICCET), vol. 3, pp. V3-155 - V3-159, 2010.

Luo, Jun, X. Yang, and L. Liu, “A fast motion estimation algorithm based on adaptive pattern and search priority", Multimedia Tools and Applications, vol. 74, no. 24, pp. 11821-11836, 2015.

M. Muzammil, G. Raja and I. Ali, "Field programmable gate array (FPGA) architecture of diamond search motion estimation algorithm for real-time video applications", NED University Journal of Research - Applied Sciences, vol. XII, No. 4, 2015.

B-Ji Zou, C. Shi, C-H. Xu and S. Chen, "Enhanced hexagonal-based search using direction-oriented inner search for motion estimation", IEEE Transactions on Circuits and Systems for Video Technology, vol. 20, no. 1, pp. 156-160, Jan. 2010.

I. Ali, G. Raja, M. Muzammil and A.K. Khan, “Adaptive modified hexagon based search motion estimation algorithm”, IEEE 4th Intl Conf. on Consumer Electronics, Berlin, pp.147-148, 7-10 Sept. 2014.

G. Raja and M. J. Mirza and T. Song, “H.264/AVC de-blocking filter based on motion activity in video sequences”, IEICE Electronics Express, vol. 5, no. 19, pp. 809 – 814, 2008.

CIF format Videos, “YUV test video sequences”, available on-line at:, Jan-2016.


  • There are currently no refbacks.