METHOD AND SYSTEM FOR VERIFICATION OF UNCERTAINLY RECOGNIZED WORDS IN AN OCR SYSTEM

• US 20090067756A1
• Filed: 02/15/2007
• Published: 03/12/2009
• Est. Priority Date: 02/17/2006
• Status: Active Grant

• Current Assignee: Lumex As
• Original Assignee: Lumex As
• Inventors: Meyer, Hans Christian, Fosseide, Knut Tharald, Carlin, Mats Stefan
• Granted Patent: US 8,315,484 B2
• Time in Patent Office: Days
• US Class Current: 382/310
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/12 Detection or correction of errors, e.g. by rescanning the pattern
• CPC Class Codes: G06V 30/268 Lexical context

Abstract

The present invention provides a method and system for confirming uncertainly recognized words as reported by an Optical Character Recognition process by using spelling alternatives as search arguments for an Internet search engine. The measured number of hits for each spelling alternative is used to provide a confirmation measure for the most probable spelling alternative. Whenever the confirmation measure is inconclusive, a plurality of search strategies are used to reach a measured result comprising zero hits except for one spelling alternative that is used as the correct alternative.

Claims

1-57. -57. (canceled)

58. A method for resolving contradicting output data from an Optical Character Recognition (OCR) system, wherein the output data comprises at least one word with at least one uncertainly recognized character, wherein the at least one uncertainly recognized character is reported in the output data together with probable alternatives for the at least one uncertainly recognized character, and the words wherein the at least one uncertainly recognized character has been encountered in an image of a text being processed by the OCR system, the method comprises the steps of:

using an Internet search engine with search arguments established according to a search strategy comprising;

a) providing initial search arguments by forming spelling alternatives for the words comprising the at least one uncertainly recognized character by substituting the at least one uncertainly recognized character with the reported probable alternatives for the at least one character, one by one, and in possible combinations in each encountered word, or by removing a character, thereby forming a plurality of spelling alternatives, and then measuring and recording number of hits for search results of each respective spelling alternative that has been formed in this manner,

b) comparing the measured number of hits for each of the spelling alternatives with an upper predefined relative threshold level and a lower predefined relative threshold level, wherein each of the respective comparisons of the plurality of measurements falls into one of three possible outcomes;

i) if the measurement of a spelling alternative is above the predefined relative upper threshold level, the corresponding spelling alternative for this measurement is the correct spelling alternative for the word, and terminating the Internet search,

ii) if the measurement of a spelling alternative is below the lower predefined relative threshold level, the corresponding spelling alternative for this measurement is deemed non-existing, and the word with this spelling alternative is discarded from further investigations, and continuing with other spelling alternatives that has been formed as search arguments for the Internet search engine,

iii) if the measurement of a spelling alternative falls between the upper relative threshold level and the lower relative threshold level, exiting the Internet search engine and modifying the search strategy providing further search arguments as a combination of members of the remaining spelling alternatives and other words encountered in the document, other character alternatives for the at least one uncertainly recognized character, phrases, adapting the upper relative threshold level, adapting the lower relative threshold level, and/or other information related to the output data from the OCR system, before continuing using the search strategy providing further measurements and comparisons for resolving the contradicting output data,

c) continuing processing step b) a number of predefined times, or until there is only one spelling alternative left, which ever occurs first, providing an iteration amongst a plurality of different search arguments used in the search strategy before terminating step b), and using the remaining spelling alternative having the highest measurement above the upper relative threshold level as the correct spelling alternative.

59. The method according to claim 58, wherein the search strategy comprises substituting the at least one uncertainly recognized character with a combination of at least two characters when forming the spelling alternatives.

60. The method according to claim 58, wherein the search strategy comprises substituting two or more of the at least one uncertainly recognized character with a single character when forming the spelling alternatives.

61. The method according to claim 58, wherein the search strategy comprises identifying if the spelling alternative under investigation is a proper name, and if so identify in the OCR process other recognized words that are proper names, then provide as a spelling alternative a combination of the word under investigation together with at least one other properly recognized proper name.

