GDI+ - finding a rectangle inside another rectangle

[sklett]

I have a situation where I'm getting in Image that has a gray (solid, same
color) background with a smaller white rectangle inside. The position is
not always the same. What I need to do is locate the postion and determine
the size fo the white rectangle and then crop the image to leave only the
white rectangle remaining.

I'm very new to GDI+ and have really no idea where to start. Can anyone
suggest a good way to accomplish this?

Thanks for any help,
Steve

[Fabio]

"sklett" <[e-mail] scritto nel messaggio
news:u8****************@TK2MSFTNGP04.phx.gbl...

>I have a situation where I'm getting in Image that has a gray (solid, same
color) background with a smaller white rectangle inside. The position is
not always the same. What I need to do is locate the postion and determine
the size fo the white rectangle and then crop the image to leave only the
white rectangle remaining.

But you know the position of all the rectangles?

--
Help The New .Net Site! http://www.devbox4.net

[sklett]

"Fabio" <zn*******@virgilio.itwrote in message
news:uj**************@TK2MSFTNGP04.phx.gbl...

>
"sklett" <[e-mail] scritto nel messaggio
news:u8****************@TK2MSFTNGP04.phx.gbl...

>>I have a situation where I'm getting in Image that has a gray (solid, same
color) background with a smaller white rectangle inside. The position is
not always the same. What I need to do is locate the postion and
determine the size fo the white rectangle and then crop the image to leave
only the white rectangle remaining.

But you know the position of all the rectangles?

There is just one rectangle that I'm interested in and I do not know the
position.

If you picture a solid color windows desktop with a single window located
*somewhere* on the desktop, I want to find the location and dimension of the
window. I don't know if that odd example makes sense, I hope it does.

>
--
Help The New .Net Site! http://www.devbox4.net

[Ben Voigt [C++ MVP]]

"sklett" <[e-mail] in message
news:%2****************@TK2MSFTNGP04.phx.gbl...

>
"Fabio" <zn*******@virgilio.itwrote in message
news:uj**************@TK2MSFTNGP04.phx.gbl...

>>
"sklett" <[e-mail] scritto nel messaggio
news:u8****************@TK2MSFTNGP04.phx.gbl...

>>>I have a situation where I'm getting in Image that has a gray (solid,
same color) background with a smaller white rectangle inside. The
position is not always the same. What I need to do is locate the postion
and determine the size fo the white rectangle and then crop the image to
leave only the white rectangle remaining.

But you know the position of all the rectangles?

There is just one rectangle that I'm interested in and I do not know the
position.

If you picture a solid color windows desktop with a single window located
*somewhere* on the desktop, I want to find the location and dimension of
the window. I don't know if that odd example makes sense, I hope it does.

Divide and conquer... find the x-coordinate of the center of the screen.
Start at the top of the screen, iterating over the y-coordinate and
inspecting the color of each pixel. If you find any non-background pixels,
you'll have the top and bottom coordinates. Then average those two to get
the y-coordinate of the center of the window, and iterate across x. If the
entire center column was background, split the screen in two and test each
half. Repeat until you find the window.

>

>>
--
Help The New .Net Site! http://www.devbox4.net

[sklett]

"Ben Voigt [C++ MVP]" <rb*@nospam.nospamwrote in message
news:%2******************@TK2MSFTNGP03.phx.gbl...

>
"sklett" <[e-mail] in message
news:%2****************@TK2MSFTNGP04.phx.gbl...

>>
"Fabio" <zn*******@virgilio.itwrote in message
news:uj**************@TK2MSFTNGP04.phx.gbl...

>>>
"sklett" <[e-mail] scritto nel messaggio
news:u8****************@TK2MSFTNGP04.phx.gbl.. .

I have a situation where I'm getting in Image that has a gray (solid,
same color) background with a smaller white rectangle inside. The
position is not always the same. What I need to do is locate the
postion and determine the size fo the white rectangle and then crop the
image to leave only the white rectangle remaining.

But you know the position of all the rectangles?

There is just one rectangle that I'm interested in and I do not know the
position.

If you picture a solid color windows desktop with a single window located
*somewhere* on the desktop, I want to find the location and dimension of
the window. I don't know if that odd example makes sense, I hope it
does.

Divide and conquer... find the x-coordinate of the center of the screen.
Start at the top of the screen, iterating over the y-coordinate and
inspecting the color of each pixel. If you find any non-background
pixels, you'll have the top and bottom coordinates. Then average those
two to get the y-coordinate of the center of the window, and iterate
across x. If the entire center column was background, split the screen in
two and test each half. Repeat until you find the window.

Thanks for the reply Ben.

Your solution makes perfect sense, I need to research how to access the
pixels of an Image and I should be good to go. I know I've seen code before
that used unsafe code to work with pixels, but I think from yoru suggestion
I should need to do more than 2 passes.

Thanks again,
Steve

>

>>

>>>
--
Help The New .Net Site! http://www.devbox4.net

[Peter Duniho]

On Thu, 19 Jul 2007 16:51:06 -0700, sklett <[e-mail]:

Your solution makes perfect sense, I need to research how to access the
pixels of an Image and I should be good to go.

You can use Bitmap.GetPixel. It's slow, but it may be fast enough for
your purposes. You wouldn't want to use it if you needed to look at each
and every pixel, but in this case that shouldn't be necessary.

I know I've seen code before
that used unsafe code to work with pixels,

The fast way to work with Bitmap data is to use LockBits, which returns an
IntPtr. I'm not sure whether you need unsafe code to manipulate that or
not, since I haven't done that sort of thing in .NET yet.

but I think from yoru suggestion
I should need to do more than 2 passes.

I'm not sure what the second clause in the sentence has with the first.
That said...

"Divide and conquer" always implies multiple passes (or at least the
potential for multiple passes...when you're lucky, the algorithm requires
only a single pass :) ).

In this case, Ben is suggesting (I believe) that you "divide and conquer"
relative to finding the top and bottom of the rectangle. If the rectangle
you're looking for does not straddle the vertical line in the middle of
the containing rectangle, then you conceptually split the containing
rectangle into two halves on that vertical line, and run the search again.

Keep doing this until you find a vertical line that _does_ intersect the
rectangle you're looking for.

When you do find a vertical line that intersects the rectangle, then you
necessarily also have found the top and bottom Y coordinates of the
rectangle. Using those coordinates, select a horizontal line to scan (it
could be any line between the top and bottom, and Ben suggests simply
using the average of the top and bottom Y coordinates), which will in a
single pass across the containing rectangle tell you the left and right X
coordinates of the rectangle.

Note that the "divide and conquer" part of the algorithm should be done as
a breadth-first search. That is, rather than completely searching one
half, and then completely searching the other half, do the initial search
of the middle of each half first, and only if that fails to find the
rectangle would you do the "divide" part of the algorithm. The reason
being that if you do it depth-first, you have a 50/50 chance of having to
visit literally every pixel in the half that _doesn't_ contain the
rectangle, which is obviously counter to the whole point of doing the
search quickly. You might as well just start doing the vertical scans at
the left and work your way right.

I sure hope this isn't a homework assignment. I hate doing people's
homework for them. :)

Pete

[sklett]

"Peter Duniho" <Np*********@nnowslpianmk.comwrote in message
news:op***************@petes-computer.local...

On Thu, 19 Jul 2007 16:51:06 -0700, sklett <[e-mail]:

>Your solution makes perfect sense, I need to research how to access the
pixels of an Image and I should be good to go.

You can use Bitmap.GetPixel. It's slow, but it may be fast enough for
your purposes. You wouldn't want to use it if you needed to look at each
and every pixel, but in this case that shouldn't be necessary.

>I know I've seen code before
that used unsafe code to work with pixels,

The fast way to work with Bitmap data is to use LockBits, which returns an
IntPtr. I'm not sure whether you need unsafe code to manipulate that or
not, since I haven't done that sort of thing in .NET yet.

>but I think from yoru suggestion
I should need to do more than 2 passes.

I'm not sure what the second clause in the sentence has with the first.
That said...

"Divide and conquer" always implies multiple passes (or at least the
potential for multiple passes...when you're lucky, the algorithm requires
only a single pass :) ).

