Title :
Bayesian graph edit distance
Author :
Myers, Richard ; Wilson, Richard C. ; Hancock, Edwin R.
Author_Institution :
Dept. of Comput. Sci., York Univ., UK
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;
Conference_Titel :
Image Analysis and Processing, 1999. Proceedings. International Conference on
Conference_Location :
Venice
Print_ISBN :
0-7695-0040-4
DOI :
10.1109/ICIAP.1999.797761
