Find bounding rectangle of objects in monochrome bitmaps

Question

Given a monochrome bitmap:

000000000000000000000000000000000000000
001000100000000000000000000000000000000
000101000000000000000000000000000000000
000010000000001000000000000000000000000
000101000000010100000000000000000000000
001000100000100010000000000000000000000
000000000000010100000000000000000000000
000000000000001000000000000000000000000
000000000000000000000000000000000000000
000000000000001111110000000000000000000
000000000000001000010000000000000000000
000000000000001000010000000000000000000
000000000000001111110000000000000000000
000000000000000000000000000000000000000
000000000000000000000000000000000000000
000000000000000000000000000000000000000

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

Are there any established algorithms that I can use?

Answer 1

What you're looking for is called "Blob" detection, which detects groups of objects that stand out from their surrounding area. Depending on the complexity you need you can also track area, convexity, perimeter, bounding-box, etc. Blobs are used in lots of machine vision and inspection applications.

There are plenty of established algorithms on Wiki and the like.

There are also image processing libraries that you can look into, one that comes to mind is called AForge -- it's an open source library written in C#: aforge.net

Or else just search for "Blob detection" and you'll find tons of info on what you need.

Good luck!

Answer 2

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

Basically you need to label all the pixels according to what connected component they belong to, and then you can take the minimum and maximum X and Y coordinates for each one.

Answer 3

What I would do is to look at any labeling algorithm. One which is easy to implement is the "Run-Track" algorithm. Then when your labeling is done you could find the (top, left, right, bottom) extreme pixels of each labeled object. It might not be the fastest way (since you will be scannning the image multiple times), but it will be easy to implement.

Here are lecture slides that (shortly) describe the RT-algorithm (along with one other): http://www.cvl.isy.liu.se/Education/UnderGraduate/TSBB08/DBgrk7.pdf