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.

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.