Probabilistic analysis of two stage matching

摘要

In this paper, we study two stage matching procedures as applied to labelled graphs and other domains relevant to computer vision. We do not require that the match be exact but only that it satisfy a specified error criterion. We show that it is computationally more efficient to initially match a subgraph and check the rest of the graph only when this match succeeds. A probabilistic analysis of the expected cost of this procedure is given with the aim of determining the optimum subgraph size which minimizes this cost. The results are extended to graph matching with geometric constraints as well as to templates.