Skip to content

giorgiomarcias/distance_transform

Repository files navigation

C++ Distance Transform

This software is a C++11 implementation of the algorithm described in:

** * Distance Transforms of Sampled Functions * **
Pedro F. Felzenszwalb, Daniel P. Huttenlocher
Theory of Computing, Vol. 8, No. 19, September 2012

See their project site.

The paper describes a linear-time algorithm for solving a class of minimization problems involving a cost function with both local and spatial terms. Such problems can be viewed as a generalization of classical distance transforms of binary images, where the binary image is replaced by an arbitrary sampled function. Consequently, it can be used as a simple, fast method for computing the Euclidean distance transform of a binary image.

Note

This software takes some cues from both their implementation and the one by Sofien Bouaziz and Andrea Tagliasacchi (check here).

Features:

  • N-Dimensional: The implementation by Felzenszwalb and Huttenlocher works only with 2-D images. Here I provide an implementation that works with arrays of any dimension N.
  • Low memory usage: By using dope vectors, there is not need of copying array data around during the computation.
  • Index of nearest element: Optionally get the index (as the linear distance from the beginning of a mono-dimensional array - see the example) of the nearest element to the one at any position in the array. Not just its distance (taken from the implementation by Sofien Bouaziz and Andrea Tagliasacchi).
  • **Parallel execution by giving the number of threads to spread.

License

This software is subject to the Apache 2.0 License.

About

Distance Transforms of Sampled Functions

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published