Apparatus and method of fusing the outputs of multiple intelligent character recognition (ICR) systems to reduce error rate

• US 5,970,171 A
• Filed: 08/14/1995
• Issued: 10/19/1999
• Est. Priority Date: 08/14/1995
• Status: Expired due to Term

• Current Assignee: OL Security LLC (Intellectual Ventures LLC)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Baraghimian, Gregory A., Host, Glenn E.
• Primary Examiner(s): COUSO, YON JUNG
• Assistant Examiner(s): Nguyen, Ha Tran
• Application Number:
  US08/515,088
• Time in Patent Office: 1,527 Days
• Field of Search: 382/229, 382/224, 382/225, 382/226, 382/227, 382/160, 382/209, 382/215, 382/309, 382/310, 382/161, 382/101, 395/3, 395/20
• US Class Current: 382/187
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data

Abstract

An ICR fuser includes a set of fusion rules for combining the outputs of multiple ICR systems. Each ICR system operates on a digital image to extract image component strings and provide a set of multiple candidate character strings and their associated confidence values. Each rule includes a test for determining whether that rule applies to the current ICR system outputs, a membership function for selecting a fused character string, and a confidence equation for assigning it a fused confidence value. The rules partition a decision space into subspaces to reduce the error rate between the fused character string and the image component string.

Claims

1. A method of fusing outputs from at least two intelligent character recognition (ICR) systems that operate on image component strings said ICR outputs including sets of candidate character strings having associated confidence values, the permutations of said outputs defining a decision space, the method comprising:

generating a set of rules that partition said decision space into a plurality of subspaces, each of said rules including a test for determining whether said ICR rules including a test for determining whether said ICR outputs lie within its subspace, a membership function for selecting a fused character string from the sets of candidate character strings, and a confidence equation for computing a fused confidence value wherein said set of rules is generated to reduce an average error rate between said fused character string and said image component strings, and further wherein generating the set of rules comprises;

(a) selecting a first one of the rules for said set;

(b) applying said rule to known training data to produce said fused character strings and their confidence values;

(c) comparing said fused character strings to the known training data to determine the average error rate;

(d) adjusting the rule'"'"'s confidence equation to reduce said average error rate; and

(e) selecting the next one of the rules from said set until the set is exhausted and repeating steps b through e;

in response to successive outputs from said ICR systems, performing said tests until one is satisfied to select the applicable rule;

executing the membership function for the applicable rule to select the fused character string;

computing the confidence equation for the applicable rule to assign the fused confidence value; and

outputting said fused character string and its confidence value.

2. The method of claim 1, wherein said rules are tested in a specified order to achieve the desired subspace partitioning.

3. The method of claim 1, wherein each of said membership functions select the candidate character string having the highest confidence value that satisfies the associated test.

4. The method of claim 1, wherein said confidence equations boost the fused confidence value relative to the selected candidate character string'"'"'s confidence value in subspaces in which the fused character string matches the image component string with a high probability and reduce the fused confidence value relative to the selected candidate character string'"'"'s confidence value in subspace in which the fused character string matches the image component string with a low probability.

5. The method of claim 1, wherein said fused confidence value is initially set equal to the confidence value of the selected candidate character string, said confidence equations are adjusted by:

modifying the confidence equation to boost the fused confidence value relative to the selected candidate character string'"'"'s confidence value;

repeating steps b and c to determine a boosted average error rate;

modifying the confidence equation to reduce the fused confidence value relative to the selected candidate character string'"'"'s confidence value;

repeating steps b and c to determine a reduced average error rate; and

selecting the modified confidence equation having the lower of the boosted and reduced average error rates.

6. The method of claim 1, wherein comparing the fused character strings to the known training data generates an error rate versus field rejection rate curve where the average error rate is proportional to the area under said curve, said confidence equations being adjusted to reduce said area.

7. A method of recognizing character strings in digital images, comprising:

providing a digital image of a text document, wherein said text document is a standardized form on which multiple text strings from known data bases are printed in known positions on the form, said ICR systems extracting said text strings as successive ones of said image component strings;

providing a plurality of intelligent character recognition (ICR) systems that segment the digital image into image component strings and from them generate respective sets of candidate character strings having associated confidence values where the permutations of said candidate character strings define a decision space wherein said ICR systems detect individual characters from respective subsets of the ASCII character set to generate the respective sets of candidate character strings and wherein three of said ICR systems detect individual characters from subsets of the ASCII character set including only upper case alpha characters, only lower case alpha characters and mixed upper and lower case alpha characters, respectively, and output their respective sets of candidate character strings in a common case;

generating a set of rules that partition said decision space into a plurality of subspaces to reduce an average recognition error rate, each of said ordered rules including a test for determining whether said candidate character strings lie within its subspace, a membership function for selecting a fused character string from the sets of candidate character strings, and a confidence equation for computing a fused confidence value and wherein a first one of said rules includes a test that selects the first rule when one and only one string appears in all three sets, a membership function that selects that one string as the fused character string, and a confidence equation that first selects the maximum confidence value from the three sets and then increases it and wherein a second one of said rules includes a test that selects the second rule when one and only one string appears in the upper and mixed case sets and the lower case set is empty or when one and only one string appears in the lower and mixed case sets and the upper case set is empty, a membership function that selects that one string as the fused character string, and a confidence equation that first selects the maximum confidence value from the sets and then increases it;

