Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
A Polynomial Algorithm for Submap Isomorphism
Application to Searching Patterns in Images
verfasst von : Guillaume Damiand, Colin de la Higuera, Jean-Christophe Janodet, Émilie Samuel, Christine Solnon
Erschienen in: Graph-Based Representations in Pattern Recognition
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.