Space-efficient pointwise computation of the distance transform on GPUs

Numair Khan, Mohamed Zahran

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

To minimize the amount of computation, traditional approaches to calculating the distance transform (DT) on a discrete volume propagate distance values in a local neighborhood. This results in recursive dependencies across the volume, requiring the DT to be calculated for all points in the domain en mass and stored as static values in memory. On the other hand, the ability to calculate the distance transform point-wise not only offers the prospect of efficient memory usage and scalability, but also a high degree of flexibility in accommodating the unique requirements of new application domains. However, among the current DT algorithms, the computationally intensive brute-force algorithm is the only one that allows point-wise computation. We demonstrate that the by decomposing it into a map and a reduction pattern on the massively parallel architecture of a modern Graphics Processing Unit (GPU), the brute-force distance transform algorithm achieves the threefold goals of memory efficiency, flexibility, and performance. We discuss a memory constrained implementation in the CUDA parallel programming model. The flexibility of point-wise computation at runtime is demonstrated by presenting an approximate and an anisotropic variant of the standard distance transform algorithm, and using these variants for the rendering of a CT scan image. Our approach allows the distance transform to be calculated for 1024 query points and up to 16 million feature points in 141.25 milliseconds while allowing direct control over the memory working-set size. These results demonstrate the potential of pointwise computation of the DT at runtime and the need for future algorithms to incorporate this capability.

Original languageEnglish (US)
Title of host publicationProceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages557-566
Number of pages10
ISBN (Electronic)9781538634080
DOIs
StatePublished - Jun 30 2017
Event31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017 - Orlando, United States
Duration: May 29 2017Jun 2 2017

Publication series

NameProceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017

Conference

Conference31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
CountryUnited States
CityOrlando
Period5/29/176/2/17

Keywords

  • Anisotropic
  • Approximate
  • Map
  • Medical Imaging
  • Memory
  • Patterns
  • Reduction
  • Rendering
  • Vision

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Information Systems

Fingerprint Dive into the research topics of 'Space-efficient pointwise computation of the distance transform on GPUs'. Together they form a unique fingerprint.

Cite this