Comparing and classifying images is an important issue in many applications. It usually requires a similarity measure that is both relevant and easy to compute. When modelling images with Region Adjacency Graphs (RAGs), measuring image similarity turns into graph matching problems that are intractable (NP-hard) in the general case.

RAGs have been extended to combinatorial maps, thus allowing one to model object topology and multi-adjacency. There exist various algorithms to construct or modify combinatorial maps. However, there does not exist similarity measures for comparing maps. The aim of this PhD thesis is to define similarity measures and to design efficient algorithms for computing these measures. Similarity measures will be defined in any dimensions, by means of constraints, in order to provide a generic tool that may be used to measure the similarity of different kinds of objects modelled by maps. In particular, we shall validate our similarity measures and algorithms on 2D and 3D image classification problems.