Publication

Graduated assignment algorithm for finding the common labelling of a set of graphs

Conference Article

Conference

Joint IAPR International Workshop on Structural, Syntactic and Statistical Pattern Recognition (SSPR&SPR)

Edition

13th

Pages

180-190

Doc link

http://dx.doi.org/10.1007/978-3-642-14980-1_17

File

Download the digital copy of the doc pdf document

Abstract

In pattern recognition applications, it is useful to represent objects by attributed graphs considering their structural properties. Besides, some graph matching problems need a Common Labelling between vertices of a set of graphs. Computing this Common Labelling is an NP-complete problem. State-of-the-art algorithms are composed by two steps: in the first, they compute all pairwise labellings among the graphs and in the second, they combine this information to obtain a Common Labelling. The drawback of these methods is that global information is only considered in the second step. To solve this problem, by reducing the Common Labelling problem to the quadratic assignment one, all graphs nodes are labelled to a virtual structure whereby the Common Labeling is generated using global information. We tested the algorithm on both real-world and synthetic data. We show that the algorithm offers better performance than a reference method with same computational cost.

Categories

pattern matching, pattern recognition.

Author keywords

graduated assignment, multiple graph matching, graph common labelling, inconsistent labelling, softassign

Scientific reference

A. Solé and F. Serratosa i Casanelles. Graduated assignment algorithm for finding the common labelling of a set of graphs, 13th Joint IAPR International Workshop on Structural, Syntactic and Statistical Pattern Recognition, 2010, Izmir, Turkey, in Structural, Syntactic, and Statistical Pattern Recognition, Vol 6218 of Lecture Notes in Computer Science, pp. 180-190, 2010, Springer, Berlin.