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]

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?

 

[sklett]

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.

 

[Ben Voigt [C++ MVP]]

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.

 

[sklett]

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

 

[Peter Duniho]

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]

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.


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.


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

 

[KWienhold]

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






- 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]]

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.

 

[sklett]

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

 

[sklett]

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