A randomized heuristic for scene recognition by graph matching

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

Abstract: We propose a new strategy for solving the non-bijective graph matching problem in model-based pattern recognition. The search for the best correspondence between a model and an over-segmented image is formulated as a 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. A randomized construction algorithm is proposed to build feasible solutions to the problem. Two neighborhood structures and a local search procedure for solution improvement are also proposed. Computational results are presented and discussed, illustrating the effectiveness of the combined approach involving randomized construction and local search.

Keywords: Scene recognition, graph matching, randomized algorithm, local search, GRASP

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

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Research report, Catholic University of Rio de Janeiro, Department of Computer Science, February 2004.

Download: [Postscript]

Entry Submitted: 04/05/2004
Entry Accepted: 04/05/2004
Entry Last Modified: 04/05/2004

Modify/Update this entry