Merging three optical character recognition outputs for improved precision using a minimum edit distance function

• US 5,459,739 A
• Filed: 03/18/1992
• Issued: 10/17/1995
• Est. Priority Date: 03/18/1992
• Status: Expired due to Fees

• Current Assignee: OCLC Online Computer Library Center Incorporated
• Original Assignee: OCLC Online Computer Library Center Incorporated
• Inventors: Handley, John C., Hickey, Thomas B.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): CHOULES, JACK M
• Application Number:
  US07/853,550
• Time in Patent Office: 1,308 Days
• Field of Search: 395/600, 382/39, 382/57, 382/62, 371/30, 371/67.1, 371/68.1, 371/68.2, 371/68.3, 371/36, 364/225.5, 364/237.6, 364/237.83
• US Class Current: 714/797
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data

Abstract

Three OCR systems are employed for text conversion and the results generated from each of the three are merged using a edit distance algorithm to estimate a correct common text ancestor. To make the process computationally feasible for large strings such as pages of documentation with 3,000 characters, the method is executed in two stages. The first procedure is carried out with each page considered as a string of lines. Where differences exist using the edit distance between the lines on a page to find the optimal alignment of the lines. In the event that choice must be made among three non-null lines, the procedure then is invoked on the three lines , by using the edit distance between the characters on a line to find the optimal alignment. The number of computations required of the procedure is further reduced by comer-cutting that hueristically determines an upper bound on the edit distance and limits calculations to those which do not exceed the upper bound.

Claims

1. A method for determining the content of an ancestral printed text from outputs of text to data conversion devices, each of said pages of printed text being made up of lines of symbols, and each of said outputs representing text symbols within strings-of-lines, said method comprising the steps of:

generating three separate ones of said outputs, A, B, and C, each of said three outputs being derived from a common one of said pages of said printed text, and each of said outputs being generated by an optical character recognition device;

merging said outputs A, B, and C by,

determining edit distances of the strings of lines, each line considered as a single unit, between the outputs A and B, A and C, and B and C,

recovering an optimal alignment between outputs A, B, and C by searching for the minimum edit distance D(A,B,C) by backtracking through the determined edit distances, and

providing a derived output representing said content of said common one of said pages of printed text, the string-of-lines said derived output representing said optimal alignment; and

recording said derived output on a memory medium.

2. The method of claim 1 including the step of computing an upper bound, K, on said edit distances;

and

said merging step is carried out by determining only those edit distances of value below said upper bound, K.

3. The method of claim 2 in which one of a said determined minimum edit distances between corresponding said strings of lines is the value of the minimum number of insertions, deletions, and substitutions transforming one said string to the other.

4. The method of claim 1 in which said merging step includes the step of deriving an edit distance array as a three-dimensional matrix having faces corresponding with paired outputs A and B, A and C, and B and C.

5. The method of claim 4 in which said merging step includes the step of initializing the entries of said edit distance array with a substantially large numerical value.

6. The method of claim 1, where said derived output is stored in a database.

7. The method of claim 1 in which said three outputs A, B, and C are derived from three different optical character recognition devices.

8. A method for determining the content of an ancestral printed text having pages composed of lines of symbols, from the outputs representing text symbols with strings-of-lines of a text to data conversion device comprising the steps of:

generating three of said outputs, A, B, and C, each of said outputs being derived from a common one of said pages of said ancestral printed text and each of said outputs being generated by an optical character recognition device;

computing an upper bound, K, on the edit distances between strings of lines represented within said outputs by deriving bounds, K_AB, K_AC, and K_BC, on each respective pair of said outputs A and B, A and C, and B and C and combining said bounds, K_AB, K_AC, and K_BC to derive said upper bound, K, on the total of the edit distances in correspondence with the expression;

K=min (K_AB +K_BC, K_AC +K_BC, K_AB +K_AC);

then

merging said outputs, A, B, and C by determining only those edit distances of value below said upper bound, K, between the strings of lines represented within outputs A and B, A and C, and B and C, then backtracking through the determined edit distances to recover an optimal alignment exhibiting a minimum edit distance D(A,B,C) to provide a merged output representing said content of said common one of said pages of said ancestral printed text; and

