ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2023-23-5-955-966ntv-128Research ArticleКОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИCOMPUTER SCIENCEНовый эффективный адаптивный алгоритм шаблонного поиска для оценки движенияA new efficient adaptive rood pattern search motion estimation algorithmhttps://orcid.org/0000-0002-2501-7584ШейкерА. Ш.ShakerSh. A.

Шейкер Абделаал Шерин — магистр, аспирант

Синток, 06000 

Sherin A. Shaker — Magister, PhD Student

Sintok, 06000

Shereenshaker2004@yahoo.comhttps://orcid.org/0009-0008-2724-1281АрифА. С. Ч.М.ArifA. S. C. M.

Ариф Ахмад Суки Че Мохамед — PhD, преподаватель, преподаватель

Синток, 06000 

Ahmad Suki C. M. Arif – PhD, Lecturer

Sintok, 06000

suki1207@uum.edu.myhttps://orcid.org/0000-0003-3544-2434ФазеаЮ.FazeaY.

Фазеа Юсеф — PhD, доцент

sc 56803894200

Хантингтон, 25755 

Yousef Fazea — PhD, Assistant Professor

 sc 56803894200

Huntington, 25755

fazeaalnades@marshall.eduУниверситет Утра МалайзииМалайзияUniversity Utara MalaysiaMalaysiaУниверситет МаршаллСоединённые Штаты АмерикиMarshall UniversityUnited States202313122024235955966Copyright © Шейкер А., Ариф А., Фазеа Ю., 20242024Шейкер А., Ариф А., Фазеа Ю.Shaker S., Arif A., Fazea Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ntv.elpub.ru/jour/article/view/128

Оценка движения играет решающую роль при кодировании видео. Адаптивный алгоритм шаблонного поиска (Adaptive Rood Pattern Search, ARPS) является известным алгоритмом быстрой оценки движения. При этом ARPS имеет следующие ограничения: отсутствие точного начального вектора движения; фиксированный порог предварительного суждения о нулевом движении (Zero Motion Prejudgment, ZMP), неподходящий для видеопоследовательностей с быстрым движением; повторяющееся использование шаблона единичного движения (Unit Rood Pattern, URP), что приводит к увеличению вычислительной сложности. Для решения данных ограничений предложен новый алгоритм под названием «Эффективный адаптивный алгоритм шаблонного поиска» (Efficient Adaptive Rood Pattern Search, EARPS). В основе EARPS лежит алгоритм полного поиска, который получает оптимальные векторы движения для первого столбца в каждом кадре, принимает динамический порог ZMP, который адаптируется к различным скоростям движения в видеопоследовательностях, и использует URP один раз для уменьшения вычислительных затрат. Выполнена оценка и сравнение производительности нового алгоритма EARPS и алгоритма ARPS с использованием различных видеопоследовательностей для различных скоростей движения. Количество точек поиска и пиковое отношение сигнал-шум (Peak Signal-to-Noise Ratio, PSNR) использованы для количественной оценки сложности и точности вычислений. Экспериментальные результаты показали, что EARPS превосходит ARPS с точки зрения вычислительной сложности, сохраняя при этом высокую степень точности PSNR. Основной вклад предложенного алгоритма оценки движения EARPS заключается в достижении высокой скорости с приемлемой точностью, независимо от скорости движения в видеокадрах. Алгоритм EARPS по сравнению с ARPS, обеспечил более эффективный метод оценки движения с более широкой применимостью в обработке видео. Полученный результат является значительным вкладом в разработку эффективных алгоритмов оценки движения.

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.

