|
EPSRC Network on Evolvability in Biology & Software SystemsSoftware Evolution and Evolutionary Computation Symposium Abstracts
University of Hertfordshire, Hatfield, U.K.
|
KEITH ANDERSON AND PETER MCOWAN
Department of Computer Science
Queen Mary, University of London
Mile End Road
London E1 4NS, U.K.
ka@dcs.qmul.ac.uk
pmco@dcs.qmul.ac.uk
Memetic algorithms are a population-based approach for heuristic search in optimisation problems. Memetic algorithms combine local search heuristics with the crossover and mutation operators found in traditional genetic algorithms. It has been reported that memetic algorithms can be several orders of magnitude faster than traditional genetic algorithms in some problem domains.
The ability to parse the contents of a scene into known shapes and relationships is fundamental to both computer and biological vision. This task is particularly difficult when the input is noisy and shapes in the scene overlap one another. In this paper we extend the work of Ozcan and Mohan [1], who developed a solution to the shape-matching problem through the use of a memetic algorithm.
The shape matching algorithm presented represents shapes as lists of normalised feature lengths and relative angles, and uses memetic algorithms to find the best match between stored known shapes and those in the observed scene. This useful representation provides support for a matching strategy that is rotation, translation, and size invariant, and one able to handle multiple shape overlap and small levels of noise in the scene.
Significant extensions made to the original Ozcan and Mohan algorithm, and presented in this paper, include alterations to the hill-climbing operator (a local search technique), which now uses directed search to prevent its use in situations where it is impossible to further improve fitness. A novel extension to the algorithm has also been implemented to allow the extraction of several movement characteristics of the shapes in the scene (centre of rotation, rate of rotation, speed of movement, direction of movement, rate of approach). We will present results indicating the usefulness of this approach to visual scene analysis and in pattern movement, rate of approach). We will present results indicating the usefulness of this approach to visual scene analysis and in pattern recognition software.