62. The method according to claim 58, wherein the search strategy comprises using at least one preceding word relative to the word under investigation in combination with the word under investigation as the spelling alternative.

63. The method according to claim 58, wherein the search strategy comprises using at least one succeeding word relative to the word under investigation in combination with the word under investigation as the spelling alternative.

64. The method according to claim 58, wherein the search strategy comprises using at least one preceding word further away relative to the word under investigation in combination with the word under investigation as the spelling alternative.

65. The method according to claim 58, wherein the search strategy comprises using at least one succeeding word further way relative to the word under investigation in combination with the word under investigation as the spelling alternative.

66. The method according to claim 58, wherein the search strategy comprises using at least one preceding word further away relative to the word under investigation which comprises a number of characters above a predefined threshold in combination with the word under investigation as the spelling alternative.

67. The method according to claim 58, wherein the search strategy comprises using at least one succeeding word further away relative to the word under investigation which comprises a number of characters above a predefined threshold in combination with the word under investigation as the spelling alternative.

68. The method according to claim 58, wherein one the search strategy comprises the steps of:

i) obtaining a counting of occurrence of words encountered in the image of the text in the OCR process,

ii) using at least one preceding word further away relative to the word under investigation which has a low number of occurrences under a predefined threshold in combination with the word under investigation as the spelling alternative.

69. The method according to claim 68, wherein the search strategy further comprises in step ii):

using at least one succeeding word further away relative to the word under investigation which has a low number of occurrences under a predefined threshold in combination with the word under investigation as the spelling alternative.

70. The method according to claim 58, wherein the search strategy comprises the steps of:

i) obtaining a counting of occurrence of words encountered in the image of the text in the OCR process,

ii) using at least one preceding word further away relative to the word under investigation which has a high number of occurrences over a first predefined threshold and which comprise a high number of characters in the word above a second threshold in combination with the word under investigation as the spelling alternative.

71. The method according to claim 70, wherein the search strategy further comprises in step ii):

using at least one succeeding word further away relative to the word under investigation which has a high number of occurrences over a first predefined threshold and which comprise a high number of characters in the word above a second threshold in combination with the word under investigation as the spelling alternative.

72. The method according to claim 58, wherein the search strategy comprises the steps of:

i) selecting preceding words further away relative to the word under investigation one by one and listing those preceding words that comprise a number of characters above a predefined threshold,

ii) using the selected words from i) as search arguments in an Internet search engine and identify the word that provides a lowest number of hits different from zero, and use that word in combination with the word under investigation as the spelling alternative.

73. The method according to claim 58, wherein the search strategy comprises the steps of:

i) selecting succeeding words further away relative to the word under investigation one by one and listing those succeeding words that comprise a number of characters above a predefined threshold,

ii) use the selected words listed in i) as a search arguments in an Internet search engine and identify the word that provides a lowest number of hits different from zero, and use that word in combination with the word under investigation as the spelling alternative.

74. The method according to claim 58, wherein the comparison with the upper threshold and the comparison with the lower threshold is based on a renormalization of the thresholds and reported total number of hits.

75. The method according to claim 58, wherein the upper and lower threshold is changed incrementally upwards and downwards cooperatively, and whenever a change of thresholds are performed, initiating a new search and confirmation process.

76. The method according to claim 58, wherein the upper and lower threshold is changed incrementally upwards and downwards independently, and whenever a change of thresholds are performed, initiating a new search and confirmation process.

77. The method according to claim 58, wherein the search strategy comprises the steps of:

selecting leading characters one by one from the word under investigation,

combining these characters in an increasing number of leading characters,

use each of the instances of increasing number of characters as an argument for a dictionary look up, and

if the dictionary returns a true word from the dictionary look up, use this word in combination with the word under investigation as the spelling alternative.

78. The method according to claim 58, wherein the search engine, as an alternative or in addition to performing searches on the Internet, searches in other information sources not accessible via the Internet, but which are accessible via an Intranet, Virtual Private Net, or similar networks, or directly by searching a connected hard disc drive comprising information.

79. The method according to claim 78, wherein a user may select from a list which information sites to be searched during the confirmation process.

80. The method according to claim 58, wherein the upper threshold is defined as

$\mathrm{acceptance}$

( i ) ⇔

# 



hits i ∑

i = 1 n 



# 



hits i ≥

γ



( # 



hits )

wherein i denotes one of the spelling alternatives, #hits_i is the measured number of hits for spelling alternative i, the denominator is the total measured number of hits for all spelling alternatives, and γ

(#hits) is a threshold level that is a function of the number hits.

81. The method according to claim 58, wherein the upper threshold is defined as

$\mathrm{acceptance}$

( i ) ⇔

# 



hits i max 

( # 



hits j ) j ≠

i ≥

γ



( # 



hits )

wherein i denotes one of the spelling alternatives, #hits_i is the measured number of hits for spelling alternative i, max(#hits_j)<sub>j≠

i</sub> is the total measured number of hits for all spelling alternatives not including the spelling alternative for i, and γ

(#hits) is a threshold level that is a function of the number hits.

82. The method according to claim 58, wherein the lower threshold is

$\mathrm{rejection}$

( i ) ⇔

# 



hits i # 



hits i + max 

( # 



hits j ) j ≠

i ≡

rBest 

( i ) ≤

κ



( # 



hits )

wherein # hits_i is the measured number of hits for spelling alternative i, max(#hits_j)<sub>j≠

i</sub> is the total measured number of hits for all spelling alternatives not including the spelling alternative for i, and κ

(#hits) is a threshold level that is a function of the number hits.

83. The method according to claim 58, wherein a merit function is used to define a measurement for the number of hits as:

$\mathrm{totscore}<br><br>\left(i\right)={\mathrm{aCRS}}_{\mathrm{word}}<br><br><br><br>\left(i\right)+b<br><br>\frac{\#<br><br><br><br>{\mathrm{hits}}_i}{{\max <br><br>\left(\#<br><br><br><br>{\mathrm{hits}}_j\right)}_{j\ne <br><br>i}}$

wherein a+b=1, CRS_word(i) is a character score value from the OCR process related to the spelling alternative i, max(#hits_j)<sub>j≠

i</sub> is the total measured number of hits for all spelling alternatives not including the spelling alternative for i.

84. The method according to claim 58, wherein a merit function is used to define a measurement for the number of hits as:

$\mathrm{totscore}<br><br>\left(i\right)=a^{\mathrm{\prime <br><br>}}<br><br>{\mathrm{CRS}}_{\mathrm{word}}<br><br>\left(i\right)+b^{\mathrm{\prime <br><br>}}<br><br>\left(1-\min <br><br>\left({\mathrm{CRS}}_i\right)\right)-c^{\mathrm{\prime <br><br>}}<br><br>\frac{1-\underset{k=1}{\overset{\mathrm{nchar}}{\sum <br><br>}}<br><br><br><br>\mathrm{\Delta <br><br>}<br><br><br><br>{\mathrm{CRS}}_{i,k}}{\mathrm{nchar}}+d^{\mathrm{\prime <br><br>}}<br><br>f<br><br>\left({\mathrm{rBest}<br><br>\left(i\right)}_{\mathrm{phrase}},{\mathrm{rBest}<br><br>\left(i\right)}_{\mathrm{single}<br><br><br><br>\mathrm{word}},{\mathrm{rBest}<br><br>\left(i\right)}_{\mathrm{mult}<br><br><br><br>\mathrm{word}}\right)$

wherein a′

+b′

+c′

+d′

=1, CRS_word(i) is a character score value from the OCR process related to the spelling alternative i, the second term is the minimum CRS for all the characters in the word, the third term is the sum of the CRS difference between the highest CRS for each character and the CRS using word(i), f is a minimum or maximum function of the upper threshold or lower threshold values as defined;

$\mathrm{acceptance}<br><br>\left(i\right)\iff <br><br>\frac{\#<br><br><br><br>{\mathrm{hits}}_i}{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>\#<br><br><br><br>{\mathrm{hits}}_i}\ge <br><br>\mathrm{\gamma <br><br>}<br><br>\left(\#<br><br><br><br>\mathrm{hits}\right)$

wherein i denotes one of the spelling alternatives, #hits_i is the measured number of hits for spelling alternative i, the denominator is the total measured number of hits for all spelling alternatives, and γ

(#hits) is a threshold level that is a function of the number hits; and

nchar is the number of characters in the word i.

85. The method according to claim 58, wherein the OCR system is a speech recognition system, and the at least one uncertainly recognized character is an uncertainly interpretation of a phoneme.

86. A system for resolving contradicting output data from an Optical Character Recognition (OCR) system, wherein the output data comprises at least one word with at least one uncertainly recognized character, wherein the at least one uncertainly recognized character is reported in the output data together with probable alternatives for the at least one uncertainly recognized character, and the words wherein this at least one uncertainly recognized character has been encountered in an image of a text being processed by the OCR system, the system comprises:

a system component using an Internet search engine with search arguments established according to a search strategy comprising;

a) the system component provides initial search arguments by forming spelling alternatives for the words comprising the at least one uncertainly recognized character by substituting the at least one uncertainly recognized character with the reported probable alternatives for the at least one character, one by one, and in possible combinations in each encountered word, or by removing a character, thereby forming a plurality of spelling alternatives, and then measuring and recording number of hits for search results of each respective spelling alternative that has been formed in this manner,

b) the system component compares the measured number of hits for each of the spelling alternatives with an upper predefined relative threshold level and a lower predefined relative threshold level, wherein each of the respective comparisons of the plurality of measurements falls into one of three possible outcomes;

i) if the measurement of a spelling alternative is above the predefined relative upper threshold level, the corresponding spelling alternative for this measurement is the correct spelling alternative for the word, and terminate the Internet search,

ii) if the measurement of a spelling alternative is below the lower predefined relative threshold level, the corresponding spelling alternative for this measurement is deemed non-existing, and the word with this spelling alternative is discarded from further investigations, and continue with other spelling alternatives that has been formed as search arguments for the Internet search engine,

iii) if the measurement of a spelling alternative falls between the upper relative threshold level and the lower relative threshold level, exit the Internet search engine and modify the search strategy providing further search arguments as a combination of members of the remaining spelling alternatives and other words encountered in the document, other character alternatives for the at least one uncertainly recognized character, phrases, adapting the upper relative threshold level, adapting the lower relative threshold level, and/or other information related to the output data from the OCR system, before continuing using the search strategy providing further measurements and comparisons for resolving the contradicting output data,

c) the system component is processing step b) a number of predefined times, or until there is only one spelling alternative left, which ever occurs first, providing an iteration amongst a plurality of different search arguments used in the search strategy before terminating step b), and using the remaining spelling alternative having the highest measurement above the upper relative threshold level as the correct spelling alternative.

87. The system according to claim 86, wherein the system component comprises substituting the at least one uncertainly recognized character with a combination of at least two characters when forming the spelling alternatives.

88. The system according to claim 86, wherein the system component comprises substituting two or more of the at least one uncertainly recognized character with a single character when forming the spelling alternatives.

89. The system according to claim 86, wherein the system component comprises a unit identifying if the spelling alternative under investigation is a proper name, and if so submit a query to the OCR process identifying other recognized words that are proper names, and then combine at least one of the other proper names properly recognized with the proper name under investigation as the spelling alternative.

90. The system according to claim 86, wherein the search system component comprises a unit using at least one preceding word relative to the word under investigation in combination with the word under investigation as the spelling alternative.

91. The system according to claim 86, wherein the system component comprises a unit using at least one succeeding word relative to the word under investigation in combination with the word under investigation as the spelling alternative.

92. The system according to claim 86, wherein the system component comprises a unit using at least one preceding word further away relative to the word under investigation in combination with the word under investigation as the spelling alternative.

93. The system according to claim 86, wherein the system component comprises a unit using at least one succeeding word further way relative to the word under investigation in combination with the word under investigation as the spelling alternative.

94. The system according to claim 86, wherein the system component comprises a unit using at least one preceding word further away relative to the word under investigation which comprise a number of characters above a predefined threshold in combination with the word under investigation as the spelling alternative.

95. The system according to claim 86, wherein the system component comprises a unit using at least one succeeding word further away relative to the word under investigation which comprise a number of characters above a predefined threshold in combination with the word under investigation as the spelling alternative.

96. The system according to claim 86, wherein the system component comprises a unit that:

i) obtains a counting of occurrence of words encountered in the image of the text from the OCR process, and store the occurrence numbers,

ii) selects at least one preceding word further away relative to the word under investigation which has a low occurrence number from i) under a predefined threshold and combine this word with the word under investigation as the spelling alternative.

97. The system according to claim 96, wherein the system component further comprises a unit that:

selects at least one succeeding word further away relative to the word under investigation which has a low occurrence number under a predefined threshold and combines this word with the word under investigation as the spelling alternative.

98. The system according to claim 86, wherein the system component comprises a unit that:

i) obtains a counting of occurrence of words encountered in the image of the text from the OCR process, and store the occurrence numbers,

ii) selects at least one preceding word further away relative to the word under investigation which has a high number of occurrences over a first predefined threshold and which comprise a high number of characters in the word above a second threshold in combination with the word under investigation as the spelling alternative.

99. The system according to claim 98, wherein the system component further comprises a unit that:

selects at least one succeeding word further away relative to the word under investigation which has a high number of occurrences over a first predefined threshold and which comprise a high number of characters in the word above a second threshold in combination with the word under investigation as the spelling alternative.

100. The system according to claim 86, wherein the system component comprises a unit that:

i) selects preceding words further away relative to the word under investigation one by one and store those preceding words that comprise a number of characters above a predefined threshold,

ii) uses the stored words from i) as search arguments in an Internet search engine, identify the word that provides a lowest number of hits different from zero, and use that word in combination with the word under investigation as the spelling alternative.

101. The system according to claim 86, wherein the system component comprises a unit that:

i) selects succeeding words further away relative to the word under investigation one by one and store those preceding words that comprise a number of characters above a predefined threshold,

ii) uses the stored words from i) as search arguments in an Internet search engine, identify the word that provides a lowest number of hits different from zero, and use that word in combination with the word under investigation as the spelling alternative.

102. The system according to claim 86, wherein the function providing comparison with the upper threshold and the comparison with the lower threshold is based on a renormalization of the thresholds and measured total number of hits.

103. The system according to claim 86, wherein the upper and lower threshold is changed incrementally upwards and downwards cooperatively.

104. The system according to claim 86, wherein the upper and lower threshold is changed incrementally upwards and downwards independently.

105. The system according to claim 86, whenever a spelling alternative is inconclusive, the spelling result providing the highest number of relative renormalized hits is selected as the most probable spelling alternative.

106. The system according to claim 86, wherein the system component, as an alternative or in addition to performing searches on the Internet, do searches in other information sources not accessible via the Internet, but which are accessible via an Intranet, VPR, or similar networks, or directly by searching a connected hard disc drive comprising information.

107. The system according to claim 106, wherein a user may select from a list a range of information sites to be searched during the confirmation process by the system component.

108. The system according to claim 86, wherein the upper threshold is defined as

$\mathrm{acceptance}$

( i ) ⇔

# 



hits i max 

( # 



hits j ) j ≠

i ≥

γ



( # 



hits ) ,

wherein i denotes one of the spelling alternatives, #hits_i is the measured number of hits for spelling alternative i, the denominator is the total measured number of hits for all spelling alternatives, and γ

(#hits) is a threshold level that is a function of the number hits.

109. The system according to claim 86, wherein the upper threshold is defined as

$\mathrm{acceptance}$

( i ) ⇔

# 



hits i max 

( # 



hits j ) j ≠

i ≥

γ



( # 



hits )

wherein i denotes one of the spelling alternatives, #hits_i is the measured number of hits for spelling alternative i, max(#hits_j)<sub>j≠

i</sub> is the total measured number of hits for all spelling alternatives not including the spelling alternative for i, and γ

(#hits) is a threshold level that is a function of the number hits.

110. The system according to claim 86, wherein the lower threshold is defined as:

$\mathrm{rejection}<br><br>\left(i\right)\iff <br><br>\frac{\#<br><br><br><br>{\mathrm{hits}}_i}{\#<br><br><br><br>{\mathrm{hits}}_i+{\max <br><br>\left(\#<br><br><br><br>{\mathrm{hits}}_j\right)}_{j\ne <br><br>i}}\equiv <br><br>\mathrm{rBest}<br><br>\left(i\right)\le <br><br>\mathrm{\kappa <br><br>}<br><br>\left(\#<br><br><br><br>\mathrm{hits}\right)$

wherein # hits_i is the measured number of hits for spelling alternative i, max(#hits_j)<sub>j≠

i</sub> is the total measured number of hits for all spelling alternatives not including the spelling alternative for i, and κ

(#hits) is a threshold level that is a function of the number hits.

111. The system according to claim 86, wherein a merit function is used to define a measurement for the number of hits as:

$\mathrm{totscore}<br><br>\left(i\right)={\mathrm{aCRS}}_{\mathrm{word}}<br><br><br><br>\left(i\right)+b<br><br>\frac{\#<br><br><br><br>{\mathrm{hits}}_i}{{\max <br><br>\left(\#<br><br><br><br>{\mathrm{hits}}_j\right)}_{j\ne <br><br>i}}$

wherein a+b=1, CRS_word(i) is a character score value from the OCR process related to the spelling alternative i, max(#hits_j)<sub>j≠

i</sub> is the total measured number of hits for all spelling alternatives not including the spelling alternative for i.

112. The system according to claim 86, wherein a merit function is used to define a measurement for the number of hits as:

$\mathrm{totscore}<br><br>\left(i\right)=a^{\mathrm{\prime <br><br>}}<br><br>{\mathrm{CRS}}_{\mathrm{word}}<br><br>\left(i\right)+b^{\mathrm{\prime <br><br>}}<br><br>\left(1-\min <br><br>\left({\mathrm{CRS}}_i\right)\right)-c^{\mathrm{\prime <br><br>}}<br><br>\frac{1-\underset{k=1}{\overset{\mathrm{nchar}}{\sum <br><br>}}<br><br><br><br>\mathrm{\Delta <br><br>}<br><br><br><br>{\mathrm{CRS}}_{i,k}}{\mathrm{nchar}}+d^{\mathrm{\prime <br><br>}}<br><br>f<br><br>\left({\mathrm{rBest}<br><br>\left(i\right)}_{\mathrm{phrase}},{\mathrm{rBest}<br><br>\left(i\right)}_{\mathrm{single}<br><br><br><br>\mathrm{word}},{\mathrm{rBest}<br><br>\left(i\right)}_{\mathrm{mult}<br><br><br><br>\mathrm{word}}\right)$

wherein a′

+b′

+c′

+d′

=1, CRS_word(i) is a character score value from the OCR process related to the spelling alternative i, the second term is the minimum CRS for all the characters in the word, the third term is the sum of the CRS difference between the highest CRS for each character and the CRS using word(i), f is a minimum or maximum function of the upper threshold or lower threshold values as defined as;

$\mathrm{rejection}<br><br>\left(i\right)\iff <br><br>\frac{\#<br><br><br><br>{\mathrm{hits}}_i}{\#<br><br><br><br>{\mathrm{hits}}_i+{\max <br><br>\left(\#<br><br><br><br>{\mathrm{hits}}_j\right)}_{j\ne <br><br>i}}\equiv <br><br>\mathrm{rBest}<br><br>\left(i\right)\le <br><br>\mathrm{\kappa <br><br>}<br><br>\left(\#<br><br><br><br>\mathrm{hits}\right)$

wherein # hits_i is the measured number of hits for spelling alternative i, max(#hits_j)<sub>j≠

i</sub> is the total measured number of hits for all spelling alternatives not including the spelling alternative for i, and κ

(#hits) is a threshold level that is a function of the number hits; and

nchar is the number of characters in the word i.

113. The system according to claim 86, wherein the OCR system is a speech recognition system, and the at least one uncertainly recognized character is an uncertainly interpretation of a phoneme.