The International Arab Journal of Information Technology (IAJIT)


Modified Cuckoo Search Algorithm for Motion Vector Estimation

Motion estimation and motion compensation are the accepted process in H.264 and H.265 video coding standard to reduce temporal redundancy. Several fast block matching algorithms have been developed to reduce the calculation cost in the motion estimation process. But quick block matching algorithms often lead to a local minimum. Several researchers used different population-based nature-inspired algorithms to perform block matching. Algorithms like genetic algorithm, differential evolution, particle swarm optimization were used in numerous motion estimation algorithms. Different algorithms used a fitness approximation strategy to reduce computation cost. Jaya algorithm-based block matching is the most efficient block matching algorithm in the available literature. Jaya algorithm is free from algorithmic specific parameter which speeds up the process. This article proposes a few modifications to the traditional cuckoo search algorithm and then, a block matching algorithm was proposed based on the modified cuckoo search algorithm. Fitness approximation, adaptive termination, and zero motion prejudgment modules were used with the modified cuckoo search algorithm to reduce the number of redundant calculations. The performance of the proposed algorithm was compared with the exhaustive search algorithm and other benchmarking algorithms in terms of Peak Signal to Noise Ratio (PSNR), Structure Similarity Index (SSIM), and average search point required to calculate a motion vector for a block. The proposed algorithm delivers better performance compared to the benchmarking algorithms.


[1] Abramowski A., “Towards H. 265 Video Coding Standard,” in Proceedings of the Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments, Poland, pp. 387-393, 2011.

[2] Acharjee S., Chakraborty S., Karaa W., Azar A., and Dey N., “Performance Evaluation of Different Cost Functions in Motion Vector Estimation,” International Journal of Service Science, Management, Engineering, and Technology, vol. 5, no. 1, pp. 45-65, 2014.

[3] Barjatya A., “Block Matching Algorithms for Motion Estimation,” IEEE Transactions Evolution Computation, vol. 8, no. 3, pp. 225-239, 2004.

[4] Barron J., Fleet D., and Beauchemin S., “Performance of Optical Flow Techniques,” International Journal of Computer Vision, vol. 12 no. 1, pp. 43-77, 1994.

[5] Bhattacharjee K. and Kumar S., “A Novel Block Matching Algorithm Based on Cuckoo Search,” in Proceedings of the 2nd International Conference on Telecommunication and Networks, Noida, pp. 1-5, 2017.

[6] Chow K. and Liou M., “Genetic Motion Search Algorithm for Video Compression,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 3, no. 6, pp. 440-445, 1993.

[7] Cuevas E., Zaldivar D., Pérez-Cisneros M, and Oliva D., “Block-matching Algorithm Based on Differential Evolution for Motion Estimation,” Engineering Applications of Artificial Intelligence, vol. 26, no. 1, pp. 488-498, 2013.

[8] Cuevas E., Zaldívar D., Pérez-Cisneros M., Sossa H., and Osuna V., “Block Matching Algorithm for Motion Estimation Based on Artificial Bee Colony (ABC),” Applied Soft Computing, vol. 13, no. 6, pp. 3047-3059, 2013.

[9] Dash B., Rup S., Mohanty F., and Swamy M., “A hybrid Block-Based Motion Estimation Algorithm Using JAYA for Video Coding Techniques,” Digital Signal Processing, vol. 88, pp. 160-171, 2019.

[10] Dixit A., Mani A., and Bansal R., Intelligence Enabled Research, Springer Singapore, 2021.

[11] Fossøy F., Sorenson M., Liang W., Ekrem T., Moksnes A., Møller A., Rutila J., Røskaft E., Takasu F., Yang C., and Stokke B., “Ancient Origin and Maternal Inheritance of Blue Cuckoo Eggs,” Nature Communications, vol. 7, no. 1, pp. 10272, pp. 1-6, 2016.

[12] Jain J. and Jain A., “Displacement Measurement and its Application in Interframe Image Coding,” IEEE Transactions on Communications, vol. 29, no. 12, pp. 1799-1808, 1981.

