How to define bounding rectangles of several elements?

Question

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

• take something like this - a pre-processed binary image

• and produce something like this

Answer 1

Check the labeling of the connected components: http://en.wikipedia.org/wiki/Connected-component_labeling . In this case, you can either find the connected components of white pixels or black pixels (white is computationally simpler, since the image has fewer white dots).

Answer 2

Can I suggest a naive approach to start:

In the image, do a two-dimensional binary search for the midpoint of the image (x, y). From now on, fill the fill.

• if the borders of the filled shape do not match the image, then you have found a closed shape and, therefore, its bounding box.

• if it fills the whole image, then you haven’t done anything, so divide the image into four chimes and do the same recursively. (You do not need to check the points that fall inside the previously found shape chart, reducing the search space in the process).

Answer 3

For each item:

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 on the highest. I mean that closest to the top of the screen is not the biggest value.

Answer 4

It seems that OpenCV has some algorithms for finding the bounding box of an already implemented contour. Thus, learning how their function works can be a good start. http://opencv.itseez.com/doc/tutorials/imgproc/shapedescriptors/bounding_rects_circles/bounding_rects_circles.html

Answer 5

You can calculate the 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 called a simply connected k-tool, and the cluster is similar to voronoi diagrams:

"The single-channel k-clustering algorithm ... is exactly the Kruskal algorithm ... equivalent to finding MST and removing the k-1 most expensive edges."

See 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 on the highest. I mean that closest to the top of the screen is not the biggest value.