Polynomial Algorithm for Submap Isomorphism: Application to searching patterns in images

Guillaume Damiand 1, 2 Colin de la Higuera 3 Jean-Christophe Janodet 3 Émilie Samuel 3 Christine Solnon 1
1 M2DisCo - Geometry Processing and Constrained Optimization
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
2 SIC
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-ujm.archives-ouvertes.fr/ujm-00389763
Contributor : Émilie Samuel <>
Submitted on : Thursday, June 9, 2011 - 1:08:23 PM
Last modification on : Tuesday, February 26, 2019 - 4:26:16 PM
Long-term archiving on : Friday, November 9, 2012 - 2:56:25 PM

File

map-isomorphism.pdf
Files produced by the author(s)

Identifiers

Citation

Guillaume Damiand, Colin de la Higuera, Jean-Christophe Janodet, Émilie Samuel, Christine Solnon. Polynomial Algorithm for Submap Isomorphism: Application to searching patterns in images. Graph-based Representations in Pattern Recognition (GbRPR), May 2009, Venise, Italy. pp.102-112, ⟨10.1007/978-3-642-02124-4_11⟩. ⟨ujm-00389763⟩

Share

Metrics

Record views

580

Files downloads

250