doi: 10.17586/2226-1494-2023-23-5-955-966

A new efficient adaptive rood pattern search motion estimation algorithm

S. A. Shaker, A. Arif, Y. Fazea

Read the full article  ';
Article in English

For citation:
Shaker S.A., Arif A.S., Fazea Y. A new efficient adaptive rood pattern search motion estimation algorithm. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2023, vol. 23, no. 5, pp. 955–966. doi: 10.17586/2226-1494-2023-23-5-955-966 

Motion estimation plays a crucial role in video coding; the Adaptive Rood Pattern Search (ARPS) algorithm is a well known fast motion estimation algorithm. However, ARPS has certain limitations, such as the lack of an accurate starting motion vector, a fixed Zero Motion Prejudgment (ZMP) threshold unsuitable for fast motion video sequences, and the repetitive use of a Unit Rood Pattern (URP) resulting in increased computational complexity. To address these issues, this paper proposes a novel algorithm called Efficient Adaptive Rood Pattern Search (EARPS). EARPS overcomes these limitations by employing the Full Search algorithm to obtain optimal motion vectors for the first column in each frame, adopting a dynamic ZMP threshold that adapts to varying motion speeds in video sequences and utilizing URP only once to reduce computational overhead. The performance of the new proposed EARPS algorithm is evaluated and compared with that of ARPS algorithm using various video sequences with different motion speeds. The number of searching points and Peak Signal-to-Noise Ratio (PSNR) are used to quantify computing complexity and accuracy. The experimental findings show that EARPS surpasses ARPS in terms of computing complexity while retaining a decent degree of PSNR accuracy. The proposed EARPS motion estimation algorithm main contribution is to achieve high speed with reasonable accuracy, regardless of the type of motion speed in the video frames. The EARPS algorithm offers a substantial advancement over ARPS, delivering a more efficient motion estimation method with broader applicability in video processing. It represents a significant contribution to the development of effective motion estimation algorithms.

