doi: 10.17586/2226-1494-2017-17-3-483-489


Nguyen Van Truong, A. A. Tropchenko

Read the full article  ';
Article in Russian

For citation: Nguyen Van Truong, Tropchenko A.A. Fast test zone search algorithm for interframe encoding. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2017, vol. 17, no. 3, pp. 483–489 (in Russian). doi: 10.17586/2226-1494-2017-17-3-483-489


The paper deals with the fast motion estimation algorithms for interframe encoding in the video data H.265 / HEVC standard. A new adaptive algorithm has been offered based on the analysis of the advantages and disadvantages of existing algorithms. The algorithm is called fast test zone search algorithm and includes the traditional test zone search algorithm (TZS) and the hierarchical search MP (Hierarchical Search or Mean Pyramid). The considered and proposed motion estimation algorithms have been tested in several video sequences using Microsoft Visual Studio software.  The terms for algorithms evaluating were: the video sequence quality criterion (by PSNR), bitrate and encoding time. The proposed method showed that it works about 4 times faster. The average loss of the RD curve value (PSNR versus bitrate) is up to 4% in all. Application of this algorithm in modern codec H.265/HEVC instead of the standard one can significantly reduce compression time, and can be recommended for further study of the JCT-VC (Joint Collaborative Team on Video Coding).

Keywords: HEVC, hybrid approach, TZS, МР, raster search, motion estimation, HM software (HEVC Test Model)

1.     Wiegand T., Sullivan G.J., Bjontegaard G., Luthra A. Overview of the H,264/AVC video coding standard. IEEE Transactions on Circuits and Systems for Video Technology, 2003, vol. 13, no. 7, pp. 560–576. doi: 10.1109/TCSVT.2003.815165
2.     Sullivan G.J., Ohm J.-R., Han W.-J., Wiegand T. Overview of the high efficiency video coding (HEVC) standard. IEEE Transactions on Circuits and Systems for Video Technology, 2012, vol. 22, no. 12, pp. 1649–1668. doi: 10.1109/TCSVT.2012.2221191
3.     Grellet M., Shafique M., Khan M.U.K. et. al. An adaptive workload management scheme for HEVC encoding. Proc. 20th IEEE Int. Conf. on Image Processing. Melbourne, Australia, 2013, pp. 1850–1854. doi: 10.1109/ICIP.2013.6738381
4.     Jain J., Jain A. Displacement measurement and its application in interframe image coding. IEEE Transaction on Communications, 1981, vol. 29, no. 12, pp. 1799–1808. doi: 10.1109/TCOM.1981.1094950
5.     Zhu C., Lin X., Chau L.-P. Hexagon-based search pattern for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 2002, vol. 12, no. 5, pp. 349–355. doi: 10.1109/TCSVT.2002.1003474
6.     Zhu S., Ma K. -K. A new diamond search algorithm for fast block matching motion estimation. Proc. Int. Conf. on Information, Communications and Signal Processing. Singapore, 1997, vol. 1, pp. 292–296. doi: 10.1109/ICICS.1997.647106
7.     Yin P., Tourapis H.-Y.C., Tourapis A.M., Boyce J. Fast mode decision and motion estimation for JVT/H,264. Proc. Int. Conf. on Image Processing. Barcelona, Spain, 2003, vol. 3, pp. 853–856. doi: 10.1109/ICIP.2003.1247379
8.     Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG. Comments on Motion Estimation Algorithms in Current JM Software (JVT-Q089). Joint Video Team Document. 17th Meeting: Nice, France, 2005.
9.     Nguyen Van Truong, Tropchenko A.A. Hierarchical adaptive rood pattern search for motion estimation at video sequence analysis. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2016, vol. 16, no. 3, pp. 474–481. (In Russian). doi: 10.17586/2226-1494-2016-16-3-474-481
10.  Nguen V.T., Tropchenko A.A. Methods and algorithms for reducing temporal redundancy of video data. Proc. II Int. Conf. on Actual Problems of Science in XXI Century. Moscow, 2015, part 2, pp. 36–41. (In Russian)
11.  Dufaux F., Gao W., Tubaro S., Vetro A. Distributed video coding: trends and perspectives. Eurasip Journal on Image and Video Processing, 2009, pp. 1–13. doi: 10.1155/2009/508167
12.  Ascenso J., Brites C., Pereira F. Improving frame interpolation with spatial motion smoothing for pixel domain distributed video coding. Proc. EURASIP Conference on Speech and Image Processing. Multimedia Comm and Services. Slovak Republic, 2005.
13.  Hong W. Coherent block-based motion estimation for motion compensated frame rate up-conversion. Proc. Int. Conf. on Consumer Electronics, ICCE. Las Vegas, USA, 2010, pp. 165–166. doi: 10.1109/ICCE.2010.5418935
14.  Li X., Wang R., Wang W., Wang Z., Ding S. Fast motion estimation methods for HEVC. Proc. IEEE Int. Symposium on Broadband Multimedia Systems and Broadcasting. Beijing, China,2014, pp. 1–4. doi: 10.1109/BMSB.2014.6873547
15.  Li X., Wang R., Cui X., Wang W. Context-adaptive fast motion estimation of HEVC. Proc. IEEE Int. Symposium on Circuits and Systems, ISCAS. Lisbon, Portugal, 2015, pp. 2784–2787. doi: 10.1109/ISCAS.2015.7169264
16.  Purnachand N., Alves L.N., Navarro A. Fast motion estimation algorithm for HEVC. Proc. IEEE Int. Conf. on Consumer Electronics. Berlin, 2012, pp. 34–37. doi: 10.1109/ICCE-Berlin.2012.6336494

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2023 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.