Polynomial Algorithms for Subisomorphism of nD Open Combinatorial Maps
| Autor: | Colin de la Higuera, Guillaume Damiand, Jean-Christophe Janodet, Christine Solnon, ímilie Samuel |
|---|---|
| Přispěvatelé: | Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire d'Informatique de Nantes Atlantique (LINA), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Hubert Curien [Saint Etienne] (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), ANR-07-BLAN-0317,SATTIC,Strings and Trees for Thumbnail Images Classification(2007), European Project: 216886,EC:FP7:ICT,FP7-ICT-2007-1,PASCAL2(2008), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Hubert Curien (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2011 |
| Předmět: |
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Image processing 0102 computer and information sciences 02 engineering and technology 01 natural sciences Polynomial algorithm Isomorphism and subisomorphism 2D and 3D images 0202 electrical engineering electronic engineering information engineering Open combinatorial maps Time complexity Subdivision Incidence (geometry) Mathematics Discrete mathematics business.industry Pattern detection 010201 computation theory & mathematics [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV] Signal Processing Adjacency list 020201 artificial intelligence & image processing Computer Vision and Pattern Recognition Isomorphism business Generalized map Software |
| Zdroj: | Computer Vision and Image Understanding Computer Vision and Image Understanding, Elsevier, 2011, 115 (7), pp.996-1010. ⟨10.1016/j.cviu.2010.12.013⟩ Computer Vision and Image Understanding, 2011, 115 (7), pp.996-1010. ⟨10.1016/j.cviu.2010.12.013⟩ |
| ISSN: | 1077-3142 1090-235X |
| DOI: | 10.1016/j.cviu.2010.12.013⟩ |
| Popis: | International audience; Combinatorial maps describe the subdivision of objects in cells, and incidence and adjacency relations between cells, and they are widely used to model 2D and 3D images. However, there is no algorithm for comparing combinatorial maps, which is an important issue for image processing and analysis. In this paper, we address two basic comparison problems, i.e., map isomorphism, which involves deciding if two maps are equivalent, and submap isomorphism, which involves deciding if a copy of a pattern map may be found in a target map. We formally define these two problems for nD open combinatorial maps, we give polynomial time algorithms for solving them, and we illustrate their interest and feasibility for searching patterns in 2D and 3D images, as any child would aim to do when he searches Wally in Martin Handford's books. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect