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.
This software takes some cues from both their implementation and the one by Sofien Bouaziz and Andrea Tagliasacchi (check here).
- 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.
This software is subject to the Apache 2.0 License.