[13] Li X., Xiao N., Claramunt C., and Lin H., “Initialization Strategies to Enhancing the Performance of Genetic Algorithms for the P- Median Problem,” Computers and Industrial Engineering, vol. 61 no. 4, pp. 1024-1034, 2011.

[14] Lin C., and Wu J., “A Lightweight Genetic Block- Matching Algorithm for Video Coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, no. 4, pp. 386-392, 1998.

[15] Liu L. and Feig E., “A block-based Gradient Descent Search Algorithm for Block Motion Estimation in Video Coding,” IEEE Transactions 348 The International Arab Journal of Information Technology, Vol. 20, No. 3, May 2023 on Circuits and Systems for Video Technology, vol. 6, no. 4, pp. 419-422, 1996.

[16] Nie Y. and Ma K., “Adaptive Rood Pattern Search for Fast Block-matching Motion Estimation,” IEEE Transactions on Image Processing, vol. 11, no. 12, pp. 1442-1449, 2002.

[17] Ong Y., Nair P., and Keane A., “Evolutionary Optimization of Computationally Expensive Problems via Surrogate Modeling,” AIAA Journal, vol. 41, no. 4, pp. 687-696, 2003.

[18] Pandian S., Bala G., and Anitha J., “A Pattern Based PSO Approach for Block Matching in Motion Estimation,” Engineering Applications of Artificial Intelligence, vol. 26, no. 8, pp. 1811- 1817, 2013.

[19] Parmar N. and Sunwoo M., “Enhanced Test Zone Search Motion Estimation Algorithm for HEVC,” in Proceedings of the International Soc Design Conference, Jeju, pp. 260-261, 2014.

[20] Rao R., “Jaya: A Simple and New Optimization Algorithm for Solving Constrained and Unconstrained Optimization Problems,” International Journal of Industrial Engineering Computations, vol. 7, no. 1, pp. 19- 34, 2016.

[21] Salih Y. and George L., “Improved Hybrid Block- based Motion Estimation for Inter-frame Coding,” Circuits, Systems, and Signal Processing, vol. 40, no. 7, pp. 3500-3522, 2021.

[22] Shi L. and Rasheed K., Computational Intelligence in Expensive Optimization Problems, Springer Berlin, pp. 3-28. 2010

[23] Tourapis A., “Enhanced Predictive Zonal Search for Single and Multiple Frame Motion Estimation,” in Proceedings of the Visual Communications and Image Processing, San Jose, 4671, pp. 1069-1079, 2002.

[24] Viswanathan G., Afanasyev V., Buldyrev S., Havlin Sh., da Luz M., Raposo E., and Eugene Stanley H., “Lévy Flights in Random Searches,” Physica A: Statistical Mechanics and its Applications, vol. 282, no. 1-2, pp. 1-12, 2000.

[25] Walker D. and Rao K., “Improved Pel-recursive Motion Compensation,” IEEE Transactions on Communications, vol. 32, no. 10, pp. 1128-1134, 1984.

[26] Wang J., Liu T., Yuan Z., and Shang Y., “A Robust Saliency Integrated Method for Monocular Motion Estimation,” in Proceedings of the International Conference on Machine Vision and Applications, Aichi, pp. 49-54, 2021.

[27] Wu L., Yang Z., Jian M., Shen J., Yang Y., and Lang X., “Global Motion Estimation with Iterative Optimization-Based Independent Univariate Model for Action Recognition,” Pattern Recognition, vol. 116, pp. 107925, 2021.

[28] Xiao N., “A Unified Conceptual Framework for Geographical Optimization Using Evolutionary Algorithms,” Annals of the Association of American Geographers, vol. 98, no. 4, pp. 795- 817, 2008.

[29] Yang X. and Deb S., “Cuckoo Search via Lévy Flights,” in Proceedings of the World Congress on Nature and Biologically Inspired Computing, Coimbatore, 2009.

[30] Zebhi S., Almodarresi S., and Abootalebi V., “Human Activity Recognition Based on Transfer Learning with Spatio-Temporal Representations,” The International Arab Journal of Information Technology, vol. 18, no. 6, pp. 839-845, 2021.