In this case, Ben is suggesting (I believe) that you "divide and conquer"
relative to finding the top and bottom of the rectangle. If the rectangle
you're looking for does not straddle the vertical line in the middle of
the containing rectangle, then you conceptually split the containing
rectangle into two halves on that vertical line, and run the search again.

Keep doing this until you find a vertical line that _does_ intersect the
rectangle you're looking for.

When you do find a vertical line that intersects the rectangle, then you
necessarily also have found the top and bottom Y coordinates of the
rectangle. Using those coordinates, select a horizontal line to scan (it
could be any line between the top and bottom, and Ben suggests simply
using the average of the top and bottom Y coordinates), which will in a
single pass across the containing rectangle tell you the left and right X
coordinates of the rectangle.

Note that the "divide and conquer" part of the algorithm should be done as
a breadth-first search. That is, rather than completely searching one
half, and then completely searching the other half, do the initial search
of the middle of each half first, and only if that fails to find the
rectangle would you do the "divide" part of the algorithm. The reason
being that if you do it depth-first, you have a 50/50 chance of having to
visit literally every pixel in the half that _doesn't_ contain the
rectangle, which is obviously counter to the whole point of doing the
search quickly. You might as well just start doing the vertical scans at
the left and work your way right.

I sure hope this isn't a homework assignment. I hate doing people's
homework for them. :)

Hi Peter,

Thanks for the great detailed post, I'm very clear on it now.
I assure this is not homework, those days are long, long gone.

I will post my code I end up using in case anyone else you like to see it.

Thanks again,
Steve

>
Pete

[KWienhold]

On 20 Jul., 03:44, "sklett" <[e-mail]:

"Peter Duniho" <[e-mail] in message

news:op***************@petes-computer.local...

On Thu, 19 Jul 2007 16:51:06 -0700, sklett <[e-mail]:

Your solution makes perfect sense, I need to research how to access the
pixels of an Image and I should be good to go.

You can use Bitmap.GetPixel. It's slow, but it may be fast enough for
your purposes. You wouldn't want to use it if you needed to look at each
and every pixel, but in this case that shouldn't be necessary.

I know I've seen code before
that used unsafe code to work with pixels,

The fast way to work with Bitmap data is to use LockBits, which returns an
IntPtr. I'm not sure whether you need unsafe code to manipulate that or
not, since I haven't done that sort of thing in .NET yet.

but I think from yoru suggestion
I should need to do more than 2 passes.

I'm not sure what the second clause in the sentence has with the first.
That said...

"Divide and conquer" always implies multiple passes (or at least the
potential for multiple passes...when you're lucky, the algorithm requires
only a single pass :) ).

In this case, Ben is suggesting (I believe) that you "divide and conquer"
relative to finding the top and bottom of the rectangle. If the rectangle
you're looking for does not straddle the vertical line in the middle of
the containing rectangle, then you conceptually split the containing
rectangle into two halves on that vertical line, and run the search again.

Keep doing this until you find a vertical line that _does_ intersect the
rectangle you're looking for.

When you do find a vertical line that intersects the rectangle, then you
necessarily also have found the top and bottom Y coordinates of the
rectangle. Using those coordinates, select a horizontal line to scan (it
could be any line between the top and bottom, and Ben suggests simply
using the average of the top and bottom Y coordinates), which will in a
single pass across the containing rectangle tell you the left and right X
coordinates of the rectangle.

Note that the "divide and conquer" part of the algorithm should be done as
a breadth-first search. That is, rather than completely searching one
half, and then completely searching the other half, do the initial search
of the middle of each half first, and only if that fails to find the
rectangle would you do the "divide" part of the algorithm. The reason
being that if you do it depth-first, you have a 50/50 chance of having to
visit literally every pixel in the half that _doesn't_ contain the
rectangle, which is obviously counter to the whole point of doing the
search quickly. You might as well just start doing the vertical scans at
the left and work your way right.

I sure hope this isn't a homework assignment. I hate doing people's
homework for them. :)

Hi Peter,

Thanks for the great detailed post, I'm very clear on it now.
I assure this is not homework, those days are long, long gone.

I will post my code I end up using in case anyone else you like to see it.

Thanks again,
Steve

Pete- Zitierten Text ausblenden -

- Zitierten Text anzeigen -- Zitierten Text ausblenden -

