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 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 : Wednesday, July 8, 2020 - 12:43:34 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

637

Files downloads

336