Incest, Cannibalism, Parochialism and the genetic algorithm

Kennedy, Dan (1999). Incest, Cannibalism, Parochialism and the genetic algorithm B.Sc Thesis, School of Computer Science and Electrical Engineering, The University of Queensland.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
Kennedy_Dan_THE15017.pdf Full text application/pdf 453.88KB 0
Author Kennedy, Dan
Thesis Title Incest, Cannibalism, Parochialism and the genetic algorithm
School, Centre or Institute School of Computer Science and Electrical Engineering
Institution The University of Queensland
Publication date 1999
Thesis type B.Sc Thesis
Total pages 95
Language eng
Subjects 0906 Electrical and Electronic Engineering
Formatted abstract

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.

Keyword Genetic algorithm
Homomorphic mapping
Monomorphic mapping
Additional Notes * 4th year electrical engineering theses and information technology abstracts. 1999

Document type: Thesis
Collection: UQ Theses (non-RHD) - UQ staff and students only
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 24 May 2013, 09:44:49 EST by Mr Yun Xiao on behalf of Scholarly Communication and Digitisation Service