- Zitierten Text anzeigen -

Just in case you do decide to work with LockBits for performance
reasons, I found that this is a good place to start:
http://www.bobpowell.net/lockingbits.htm

hth,
Kevin Wienhold

[Ben Voigt [C++ MVP]]

"sklett" <[e-mail] in message
news:e7**************@TK2MSFTNGP03.phx.gbl...

>
"Ben Voigt [C++ MVP]" <rb*@nospam.nospamwrote in message
news:%2******************@TK2MSFTNGP03.phx.gbl...

>>
"sklett" <[e-mail] in message
news:%2****************@TK2MSFTNGP04.phx.gbl...

>>>
"Fabio" <zn*******@virgilio.itwrote in message
news:uj**************@TK2MSFTNGP04.phx.gbl...

"sklett" <[e-mail] scritto nel messaggio
news:u8****************@TK2MSFTNGP04.phx.gbl. ..

>I have a situation where I'm getting in Image that has a gray (solid,
>same color) background with a smaller white rectangle inside. The
>position is not always the same. What I need to do is locate the
>postion and determine the size fo the white rectangle and then crop the
>image to leave only the white rectangle remaining.

But you know the position of all the rectangles?

There is just one rectangle that I'm interested in and I do not know the
position.

If you picture a solid color windows desktop with a single window
located *somewhere* on the desktop, I want to find the location and
dimension of the window. I don't know if that odd example makes sense,
I hope it does.

Divide and conquer... find the x-coordinate of the center of the screen.
Start at the top of the screen, iterating over the y-coordinate and
inspecting the color of each pixel. If you find any non-background
pixels, you'll have the top and bottom coordinates. Then average those
two to get the y-coordinate of the center of the window, and iterate
across x. If the entire center column was background, split the screen
in two and test each half. Repeat until you find the window.

One very effective way to do this is to maintain a queue (i.e. LinkedList)
of Rectangles. Start with the whole image. Each time you bisect the image
without hitting the target, add both halves to the queue. Loop on the
queue. Then you can implement one additional optimization -- bisect each
rectangle along the shorter dimension, keeping the resulting halves at less
than a 2:1 aspect ratio.

>
Thanks for the reply Ben.

Your solution makes perfect sense, I need to research how to access the
pixels of an Image and I should be good to go. I know I've seen code
before that used unsafe code to work with pixels, but I think from yoru
suggestion I should need to do more than 2 passes.

Thanks again,
Steve

>>

>>>
--
Help The New .Net Site! http://www.devbox4.net

[sklett]

"Ben Voigt [C++ MVP]" <rb*@nospam.nospamwrote in message
news:%2****************@TK2MSFTNGP03.phx.gbl...

>
"sklett" <[e-mail] in message
news:e7**************@TK2MSFTNGP03.phx.gbl...

>>
"Ben Voigt [C++ MVP]" <rb*@nospam.nospamwrote in message
news:%2******************@TK2MSFTNGP03.phx.gbl. ..

>>>
"sklett" <[e-mail] in message
news:%2****************@TK2MSFTNGP04.phx.gbl.. .

"Fabio" <zn*******@virgilio.itwrote in message
news:uj**************@TK2MSFTNGP04.phx.gbl...
>
"sklett" <[e-mail] scritto nel messaggio
news:u8****************@TK2MSFTNGP04.phx.gbl.. .
>
>>I have a situation where I'm getting in Image that has a gray (solid,
>>same color) background with a smaller white rectangle inside. The
>>position is not always the same. What I need to do is locate the
>>postion and determine the size fo the white rectangle and then crop
>>the image to leave only the white rectangle remaining.
>
But you know the position of all the rectangles?

There is just one rectangle that I'm interested in and I do not know
the position.

If you picture a solid color windows desktop with a single window
located *somewhere* on the desktop, I want to find the location and
dimension of the window. I don't know if that odd example makes sense,
I hope it does.

Divide and conquer... find the x-coordinate of the center of the screen.
Start at the top of the screen, iterating over the y-coordinate and
inspecting the color of each pixel. If you find any non-background
pixels, you'll have the top and bottom coordinates. Then average those
two to get the y-coordinate of the center of the window, and iterate
across x. If the entire center column was background, split the screen
in two and test each half. Repeat until you find the window.

