Text line bounding system

• US 4,558,461 A
• Filed: 06/17/1983
• Issued: 12/10/1985
• Est. Priority Date: 06/17/1983
• Status: Expired due to Term

• Current Assignee: Litton Systems Incorporated (Northrop Grumman Corporation)
• Original Assignee: Litton Systems Incorporated (Northrop Grumman Corporation)
• Inventors: Schlang, Arthur
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/505,545
• Time in Patent Office: 907 Days
• Field of Search: 382/9, 382/48, 382/46, 382/61, 340/727
• US Class Current: 382/290
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines

Abstract

A text line bounding system for non-mechanically adjusting for skewed text in scanned text. The data from scanned page texts are divided into vertical swaths and all pixels at respective vertical levels within each swath are set black if any one pixel within the swath at the level is black. Intersections and terminations are found and the datum for each line is established after removing extraneous data. The skew angle of the text is then established, following which the text lines are statistically bounded. The actual text data is then rotated according to the orientation established for conventional processing.

Claims

1. In an optical scanning system having an optical scanning head for sequentially scanning horizontally across a document to create pixel oriented data representing text of the document for subsequent comparison searching to determine the alpha-numeric contents of the document, the improvement for automatically compensating for text line skew comprising:

(a) means for dividing the data into equal swaths representing vertical columns on the documents;

(b) means for scanning the data by swath to determine the apparent text line initiations and termination contained therein and for creating a data matrix of initiation/termination pairs by swath;

said data matrix having at least left and right boundaries;

(c) means for sequentially searching the data in the data matrix left and right for each pair in a base vector swath, representative of a predetermined range of apparent text line initiations and terminations, to trace the data indicative of apparent text lines to determine a plurality of points apparently on base lines of respective ones of the apparent text lines of the document;

(d) means for determining the apparent skew angle of the text from the points on the apparent base lines; and

;

(e) means for bounding the data of the apparent text lines for subsequent comparison searching from the found intersection/termination pairs and apparent skew angle determined.

2. The improvement to an optical scanning system of claim 1 wherein said means for sequentially searching the data in the data matrix includes means for addressing vertical rows within each swath and additionally:

means for temporarily connecting the data by swath during intersection/termination determination such that each vertical addressable row in each swath is treated as having all black pixels if any one pixel therein is, in fact, black.

3. The improvement to an optical scanning system of claim 1 wherein:

said scanning means includes means for checking the separation between apparent initiations and terminations and for rejecting apparent pairs which do not meet pre-established separation criteria.

4. The improvement to an optical scanning system of claim 3 wherein:

said scanning and rejecting means is adapted to reject an apparent initiation following an apparent termination unless at least two black pixels in sequence follow at least two white pixels in sequence in the swath being scanned.

5. In an optical scanning system having an optical scanning head for sequentially scanning horizontally across a document to create pixel oriented data representing the text of the document which is subsequently comparison searched to determine the alpha-numeric contents of the document, the method for automatically compensating for text line skew comprising:

(a) dividing the data into equal swaths representing vertical columns on the document said swaths also containing vertically addressable rows;

(b) scanning the data by swath to determine the apparent text line initiations and terminations contained therein and creating a data matrix of initiation/termination pairs by swath;

said data matrix having at least left and right boundaries;

(c) sequentially searching the data in the matrix left and right for each pair in a base vector swath, representative of a predetermined range of apparent text line initiations and terminations, to trace the data indicative of apparent text lines to determine a plurality of points apparently on base lines of respective ones of the apparent text lines of the document;

(d) determining the apparent skew angle of the text from the points on the apparent base lines;

(e) bounding the data of the apparent text lines from the found intersection/termination pairs and apparent skew angle determined; and

(f) using the bounded apparent text line data for the comparison searching.

6. The method of claim 5 and additionally:

temporarily connecting the data by swath during step (b) of intersection/termination determination such that each vertical addressable row in each swath is treated as having all black pixels if any one pixel therein is, in fact, black.

7. An optical scanning system capable of automatically compensating for document text line skewing comprising:

(a) scanning head means for sequentially scanning across the document to develop a data matrix of pixel oriented digital data bits;

(b) logic means for searching said data bits by document column related swaths to determine a plurality of points apparently lying on the document text lines, for determining said text lines'"'"' apparent skew angle from said points, and for determining the left, right, top, and bottom boundaries in said data matrix for respective ones of said text lines from said points and said skew angle, said swaths also containing vertically addressable rows and

(c) means for picking up the data from said data matrix within said boundaries for use in comparing said data bits to known bit configurations and determining the alpha-numeric contents of the document text;

said logic means including means for setting all said pixel oriented digital data bits for each addressable vertical row within each swath to indicate black if any one of said bits initially indicates black.

8. The optical scanning system of claim 7 wherein:

said logic means includes means for determining apparent pairs of initiations and terminations of text lines within said swaths, for checking the separation between said apparent initiations and terminations, and for rejecting apparent pairs which do not meet pre-established separation criteria.

9. The optical scanning system of claim 8 wherein:

said logic means is adapted to reject an apparent initiation following an apparent termination unless at least two black pixels in sequence follow at least two white pixels in sequence in the swath being scanned.

10. An optical scanning system capable of automatically compensating for document text line skewing comprising:

scanning head means for sequentially scanning across the document to develop a data matrix of pixel oriented digital data bits;

logic means for searching said data bits by document column related swaths to determine a plurality of points apparently lying on the document text lines, for determining said text lines'"'"' apparent skew angle from said points, and for determining the left, right, top, and bottom boundaries in said data matrix for respective ones of said text lines from said points and said skew angle, said swaths also containing vertically addressable rows; and

means for picking up the data from said data matrix within said boundaries for use in comparing said data bits to known bit configurations and determining the alpha-numeric contents of the document text;

said logic means including storage means and counter means and further including logic to accomplish the steps of;

(a) dividing the data into swaths;

(b) filling in partial swath strips such that all pixels for each addressable vertical row within each swath are treated as black if any one of the bits is initially black;

(c) initializing the storage means and counter means;

(d) starting at swath #1;

(e) starting at the bottom of the swath;

(f) setting the condition "looking for intersection";

(g) checking to see if an edge has been found and if it has, going to step (l);

(h) moving up the data in the swath;

(i) checking to see if the end of the swath has been reached and if it has not, going back to step (g);

(j) checking to see if the last swath has been done and if it has, terminating this portion of the logic;

(k) proceeding to the next swath and returning to step (e);

(l) checking to see if the edge is an intersection and if not, going to step (p);

(m) checking to see if the "looking for intersection" condition is set and if not, going back to step (h);

(n) saving the vertical address of the intersection by swath number;

(o) setting the "looking for termination" condition and going back to step (h);

(p) checking to see if the "looking for termination" condition is set and if not returning to step (h);

(q) checking to see if the termination edge found is within the allowed distance limitations of the matching intersection and if it is, proceeding to step (s);

(r) discarding both the intersection and termination addresses and proceeding back to step (h);

(s) bumping the pair count by one for this swath;

(t) saving the vertical address of the termination by swath number; and

,

(u) setting the "looking for intersection" condition and proceeding back to step (h).

11. The optical scanning system of claim 10 wherein such logic means includes a text line counter and a hits counter and additionally includes logic following step (j) thereof when the last swath is done to accomplish the additional steps of:

(a) finding the rightmost swath with the maximum number of pairs;

(b) setting that swath as the base vector;

(c) starting at the bottom of the base vector swath;

(d) clearing the text line counter;

(e) clearing the hits counter;

(f) picking up the next intersection in the swath;

(g) saving it in a line array;

(h) designating it as "VB";

(i) setting a left search condition;

(j) going to step (aa);

(k) setting a right search condition;

(l) going to step (aa);

(m) checking to see if there were too few hits and if there were, proceeding the step (p);

(n) processing and saving the data presently in the line array;

(o) bumping the text line count by one;

(p) checking to see if the processing of the base vector is finished and going to step (r) if it is;

(q) clearing the line array and going back to step (e);

(r) checking to see if there were too few text lines determined to be in the document and terminating the logic in an error state if there were;

(s) determining the skew angle of the text by a linear regression analysis of the data and terminating this portion of the logic;

(aa) accessing the text swath to the left or right as requested;

(ab) starting at the bottom of the swath;

(ac) picking up the next intersection in the swath;

(ad) checking to see if no intersection was found and if none was found, going to step (ao);

(ae) checking to see if the intersection found was within ten vertical lines of VB and if it was, going to step (ag);

(af) checking to see if processing of this swath is finished and going to step (al) if it is and back to step (ac) if it is not;

(ag) resetting the bad swath'"'"'s count;

(ah) saving the intersection in the line array;

(ai) bumping the hits count;

(aj) checking to see if there are presently over 100 hits and going to step (ao) if there are;

(ak) designating this intersection as the new VB and going to step (am);

(al) bumping the bad swaths count by one;

(am) checking to see if swath #1 or swath #79 has been finished and going to step (ao) if it has;

(an) checking to see if the bad swaths count is equal to 4 and going to step (aa) if it is not; and

,

(ao) returning to step (k) if a left search was just accomplished and to step (m) if a right search was just accomplished.

12. The optical scanning system of claim 11 wherein said logic means includes a histogram buffer and additionally includes logic following step(s) thereof to accomplish the additional steps of:

(a) starting at the first swath;

(b) de-skewing the intersection data for this swath by using the skew angle calculated in the logic previously;

(c) checking to see if the last swath has been processed and if it has, going to step (e);

(d) going to the next swath and returning to step (b);

(e) starting at the first swath;

(f) starting at the bottom of the swath;

(g) picking up the next intersection address;

(h) adding one to this address'"'"'s counter in the histogram buffer;

(i) checking to see if that was the last address in the swath and returning to step (g) if it was not;

(j) checking to see if the last swath has been processed and going to step (l) if it has;

(k) going to the next swath and returning to step (f);

(l) finding the datums in the histogram; and

,

(m) establishing the top, bottom, left, and right boundaries for the apparent text lines with respect to the datums.