Method and system for auto-correcting perspective distortion in document images

• US 9,171,359 B1
• Filed: 09/11/2013
• Issued: 10/27/2015
• Est. Priority Date: 09/11/2013
• Status: Active Grant

• Current Assignee: Open Text Corporation
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Lund, Christopher D.
• Primary Examiner(s): Akhavannik, Hadi
• Application Number:
  US14/024,433
• Time in Patent Office: 776 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06V 10/243 by compensating for image skew or non-uniform image deformations
• CPC Class Codes: G06V 10/247 by affine transforms, e.g. correction due to perspective effects; Quadrilaterals, e.g. trapezoids
• CPC Class Codes: G06V 30/412 Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables
• CPC Class Codes: H04N 1/3878 Skew detection or correction

Abstract

Auto-correcting perspective distortion in document images is described. Line segments are identified in a distorted document image. Line segments are combined to form candidate lines. Candidate lines are grouped into a substantially horizontal group of lines and a substantially vertical group of lines. Linear equations are calculated to fit the substantially horizontal group of lines. Linear equations are calculated to fit the substantially vertical group of lines. The distorted document image is transformed based on two linear equations associated with two substantially horizontal lines and two linear equations associated with two substantially vertical lines.

Claims

1. A system for auto-correcting perspective distortion in document images, the system comprising:

a processor-based application, which when executed on a computer, will cause the processor to;

identify a plurality of line segments in a distorted document image;

combine a second plurality of line segments to form a plurality of candidate lines;

group a second plurality of candidate lines into a substantially horizontal group of lines;

group a third plurality of candidate lines into a substantially vertical group of lines;

calculate a first plurality of linear equations to fit the substantially horizontal group of lines;

calculate a second plurality of linear equations to fit the substantially vertical group of lines; and

transform the distorted document image based on a first two linear equations of the first plurality of linear equations associated with two substantially horizontal lines comprising a lowest substantially horizontal line and a highest substantially horizontal line of the substantially horizontal group of lines and a second two linear equations of the second plurality of linear equations associated with two substantially vertical lines comprising a leftmost substantially vertical line and a rightmost substantially vertical line of the substantially vertical group of lines.

2. The system of claim 1, wherein identifying the plurality of line segments in the distorted document image comprises:

creating a grayscale image of the distorted document image;

applying a blur algorithm to the grayscale image to remove the effects of noise in the grayscale image;

applying an edge detector algorithm to the grayscale image to identify a plurality of edges in the grayscale image;

dilating the plurality of edges to merge together edges within a proximity threshold to form a plurality of dilated line segments;

applying a skeleton transform to the plurality of dilated line segments to thin the plurality of dilated line segments to a plurality of potential line segments; and

applying a probabilistic transform algorithm to the plurality of potential line segments to identify the plurality of line segments.

3. The system of claim 1, wherein the plurality of line segments is based on at least one of document text, an edge of the distorted document image, and a barcode.

4. The system of claim 1, wherein combining the second plurality of line segments to form the plurality of candidate lines comprises combining a plurality of line segments that are substantially collinear to form a candidate line, and wherein an angle and an intercept associated with the candidate line is based on a weighted average of angles and intercepts associated with each of the plurality of line segments that are substantially collinear.

5. The system of claim 1, wherein grouping the second plurality of candidate lines into the substantially horizontal group of lines comprises:

grouping the second plurality of candidate lines associated with an angle between negative 45 degrees to a horizon and positive 45 degrees to the horizon; and

discarding a candidate line based on at least one of determining that farthest apart points in a candidate line are less apart than a distance threshold and determining that an angle associated with the candidate line differs from an average angle associated with the second plurality of the candidate lines by more than an angle threshold.

6. The system of claim 1, wherein grouping the third plurality of candidate lines into the substantially vertical group of lines comprises:

grouping the third plurality of candidate lines associated with an angle between positive 45 degrees to a horizon and positive 135 degrees to the horizon; and

discarding a candidate line based on at least one of determining that farthest apart points in a candidate line are less apart than a distance threshold and determining that an angle associated with the candidate line differs from an average angle associated with the third plurality of the candidate lines by more than an angle threshold.

7. A computer-implemented method for auto-correcting perspective distortion in document images, the method comprising:

identifying a plurality of line segments in a distorted document image;

combining a second plurality of line segments to form a plurality of candidate lines;

grouping a second plurality of candidate lines into a substantially horizontal group of lines;

grouping a third plurality of candidate lines into a substantially vertical group of lines;

calculating a first plurality of linear equations to fit the substantially horizontal group of lines;

calculating a second plurality of linear equations to fit the substantially vertical group of lines; and

transforming the distorted document image based on a first two linear equations of the first plurality of linear equations associated with two substantially horizontal lines comprising a lowest substantially horizontal line and a highest substantially horizontal line of the substantially horizontal group of lines and a second two linear equations of the second plurality of linear equations associated with two substantially vertical lines comprising a leftmost substantially vertical line and a rightmost substantially vertical line of the substantially vertical group of lines.

8. The computer-implemented method of claim 7, wherein identifying the plurality of line segments in the distorted document image comprises:

creating a grayscale image of the distorted document image;

applying a blur algorithm to the grayscale image to remove the effects of noise in the grayscale image;

applying an edge detector algorithm to the grayscale image to identify a plurality of edges in the grayscale image;

dilating the plurality of edges to merge together edges within a proximity threshold to form a plurality of dilated line segments;

applying a skeleton transform to the plurality of dilated line segments to thin the plurality of dilated line segments to a plurality of potential line segments; and

applying a probabilistic transform algorithm to the plurality of potential line segments to identify the plurality of line segments.

9. The computer-implemented method of claim 7, wherein the plurality of line segments is based on at least one of document text, an edge of the distorted document image, and a barcode.

10. The computer-implemented method of claim 7, wherein combining the second plurality of line segments to form the plurality of candidate lines comprises combining a plurality of line segments that are substantially collinear to form a candidate line, and wherein an angle and an intercept associate with the candidate line is based on a weighted average of angles and intercepts associated with each of the plurality of line segments that are substantially collinear.

11. The computer-implemented method of claim 7, wherein grouping the second plurality of candidate lines into the substantially horizontal group of lines comprises:

grouping the second plurality of candidate lines associated with an angle between negative 45 degrees to a horizon and positive 45 degrees to the horizon; and

discarding a candidate line based on at least one of determining that farthest apart points in a candidate line are less apart than a distance threshold and determining that an angle associated with the candidate line differs from an average angle associated with the second plurality of the candidate lines by more than an angle threshold.

12. The computer-implemented method of claim 7, wherein grouping the third plurality of candidate lines into the substantially vertical group of lines comprises:

grouping the third plurality of candidate lines associated with an angle between positive 45 degrees to a horizon and positive 135 degrees to the horizon; and

discarding a candidate line based on at least one of determining that farthest apart points in a candidate line are less apart than a distance threshold and determining that an angle associated with the candidate line differs from an average angle associated with the third plurality of the candidate lines by more than an angle threshold.

13. A computer program product, comprising computer-readable program code to be executed by one or more processors when retrieved from a non-transitory computer-readable medium, the computer-readable program code including instructions to:

identify a plurality of line segments in a distorted document image;

combine a second plurality of line segments to form a plurality of candidate lines;

group a plurality of candidate lines into a substantially horizontal group of lines;

group a second plurality of candidate lines into a substantially vertical group of lines;

calculate a first plurality of linear equations to fit the substantially horizontal group of lines;

calculate a second plurality of linear equations to fit the substantially vertical group of lines; and

transform the distorted document image based on a first two linear equations of the first plurality of linear equations associated with two substantially horizontal lines comprising a lowest substantially horizontal line and a highest substantially horizontal line of the substantially horizontal group of lines and a second two linear equations of the second plurality of linear equations associated with two substantially vertical lines comprising a leftmost substantially vertical line and a rightmost substantially vertical line of the substantially vertical group of lines.

14. The computer program product of claim 13, wherein identifying the plurality of line segments in the distorted document image comprises:

creating a grayscale image of the distorted document image;

applying a blur algorithm to the grayscale image to remove the effects of noise in the grayscale image;

applying an edge detector algorithm to the grayscale image to identify a plurality of edges in the grayscale image;

dilating the plurality of edges to merge together edges within a proximity threshold to form a plurality of dilated line segments;

applying a skeleton transform to the plurality of dilated line segments to thin the plurality of dilated line segments to a plurality of potential line segments; and

applying a probabilistic transform algorithm to the plurality of potential line segments to identify the plurality of line segments.

15. The computer program product of claim 14, wherein the plurality of line segments is based on at least one of document text, an edge of the distorted document image, and a barcode.

16. The computer program product of claim 13, wherein combining the second plurality of line segments to form the plurality of candidate lines comprises combining a plurality of line segments that are substantially collinear to form a candidate line, and wherein an angle and an intercept associate with the candidate line is based on a weighted average of angles and intercepts associated with each of the plurality of line segments that are substantially collinear.

17. The computer program product of claim 13, wherein grouping the second plurality of candidate lines into the substantially horizontal group of lines comprises:

grouping the second plurality of candidate lines associated with an angle between negative 45 degrees to a horizon and positive 45 degrees to the horizon; and

discarding a candidate line based on at least one of determining that farthest apart points in a candidate line are less apart than a distance threshold and determining that an angle associated with the candidate line differs from an average angle associated with the second plurality of the candidate lines by more than an angle threshold; and

wherein grouping the third plurality of candidate lines into the substantially vertical group of lines comprises;

grouping the third plurality of candidate lines associated with an angle between positive 45 degrees to a horizon and positive 135 degrees to the horizon; and

discarding a candidate line based on at least one of determining that farthest apart points in a candidate line are less apart than a distance threshold and determining that an angle associated with the candidate line differs from an average angle associated with the third plurality of the candidate lines by more than an angle threshold.