in response to successive sets of candidate character strings, performing said tests until one is satisfied to select the applicable rule;

executing the membership function for the applicable rule to select the fused character string;

computing the equation for the applicable rule to assign the fused confidence value; and

when said fused confidence value exceeds a threshold, transmitting said fused character string to a data base,

otherwise rejecting said fused character string and accepting a user generated string for transmission to said data base.

8. The method of claim 7, wherein a third one of said rules includes a test that selects the third rule when all of the candidate character strings have associated confidence value less than a threshold value, a membership function that selects the candidate character sign having the highest confidence value as the fused character string, and a confidence equation that reduces the highest confidence value as a function of the total number of recognized candidate character strings.

9. The method of claim 8, wherein a fourth one of said rules includes a test that selects the fourth rule when only one of the three sets includes a candidate character string, a membership function that selects that one candidate character string as the fused character string, and a confidence equation that reduces the selected string'"'"'s confidence value to provide the fused confidence value.

10. The method of claim 9, wherein a fifth one of said rules includes a test that selects the fifth rule when at least one of the upper and mixed case sets and the lower and mixed case sets share a common candidate character string, a membership function that selects the common candidate character string having the high confidence value as the fused character string, and a confidence equation that increases the selected common candidate character string'"'"'s confidence value to provide the fused confidence value.

11. The method of claim 10, wherein a last one of said rules is a default rule that is applied when the first five tests fail, said last rule selecting the candidate character string having the high confidence value as the fused string and assigning its confidence value as the fused confidence value.

12. An intelligent character recognition (ICR) fuser for combining the outputs of a plurality of ICR systems, said ICR outputs including sets of candidate character strings having associated confidence values where the permutations of said ICR outputs define a decision space, comprising:

a computer programmed with an ordered set of rules that partition said decision space into a plurality of subspaces to reduce an average recognition error rate, each of said rules including a test for determining whether said ICR outputs lie within its subspace, wherein said tests partition said decision space such that the fused character strings selected from a first one of the subspaces have a low error probability and those selected from a second one of the subspaces have a high error probability,

at least one membership function for selecting a fused character string from the sets of candidate text strings, wherein each of said membership functions select the candidate character string having the highest confidence value that satisfies the associated test; and

at least two confidence equations for computing a fused confidence value, wherein the confidence equation associated with said first subspace boost the fused confidence value relative to the selected candidate character string'"'"'s confidence value, and the confidence equation associated with second subspace reduces the fused confidence value relative to the selected candidate character string'"'"'s confidence value.

13. A character recognition system, comprising:

an input storage medium for storing a digital image of a text document wherein said text document is a standardized form on which multiple text document is a standardized form on which multiple text strings from known data bases are printed in known positions on the form, said ICR systems extracting said text strings as successive ones of said image component strings;

a plurality of intelligent character recognition (ICR) systems that segment said digital image to extract successive image component strings and convert them into sets of candidate character strings having associated confidence values where the permutations of said candidate strings define a decision space and wherein said ICR systems detect individual characters from respective subsets of the ASCII character set to generate the respective sets of candidate character strings and wherein three of said ICRs detect individual characters from subsets of the ASCII character set including only upper case alpha characters, only lower case alpha characters and mixed upper and lower case alpha characters, respectively, and output their respective sets of candidate character strings in a common case;

a computer programmed with an ordered set of rules that partition said decision space into a plurality of subspaces to reduce an average recognition error rate, each of said ordered rules including a test for determining whether said sets of candidate character strings lie with its subspace, a membership function for selecting a fused character string from those sets, and a confidence equation for computing a fused confidence value, wherein a first one of said rules includes a test that selects the first rule when one and only one string appears in all three sets, a membership function that selects that one string s the fused character string, and a confidence equation that first selects the maximum confidence value from the three sets and then increases it wherein a second one of said rules includes a test that selects the second rule when one and only one string appears in the upper and mixed case sets and the lower case set is empty or when one and only one string appears in the lower and mixed case sets and the upper case set is empty, a membership function that selects that one string as the fused character string, and a confidence equation that first selects the maximum confidence value from the sets and then increases it;

a manual input device for replacing said fused character string with a user generated string when said fused confidence value is less than a threshold value; and

an output storage medium for storing said fused strings and said user generated strings.

14. The character recognition system of claim 13, wherein a third one of said rules includes a test that selects the third rule when all of the candidate character strings have associated confidence values less than a threshold value, a membership function that selects the candidate character string having the highest confidence value as the fused character string, and a confidence equation that reduces the highest confidence value as a function of the total number of recognized candidate character strings.

15. The character recognition system of claim 14, wherein a fourth one of said rules includes a test that selects the fourth rule when only one of the three sets includes a candidate character string, a membership function that selects that one candidate character string as the fused character string, and a confidence equation that reduces the selected string'"'"'s confidence value to provide the fused confidence value.

16. The character recognition system of claim 15, wherein a fifth one of said rules includes a test that selects the fifth rule when at least one of the upper and mixed case sets and the lower and mixed case sets share a common candidate character string, a membership function that selects the common candidate character string having the high confidence value as the fused character string, and a confidence equation that increases the selected common candidate character string'"'"'s confidence value to provide the fused confidence value.

17. The character recognition system of claim 16, wherein a last one of said rules is a default rule that is applied when the first five tests fail, said last rule selecting the candidate character string having the high confidence value as the fused string and assigning its confidence value as the fused confidence value.