Algorithm to detect corners of paper sheet in photo

Question

What is the best way to detect the corners of an invoice/receipt/sheet-of-paper in a photo? This is to be used for subsequent perspective correction, before OCR.

My current approach has been:

RGB > Gray > Canny Edge Detection with thresholding > Dilate(1) > Remove small objects(6) > clear boarder objects > pick larges blog based on Convex Area. > [corner detection - Not implemented]

I can't help but think there must be a more robust 'intelligent'/statistical approach to handle this type of segmentation. I don't have a lot of training examples, but I could probably get 100 images together.

Broader context:

I'm using matlab to prototype, and planning to implement the system in OpenCV and Tesserect-OCR. This is the first of a number of image processing problems I need to solve for this specific application. So I'm looking to roll my own solution and re-familiarize myself with image processing algorithms.

Here are some sample image that I'd like the algorithm to handle: If you'd like to take up the challenge the large images are at http://madteckhead.com/tmp

_{(source: madteckhead.com)}

_{(source: madteckhead.com)}

_{(source: madteckhead.com)}

_{(source: madteckhead.com)}

In the best case this gives:

_{(source: madteckhead.com)}

_{(source: madteckhead.com)}

_{(source: madteckhead.com)}

However it fails easily on other cases:

_{(source: madteckhead.com)}

_{(source: madteckhead.com)}

_{(source: madteckhead.com)}

Thanks in advance for all the great ideas! I love SO!

EDIT: Hough Transform Progress

Q: What algorithm would cluster the hough lines to find corners? Following advice from answers I was able to use the Hough Transform, pick lines, and filter them. My current approach is rather crude. I've made the assumption the invoice will always be less than 15deg out of alignment with the image. I end up with reasonable results for lines if this is the case (see below). But am not entirely sure of a suitable algorithm to cluster the lines (or vote) to extrapolate for the corners. The Hough lines are not continuous. And in the noisy images, there can be parallel lines so some form or distance from line origin metrics are required. Any ideas?

_{(source: madteckhead.com)}

Solution 1

I'm Martin's friend who was working on this earlier this year. This was my first ever coding project, and kinda ended in a bit of a rush, so the code needs some errr...decoding... I'll give a few tips from what I've seen you doing already, and then sort my code on my day off tomorrow.

First tip, OpenCV and python are awesome, move to them as soon as possible. :D

Instead of removing small objects and or noise, lower the canny restraints, so it accepts more edges, and then find the largest closed contour (in OpenCV use findcontour() with some simple parameters, I think I used CV_RETR_LIST). might still struggle when it's on a white piece of paper, but was definitely providing best results.

For the Houghline2() Transform, try with the CV_HOUGH_STANDARD as opposed to the CV_HOUGH_PROBABILISTIC, it'll give rho and theta values, defining the line in polar coordinates, and then you can group the lines within a certain tolerance to those.

My grouping worked as a look up table, for each line outputted from the hough transform it would give a rho and theta pair. If these values were within, say 5% of a pair of values in the table, they were discarded, if they were outside that 5%, a new entry was added to the table.

You can then do analysis of parallel lines or distance between lines much more easily.

Hope this helps.

Solution 2

Here's what I came up with after a bit of experimentation:

import cv, cv2, numpy as np
import sys

def get_new(old):
    new = np.ones(old.shape, np.uint8)
    cv2.bitwise_not(new,new)
    return new

