2D Subquadratic Separable Distance Transformation for Path-Based Norms - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

2D Subquadratic Separable Distance Transformation for Path-Based Norms

Résumé

In many applications, separable algorithms have demon- strated their efficiency to perform high performance volumetric com- putations, such as distance transformation or medial axis extraction. In the literature, several authors have discussed about the conditions on the metric to be considered in a separable approach. In this article, we present generic separable algorithms to efficiently compute Voronoi maps and distance transformations for a large class of metrics. Focusing to path based norms (chamfer masks, neighborhood sequences, ...), we detail a subquadratic algorithm to compute such volumetric transformations in dimension 2. More precisely, we describe a O(log2 m · N2) algorithm in dimension 2 for shapes in a N × N domain with chamfer norm of size m.
Fichier principal
Vignette du fichier
Liris-6698.pdf (7.1 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01118477 , version 1 (19-02-2015)

Identifiants

  • HAL Id : hal-01118477 , version 1

Citer

David Coeurjolly. 2D Subquadratic Separable Distance Transformation for Path-Based Norms. 18th International Conference on Discrete Geometry for Computer Imagery, Sep 2014, Siena, Italy. pp.75-87. ⟨hal-01118477⟩
138 Consultations
110 Téléchargements

Partager

Gmail Facebook X LinkedIn More