Optimization Online


A randomized heuristic for scene recognition by graph matching

Maria Claudia Boeres (boeres***at***inf.ufes.br)
Celso Ribeiro (celso***at***inf.puc-rio.br)
Isabelle Bloch (Isabelle.Bloch***at***enst.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society