Board index » cppbuilder » Perimeter of a given shape of a given color in a bitmap

Perimeter of a given shape of a given color in a bitmap

I need to get the Rect of a square or rectangle in a bitmap which is of
a specific color. Say for simplicity's sake, I have a TImage which has a
white background on it is a red square of some unknown size. I need to
get the topleft and bottom right coords for this. Any insight on a good
approach anyone?
 

Re:Perimeter of a given shape of a given color in a bitmap


David Mc Dermid <dmcder...@sprintmail.com> spake the secret code
<370975D7.230E3...@sprintmail.com> thusly:

Quote
>I need to get the Rect of a square or rectangle in a bitmap which is of
>a specific color. Say for simplicity's sake, I have a TImage which has a
>white background on it is a red square of some unknown size. I need to
>get the topleft and bottom right coords for this. Any insight on a good
>approach anyone?

Without extra knowledge of how the rectangle was drawn, you're going to
have to scan the pixels in the image, no matter what you do.

If you know where the rectangle comes from, you could record its
extent when you draw it and then fetch it back out later.

If you don't draw the rectangle yourself, or you can't insert
instrumentation code (i.e. third party library) to get the coordinates
of the rectangle, then scanning the pixels is the only way to go.  If
you are certain that the TImage contains a rectangle or square, and
not some odd shape with holes or something like that, then scan the
upper left corner of the image for the upper left corner of the
rectangle, then scan the bottom right corner of the TImage for the
bottomr right corner of the rectangle and compute the extent from what
you find.
--
http://www.xmission.com/~legalize Legalize {*word*62}hood!
legal...@xmission.com
``Ain't it funny that they all fire the pistol,     <URL: http://
  at the wrong end of the race?''--PDBT     www.eden.com/~thewho>

Re:Perimeter of a given shape of a given color in a bitmap


David,
        A very simple approach would be to do a serial scan through the image,
pixel-by-pixel, testing to see if the pixel is red.  Once a red is
found, you have the top left corner, at which point you set a flag to
test for white.  Once a white is found subtract one from the x and y
loop values, and you have the bottom left corner.  Obviously, that
appraoch is very expensive.  A better appraoch would be to start
scanning from the top-left corner, pixel-by-pixel until a red is found,
at which point you have the top-left corner.  Then, start scanning up
from the bottom-right corner of the image, to yield the bottom-right
corner...

//start scanning from top-left corner
for (int x = 0; x < Image1->Width; x++)
    for (int y = 0; y < Image1->Height; y++)
        if (Image1->Canvas->Pixels[x][y] == clRed)
        {
                int Left = x;
                int Top = y;

                //terminate loops
                x = Image1->Width;
                y = Image1->Height;
        }

    //start scanning from bottom-right corner
for (int x = Image1->Width; x > 0; x--)
    for (int y = Image1->Height; y > 0; y--)
        if (Image1->Canvas->Pixels[x][y] == clRed)
        {
                int Right = x;
                int Bottom = y;

                //terminate loops
                x = 0;
                y = 0;
        }

This method is may be faster than the first approach, depending on the
location of the rectangle in the image.  A "smarter" approach would be
to do a "segmented" scan.  That is, scan say every 10 lines for the
first occurence of a red pixel, at which point you'd back up 10 pixels
and start scanning one by one until a red is found, to get the top-left
corner.  Then do the same starting at the bottom-right corner, scannning
every 10 pixels until a red is found, shift back down 10 pixels, then
scan one by one until you get the bottom-right coordinates...

    int NextStartX, NextStartY;

    //start scanning from top-left corner inc 10
    for (int x = 0; x < Image1->Width; x = x + 10)
        for (int y = 0; y < Image1->Height; y = y + 10)
            if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                //shift back 10 and start next scans from there
                NextStartX = x - 10;
                NextStartY = y - 10;

                //terminate loops
                x = Image1->Width;
                y = Image1->Height;
            }

    //start scanning from previously found values
    for (int x = NextStartX; x < Image1->Width; x++)
        for (int y = NextStartY; y < Image1->Height; y++)
            if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                int Left = x;
                int Top = y;

                //terminate loops
                x = Image1->Width;
                y = Image1->Height;
            }

   //start scanning from bottom-right corner inc 10
    for (int x = Image1->Width; x > 0; x = x - 10)
        for (int y = Image1->Height; y > 0; y = y - 10)
            if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                //shift back 10 and start next scans from there
                NextStartX = x + 10;
                NextStartY = y + 10;

                //terminate loops
                x = 0;
                y = 0;
            }

    //start scanning from values previously found values
    for (int x = NextStartX; x > 0; x--)
        for (int y = NextStartY; y > 0; y--)
            if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                int Right = x;
                int Bottom = y;

                //terminate loops
                x = 0;
                y = 0;
            }

