Inexact matching of structural models based on the duality of patterns and classifiers

Abstract

In many computer vision problems, the essential information can be most easily interpreted in the form of structural models. However, the computation of distances between structural models can be difficult, since small changes in the underlying image data often cause significant differences in the graph layout. The other way around, changes in the link structure of a graph often mean complex changes in feature attributes or do not correspond to any valid visual data at all. In contrast, structural models can often be used conveniently for the classification of a pattern. Based on this observation, we propose to shift the graph matching problem to the easier problem of matching classifiers and patterns. The similarity between two models is detected if a model serving as a pattern can be recognised by another model serving as classifier. To extend this measure beyond single binary digits, models are compared to whole sets of other models. Single models are described by the vector of similarities to the set. Further comparisons between models can be done using appropriate distance functions on the vector representation. The use of the method is demonstrated in a graph clustering task. We also discuss the numerical stability of the method with respect to the dimensionality of the descriptors.