Keywords: motion estimation, computational complexity, ARPS, ZMP, PSNR

  1. Adapa V.P., Vuyyuru A. A survey on block matching algorithms for video coding. International Journal of Electrical and Computer Engineering (IJECE), 2017. vol. 7, no. 1, pp. 216–224.
  2. Manikandan L.C., Nair S.A.H., Sanal Kumar K.P., Selvakumar R.K. A study and analysis on block matching algorithms for motion estimation in video coding. Cluster Computing, 2019, vol. 22, no. S5, pp. 11773–11780.
  3. Srinivas Rao K., Paramkusam A.V. Block matching algorithms for the estimation of motion in image sequences. Pattern Recognition and Image Analysis, 2022, vol. 32, no. 1, pp. 33–44.
  4. Agha S., Khan M., Jan F. Efficient fast motion estimation algorithm for real-time applications. Journal of Real-Time Image Processing, 2022, vol. 19, no. 2, pp. 403–413.
  5. Sehairi K., Chouireb F., Meunier J. Comparative study of motion detection methods for video surveillance systems. Journal of Electronic Imaging, 2017, vol. 26, no. 2, pp. 023025.
  6. Pang S., Zhang X., Li H., Lu Y. Robust block-matching algorithm for motion estimation using an anti-interference similarity criterion and the bilateral optimization scheme. Applied Optics, 2021, vol. 60, no. 16, pp. 4746.
  7. Ravi P.R. Diamond search optimization-based technique for motion estimation in video compression. International Journal of e- collaboration, 2023, vol. 19, no. 3, pp. 1–4.
  8. Jiao S., Wang Y., Luan L., Yu X. Research on fast motion estimation in H264 coding. Proceedings of SPIE, 2022, vol. 12083, pp. 120832T.
  9. Pan Z., Zhang R., Ku W., Wang Y. Adaptive pattern selection strategy for diamond search algorithm in fast motion estimation. Multimedia Tools and Applications, 2019, vol. 78, no. 2, pp. 2447–2464.
  10. Amirpour H., Mousavinia A. A dynamic search pattern motion estimation algorithm using prioritized motion vectors.Signal, Image and Video Processing,2016,vol. 10,no. 8,pp. 1393–1400.
  11. Arnaudov P., Ogunfunmi T. Dynamically adaptive fast motion estimation algorithm for HD video.Journal of Signal Processing Systems, 2020, vol. 92, no. 10, pp. 1115–1131.
  12. Vanshree V. A novel adaptive rood pattern search algorithm. IOSR Journal of Electrical and Electronics Engineering, 2013, vol. 4, no. 4, pp. 14–18.
  13. Schinde T. Adaptive pixel-based direction oriented fast motion estimation for predictive coding. Proc. of the 2022 Picture Coding Symposium (PCS), 2022, pp. 331–335.
  14. Nie Y., Ma K.-K.Adaptive rood pattern search for fast block-matching motion estimation. IEEE Transactions on Image Processing, 2002, vol. 11, no. 12, pp. 1442–1449.
  15. Madhuvappan C.A., Ramesh J. An efficient VLSI architecture for fast motion estimation exploiting zero motion prejudgment technique and a new quadrant depended on search algorithm in HEVC. Wireless Personal Communications, 2023, vol. 130, no. 4, pp. 2305–2325.
  16. Shajin F.H., Rajesh P., Raja M.R.An efficientVLSI architecture for fast motion estimation exploiting zero motion prejudgment technique and a new quadrant-based search algorithm in HEVC. Circuits, Systems, and Signal Processing, 2022, vol. 41, no. 3, pp. 1751–1774.
  17. Arora S.M., Rajpal N., Khanna K. A new approach with enhanced accuracy in ZMP for motion estimation in real time applications.Journal of Real-Time Image Processing, 2019, vol. 16, no. 4, pp. 989–1005.
  18. Yi X., Ling N. Fast pixel-based video scene change detection. Proc. of the IEEE International Symposium on Circuits and Systems (ISCAS), 2005, pp. 3443–3446.
  19. Mukherjee R., Biswas B., VinodI.G. Half-way stop adaptive pattern search algorithm for motion estimation and dedicated VLSI architecture.Circuits, Systems, and Signal Processing, 2023, vol. 42, no. 3, pp. 1617–1638.
  20. Mishra A.K., Kohli N. Enhanced adaptive threshold algorithm with weighted search points for fast motion estimation. International Journal of Information Technology, 2023, vol. 15, no. 2, pp. 845–857.
  21. Deepa M.T. PSNR based analysis of block matching algorithms for motion estimation. International Journal of Scientific & Engineering Research, 2013, vol. 4, no. 8, pp. 5518.
  22. Mukkerjee R., Puniyani A. A fast adaptive algorithm for sub-pixel motion estimation. Proc. of the IEEE Region 10 Symposium (TENSYMP), 2022, pp. 1–5.
  23. Arora S.M., Rajpal N., Purwar R. Dynamic pattern search algorithm with zero motion prejudgment for fast motion estimation. Proc. of the Fifth International Conference on Advanced Computing & Communication Technologies, 2015, pp. 138–142.
  24. Rippel O., Nair S., Lew C., Branson S., Anderson A., Bourdev L. Learned video compression. Proc.of the IEEE/CVF International Conference On Computer Vision, 2019, pp. 3454–3463.
  25. Kerfa D., Saidane A. An efficient algorithm for fast block matching motion estimation using an adaptive threshold scheme. Proceedings of SPIE, 2019, vol. 10996, pp. 109960C.
  26. Salih Y.A., George L.E. Improved hybrid block-based motion estimation for inter-frame coding.Circuits, Systems, and Signal Processing, 2021, vol. 40, no. 7, pp. 3500–3522.
  27. Chatterjee S.K., Vittapu S.K., Kundu S. Prediction-biased diamond search algorithm: a new approach to reduce motion estimation complexity. Microsystem Technologies, 2021, vol. 27, no. 5, pp. 2027–2032.
  28. Roberto E Souza M., Maia H.D.A., Pedrini H. Survey on digital video stabilization: concepts, methods, and challenges. ACM Computing Surveys, 2023, vol. 55, no. 3, pp. 1–37.
  29. Kidani Y., Unno K., Kawamura K., Watanabe H. Memory bandwidth constrained overlapped block motion compensation for video coding. ITE Transactions on Media Technology and Applications, 2023, vol. 11, no. 1, pp. 1–12.

Creative Commons License

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