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
temp_rs.pixel(x,y)=mask_color
//
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
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 DisableBackgroundTasks
#pragma DisableBoundsChecking
#pragma DisableAutoWaitCursor
#pragma StackOverflowchecking False
#pragma NilObjectChecking False
#EndIf
Const mask_color1=&c010000
Const mask_color2=&c000001
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
temp_rs.pixel(xx,yy)=mask_color1
Else
temp_rs.Pixel(xx,yy)=mask_color2
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
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.
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.
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
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
I would second Kems 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.
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
temp_rs.pixel(x,y)=mask_color
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
