Measuring the Distance of Generalized Maps

Combier C., Damiand G., Solnon C.

Proc. of 8th Workshop on Graph-Based Representation in Pattern Recognition (GBR)
Lecture Notes in Computer Science 6658, pages 82-91, May 2011, Münster, Germany

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 define a first error-tolerant distance measure for comparing generalized maps, which is an important issue for image processing and analysis. This distance measure is defined by means of the size of a largest common submap, in a similar way as a graph distance measure may be defined by means of the size of a largest common subgraph. We show that this distance measure is a metric, and we introduce a greedy randomized algorithm which allows us to efficiently compute an upper bound of it.

Keywords: Generalized Map; Distance; Maximum Common Submap; Approximation Algorithm.

BibTex references

@InProceedings{CDS11,
      author = {Combier, C. and Damiand, G. and Solnon, C.},
      title = {Measuring the Distance of Generalized Maps},
      booktitle = {Proc. of 8th Workshop on Graph-Based Representation in Pattern Recognition (GBR)},
      series = {Lecture Notes in Computer Science},
      publisher = {Springer Berlin/Heidelberg},
      volume = {6658},
      pages = {82-91},
      month = {May},
      year = {2011},
      address = {M\ünster, Germany},
      keywords = {Generalized Map; Distance; Maximum Common Submap; Approximation Algorithm.},
      url = {https://doi.org/10.1007/978-3-642-20844-7_9}
}

Guillaume Damiand

Measuring the Distance of Generalized Maps

Links:

BibTex references

Image