Post-processing system and method for correcting machine recognized text

• US 20040086179A1
• Filed: 11/04/2002
• Published: 05/06/2004
• Est. Priority Date: 11/04/2002
• Status: Active Grant

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Ma, Yue, Li, Mu, Guo, Jinhong Katherine, Yao, Tian-shun, Tong, Yu-kun, Zhu, Jing-bo
• Granted Patent: US 7,092,567 B2
• Time in Patent Office: Days
• US Class Current: 382/177
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/268 Lexical context

Abstract

A method of post-processing character data from an optical character recognition (OCR) engine and apparatus to perform the method. This exemplary method includes segmenting the character data into a set of initial words. The set of initial words is word level processed to determine at least one candidate word corresponding to each initial word. The set of initial words is segmented into a set of sentences. Each sentence in the set of sentences includes a plurality of initial words and candidate words corresponding to the initial words. A sentence is selected from the set of sentences. The selected sentence is word disambiguity processed to determine a plurality of final words. A final word is selected from the at least one candidate word corresponding to a matching initial word. The plurality of final words is then assembled as post-processed OCR data.

Claims

1. A post-processor for character data of an optical character recognition (OCR) engine comprising:

a word segmentation engine coupled to the OCR engine to segment the character data into a plurality of initial words;

a word level processor coupled to the word segmentation engine to process the plurality of initial words and determine a set of candidate words corresponding to each initial word;

a sentence segmentation engine coupled to the word level processor to segment the plurality of initial words into at least one sentence; and

a word disambiguity processor coupled to the sentence segmentation engine to determine a final word from each set of candidate words;

wherein the word disambiguity processor processes each sentence of the at least one sentence separately.

2. The post-processor of claim 1, wherein the word level processor includes:

a word selector coupled to the word segmentation engine to select initial words for processing;

a word arbitrator coupled to the word selector to compare the selected initial words to a dictionary word list and to determine a set of candidate words for each selected initial word found in the dictionary word list;

an error type arbitrator coupled to the word checking and unknown word arbitrator to determine an error type of each selected initial word not found in the dictionary word list; and

at least one match engine coupled to the error type arbitrator to determine a set of candidate words for the selected initial words not found in the dictionary word list;

wherein one match engine of at least one match engine is chosen to process a selected initial word based on the error type of the selected initial word determined by the error type arbitrator.

3. The post-processor of claim 2, wherein the at least one match engine includes at least one of:

a capital word error match engine;

a digital word error match engine;

a word segmentation error match engine;

a pattern transformation match engine;

an edit distance match engine; and

an OCR output based match engine.

4. The post-processor of claim 1, wherein the word disambiguity processor includes:

a sentence selector coupled to the sentence segmentation engine to select the one sentence of the at least one sentence at a time for processing; and

at least one linguistic method processor coupled to the sentence selector to determine the final word from each set of candidate words of the selected sentence.

5. The post-processor of claim 4, wherein the at least one linguistic method processor includes at least one of:

a pattern rule processor;

a chunk method processor;

a word-type tri-gram processor;

a word tri-gram processor; and

a priority based method processor.

6. A method of post-processing character data from an optical character recognition (OCR) engine, comprising the steps of:

a) segmenting the character data into a set of initial words;

b) word level processing the set of initial words and determining at least one candidate word corresponding to each initial word;

c) segmenting the set of initial words into a set of sentences, each sentence in the set of sentences including a plurality of initial words and candidate words corresponding to the initial words;

d) selecting, from the set of sentences, a sentence;

e) word disambiguity processing the sentence selected in step (d) to determine a plurality of final words, wherein a final word is selected from the at least one candidate word corresponding to a matching initial word; and

f) assembling the plurality of final words as post-processed OCR data.

7. The method of claim 6, wherein step (b) further includes the steps of:

b1) selecting one initial word;

b2) comparing the selected initial word to a set of dictionary words;

b3) determining the at least one candidate word corresponding to the selected initial word to be the selected initial word when the selected initial word matches a dictionary word;

b4) determining an error type, from a set of error types, corresponding to the selected initial word when the selected initial word does not match a dictionary word; and

b5) determining the at least one candidate word corresponding to the selected initial word based on the error type determined in step (b4) and the set of dictionary words when the selected initial word does not match a dictionary word.

8. The method of claim 7, wherein:

the set of error types include capitalization error, digital error, word segmentation error, pattern error, common word error; and

step (b5) includes the steps of;

correcting capitalization errors of the selected initial word and determining the corrected word to be the at least one candidate word corresponding to the selected initial word when the error type determined in step (b4) is a capitalization error;

correcting digital errors of the selected initial word and determining the corrected word to be the at least one candidate word corresponding to the selected initial word when the error type determined in step (b4) is a digital error;

correcting word segmentation errors of the selected initial word and determining the corrected word to be the at least one candidate word corresponding to the selected initial word when the error type determined in step (b4) is a word segmentation error;

transforming the selected initial word based on predetermined transformation patterns of the OCR engine and determining the transformed word to be the at least one candidate word corresponding to the selected initial word when the error type determined in step (b4) is a pattern error;

transforming at least one character datum of the selected initial word to determine the at least one candidate word corresponding to the selected initial word, calculating an transformation cost based on the at least one character datum transformation for each determined candidate word, and ordering the determined candidate words in ascending calculated transformation cost order when the error type determined in step (b4) is a common word error.

9. The method of claim 8, wherein the transformation cost of a candidate word includes:

edit distance to transform the at least one character datum;

number of same character data in the selected initial word and candidate word; and

a predetermined frequency of the candidate word.

10. A computer readable medium adapted to instruct a general purpose computer to post-process character data from an optical character recognition (OCR) engine, the method comprising the steps of:

a) segmenting the character data into a set of initial words;

b) word level processing the set of initial words and determining at least one candidate word corresponding to each initial word;

c) segmenting the set of initial words into a set of sentences, each sentence including a plurality of initial words and candidate words corresponding to the initial words;

d) selecting, from the set of sentences, a sentence;

e) word disambiguity processing the sentence selected in step (d) to determine a plurality of final words, wherein a final word is selected from the at least one candidate word corresponding to a matching initial word; and

f) assembling the plurality of final words as post-processed OCR data.

11. The computer readable medium of claim 10, wherein step (e) of the method includes the step of:

e1) determining a final word to be the at least one candidate word corresponding to a matching initial word when there is exactly one corresponding candidate word.

12. The computer readable medium of claim 11, wherein step (e) of the method further includes the steps of:

e2) skipping to step (f) if each initial word of the plurality of initial words of the selected sentence has a matching final word;

e3) comparing selected candidate words to a set of forward pattern words;

e4) determining a first candidate word of the at least one candidate word corresponding to a forward patterned initial word to be the matching final word of the forward patterned initial word, the forward patterned initial word being directly following an initial word of the selected sentence matching one of the set of forward pattern words;

e5) comparing selected candidate words to a set of backward pattern words; and

e6) determining a first candidate word of the at least one candidate word corresponding to a backward patterned initial word to be the matching final word of the backward patterned initial word, the backward patterned initial word being directly before an initial word of the selected sentence matching one of the set of backward pattern words.

13. The computer readable medium of claim 12, wherein:

the at least one candidate word corresponding to each initial word determined in step (b) of the method are ordered; and

step (e) of the method further includes the steps of;

e7) skipping to step (f) if each initial word of the plurality of initial words of the selected sentence has a matching final word;

e8) determining the matching final word to be the first candidate word corresponding to each initial word of the sentence for which a matching final word is not determined.

14. The computer readable medium of claim 11, wherein step (e) of the method further includes the steps of:

e2) skipping to step (f) if each initial word of the plurality of initial words of the selected sentence has a matching final word;

e3) selecting a chunk of initial words of the selected sentence, the chunk including;

a predetermined number of consecutive initial words, at least one of the included initial words not having a matching final word;

the final word matching an initial word of the chunk when the final word is determined; and

the at least one candidate word corresponding to an initial word of the chunk when a matching final word is not determined;

e4) creating a set of candidate chunks from combinations of the matching final words and corresponding candidate words included in the selected chunk;

e5) comparing each candidate chunk to a set of predetermined chunks; and

e6) choosing a candidate chunk matching one chunk of the set of predetermined chunks as a final chunk;

e7) determining each final word matching each initial word of the selected chunk to be the corresponding word of the final chunk when there is exactly one final chunk;

e8) repeating (e3), (e4), (e5), (e6), and (e7) until all chunks of the sentence are selected.

15. The computer readable medium of claim 14, wherein:

the at least one candidate word corresponding to each initial word determined in step (b) of the method are ordered; and

step (e) of the method further includes the steps of;

e9) skipping to step (f) if each initial word of the plurality of initial words of the selected sentence has a matching final word;

e10) determining the matching final word to be the first candidate word corresponding to each initial word of the sentence for which a matching final word is not determined.

16. The computer readable medium of claim 11, wherein step (e) of the method further includes the steps of:

e2) skipping to step (f) if each initial word of the plurality of initial words of the selected sentence has a matching final word;

e3) determining a part of speech (POS) for each determined final word of the sentence;

e4) determining a POS for each candidate word of each initial word of the sentence for which a matching final word is not determined;

e5) creating a set of candidate sentence diagrams from combinations of the determined POS'"'"'s corresponding to each initial word of the selected sentence;

e6) creating a complete set of POS N-grams of the determined POS'"'"'s for each candidate sentence diagram;

e7) providing a POS occurrence rate for each POS N-gram;

e8) calculating a POS cost for each candidate sentence diagram, the POS cost of a candidate sentence diagram equaling the product of POS occurrence rates of each POS N-gram of the complete set of POS N-grams of the candidate sentence diagram;

e9) selecting a final sentence diagram having a highest POS cost when one candidate sentence diagram has a POS cost higher than the other candidate sentence diagrams; and

e10) creating a final sentence by replacing each POS in the final sentence diagram with the word from which the POS was determined when one candidate sentence diagram has a POS cost higher than the other candidate sentence diagrams;

e11) determining each final word of the sentence to be the word of the final sentence matching each initial word when one candidate sentence diagram has a POS cost higher than the other candidate sentence diagrams.

17. The computer readable medium of claim 16, wherein:

the at least one candidate word corresponding to each initial word determined in step (b) of the method are ordered; and

step (e) of the method further includes the steps of;

e12) skipping to step (f) if each initial word of the plurality of initial words of the selected sentence has a matching final word;

e13) determining the matching final word to be the first candidate word corresponding to each initial word of the sentence for which a matching final word is not determined.

18. The computer readable medium of claim 16, wherein N equals three.

19. The computer readable medium of claim 11, wherein step (e) of the method further includes the steps of:

e2) skipping to step (f) if each initial word of the plurality of initial words of the selected sentence has a matching final word;

e3) creating a set of candidate sentences from combinations of the determined final words of the selected sentence and the at least one candidate word corresponding to each initial word of the selected sentence not having the matching final word;

e4) creating a complete set of word N-grams for each candidate sentence;

e5) providing a word occurrence rate for each word N-gram;

e6) calculating a word cost for each candidate sentence, the word cost of a candidate sentence equaling the product of word occurrence rates of each word N-gram of the complete set of word N-grams of the candidate sentence;

e7) selecting a final sentence having a highest word cost when at least one candidate sentence has a word cost higher than other ones of the candidate sentences; and

e8) determining each final word of the sentence to be the word of the final sentence matching each initial word when one candidate sentence has a word cost higher than the other candidate sentences.

20. The computer readable medium of claim 19, wherein:

the at least one candidate word corresponding to each initial word determined in step (b) of the method are ordered; and

step (e) of the method further includes the steps of;

e9) skipping to step (f) if each initial word of the plurality of initial words of the selected sentence has a matching final word;

e10) determining the matching final word to be the first candidate word corresponding to each initial word of the sentence for which a matching final word is not determined.

21. The computer readable medium of claim 19, wherein N equals three.