title: Algorithm to detect corners of paper sheet in photo
body: <p>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.</p>
  
  <h2>My current approach has been:</h2>
  
  <p>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]</p>
  
  <p>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.</p>
  
  <h2>Broader context:</h2>
  
  <p>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. </p>
  
  <p>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 <a href="http://madteckhead.com/tmp" rel="noreferrer">http://madteckhead.com/tmp</a> </p>
  
  <p><a href="https://i.stack.imgur.com/z13MW.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/z13MW.jpg" alt="case 1"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0773_sml.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>
  
  <p><a href="https://i.stack.imgur.com/6GOPm.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/6GOPm.jpg" alt="case 2"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0774_sml.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>
  
  <p><a href="https://i.stack.imgur.com/y6Nq8.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/y6Nq8.jpg" alt="case 3"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0775_sml.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>
  
  <p><a href="https://i.stack.imgur.com/Mzaud.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/Mzaud.jpg" alt="case 4"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0776_sml.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>
  
  <h2>In the best case this gives:</h2>
  
  <p><a href="https://i.stack.imgur.com/817rw.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/817rw.jpg" alt="case 1 - canny"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0773_canny.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>
  
  <p><a href="https://i.stack.imgur.com/NFior.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/NFior.jpg" alt="case 1 - post canny"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0773_postcanny.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>
  
  <p><a href="https://i.stack.imgur.com/suaqb.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/suaqb.jpg" alt="case 1 - largest blog"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0773_blob.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>
  
  <h2>However it fails easily on other cases:</h2>
  
  <p><a href="https://i.stack.imgur.com/nKNwp.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/nKNwp.jpg" alt="case 2 - canny"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0774_canny.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>
  
  <p><a href="https://i.stack.imgur.com/ZqznM.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/ZqznM.jpg" alt="case 2 - post canny"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0774_postcanny.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>
  
  <p><a href="https://i.stack.imgur.com/X8hba.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/X8hba.jpg" alt="case 2 - largest blog"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0774_blob.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>
  
  <p>Thanks in advance for all the great ideas! I love SO!</p>
  
  <h2>EDIT: Hough Transform Progress</h2>
  
  <p>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?</p>
  
  <p><img src="https://web.archive.org/web/20130913020727/http://madteckhead.com/tmp/IMG_0773_hough.jpg" alt="case 1">
  <a href="https://i.stack.imgur.com/NYGGm.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/NYGGm.jpg" alt="case 2"></a>
  <a href="https://i.stack.imgur.com/toesV.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/toesV.jpg" alt="case 3"></a>
  <a href="https://i.stack.imgur.com/Cyq6f.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/Cyq6f.jpg" alt="case 4"></a><br>
  <sub>(source: <a href="http://madteckhead.com/tmp/IMG_0776_hough.jpg" rel="noreferrer">madteckhead.com</a>)</sub>  </p>