From Maximum Common Submaps to Edit Distances of Generalized Maps

Abstract: Generalized maps are widely used to model the topology of nD objects (such as images) by means of incidence and adjacency relationships between cells (vertices, edges, faces, volumes, ...). In this paper, we introduce distance measures for comparing generalized maps, which is an important issue for image processing and analysis. We introduce a first distance measure which is defined by means of the size of a largest common submap. This distance is generic: it is parameterized by a submap relation (which may either be induced or partial), and by weights to balance the importance of darts with respect to seams. We show that this distance measure is a metric. We also introduce a map edit distance, which is defined by means of a minimum cost sequence of edit operations that should be performed to transform a map into another map. We relate maximum common submaps with the map edit distance by introducing special edit cost functions for which they are equivalent. We experimentally evaluate these distance measures and show that they may be used to classify meshes.

Keywords: Generalized map; Edit distance; Partial submap isomorphism; Metric distance