By the same authors

From the same journal

From the same journal

A Bayesian compatibility model for graph matching

Research output: Contribution to journalArticle



Publication details

JournalPattern Recognition Letters
DatePublished - 6 Mar 1996
Issue number3
Number of pages14
Pages (from-to)263-276
Original languageEnglish


This letter presents a new methodology for determining the compatibility coefficients required for performing graph matching by probabilistic relaxation. The adopted framework is Bayesian and commences by specifying the effects of segmentation errors in corrupting the connectivity structure or topology of the graphs under match. This model of relational constraint corruption leads to a pattern of compatibility coefficients that is completely determined by the global topological properties of the graphs under match. We illustrate the application of this new theory in two graph matching applications. The first of these is concerned with exploiting constraints provided by edges. Here the compatibility coefficient for consistent edges is equal to the inverse edge-density. Our second illustration extends the compatibility model to the level of graph faces; the required coefficients are again parameter-free. We provide experimental validation of our method in the matching of aerial images. Here we demonstrate that the theoretical values of our compatibility coefficients are close to their experimentally optimal values.

    Research areas


Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations