No Access

TEMPLATE MATCHING IN DIGITAL IMAGES USING A COMPACT GENETIC ALGORITHM WITH ELITISM AND MUTATION

Bioinformatics Laboratory, Federal University of Technology — Paraná, Av. 7 de setembro 3165, 80230-901 Curitiba (PR), Brazil

Search for more papers by this author

CARLOS R. ERIG LIMA

Bioinformatics Laboratory, Federal University of Technology — Paraná, Av. 7 de setembro 3165, 80230-901 Curitiba (PR), Brazil

Search for more papers by this author

, and

HEITOR S. LOPES

Bioinformatics Laboratory, Federal University of Technology — Paraná, Av. 7 de setembro 3165, 80230-901 Curitiba (PR), Brazil

Search for more papers by this author

https://doi.org/10.1142/S0218126610006025Cited by:3 (Source: Crossref)

Abstract

The emCGA is a new extension of the compact genetic algorithm (CGA) that includes elitism and a mutation operator. These improvements do not increase significantly the computational cost or the memory consumption and, on the other hand, increase the overall performance in comparison with other similar works. The emCGA is applied to the problem of object recognition in digital images. The objective is to find a reference image (template) in a landscape image, subject to distortions and degradation in quality. Two models for dealing with the images are proposed, both based on the intensity of light. Several experiments were done with reference and landscape images, under different situations. The emCGA was compared with an exhaustive search algorithm and another CGA proposed in the literature. The emCGA was found to be more efficient for this problem, when compared with the other algorithms. We also compared the two proposed models for the object. One of them is more suitable for images with rich details, and the other for images with low illumination level. Both models seem to perform equally in the presence of distortions. Overall, results suggested the efficiency of emCGA for template matching in images and encourages future developments.

Keywords:

References

E. P. Ferlinet al., Lect. Notes Comput. Sci. 4419 (2007) pp. 326–336. Google Scholar
G. Harik, F. Lobo and D. E. Goldberg, IEEE Trans. Evol. Comput. 3, 287 (1999), DOI: 10.1109/4235.797971. Web of Science, Google Scholar
F. G. Lobo, C. F. Lima and H. Mártires, Lect. Notes Comput. Sci. 3103 (2004) pp. 412–413. Google Scholar
K. Sastry, D. E. Goldberg and X. Llora, Towards billion-bit optimization via a parallel estimation of distribution algorithm, Proc. Genetic and Evolutionary Computation Conference (2007) pp. 114–125. Google Scholar
C. R. E. Lima and J. M. Rosário, Reconfigurable architecture proposal applied to mobile robots, Proc. ABCM Symp. Series in Mechatronics1 (2004) pp. 68–75. Google Scholar
H. S. Lopes, C. R. E. Lima and N. J. Murata, J. Circuits Syst. Comput. 16, 1 (2007), DOI: 10.1142/S0218126607003885. Web of Science, Google Scholar
N. K. Ratha and A. K. Jain, IEEE Trans. Par. Distr. Syst. 10, 29 (1999), DOI: 10.1109/71.744833. Web of Science, Google Scholar
R. R. Silva, H. S. Lopes and C. R. Erig Lima, Lect. Notes Comput. Sci. 4431 (2007) pp. 159–166. Google Scholar
P. Larrañaga and J. A. Lozano , Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation ( Kluwer , Dordrecht , 2002 ) . Google Scholar
G. Hariket al., Evol. Comput. 7, 231 (1999), DOI: 10.1162/evco.1999.7.3.231. Web of Science, Google Scholar
A. Rogers and A. Pruegel-Bennett, IEEE Trans. Evol. Comput. 49, 298 (1999). Google Scholar
D. Dumitrescu et al. , Evolutionary Computation ( CRC Press , Boca Raton , 2000 ) . Google Scholar
R. Rastegar and A. Hariri, Evol. Comput. 14, 277 (2006), DOI: 10.1162/evco.2006.14.3.277. Web of Science, Google Scholar
C. Ahn and R. Ramakrishna, IEEE Trans. Evol. Comput. 7, 367 (2003). Web of Science, Google Scholar
J. Gallagher, S. Vigraham and G. Kramer, IEEE Trans. Evol. Comput. 8, 111 (2004), DOI: 10.1109/TEVC.2003.820662. Web of Science, Google Scholar
C. Zhou, K. Meng and Z. Qiu, Compact genetic algorithm mutated by bit, Proc. 4th World Congress on Intelligent Control and Automation4 (2002) pp. 1836–1839. Google Scholar
R. Brunelli , Template Matching Techniques in Computer Vision: Theory and Practice ( Wiley , New York , 2009 ) . Google Scholar
M. K. Felizbertoet al., Comput. Vis. Image Underst. 102, 238 (2006). Web of Science, Google Scholar
H. A. Perlin, H. S. Lopes and T. C. Mezzadri, Lect. Notes Comput. Sci. 5027 (2008) pp. 11–21. Google Scholar
R. Dattaet al., ACM Comput. Surv. 40, 1 (2008), DOI: 10.1145/1348246.1348248. Web of Science, Google Scholar