*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/