ENG
РУС
Search
Menu
About the Edition
Open Access Statement
Editorial Board
Editorial Policy
Editorial Ethics
Rules for peer-review
Rules for presentation of papers
Forms of Submitted Documents
Recommendations for the Design of References to Our Journal
Editorial Staff
Information for Subscribers
Summaries of the Issue
List of Authors
Issues
Publishers license agreement
Procedure of work with personal data
Publications
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.
Partners













































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 


Abstract
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

References
  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. https://doi.org/10.11591/ijece.v7i1.pp216-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. https://doi.org/10.1007/s10586-017-1478-z
  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. https://doi.org/10.1134/s1054661822010072
  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. https://doi.org/10.1007/s11554-021-01188-7
  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. https://doi.org/10.1117/1.jei.26.2.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. https://doi.org/10.1364/ao.424238
  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. https://doi.org/10.4018/ijec.316773
  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. https://doi.org/10.1117/12.2623419
  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. https://doi.org/10.1007/s11042-018-6353-2
  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. https://doi.org/10.1007/s11760-016-0906-5
  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. https://doi.org/10.1007/s11265-020-01574-7
  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. https://doi.org/10.9790/1676-0441418
  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. https://doi.org/10.1109/pcs56426.2022.10018044
  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. https://doi.org/10.1109/tip.2002.806251
  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. https://doi.org/10.1007/s11277-023-10237-2
  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. https://doi.org/10.1007/s00034-021-01850-2
  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. https://doi.org/10.1007/s11554-016-0593-z
  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. https://doi.org/10.1109/iscas.2005.1465369
  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. https://doi.org/10.1007/s00034-022-02182-5
  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. https://doi.org/10.1007/s41870-022-01067-9
  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. https://doi.org/10.1109/tensymp54529.2022.9864538
  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. https://doi.org/10.1109/acct.2015.133
  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. https://doi.org/10.1109/iccv.2019.00355
  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. https://doi.org/10.1117/12.2505732
  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. https://doi.org/10.1007/s00034-020-01637-x
  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. https://doi.org/10.1007/s00542-020-05167-z
  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. https://doi.org/10.1145/3494525
  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. https://doi.org/10.3169/mta.11.1


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.

Яндекс.Метрика