A BAYESIAN COMPATIBILITY MODEL FOR GRAPH MATCHING

This letter presents a new methodology for determining the compatibili ty coefficients required for performing graph matching by probabilisti c relaxation. The adopted framework is Bayesian and commences by speci fying the effects of segmentation errors in corrupting the connectivit y structure or topology of the graphs under match. This model of relat ional constraint corruption leads to a pattern of compatibility coeffi cients that is completely determined by the global topological propert ies of the graphs under match. We illustrate the application of this n ew theory in two graph matching applications. The first of these is co ncerned with exploiting constraints provided by edges. Here the compat ibility coefficient for consistent edges is equal to the inverse edge- density. Our second illustration extends the compatibility model to th e 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 optim al values.