Help needed with a very silly idea...

[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...).

[Karlos]

Hi Jose,

Yes. It's basically the case that there will be several such shapes in any given 2D area. The idea is to find the smallest bounding boxes around them, within a tolerance threshold.

The problem is still open ended, but I'm also looking into another solution which may be more useful, especially for awkward shapes.

[Karlos]

Here's an image to make the problem more visual:



The blue areas are outside our tolerance, the grey areas inside. The white rectangles are the areas I wish to find. Note from the diagram that:

A bounding rectangle may contain more than one 'blob', provided it properly fits the largest one.

A blob may be 'hollow' - I am only interested in the box around the outer extent.

[Jose]

Hey. Since the blobs can repeat themselves in a line I think all pixels have to be scanned. So the thing would be to opimize the detection routine. I know you more than know this, it's just that the program I'm doing has a similar routine;) Except that instead of trying to identify pixels that fall within a certain range it compares pixels of two successive images. I'll let y'all know what it does when I get a good, completed working version. I had a doubt that I think applies here too:
 When comparing two pixels and checking the difference is there a way to use LONGs instead of BYTES to access compare and infere about the diference of each color component between 2 pixels? That would probably acceleratte it by 3 times or so..
I want to use C for now to make it portable to AOS4 so no 68k assembler (just for now :-D ).

Sorry for hijacking the thread  :-D but I think this could be usefull for the code that makes the pixel comparisons used in your detection routine too, it's practically the same I think, except that you're using a range (two pixel comparisons probably for the higher and lower values ?).

[EDIT] I meant, in your case it could be two pixel comparsions(higher and lower range value checking) each for each color component.

[Karlos]

@Jose

Are your pixels arranged as 8-bit bytes? If your data reside in copyback memory, you will find that on 040+ bytewise comparison is not such a big issue. It is still slower but, not as bad as you might expect.

However, you can compare 2 sets of 4x8-bit pixels or 2 sets of 2x15/16-bit pixels using longwords.

If you exclusively or the two longwords together, you will highlight any bits that are different in each set of pixels. All the bits which are the same in both sets of pixels will be zero. Depending on what you intend to do with the data, I'm not sure if this will help you or not.

Oh - if you need to know which pixels are different, there are a couple of ways of working it out. Probably the easiest is to take the result of the 32-bit xor operation and mask it with four succesive 32-bit masks that each isolate a byte in the long word. Anything coming up as non zero is a difference.

[woof]

>I don't see why you need to scan vertically
All right i said vertically but you can scan first horizontally : but my idea was to not scan each line after
another (but skip N lines) so IF the shape is at the bottom (or right) of the screen you hit at first time only in several scan lines not by scanning all lines (or colonnes)

>Also by scanning vertically u arereading from RAM non->sequentially is very slow.
Absolutely right :-)

BTW with Altivec u can do massive compare of datas
some instructions on UBYTEs
vavgub         Average 16 UBYTE   
vcmpgtsb      Compare Greater-Than of 16 BYTE   
vmaxub         Maximum of 16 UBYTE   
vminub         Minimum of 16 UBYTE
etc...

Alain :-D

[Karlos]

@woof

That's interesting to know - pity I dont have altivec :-(

Well, not yet ;-)

As it goes, this doesn't help my immediate problem - which is better explained by the image than anything I can easily write :-)

Mind you, course all I am looking for is to speed up something that isn't really time critical (or at least not yet anyway - that might change).

[Kronos]

I cant say that I understood all in here, but that won't stop me from
adding my "mustard"

I would create 2 arrays of "struct blob" (minx,maxx,miny,maxy), both
big enough to hold the maximum amount of blobs I expect per line
(+safety offcoure, lets say struct blob even[20] and odd[20]).

I would now start with line 0, and eachtime I get a hit I fill in
the mins into one odd blob.
I'll then search for the end of the blob in
this line and and add the maxx. Maxy is set to the same as miny.

Then I do the same for line 1 filling in odd blobs.

Now I do check wether blobs in even are connected to blobs in odd, and
change the odd ones to include the even one.

Even blobs that have no partner are fully found and pushed into the
outbuffer.

And now I fill the even blobs with line 2 and so one.

Makes sure at every pixel is only looked at once, and I don't think
the blob-comparing adds much overhead.

[Karlos]

[Waccoon]

Here's something cool I found, though it's designed for "shrinkwrap" boundings and not boxes:

http://cgm.cs.mcgill.ca/~orm/rotcal.html

What language are you using?  I'm thinking about writing some code to allow for a flood filler that won't work if an object is open (spilling out to the edges of the screen).  It's for a paint program that lets multiple people use one canvas.

[minator]

@ Karlos

Out of interest, what is this for?

[Karlos]

@Waccoon

I'm using C. Well, I'm really using C++, but the code might be used in a related C project so it might as well be just C.

@Minator

I could tell you, but then I'd have to kill you :lol:

Nah, it isn't for anything important, it was just a small problem that cropped up in a recent project that I suddenly found interesting in it's own right.

Basically I am determining some bounding-box extents based on the opacity of an image for some processing I need to do. As it goes, contrary to what you might expect, I need the actual bounding box and not the pixel-exact 'mask' of the area.

That said, even if one does find the pixel exact mask, one can easily determine the bounding box, but I thought there might be a quicker way that takes advantage of not needing the exact mask...

[bloodline]

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

[Karlos]

bleh, you lazy, unoptimizing git :lol:

[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!!! ;-)

[Karlos]

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 worry that the arts of problem analysis, algorithm design and implementation efficiency are fast dying.