CODEWITHSUNDEEP
javascriptalgorithmimage-processingcomputer-visionbounding-box
Tomáš Zato
Tomáš Zato

Reputation: 53226

Find geomethric center of object and rotate it to maximize bounding box height

This is a hard question and I've done some thinking without much success. My main goal is to rotate an arbitrary pixel object to minimize it's bounding box' width. (or to maximize the height, that should be the same assuming circumference is constant)

Because such goal is not in the scope of SO question, I have determined a simpler goal that will lead to the solution: Find a geometric center of the pixel object.

Why? Because if I have this center, I will able to find points furthest from it and then rotate the object so that those points are vertically aligned.

I originally thought this would be as simple as calculating the center of the bounding box. Quick test in Inkscape proved that wrong: center of bounding box is not rotation invariant:

enter image description here

So, how can I find the real geometric center to calculate object extremes and rotate it? Here are some illustrations of what I'm trying to achieve - mind that I'm working with PIXELS not vector data:

enter image description here

Upvotes: 2

Views: 1484

Answers (4)

Felix Goldberg
Felix Goldberg

Reputation: 421

cv2.minAreaRect might be just what you looking for. See here for an example of using it.

Upvotes: 1

Francesco Callari
Francesco Callari

Reputation: 11795

Ralf Kleberhoff's answer is almost right, but it needs a twist.

Algorithm:

  1. Compute the convex hull of your shape.
  2. Find the maximal diameter of the convex hull, i.e. the pair of convex hull vertices at the largest distance from each other, and the segment joining them.
  3. The center you want is the midpoint of the maximal diameter.
  4. The rotation about that center that brings the maximal diameter to the vertical is necessarily the one that yields the tallest (max height) bounding box. Note that this is not necessarily the configuration with the thinnest (min width) bounding box, as the two conditions are not equivalent.

Proof: The circle whose center is the midpoint of the maximal diameter of the convex hull is the circle with minimal area encompassing the entire object. By contradiction, if there existed a smaller circle, its diameter's length would be smaller than the maximal diameter, which implies that at least one of the extrema of the maximal diameter would be outside of such a circle.

Upvotes: 0

Ralf Kleberhoff
Ralf Kleberhoff

Reputation: 7290

For finding the bounding box with the smallest width, I suggest the following steps:

Step1: Replace the object by its convex hull, as they have the same bounding box, for all angles.

An observation regarding the box: Of the smallest-width box, either the left or the right vertical box line must be aligned with one line segment of the hull - otherwise, you'd get a smaller-width one by rotating a few degrees. So that limits the orientation to the convex hull's line segments.

Step2: For all these orientations, compute the minimum and the maximum rotated-x values for all points of the hull, giving the width.

Upvotes: 0

Spektre
Spektre

Reputation: 51863

Google how to compute center of mass but I would rather approach your main goal directly:

  1. compute OBB (Oriented Bounding Box)

    there are more approaches for this. Some are using PCA or Eigen Vectors for this I am doing this:

    Which can be applied on both vector and raster input.

  2. rotate so the OBB main axis will be aligned to vertical axis

    So you can compute the angle from OBB directly just use atan2 on the bigger OBB side vector. And rotate by 90-angle CCW (if your coordinate system is x+ goes to right, y+ goes up and angle is increasing from x+ axis in CCW direction).

Upvotes: 2

Related Questions