Multi-perpendicular line-based deskew with affine and perspective distortion correction

• US 8,731,336 B2
• Filed: 12/14/2011
• Issued: 05/20/2014
• Est. Priority Date: 12/14/2011
• Status: Active Grant

• Current Assignee: Ancestry.com Operations Inc. (Ancestry.com Incorporated)
• Original Assignee: Ancestry.com Operations Inc. (Ancestry.com Incorporated)
• Inventors: Reese, Jack, Reid, Shawn
• Primary Examiner(s): Allison, Andrae S
• Application Number:
  US13/325,396
• Publication Number:
  US 20130156344A1
• Time in Patent Office: 888 Days
• Field of Search: 382/162, 382/192, 382/276, 382/286, 382289-290, 382/296, 358/488, 358/452, 358/474, 358/537, 358/455
• US Class Current: 382/296
• CPC Class Codes: G06T 3/608 by skew deformation, e.g. two-pass or three-pass rotation
• CPC Class Codes: G06T 5/80 Geometric correction
• CPC Class Codes: G06V 10/243 by compensating for image skew or non-uniform image deformations
• CPC Class Codes: H04N 1/3878 Skew detection or correction

Abstract

The present invention provides a method of correcting alignment of an image. The method includes identifying an image of a document, and detecting a plurality of lines within the image. The method also includes classifying at least a subset of the plurality of lines as either horizontal or vertical lines, and determining whether a variance exists within a subset of the plurality of lines. Furthermore, the method includes applying a corrective transformation to adjust the image, where the variance within the subset of the plurality of lines is at least partially reduced as compared to the variance prior to the application of the corrective transformation.

Claims

1. A method of correcting alignment of an image, the method comprising:

identifying an image of a document;

detecting a plurality of lines that appear within the image;

classifying at least a subset of the plurality of lines as horizontal lines or vertical lines;

determining that a variance exists within the subset of the plurality of lines, wherein the variance that exists within the subset of the plurality of the lines is between at least one horizontal line and at least one vertical line, and the variance comprises the intersection of the lines being at an angle other than perpendicular to each other; and

applying a corrective transformation to adjust the image, wherein the variance within the subset of the plurality of lines is at least partially reduced as compared to the variance prior to the application of the corrective transformation.

2. The method of correcting alignment of an image as in claim 1, wherein the variance comprises skew or shear distortion.

3. The method of correcting alignment of an image as in claim 1, further comprising after applying the corrective transformation:

determining that the adjusted image orientation is at an angle other than the orientation of a reference set of axes; and

rotating the adjusted image to equalize the orientation of the adjusted image with the reference set of axes.

4. The method of correcting alignment of an image as in claim 1, wherein the identification of the image occurs at a computer imaging device that processes the image identified, stores the image, and retrieves the image prior to detecting the plurality of lines within the image.

5. The method of correcting alignment of an image as in claim 1, wherein the image is a computer readable image.

6. The method of correcting alignment of an image as in claim 5, further comprising generating the computer readable image with a document imaging system that captures the image of a document.

7. The method of correcting alignment of an image as in claim 6, wherein the document imaging system comprises at least one of microfilm, microfiche, an on demand printer, a facsimile machine, a copier, a document scanner, or a multifunction printer.

8. The method of claim 1, wherein the document comprises at least one of a table, a grid, or another detectable line-based aspect of the image.

9. A non-transitory computer-readable medium having sets of instructions stored thereon, which when executed by a computer cause the computer to:

identify an image of a document;

detect a plurality of lines that appear within the image;

classify at least a subset of the plurality of lines as horizontal lines or vertical lines;

determine that a variance exists within the subset of the plurality of lines, wherein the variance that exists within the subset of the plurality of the lines is between at least one horizontal line and at least one vertical line, and the variance comprises the intersection of the lines being at an angle other than perpendicular to each other; and

apply a corrective transformation to adjust the image, wherein the variance within the subset of the plurality of lines is at least partially reduced as compared to the variance prior to the application of the corrective transformation.