7

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:

enter image description here

The convex hull:

enter image description here

The minimum bounding box (rotating calliper):

enter image description here

My Goal: (ms-paint):

enter image description here

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?

Douglas Gaskell
  • 9,017
  • 9
  • 71
  • 128
  • Why not the Harris corner detector? Alternatively with your current algorithm you could reject the small lines from convex hull, and find the intersections of the long lines. With the two endpoints you can find the intersection [using determinants](https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line). Or you can keep all the points you have from convex hull and use [`kmeans` clustering](http://docs.opencv.org/3.0-beta/modules/core/doc/clustering.html) to find the centers of those 4 points and call those your points. – alkasm Jun 20 '17 at 02:19
  • 1
    See my answer [here](https://stackoverflow.com/questions/44449871/fine-tuning-hough-line-function-parameters-opencv/44454619#44454619) for an example of doing intersection clustering with Hough Lines. I think finding contours might be better for that image, and then fitting lines and finding the intersections like I did in that answer. – alkasm Jun 20 '17 at 02:21
  • @AlexanderReynolds Good ideas. Right now I generate contours, approximate them down, convex-hull them, then look for the minimum bounding box. The only reason I don't want to use the convex hull or contours is for awkwardly shaped receipts where you have very rounded or warped edges. Hough lines is an alternative, but I get hundreds and hundreds of lines from the text, even after heavy blurring and smoothing before edge detection. That would be another question if I want to improve that. Edit Good answer there, looks promising. – Douglas Gaskell Jun 20 '17 at 02:26
  • Use morphological operations to make the text virtually disappear before finding the contours. See an excellent example [here](https://stackoverflow.com/a/44054699/5087436) on Stack, doing everything *except* what you want to do. Either way the text processing can help get those Hough lines on track to the borders. And might be helpful for further processing that I'm assuming you'll be doing. – alkasm Jun 20 '17 at 02:32

1 Answers1

3

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:

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:

Filtering

Closing:

Closing

Opening:

Opening

alkasm
  • 22,094
  • 5
  • 78
  • 94
  • Thanks alex! I'm going through this now. Why did you chose the low/high colors that you did? Was that arbitrary, specific to this image, or a standard? If it's specific to just this image, would there be a method to try and determine what the low/high should be for a given image? – Douglas Gaskell Jun 20 '17 at 23:46
  • Completely specific to this image. Trying to do automatic filtering is pretty difficult in general without specific knowledge of what backgrounds there might be. If you're developing an app that should work with any background, this method is not very robust. You should experiment in different colorspaces to get a feel for what corresponds to white & light gray in each. For arbitrary images it's easier to proceed with your original method---contours and following them to corners in the ways I suggested in the comments on your question. – alkasm Jun 21 '17 at 05:04