Adapting scanline fill to detect discrete objects

Question

I'm trying to detect contiguous areas of close-enough colors in Python. I independently stumbled across the 8-way recursive flood fill algorithm (terminating when the Euclidian distance between the found and desired RGB colors exceeds a threshold), which works great at small scale, but causes a stack overflow on a 2 megapixel image.

Stack Overflow and Wikipedia point to scanline fill as the answer, but every explanation I've found is either in C++ or about filling a polygon with known vertices. Can someone point me to a good pseudocode explanation for a situation analogous to recursive flood fill?

I'm hitting a wall on researching image segmentation due to a lack of formal mathematics (I'm in high school.) If there is a plain-English explanation of K-Means or something like it, that'd be great too. OpenCV looked promising but it appears all I get is a color-flattened image; all I care about is a list of pixels in the object at x,y.

Abyssinia

Answer 1

The idea of scanline flood fill is the following

1. you are given the initial point (seed) (x, y)
2. go left as far as possible until the pixel (x-1, y) is not to be filled or you get to x=0
3. the x you reached will be the start of scanline; keep two flags "look for caverns above" and "look for caverns below", both initialized at true
4. this is the begin of scanline loop. Check the pixel above (x, y-1) if it's to be filled and now considering the look-above flag and the pixel there are 4 cases:
   • if "look above" is true and the pixel is to be filled then you found a "new cavern", store (x, y-1) in the "to-do-list" and mark "look above" as false
   • if "look above" is false and the pixel is NOT to be filled then the current cavern is complete and you need to look for another one, so just mark "look_above" as true
   • in other cases (look above is true and pixel is not to be filled or look above is false and pixel is to be filled) you just do nothing
5. Repeat the same reasoning with the "look below" flag and the color of pixel (x, y+1)
6. paint the pixel (x, y) and move to (x+1, y), repeating from (5) unless the pixel you move to is not going to be painted.
7. if there is anything in the "to-do list" pick it out and go back at (1) using the coordinates you found in the to-do list as (x, y)

This is the version for a 4-connected flood fill. For an 8-connected fill you also need to check for caverns at (x-1, y-1) and (x-1, y+1) when starting the scanline and you need to check for caverns (x+1, y-1) and (x+1, y+1) at scanline end (if the corresponding flags are true).

When moving on the scanline what you want to do is adding the green points in the picture to your to-do list:

                                                         

Note that the number of seeds will not be "minimal" (for example the first two "above seeds" in the example will end up in the same cavern and therefore only one of them is really needed). Still the amount of stack needed to store them will be normally much smaller than the amount needed for a pixel-by-pixel recursive approach.

Another possible approach to limit the amount of memory needed is using a frontier painting algorithm:

1. You put the initial seed (x, y) in the current_active list and paint it
2. Initialize a next_active list to empty
3. for every pixel in the current_active list check for neighbors that need to be painted: when you find one paint it and add it to the next_active list
4. when you're done set current_active list to next_active list and repeat from 2 unless the list was empty

You can see an example of the two algorithms in action in this video.

Brooklime

Wow! Thanks for the information. Scanline finally makes sense now. I'm actually more intrigued by the "frontier" algorithm, which seems to be the iterative equivalent of what I was doing. Why does Python easily handle a 30,000+ item list but fail when I try for a recursion depth above 10,000? – Abyssinia

I actually went with your "frontier" approach because it seemed to be closest to the original idea and was plenty fast. Still interesting why that's so much faster than the recursive approach, though... – Abyssinia

@jacobbaer: CPython doesn't handle unlimited recursion because it relies on the C stack in the interpreter and the limits on C stack are sometimes quite low. You can raise the python limit with sys.setrecursionlimit, but setting it too high you will just crash python itself instead of getting the exception. Also note that Python doesn't handle tail call optimization and that the pure functional programming view is not really endorsed. Recursion is of course fine, but deep recursion (e.g using recursion to traverse a linked list) is a bad idea. – Brooklime

@Brooklime How do you check if you already filed a line so you don't check the pixel up or down more than once, or is checking pixels more than one unavoidable. – Air

While filling a scanline you look "above" (i.e. y-1) and every time you see a new aperture you place a seed but only one until you see the ceiling closed again. Supposing looking above you see 1100001111100011111011111 you only need to place a seed in third, twelfth and twentieth position. Of course it's possible that placing a seed is not needed because multiple apertures may be part of the same cavern but you cannot know without a global search. – Brooklime

@Brooklime Tnx, this means that some pixels will be checked more than once, right? – Air