What do you call an iterated flood fill algorithm?

Question

I have an algorithm that I'm using for my work, but I need a name for it. I am curious if name exists in the literature for an algorithm of this type.

The algorithm takes a pixelated height map and a starting point s, and returns a modified pixelated height map. For each pixel p in the returned height map, p is the value of lowest height you must pass through to get from s to p.

Example, consider the "peak" image in Matlab: imagesc(peak) .

And use the pixel (20,20) as the seed, then this modified height map I am describing looks like this: .

I had called this a flood fill algorithm, until my colleagues pointed out that flood fills are typically binary maps. So, Ive taken to calling this a "graduated flood fill" algorithm.

We have not found this operation defined in the literature. Any suggestions?

Answer 1

I've worked in image processing a bit, but I've never come across an algorithm that does this before. So you can call it whatever you like, really. How about the "John" algorithm ;-)

Alternatively, you could consider calling it a "least descent" algorithm (or least descent filter, perhaps), since it effectively calculates the smallest amount of descent necessary to travel from one point to any other.

I'd avoid the word "fill" altogether, since it usually describes algorithms that are used to fill areas with a solid colour.

Answer 2

This algorithm has similarity to "distance transform" in that it is also about a path. Thus, "minimum descent transform" or "minimum path descent transform" may be an idea, since the pixel value becomes the lowest value one needs to descend to on the way to the seed point.