Multiple hypothesis testing for word detection

• US 9,152,871 B2
• Filed: 05/02/2014
• Issued: 10/06/2015
• Est. Priority Date: 09/02/2013
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Soundararajan, Rajiv, Baheti, Pawan Kumar, Barman, Kishor Kumar
• Primary Examiner(s): Harandi, Siamak
• Application Number:
  US14/268,904
• Publication Number:
  US 20150063700A1
• Time in Patent Office: 522 Days
• US Class Current: 1/1
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/153 using recognition of characters or words
• CPC Class Codes: G06V 30/224 of printed characters having additional code marks or containing code marks
• CPC Class Codes: G06V 30/2445 Alphabet recognition, e.g. Latin, Kanji or Katakana
• CPC Class Codes: G06V 30/268 Lexical context

Abstract

Embodiments disclosed pertain to Optical Character Recognition using Multiple Hypothesis Testing based techniques on images occurring in a variety of settings, including images captured by mobile stations. In some embodiments, a set of bifurcation points for a character cluster in an image may be determined. The character cluster may comprise non-uniformly spaced text or closely spaced text. A plurality of hypotheses may be determined for the character cluster, where each hypothesis is based on a subset of the bifurcation points and comprises a set of words generated from the character cluster. A plurality of scores corresponding to the plurality of hypotheses may be determined, where each score corresponds to a hypothesis, and a hypothesis may be selected from among the plurality of hypotheses based on a score associated with the selected hypothesis.

Claims

1. A processor implemented method for determining words in a character sequence output during Optical Character Recognition (OCR), the method comprising:

determining a set of one or more bifurcation points for the character sequence, wherein each bifurcation point identifies a location to split the character sequence into two or more words and wherein the one or more bifurcation points are determined based on a separation between adjacent characters in the character sequence;

generating a plurality of hypotheses, each hypothesis comprising one or more words formed by the character sequence, at least one of the hypotheses being generated based on the one or more bifurcation points;

computing a plurality of normalized scores, each normalized score corresponding to a hypothesis, wherein the normalized score for a corresponding hypothesis is based, in part, on a length of each word in a set of the one or more words associated with the corresponding hypothesis; and

selecting a hypothesis from the plurality of hypotheses based on a corresponding normalized score associated with the selected hypothesis.

2. The method of claim 1, wherein computing a normalized score in the plurality of normalized scores comprises:

determining, for each word in the set of the one or more words associated with the corresponding hypothesis, a corresponding word likelihood; and

computing the normalized score for the corresponding hypothesis based, in part, on the word likelihoods of the words in the set of the one or more words associated with the corresponding hypothesis.

3. The method of claim 2, wherein determining the word likelihood associated with each word in the set of the one or more words associated with the corresponding hypothesis comprises:

obtaining a character likelihood for each character in a word in the set of the one or more words; and

determining a likelihood for the word based, in part, on character likelihoods corresponding to characters in the word.

4. The method of claim 3, wherein the method is performed by a text processing module comprising a character detection module coupled to a word decoding module, wherein:

the character detection module outputs the character sequence and the character likelihood for each character in the character sequence; and

the word decoding module obtains, from the character detection module, the character likelihood corresponding to each character in the word and determines the word likelihood for the word.

5. The method of claim 2, wherein determining the word likelihood associated with each word in the set of the one or more words associated with a hypothesis comprises:

associating, with each word in the set of the one or more words, a corresponding measure of proximity relative to words in a dictionary; and

determining a likelihood for each word in the set of the one or more words based, in part, on the corresponding measure of proximity.

6. The method of claim 5, wherein a Levenshtein distance relative to words in the dictionary is used as the measure of proximity corresponding to each word in the set of the one or more words.

7. The method of claim 1, wherein determining the set of one or more bifurcation points for the character sequence comprises:

determining a plurality of inter-character separations, each inter-character separation corresponding to a distance between a pair of adjacent characters in the character sequence; and

selecting, as the one or more bifurcation points, inter-character separations in the plurality of inter-character separations that exceed a first threshold separation.

8. The method of claim 7, wherein the first threshold separation is dynamically configurable.

9. The method of claim 1, further comprising:

displaying the selected hypothesis, when a confidence interval associated with the selected hypothesis exceeds a confidence interval threshold.

10. The method of claim 9, further comprising:

determining, for each hypothesis, a corresponding set of inter-character separations between a pair of characters adjoining each bifurcation point;

displaying an alternate hypothesis, wherein the alternate hypothesis is selected based on a comparison of inter-character separations in the corresponding set of inter-character separations with a second threshold separation.

11. An apparatus comprising:

a processor configured to;

determine a set of one or more bifurcation points for a character sequence output during Optical Character Recognition (OCR), wherein each bifurcation point identifies a location to split the character sequence into two or more words and wherein the one or more bifurcation points are determined based on a separation between adjacent characters in the character sequence;

generate a plurality of hypotheses comprising one or more words formed by the character sequence, at least one of the hypotheses being generated based on the one or more bifurcation points

compute a plurality of normalized scores, each normalized score corresponding to a hypothesis, wherein the normalized score for a corresponding hypothesis is based, in part, on a length of each word in the set of the one or more words associated with the corresponding hypothesis; and

select a hypothesis from the plurality of hypotheses based on a corresponding normalized score associated with the selected hypothesis.

12. The apparatus of claim 11, wherein to compute a normalized score in the plurality of normalized scores, the processor is configured to:

determine, for each word in the set of the one or more words associated with the corresponding hypothesis, a corresponding word likelihood; and

compute the normalized score for the corresponding hypothesis based, in part, on the word likelihoods of the words in the set of the one or more words associated with the corresponding hypothesis.

13. The apparatus of claim 12, wherein to determine the word likelihood associated with each word in the set of the one or more words associated with the corresponding hypothesis, the processor is configured to:

obtain a character likelihood for each character in a word in the set of the one or more words; and

determine a likelihood for the word based, in part, on character likelihoods corresponding to characters in the word.

14. The apparatus of claim 13, wherein the processor comprises:

a text processing module comprising a character detection module coupled to a word decoding module, wherein;

the character detection module is configured to output the character sequence and the character likelihood for each character in the character sequence; and

the word decoding module is configured to obtain the character likelihood corresponding to each character in the word and determine the word likelihood for the word.

15. The apparatus of claim 12, wherein to determine the word likelihood associated with each word in the set of the one or more words associated with a hypothesis, the processor is configured to:

associate, with each word in the set of the one or more words, a corresponding measure of proximity, the measure of proximity being determined relative to words in a dictionary; and

determine a likelihood for each word in the set of the one or more words based, in part, on the corresponding measure of proximity.

16. The apparatus of claim 15, wherein a Levenshtein distance relative to words in the dictionary is used as the measure of proximity corresponding to each word in the set of the one or more words.

17. The apparatus of claim 11, wherein to determine the set of the one or more bifurcation points for the character sequence, the processor is configured to:

determine a plurality of inter-character separations, each inter-character separation corresponding to a distance between a pair of adjacent characters in the character sequence; and

select, as the one or more bifurcation points, inter-character separations in the plurality of inter-character separations that exceed a first threshold separation.

18. The apparatus of claim 17, wherein the processor is configured to dynamically configure the first threshold separation.

19. The apparatus of claim 11, wherein the processor is further configured to:

initiate the display of the selected hypothesis, when a confidence interval associated with the selected hypothesis exceeds a confidence interval threshold;

determine, for each hypothesis, a corresponding set of inter-character separations between a pair of characters adjoining each bifurcation point; and

initiate the display of an alternate hypothesis, wherein the processor is configured to select the alternate hypothesis based on a comparison of inter-character separations in the corresponding set of inter-character separations with a second threshold separation.

20. An apparatus comprising:

processing means, the processing means further comprising;

means for determining a set of one or more bifurcation points for a character sequence output from Optical Character Recognition (OCR), wherein each bifurcation point identifies a location to split the character sequence into two or more words and wherein the one or more bifurcation points are determined based on a separation between adjacent characters in the character sequence;

generating a plurality of hypotheses comprising one or more words formed by the character sequence, at least one of the hypotheses being generated based on the one or more bifurcation points

means for computing a plurality of normalized scores, each normalized score corresponding to a hypothesis, wherein the normalized score for a corresponding hypothesis is based, in part, on the length of each word in the set of the one or more words associated with the corresponding hypothesis; and

means for selecting a hypothesis from the plurality of hypotheses based on a corresponding normalized score associated with the selected hypothesis.