Floodfill algorithm

Factual Questions
1

Wow, I’m actually going to use this board for a work-related purpose…

Here’s the situation: I have an image (actually, about a third of a million images, so optimization is important) in the form of a 2-d short integer array. I want to be able to specify a pixel within a given region bounded by pixels of a certain value, and fill all pixels within that region to a specified value-- Sort of like the paintbucket tool in MS Paint. If necessary, I can arrange for all of the pixels in that region to start at the same value. I know of a couple of ways to do this, but they’re all of order n[sup]2[/sup] in the total number of pixels, and like I said, optimization is important. I know that there’s some quick way to do it, as Paint and other image-processing programs do it near-instantaneously. Does anyone know how to accomplish this?

If it matters, the language I’m using is IDL, and the platform is UNIX (Solaris and Linux).

2

IDL isn’t a programming language. It’s a way of specifying an interface for CORBA. You still have to implement that interface in a traditional language. Java is my favorite, but for sheer speed in filling up an array with a set value, it’s hard to beat C’s memset.

3

The ugly recursive way (make sure you have plenty of stack)


floodfill(x, y) {
  if pixel(x,y) should be filled
    fill pixel(x,y)
    floodfill(x-1, y)
    floodfill(x+1, y)
    floodfill(x, y-1)
    floodfill(x, y+1)
}

The slicker O(N) way (from Robot Vision, Horn 1994):

Keep this picture in mind:


D C
B A

scan from left to right, top to bottom, labelling the pixels (you could do this with another image of the same size). The pixel you’re currently looking at is A, and you’ve already labled D, C, and B. If the pixel is outside of your fill tolerance, label it 0. If its inside of the fill tolerance, then:
If D has a non-zero label, set A to D’s label.
If either B or C have labels, set A to that label.
If neither B nor C have labels, create a new label for A.
If both B and C have labels, which are different, then what happened was we just discovered that two of the regions we were filling in are connected. So make a note that these regions are the same.

Then, you have a bunch of sets of labels. Find out which label the seed pixel has, and then for every pixel in the image, if it has a label that’s in the seed pixel’s set, color it.

Phew.

So what you’re doing is classifying regions, and the way the classification works, since it only looks up and to the left, could have you start classifying two regions the same.


     XXXX         1111
      XXXX         1111
  XX  XXX      22  111
 XXXXXXX      2222211

So you have to make a note that these represent the same region. And then when you do the actual fill, color in both region 1 and 2.

(somethig tells me you may not need to use cell D. You could try it both ways)

4

Thank you, Hunsecker! That’s exactly what I was looking for. The only thing I’m left wondering there, is what you mean by “fill tolerance”. Is that the values which I’m willing to overwrite?
The inefficient method I was thinking of was more like a cellular automaton, but it’s similar to the recursive method you listed.
I’m not familiar with the Robot Vision book you mention, but does it by chance deal with shape recognition? Interestingly, that’s actually what I’m dealing with here.

5

I think he’s talking about Interactive Data Language, not Interface Definition Language (or whatever the other one is). Interactive Data Language is considered a programming language, but it’s more of a data analysis environment. It’s awesome for handling large images. It’s the standard tool in many fields of astronomy and geology. Unfortunately it’s a commercial software and is rather expensive.

6

Not quite, I lied to you. Technically that algorithm is worst-case O(N log(N)). The N log(N) part comes in after you’ve scanned and labeled the image, and then need to color each pixel that has one of the target labels. Since there can be O(N) different labels, checking to see if the pixel you’re currently looking at has one of those labels is potentially a log(N) operation.

One way I thought to speed it up would be to use powers of two for your labels. So if you find in practice that you’re never using more than, say, 32 labels, you could make each label 2[sup]i[/sup] rather than i. Once you do that, to build the set of target labels, just add all the label values together. And to test if a pixel has a label in the target set, do a bitwise AND with that sum.

(You’ll have to have special code that handles more than 32 labels, and falls back to the slower method)

Yeah. In photoshop (for one) you don’t just fill pixels that are exactly equal to the target pixel, you fill pixels whos colors are within some tolerance of the target. So I wasn’t sure which kind of filling you want.

