Minimum Bounding Box or Convex Hull for any shape quadrilateral?

Question

Note: I am trying to make a process that can work with a general range of images, orientations, and qualities, not specific to just this image.

I understand that you can use convex hull to enclose a set of points with a polygon, and you can use one of the several algorithms to create a minimum bounding box for those points. However, I want to do what is similar to the minimum bounding box, but without limiting it to be a rectangle.

Say I have this receipt:

The convex hull:

The minimum bounding box (rotating calliper):

My Goal: (ms-paint):

As you can see the minimum bounding box doesn't quite work out, since the receipt is a trapezoid from the perspective. This only gets worse the lower the perspective. I want to have 4 points, and sharp corners, so I can't use the convex hull.

Is there an algorithm that I can use to get something similar to the convex hull, or minimum bounding box, but limited to 4 points, and any quadrilateral shape?

Answer 1

With some messing around with colorspace filtering and morphological operations, I was able to use the Harris detector with success. You could also expand this out using intersection points like I did here from Hough Lines instead, which might be useful, though a little verbose. This works well for this particular image, but for a pipeline it requires a lot of parameters (opening and closing kernel sizes, iterations).

My implementation is in Python, but this of course could work in C++ or Java as well:

import numpy as np
import cv2

# read image
img = cv2.imread('receipt.png')

# thresholding
blur = cv2.GaussianBlur(img, (5,5), 1)
hls = cv2.cvtColor(blur, cv2.COLOR_BGR2HLS)
low = np.array([0, 70, 0])
high = np.array([255, 255, 85])
thresh = cv2.inRange(hls, low, high)

# morphological operations to get the paper
kclose = np.ones((3,3), dtype=np.uint8)
kopen = np.ones((5,5), dtype=np.uint8)
closing = cv2.morphologyEx(thresh, cv2.MORPH_CLOSE, kclose, iterations=2)
opening = cv2.morphologyEx(closing, cv2.MORPH_OPEN, kopen, iterations=6)

# corner detection
opening = cv2.GaussianBlur(opening, (3,3), 1)
opening = np.float32(opening)
dst = cv2.cornerHarris(opening, 2, 3, 0.04)

# drawing corners
dst = cv2.dilate(dst, None)
img[dst>0.01*dst.max()]=[0,0,255]

cv2.imshow('Corners', img)
cv2.waitKey(0)

And here's the corners:

Note that you get multiple pixels from Harris so you'll have to do clustering to get singular corner points if you want to use them to do warping afterwards.

I applied the masks from colorspace filtering, closing, and opening on the image so you can see the masks after those operations.

Filtering:

Closing:

Opening: