A Genetic Programming Approach to the Design of Interest Point Operators

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Gustavo Olague and Leonardo Trujillo: A Genetic Programming Approach to the Design of Interest Point Operators. In: Bio-Inspired Hybrid Intelligent Systems for Image Analysis and Pattern Recognition. Studies in Computational Intelligence, Vol. 256, pp. 49-65, Springer, 2009.




Recently, the detection of local image feature has become an indispensable process for many image analysis or computer vision systems. In this chapter, we discuss how Genetic Programming (GP), a form of evolutionary search, can be used to automatically synthesize image operators that detect such features on digital images. The experimental results we review, confirm that artificial evolution can produce solutions that outperform many man-made designs. Moreover, we argue that GP is able to discover, and reuse, small code fragments, or building blocks, that facilitate the synthesis of image operators for point detection. Another noteworthy result is that the GP did not produce operators that rely on the auto-correlation matrix, a mathematical concept that some have considered to be the most appropriate to solve the point detection task. Hence, the GP generates operators that are conceptually simple and can still achieve a high performance on standard tests.

Extended Abstract


Used References

Schmid, C., Mohr, R., Bauckhage, C.: Evaluation of interest point detectors. International Journal of Computer Vision 37(2), 151–172 (2000) http://dx.doi.org/10.1023/A:1008199403446

Mikolajczyk, K., Schmid, C.: A performance evaluation of local descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence 27(10), 1615–1630 (2005) http://dx.doi.org/10.1109/TPAMI.2005.188

Tuytelaars, T., Mikolajczyk, K.: Local invariant feature detectors: a survey. Found. Trends Comput. Graph. Vis. 3(3), 177–280 (2008) http://dx.doi.org/10.1561/0600000017

Schmid, C., Mohr, R.: Local grayvalue invariants for image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence 19(5), 530–534 (1997) http://dx.doi.org/10.1109/34.589215

Lowe, D.G.: Object recognition from local scale-invariant features. In: Proceedings of the International Conference on Computer Vision (ICCV), Kerkyra, Corfu, Greece, September 20-25, vol. 2, pp. 1150–1157. IEEE Computer Society, Los Alamitos (1999) http://dx.doi.org/10.1109/ICCV.1999.790410

Trujillo, L., Olague, G., Legrand, P., Lutton, E.: Regularity based descriptor computed from local image oscillations. Optics Express 15, 6140–6145 (2007) http://dx.doi.org/10.1364/OE.15.006140

Perez, C.B., Olague, G.: Learning invariant region descriptor operators with genetic programming and the f-measure. In: Proceedings of the 2008 International Conference on Pattern Recognition (ICPR 2008), pp. 1–4 (2008)

Bouchard, G., Triggs, B.: Hierarchical part-based visual object categorization. In: Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), San Diego, CA, June 20-26, 2005, vol. 1, pp. 710–715. IEEE Computer Society Press, Los Alamitos (2005) http://dx.doi.org/10.1109/CVPR.2005.174

Ferrari, V., Tuytelaars, T., Van Gool, L.: Simultaneous object recognition and segmentation from single or multiple model views. Int. J. Comput. Vision 67(2), 159–188 (2006) http://dx.doi.org/10.1007/s11263-005-3964-7

Wang, J., Zha, H., Cipolla, R.: Coarse-to-fine vision-based localization by indexing scale-invariant features. IEEE Transactions on Systems, Man, and Cybernetics, Part B 36(2), 413–422 (2006) http://dx.doi.org/10.1109/TSMCB.2005.859085

Trujillo, L., Olague, G., de Vega, F.F., Lutton, E.: Evolutionary feature selection for probabilistic object recognition, novel object detection and object saliency estimation using gmms. In: Proceedings from the 18th British Machine Vision Conference, September 10-13, Warwick, UK, pp. 630–639. British Machine Vision Association (2007)

Trujillo, L., Olague, G.: Synthesis of interest point detectors through genetic programming. In: Cattolico, M. (ed.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), Seattle, Washington, July 8-12, vol. 1, pp. 887–894. ACM Press, New York (2006) http://dx.doi.org/10.1145/1143997.1144151

Trujillo, L., Olague, G.: Using evolution to learn how to perform interest point detection. In: Proceedings of the 18th International Conference on Pattern Recognition (ICPR), Hong Kong, China, August 20-24, vol. 1, pp. 211–214. IEEE Computer Society Press, Los Alamitos (2006)

Trujillo, L., Olague, G., Lutton, E., de Vega, F.F.: Multiobjective design of operators that detect points of interest in images. In: Cattolico, M. (ed.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), Atlanta, GA, USA, July 12-16, pp. 1299–1306. ACM, New York (2008) http://dx.doi.org/10.1145/1389095.1389344

Trujillo, L., Olague, G.: Automated design of image operators that detect interest points. Evolutionary Computation 16(4), 483–507 (2008) http://dx.doi.org/10.1162/evco.2008.16.4.483

Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)

O’Reilly, U.-M., Oppacher, F.: The troubling aspects of a building block hypothesis for genetic programming. In: Proceedings of the Third Workshop on Foundations of Genetic Algorithms (FOGA), Estes Park, Colorado, USA, FOGA, July 31 - August 2, 1994, pp. 73–88. Morgan Kaufmann, San Francisco (1994)

Langdon, W.B., Poli, R.: Foundations of Genetic Programming. Springer, New York (2002)

Trujillo, L., Olague, G.: Scale invariance for evolved interest operators. In: Giacobini, M. (ed.) EvoWorkshops 2007. LNCS, vol. 4448, pp. 423–430. Springer, Heidelberg (2007)

McGlone, J., et al. (eds.): Manual of photogrammetry. American Society of Photogrammetry and Remote Sensing (2004)

Tissainayagam, P., Suter, D.: Assessing the performance of corner detectors for point feature tracking applications. Image Vision Comput. 22(8), 663–679 (2004) http://dx.doi.org/10.1016/j.imavis.2004.02.001

Shi, J., Tomasi, C.: Good features to track. In: Proceedings of the 1994 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 1994), Seattle, WA, USA, June 1994, pp. 593–600. IEEE Computer Society, Los Alamitos (1994)

Olague, G., Hernández, B.: A new accurate and flexible model based multi-corner detector for measurement and recognition. Pattern Recognition Letters 26(1), 27–41 (2005) http://dx.doi.org/10.1016/j.patrec.2004.08.026

Harris, C., Stephens, M.: A combined corner and edge detector. In: Proceedings from the Fourth Alvey Vision Conference, vol. 15, pp. 147–151 (1988)

Förstner, W., Gülch, E.: A fast operator for detection and precise location of distinct points, corners and centres of circular features. In: ISPRS Intercommission Conference on fast processing of photogrammetric data, pp. 149–155 (1987)

Beaudet, P.R.: Rotational invariant image operators. In: Proceedings of the 4th International Joint Conference on Pattern Recognition (ICPR), Tokyo, Japan, pp. 579–583 (1978)

Kitchen, L., Rosenfeld, A.: Gray-level corner detection. Pattern Recognition Letters 1, 95–102 (1982) http://dx.doi.org/10.1016/0167-8655(82)90020-4

Noble, A.: Descriptions of Image Surfaces. PhD thesis, Department of Engineering Science. Oxford University, Oxford (1989)

Kenney, C.S., Zuliani, M., Manjunath, B.S.: An axiomatic approach to corner detection. In: International Conference on Computer Vision and Pattern Recognition (CVPR) (June 2005)

Davison, A.J., Molton, N.D.: Monoslam: Real-time single camera slam. IEEE Trans. Pattern Anal. Mach. Intell. 29(6), 1052–1067 (2007); Member-Ian D. Reid and Member-Olivier Stasse http://dx.doi.org/10.1109/TPAMI.2007.1049

Yang, G., Stewart, C.V., Sofka, M., Tsai, C.-L.: Registration of challenging image pairs: Initialization, estimation, and decision. IEEE Trans. Pattern Anal. Mach. Intell. 29(11), 1973–1989 (2007) http://dx.doi.org/10.1109/TPAMI.2007.1116

De Jong, K.: Evolutionary Computation: A Unified Approach. MIT Press, Cambridge (2001)

Koza, J.R., Keane, M.A., Yu, J., Bennett III, F.H., Mydlowec, W.: Automatic creation of human-competitive programs and controllers by means of genetic programming. Genetic Programming and Evolvable Machines 1(1-2), 121–164 (2000) http://dx.doi.org/10.1023/A:1010076532029

Poli, R., Langdon, W.B., McPhee, N.F.: A field guide to genetic programming (2008) Published via, http://lulu.com and freely available, http://www.gp-field-guide.org.uk (With contributions by Koza, J.R.)

Olague, G., Cagnoni, S., Lutton, E.: Preface: introduction to the special issue on evolutionary computer vision and image understanding. Pattern Recognition Letters 27(11), 1161–1163 (2006) http://dx.doi.org/10.1016/j.patrec.2005.07.013

Cagnoni, S., Lutton, E., Olague., G. (eds.): Genetic and Evolutionary Computation for Image Processing and Analysis. EURASIP Book Series on Signal Processing and Communications, vol. 8. Hindawi Publishing Corporation (2007)

Cagnoni, S., Lutton, E., Olague, G.: Editorial introduction to the special issue on evolutionary computer vision. Evoutionary Computation 16(4), 437–438 (2008) http://dx.doi.org/10.1162/evco.2008.16.4.437

Krawiec, K.: Genetic programming-based construction of features for machine learning and knowledge discovery tasks. Genetic Programming and Evolvable Machines 3(4), 329–343 (2002) http://dx.doi.org/10.1023/A:1020984725014

Ebner, M.: On the evolution of interest operators using genetic programming. In: Poli, R., et al. (eds.) EuroGP 1998. LNCS, vol. 1391, pp. 6–10. Springer, Heidelberg (1998)

Zhang, Y., Rockett, P.I.: Evolving optimal feature extraction using multi-objective genetic programming: a methodology and preliminary study on edge detection. In: GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, pp. 795–802. ACM, New York (2005) http://dx.doi.org/10.1145/1068009.1068143

Jaśkowski, W., Krawiec, K., Wieloch, B.: Multitask visual learning using genetic programming. Evol. Comput. 16(4), 439–459 (2008) http://dx.doi.org/10.1162/evco.2008.16.4.439

Lin, Y., Bhanu, B.: Evolutionary feature synthesis for object recognition. IEEE Transactions on Systems, Man and Cybernetics, Part C, Special Issue on Knowledge Extraction and Incorporation in Evolutionary Computation 35(2), 156–171 (2005)

Krawiec, K., Bhanu, B.: Visual learning by evolutionary and coevolutionary feature synthesis. IEEE Trans. on Evolutionary Computation 11, 635–650 (2007) http://dx.doi.org/10.1109/TEVC.2006.887351

Howard, D., Roberts, S.C., Ryan, C.: Pragmatic genetic programming strategy for the problem of vehicle detection in airborne reconnaissance. Pattern Recogn. Lett. 27(11), 1275–1288 (2006) http://dx.doi.org/10.1016/j.patrec.2005.07.025

Zhang, M., Ciesielski, V.B., Andreae, P.: A domain-independent window approach to multiclass object detection using genetic programming. EURASIP Journal on Applied Signal Processing, Special Issue on Genetic and Evolutionary Computation for Signal Processing and Image Analysis (8), 841–859 (2003)

Song, A., Ciesielski, V.: Texture segmentation by genetic programming. Evol. Comput. 16(4), 461–481 (2008) http://dx.doi.org/10.1162/evco.2008.16.4.461

Keijzer, M., Babovic, V.: Declarative and preferential bias in gp-based scientific discovery. Genetic Programming and Evolvable Machines 3(1), 41–79 (2002) http://dx.doi.org/10.1023/A:1014596120381

Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975)

Grefenstette, J.J.: Deception considered harmful. In: Whitley, D.L. (ed.) Foundations of Genetic Algorithms 2, pp. 75–91. Morgan Kaufmann, San Mateo (1993)

Vose, M.D.: The simple genetic algorithm: foundations and theory. MIT Press, Cambridge (1999)

Lindeberg, T.: Feature detection with automatic scale selection. International Journal of Computer Vision 30(2), 79–116 (1998) http://dx.doi.org/10.1023/A:1008045108935


Full Text

[extern file]

intern file

Sonstige Links