Scan fill adaptation for discrete object detection

Question

I am trying to detect contiguous areas of fairly close colors in Python. I myself came across an 8-sided recursive fill filling algorithm (ending when the Euclidean distance between the found and the desired RGB colors exceeds the threshold), which works fine on a small scale, but causes a stack overflow on a 2-megapixel image.

Stack overflow and Wikipedia indicate filling the line as an answer, but each explanation I found is either in C ++ or filling the polygon with known vertices. Can someone please give me a good explanation of the pseudo-code for a situation similar to a recursive fill of a fill?

I am on the wall researching image segmentation due to a lack of formal math (I'm in high school). If there is a simple English explanation for K-Means or something like that, it will be great too. OpenCV looked promising, but it seems that all I get is color smoothing; all i care about is a list of pixels in an object in x, y.

Answer 1

The scanline fill idea is as follows

• you are given the starting point (seed) (x, y)
• go as far as possible until the pixel (x-1, y) is full or you get x = 0
• x you will reach the start of scanline; hold two flags "look for caves above" and "look for caves below", both initialized to true
• This is the start of the scanline cycle. Check the pixel above (x, y-1) if it is full, and now, given the label flag and pixel, there are 4 cases:
  • If the “look above” is true and the pixel needs to be filled, then you find a “new cave”, save (x, y-1) in the “to-do list” and mark “look above” as false
  • If the “look above” is false and the pixel is NOT filling, then the current cave is complete and you need to look for another, so just mark “look_above” as true
  • in other cases (see above, true, and the pixel should not be filled or look higher - this is false, and the pixel should be filled), you just do nothing
• Repeat the same reasoning with the “see below” flag and the pixel color (x, y + 1)
• draw a pixel (x, y) and go to (x + 1, y), repeating (5) if the pixel that you moved will not be painted.
• if there is anything in the to-do list and go back to (1) using the coordinates you found in the to-do list like (x, y)

This is the version for 4-connected fill fill. For an 8-connected filling, you also need to check for the caves in (x-1, y-1) and (x-1, y + 1) when starting the scan line, and you need to check for the caves (x + 1, y -1 ) and (x + 1, y + 1) at the end of the scanline (if the corresponding flags are correct).

When moving along the scan line, what you want to do is add green dots in the picture to the to-do list:

Please note that the number of seeds will not be "minimum" (for example, the first two "above the seeds" in the example will end up in the same cave, and therefore only one of them is really necessary). However, the amount of stack required to store them will usually be much less than the amount needed for the pixel recursive approach.

Another possible approach to limiting the amount of required memory is to use the border graphics algorithm:

• You put the seed (x, y) in the current_active list and draw it
• Initialize next_active list to empty
• for each pixel in the current_active list, check for the neighbors to be painted: when you find one paint and add it to the next_active list
• when you are done set the current_active list to the next_active list and repeat from 2 if the list was not empty.

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