if __name__ == '__main__':
    orig = cv2.imread(sys.argv[1])

    # these constants are carefully picked
    MORPH = 9
    CANNY = 84
    HOUGH = 25

    img = cv2.cvtColor(orig, cv2.COLOR_BGR2GRAY)
    cv2.GaussianBlur(img, (3,3), 0, img)


    # this is to recognize white on white
    kernel = cv2.getStructuringElement(cv2.MORPH_RECT,(MORPH,MORPH))
    dilated = cv2.dilate(img, kernel)

    edges = cv2.Canny(dilated, 0, CANNY, apertureSize=3)

    lines = cv2.HoughLinesP(edges, 1,  3.14/180, HOUGH)
    for line in lines[0]:
         cv2.line(edges, (line[0], line[1]), (line[2], line[3]),
                         (255,0,0), 2, 8)

    # finding contours
    contours, _ = cv2.findContours(edges.copy(), cv.CV_RETR_EXTERNAL,
                                   cv.CV_CHAIN_APPROX_TC89_KCOS)
    contours = filter(lambda cont: cv2.arcLength(cont, False) > 100, contours)
    contours = filter(lambda cont: cv2.contourArea(cont) > 10000, contours)

    # simplify contours down to polygons
    rects = []
    for cont in contours:
        rect = cv2.approxPolyDP(cont, 40, True).copy().reshape(-1, 2)
        rects.append(rect)

    # that's basically it
    cv2.drawContours(orig, rects,-1,(0,255,0),1)

    # show only contours
    new = get_new(img)
    cv2.drawContours(new, rects,-1,(0,255,0),1)
    cv2.GaussianBlur(new, (9,9), 0, new)
    new = cv2.Canny(new, 0, CANNY, apertureSize=3)

    cv2.namedWindow('result', cv2.WINDOW_NORMAL)
    cv2.imshow('result', orig)
    cv2.waitKey(0)
    cv2.imshow('result', dilated)
    cv2.waitKey(0)
    cv2.imshow('result', edges)
    cv2.waitKey(0)
    cv2.imshow('result', new)
    cv2.waitKey(0)

    cv2.destroyAllWindows()

Not perfect, but at least works for all samples:

Solution 3

A student group at my university recently demonstrated an iPhone app (and python OpenCV app) that they'd written to do exactly this. As I remember, the steps were something like this:

• Median filter to completely remove the text on the paper (this was handwritten text on white paper with fairly good lighting and may not work with printed text, it worked very well). The reason was that it makes the corner detection much easier.
• Hough Transform for lines
• Find the peaks in the Hough Transform accumulator space and draw each line across the entire image.
• Analyse the lines and remove any that are very close to each other and are at a similar angle (cluster the lines into one). This is necessary because the Hough Transform isn't perfect as it's working in a discrete sample space.
• Find pairs of lines that are roughly parallel and that intersect other pairs to see which lines form quads.

This seemed to work fairly well and they were able to take a photo of a piece of paper or book, perform the corner detection and then map the document in the image onto a flat plane in almost realtime (there was a single OpenCV function to perform the mapping). There was no OCR when I saw it working.

Solution 4

Instead of starting from edge detection you could use Corner detection.

Marvin Framework provides an implementation of Moravec algorithm for this purpose. You could find the corners of the papers as a starting point. Below the output of Moravec's algorithm:

Solution 5

Also you can use MSER (Maximally stable extremal regions) over Sobel operator result to find the stable regions of the image. For each region returned by MSER you can apply convex hull and poly approximation to obtain some like this:

But this kind of detection is useful for live detection more than a single picture that not always return the best result.

View more solutions

Comments

[Nathan Keller]

Yes, I got it to work in about 95% of cases. I've since had to shelve the code due to time shortages. I'll post a follow up at some stage, feel free to commission me if you require urgent help. Sorry for the lack of good follow up. I'd love to get back to working on this feature.

[tim]

Nathan, could you please post a follow up on how you ended up doing it? I've stuck at the same point recognizing corners / outter-contour of sheet of papers. I run into the exact same problems as you did so I'd be highly interested in a solution.

[ChrisF]

All of the images in this post now 404.

[Nathan Keller]

Thanks for the great ideas Martin. Ive taken your advice and implemented the Hough transform approach. (See results above). I'm struggling to determine a robust algorithm that will extrapolate the lines to find the intersections. There are not many lines, and a few false positives. Do you have any advice on how I might best merge and discard lines? If your students are interested, please encourage them to get in contact. I'd love to hear their experiences in getting the algorithms to run on a mobile platform. (That is my next goal). Many thanks for your ideas.

