How to determine bounding rectangles of multiple elements?

Question

I would like to implement an algorithm which will find the bounding rectangles of contours (already determined by another algorithm). The only thing I have is a binarized image (as shown below). The basic idea would be to :

• take something like this - a preprocessed binarized image

• and produce something like this

Answer 1

Check out connected component labeling: http://en.wikipedia.org/wiki/Connected-component_labeling . You can either find connected components of white pixels or black pixels in this case (White is computationally easier since you have fewer white points in the image).

Answer 2

May I suggest a naive approach for a start:

In the image, do a 2D binary search for a middle point in the image (x,y). From that point, perform a flood fill.

• if the bounds of the filled figure are not those of the image, then you found a closed figure, and therefore its bounding box.

• if it fills the whole image, then you hitted nothing, so divide the image in four cuadrants and do the same recursively. (You don't need to check for points that fall inside a previously found bounding box figure, cutting your search space in the process).

Answer 3

For each element:

They highest y - 1 is the top of the rectangle. 
The leftmost x - 1 is the left of the rectangle. 
The lowest y + 1 is the bottom of the rectangle. 
The rightmost x + 1 is the right of the rectangle.

Note by highest I mean closest to the top of the screen not the greatest value.

Answer 4

It looks like OpenCV has some algorithms for finding the bounding box of a contour already implemented. So looking into how their function works might be a good way to start. http://opencv.itseez.com/doc/tutorials/imgproc/shapedescriptors/bounding_rects_circles/bounding_rects_circles.html

Answer 5

You can calculate a minimum spanning tree and remove the longest edges. Then you can calculate the k-means. Remove another long edge and calculate the k-means. Rinse and repeat until you have N=10. I believe this algorithm is named single-link k-means and the cluster are similar to voronoi diagrams:

"The single-link k-clustering algorithm ... is precisely Kruskal's algorithm ... equivalent to finding an MST and deleting the k-1 most expensive edges."

See for example here: https://stats.stackexchange.com/questions/1475/visualization-software-for-clustering

Then for each cluster you apply this rule:

They highest y - 1 is the top of the rectangle. 
The leftmost x - 1 is the left of the rectangle. 
The lowest y + 1 is the bottom of the rectangle. 
The rightmost x + 1 is the right of the rectangle.

Note by highest I mean closest to the top of the screen not the greatest value.