Extending that idea, you could set the scan increment value even higher,
and progressively decay down...

    int NextStartX, NextStartY;

    //start scanning from top-left corner inc 50
    for (int x = 0; x < Image1->Width; x = x + 50)
        for (int y = 0; y < Image1->Height; y = y + 50)
                if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                //shift back 10 and start next scans from there
                NextStartX = x - 50;
                NextStartY = y - 50;

                //terminate loops
                x = Image1->Width;
                y = Image1->Height;
            }

    //start scanning from values previously found values inc 10
    for (int x = NextStartX; x < Image1->Width; x = x + 10)
        for (int y = NextStartY; y < Image1->Height; y = y + 10)
                if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                //shift back 10 and start next scans from there
                NextStartX = x - 10;
                NextStartY = y - 10;

                //terminate loops
                x = Image1->Width;
                y = Image1->Height;
            }

    //start scanning from previously found values
    for (int x = NextStartX; x < Image1->Width; x++)
        for (int y = NextStartY; y < Image1->Height; y++)
                if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                int Left = x;
                Memo1->Lines->Add(Left);
                int Top = y;
                Memo1->Lines->Add(Top);

                //terminate loops
                x = Image1->Width;
                y = Image1->Height;
            }

    //start scanning from bottom-right corner inc 50
    for (int x = Image1->Width; x > 0; x = x - 50)
        for (int y = Image1->Height; y > 0; y = y - 50)
                if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                //shift back 10 and start next scans from there
                NextStartX = x + 50;
                NextStartY = y + 50;

                //terminate loops
                x = 0;
                y = 0;
            }

    //start scanning from values previously found values inc 10
    for (int x = NextStartX; x > 0; x = x - 10)
        for (int y = NextStartY; y > 0; y = y - 10)
            if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                //shift back 10 and start next scans from there
                NextStartX = x + 10;
                NextStartY = y + 10;

                //terminate loops
                x = 0;
                y = 0;
            }

    //start scanning from values previously found values
    for (int x = NextStartX; x > 0; x--)
        for (int y = NextStartY; y > 0; y--)
            if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                int Right = x;
                Memo1->Lines->Add(Right);
                int Bottom = y;
                Memo1->Lines->Add(Bottom);

                //terminate loops
                x = 0;
                y = 0;
            }

This leads to an strategically decaying scanning increment where the
increment approaches one (kind of like the limit as x,y --> 1).  I
demonstrate this idea in the following three functions.  Drop a TMemo on
your form, and see how fast this method is (nearly instantaneous for a
768x768 image, small red rectangle in center, on a 166Mhz machine!)

TPoint __fastcall TForm1::FindTopLeft(int NextStartX, int NextStartY,
int inc)
{
    TPoint TopLeft;
    //start scanning from previously found values
    for (int x = NextStartX; x < Image1->Width; x = x + inc)
        for (int y = NextStartY; y < Image1->Height; y = y + inc)
            if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                TopLeft.x = x - inc;
                TopLeft.y = y - inc;

                return TopLeft;
            }

Quote
}

TPoint __fastcall TForm1::FindBottomRight(int NextStartX, int
NextStartY, int inc)
{
    TPoint BottomRight;
    //start scanning from values previously found values
    for (int x = NextStartX; x > 0; x = x - inc)
        for (int y = NextStartY; y > 0; y = y - inc)
            if (Image1->Canvas->Pixels[x][y] == clRed)
            {
                BottomRight.x = x + inc;
                BottomRight.y = y + inc;

                return BottomRight;
            }

Quote
}

void __fastcall TForm1::Button3Click(TObject *Sender)
{
   TPoint CurrentTopLeft, CurrentBottomRight;

    CurrentTopLeft.x = 0;
    CurrentTopLeft.y = 0;
    CurrentBottomRight.x = 0;
    CurrentBottomRight.y = 0;

    for (int inc = 100; inc >= 1; inc = inc - 10)
    {
        CurrentTopLeft = FindTopLeft(CurrentTopLeft.x, CurrentTopLeft.y,
inc);
        CurrentBottomRight = FindBottomRight(CurrentBottomRight.x,
CurrentBottomRight.y, inc);
    }

    Memo1->Lines->Add((int)CurrentTopLeft.x);
    Memo1->Lines->Add((int)CurrentTopLeft.y);
    Memo1->Lines->Add((int)CurrentBottomRight.x);
    Memo1->Lines->Add((int)CurrentBottomRight.y);

Quote
}

In addition, there are even some methods that are based on probablility
models if you are not completely concerned with accuracy.  Hope this
give you some new ideas.

//Damon

-------------------------------------
http://bcbcaq.freeservers.com
Answers to <Commonly Asked Questions>

Re:Perimeter of a given shape of a given color in a bitmap


In the last function, the line...

Quote
>     for (int inc = 100; inc >= 1; inc = inc - 10)

Should be changed to...

  for (int inc = 101; inc >= 1; inc = inc - 10)

so that the algorithm will converge on a correct answer.

//Damon

-------------------------------------
http://bcbcaq.freeservers.com
Answers to <Commonly Asked Questions>

