2

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

Tomáš Zato
  • 50,171
  • 52
  • 268
  • 778
  • Minimizing the bounding box'es width isn't the same as maximizing its height. E.g. your "BAD rectangle" example is close to maximum height (it were exactly if the upper and lower corner were vertically aligned), but surely doesn't have the minimum width. – Ralf Kleberhoff Dec 16 '17 at 14:23
  • @RalfKleberhoff Well, all that thinking and I still got it all wrong... :) – Tomáš Zato Dec 16 '17 at 14:57
  • 1
    May be if you describe the real problem you have you will get a solution for it. Minimization of b-box width, maximization of b-box height, selection of center are all different problems (the last one itself is a set of different problems). And it looks like your original problem is not one of these... – maxim1000 Dec 17 '17 at 09:38
  • @maxim1000 Well, the actual problem is described by the pictures at the end of question: I have pictures of tall objects, but they are tilted and I want to set them straight. I can detect the objects and extract them from the photo, but I can't figure hot to rotate them so that they're straight. – Tomáš Zato Dec 17 '17 at 11:44
  • @TomášZato, what should be for L ? – maxim1000 Dec 18 '17 at 19:00

4 Answers4

2

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

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Yeah, my googling research led to similar conclusions. I still hoped there might be a trick without implementing all that. – Tomáš Zato Dec 16 '17 at 10:00
  • @TomášZato btw the centroid and most distant point approach does not necessarily reveal the best angle position (did go that path before). For example take simple rectangle the corners are not aligned with Y axis for minimal width BBOX. And the angle difference can not be inferred from that corner position.... – Spektre Dec 16 '17 at 14:08
1

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

Felix Goldberg
  • 401
  • 4
  • 18
0

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.

Ralf Kleberhoff
  • 6,990
  • 1
  • 13
  • 7
0

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.

Francesco Callari
  • 11,300
  • 2
  • 25
  • 40