Evolving optimal feature extraction using multi-objective genetic programming: a methodology and preliminary study on edge detection

ABSTRACT

In this paper we describe a generic methodology to create an "optimal" feature extraction pre-processing stage for pattern classification. Our aim is to map the input data into a new, one-dimensional feature space in which separability is maximized under a simple thresholding classification. We have used multi-objective genetic programming with Pareto strength-based ranking to bias the selection procedure. The methodology is applied to the edge detection problem in image processing; we make quantitative comparison with the pre-processing stages of the well-known Canny edge detector using synthetic and real-world edge data and conclude that the performance of our evolutionary-based method is much superior to the Canny algorithm based on the criterion of minimum Bayes risk.

REFERENCES

• 1: P.I.Rockett. Performance Assessment of Feature Detection Algorithms: A Methodology and Case Study on Corner Detectors. IEEE Transactions on Image Processing. Vol.12, No.11. Nov 2003.
• 2: N.R. Harvey, S.P. Brumby, S. Perkins, J.J. Szymanski. J. Theiler, J.J. Bloch, R.B. Porter, M. Galassi & A.C. Young. Image Feature Extraction: GENIE vs Conventional Supervised Classification Techniques. IEEE Transactions on Geoscience and Remote Sensing, Vol. 40, No. 2, pp 393--404, 2002.
• 3: J.R.Sherrah, R.E.Bogner & A.Bouzerdoum. The Evolutionary Pre-Processor: Automatic Feature Extraction for Supervised Classification using Genetic Programming. Genetic Programming 1997: Proceedings of the Second Annual Conference. Stanford University, CA, USA. Pages 304--312 1997
• 4: Chris Gathercole , Peter Ross, Dynamic Training Subset Selection for Supervised Learning in Genetic Programming, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.312-321, October 09-14, 1994
• 5: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 6: L.Devroye, L. Györfi & G. Lugosi. A Problabilistic Theory of Pattern Recognition. Springer-Verlag, 1996.
• 7: J.R.Sherrah, Automatic Feature Extraction for Pattern Recognition. PhD Thesis, Dept. of EEE, The University of Adelaide, South Australia, July. 1998
• 8: Peter J. Angeline, Genetic programming and emergent intelligence, Advances in genetic programming, MIT Press, Cambridge, MA, 1994
• 9: Mike Heath , Sudeep Sarkar , Thomas Sanocki , Kevin Bowyer, Comparison of Edge Detectors: A Methodology and Initial Study, Proceedings of the 1996 Conference on Computer Vision and Pattern Recognition (CVPR '96), p.143, June 18-20, 1996
• 10: S. Bleuler, M. Brack, L. Thiele & E. Zitzler. Multiobjective Genetic Programming: Reducing Bloat Using SPEA2. Congress on Evolutionary Computation (CEC 2001). Pages 536--543. 5/2001
• 11: W. B. Langdon & S. J. Barrett. Genetic Programming in Data Mining for Drug Discovery, Chapter 10 in Evolutionary Computing in Data Mining, Ashish Ghosh and Lakhmi C. Jain editors, Physica Verlag, pages 211--235, 2004.
• 12: Takuya Ito , Hitoshi Iba , Satoshi Sato, Non-destructive Depth-Dependent Crossover for Genetic Programming, Proceedings of the First European Workshop on Genetic Programming, p.71-82, April 14-15, 1998
• 13: Kevin Bowyer , Christine Kranenburg , Sean Dougherty, Edge detector evaluation using empirical ROC curves, Computer Vision and Image Understanding, v.84 n.1, p.77-103, October 2001 [doi>10.1006/cviu.2001.0931]
• 14: M.H.Zweig & G.Campbell. Receiver Operating Characteristic (ROC) Plots: A Fundamental Evaluation Tool in Clinical Medicine. In Clinical Chemistry, vol. 39, iss. 4, pp561--577 1993
• 15: W.C.Chen, N.A.Thacker & P.I.Rockett. An adaptive step edge model for self-consistent training of a neural network for probabilistic edge labeling. In IEE Proceedings - Vision, Image & Signal Processing, VISP 143 No.1, Pages 41--50 Feb. 1996.
• 16: R.K.Cope & P.I.Rockett. The efficacy of Gaussian smoothing in the Canny edge detector. In Electronics Letters, Vol 36 (19), Pages 1615--1617 2000.
• 17: T. Kanungo , R. M. Haralick, Receiver operating characteristic curves and optimal Bayesian operating points, Proceedings of the 1995 International Conference on Image Processing (Vol. 3)-Volume 3, p.3256, October 23-26, 1995
• 18: Walter Alden Tackett, Genetic Programming for Feature Discovery and Image Discrimination, Proceedings of the 5th International Conference on Genetic Algorithms, p.303-311, June 01, 1993

INDEX TERMS

General Terms:
Algorithms, Design, Theory

Keywords:
edge detector, feature extractor, multi-objective genetic programming