Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Fractal triangular search: a metaheuristic for image content search

  • Author(s): Erick O. Rodrigues 1, 2 ; Panos Liatsis 3 ; Luiz Satoru 1 ; Aura Conci 1
    • View affiliations
  • Source: Volume 12, Issue 8, August 2018, p. 1475 – 1484
    DOI:  10.1049/iet-ipr.2017.0790 , Print ISSN 1751-9659, Online ISSN 1751-9667
© The Institution of Engineering and Technology
Received 25/07/2017, Accepted 16/03/2018, Revised 26/02/2018, Published 26/03/2018

This work proposes a variable neighbourhood search (FTS) that uses a fractal-based local search primarily designed for images. Searching for specific content in images is posed as an optimisation problem, where evidence elements are expected to be present. Evidence elements improve the odds of finding the desired content and are closely associated to it in terms of spatial location. The proposed local search algorithm follows the fashion of a chain of triangles that engulf each other and grow indefinitely in a fractal fashion, while their orientation varies in each iteration. The authors carried out an extensive set of experiments, which confirmed that FTS outperforms state-of-the-art metaheuristics. On average, FTS was able to locate content faster, visiting less incorrect image locations. In the first group of experiments, FTS was faster in seven out of nine cases, being >8% faster on average, when compared to the second best search method. In the second group, FTS was faster in six out of seven cases, and it was >22% faster on average when compared to the approach ranked second best. FTS tends to outperform other metaheuristics substantially as the size of the image increases.

Inspec keywords: search problems; fractals; optimisation

Other keywords: fractal fashion; incorrect image locations; state-of-the-art metaheuristics; variable neighbourhood search; desired content; CT images; fractal-based local search; image content search; image increases; local search algorithm; search method; fractal triangular search; evidence elements; searching; specific content; FTS; novel metaheuristic

Subjects: Optical, image and video signal processing; Optimisation techniques; Optimisation techniques; Computer vision and image processing techniques; Combinatorial mathematics

