Line alignment apparatus and process

• US 5,434,932 A
• Filed: 07/28/1994
• Issued: 07/18/1995
• Est. Priority Date: 07/28/1994
• Status: Expired due to Term

• Current Assignee: Thomson Reuters Enterprise Centre GmbH (The Woodbridge Co. Ltd.)
• Original Assignee: West Publishing Corporation (The Woodbridge Co. Ltd.)
• Inventors: Scott, Donald D.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/281,825
• Time in Patent Office: 355 Days
• Field of Search: 382/57, 382/38, 382/40, 382/62
• US Class Current: 382/309
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06V 10/98 Detection or correction of errors, e.g. by rescanning the pattern or by human intervention; Evaluation of the quality of the acquired patterns

Abstract

A computer implemented process of matching two lines of text produced by optical character readers analyzes words in the two lines to identify matching words in corresponding positions in the two lines. Lines are then identified as matching based on the number of matching words in corresponding positions.

Claims

1. A computer-implemented process of comparing a line of text produced by reading a digital image of a document by a first reader to a line of text produced by reading a digital image of the same document by a second reader, each of the lines of text having a plurality of words, the process comprising:

identifying the positions of words in the line of text produced by the first reader and in the line of text produced by the second reader;

analyzing the words in the line of text produced by the first reader and in the line of text produced by the second reader to identify matching words in corresponding positions in the lines of text produced by the first and second readers; and

outputting the line of text produced by the first reader to a first line-aligned file and output the line of text produced by the second reader to a second line-aligned file if the number of matching words in corresponding positions exceeds a predetermined threshold.

2. The process of claim 1 wherein the step of identifying is performed by forming a truth table having a first axis representing words of a selected line of text in a first raw text file and a second axis representing words of a selected line of text in a second raw text file, and the step of analyzing is performed by inserting entries on the table indicating that individual words along the first axis match individual words along the second axis.

3. The process of claim 2 including;

establishing the threshold based on the number of words along at least one of the axes; and

identifying a diagonal of the truth table having a number of entries indicating matches that exceeds the threshold.

4. The process of claim 3 wherein the threshold is established by counting the number of words along the first and second axes and selecting a threshold as a predetermined fraction of the number of words along the axis having the most words.

5. The process of claim 3 wherein the step of identifying a diagonal comprises:

determining whether the number of words along the first and second axes are equal;

if the number of words along the first and second axes are equal so that the truth table forms a single prime diagonal, determining whether the number of entries indicating matches in the prime diagonal exceeds the threshold; and

if the number of words along the first and second axes are unequal so that the truth table forms plural prime diagonals, selecting a first prime diagonal having an initial position containing the first word of the line of text produced by the first reader and the first word of the line of text produced by the second reader and determining whether the number of entries indicating matches in the first prime diagonal exceeds the threshold.

6. The process of claim 5 wherein if the number of words along the first and second axes are unequal so that the truth table forms plural prime diagonals and the first prime diagonal does not contain a number of entries indicating matches exceeding the threshold, selecting a second prime diagonal having a last position containing the last word of the line of text produced by the first reader and the last word of the line of text produced by the second reader, and determining whether the number of entries indicating matches in the second prime diagonal exceeds the threshold.

7. The process of claim 2 wherein forming the truth table comprises converting each word of the lines of text produced by the first and second readers into a corresponding token that represents the respective word in the truth table.

8. The process of claim 7 wherein each token comprises first and second values.

9. The process of claim 8 wherein the first value is based on the difference between the ASCII values of a first and a last character of the respective word and the second value is based on the sum of ASCII values of all characters of the respective word.

10. The process of claim 2 including:

establishing the threshold based on the number of words along at least one of the axes; and

identifying a diagonal of the truth table having a number of entries indicating matches that exceeds the threshold.

11. The process of claim 1 wherein a digital image of the document is read by at least three readers to produce corresponding raw text files, the process producing at least three line-aligned files, each line-aligned file corresponding to a raw text file, the process further including:

identifying a line of matching text appearing in a majority of raw text files and not in all raw text files; and

copying an identified line of text from one of the majority of raw text files into those line-aligned files corresponding to raw text files that did not contain the identified line of text.

12. A computer-implemented process of comparing a line of text produced by reading a digital image of a document by a first reader to a line of text produced by reading a digital image of the same document by a second reader, each of the lines of text having a plurality of words, the process comprising:

forming a truth table having a first axis representing words of the line of text produced by the first reader, a second axis representing words of the line of text produced by the second reader, and entries indicating that individual words along the first axis match individual words along the second axis;

establishing a threshold;

identifying a diagonal of the truth table;

calculating a matching proportion for the diagonal by dividing the number of entries along the diagonal by the number of words along an axis;

comparing the matching proportion to the threshold; and

outputting the lines of text to separate line-aligned files if the matching proportion exceeds the threshold.

13. The process of claim 12 wherein the matching proportion is calculated by dividing the number of entries along the diagonal by the number of words along the axis containing the greater number of words.

14. The process of claim 12 wherein a digital image of the document is read by at least three readers to produce corresponding raw text files, the process producing at least three line-aligned files, each line-aligned file corresponding to a raw text file, the process further including:

identifying a line of matching text appearing in a majority of raw text files and not in all raw text files; and

copying an identified line of text from one of the majority of raw text files into those line-aligned files corresponding to raw text files that did not contain the identified line of text.

15. A computer-implemented process of forming a computer-readable file of text comprising:

reading a digital image of a document by each of a plurality of readers to produce a corresponding plurality of raw text files, each raw text file containing lines of text;

line-aligning at least one raw text file to at least one other raw text file to produce a corresponding plurality of line-aligned files, wherein line-aligning comprises;

identifying the positions of words in the lines of text contained in the raw text files being line-aligned;

analyzing the words in the lines of text contained in the raw text files being line-aligned to identify matching words in corresponding positions;

identifying matching lines of text based on the number of matching words in corresponding positions; and

producing a plurality of line-aligned files containing the matching lines of text produced by the plurality of readers;

character-aligning the line-aligned files to produce a corresponding plurality of line-aligned, character-aligned files;

comparing the characters of the plurality of line-aligned, character-aligned files; and

selecting a probable character from the plurality of line-aligned, character-aligned files for each character position in the computer-readable file of text.

16. The process of claim 15 wherein the step of identifying the positions of words in the lines of text is performed by forming a truth table having a first axis representing words of a selected line of text in a first raw text file and a second axis representing words of a selected line of text in a second raw text file, and the step of analyzing is performed by inserting entries indicating that individual words along the first axis match individual words along the second axis.

17. The process of claim 16 wherein the step of matching comprises:

establishing a threshold based on the number of words along at least one of the axes; and

identifying a diagonal of the truth table having a number of matches that exceeds the threshold.

18. The process of claim 17 wherein the threshold is established by counting the number of words along the first and second axes and selecting a threshold as a predetermined fraction of the number of words along the axis having the most words.

19. The process of claim 17 wherein the step of identifying a diagonal comprises:

determining whether the number of words along the first and second axes are equal;

if the number of words along the first and second axes are equal so that the truth table forms a single prime diagonal, determining whether the number of entries indicating matches in the prime diagonal exceeds the threshold; and

if the number of words along the first and second axes are unequal so that the truth table forms plural prime diagonals, selecting a first prime diagonal having an initial position containing the first word of the selected line of text in the second raw text file, and determining whether the number of entries indicating matches in the first prime diagonal exceeds the threshold.

20. The process of claim 19 wherein if the number of words along the first and second axes are unequal so that the truth table forms plural prime diagonals and the first prime diagonal does not contain a number of entries indicating matches exceeding the threshold, selecting a second prime diagonal having a last position containing the last word of the selected line of text in the first raw text file and the last word of the selected line of text in the second raw text file, and determining whether the number of entries indicating matches in the second prime diagonal exceeds the threshold.

21. The process of claim 16 wherein forming the truth table comprises converting each word of each of the selected lines of text in the first and second raw text files into a corresponding token that represents the respective word in the truth table.

22. The process of claim 21 wherein each token comprises first and second integers.

23. The process of claim 22 wherein the first integer is based on the difference between the ASCII values of a first and a last character of the respective word and the second integer is based on the sum of ASCII values of all characters of the respective word.

24. The process of claim 15 wherein a digital image of the document is read by at least three readers to produce corresponding raw text files, the process producing at least three line-aligned files, each file-aligned file corresponding to a raw text file, the process further including:

identifying a line of matching text appearing in a majority of raw text files and not in all raw text files; and

copying an identified line of text from one of the majority of raw text files into those line-aligned files corresponding to raw text files that did not contain the identified line of text.