[Nathan Keller]

Hi Ares, thanks for your ideas! I've implemented the Hough transform (see above). I can't work out a robust way to find the corners given the false positives, and non continuous lines. Do you have any further ideas? It has been awhile since I looked at SVM techniques. Am is this a supervised approach? I don't have any training data, but I could generate some. I would be interested in exploring the approach as am keen to learn more about SVM. Can you recommend any resources. Kind regards. Nathan

[Martin Foot]

It looks like the HT for lines has worked well in all but your second image, but are you defining a threshold tolerance for your start and end values in the accumulator? The HT doesn't really define start and end positions, rather the m and c values in y=mx+c. See here - note that this is using polar coordinates in the accumulator rather than cartesian. In this way you can group lines by c and then by m in order to thin them out and by imagining the lines as extending across the whole image you'll find more useful intersections.

[Nathan Keller]

Hi Daniel, thanks for getting involved. I like you approach. its actually the route Im getting good results with at the moment. There was even and OpenCV example what detected the rectangles. Just had to do some filtering on the results. as you were saying the white on white is difficult t detect with this method. But it was a simple and less costly approach than the hough. I've actually left the hough approach out of my algo and have done a poly approximation, have a look at the squares example in opencv. I'd like to see your implementation of the hough voting. Thanks in advance, Nathan

[Navneet Singh]

I'm working on the similar project. I run above the code and it gives me the error " No module named cv ". I installed the Open CV 2.4 version and import cv2 is working perfectly for me.

[Can Ürek]

Where is lines variable definition? Must be std::vector<cv::Vec4i> lines;

[GBF_Gabriel]

@CanÜrek You are right. std::vector<cv::Vec4i> lines; is declared in a global scope in my project.

[Monty]

Can you share some more details for this perhaps some code, thanks a bunch in advance

[Praveen]

I am receiving an error in cv2.CHAIN_APPROX_SIMPLE saying too many values to unpack. Any idea? I am using a 1024*1024 image as my sample

[Praveen]

Thanks all, just figured out the change of syntax in the current Opencv branch answers.opencv.org/question/40329/…

[the7erm]

Would you be kind enough to update this code so it works? pastebin.com/PMH5Y0M8 it just gives me a black page.

[aurelianr]

Do you have any idea about how to transform the following code to java: for line in lines[0]: cv2.line(edges, (line[0], line[1]), (line[2], line[3]), (255,0,0), 2, 8) # finding contours contours, _ = cv2.findContours(edges.copy(), cv.CV_RETR_EXTERNAL, cv.CV_CHAIN_APPROX_TC89_KCOS) contours = filter(lambda cont: cv2.arcLength(cont, False) > 100, contours) contours = filter(lambda cont: cv2.contourArea(cont) > 10000, contours)

[Anshuman Kumar]

Isn't MSER meant to extract blobs? I tried it and it detects most of the text only

[Anshuman Kumar]

I was having issues with this approach, I will post a solution if I can devise something better for future reference

[Carlos Diego]

@AnshumanKumar i'm really in need of help with this question, can you help me, please? stackoverflow.com/questions/61216402/…

[Carlos Diego]

@MartinFoot i'm really in need of help with this question, can you help me, please? stackoverflow.com/questions/61216402/…

[Carlos Diego]

Vanuan i'm really in need of help with this question, can you help me, please? stackoverflow.com/questions/61216402/…

[Akash Chaudhary]

Hey @GBF_Gabriel, Can you please tell how to find the four corners or edges of the required image instead of drawing lines.

[Akash Chaudhary]

I am getting this error E/cv::error(): OpenCV(4.3.0) Error: Assertion failed (reader.ptr != NULL) in cvDrawContours