References

    1. 1)
      • 16. Rodrigues, E.O., Torok, L., Liatsis, P., et al: ‘K-MS: a novel clustering algorithm based on morphological reconstruction’, Pattern Recognit., 2017, 66, pp. 392–403.
    2. 2)
      • 8. Hansen, P., Mladenovic, N., Perez, J.A.M.: ‘Variable neighbourhood search: methods and applications’, Oper. Res., 2009, 175, pp. 367–407.
    3. 3)
      • 7. Rodrigues, E., Conci, A., Morais, F., et al: ‘Towards the automated segmentation of epicardial and mediastinal fats: a multi-manufacturer approach using intersubject registration and random forest’. IEEE Int. Conf. Industrial Technology (ICIT), 2015, pp. 1779–1785.
    4. 4)
      • 11. Rodrigues, E.O., Rodrigues, L.O., Oliveira, L.S.N., et al: ‘Automated recognition of the pericardium contour on processed CT images using genetic algorithms’, Comput. Biol. Med., 2017, 87, pp. 38–45.
    5. 5)
      • 18. Rodrigues, E., Conci, A., Morais, F.: ‘On the automated segmentation of epicardial and mediastinal cardiac adipose tissues using classification algorithms’. World Congress on Medical and Health Informatics (MEDINFO), 2015.
    6. 6)
      • 23. Lourenço, H., Martin, O., Stutzle, T.: ‘Iterated local search: framework and applications’, in: ‘Handbook of Metaheuristics’ (2010), 146, pp. 363–397.
    7. 7)
      • 22. Rikxoort, E., Arzhaeva, Y., Ginneken, B.: ‘Automatic segmentation of the liver in computed tomography scans with voxel classification and atlas matching’, 3D Segment. Clin., 2007, 16, pp. 101–108.
    8. 8)
      • 12. Santamaria, J., Cordon, O., Damas, S., et al: ‘Grasp and path relinking hybridizations for the point matching-based image registration problem’, J. Heuristics, 2012, 18, pp. 169–192.
    9. 9)
      • 26. Dammeyer, F., VoB, S.: ‘Dynamic tabu list management using the reverse elimination method’, Ann. Oper. Res., 1993, 41, pp. 29–46.
    10. 10)
      • 19. Rodrigues, E., Morais, F., Morais, N., et al: ‘A novel approach for the automated segmentation and volume quantification of cardiac fats on computed tomography’, Comput. Methods Programs Biomed., 2016, 123, pp. 109–128.
    11. 11)
      • 14. Chen, B., Chen, L., Chen, Y.: ‘Efficient ant colony optimization for image feature selection’, Signal Process., 2013, 93, pp. 1566–1576.
    12. 12)
      • 27. Grimmett, G.,, Stirzaker, D.: ‘Probability and random processes’ (Clarendon Press, Oxford, 1992, 2nd edn.).
    13. 13)
      • 5. Borcharrt, T., Conci, A., d'Ornellas, M.: ‘A warping based approach to correct distortions in endoscopic images’. Proc. 22nd Brazilian Symp. Computer Graphics and Image Processing, 2009.
    14. 14)
      • 3. Subburaman, V.B., Marcel, S.: ‘Alternative search techniques for face detection using location estimation and binary features’, Comput. Vis. Image Underst., 2013, 117, pp. 551–570.
    15. 15)
      • 21. Withey, D.J., Koles, Z.J.: ‘A review of medical image segmentation methods and available software’, Int. J. Bioelectromagnetism, 2008, 10, pp. 125–148.
    16. 16)
      • 1. Sotiras, A., Davatzikos, C., Paragios, N.: ‘Deformable medical image registration: a survey’, IEEE Trans. Med. Imaging, 2013, 32, pp. 1153–1190.
    17. 17)
      • 6. Fernandes, L.A., Oliveira, M.M.: ‘Real-time line detection through an improved hough transform voting scheme’, Pattern Recognit., 2008, 41, pp. 299–314.
    18. 18)
      • 9. Peitgen, H., Peter, R.: ‘The beauty of fractals’ (Springer-Verlag, Heidelberg, 1986).
    19. 19)
      • 24. Glover, F., Laguna, M.: ‘Tabu search – Part I’, ORSA J. Comput., 1989, 1, pp. 190–206.
    20. 20)
      • 2. Deshmukh, M.P., Bhosle, U.: ‘A survey of image registration’, Int. J. Image Process., 2011, 5, pp. 245–269.
    21. 21)
      • 25. Kramer, O.: ‘Evolutionary self-adaptation: a survey of operators and strategy parameters’, Evol. Intell., 2010, 3, pp. 51–65.
    22. 22)
      • 20. Fooprateepsiri, R., Kurutach, W.: ‘A general framework for face reconstruction using single still image based on 2d-to-3d transformation kernel’, Forensic Sci. Int., 2014, 236, pp. 117–126.
    23. 23)
      • 15. Firouzi, H., Najjaran, H.: ‘Efficient and robust multi-template tracking using multi-start interactive hybrid search’, Comput. Vis. Image Underst., 2014, 120, pp. 70–80.
    24. 24)
      • 4. Rodrigues, E., Conci, A., Borchartt, T., et al: ‘Comparing results of thermographic images based diagnosis for breast diseases’. Int. Conf. Systems, Signals and Image Processing (IWSSIP), 2014, pp. 39–42.
    25. 25)
      • 13. Changsoo, J., Huang-Min, P.: ‘Optimized hierarchical block matching for fast and accurate image registration’, Signal Process., Image Commun., 2013, 28, pp. 779–791.
    26. 26)
      • 17. Aiger, D., Kedem, K.: ‘Approximate input sensitive algorithms for point pattern matching’, Pattern Recognit., 2010, 43, pp. 153–159.
    27. 27)
      • 10. Jiang, T., Yang, F.: ‘An evolutionary tabu search for cell image segmentation’, IEEE Trans. Syst. Man Cybern., B, 2002, 32, pp. 675–678.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ipr.2017.0790
Loading

Related content

content/journals/10.1049/iet-ipr.2017.0790
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address