Fast Convolutional Distance Transform

Christina Karam*, Kenjiro Sugimoto, Keigo Hirakawa

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


We propose 'convolutional distance transform' - efficient implementations of distance transform. Specifically, we leverage approximate minimum functions to rewrite the distance transform in terms of convolution operators. Thanks to the fast Fourier transform, the proposed convolutional distance transforms have \mathcal {O}(N\log N) complexity, where N is the total number of pixels. The proposed acceleration technique is 'distance metric agnostic.' In the special case that the distance function is a p-norm, the distance transform can be further reduced to separable convolution filters; and for Euclidean norm, we achieve \mathcal {O}(N) using constant-time Gaussian filtering.

Original languageEnglish
Article number8686167
Pages (from-to)853-857
Number of pages5
JournalIEEE Signal Processing Letters
Issue number6
Publication statusPublished - 2019 Jun


  • Convolution
  • distance transform

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Fast Convolutional Distance Transform'. Together they form a unique fingerprint.

Cite this