Polynomial Algorithm for Submap Isomorphism: Application to Searching Patterns in Images

Damiand G., De La Higuera C., Janodet J.-C., Samuel E., Solnon C.

Proc. of 7th Workshop on Graph-Based Representation in Pattern Recognition (GBR)
Lecture Notes in Computer Science 5534, pages 102-112, May 2009, Venice, Italy

Abstract: In this paper, we address the problem of searching for a pattern in a plane graph, i.e., a planar drawing of a planar graph. To do that, we propose to model plane graphs with 2-dimensional combinatorial maps, which provide nice data structures for modelling the topology of a subdivision of a plane into nodes, edges and faces. We define submap isomorphism, we give a polynomial algorithm for this problem, and we show how this problem may be used to search for a pattern in a plane graph. First experimental results show the validity of this approach to efficiently search for patterns in images.

BibTex references

@InProceedings{DHJSS09,
      author = {Damiand, G. and De La Higuera, C. and Janodet, J.-C. and Samuel, E. and Solnon, C.},
      title = {Polynomial Algorithm for Submap Isomorphism: Application to Searching Patterns in Images},
      booktitle = {Proc. of 7th Workshop on Graph-Based Representation in Pattern Recognition (GBR)},
      series = {Lecture Notes in Computer Science},
      publisher = {Springer Berlin/Heidelberg},
      volume = {5534},
      pages = {102-112},
      month = {May},
      year = {2009},
      address = {Venice, Italy},
      url = {https://doi.org/10.1007/978-3-642-02124-4_11}
}

Guillaume Damiand

Polynomial Algorithm for Submap Isomorphism: Application to Searching Patterns in Images

Links:

BibTex references

Image