Euclidian Distance Transform Algorithms : A comparative study

We compare the most frequently used algorithms for computing distance transforms in terms of speed, scalability and accuracy. The algorithms we consider are: partial differential equation based distancing methods of different finite difference accuracy, fast marching methods and fast sweeping methods. Our results show clearly that all the first order algorithms perform similarly in terms of accuracy and that the only major difference is efficiency. In parallel with the revision of the preprint we find that the newly proposed O(N) quantized fast marching algorithm in practice does not scale linearly