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.
Citation
Research report, submitted for publication, 2003.