Applied and Computational Mathematics

| Peer-Reviewed |

Heuristic Algorithms of Coincidence for the Estimation of Movements in Compression of Images

Received: 14 September 2019    Accepted: 25 May 2020    Published: 08 June 2020
Views:       Downloads:

Share This Article

Abstract

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.

DOI 10.11648/j.acm.20200903.15
Published in Applied and Computational Mathematics (Volume 9, Issue 3, June 2020)
Page(s) 85-95
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Movement Estimation, Heuristics, Discrete Cosine Transform and Wavelets, Search Algorithm

References
[1] 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.
[2] Boonthep, N., & Chamnongthai, K. (2019). A Method of Motion-Estimation-Based H. 264 Video Coding Using Optimal Search-Range. Wireless Personal Communications, 1-18.
[3] 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.
[4] CH, C. S., Ratnam, J. V. K., and Student, P. G. “Comparison of Fast Block Matching Algorithms for Motion Estimation’’.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] DUFAUX, F. (2010). “Motion Estimation Techniques for Digital TV: A Review and a New Contribution’’.
[10] Ghanbari, M. (1990). “The cross-search algorithm for motion estimation (image coding)’’. IEEE Transactions on Communications, 38 (7), 950-953.
[11] 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.
[12] Glover, F. W., and Kochenberger, G. A. (Eds.). (2006). “Handbook of metaheuristics’’. (Vol. 57). Springer Science & Business Media.
[13] 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).
[14] 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.
[15] 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.
[16] Lucas, B. D., & Kanade, T. (1981). “An iterative image registration technique with an application to stereo vision’’. In IJCAI, pages 674-679, 1981.
[17] 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.
[18] 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.
[19] 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.
[20] Reisslein, M. (2005-2011). “Video Trace Library’’. Arizona State University, [online] Available: http://trace.eas.asu.edu.
[21] 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.
Author Information
  • Department of Mathematics, Faculty of Science and Engineering, UNAN, Managua, Nicaragua

Cite This Article
  • APA Style

    Fernando José Hernández Gómez. (2020). Heuristic Algorithms of Coincidence for the Estimation of Movements in Compression of Images. Applied and Computational Mathematics, 9(3), 85-95. https://doi.org/10.11648/j.acm.20200903.15

    Copy | Download

    ACS Style

    Fernando José Hernández Gómez. Heuristic Algorithms of Coincidence for the Estimation of Movements in Compression of Images. Appl. Comput. Math. 2020, 9(3), 85-95. doi: 10.11648/j.acm.20200903.15

    Copy | Download

    AMA Style

    Fernando José Hernández Gómez. Heuristic Algorithms of Coincidence for the Estimation of Movements in Compression of Images. Appl Comput Math. 2020;9(3):85-95. doi: 10.11648/j.acm.20200903.15

    Copy | Download

  • @article{10.11648/j.acm.20200903.15,
      author = {Fernando José Hernández Gómez},
      title = {Heuristic Algorithms of Coincidence for the Estimation of Movements in Compression of Images},
      journal = {Applied and Computational Mathematics},
      volume = {9},
      number = {3},
      pages = {85-95},
      doi = {10.11648/j.acm.20200903.15},
      url = {https://doi.org/10.11648/j.acm.20200903.15},
      eprint = {https://download.sciencepg.com/pdf/10.11648.j.acm.20200903.15},
      abstract = {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.},
     year = {2020}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Heuristic Algorithms of Coincidence for the Estimation of Movements in Compression of Images
    AU  - Fernando José Hernández Gómez
    Y1  - 2020/06/08
    PY  - 2020
    N1  - https://doi.org/10.11648/j.acm.20200903.15
    DO  - 10.11648/j.acm.20200903.15
    T2  - Applied and Computational Mathematics
    JF  - Applied and Computational Mathematics
    JO  - Applied and Computational Mathematics
    SP  - 85
    EP  - 95
    PB  - Science Publishing Group
    SN  - 2328-5613
    UR  - https://doi.org/10.11648/j.acm.20200903.15
    AB  - 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.
    VL  - 9
    IS  - 3
    ER  - 

    Copy | Download

  • Sections