Least-commitment graph matching with genetic algorithms

This paper concerns the correspondence matching of ambiguous feature sets e xtracted from images. The first contribution made in this paper is to exten d Wilson and Hancock's Bayesian matching framework (Wilson and Hancock, IEE E Trans. Pattern Anal. Mach. Intell. 19 (1997) 634-648) by considering the case where the feature measurements are ambiguous. The second contribution is the development of a multimodal evolutionary optimisation framework whic h is capable of simultaneously producing several good alternative solutions . Previous multimodal genetic algorithms have required additional parameter s to be added to a method which is already over-parameterised. The algorith m presented in this paper requires no extra parameters: solution yields are maximised by removing bias in the selection step, while optimisation perfo rmance is maintained by a local search step. This framework is in principle applicable to any multimodal optimisation problem where local search perfo rms well. An experimental study demonstrates the effectiveness of the new a pproach on synthetic and real data. (C) 2000 Pattern Recognition Society. P ublished by Elsevier Science Ltd. All rights reserved.