OCR image pre-processor for detecting and reducing skew of the image of textual matter of a scanned document

• US 5,594,817 A
• Filed: 05/22/1995
• Issued: 01/14/1997
• Est. Priority Date: 10/19/1992
• Status: Expired due to Term

• Current Assignee: Accusoft Corporation
• Original Assignee: TMSSequoia Co.
• Inventors: Allen, Dana R., Fast, Bruce B.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US08/445,927
• Time in Patent Office: 603 Days
• Field of Search: 382/289, 382/290, 382/293, 382/296, 382/308, 382/174, 382/176, 382/245, 382/254, 382/256, 382/257, 358/261.1, 358/452
• US Class Current: 382/290
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines
• CPC Class Codes: G06V 30/155 Removing patterns interfering with the pattern to be recognised, such as ruled lines or underlines
• CPC Class Codes: G06V 30/164 Noise filtering
• CPC Class Codes: H04N 1/38 Circuits or arrangements for blanking or otherwise eliminating unwanted parts of pictures H04N1/387 takes precedence
• CPC Class Codes: H04N 1/3878 Skew detection or correction
• CPC Class Codes: H04N 1/409 Edge or detail enhancement; Noise or error suppression

Abstract

A method is provided for identifying, correcting, modifying and reporting imperfections and features in pixel images that prevent or hinder proper OCR (Optical Character Recognition) and other document imaging processes. One embodiment of this invention provides that run length compressed images can be analyzed and corrected directly for improved performance. Major steps included in this invention for the enhancement of images for OCR and document imaging are: The detection, correction and reporting of skew from text or graphical lines. The detection, correction, and reporting of varying image registration. The detection, conversion and reporting of inverse type. The detection, removal and reporting of dot shading and lines with protection of characters.

Claims

1. A process for enhancing an image of a scanned document, said image consisting of run-length coded scan lines including white run-length values and black-run-length values, and containing a first plurality of lines of textual matter, said textual matter including characters with descenders, said process including a de-skew step for reducing skew of said textual matter, said skew including a vertical skew component and a horizontal skew component, said de-skew step comprising

a sub-step for determining a line skew in scan lines per line of textual matter for each one of a second plurality of said lines of textual matter of said image,

a sub-step for defining a determined skew value and a skew direction using the line skew values so determined for said second plurality of lines of textual matter;

a sub-step for reducing said vertical skew component of said skew using said determined skew value;

a sub-step for reducing said horizontal skew component of said skew using said determined skew value,

said sub-step for reducing said vertical skew component includes sequentially dividing each of said run-length coded scan lines into a plurality of skewed line segments of substantially equal lengths,

wherein said plurality of skewed line segments equals said determined skew value plus 1 and includes a reference skew segment, and

wherein said sub-step for reducing said vertical skew moves each of said skewed line segments proportionally to the determined skew value and relative to its distance from said reference skew segment measured in skewed line segments.

2. A process for enhancing an image of a scanned document as claimed in claim 1, wherein said substep for defining said determined skew value includes averaging said line skew values, thereby determining a determined average line skew value and comparing said determined average line skew value with a predetermined upper and a predetermined lower limit and using said average line skew value as the determined skew value for reducing said skew if said determined average line skew value falls between said predetermined upper and lower limit.

3. A process for enhancing an image of a scanned document as claimed in claim 2, wherein said substep for defining the determined skew value includes selecting a line skew value closest to the average line skew value as the effective line skew value in said deskew step for the image.

4. A scanned document image enhancement process for reducing skew of said document image provided in run-length representation having white run-length values and black run-length values, said document including a plurality of lines of characters including characters, said image having scan lines and pixel columns addresses, said process including the steps of

determining the existence of skew;

determining a line skew value for each of selected lines of characters included in said plurality of lines of characters for reducing the skew of said image; and

reducing the skew;

said step for determining the line skew value includes for each of said selected lines of characters

a step for eliminating the descenders from said characters in each of said selected lines of characters and blurring each of said selected lines of characters by eliminating white spaces under a predetermined width in and between said characters of said lines of characters to form new black run-length values and then eliminating black run-length values under a predetermined value, thereby providing a blurred copy of said selected lines of characters and generating for each of said selected lines of characters a sequence of black reference run-length segments at the bottom of said selected line of characters, a step for determining the begin and end of said sequence of black run-length segments thereby defining a reference line, said reference line having a begin and an end, and

a step for determining a skew number of scan lines between the begin and end of said reference line,

said step for determining the line skew value further including step for providing an average skew number of scan lines for said selected lines of characters by averaging said skew number of scan lines of said selected lines of characters, and wherein said line skew value is said average skew number; and

said step of reducing the skew further including a step for subdividing said run length representation of said image into a multi-run-length segment representation of equal length segments, whereby the number of segments is equal to the line skew in scan lines plus one.

5. A scanned document image enhancement process for reducing skew of said image as claimed in claim 4, wherein said step for reducing the skew is subdivided into a step for reducing vertical skew and a step for reducing horizontal skew;

said step for reducing said vertical skew sequentially includes assembling run-lengths representations of sequential column sections of adjacent scan lines to a complete run-length representation of a de-skewed scan line of said image, said step for reducing said horizontal skew including

determining a reference scan line,

determining a total horizontal image skew, assigning for each of the scan lines a proportional skew value, and increasing in each of said scan lines the white run-length value of a white border area of the image by said proportional skew value.

6. A scanned document image enhancement process for reducing skew of said image as claimed in claim 5, wherein said step for reducing said horizontal skew includes a sub-step for determining a first white run-length value for the border area at the top of the document image, and a second white run-length value for the border area at the bottom of the document, determining the larger one of said first and second white run-length values, and applying said proportional skew values successively to adjacent scan lines towards the other one of said first and second white run-length values.

7. A scanned document image enhancement process for reducing skew of said document image provided in run-length representation having white run-length values and black run-length values, said document including a plurality of lines of characters including characters, said image having scan lines and pixel columns addresses, said process including the steps of

determining the existence of skew;

determining a line skew value for selected lines of characters included in said plurality of lines of characters for reducing the skew of said image; and

reducing the skew;

said step for determining the line skew value includes for each of said selected lines of characters

a step for eliminating the descenders from said characters of said selected lines and blurring said selected lines of characters by eliminating white spaces under a predetermined width in and between said characters of said selected lines of characters and by eliminating black run-length values under a predetermined value, thereby providing a blurred copy of said selected lines of characters and generating for each of said selected lines of characters a sequence of black reference run-length segments at the bottom of said selected lines of characters, a step for determining the begin and end of said sequence of black run-length segments thereby defining a reference line, said reference line having a begin and an end, and

a step for determining a skew number of scan lines between the begin and the end of said reference line,

said step for determining the line skew value further including a step for providing an average skew number of scan lines for said selected lines of characters by averaging said skew number of scan lines of said selected lines of characters, and wherein said line skew value is said average skew number, and a step for determining local skew values within said selected lines of characters and a step for detecting differences between adjacent local skew values inside each of said selected lines of characters.

8. A scanned document image enhancement process for reducing skew of said image as claimed in claim 7 wherein said step for detecting differences initiates a fool'"'"'s skew evaluation step if a detected difference exceeds a predetermined difference value.

9. A scanned document image enhancement process for reducing skew of said image as claimed in claim 8 wherein said fool'"'"'s skew evaluation step selects the skew of the longest line section as line skew value if a fool'"'"'s skew condition exists.