INEXACT GRAPH MATCHING USING GENETIC SEARCH

This paper describes a framework for performing relational graph match ing using genetic search. There are three novel ingredients to the wor k. Firstly, we cast the optimisation process into a Bayesian framework by exploiting the recently reported global consistency measure of Wil son and Hancock as a fitness measure. The second novel idea is to real ise the crossover process at the level of subgraphs, rather than emplo ying string-based or random crossover. Finally we accelerate convergen ce by employing a deterministic hill-climbing process prior to selecti on. Since we adopt the Bayesian consistency measure as a fitness funct ion, the basic measure of relational distance underpinning the techniq ue is Hamming distance. Our standpoint is that genetic search provides a more attractive means of performing stochastic discrete optimisatio n on the global consistency measure than alternatives such as simulate d annealing. Moreover, the action of the optimisation process is easil y 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 tha n simulated annealing. We provide some experimental evaluation of the method in the matching of aerial stereograms and evaluate its sensitiv ity on synthetically generated graphs. (C) 1997 Pattern Recognition So ciety.