Polynomial Algorithm for Submap Isomorphism: Application to searching patterns in images - Archive ouverte HAL Access content directly
Conference Papers Year : 2009

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

(1) , (2) , (2) , (2) , (1)
1
2

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.
Fichier principal
Vignette du fichier
map-isomorphism.pdf (183.71 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

ujm-00389763 , version 1 (09-06-2011)

Identifiers

Cite

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⟩
349 View
244 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More