Practica

NICHING METHODS WITH THE BREEDER GENETIC ALGORITHM FOR GEOMETRIC PRIMITIVE EXTRACTION: PRELIMINARY RESULTS
Diago, L(*) and Ochoa, A. (*)Center of Bioengineering , CEBIO, ISPJAE - University, 127 s/n Marianao, C-Havana, Cuba. diago@electrica.ispjae.edu.cu Institute of Cybernetics Mathematics and Physics, Calle 15 e/ C y D, Vedado, C-Havana, Cuba.

ABSTRACT
Geometric primitive extraction orlocalization is a widely used method in image recognition tasks. A geometric primitive is a curve or surface, which can be described by an equation with a number of free parameters. A major problem faced in geometric primitive extraction deals with the characteristics of the search space: multimodal, nonlineal, noisy and highly dimensional; and with the possible variations of shapes of primitives.Genetic algorithms (GAs) [1] offer a domain-independent approach suitable for working with such complex problems. The Breeder Genetic Algorithm (BGA) [8] is a GA inspired by the science of breeding animals. This paper explores the use of a BGA with niching methods [7] to find multiples primitives at the same time. Niching methods extend GAs to domains that require the location and maintenance ofmultiple solutions. We investigate two types of niching techniques, the so called sharing and crowding methods. Our simulations have shown a clear superiority of crowding in this application. Therefore we develop and test this method further to consider the use of truncation selection in the BGA with eye fundus images. . Index terms: genetic algorithms, computer vision, feature extraction.

1.INTRODUCTION
A genetic algorithm (GA) is an optimization approach based on the evolutionary metaphor [1]. Previous studies on why and how the GA works have proceeded along different lines, most arguments are based on the Schema Theorem [5]. Mhlenbein [8] have criticized this theorem and proposed the Breeder Genetic Algorithm (BGA). BGA is inspired by the science of breeding animals. In thisalgorithm, each one of a set of virtual breeders has the task to improve its own subpopulation. Like human breaders a BGA uses truncation selection.

In this paper, a geometric primitive is a curve or surface, which can be described by an equation with a number of free parameters. It has recently been shown that extracting the best geometric primitive from a given geometric data is equivalent to findingthe optimum value of a cost function [11]. Geometric data are an unordered list of points in two or three-dimensional Cartesian space, which can be obtained by edge detection process. Once it is understood that primitive extraction is such an optimization problem, the use of GA suggests itself. To use GA, the parameter vector must be encoded in chromosome form. The parameter vector is what we haveinto the chromosomes to represent the primitive's parameters. In our experiments a chromosome representation of a primitive by a minimal subset of member points is used. Such a subset is the smallest number of points necessary to define a unique instance of a primitive [12]. The Hough Transform (HT) is the must common method of primitive extraction [6]. Roth and Levine [12] mentioned that themain disadvantage of the GA approach relative to the HT is that the GA must be applied repeatedly to the geometric data for each extracted primitive, while the HT extracts all the primitives at once. Our alternative find a number of primitives at the same time by using the idea of niches described in GA literature [7]. We investigate two types of niching techniques, the so called sharing and crowdingmethods. Our simulations have shown a clear superiority of crowding in this application. Therefore we develop and test this method further to consider the use of truncation selection in the BGA with eye fundus images.

2. A BRIEF DESCRIPTION OF NICHING METHODS FOR GENETIC ALGORITHMS
Users utilize population size (n), crossover probability (pc) and mutation probability (pm) to maintain...