Matching Delaunay Graphs

Andrew M. Finch, Edwin R. HancockICIAP 1995 · OpenReview

Abstract

This paper describes a Bayesian framework for matching Delaunay graphs. 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 terms of triangular face-units of the graphs under match. In this way we draw on more expressive constraints than is possible at the level of edge-units alone. We present a particularly simple face compatibility model that is entirely devoid of free parameters. It requires only knowledge of the numbers of nodes, edges and faces in the model graph. The resulting matching scheme is evaluated on radar images and compared with its edge-based counterpart.

Introduction

Inexact graph matching is a fundamental challenge in computer vision, where a noisy "data graph" representing a real-world scene must be aligned with a clean "model graph." Traditional approaches typically rely on pairwise constraints, matching edges in the data graph to edges in the model. However, for Delaunay graphs—triangulations frequently used to represent spatial distributions—edge-based methods often fail. These graphs are dense with triangular cycles, and ignoring this higher-order structural information leads to poor performance in the presence of "clutter" (extraneous data points).

Methodology

The proposed method shifts the focus from simple connectivity to the local topology of triangular "face-units." By leveraging the properties of planar graphs, specifically the cyclic ordering of nodes around a center point, the authors develop a more robust matching framework.

Face-Unit Support Function

The core of the approach is a Bayesian probabilistic relaxation scheme. Instead of evaluating node matches in isolation or pairs, the algorithm uses a recursive support function that considers triples of nodes forming triangular faces. This captures the geometric context of the local area, making it significantly harder for random noise to induce false matches.

Schematic of the face-unit support function showing cyclic ordering of nodes around a central node.

Parameter-Free Compatibility Model

A key innovation is the parameter-free compatibility model. It classifies potential face matches into four categories: uncorrupted (all nodes match), partial (one or two nodes match while others are noise), and total null (all nodes are noise). By explicitly including a "null" category ($\phi$), the system can effectively identify and discard clutter rather than forcing incorrect matches. The weights for these categories are derived directly from the global statistics of the model graph (number of nodes, edges, and faces).

Experimental Evaluation

The method was tested using Synthetic Aperture Radar (SAR) data, where the goal was to match linear hedge structures detected in radar imagery against a digital cartographic map. Delaunay graphs were constructed using the midpoints of detected line segments. The model graph consisted of 28 nodes, 46 faces, and 142 edges.

Results and Discussion

The face-based approach demonstrated superior performance over traditional edge-based methods, particularly in handling clutter. In the SAR experiments, the face-based method correctly identified 64 nodes as noise with only 5 errors. In contrast, the edge-based method identified only 22 nodes as noise and produced 46 incorrect matches.

Performance surface illustrating the "broad plateau" of accuracy, indicating the stability of the matching process.

Furthermore, the method exhibited high stability. As shown in the performance surface, there is a broad plateau of high matching accuracy across a wide range of compatibility values, suggesting that the model is not overly sensitive to precise parameter tuning.

Conclusion

By prioritizing topology over simple connectivity, this face-based matching framework provides a significant advancement for processing high-density graphs with many first-order cycles. The use of triangular faces as the primary unit of constraint allows for more expressive matching that is inherently resistant to noise and clutter. Future work may extend this framework to non-planar structures and larger-scale 3D mesh matching applications.

Summary updated

Abstract

This paper describes a Bayesian framework for matching Delaunay graphs. 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 terms of triangular face-units of the graphs under match. In this way we draw on more expressive constraints than is possible at the level of edge-units alone. We present a particularly simple face compatibility model that is entirely devoid of free parameters. It requires only knowledge of the numbers of nodes, edges and faces in the model graph. The resulting matching scheme is evaluated on radar images and compared with its edge-based counterpart.
BibTeX
@inproceedings{finch1995matching,
  author = {Andrew M. Finch and Edwin R. Hancock},
  title = {{Matching Delaunay Graphs}},
  booktitle = {ICIAP},
  year = {1995},
  url = {https://openreview.net/forum?id=DfohDYJE9f},
}
Figure