A Work Efficient Parallel Algorithm for Exact Euclidean Distance Transform
- Submitting institution
-
Swansea University / Prifysgol Abertawe
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 50104
- Type
- D - Journal article
- DOI
-
10.1109/TIP.2019.2916741
- Title of journal
- IEEE Transactions on Image Processing
- Article number
- -
- First page
- 5322
- Volume
- 28
- Issue
- 11
- ISSN
- 1057-7149
- Open access status
- Compliant
- Month of publication
- May
- Year of publication
- 2019
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
-
- Research group(s)
-
-
- Citation count
- 3
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Euclidean Distance maps have been a significant area of research since the 1960s, underpinning new applications such as 3D printing and 3D object matching. We introduce the first fully parallelized work-time optimal algorithm for Euclidean Distance Transform. It is the first to achieve O(logn) complexity for all algorithm stages and uses GPU warp for constant speed-up (moving from log base 2 to log base 32).
Unlike previous algorithms, we retain exactness without any failure cases. We demonstrate this through algorithm descriptions, diagrams, and proofs. We validate on very large image sizes (exceeding previous testing image sizes).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -