Confusion matrix based method and system for correcting misrecognized words appearing in documents generated by an optical character recognition technique

• US 6,154,579 A
• Filed: 08/11/1997
• Issued: 11/28/2000
• Est. Priority Date: 08/11/1997
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Goldberg, Randy G.
• Primary Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/909,199
• Time in Patent Office: 1,205 Days
• Field of Search: 382/229, 382/231, 382/225, 382/189, 382/228, 382/187, 382/198, 382/310, 382/321, 704/1, 704/9, 704/10, 707/533
• US Class Current: 382/310
• 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
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

A method and apparatus for correcting misrecognized words appearing in electronic documents that have been generated by scanning an original document in accordance with an optical character recognition ("OCR") technique. If an incorrect word is found in the electronic document, the present invention generates at least one reference word and selects the reference word that is the most likely correct replacement for the incorrect word. This selection is accomplished by performing a probabilistic determination that assigns to each reference word a replacement word recognition probability. The probabilistic determination is carried out on the basis of a pre-stored confusion matrix that stores a plurality of probability values. The confusion matrix is used to associate each character of recognized word in the electronic document with a corresponding character of a word in the original document on the basis of these probability values.

Claims

1. A method of recognizing at least one word in a document, the word including at least one predetermined character, the method comprising the steps of:

a) providing a recognized word based on the word in the document;

b) determining whether the recognized word is correct;

c) generating, if the recognized word is incorrect, at least one reference word, each reference word comprising a different set of predetermined characters and being generated according to a process that is independent of a content of at least one confusion matrix;

d) determining for each reference word a corresponding replacement word value based on a calculation involving a mathematical function being applied to a content of the at least one confusion matrix; and

e) replacing the incorrect recognized word with the reference word most likely matching the at least one word in the document based on the corresponding replacement word value.

2. The method according to claim 1, wherein each one of the at least one word in the document, the recognized word, and each reference word comprises at least one alphanumeric character.

3. The method according to claim 1, wherein each one of the at least one word in the document, the recognized word, and each reference word comprises at least one number.

4. The method according to claim 1, wherein each one of the at least one word in the document, the recognized word, and each reference word comprises at least one alphabetical letter.

5. The method according to claim 1, wherein each one of the at least one word in the document, the recognized word, and each reference word comprises at least one typographic character.

6. The method according to claim 1, wherein:

the step b) comprises determining whether the recognized word is spelled correctly,

the at least one confusion matrix includes a plurality of character values, and

the step d) comprises, if the recognized word is spelled incorrectly;

i) obtaining, for each character sequence in each one of the at least one reference word, a character value representing a likelihood that the character sequence of the at least one reference word is recognized as the corresponding character sequence in the incorrectly spelled recognized word, wherein each of the character sequence of the at least one reference word and the character sequence of the incorrectly spelled recognized word comprises at least one character position, respectively,

ii) establishing a reference word recognition value based on the obtained character values, and

iii) repeating steps i) and ii) for each reference word, each reference word being associated with a corresponding reference word recognition value, each replacement word value comprising a corresponding reference word recognition value.

7. The method according to claim 6, wherein each of the obtained character values is a probability.

8. The method according to claim 6, wherein each reference word recognition value is established by multiplying the character values obtained for the corresponding reference word.

9. The method according to claim 1, wherein each one of the at least one confusion matrix corresponds to a different font.

10. The method of claim 1, wherein the at least one word in the document comprises a printed word appearing on a physical document.

11. The method of claim 1, wherein the at least one word in the document comprises a handwritten word appearing on a physical document.

12. The method according to claim 1, wherein the recognized word is provided by an optical character recognition technique.

13. The method according to claim 1, wherein the reference word selected in step e) to replace the incorrect recognized word corresponds to the highest replacement word value determined in step d).

14. The method according to claim 1, wherein:

the at least one confusion matrix includes a plurality of character values, and

the step d) comprises, if the recognized word is incorrect;

i) obtaining, for each character sequence in the at least one reference word, a character value representing a likelihood that the character sequence of the at least one reference word is recognized as the corresponding character sequence in the incorrect recognized word, wherein each of the character sequence of the at least one reference word and the character sequence of the incorrect recognized word comprises at least one character position,

ii) establishing a reference word recognition value based on the obtained character values,

iii) generating a plurality of grammar values based on the incorrect recognized word, each grammar value corresponding to a different part of speech,

iv) determining for the reference word a composite value based on the corresponding reference word recognition value and on one of the plurality of grammar values corresponding to the part of speech of the reference word, and

v) repeating steps i)-iv) for each reference word, each reference word being associated with a corresponding composite value, and each replacement word value comprising a corresponding composite value.

15. The method according to claim 14, wherein the step b) comprises:

vi) determining whether the recognized word is incorrectly spelled by determining whether the recognized word is found in a prestored dictionary maintained in memory, and

vii) determining, if the recognized word is correctly spelled, whether the recognized word is grammatically correct.

16. The method according to claim 15, wherein the step b) further comprises determining, if the recognized word is spelled correctly and is grammatically correct, whether the recognized word is contextually correct.

17. The method according to claim 1, further comprising the steps of:

providing a plurality of word correction modules, each word correction module being associated with a different confusion matrix;

selecting one of the plurality of word correction modules; and

performing at least step d) in accordance with the confusion matrix associated with the selected word correction module.

18. A method of recognizing at least one word in a document, the word including at least one predetermined character, the method comprising the steps of:

a) providing a recognized word based on the word in the document;

b) determining whether the recognized word is correct;

c) providing, if the recognized word is incorrect, at least one reference word, each reference word comprising a different set of predetermined characters;

d) determining for each reference word a corresponding replacement word value based on a calculation derived from a content of at least one confusion matrix; and

e) replacing the incorrect recognized word with the reference word most likely matching the at least one word in the document based on the corresponding replacement word value, wherein;

the at least one confusion matrix includes a plurality of character values the step d) comprises, if the recognized word is incorrect;

i) obtaining for each character sequence in the at least one reference word, a character value representing a likelihood that the character sequence of the at least one reference word is recognized as the corresponding character sequence in the incorrect recognized word, wherein each of the character sequence of the at least one reference word and the character sequence of the incorrect recognized word comprises at least one character position,

ii) establishing a reference word recognition value based on the obtained character values,

iii) generating a plurality of grammar values based on the incorrect recognized word, each grammar value corresponding to a different part of speech,

iv) determining for the reference word a composite value based on the corresponding reference word recognition value and on one of the plurality of grammar values corresponding to the part of speech of the reference word, and

v) repeating steps i)-iv) for each reference word, each reference word being associated with a corresponding composite value, and each replacement word value comprising a corresponding composite value, each reference word recognition value is established by multiplying the character values obtained for the corresponding reference word, and each composite value is determined by multiplying each reference word recognition value with one of the plurality of grammar values corresponding to the part of speech of the associated reference word.

19. A method of recognizing at least one word in a document, the word including at least one predetermined character, the method comprising the steps of:

a) providing a recognized word based on the word in the document,

b) determining whether the recognized word is correct,

c) providing, if the recognized word is incorrect, at least one reference word, each reference word comprising a different set of predetermined characters,

d) determining for each reference word a corresponding replacement word value based on a calculation derived from a content of at least one confusion matrix; and

e) replacing the incorrect recognized word with the reference word most likely matching the at least one word in the document based on the corresponding replacement word value, wherein before the step e), the method further comprises the step of determining whether any of the at least one reference word is associated with a replacement word value higher than a predetermined threshold, and wherein the reference word used to replace the incorrect recognized word in step e) is associated with a replacement word value that is higher than the predetermined threshold.

20. An apparatus for recognizing at least one word in a document, the word including at least one predetermined character, the apparatus comprising:

means for providing a recognized word based on the word in the document;

first determining means for determining whether the recognized word is correct;

means for generating if the recognized word is incorrect, at least one reference word, each reference word comprising a different set of predetermined characters and being generated according to a process that is independent of a content of at least one confusion matrix;

second determining means for determining for each reference word a corresponding replacement word value based on a calculation involving a mathematical function being applied to a content of the at least one confusion matrix; and

means for replacing the incorrect recognized word with the reference word most likely matching the at least one word in the document based on the corresponding replacement word value.

21. The apparatus according to claim 20, wherein:

the first determining means comprises means for determining whether the recognized word is spelled correctly,

the at least one confusion matrix includes a plurality of character values and

the second determining means comprises;

means for obtaining, for each character sequence in each one of the at least one reference word, a character value representing a likelihood that the character sequence of the at least one reference word is recognized as the corresponding character sequence in the incorrectly spelled recognized word, wherein each of the character sequence of the at least one reference word and the character sequence of the incorrectly spelled recognized word comprises at least one character position, respectively, and

means for establishing a reference word recognition value based on the obtained character values.

22. The apparatus according to claim 21, further comprising a memory for arranging the obtained character values as the at least one confusion matrix.

23. The apparatus according to claim 20, wherein:

the at least one confusion matrix includes a plurality of character values and

the second determining means comprises;

means for obtaining, for each character sequence in the at least one reference word, a character value representing a likelihood that the character sequence of the at least one reference word is recognized as the corresponding character sequence in the incorrect recognized word, wherein each of the character sequence of the at least one reference word and the character sequence of the incorrect recognized word comprises at least one character position,

means for establishing a reference word recognition value based on the obtained character values,

means for generating a plurality of grammar values based on the incorrect recognized word, each grammar value corresponding to a different part of speech, and

means for determining for the reference word a composite value based on the corresponding reference word recognition value and on one of the plurality of grammar values corresponding to the part of speech of the reference word.

24. The apparatus according to claim 23, wherein the first determining means comprises:

means for determining whether the recognized word is incorrectly spelled by determining whether the recognized word is found in a pre-stored dictionary maintained in memory, and

means for determining whether the recognized word is grammatically correct.

25. The apparatus according to claim 24, wherein the first determining means for further comprises determining whether the recognized word is contextually correct.

26. The apparatus according to claim 20, further comprising:

means for providing a plurality of word correction modules, each word correction module being associated with a different confusion matrix;

means for selecting one of the plurality of word correction modules; and

means for causing the second determining means to determine each replacement word value in accordance with the confusion matrix associated with the selected word correction module.

27. An apparatus for recognizing at least one word in a document, the word including at least one predetermined character, the apparatus comprising:

a scanning device for providing a recognized word based on the word in the document; and

a processing device in communication with the scanning device, wherein the processing device comprises;

a central processing unit,

an optical character recognition module in communication with the control processing unit,

a confusion matrix memory in communication with the central processing unit,

a word checking module in communication with the central processing unit and for generating a reference word according to a process that is independent of a content of the confusion matrix memory, and

a word correction module in communication with the central processing unit, wherein, if the central processing unit operating in accordance with the word checking module determines that the recognized word is incorrect, the central processing unit, operating in accordance with the word correction module and a content of the confusion matrix memory, replaces the recognized with a reference word associated with a replacement word value generated in accordance with a calculation involving a mathematical function being applied to the content of the confusion matrix memory.

28. The apparatus according to claim 27, wherein the word checking module comprises at least one of a spell checking module, a grammar checking module, and a natural language module.

29. The apparatus according to claim 28, wherein the processing device further comprises:

a data input device in communication with the central processing unit; and

a display device in communication with the central processing unit.

30. An apparatus for recognizing at least one word in a document, the word including at least one predetermined character the apparatus comprising:

a scanning device for providing a recognized word based on the word in the document; and

a processing device in communication with the scanning device, wherein the processing device comprises;

a central processing unit,

an optical character recognition module in communication with the control processing unit,

a confusion matrix memory in communication with the central processing unit,

a word checking module in communication with the central processing unit,

a word correction module in communication with the central processing unit,

a data input device in communication with the central processing unit, and

a display device in communication with the central processing unit, wherein;

if the central processing unit operating in accordance with the word checking module determines that the recognized word is incorrect, the central processing unit, operating in accordance with the word correction module and a content of the confusion matrix memory replaces the recognized with a reference word associated with a replacement word value generated in accordance with the content of the confusion matrix memory,

the word checking module comprises at least one of a spell checking module, a grammar checking module, and a natural language module,

the confusion matrix memory stores a plurality of confusion matrices,

the data input device includes a selecting device for selecting one of the plurality of confusion matrices, and

the reference word is generated in accordance with the selected confusion matrix.

31. A method of recognizing at least one word in an original document, the word including at least one predetermined character, the method comprising the steps of:

a) providing a first displayable electronic document including at least a recognized word based on the word in the original document;

b) applying a word error detection application to the first displayable electronic document to determine whether the recognized word is correct; and

c) if the recognized word is incorrect, performing the steps of;

d) providing at least one reference word, each reference word comprising a different set of predetermined characters,

e) determining for each reference word a corresponding replacement word value, and

f) providing a second displayable electronic document in which the incorrect recognized word is replaced with the reference word most likely matching the at least one word in the original document based on the corresponding replacement word value.

32. An apparatus for recognizing at least one word in an original document, the word including at least one predetermined character, the apparatus comprising:

means for providing a first displayable electronic document including at least a recognized word based on the word in the original document;

means for applying a word error detection application to the first displayable electronic document to determine whether the recognized word is correct;

means for providing, if the recognized word is incorrect, at least one reference word, each reference word comprising a different set of predetermined characters;

second determining means for determining, if the recognized word is incorrect, for each reference word a corresponding replacement word value; and

means for providing, if the recognized word is incorrect, a second displayable electronic document in which the incorrect recognized word is replaced with the reference word most likely matching the at least one word in the original document based on the corresponding replacement word value.

33. An apparatus for recognizing at least one word in an original document, the word including at least one predetermined character, the apparatus comprising:

a scanning device for producing at least a first displayable electronic document including at least a recognized word based on the word in the original document; and

a processing device in communication with the scanning device, wherein the processing device comprises;

a central processing unit,

an optical character recognition module in communication with the control processing unit,

a confusion matrix memory in communication with the central processing unit,

a word checking module in communication with the central processing unit, and

a word correction module in communication with the central processing unit, wherein, if the central processing unit operating in accordance with the word checking module determines that the recognized word in the first displayable electronic document is incorrect, the central processing unit, operating in accordance with the word correction module and a content of the confusion matrix memory, causes the scanning device to produce a second displayable electronic document in which the incorrect recognized word is replaced with a reference word generated in accordance with the content of the confusion matrix memory.