MATCHING DELAUNAY GRAPHS

This paper describes a Bayesian framework for matching Delaunay triang ulations. Relational structures of this sort are ubiquitous in interme diate level computer vision, being used to represent both Voronoi tess ellations of the image plane and volumetric surface data. Our matching process is realised in terms of probabilistic relaxation. The novelty of our method stems from its use of a support function specified in t erms of face-units of the graphs under match. In this way, we draw on more expressive constraints than is possible at the level of edge-unit s alone. In order to apply this new relaxation process to the matching of realistic imagery requires a model of the compatibility between fa ces of the data and model graphs. We present a particularly simple com patibility model that is entirely devoid of free parameters. It requir es only knowledge of the numbers of nodes, edges and faces in the mode l graph. The resulting matching scheme is evaluated on radar images an d compared with its edge-based counterpart. We establish the operation al limits and noise sensitivity on the matching of random-dot patterns . Copyright (C) 1996 Pattern Recognition Society.