Heuristic Algorithms of Coincidence for the Estimation of Movements in Compression of Images
Applied and Computational Mathematics
Volume 9, Issue 3, June 2020, Pages: 85-95
Received: Sep. 14, 2019;
Accepted: May 25, 2020;
Published: Jun. 8, 2020
Views 47 Downloads 59
Fernando José Hernández Gómez, Department of Mathematics, Faculty of Science and Engineering, UNAN, Managua, Nicaragua
The NP-Completeness theory states that exact and efficient algorithms are unlikely to exist for the class of NP-difficult problems. One way to deal with NP hardness is to relax the optimality requirement and look for solutions instead that are close to the optimum. This is the main idea behind the approximation algorithms, which are called heuristic or metaheuristic. The problem of motion estimation is a process with a high degree of computational complexity, it requires sufficient memory space and execution time. It represents the cost of static, dynamic and video image sequence coding. The main task is to minimize the distortion rate and improve visual quality. This makes research in the field of coding, image compression and video focus on finding efficient algorithms to carry out the estimation of movement in a reasonable time. If a list of images of n elements is analyzed, there are feasible solutions. So, an exhaustive search is too slow, even for small values of the solution space. Therefore, from a practical point of view, it is crucial to have efficient and fast heuristic algorithms that avoid thorough search. In this investigation we design and implement heuristic algorithms, based on the frequency domain, which are applied on the coefficients of the discrete transform of the cosine and wavelets. Also, we propose temporal domain algorithms such as block-matching algorithms, which focus your search on the maximum coincidence of the current image with the reference one. The algorithms used during the implementation of this research work were written with the mathematical programming language MATLAB. In addition, we review the basic concepts of image processing, video, compression algorithms and motion estimation frequently used. The evaluation of the algorithms was carried out with a set of images provided by a previous acquisition system. We show the improvement of visual quality, the amount of compressed or reconstructed information and the behavior of the methods in the search for similarities between pixels or images. Finally, we contribute to the dissemination of new lines of scientific research that lead to the expansion and improvement of the study, the generation of new knowledge, since it is a young area within the Education discipline of Nicaragua.
Fernando José Hernández Gómez,
Heuristic Algorithms of Coincidence for the Estimation of Movements in Compression of Images, Applied and Computational Mathematics.
Vol. 9, No. 3,
2020, pp. 85-95.
Ahmed, Z., Hussain, A. J., Khan, W., Baker, T., Al-Askar, H., Lunn, J.,... & Liatsis, P. (2020). Lossy and Lossless Video Frame Compression: A Novel Approach for High-Temporal Video Data Analytics. Remote Sensing, 12 (6), 1004.
Boonthep, N., & Chamnongthai, K. (2019). A Method of Motion-Estimation-Based H. 264 Video Coding Using Optimal Search-Range. Wireless Personal Communications, 1-18.
Brox, T., Bruhn, A., Papenberg, N., and Weickert, J. (2004). “High accuracy optical flow estimation based on a theory for warping’’. Computer Vision-ECCV, 25-36.
CH, C. S., Ratnam, J. V. K., and Student, P. G. “Comparison of Fast Block Matching Algorithms for Motion Estimation’’.
Chen, W. H., Smith, C. H., and Fralick, S. C. (1977). “A fast computational algorithm for the discrete cosine transform’’. IEEE Transactions on communications, 25 (9), 1004-1009.
Cheung, C. H., and Po, L. M. (2002). “A novel cross-diamond search algorithm for fast block motion estimation’’. IEEE transactions on Circuits and Systems for Video Technology, 12 (12), 1168-1177.
Cook, S. A. (1971, May). “The complexity of theorem-proving procedures’’. In Proceedings of the third annual ACM symposium on Theory of computing (pp. 151-158). ACM.
Cuevas, E., Zaldívar, D., Pérez-Cisneros, M., Sossa, H., Osuna, V. (2013). “Block matching algorithm for motion estimation based on Artificial Bee Colony (ABC)’’, Applied Soft Computing Journal 13 (6), pp. 3047-3059.
DUFAUX, F. (2010). “Motion Estimation Techniques for Digital TV: A Review and a New Contribution’’.
Ghanbari, M. (1990). “The cross-search algorithm for motion estimation (image coding)’’. IEEE Transactions on Communications, 38 (7), 950-953.
Gogoi, S., & Peesapati, R. (2019, December). A Hybrid Motion Estimation Search Algorithm for HEVC/H. 265. In 2019 IEEE International Symposium on Smart Electronic Systems (iSES)(Formerly iNiS) (pp. 129-132). IEEE.
Glover, F. W., and Kochenberger, G. A. (Eds.). (2006). “Handbook of metaheuristics’’. (Vol. 57). Springer Science & Business Media.
Hernández Gómez, F. J. (2017). “Algoritmos Heurísticos de Coincidencia para la Estimación de Movimientos en Compresión de Imágenes’’. (Doctoral dissertation, Universidad Nacional Autónoma de Nicaragua, Managua).
Herbst Evan, Ren Xiaofeng, and Fox Dieter. (2013) “Rgb-d flow: Dense 3-d motion estimation using color and depth’’. In Robotics and Automation (ICRA), IEEE International Conference on, pages 2276-2282. IEEE, 2013.
Li, R., Zeng, B., and Liou, M. L. (1994). “A new three-step search algorithm for block motion estimation’’. IEEE transactions on circuits and systems for video technology, 4 (4), 438-442.
Lucas, B. D., & Kanade, T. (1981). “An iterative image registration technique with an application to stereo vision’’. In IJCAI, pages 674-679, 1981.
Nie, Y., and Ma, K. K. (2002). “Adaptive rood pattern search for fast block-matching motion estimation’’. IEEE Transactions on image processing, 11 (12), 1442-1449.
Ortega-Sánchez, N., Cuevas, E., Pérez, M. A., & Osuna-Enciso, V. (2020). Clustering Data Using Techniques of Image Processing Erode and Dilate to Avoid the Use of Euclidean Distance. In Applications of Hybrid Metaheuristic Algorithms for Image Processing (pp. 187-203). Springer, Cham.
Pyko, N. S., Pyko, S. M., Mikus, O. A., & Filippov, B. S. (2020, January). Motion Vectors Estimation for Video Encoding Based on the Macroblock Signatures. In 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus) (pp. 1417-1420). IEEE.
Reisslein, M. (2005-2011). “Video Trace Library’’. Arizona State University, [online] Available: http://trace.eas.asu.edu.
Yaakob, R., Aryanfar, A., Halin, A. A., and Sulaiman, N. (2013). “A comparison of different block matching algorithms for motion estimation’’. Procedia Technology, 11, 199-205.