Inexact graph matching using genetic search

This paper describes a framework for performing relational graph matching using genetic search. There are three novel ingredients to the work. Firstly, we cast the optimisation process into a Bayesian framework by exploiting the recently reported global consistency measure of Wilson and Hancock as a...

Full description

Saved in:
Bibliographic Details
Published in:Pattern recognition 1997-06, Vol.30 (6), p.953-970
Main Authors: Cross, Andrew D.J., Wilson, Richard C., Hancock, Edwin R.
Format: Article
Language:English
Subjects:
Aerial stereograms
Algorithmics. Computability. Computer arithmetics
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Computer systems performance. Reliability
Discrete relaxation
Exact sciences and technology
Genetic search
Graph matching
Pattern recognition. Digital image processing. Computational geometry
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper describes a framework for performing relational graph matching using genetic search. There are three novel ingredients to the work. Firstly, we cast the optimisation process into a Bayesian framework by exploiting the recently reported global consistency measure of Wilson and Hancock as a fitness measure. The second novel idea is to realise the crossover process at the level of subgraphs, rather than employing string-based or random crossover. Finally, we accelerate convergence by employing a deterministic hill-climbing process prior to selection. Since we adopt the Bayesian consistency measure as a fitness function, the basic measure of relational distance underpinning the technique is Hamming distance. Our standpoint is that genetic search provides a more attractive means of performing stochastic discrete optimisation on the global consistency measure than alternatives such as simulated annealing. Moreover, the action of the optimisation process is easily understood in terms of its action in the Hamming distance domain. We demonstrate empirically not only that the method possesses polynomial convergence time but also that the convergence rate is more rapid than simulated annealing. We provide some experimental evaluation of the method in the matching of aerial stereograms and evaluate its sensitivity on synthetically generated graphs.
ISSN:0031-3203
1873-5142
DOI:10.1016/S0031-3203(96)00123-9