How to force approxPolyDP() to return only the best 4 corners? - Opencv 2.4.2

Question

well the question says it all

I have some contour and I want to get the best quadrangular out of it

Answer 1

I believe you can perform a binary search on epsilon value to find best simplification.

The code:

def simplify_contour(contour, n_corners=4):
    '''
    Binary searches best `epsilon` value to force contour 
        approximation contain exactly `n_corners` points.

    :param contour: OpenCV2 contour.
    :param n_corners: Number of corners (points) the contour must contain.

    :returns: Simplified contour in successful case. Otherwise returns initial contour.
    '''
    n_iter, max_iter = 0, 100
    lb, ub = 0., 1.

    while True:
        n_iter += 1
        if n_iter > max_iter:
            return contour

        k = (lb + ub)/2.
        eps = k*cv2.arcLength(contour, True)
        approx = cv2.approxPolyDP(contour, eps, True)

        if len(approx) > n_corners:
            lb = (lb + ub)/2.
        elif len(approx) < n_corners:
            ub = (lb + ub)/2.
        else:
            return approx

Answer 2

I had a problem with cards with rounded corners where even if I got approxPolyDP() to return only 4 points/edges it was never the best because the "corners" were frequently picked to be closer to these rounded edges. My solution involved increasing the number of points returned to follow the corners and then my problem allowed me to relatively safely assume that the four longest edges found represented the sides. Take these four longest edges in order and find where each pair intersects and you have the points of the quad.

As a bonus you already have the lengths so you can feed the points to your perspective transform in the right order so it doesn't get squashed and stretched the wrong way.

Answer 3

You have to find an appropriate value for epsilon by using the method of nested intervals, since the number of points increases with decreasing epsion. It may be possible, that the value of 4 corner points cannot be reached though, since the number of points may jump from 3 to 5 at a certain value of epsilon.

If you want to exclude this case, you might need to implement the Ramer–Douglas–Peucker algorithm yourself and modify it, so a given number of points will be returned. (By the way, you're asking for the 'best' 4 corners. You have to specify what best means. approxPolyDp() does not claim an optimal solution!)

Other than that, I see no way to force approxPolyDP() to return 4 points.