WORD RECOGNITION OF TEXT UNDERGOING AN OCR PROCESS

• US 20110268360A1
• Filed: 05/03/2010
• Published: 11/03/2011
• Est. Priority Date: 05/03/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Antonijevic, Aleksandar, Nijemcevic, Djordje, Cimpoi, Mircea, Mitic, Ivan
• Granted Patent: US 8,401,293 B2
• Time in Patent Office: Days
• US Class Current: 382/177
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/153 using recognition of characters or words

Abstract

A method for identifying words in a textual image undergoing optical character recognition includes receiving a bitmap of an input image which includes textual lines that have been segmented by a plurality of chop lines. The chop lines are each associated with a confidence level reflecting a degree to which the respective chop line properly segments the textual line into individual characters. One or more words are identified in one of the textual lines based at least in part on the textual lines and a first subset of the plurality of chop lines which have a chop line confidence level above a first threshold value. If the first word is not associated with a sufficiently high word confidence level, at least a second word in the textual line is identified based at least in part on a second subset of the plurality of chop lines which have a confidence level above a second threshold value lower than the first threshold value.

Claims

1. A method for identifying words in a textual image undergoing an OCR process, comprising:

(a) receiving a bitmap of an input image that includes textual lines that have been segmented by chop lines to define symbols therebetween, wherein each of the chop lines is associated with a chop line confidence level reflecting a degree to which the respective chop line properly segments the textual line into individual characters;

(b) maintaining a data structure that stores data elements including the bitmap, the chop lines with their respective chop line confidence levels and the symbols;

(c) producing a first set of candidate characters with character confidence levels associated therewith from a first subset of the data elements in the data structure, the first subset of data elements having respective candidate confidence levels that each exceed a respective one of a first set of data element threshold values;

(d) updating the data structure by further including the first set of candidate characters with their respective character confidence levels;

(e) identifying at least a first word from the first set of candidate characters, wherein the first word has a first word confidence level associated therewith;

(f) wherein if the first word confidence level is below a first word threshold level, updating the data structure to further include the first word and its first word confidence level and

(g) repeating steps (c)-(e) for a second subset of the data elements in the updated data structure having respective data element confidence levels that each exceed a respective one of a second set of data element threshold values lower than the first set of data element threshold values to thereby produce at least a second word and a second word confidence level associated therewith.

2. The method of claim 1 further comprising repeating steps (c)-(f) for subsequent subsets of data elements in the data structure until a subsequent word with a subsequent word confidence level is produced such that the subsequent word confidence level exceeds a word threshold value that depends in part on a number of times steps (c)-(f) have been repeated.

3. The method of claim 2 wherein each subsequent subset of data elements has a data element threshold value associated therewith that is lower than a data element threshold value associated with any previous subset of data elements.

4. The method of claim 1 further comprising repeating steps (c)-(f) for subsequent subsets of data elements in the data structure until the number of times steps (c)-(f) have been repeated reaches a predetermined maximum number of times.

5. The method of claim 1 wherein producing the first set of candidate characters with candidate confidence levels associated therewith from the first subset of data elements is performed using a first character recognition algorithm and further comprising producing a second set of candidate characters with candidate confidence levels associated therewith from the second subset of data elements using a second character recognition algorithm different from the first character recognition algorithm.

6. The method of claim 5 wherein the first character recognition algorithm is an algorithm that is faster and less accurate than the second character recognition algorithm.

7. The method of claim 1 further comprising identifying the first word using a first word search algorithm and identifying the second word using a second word search algorithm that is different from the first word search algorithm.

8. The method of claim 7 wherein the first word search algorithm is an algorithm that is faster and less accurate than the second word search recognition algorithm.

9. The method of claim 1 further comprising selecting a subset of data elements, wherein selecting the subset of data elements includes selecting pairs of chop lines having additional chop lines located therebetween for which a sum of the respective chop line confidence levels associated with the additional chop lines is less than a predetermined threshold value.

10. The method of claim 9 wherein the predetermined threshold value changes when steps (c)-(e) are repeated.

11. A system for identifying words in a textual image undergoing an OCR process, comprising:

an input component for receiving a bitmap of an input image that includes text lines that have been segmented by chop lines to define symbols therebetween, wherein a confidence level reflecting chop line accuracy is associated with each chop line;

a data structure for storing data elements that include the bitmap, the chop lines with their respective chop line confidence levels and the symbols;

a character recognition component for producing a first set of candidate characters with confidence levels associated therewith from a first subset of the data elements in the data structure having respective confidence levels that each exceed a respective one of a first set of data element threshold values, wherein the character recognition component is configured to cause the data structure to be updated by further including in the data structure the first set of candidate characters with their respective character confidence levels; and

a word search component for identifying at least a first word from the first set of candidate characters, wherein the first word has a first word confidence level associated therewith, wherein, the word recognition component is configured to cause the data structure to be updated to further include the first word and its first word confidence level if the first word confidence level is below a first word threshold level, wherein the character recognition component and the word search component are further configured to produce a second set of candidate characters and at least a second word, respectively, from data elements in the updated data structure which have respective confidence levels that each exceed a respective one of a second set of data element threshold values less than the first set of data element threshold values.

12. The system of claim 11 wherein the character recognition component is configured to produce the first set of candidate characters using a first character recognition algorithm and the second set of candidate characters using a second character recognition algorithm different from the first character recognition algorithm.

13. The system of claim 12 wherein the first character recognition algorithm is an algorithm that is faster and less accurate than the second character recognition algorithm.

14. The system of claim 11 wherein the word search component is configured to identify the first word using a first word search algorithm and identifying the second word using a second word search algorithm that is different from the first word search algorithm.

15. A medium comprising instructions executable by a computing system, wherein the instructions configure the computing system to perform a method for identifying words in a textual image undergoing optical character recognition, comprising:

receiving a bitmap of an input image that includes textual lines that have been segmented by a plurality of chop lines that are each associated with a confidence level reflecting a degree to which the respective chop line properly segments the textual line into individual characters;

identifying at least a first word in one of the textual lines based at least in part on the textual lines and a first subset of the plurality of chop lines which have a chop line confidence level above a first threshold value; and

if the first word is not associated with a sufficiently high word confidence level, identifying at least a second word in the one textual line based at least in part on a second subset of the plurality of chop lines which have a confidence level above a second threshold value lower than the first threshold value.

16. The medium of claim 15 further comprising producing a first set of candidate characters each associated with a respective one of a first set of candidate confidence levels, wherein the first set of candidate characters is produced from the textual lines and the first subset of the plurality of chop lines.

17. The medium of claim 16 wherein identifying at least the first word includes identifying the first word additionally based at least in part on the first set of candidate characters.

18. The medium of claim 16 wherein, if the first word is not associated with the sufficiently high confidence level, producing a second set of candidate characters each associated with a respective one of a second set of candidate confidence levels, wherein the second set of candidate characters is produced from the textual lines and the second subset of the plurality of chop lines.

19. The medium of claim 18 wherein identifying at least the second word includes identifying the second word additionally based at least in part on the second set of candidate characters.

20. The medium of claim 18 wherein each of the second candidate confidence levels is less than a candidate confidence threshold associated with each of the first set of candidate confidence levels.