Deterministic search for relational graph matching

This paper describes a comparative study of various deterministic discrete search-strategies for graph-matching. The framework for our study is provid ed by the Bayesian consistency measure recently reported by Wilson and Hanc ock (IEEE PAMI 19 (1997) 634-648; Pattern Recognition 17 (1996) 263-276) an d Wilson et al. (Comput. Vision Image Understanding 72 (1998) 20-38' We inv estigate two classes of update process. The first of these aims to exploit discrete gradient ascent methods. We investigate the effect of searching in the direction of both the local and global gradient maximum. An experiment al study demonstrates that although more computationally intensive, the glo bal gradient method offers significant performance advantages in terms of a ccuracy of match. Our second search strategy is based on tabu search. In or der to develop this method we introduce memory into the search procedure by defining context-dependant search paths. We illustrate that although it is more efficient than the global gradient method, tabu search delivers almos t comparable performance. (C) 1999 Pattern Recognition Society. Published b y Elsevier Science Ltd. All rights reserved.