Deterministic search for relational graph matching

Citation
Ml. Williams et al., Deterministic search for relational graph matching, PATT RECOG, 32(7), 1999, pp. 1255-1271
Citations number
33
Categorie Soggetti
AI Robotics and Automatic Control
Journal title
PATTERN RECOGNITION
ISSN journal
00313203 → ACNP
Volume
32
Issue
7
Year of publication
1999
Pages
1255 - 1271
Database
ISI
SICI code
0031-3203(199907)32:7<1255:DSFRGM>2.0.ZU;2-K
Abstract
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.