Incest, Cannibalism, Parochialism and the genetic algorithm
Dan Kennedy · The University of Queensland · 1999
This thesis is an investigation into the application of a genetic algorithm to the task of model and scene based pattern recognition. The genetic algorithm is used to locate instances of model graphs embedded within scene graphs for several different classes of pattern recognition problem. Input to the pattern recognition system consists of two picture graphs constructed from a single kind of primitive. In these experiments the primitives used to construct model and scene picture graphs are spheres, line segments, and in the case where the recognition system is applied to polygon silhouette images, corner points of the polygons. An attributed relational graph, which describes the scene with a vector of attributes for each primitive and a vector of attributes to express the relationship between each pair of primitives, is extracted from both the model and the scene. The attributed relational graph is designed to use attributes which are not affected by translation or rotation. The genetic algorithm that this thesis represents a study of will be designed to determine the mapping of model nodes to scene nodes which results in the best overall match between model attribute vectors and the scene attribute vectors they are mapped to. A distance measure is developed to compare attributed relational graphs numerically and extract a cost of mapping, so that different mappings can be compared to establish which is more accurate. The genetic algorithm uses strings of integers representing mappings as the population, the distance measure as a fitness function, and generic genetic operators to optimise the mapping between model and scene graphs. The genetic algorithm is applied to matching problems in two domains, homomorphic mapping, where any model node can be mapped to any scene node, and monomorphic mapping, where each scene node can be mapped to at most one model node. Special versions of the two generic genetic operators used, uniform crossover and one-point mutation, are developed to restrict the population to monomorphic mappings. In order to facilitate multiple instance recognition using a single genetic algorithm, a combination of existing niching techniques are used to promote diversity within the population. The new niching technique is shown to be both effective and scalable. The conclusions of this thesis are that although at this stage the results obtained using this approach are easily out-done by other algorithms, the genetic algorithm is well suited to the problem of pattern recognition by attributed relational graph matching.