0
$\begingroup$

In an image processing project (using opencv with python), I am trying to detect as precisely as possible the location of a rectangular object in a photograph. My final goal is to output the 4 corners of the object.

For example, an image could look like this: Original image

In the first stage I am able to detect an approximate boundary for the image, like so: Initial Detection

Now, I have the above red convex polygon.

Next, I would like to compute the Minimum Area Bounding Quadrilateral, and this is where I'm stuck.

My question is, given a convex polygon, what is an efficient algorithm to find a minimum area bounding quadrilateral?

Thanks!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ "A rectangular object" vs "minimum area bounding quadrilateral" are not consistent. Can you explain in the question why you do not care it being rectangular any more? $\endgroup$
    – John L.
    Jul 21, 2019 at 9:51
  • 1
    $\begingroup$ @Apass.Jack: isn't it obvious that the object is rectangular and perspective deforms it ? $\endgroup$
    – Yves Daoust
    Jul 21, 2019 at 10:07
  • $\begingroup$ @YvesDaoust Yes, it is obvious. I was just being careful to avoid XY problem. I also hoped that the questioner could explain the "minimum area" as well, although it is also obvious that the "minimum area" could be a reasonable requirement. Is there a different approach to approximate a quadrilateral? $\endgroup$
    – John L.
    Jul 21, 2019 at 10:20
  • $\begingroup$ @Apass.Jack: if the shape is truly a convex quadrilateral, both the minimum area and minimum perimeter criteria will exactly return this quadrilateral; which will also be the convex hull, made of four segments. In real life, you get "some" approximation. $\endgroup$
    – Yves Daoust
    Jul 21, 2019 at 15:52
  • 1
    $\begingroup$ @YvesDaoust Yes, I agreed. I was encouraging the OP to explain his approach as well as to looks for different ideas. By the way, your answer is pretty good. I upvoted. $\endgroup$
    – John L.
    Jul 21, 2019 at 16:03

1 Answer 1

Reset to default
1
$\begingroup$

The fitting of a minimum area quadrilateral to a set of points is an uneasy problem, and I believe that simpler approaches are good enough.

Notice that the corners are rounded and cannot be used as such. So you'd better fit straight edges and intersect them to obtain the quadrilateral.

One approach is by the Hough transform. To make it maximally efficient, I would recommend to process four tight areas or interest around the edges of the axis-aligned bounding box. This will make processing much faster, avoid false positives and avoid any ambiguity on the correspondences.

You can also sample points on the four sides and fit a straight line by total-least squares, or by some robust line fitting method.

If you want to make sure that the fitted lines don't cross the shape at all, you can handle the four sides independently and consider a partition of the plane in the four quadrants delimited by the diagonals (even if they are approximate). In every quadrant, you will find the minimum area triangle formed by the line against an edge of the convex hull. Just try every edge of the convex hull in turn.

[Technically, it is possible that the minimum is achieved with a line through some vertex of the convex hull, with an intermediate angle, i.e. not in the direction of a hull side. We should also check if the area function is always unimodal in terms of the line angle. IMO these refined considerations can come later.]

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! How do I approximate the diagonals? $\endgroup$
    – Mathguy
    Jul 22, 2019 at 11:07
  • $\begingroup$ @Mathguy: find points farthest form the center. $\endgroup$
    – Yves Daoust
    Jul 22, 2019 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.