Fastest available algorithm for distance transform
I am looking for the fastest available algorithm for distance transform.
According to this site http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm, it describes: "The distance transform can be calculated much more efficiently using clever algorithms in only two passes (e.g. Rosenfeld and Pfaltz 1968)."
Searching around, I found: "Rosenfeld, A and Pfaltz, J L. 1968. Distance Functions on Digital Pictures. Pattern Recognition, 1, 33-61."
But I believe we should have a better and faster algorithm than the one in 1968 already? In fact, I could not find the source from 1968, so any help is highly appreciated.
Answer
This paper reviews the known exact distance transform algorithms:
"2D Euclidean distance transform algorithms: A comparative survey"
http://liu.diva-portal.org/smash/get/diva2:23335/FULLTEXT01
The fastest exact distance transform is from Meijster:
"A General Algorithm for Computing Distance Transforms in Linear Time."
http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf
The design of the algorithm is particularly well suited for parallel calculation.
This is implemented in my open source library which tries to emulate Photoshop's "Layer Style:"