Elastic graph matching

Elastic graph matching is the basic process to compare graphs with images and to generate new graphs. In its simplest version a single labeled graph is matched onto an image. A labeled graph has a set of jets arranged in a particular spatial order. A corresponding set of jets can be selected from the Gabor-wavelet transform of the image. The image jets initially have the same relative spatial arrangement as the graph jets, and each image jet corresponds to one graph jet. The similarity of the graph with the image then is simply the average jet similarity between image and graph jets.

In order to increase the similarity one allows the graph to translate, scale and distord to some extent, resulting in a different selection of image jets. The distortion and scaling is limited by a penalty term in the matching cost function. The image jet selection which leads to the highest similarity with the graph is used to generate a new graph.

When a bunch graph is used for matching, the procedure gets only a little bit more complicated. Beside selecting different image locations the graph similarity is also maximized by selecting the best fitting jet in each bunch. This is done independently of the other bunches to take full advantage of the combinatorics of the bunch graph representation.

setup May 20, 1996 or earlier; updated May 20, 1996
Laurenz Wiskott, http://www.neuroinformatik.ruhr-uni-bochum.de/PEOPLE/wiskott/