It does talk a lot about shape recognition (sobel filters, hough transforms, all that good stuff), but its very mathematical. In fact, looking up this flood fill algorithm is about the most use I’ve gotten out of it, we didn’t use it much in my Computer Vision class. It may be worth checking out though.

7

I’m not smart enough to write in a high-level language, but
there are an infinite number of algorithms to handle this. The simplest might be to search backwards from the initial point until the boundary is found. Then you could follow the boundary clockwise, filling in all pixels in each row until the next boundary pixel is found. After each
row is filled, you would jump up one row and search for the boundary one pixel to the left and one to the right. Once you find a row composed solely of boundary pixels, you will have reached the top of that node.
At this point, you must follow the boundary around to the right back down to the initial row to make sure it doesn’t go up again. The bottom half of the fill block should be filled by moving down a row at a time and repeating the same process.

Here are some useful assembly routines:

Assume: EDI points to some pixel
AX = boundary pixel value
DX = fill pixel value

Searching backwards for boundary:

    MOV     ECX,EDI                ;CURRENT LOCATION POINTER TO ECX
    SUB     ECX,LEFT_ROW_START     ;THIS MAY HAVE TO BE CALCULATED
    JECXZ   ATLEFT                 ;AT LEFT EDGE
    STD                            ;"DOWN"
    SHR     ECX,1                  ;FORM WORD COUNT
    REPNZ   SCASW                  ;BOUNDARY PIXEL FOUND?
    CLD                            ;"UP"
    JNZ     NOTFND                 ;NO
    INC     EDI
    INC     EDI                    ;ADJUST TO BOUNDARY PIXEL

The count in ECX may need to be adjusted by 1 to get the correct search count.

Searching forward for boundary:

    MOV     ECX,RIGHT_ROW_END+2    ;POINT TO ROW END+2
    SUB     ECX,EDI                ;CALCULATE PIXEL COUNT
    JECXZ   ATRHT                  ;AT RIGHT EDGE
    SHR     ECX,1                  ;FORM WORD COUNT
    REPNZ   SCASW                  ;BOUNDARY PIXEL FOUND?
    JNZ     NOTFND                 ;NO
    DEC     EDI
    DEC     EDI                    ;ADJUST TO BOUNDARY PIXEL

Filling a block:

    MOV     ECX,FILL_COUNT         ;THIS WILL BE CALCULATED
    MOV     EDI,FILL_START         ;POINT TO FILL START (CALCULATED)
    XCHG    EAX,EDX                ;FILL VALUE TO AX, BOUNDARY VALUE

TO DX
REP STOSW ;FILL ROW
XCHG EAX,EDX ;FILL VALUE TO DX, BOUNDARY VALUE
TO AX

Adjusting pointer up/down a row:

    MOV     EBX,PIXELS_PER_ROW
    NEG     EBX                    ;IF DOWN

    LEA     EDI,[EDI+EBX*2]        ;ADJUST EDI UP OR DOWN 1 ROW
       or
    ADD     EBX,EBX
    ADD     EDI,EBX                ;DOWN

    ADD     EBX,EBX
    SUB     EDI,EBX                ;UP
8

tcburnett:

I could be reading this wrong (since I’m not smart enough to read low-level languages), but from your description I don’t think regions with holes will be handled correctly. For example, if I’m filling a region like this:


     XXOXXXX
   XXXXXXXXXXX
  XXX   XX  XXX
   XX   XX  XX
   XXXXXXXXXX

If my seed is the O on the first row, It doesn’t look like the 4 X’s in between the two holes would get filled.

9

I forgot this earlier, but you may want to look into the Graphics Gems series. They have a lot of common image procssing algorithms in them.

10

This is great stuff… I’ll be sure to let you all know how the end result works. And I could force the whole region to be the same value, but it’ll be a lot easier if I can specify a tolerance like that, Hunsecker. By the way, tcburnett, may I say I’m impressed? I didn’t know that anyone still programmed in Assembly.

11

No, I don’t think they will either. If it turns out to be important, I’ll fix it. What do you expect from an old guy late at night? :slight_smile:

12

I think Greg had a good point about memset. Instead of only trying to make a very efficient algorithm you should also keep in mind how fast that data can be copied. Instead of doing it one pixel at a time you might be better off by using something that affects bigger chunks of memory.