Randomized Algorithms for Scene Recognition by Inexact Graph Matching

Maria Claudia Boeres (boeresinf.ufes.br)
Celso Ribeiro (celsoinf.puc-rio.br)
Isabelle Bloch (Isabelle.Blochenst.fr)

Abstract: We propose a new method for non-bijective graph matching for model-based pattern recognition. We formulate the search for the best correspondence between a model and an over-segmented image as a new combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together with the node and edge similarities between them. We discuss the choice of the objective function and the nature of the constraints of the graph matching problem. A randomized construction algorithm is proposed to build feasible solutions to the problem. A neighborhood structure and a local search procedure for solution improvement are also proposed. Computational results on ten test instances are presented and discussed, llustrating the effectiveness of the combined approach involving randomized construction and local search.

Keywords: Scene recognition, graph matching, randomized algorithms, heuristics

Category 1: Applications -- Science and Engineering (Biomedical Applications )

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Research report, submitted for publication, 2003.

Download: [Postscript]

Entry Submitted: 10/12/2003
Entry Accepted: 10/12/2003
Entry Last Modified: 10/12/2003

Modify/Update this entry