Help needed with a very silly idea...

[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 :-/

[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... :-/

[bloodline]

Ahhh... Karlos... just get a 4Ghz (or preferably an Athlon64 4000+) machine and brute force it, by scanning every pixel :-D

[bloodline]

Karlos wrote:
bleh, you lazy, unoptimizing git :lol:

:roflmao: Well what you are suggesting is like trying to dig a tunnel with spoon... use a spade man!!! ;-)

[bloodline]

Karlos wrote:
You know, it's an interesting in point.

I know a few people who write the most atrocious code imaginable, simply because they are spoiled by the performance of their hardware. People who should not be let anywhere near a compiler, for that matter. Their only skill is in the application of brute force to solve any problem. Then they use some convenience-oriented, high-level language/design tools with which to write their ill thought out code.

I would fit probably into that category. I loved the Amiga because I could program stuff in any sloppy way and get great results, much better than my Speccie/Amstrad/C64 friends :-D

I worry that the arts of problem analysis, algorithm design and implementation efficiency are a fast dying.

Well, I would suggest the shift is from a problem oriented view of program design to a solution one.
Err... We don't need to worry about the implementation of the problem, and instead worry more abotu the outcome of the solution... or something...

[bloodline]

Karlos wrote:

bloodline wrote:

Well, I would suggest the shift is from a problem oriented view of program design to a solution one.
Err... We don't need to worry about the implementation of the problem, and instead worry more abotu the outcome of the solution... or something...

Which is a completely bollox approach for this situation. And indeed most of the things I work on.

I guess I like the mental challenges of actually doing something well.

Yeah, well I suppose when it's a computer problem... hmmm. Anyay, there is a reason why DSPs have been developed... and that's for this type of task... so get yourself a DSP or more horsepower :-D