I believe that Daniel Huttenlocher and Pedro Felzenszwalb should be credited for...

dahart · on July 21, 2023

I like that paper, but I don’t think it was the first to suggest separating x and y and using multi-pass for distance transforms.

Here are a few that predate and I think make the same observation:

https://dl.acm.org/doi/10.1016/j.ipl.2006.12.005

https://www.sciencedirect.com/science/article/abs/pii/002001...

That second paper from 1996 references an even older paper from 94, saying “Dividing rows and columns alternately, Chen and Chuang reduced the time complexity to O(N^2) which is optimal.”

https://www.sciencedirect.com/science/article/abs/pii/002001...

an1sotropy · on July 21, 2023

Interesting - thanks dahart (hi again!) for pointing out these references. They do seem to be missing in the Cornell report.

JyrkiAlakuijala · on July 21, 2023

I had "invented" that independently for shape based interpolation needs I had in early 2000.