Abstract:

Graph matching is often used for image recognition. Different kinds of graph matchings have been proposed, e.g., (sub)graph isomorphism, error-tolerant graph matching. These graph matchings have given rise to different distance measures that can be used to measure the similarity of two graphs.

A first goal of this paper is to show that these different distance measures can be viewed as special cases of a generic similarity measure introduced in [Champin et al.03]. We show that this measure, originally used to compare design objects, is well suited to image recognition. In particular, it is based on a non-bijective graph matching (like [Boereset al.04] and [Ambauen et al.03]) so that over/under-segmentation problems can be handled by linking one vertex to a set of vertices.

In a second part, we address the problem of computing this measure and we describe two algorithms: a greedy algorithm, that quickly computes sub-optimal solutions, and a reactive Tabu search algorithm, that may improve these solutions. Some experimental results are given.