Skip to main content
Springer Nature Link
Log in

Learning-based bypass zone search algorithm for fast motion estimation

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

Abstract

Video coding has been widely explored by academia and industry in recent years, mainly due to the great popularization of video applications and multimedia-capable devices. The Motion Estimation (ME) process receives special attention since it is one of the most complex steps in video coding. The Test Zone Search (TZS) is the main algorithm employed for integer ME in recent video codecs, such as those based on the High Efficiency Video Coding (HEVC), and has been used in the standardization process of the future Versatile Video Coding (VVC) standard. However, even though it is designed as a fast ME algorithm, the computational effort required by TZS is still very high, compromising the encoding process in multimedia-capable devices that operate on limited energy or computational resources. This work presents the Bypass Zone Search (BZS) algorithm, a learning-based solution for fast ME that improves TZS, aiming at a better tradeoff between compression efficiency and computational cost. First, a set of analyses on TZS is presented, which allowed the design of two strategies to reduce the ME computational cost. The first one, named as Learning-based Bypass Motion Estimation (LBME), consists of a machine learning-based approach that predicts whether the best motion vector has already been found and bypasses the remaining ME steps. The second strategy, named as Astroid Raster Pattern (ARP), is a novel search pattern developed for the most complex TZS step, the Raster Search. By combining the two proposed strategies in BZS, the ME processing time is reduced by 60.98% (Random Access) and 63.05% (Low Delay) in comparison to TZS. The overall HEVC encoding time is reduced by 14.32% (Random Access) and 17.64% (Low Delay), with a negligible loss of 0.0837% (Random Access) and 0.04% (Low Delay) in BD-rate.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Afonso V, Maich H, Audibert L, Zatt B, Porto M, Agostini L, Susin A (2016) Hardware implementation for the HEVC fractional motion estimation targeting real-time and low-energy. J Integr Circuits Syst 11(2):106

    Article  Google Scholar 

  2. Agarwal PK, Sharir M, Comput ACM (1998) Efficient algorithms for geometric optimization. Surv 30(4):412–458. https://doi.org/10.1145/299917.299918

    Article  Google Scholar 

  3. Belghith F, Kibeya H, Loukil H, Ayed MAB, Masmoudi N (2016) A new fast motion estimation algorithm using fast mode decision for highefficiency video coding standard. J Real-Time Image Proc 11(4):675

    Article  Google Scholar 

  4. Bjontegaard G (2001) Calculation of average PSNR differences between RD-curves. VCEG-M33

  5. Bross B, Chen J, Liu S, Wang Y (2020) Versatile Video Coding (Draft 8). JVET-Q2001

  6. CISCO (2018) Cisco visual networking index: Global mobile data traffic forecast update 2017–2022. Cisco Visual Networking Index (VNI)

  7. Cheung C-H, Po L-M (2005) Novel cross-diamond-hexagonal search algorithms for fast block motion estimation. IEEE Trans Multimedia 7(1):16. https://doi.org/10.1109/TMM.2004.840609

    Article  Google Scholar 

  8. Correa G, Assuncao P, Agostini L, da Silva Cruz LA (2012) Performance and computational complexity assessment of high-efficiency video encoders. IEEE Trans Circuits Syst Video Technol 22(12):1899. https://doi.org/10.1109/TCSVT.2012.2223411

    Article  Google Scholar 

  9. Fan R, Zhang Y, Li B (2017) Motion classification-based fast motion estimation for high-efficiency video coding. IEEE Trans Multimedia 19 (5):893. https://doi.org/10.1109/TMM.2016.2642786

    Article  Google Scholar 

  10. Gonçalves P., Correa G, Porto M, Zatt B, Agostini L (2017) Multiple early termination scheme for TZ search algorithm based on data mining and decision trees. In: 2017 IEEE 19th international workshop on multimedia signal processing (MMSP). https://doi.org/10.1109/MMSP.2017.8122245, pp 1–6

  11. Goncalves P, Moraes C, Porto M, Correa G (2019) Complexity-aware TZS algorithm for mobile video encoders. J Integr Circuits Syst 14(3):1

    Article  Google Scholar 

  12. Goncalves P, Porto M, Zatt B, Agostini L, Correa G (2018) Octagonal-axis raster pattern for improved Test Zone Search motion estimation. In: 2018 IEEE international conference on acoustics. speech and signal processing (ICASSP). https://doi.org/10.1109/ICASSP.2018.8462580, pp 1763–1767

  13. Hu N, Yang E (2014) Fast motion estimation based on confidence interval. IEEE Trans Circuits Syst Video Technol 24(8):1310. https://doi.org/10.1109/TCSVT.2014.2306035

    Article  Google Scholar 

  14. ISO/IEC-JCT1/SC29/WG11 (2020) High Efficiency Video Coding (HEVC) Test Model 16 (HM16) Encoder Description. JVET-q2001

  15. ITU Telecommunication Standardization (2003) ITU-T Recommendation H.264

  16. ITU-T (2008) Subjective video quality assessment methods for multimedia applications. p 910

  17. Jia L, Tsui C, Au OC, Jia K (2019) A new rate-complexity-distortion model for fast motion estimation algorithm in HEVC. IEEE Transactions on Multimedia 21(4):835. https://doi.org/10.1109/TMM.2018.2866762

    Article  Google Scholar 

  18. Jing X, Chau Lap-Pui (2004) An efficient three-step search algorithm for block motion estimation. IEEE Transactions on Multimedia 6(3):435. https://doi.org/10.1109/TMM.2004.827517

    Article  Google Scholar 

  19. Karegowda A, Manjunath A (2010) Comparative study of attribute selection using gain ratio and correlation based feature selection. International Journal of Information Technology and Knowledge Management 2

  20. Li N, Zhang Y, Zhu L, Luo W, Kwong S (2019) Reinforcement learning based coding unit early termination algorithm for high efficiency video coding. J Vis Commun Image Represent 60:276. https://doi.org/10.1016/j.jvcir.2019.02.021. http://www.sciencedirect.com/science/article/pii/S1047320319300677

    Article  Google Scholar 

  21. Linck I, Gomez AT, Alaghband G (2018) Test Zonal Search based on Region Label (TZSR) for Motion Estimation in HEVC. In: 2018 IEEE 20th international workshop on multimedia signal processing (MMSP), pp 1–6

  22. Liu Z, Lin TL, Chou CC (2016) Efficient prediction of CU depth and CU mode for fast HEVC encoding using statistical analysis. J Vis Commun Image Represent 38:474. https://doi.org/10.1016/j.jvcir.2016.03.025

    Article  Google Scholar 

  23. Luo F, Wang S, Wang S, Zhang X, Ma S, Gao W (2019) GPU-based hierarchical motion estimation for high efficiency video coding. IEEE Transactions on Multimedia 21(4):851. https://doi.org/10.1109/TMM.2018.2867260

    Article  Google Scholar 

  24. Nalluri P, Alves LN, Navarro A (2015) Complexity reduction methods for fast motion estimation in HEVC. Signal Process Image Commun 39:280. https://doi.org/10.1016/j.image.2015.09.015

    Article  Google Scholar 

  25. Pakdaman F, Hashemi M, Ghanbari M (2020) A low complexity and computationally scalable fast motion estimation algorithm for HEVC. Multimedia Tools and Applications 79. https://doi.org/10.1007/s11042-019-08593-y

  26. Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, Prettenhofer P, Weiss R, Dubourg V, Vanderplas J, Passos A, Cournapeau D, Brucher M, Perrot M, Duchesnay E (2011) Scikit-learn: machine learning in python. J Mach Learn Res 12:2825

    MathSciNet  MATH  Google Scholar 

  27. Quinlan JR (2004) Data mining tools see5 and c5. 0. http://www.rulequest.com/see5-info.html

  28. Quinlan JR (2014) C4. 5: programs for machine learning. Elsevier, New York

    Google Scholar 

  29. R Core Team (2019) R foundation for statistical computing. R: A Language and Environment for Statistical Computing. http://www.R-project.org/

  30. Sharman K (2018) Common test conditions for HM video coding experiments. JCT-VC Document AC1100

  31. Sullivan GJ, Ohm J, Han W, Wiegand T (2012) . IEEE Trans Circuits Syst Video Technol 22(12):1649. https://doi.org/10.1109/TCSVT.2012.2221191

    Article  Google Scholar 

  32. U.V. Group (2019) Ultra Video Group. Tampere University of Technology. http://ultravideo.cs.tut.fi/

  33. Valizadeh S, Nasiopoulos P, Ward R (2021) Improving compression efficiency of HEVC using perceptual coding. Multimed Tools Appl 80:1

    Article  Google Scholar 

  34. Vanne J, Viitanen M, Hämäläinen TD (2014) Efficient mode decision schemes for HEVC inter prediction. IEEE Trans Circuits Syst Video Technol 24 (9):1579. https://doi.org/10.1109/TCSVT.2014.2308453

    Article  Google Scholar 

  35. Video Technology Research Group (ViTech) GitHub Repository. https://github.com/vitech-ufpel/LBME

  36. Wang Y, Fan X, Xiong R, Zhao D, Gao W (2021) Neural network-based enhancement to inter prediction for video coding. IEEE Trans Circuits Syst Video Technol 1–1

  37. Zhang Y, Zhang C, Fan R, Ma S, Chen Z, Kuo CJ (2019) Recent advances on hevc inter-frame coding: from optimization to implementation and beyond. IEEE Trans Circuits Syst Video Technol 1–1

  38. Zhu C, Lin X, Chau L-P (2002) Hexagon-based search pattern for fast block motion estimation. IEEE Trans Circuits Syst Video Technol 12(5):349. https://doi.org/10.1109/TCSVT.2002.1003474

    Article  Google Scholar 

  39. Zhu S, Ma K-K (2000) A new diamond search algorithm for fast block-matching motion estimation. IEEE Trans Image Process 9(2):287. https://doi.org/10.1109/83.821744

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported by the Brazilian Agency for Scientific and Technological Development (CNPq, Brazil). This research was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) – Finance code 001, the Conselho Nacional de Desenvolvimento Científico e Tecnológico - Brasil (CNPq), and the Fundação de Amparo à Pesquisa do Rio Grande do Sul - Brasil (FAPERGS).

Author information

Authors and Affiliations

  1. Video Technology Research Group (ViTech), Graduate Program in Computing (PPGC), Federal University of Pelotas (UFPel), Pelotas, Brazil

    Paulo Goncalves, Guilherme Correa, Luciano Agostini & Marcelo Porto

Authors
  1. Paulo Goncalves
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guilherme Correa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Luciano Agostini
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Marcelo Porto
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Guilherme Correa.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Goncalves, P., Correa, G., Agostini, L. et al. Learning-based bypass zone search algorithm for fast motion estimation. Multimed Tools Appl 82, 3535–3560 (2023). https://doi.org/10.1007/s11042-022-13094-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-022-13094-6

Keywords

Search

Navigation