then recording said merged output within the memory medium of a database.

9. A method for determining the content of an ancestral printed text having pages composed of lines of symbols, from the outputs representing text symbols within strings-of-lines of a text to data conversion device comprising the steps of:

generating three of said outputs, A, B, and C, each of said outputs being derived from a common one of said pages of said ancestral printed text and each of said outputs being generated by an optical character recognition device;

normalizing each of said outputs A, B, and C subsequent to said generation thereof by eliminating regions of said outputs not corresponding with said lines of symbols, then,

merging said outputs A, B, and C by determining the edit distances between the strings of lines represented within outputs A and B, A and C, and B and C, then backtracking through the determined edit distances to recover an optimal alignment exhibiting a minimum edit distance D(A,B,C) to provide a merged output representing said content of said common one of said pages of said ancestral printed text; and

then recording said merged output within the memory medium of a database.

10. A method for determining the content of an ancestral printed text having pages composed of lines of symbols, from the outputs representing text symbols within strings-of-lines of a text to data conversion device comprising the steps of:

generating three of said outputs, A, B, and C, each of said outputs being derived from a common one of said pages of said ancestral printed text and each of said outputs being generated by an optical character recognition device;

computing an upper bound, K, on the edit distances between the strings of lines represented within said outputs by;

finding the closest matching of groups of said lines of said common one of said pages by determining traces between said outputs A, B, and C,

enlarging said groups to lengthen runs of said groups of lines,

removing crossings representing traces extending from two lines of one output to one line of another output,

then retracing to determine the number of trace based matches between said groups, and

estimating the minimum edit distance between said strings-of-lines and setting the value of said upper bound, K, in correspondence therewith, then,

merging said outputs A, B, and C by determing only those edit distances of value below said upper bound, K, between strings of lines represented within outputs A and B, A and C, and B and C, then backtracking through the determined edit distances to recover an optimal alignment exhibiting a minimum edit distance D(A,B,C) to provide a merged output representing said content of said common one of said pages of said ancestral printed text; and

then recording said merged output within the memory medium of a database.

11. A method for determining the content of an ancestral printed text having pages composed of lines of symbols, from the outputs representing text symbols within strings-of-lines of a text to data conversion device comprising the steps of:

generating three of said outputs, A, B, and C, each of said outputs being derived from a common one of said pages of said ancestral printed text, and each of said outputs being generated by an optical character recognition device;

computing an upper bound, K, on the edit distances between the strings of lines represented within said outputs by deriving bounds K_AB, K_AC, and K_BC on the strings-of-lines alignment distance for each respective output pair A and B, A and C, and B and C, said upper bound, K, being for the total strings-of-lines edit distance and being derived in correspondence with the expression;

K=min (K_AB +K_BC, K_AC +K_BC, K_AB +K_AC);

merging said outputs, A, B, and C by determining only those edit distances of value below said upper bound, K, between the strings of lines represented within outputs A and B, A and C, and B and C,

deriving an edit distance array as a three-dimensional matrix having faces corresponding with paired outputs A and B, A and C, and B and C,

providing edit distance entries for said array which are derived by determining a lower bound for the cumulative lengths for respective lines, i, j, k of said outputs A, B, and C, and deriving an edit distance entry D(i,j,k) for said array when said lower bound is less than said upper bound, K,

then backtracking through the determined edit distances to recover an optimal alignment exhibiting a minimum edit distance D(A,B,C) to provide a merged output representing said content of said common one of said pages of said ancestral printed text; and

then recording said merged output within a memory medium of a database.

12. The method of claim 11 in which said edit distance entry D(i,j,k) is derived as the minimum of the values, m1, m2, m3, m4, m5, m6, m7, where:

m1=D(i-1,j-1,k-1) plus a weighting factor,

m2=D(i,j-1,k-1) plus a weighting factor,

m3=D(i-1,j,k-1) plus a weighting factor,

m4=D(i-1,j-1,k) plus a weighting factor,

m5=D(i,j,k-1) plus the length of the kth line of output C,

m6=D(i,j-1,k) plus the length of the jth line of output B, and

m7=D(i-1,j,k) plus the length of the ith line of A.

13. The method of claim 11 in which said backtracking includes the comparative steps of:

outputting a minimum weight line (λ

,B_j,C_k) when a given entry D(i,j,k) equals the entry D(i,j-1,k-1) plus a weighting factor;

outputting a minimum weight line (A_i,λ

,C_k) when a given entry D(i,j,k) equals the entry D(i-1,j,k-1) plus a weighting factor;

outputting a minimum weight line A_i,B_j,λ

) when a given entry D(i,j,k) equals the entry D(i-1,j-1,k) plus a weighting factor;

outputting a minimum weight line (λ

,λ

,C_k) when a given entry D(i,j,k) equals the entry D(i,j,k-1) plus the length of the kth line of output C;

outputting a minimum weight line λ

(λ

,B_j,λ

) when a given entry D(i,j,k) equals the entry D(i,j-1,k) plus the length of the jth line of output B; and

outputting a minimum weight line (A_i,λ

,λ

) when a given entry D(i,j,k) equals the entry D(i-1,j,k) plus the length of the ith line of output A;

where λ

, denotes a null line.

14. The method of claim 13 in which said backtracking outputs a common ancestor function Caf (A_i,B_j,C_k) in the absence of an equality at said comparative steps.

15. The method of claim 13 in which said comparative steps are carried out in a descending sequence wherein the initial value of i is equal to the number of lines represented at output A, the initial value of j is equal to the number of lines represented at output B, and the initial value of k is equal to the number of lines represented at output c.

16. A system for generating the content of an ancestral printed text, having pages composed of lines of symbols, from outputs within strings of lines representing text symbols of an optical character recognition device, comprising:

a first optical character recognition device having an output, A, derived from a given page of said ancestral printed text;

a second optical character recognition device having an output, B, derived from said given page of said ancestral printed text;

a third optical character recognition device having an output, C, derived from said given page of said ancestral printed text;

merge processing means responsive to each of said outputs A, B, and C, as said strings-of-lines, for computing an upper bound, K, on the total alignment distance exhibited by said outputs from bounds, K_AB, K_AC, and K_BC on each respective pair of said outputs A and B, A and C, and B and C, said upper bound, K, being derived in correspondence with the expression;

K=min (K_AB +K_BC, K_AC +K_BC, K_AB +K_AC),

for deriving an edit distance array as a three-dimensional matrix having faces corresponding with paired outputs A and B, A and C, and B and C,

for generating edit distance entries for said array by deriving a lower bound value with respect to said outputs and providing an edit distance entry D(i,j,k) for said array corresponding with the ith line of output A, the jth line of output B, and the kth line of output C when said lower bound value is less than said upper bound, K;

for backtracking through said array to recover an optimal alignment of said strings-of-lines exhibiting a minimum edit distance to provide a merged output representing said given page of ancestral printed text; and

memory means for receiving and retaining said merged output as an archival database.

17. The system of claim 16 in which said merge processing means is responsive to each of said outputs A, B, and C to effect the normalization thereof by eliminating outputs representing blank lines and blanks within said lines.

18. The system of claim 16 in which said merge processing means derivation of said edit distance array includes an initialization of the entries thereof with a large numerical value.

19. The system of claim 16 in which said merge processing means edit distance entry D(i,j,k) is generated as the minimum of the values, m1, m2, m3, m4, m5, m6, m7, where:

m1=D(i-1,j-1,k-1) plus a weighting factor,

m2=D(i,j-1,k-1) plus a weighting factor,

m3=D(i-1,j,k-1) plus a weighting factor,

m4=D(i-1,j-1,k) plus a weighting factor,

m5=D(i,j,k-1) plus the length of the kth line of output C,

m6=D(i,j-1,k) plus the length of the jth line of output B, and

m7=D(i-1,j,k) plus the length of the ith line of A.

20. The system of claim 16 in which said merge processing means lower bound value is a function of line indices i, j, and k.

21. The system of claim 20 in which said merge processing means lower bound value corresponds with the cumulative lengths for respective lines i, j, k of said outputs A, B, and C.