Find the bounding rectangle of objects in monochrome bitmaps

Question

For monochrome bitmap:

  0000000000000000000000000000000000000000000
 0010001000000000000000000000000000000000000
 0001010000000000000000000000000000000000000
 0000100000000010000000000000000000000000000
 000101000000010100000000000000000000000
 001000100000100010000000000000000000000
 0000000000000101000000000000000000000000000
 00000000000000100000000000000000000000000
 0000000000000000000000000000000000000000000
 000000000000001111110000000000000000000000
 000000000000001000010000000000000000000
 000000000000001000010000000000000000000
 000000000000001111110000000000000000000000
 0000000000000000000000000000000000000000000
 0000000000000000000000000000000000000000000
 0000000000000000000000000000000000000000000

I want to be able to find the bounding rectangle of each object in the bitmap.

Are there any established algorithms that I can use?

Answer 1

What you are looking for is called "Blob" detection, which detects groups of objects that stand out from their environment. Depending on the complexity that you need, you can also track area, bulge, perimeter, bounding box, etc. Blobs are used in many machine vision and control applications.

There are many installed algorithms in the Wiki, etc.

There are also image processing libraries that you can learn, and this suggests that AForge is an open source library written in C #: aforge.net

Or just search for "Blob Detection" and you will find a ton of information about what you need.

Good luck

Answer 2

If you have access to MATLAB, you can take a look at the source of the regionprops function. It does a lot of things, including finding bounding rectangles.

Basically, you need to mark all the pixels depending on which connected component they belong to, and then you can take the minimum and maximum X and Y coordinates for each of them.

Answer 3

What I would do is look at any labeling algorithm. One that is easy to implement is the Run-Track algorithm. Then, when your marking is done, you can find the extreme pixels (top, left, right, bottom) for each marked object. This may not be the fastest way (since you will scan the image several times), but it will be easy to implement.

Here are the lecture slides that (in brief) describe the RT algorithm (along with another): http://www.cvl.isy.liu.se/Education/UnderGraduate/TSBB08/DBgrk7.pdf