Help needed with a very silly idea...

[Karlos]

Hi,

I'm looking for an algorithm that can look at a bitmap image and find bounding rectangles for any closed sets (eg a solid blob, of arbitary shape) of pixels that match a particular criteria, such as colour etc. I don't need to find the exact shape, just the bounding rectangle.

For example, suppose we had an image containing 3 non overlapping ovals of a particular colour we are interested in. The algorithm needs to return the 3 rectangles that contain the oval shapes.

I do have an algorithm already that needs to make a pair of line by line scans across the bitmap (first vertically, then horizontally, finally correlating the two scans) but it is a bit slow, even with the various early-out optimisations you can make to the line-scanning.

Any takers?

[FluffyMcDeath]

Why not take a 2D FFT and the corrolate that against a series of FFTs of every conceivable shape and then ...
Hmmmm.
Your way is probably faster and more possible in a finite amount of time.

[FluffyMcDeath]

Thinks a bit more...

Are these areas allowed to be "hollow" e.i. can they enclose a set of out of range pixels?

And how do you start looking? Do you start in the shape, as if you were doing a paint fill, or are you just looking for pixels that satisfy the criteria within the entire pixmap?
(So, could there be more than one match.)


And, if you scan one way, haven't you already scanned the other? Really?
Like if you walk the Ys and you know the x where you hit the good stuff and the x where you left.

And you could get faster if you took those start and ends and went straight down from there to the next Y
and if you are on the right side (for e.g.) and you go down and your pixel is in range, then go right further to find the edge, else go left.
For the other side, vice versa. If your left and right get to be the same, you've closed out the bottom.
Then from your starting Y go back up the same way to close your top.

[FluffyMcDeath]

re-reading, I see you've answered one of my questions.

Anyway, I don't think what I said would catch convex shapes coz you'd have to go back on yourself when they fold, but it's pretty close to a generic fill algo and there's a bunch of them around.
The amount of time it takes to finish depends upon the shape, but your method should be the same amount of time for anything.

[FluffyMcDeath]

By the way, I should thank you for helping me boost my post count which has been languishing of late.

[bloodline]

Karlos wrote:
Hi,

I'm looking for an algorithm that can look at a bitmap image and find bounding rectangles for any closed sets (eg a solid blob, of arbitary shape) of pixels that match a particular criteria, such as colour etc. I don't need to find the exact shape, just the bounding rectangle.

For example, suppose we had an image containing 3 non overlapping ovals of a particular colour we are interested in. The algorithm needs to return the 3 rectangles that contain the oval shapes.

I do have an algorithm already that needs to make a pair of line by line scans across the bitmap (first vertically, then horizontally, finally correlating the two scans) but it is a bit slow, even with the various early-out optimisations you can make to the line-scanning.

Any takers?

I had to make something similar when I was trying to make GUI in SDL.

I had to look for all the areas where the "windows" over lapped and then make sure those areas were not updated.

I had to do it Vertically and then Horizontally (For every window, starting at the one below the top most one) too, I thought it would be slow, but it's not... on any of my PC's... I wouldn't want to run it on my 68K's or even my PPC :-/

[Karlos]

Hi,

First of all, I should point out that this would be a pre-processing step, so it isn't critical speed wise. I just don't like slowness in general.

What is important is that the rectangles generated are as tight fitting as possible, as their content is used for a realtime application.

FluffyMcDeath wrote:
Thinks a bit more...

Are these areas allowed to be "hollow" e.i. can they enclose a set of out of range pixels?

It's not that complex. Consider the letter C - the algorithm would return the smallest rectangle that the complete letter fits into. A letter O of the same basic size would return the same rectangle.

The shapes are allowed to be hollow, just like the letter O in the above example. As long as the outer boundary is enclosed in the box, that is all that matters.

And how do you start looking? Do you start in the shape, as if you were doing a paint fill, or are you just looking for pixels that satisfy the criteria within the entire pixmap?
(So, could there be more than one match.)

What the existing algorithm does is to first scan down vertically a line at a time. It starts out witth the assumption that we haven't hit an area.

The moment we find a pixel along the current scanline that matches our criteria, the y coord is noted as a 'starting Y ordinate' (yMin), and the method of scanning now changes to look for the next scanline line that doesn't contain a pixel matching our requirements. When one of those is found, the y value is noted as a 'terminating Y ordinate' (yMax).

If we get to the end of the bitmap, it is always terminated as a yMax if we happen to be in an area of "the good stuff".

And so the scan proeeds. At the end, we have a set of yMin/yMax pairs.

We then do a horizontal scan in the same way to locate the corresponding xMin / xMax pairs.

We can correlate these to get a list of rectangles. It isn't perfect in that suppose we had two circles - one large and one small, with their y centres the same but at non-overlapping values of X.

The bounding rectangle for the larger one will be perfect, but the bounding rectangle for the smaller one will be as tall as the larger one. However, this is really a trifling inconvenience for what I have in mind.

