# Flood Fill

I know that RGBSurface has a flood command, and I use it quite often… however I have a special need

I need to replicate the function, but instead of replacing color X with Color Y … .
I need to flood with Color Y where pixels meet a range of colors… which will be the result of a function I already have

``if color_match(seed,rs.pixel(x,y)) then rs.pixel(x,y)=new_color``

where “seed” is a pre-determined base color, and color_match determines if the comparison of “seed” vs a given pixel meets my criteria

I’ve tried two basic flood algorithms… one causes a stack overflow… the other “works”… but takes an extremely long time (like 30 seconds)…

Might Transform help you here? For each seed, map a new color, then just transform. Maybe something like this:

``````// Initialize the maps
dim redMap( 255 ), greenMap( 255 ), blueMap( 255 ) as Integer
for i as integer = 0  to 255
redMap( i ) = i
greenMap( i ) = i
blueMap( i ) = i
next i

// Let's say just one seed
redMap( seed.Red ) = newColor.Red
greenMap( seed.Green ) = newColor.Green
blueMap( seed.Blue ) = newColor.Blue

rs.Transform( redMap, greenMap, blueMap )``````

Since you need a range around each seed, it would be something like that.

That would tranforms EVERY pixel (I use this for color inversions

I need a FLOOD fill… where it starts with a given point, and transforms all connected pixels that fan out from that point, but ONLY meet a given criteria (in this case are +/- a particular tolerance… like all “reddish” pixels)

Think of it this way. you have a picture with grass and sky… the sky is made up of “shades” of blue. you click on a pixel in the sky area, and the entire sky is selected (random shaped polygon, not a square or rectangle). The grass area is NOT selected, becuase the app is searching for only “bluish” pixels.

But if the grass area had a blue lake in it, that area would NOT be selected, because it was not “connected” to the sky.

This is the algormithm I found, but seems to take forever

where “SEED” it the base pixel color , and color_compare returns TRUE is seed is +/- a given tolerance from pixel being examined
for testing… they must be equal (one step at a time)

``````  Const mask_color=&c010101
Dim px As Color
dim pt as point_record
flood_stack.append Point_of(x,y)
While flood_stack.ubound>=0
pt=flood_stack.Pop
x=pt.x
y=pt.y
If x>=0 And y>=0 And x<work_area.Width Or y<work_area.Height Then
//
px=temp_rs.Pixel(x,y)
If color_compare(px,seed) Then
//
flood_stack.append point_of(x + 1, y)
flood_stack.append point_of(x - 1, y)
flood_stack.append point_of(x,     y + 1)
flood_stack.append point_of(x,     y - 1)
End If
End If
Wend``````

Have you tried doing a profile to see where it’s slow?

It is slow because it isn’t smart enough to avoid pixels it has already done, (it touches each pixel avg of 3 times)…

So… I cheated

Below will take an image 3680x2070 and mask off the desired area in 1.3 seconds … not great but better that close to 60 seconds for the above method

``````FUNCTION mask_area(x as integer, y as integer)
#If Not DebugBuild
#pragma DisableBoundsChecking
#pragma DisableAutoWaitCursor
#pragma StackOverflowchecking False
#pragma NilObjectChecking False
#EndIf
Dim px As Color
Dim pt As point_record
Dim yy As Integer
Dim xx As Integer
//
// Step 01 - Change every pixel close to "seed" color to mask_color1
//           Change everything else to mask_color2
//
For yy=0 To work_area.height-1
For xx=0 To work_area.width-1
px=temp_rs.Pixel(xx,yy)
If color_compare(px,seed) Then
Else
End If
Next xx
Next yy
//
//  Step 02 - Change Designated Area (mask_color1) to pure SEED value
//
temp_rs.FloodFill x,y,seed
//
//  RGBSurface is now 3 colors .... keep ONLY SEED color area(s)
//  Change desired area BLACK, everything else WHITE
//
For yy=0 To work_area.height-1
For xx=0 To work_area.width-1
px=temp_rs.Pixel(xx,yy)
If px=seed Then
temp_rs.pixel(xx,yy)=&c000000
Else
temp_rs.Pixel(xx,yy)=&cffffff
End If
Next xx
Next yy``````

If you can think of anyway to make it faster still… I’m open

2nd set of loops could ‘probably’ be replaced with a transform… but I have trouble getting my head around those mappings

Some ideas that may or may not help or insignificantly

Precompute these values: work_area.Width, work_area.Height.

If point_of() is constructing an instance try switching the stack to 2 parallel xy arrays.

Break it up into a few function calls and Profile to narrow down whats taking so long.

I haven’t fully followed the algorithm but it looks like pixels are being tested multiple times. Where does this algo come from?

Don’t add pixels to the stack that aren’t in bounds.

Pass temp_rs.Pixel(x,y) directly to color_compare()?

Pragmas

Can you post the code behind color_compare? And where is that located, in a class or module?

I think the last loop could be replaced with this:

``````dim redMap( 255 ), greenMap( 255 ), blueMap( 255 ) as integer

// Only mask_color1, mask_color2, and seed exist in the image now

redMap( mask_color1.Red ) = &hFF
greenMap( mask_color1.Green ) = &hFF
blueMap( mask_color1.Blue ) = &hFF

redMap( mask_color2.Red ) = &hFF
greenMap( mask_color2.Green ) = &hFF
blueMap( mask_color2.Blue ) = &hFF

redMap( seed.Red ) = &h00
greenMap( seed.Green ) = &h00
blueMap( seed.Blue ) = &h00

temp_rs.Transform( redMap, greenMap, blueMap )``````

If there is overlap between the seed and either of the mask colors, you’re in trouble, so you might want to put some defensive code in for that.

Having said that, you are looking at every pixel of the image even if the area you want to affect is very small, so it seems like the first version should be faster as long as you put in some sort of flag to keep track of the pixels you’ve already touched. A two-dimensional boolean array would do the trick, and you just mark a particular pixel as true after you’ve considered it. When adding new pixels to the stack, check the array first and skip it if it’s already been considered.

Right now Color_Compare is a simple (clr1=clr2), but will be replaced with a more complex equation after I get the rest of the routine working.

I realize the issue if SEED and either mask colors are the same, which is why I picked such obscure mask colors

The first alogrithm is not mine, and I have search the web, and every single instance I found (regardless of the langauge) was exactly that way… So I figure if it could easily be made faster, someone would have done so already.

Let me try your transform idea … THANKS

I wouldn’t assume that since other languages have other optimizations, and right now, Xojo has barely any. In Xojo, you want to minimize the number of method calls and number of additions to the stack. It’s more code, but I think it can be made faster.

Since you’re already in a position to test, and if you wouldn’t mind, I’ll post another version of that code for you to try. If I’m wrong, I’m wrong, but at least we’ll know.

If you’re willing, I’ll do that later this afternoon.

FYI… your transform idea didn’t work

While it did in fact change my selected area black as desired… it altered other areas to colors (yellow and cyan) that were not in the selected area… but it did do it FAST

I had a white background with 5 GREEN shapes… it turned the selected green shape to black, the non-selected green shapes to yellow and the background to cyan

Weird, then I’m misunderstanding something. What if you initialize the maps first?

``````dim redMap( 255 ), greenMap( 255 ), blueMap( 255 ) as integer

for i as integer = 0 to 255
redMap( i ) = i
greenMap( i ) = i
blueMap( i ) = i
next i

// Only mask_color1, mask_color2, and seed exist in the image now

redMap( mask_color1.Red ) = &hFF
greenMap( mask_color1.Green ) = &hFF
blueMap( mask_color1.Blue ) = &hFF

redMap( mask_color2.Red ) = &hFF
greenMap( mask_color2.Green ) = &hFF
blueMap( mask_color2.Blue ) = &hFF

redMap( seed.Red ) = &h00
greenMap( seed.Green ) = &h00
blueMap( seed.Blue ) = &h00

temp_rs.Transform( redMap, greenMap, blueMap )``````

Tried that (and other combinations as well)

The selected area changes as desired… but every other colored pixel on the image changes to something else (NOT white)

each array affects the color (red,green or blue) independent of the others

So any color that has the same RED value as SEED has its RED value set to zero, but its GREEN and BLUE would stay the SAME
likewise for the GREEN and BLUE… if they were the same they’d be set to zero, but the other two componets would remain the same.

So if SEED were &cAABBCC … all matching colors would be come BLACK
but &cAA1234 would become &c001234 not white

@Dave S Are you using it for blob detection? It’s because I’m working on this also for eye tracking at his moment and I’m looking into similar functions

Perhaps the other areas colors are not important as long as Ihave a solid colored area filled…

Let me go further to explain where I want to end up.

1. User selects a pixel from the image
2. app flood fills the image with a solid known color for all similar colors (turn the various blues in a sky to a solid single blue for example)
3. THEN… working from the original X,Y point , create an ARRAY of points the represent an XOJO polygon array the would outline that area

#3 is where I really need to be

Detecting the edges of the flooded area is easy… however they are not in proper order to be used as a Polygon

So I need something that can “walk around” the edge and fill in such an array

For a point of reference… think of “Magic Wand” in Paint.Net (or similar programs)

I would second Kems boolean array suggestion. It should speed up the algorithm considerably as it avoids dealing with the same pixel more than once and would also solve any issues with overlapping seed and mask colours.

See topic on EDGE DETECTION… this solved my problem VERY FAST

In response to this post, I fooled around with this and found a pretty fast way to do it. It doesn’t product polygons, which is what you need, but it includes the concept of tolerance and locality (only selecting the colors that are contiguous with the selection coordinates).

It looks like you’ve solved the problem using an edge detection algorithm, though. Let me know if you would like further details on how my solution works - it only uses RGBSurface.Transform and RGBSurface.FloodFill.

Also in the interest of completeness, I sped up the original algorithm that Dave posted. It’s still not as fast as FloodFill, but I got it down by using a boolean map to avoid double-checking pixels and (more importantly) preallocating the stack so objects weren’t continuously being torn down. It’s the latter that sped it up from about 900 seconds (give or take) to about 1.5 seconds. A FloodFill does the same job in about 40 ms.

Here is my code, in case anyone else wants to see what they can do:

``````Const mask_color=&c00FF00

dim temp_rs as RGBSurface = p.RGBSurface
dim seed as Color = temp_rs.Pixel( x, y )

dim flood_stack() as Point
dim initFloodStackSize as integer = ( p.Height * p.Width ) \\ 8
if initFloodStackSize < 4 then initFloodStackSize = initFloodStackSize * 2
redim flood_stack( initFloodStackSize )
dim floodStackIndex as integer = 0

dim map( -1, -1 ) as boolean
redim map( p.Width - 1, p.Height - 1 )

Dim px As Color
flood_stack( floodStackIndex ) = new Point(x,y)

While floodStackIndex > -1
dim pt as Point = flood_stack( floodStackIndex )
floodStackIndex = floodStackIndex - 1

x = pt.x
y = pt.y
map( x, y ) = true

px=temp_rs.Pixel(x,y)
'If color_compare(px,seed) Then
if px = seed then

dim lowx as integer = x - 1
dim highx as integer = x + 1
dim lowy as integer = y - 1
dim highy as integer = y + 1

if lowx > -1 and not map( lowx, y ) then
floodStackIndex = floodStackIndex + 1
if flood_stack.Ubound < floodStackIndex then
redim flood_stack( flood_stack.Ubound * 2 )
end if
flood_stack( floodStackIndex ) = new Point( lowx, y )
end if
if highx < p.Width and not map( highx, y ) then
floodStackIndex = floodStackIndex + 1
if flood_stack.Ubound < floodStackIndex then
redim flood_stack( flood_stack.Ubound * 2 )
end if
flood_stack( floodStackIndex ) = new Point( highx, y )
end if
if lowy > -1 and not map( x, lowy ) then
floodStackIndex = floodStackIndex + 1
if flood_stack.Ubound < floodStackIndex then
redim flood_stack( flood_stack.Ubound * 2 )
end if
flood_stack( floodStackIndex ) = new Point( x, lowy )
end if
if highy < p.Height and not map( x, highy ) then
floodStackIndex = floodStackIndex + 1
if flood_stack.Ubound < floodStackIndex then
redim flood_stack( flood_stack.Ubound * 2 )
end if
flood_stack( floodStackIndex ) = new Point( x, highy )
end if

End If
Wend``````