Modified Adaptive Predict Hexagon Based Search Motion Estimation Algorithm

Authors

  • I. Ali National Centre for Physics, Islamabad
  • M. Muzammil International Islamic University
  • A. Basit Pakistan Institute of Nuclear Science and Technology, Islamabad
  • I. Haq International Islamic University

Abstract

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.

Author Biographies

I. Ali, National Centre for Physics, Islamabad

National Centre for Physics, Islamabad

M. Muzammil, International Islamic University

Islamabad

A. Basit, Pakistan Institute of Nuclear Science and Technology, Islamabad

TPPD

I. Haq, International Islamic University

Islamabad

References

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, https://doi.org/10. 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: http://media.xiph.org/video/derf/, Jan-2016.

Downloads

Published

07-12-2018

How to Cite

[1]
I. Ali, M. Muzammil, A. Basit, and I. Haq, “Modified Adaptive Predict Hexagon Based Search Motion Estimation Algorithm”, The Nucleus, vol. 55, no. 4, pp. 164–170, Dec. 2018.

Issue

Section

Articles