оценка движениявычислительная сложностьARPSZMP и PSNRmotion estimationcomputational complexityARPSZMPPSNRReferencesAdapa V.P., Vuyyuru A. A survey on block matching algorithms for video coding // International Journal of Electrical and Computer Engineering (IJECE). 2017. V. 7. N 1. P. 216–224. https://doi.org/10.11591/ijece.v7i1.pp216-224Adapa 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-224Manikandan 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. V. 22. N S5. P. 11773–11780. https://doi.org/10.1007/s10586-017-1478-zManikandan 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-zSrinivas Rao K., Paramkusam A.V. Block matching algorithms for the estimation of motion in image sequences // Pattern Recognition and Image Analysis. 2022. V. 32. N 1. P. 33–44. https://doi.org/10.1134/s1054661822010072Srinivas 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/s1054661822010072Agha S., Khan M., Jan F. Efficient fast motion estimation algorithm for real-time applications // Journal of Real-Time Image Processing. 2022. V. 19. N 2. P. 403–413. https://doi.org/10.1007/s11554-021-01188-7Agha 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-7Sehairi K., Chouireb F., Meunier J. Comparative study of motion detection methods for video surveillance systems // Journal of Electronic Imaging. 2017. V. 26. N 2. P. 023025. https://doi.org/10.1117/1.jei.26.2.023025Sehairi 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.023025Pang 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. V. 60. N 16. P. 4746. https://doi.org/10.1364/ao.424238Pang 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.424238Ravi P.R. Diamond search optimization-based technique for motion estimation in video compression // International Journal of e- collaboration. 2023. V. 19. N 3. P. 1–4. https://doi.org/10.4018/ijec.316773Ravi 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.316773Jiao S., Wang Y., Luan L., Yu X. Research on fast motion estimation in H264 coding // Proceedings of SPIE. 2022. V. 12083. P. 120832T. https://doi.org/10.1117/12.2623419Jiao 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.2623419Pan Z., Zhang R., Ku W., Wang Y. Adaptive pattern selection strategy for diamond search algorithm in fast motion estimation // Multimedia Tools and Applications. 2019. V. 78. N 2. P. 2447–2464. https://doi.org/10.1007/s11042-018-6353-2Pan 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-2Amirpour H., Mousavinia A. A dynamic search pattern motion estimation algorithm using prioritized motion vectors // Signal, Image and Video Processing. 2016. V. 10. N 8. P. 1393–1400. https://doi.org/10.1007/s11760-016-0906-5Amirpour 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-5Arnaudov P., Ogunfunmi T. Dynamically adaptive fast motion estimation algorithm for HD video // Journal of Signal Processing Systems. 2020. V. 92. N 10. P. 1115–1131. https://doi.org/10.1007/s11265-020-01574-7Arnaudov 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-7Vanshree V. A novel adaptive rood pattern search algorithm // IOSR Journal of Electrical and Electronics Engineering. 2013. V. 4. N 4. P. 14–18. https://doi.org/10.9790/1676-0441418Vanshree 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-0441418Schinde T. Adaptive pixel-based direction oriented fast motion estimation for predictive coding // Proc. of the 2022 Picture Coding Symposium (PCS). 2022. P. 331–335. https://doi.org/10.1109/pcs56426.2022.10018044Schinde 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.10018044Nie Y., Ma K.-K. Adaptive rood pattern search for fast block-matching motion estimation // IEEE Transactions on Image Processing. 2002. V. 11. N 12. P. 1442–1449. https://doi.org/10.1109/tip.2002.806251Nie 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.806251Madhuvappan 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. V. 130. N 4. P. 2305–2325. https://doi.org/10.1007/s11277-023-10237-2Madhuvappan 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-2Shajin F.H., Rajesh P., Raja M.R. An efficient VLSI 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. V. 41. N 3. P. 1751–1774. https://doi.org/10.1007/s00034-021-01850-2Shajin F.H., Rajesh P., Raja M.R. An efficient VLSI 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-2Arora 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. V. 16. N 4. P. 989– 1005. https://doi.org/10.1007/s11554-016-0593-zArora 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-zYi X., Ling N. Fast pixel-based video scene change detection // Proc. of the IEEE International Symposium on Circuits and Systems (ISCAS). 2005. P. 3443–3446. https://doi.org/10.1109/iscas.2005.1465369Yi 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.1465369Mukherjee R., Biswas B., Vinod I.G. Half-way stop adaptive pattern search algorithm for motion estimation and dedicated VLSI architecture // Circuits, Systems, and Signal Processing. 2023. V. 42. N 3. P. 1617–1638. https://doi.org/10.1007/s00034-022-02182-5Mukherjee R., Biswas B., Vinod I.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-5Mishra A.K., Kohli N. Enhanced adaptive threshold algorithm with weighted search points for fast motion estimation // International Journal of Information Technology. 2023. V. 15. N 2. P. 845–857. https://doi.org/10.1007/s41870-022-01067-9Mishra 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-9Deepa M.T. PSNR based analysis of block matching algorithms for motion estimation // International Journal of Scientific & Engineering Research. 2013. V. 4. N 8. P. 5518.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.Mukkerjee R., Puniyani A. A fast adaptive algorithm for sub-pixel motion estimation // Proc. of the IEEE Region 10 Symposium (TENSYMP). 2022. P. 1–5. https://doi.org/10.1109/tensymp54529.2022.9864538Mukkerjee 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.9864538Arora 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. P. 138–142. https://doi.org/10.1109/acct.2015.133Arora 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.133Rippel 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. P. 3454–3463. https://doi.org/10.1109/iccv.2019.00355Rippel 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.00355Kerfa D., Saidane A. An efficient algorithm for fast block matching motion estimation using an adaptive threshold scheme // Proceedings of SPIE. 2019. V. 10996. P. 109960C. https://doi.org/10.1117/12.2505732Kerfa 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.2505732Salih Y.A., George L.E. Improved hybrid block-based motion estimation for inter-frame coding // Circuits, Systems, and Signal Processing. 2021. V. 40. N 7. P. 3500–3522. https://doi.org/10.1007/s00034-020-01637-xSalih 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-xChatterjee S.K., Vittapu S.K., Kundu S. Prediction-biased diamond search algorithm: a new approach to reduce motion estimation complexity // Microsystem Technologies. 2021. V. 27. N 5. P. 2027– 2032. https://doi.org/10.1007/s00542-020-05167-zChatterjee 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-zRoberto E Souza M., Maia H.D.A., Pedrini H. Survey on digital video stabilization: concepts, methods, and challenges // ACM Computing Surveys. 2023. V. 55. N 3. P. 1–37. https://doi.org/10.1145/3494525Roberto 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/3494525Kidani 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. V. 11. N 1. P. 1–12. https://doi.org/10.3169/mta.11.1Kidani 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

The authors declare that there are no conflicts of interest present.