One very effective way to do this is to maintain a queue (i.e. LinkedList)
of Rectangles. Start with the whole image. Each time you bisect the
image without hitting the target, add both halves to the queue. Loop on
the queue. Then you can implement one additional optimization -- bisect
each rectangle along the shorter dimension, keeping the resulting halves
at less than a 2:1 aspect ratio.

Yes, that is a good suggestion and I have already implemented my solution
that way, nice to know it's a sound decision! :)
Have a good weekend,
Steve

>

>>
Thanks for the reply Ben.

Your solution makes perfect sense, I need to research how to access the
pixels of an Image and I should be good to go. I know I've seen code
before that used unsafe code to work with pixels, but I think from yoru
suggestion I should need to do more than 2 passes.

Thanks again,
Steve

>>>
>
--
Help The New .Net Site! http://www.devbox4.net
>

[sklett]

"KWienhold" <he******@trashmail.netwrote in message
news:11**********************@57g2000hsv.googlegro ups.com...

On 20 Jul., 03:44, "sklett" <[e-mail]:

>"Peter Duniho" <[e-mail] in message

news:op***************@petes-computer.local...

On Thu, 19 Jul 2007 16:51:06 -0700, sklett <[e-mail]:

>Your solution makes perfect sense, I need to research how to access
the
pixels of an Image and I should be good to go.

You can use Bitmap.GetPixel. It's slow, but it may be fast enough for
your purposes. You wouldn't want to use it if you needed to look at
each
and every pixel, but in this case that shouldn't be necessary.

>I know I've seen code before
that used unsafe code to work with pixels,

The fast way to work with Bitmap data is to use LockBits, which returns
an
IntPtr. I'm not sure whether you need unsafe code to manipulate that
or
not, since I haven't done that sort of thing in .NET yet.

>but I think from yoru suggestion
I should need to do more than 2 passes.

I'm not sure what the second clause in the sentence has with the first.
That said...

"Divide and conquer" always implies multiple passes (or at least the
potential for multiple passes...when you're lucky, the algorithm
requires
only a single pass :) ).

In this case, Ben is suggesting (I believe) that you "divide and
conquer"
relative to finding the top and bottom of the rectangle. If the
rectangle
you're looking for does not straddle the vertical line in the middle of
the containing rectangle, then you conceptually split the containing
rectangle into two halves on that vertical line, and run the search
again.

Keep doing this until you find a vertical line that _does_ intersect
the
rectangle you're looking for.

When you do find a vertical line that intersects the rectangle, then
you
necessarily also have found the top and bottom Y coordinates of the
rectangle. Using those coordinates, select a horizontal line to scan
(it
could be any line between the top and bottom, and Ben suggests simply
using the average of the top and bottom Y coordinates), which will in a
single pass across the containing rectangle tell you the left and right
X
coordinates of the rectangle.

Note that the "divide and conquer" part of the algorithm should be done
as
a breadth-first search. That is, rather than completely searching one
half, and then completely searching the other half, do the initial
search
of the middle of each half first, and only if that fails to find the
rectangle would you do the "divide" part of the algorithm. The reason
being that if you do it depth-first, you have a 50/50 chance of having
to
visit literally every pixel in the half that _doesn't_ contain the
rectangle, which is obviously counter to the whole point of doing the
search quickly. You might as well just start doing the vertical scans
at
the left and work your way right.

I sure hope this isn't a homework assignment. I hate doing people's
homework for them. :)

Hi Peter,

Thanks for the great detailed post, I'm very clear on it now.
I assure this is not homework, those days are long, long gone.

I will post my code I end up using in case anyone else you like to see
it.

Thanks again,
Steve

Pete- Zitierten Text ausblenden -

- Zitierten Text anzeigen -- Zitierten Text ausblenden -

- Zitierten Text anzeigen -

Just in case you do decide to work with LockBits for performance
reasons, I found that this is a good place to start:
http://www.bobpowell.net/lockingbits.htm

Thanks Kevin, looks like a very good article, in fact looks like there is
lots of good stuff on this site!
Have a good one,
Steve

hth,
Kevin Wienhold