Re:Perimeter of a given shape of a given color in a bitmap


Quote
Damon Chandler wrote:
> David,
>         A very simple approach would be to do a serial scan through the image,

and lots more...

Wow, what an incredibly through response. Many thanks. I only wish I had been more
concise in my question. Damon, what I am attempting to do is to capture a given
area of a certain color when it is picked. To be more precise, when a TImage is
clicked I check the pixel color and see if it matches a given color set. If so I
wish to grab the rectangular area filled with the given color. I am currently
doing this by, as you put it, scanning around to find the edges by first
decrementing the y coord. to get the top then incrementing to get bottom and same
for sides. This works fine but as you say is expensive. I need to look more
closely at your ideas before I comment farther, but I am guessing from what I read
so far I will be able to improve performance utilizing some of your tactics, maybe
something like a binary search could be used (ie go up 2 if still same color go 4
if still same 8 then 16 if not go 12 if is go 14 ...).

Now I have the next hurdle to overcome. I need to handle an instance when a given
rectangle intersects another rectangle of the same color.Obviously the previous
scheme is invalid if say the x dimensions are identical. This is something I can
live with. I need to handle when they lay in a different coord. set that
intersects though. In this occurance, I need to 'get' just the first 'picked'
item. I have tried a few ideas with mixed results. Have you ever accomplished
something of this nature?

Last obstical I currently have no handle on at all ( I wanted to tackle the easy
stuff first, chicken I guess). I need to account for an instance where the shape
is other then a simple square or rectangle ie triangle, polygon, or yuk circle
(slow math performance I fear). Do you know of any algos that are well suited for
this type of work?

Thanks again for all your insight. I will retain all the more hair because of it!

Re:Perimeter of a given shape of a given color in a bitmap


Quote
> I am guessing from what I read
> so far I will be able to improve performance utilizing some of your tactics, maybe
> something like a binary search could be used (ie go up 2 if still same color go 4
> if still same 8 then 16 if not go 12 if is go 14 ...).

David,
        Yes, except that in this case, we're converging down since testing more
pixels is more expensive.  Think of it as a grid getting finer and
finer.  The more grid points you need to test, the more time ti will
take.  Another thing to note is that you shouldn't make the grid too
sparse, or you might completely miss smaller rectangles.

Quote
> Now I have the next hurdle to overcome. I need to handle an instance when a given
> rectangle intersects another rectangle of the same color.Obviously the previous
> scheme is invalid if say the x dimensions are identical. This is something I can
> live with. I need to handle when they lay in a different coord. set that
> intersects though. In this occurance, I need to 'get' just the first 'picked'
> item. I have tried a few ideas with mixed results. Have you ever accomplished
> something of this nature?

Say your shape is like this...

(A)************
   *          *
   *          *
   *****      ********
       *             *
       *     X       *
       *             *
       ***************(B)

with the object selected by the "X."  You want to be able to extract
just the lower rectangle?  If that's the case, the the algorithm will
find points "A" and "B."  From these you can implicitly find "C" and
"D"...

(A)************       (D)
   *          *
   *          *
   *****      ********
       *             *
       *     X       *
       *             *
(C)    ***************(B)

In this case, I'd start scanning down from "D" to find the Top of the
desired rectangle, and scan right from "C" to find the Left of the
desired rectangle. Of course, there are more configurations to test, but
the idea is the same.  All of this and solutions to locating non
rectangular objects are covered in a technique called "ray tracing."  It
is the basis for reflections and shadows that you see in advanced
rendered scenes.  I'd suggest finding a good text on that subject, as I
personally hate doing retracing!  You also might want to check out
Earl's graphics page...

http://www.efg2.com/lab/library/delphi/graphics/algorithms.htm

It's loaded with links to graphics related sites and code.

Good luck.

//Damon

-------------------------------------
http://bcbcaq.freeservers.com
Answers to <Commonly Asked Questions>

Re:Perimeter of a given shape of a given color in a bitmap


In article <370D7F31.87834...@sprintmail.com>,
 David Mc Dermid <dmcder...@sprintmail.com> writes:
|>
|>    ( to full paragraphs removed)

|> Last obstical I currently have no handle on at all ( I wanted to tackle the easy
|> stuff first, chicken I guess). I need to account for an instance where the shape
|> is other then a simple square or rectangle ie triangle, polygon, or yuk circle
|> (slow math performance I fear). Do you know of any algos that are well suited for
|> this type of work?
|>
|> Thanks again for all your insight. I will retain all the more hair because of it!

David,

I am afraid this can't be done by simply analyzing a bitmap.

If I understood you right, your rectangles, triangles etc. have the
same outline color and fill color.

If so, it is not possible to distinguish two partially overlapping
rectangles (e.g.) and an identically looking polygon.

I think your best bet is to keep track of all shapes being drawn.

Good luck

Kjell

kamfj...@hotmail.com

Other Threads