Document skew detection/control system for printed document images containing a mixture of pure text lines and non-text portions

• US 5,506,918 A
• Filed: 12/23/1992
• Issued: 04/09/1996
• Est. Priority Date: 12/26/1991
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Ishitani, Yasuto
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/996,106
• Time in Patent Office: 1,203 Days
• Field of Search: 382/46, 382/18, 382/9, 382/289, 382/290, 382/296, 382/297, 382/173, 382/174, 382/176, 382/180, 382/205, 345/126
• US Class Current: 382/289
• CPC Class Codes: G06T 3/608 by skew deformation, e.g. two-pass or three-pass rotation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines
• CPC Class Codes: H04N 1/3878 Skew detection or correction

Abstract

A document skew detection apparatus for facilitating the recognition of the contents of a printed document includes an image processing section for generating a binary coded image of the document containing a plurality of black picture elements distributed among white picture elements to depict pure text lines and non-text portions of the document. The binary coded image is then modified so that certain ones of the black picture elements satisfying a predetermined condition are integrated together to generate a coarse document image being decreased in resolution. The apparatus also includes an image extraction section for extracting from the document image a local image region containing pure text lines occupying an almost entire area thereof, and skew detection section for detecting a direction of orientation of the text lines of the local region, and for determining an angular difference between a detected direction and a reference direction as a skew angle of the printed document.

Claims

1. An apparatus for determining a skew angle of an input document that contains at least a plurality of lines of text characters and a non-text portion, said apparatus comprising:

input means for generating an image of the input document;

detection means coupled to said input means for detecting a skew angle of said plurality of lines of text characters, comprising means for extracting at least one region including only text lines from the document with respect to a plurality of scanning lines which across the document image at selected angles that vary intermittently from a reference angle, means for computing complexity at each of angles, means for finding out a characteristic parameter in a distribution of the parameters in the region, and means for determining a corresponding angle, at which said characteristic parameter appears, as the skew angle of the input document; and

output means coupled to said detection means for generating a signal indicative of the skew angle thus determined.

2. The apparatus according to claim 1, wherein said input means comprises:

image processor means for generating a binary coded image of the input document, which contains a plurality of first picture elements having a first density level to depict contents of the document and a plurality of second picture elements having a second density level.

3. The apparatus according to claim 2, wherein said computing means computes said parameters by determining a plurality of parallel scanning lines across said extracted local region at a selected angle, counting a number of crossing points of each scanning line with the first picture elements to generate resultant count values of the scanning lines, and computing a complexity on the basis of the count values with respect to the selected angle, thereby obtaining complexities with the selected angle being varied intermittently.

4. The apparatus according to claim 3, wherein said determining means determines said corresponding angle as the skew angle of the input document, by finding out, from the complexities, a maximum complexity of highest sharpness of distribution and a scanning angle at which said maximum complexity occurs, and identifying said scanning angle as said skew angle.

5. The apparatus according to claim 4, wherein said complexity is substantial equal to:

space="preserve" listing-type="equation">(1/N)·

Σ

{(Ni-M).sup.2 },

where N is a total number of the scanning lines, Ni is a count value of transitions between said first and second picture elements and M is an average value of the count values at the selected angle.

6. The apparatus according to claim 5, further comprising:

skew corrector means coupled to said output means, for analyzing whether the skew angle thus detected falls within a predetermined range, and for, if such analysis is unsuccessful, rotate the document image by a specific angle compensating for said skew angle.

7. The apparatus according to claim 5, further comprising:

additional detection means coupled to said input means for detecting said skew angle, comprising means for iteratively computing another group of said parameters, with respect to a respective one of a plurality of scanning lines that cross the document image at selected angles that vary intermittently from another reference angle, means for finding out a characteristic parameter in a distribution of the parameters, and means for determining a corresponding angle thereof as the skew angle of the input document.

8. The apparatus according to claim 7, wherein said reference angle defines one of vertical and horizontal directions, and said another reference angle defines the other of the directions.

9. The apparatus according to claim 8, further comprising:

skew determination means coupled to said detection means and said additional detection means, for receiving detection results from them, and for finally determining the skew angle of the input document on the basis of the detection results in such a manner that, when a most distinguishable parameter having a highest peak sharpness is present in one of the vertical and horizontal directions, a corresponding angle at which said most distinguishable parameter appears is determined as the skew angle of the input document.

10. The apparatus according to claim 2, wherein said extracting means extracts said at least one region by dividing said document image into an array of rows and columns of sections, defining one or a plurality of parallel scanning lines crossing each of said sections, counting a number of transitions of each scanning line between the first and second picture elements in each section to generate resultant count values of the scanning lines, obtaining a sum of the count values with respect to every one of said sections, and determining, as said local region, one of said sections being greater in value than the remaining ones of said sections.

11. The apparatus according to claim 2, wherein said extracting means extracts said at least one region by defining a movable circular region in said document image, defining one or a plurality of parallel scanning lines crossing the circular region at a selected position, counting a number of transitions of each scanning line between the first and second picture elements in each section to generate resultant count values of the scanning lines, obtaining a sum of the count values, iteratively effecting similar operations while the circular region is moved at different positions in said document image, and determining, as said local region, the circular region being positioned at a specific position at which the sum of count values is greater than those obtained at the remaining positions of said circular region.

12. The apparatus according to claim 2, wherein said extracting means extracts said at least one region by slicing said document image into a plurality of stripe-shaped sections in a first reference direction, defining one or a plurality of parallel scanning lines crossing each of said sections, counting a number of transitions of each scanning line between the first and second picture elements of each section to generate resultant count values of the scanning lines, obtaining a sum of the count values with respect to each of said sections, identifying a preselected number of adjacent sections being maximum in the sum of count values, dividing said adjacent sections into a plurality of subsections in a second reference direction transverse to the first direction, computing a sum of similar count values with respect to each subsection, and determining, as said local region, a rectangular region consisting of a predetermined number of neighboring subsections being maximum in the sum of count values.

13. A document skew determination tool for facilitating the recognition of the contents of a printed document comprising the steps of:

generating a binary coded image of the document containing a plurality of black picture elements distributed among white picture elements to depict pure text lines and non-text portions of the document;

modifying the binary coded image so that certain ones of the black picture elements satisfying a predetermined condition are integrated together to generate a coarse document image being decreased in resolution;

extracting a local region from the document image, said local region containing pure text lines occupying an almost entire area thereof;

detecting a direction of orientation of the text lines in said local region; and

determining an angular difference between a detected direction and a reference direction as a skew angle of the printed document.

14. The tool according to claim 13, wherein said detecting step includes the substeps of:

scanning said local region at selected angles of projection;

computing a respective complexity with respect to each one of the selected angles;

verifying resultant complexities to determine whether a specific complexity which is greatest in value and in sharpness of peak distribution is present among the complexities thus obtained; and

identifying a corresponding angle at which said specific complexity appears.

15. The tool according to claim 14, wherein said complexity is a function of crossing numbers of a plurality of parallel scanning lines crossing said local region at a selected angle of projection with respect to the black picture elements aligned along said scanning lines.

16. The tool according to claim 15, wherein said complexity is defined by:

space="preserve" listing-type="equation">(1/N)·

Σ

{(Ni-M).sup.2 },

where N is a total number of the scanning lines, Ni is a count value of transitions between said first and second picture elements and M is an average value of a count value of the crossing numbers.

17. The tool according to claim 15, wherein said local region is one of an array of rows and columns of rectangular sections divided from said document image.

18. The tool according to claim 15, wherein said local region is a circular region that is defined at a certain position in said document image.