And, if you scan one way, haven't you already scanned the other? Really?
Like if you walk the Ys and you know the x where you hit the good stuff and the x where you left.

This is what I was thinking, in a way.

And you could get faster if you took those start and ends and went straight down from there to the next Y
and if you are on the right side (for e.g.) and you go down and your pixel is in range, then go right further to find the edge, else go left.
For the other side, vice versa. If your left and right get to be the same, you've closed out the bottom.
Then from your starting Y go back up the same way to close your top.

Hmm. So you are saying we could basically floodfill the areas when we find them and keep track of the xMin/xMax and yMin/yMax during the fill. That might be a good solution.

[Karlos]

FluffyMcDeath wrote:
By the way, I should thank you for helping me boost my post count which has been languishing of late.

My pleasure :-D

[Karlos]

bloodline wrote:

I had to make something similar when I was trying to make GUI in SDL.

I had to look for all the areas where the "windows" over lapped and then make sure those areas were not updated.

I had to do it Vertically and then Horizontally (For every window, starting at the one below the top most one) too, I thought it would be slow, but it's not... on any of my PC's... I wouldn't want to run it on my 68K's or even my PPC :-/

You did this for rectangular windows? How come you never used a straightforward layered rectangle clipping approach for that? It would be orders of magnitude more efficient than scanning pixels.

My problem is that I'm dealing with irregular blobs so I have to do this.

[bloodline]

Karlos wrote:

bloodline wrote:

I had to make something similar when I was trying to make GUI in SDL.

I had to look for all the areas where the "windows" over lapped and then make sure those areas were not updated.

I had to do it Vertically and then Horizontally (For every window, starting at the one below the top most one) too, I thought it would be slow, but it's not... on any of my PC's... I wouldn't want to run it on my 68K's or even my PPC :-/

You did this for rectangular windows? How come you never used a straightforward layered rectangle clipping approach for that? It would be orders of magnitude more efficient than scanning pixels.

No, I didn't scan pixels :-), but I had two loops. one that divided the windows horisontally, and one that did it virtically, which at the end cuts the windows up into visible and invisible rectangles.

I was just saying that the separating out the H and the V is not a bad thing in my mind.

My problem is that I'm dealing with irregular blobs so I have to do this.

What about colour? do you always know what colour the background is going to be?

I'm wondering if you can't use some collision detection thingie... :-/

[Karlos]

The background colour is not really known.

All you really know, is that within the image, there will be irregular splodges that have a value within your target tolerance. All around them are pixels simply outside your tolerance. There are no areas of flat colour for the background.

[woof]

If your shape is in ONE piece then you can
For (say) a Screen 640x480
scan vertical lines separated by 80 pixels
(y=0 80 160 240 320 400)
if nothing hitted
continue with
(y=1 81 161 241 321 401)
etc...
When a line hitted say 241 then finish 319 -> 242
Idem in X
:-)

Alain
 

[minator]

@ Karlos

I don't see why you need to scan vertically, you should be able to get x and y values by scanning horizontally.

Also by scanning vertically you'll get a potentially massive speed hit as reading from RAM non-sequentially is very slow.



Assuming the index is in the top left:

Scan across, and when you hit the first correct pixel record xMin, xMax, yMin and yMax.

Scan the next line, if the pixel's x value is lower and it's touching the xMin you can record it as a new xMin, and increment yMax while there are other releant pixels touching you set a higher xMax.

--

That should work for solid areas but you'll need to implement something to track "previous pixels which were touching" if you want to capture non-solid objects.

That useful?

EDIT: I was suggesting an area fill for an alternative but this will not work on irregular shapes (i.e. an S).

[Karlos]

@Minator

When I said "scanning vertically" I meant scanning lines in the Y direction, rather than actually scanning reading down a column of 1-pixel. I guess that isnt very obvious :lol:

To be clear, I read successive scanlines (each one at am increasing y) first, to determine the yMin / yMax boundaries. This amounts to reading along a horizontal line until we first hit something. This is our first yMin.

The thing is, due to the irregularity of the shapes, you can't say "this is also your x-min" because it simply isn't possible to know - unless it occurs at x=0, that is. The next scanline might have a pixel of the same criteria some pixels to the left of the one on the previous line. You would need a quite sophisticated mechanism for tracking all the x values you uncovered in the previous scanline and working out which ones correspond to the equivalent x values on the current scanline.

By using 2 scans, we can concentrate on resolving only one set of extrema for each pass. The idea works but it's just trying to find a more optimal approach. As you say, it's scanning the successive vertical lines (each one at an increasing value of x) that takes a hit.

Of course, a single scan of the entire thing does uncover all the information but it is not easy to resolve it without using a memory of some kind. The two scan approach basically forgoes this.

[Jose]

@Karlos

Just another silly idea...
Could there be more than one object you're trying to identify in the same horizontal space? If not you could use some form of prediction about where the start of the object is based on the start of the previous line (after you detect the start of an horizontal line that is...).