Treffer: A parallel Euclidean distance transformation algorithm
Title:
A parallel Euclidean distance transformation algorithm
Authors:
Source:
Computer vision and image understanding (Print). 63(1):15-26
Publisher Information:
San Diego, CA: Elsevier, 1996.
Publication Year:
1996
Physical Description:
print, 12 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Physique, Physics, Domaines classiques de la physique (y compris les applications), Fundamental areas of phenomenology (including applications), Optique, Optics, Formation des images et traitement optique, Imaging and optical processing, Formation et traitement des images, Image forming and processing, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Intelligence artificielle, Artificial intelligence, Reconnaissance des formes. Traitement numérique des images. Géométrie algorithmique, Pattern recognition. Digital image processing. Computational geometry, Algorithme parallèle, Parallel algorithm, Algoritmo paralelo, Algorithme rapide, Fast algorithm, Algoritmo rápido, Complexité calcul, Computational complexity, Complejidad computación, Diagramme Voronoï, Voronoï diagram, Diagrama Voronoi, Distance, Distancia, Géométrie euclidienne, Euclidean geometry, Geometría euclidiana, Image binaire, Binary image, Imagen binaria, Méthode diviser pour régner, Divide and conquer method, Método dividir para vencer, Timing, Transformation déplacement, Displacive transformation, Transformación desplazamiento, Algorithme séquentiel, Sequential algorithm, Load imbalance
Document Type:
Fachzeitschrift
Article
File Description:
text
Language:
English
Author Affiliations:
Katholieke univ. Leuven, dep. computerwetenschappen, 3001 Heverlee, Belgium
ISSN:
1077-3142
Rights:
Copyright 1996 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Physics: optics
Physics: optics
Accession Number:
edscal.3005999
Database:
PASCAL Archive
Weitere Informationen
We present a parallel algorithm for the Euclidean distance transformation (EDT). It is a divide-and-conquer algorithm based on a fast sequential algorithm for the signed EDT (SEDT). The combining step that follows the local partial calculation of the SEDT can be done efficiently after reformulating the SEDT problem as the partial calculation of a Voronoi diagram. This leads to an algorithm with two local calculation steps with a computational complexity proportional to the number of pixels of the subregions and a global calculation step with complexity proportional to the image perimeter. This article contains a description of the algorithm, a complexity analysis, a discussion on load imbalance, and timings obtained on an iPSC/2.