HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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

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 metadata

Cited literature [9 references]  Display  Hide  Download

https://hal-ujm.archives-ouvertes.fr/ujm-00389763
Contributor : Émilie Samuel Connect in order to contact the contributor
Submitted on : Thursday, June 9, 2011 - 1:08:23 PM
Last modification on : Tuesday, June 1, 2021 - 2:08:07 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

346

Files downloads

231