Bayesian graph edit distance

Author

Myers, Richard ; Wilson, Richard C. ; Hancock, Edwin R.

Author_Institution

Dept. of Comput. Sci., York Univ., UK

fYear

1999

fDate

1999

Firstpage

1166

Lastpage

1171

Abstract

This paper describes a novel framework for comparing and matching corrupted relational graphs. The normalised edit distance of Marzal and Vidal (1993) can be used to model the probability distribution for structural errors in the graph-matching problem. This probability distribution is used to locate matches using MAP label updates. We compare this criterion with that recently reported by Wilson and Hancock (1997). The use of edit distance offers an elegant alternative to the exhaustive compilation of label dictionaries. Moreover the method is polynomial rather than exponential in its worst-case complexity. We support our approach with an experimental study on synthetic data, and illustrate its effectiveness on an uncalibrated stereo correspondence problem

Keywords

Bayes methods; computational complexity; graph theory; image matching; probability; stereo image processing; Bayesian graph; MAP label updates; graph-matching problem; normalised edit distance; polynomial complexity; probability distribution; relational graphs; structural errors; uncalibrated stereo correspondence; Bayesian methods; Computer science; Concrete; Dictionaries; Electrical capacitance tomography; Hamming distance; Layout; Machine vision; Pattern recognition; Sensor fusion;

fLanguage

English

Publisher

ieee

Conference_Titel

Image Analysis and Processing, 1999. Proceedings. International Conference on

Conference_Location

Venice

Print_ISBN

0-7695-0040-4

Type

conf

DOI

10.1109/ICIAP.1999.797761

Filename

797761