CODEWITHSUNDEEP
algorithmgraphicsgeometrybounding-box
Patryk
Patryk

Reputation: 24140

How to determine bounding rectangles of multiple elements?

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 :

Upvotes: 5

Views: 2468

Answers (5)

ElKamina
ElKamina

Reputation: 7817

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).

Upvotes: 5

Cybercartel
Cybercartel

Reputation: 12592

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.

Upvotes: -1

aoi222
aoi222

Reputation: 733

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

Upvotes: 0

Steve Wellens
Steve Wellens

Reputation: 20638

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.

Upvotes: -1

Gabriel Belingueres
Gabriel Belingueres

Reputation: 2985

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).

Upvotes: 1

Related Questions