Text recognition using two-dimensional stochastic models

• US 5,787,198 A
• Filed: 10/25/1994
• Issued: 07/28/1998
• Est. Priority Date: 11/24/1992
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Kuo, Shyh-Shiaw, Agazzi, Oscar Ernesto
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): DEL ROSSO, GERARD DOMNICK
• Application Number:
  US08/329,047
• Time in Patent Office: 1,372 Days
• Field of Search: 382/10, 382/20, 382/22, 382/30, 382/36, 382/39
• US Class Current: 382/196
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models

Abstract

Pseudo two-dimensional hidden Markov models (HMMs) are used to represent text elements, such as characters or words. Observation vectors for each text element are based on pixel maps obtained by optical scanning. A character is represented by a pseudo two-dimensional HMM having a number of superstates, with each superstate having at least one state. Text elements are compared with such models by using the Viterbi algorithm, first in connection with the states in each superstate, then the superstates themselves, to calculate the probability that a particular model represents the text element. Parameters for the models are generated by training routines. Probabilities can be adjusted to compensate for changes in scale, translations, slant, and rotation.

An embodiment is also disclosed for identifying keywords in a body of text. A first pseudo two-dimensional HMM is created for the words that may appear in the text. Each word in the text is compared with both models, again using the Viterbi algorithm, to calculate probabilities that the model represents the subject word. If the probability for the keyword is greater than that for the extraneous words, the subject word is identified as being the keyword. Preprocessing steps for reducing the number of words to be compared can be added.

Claims

1. A method of using a computer to spot a keyword in a document, which comprises the steps of:

storing first signals representing a first pseudo two-dimensional hidden Markov model in said computer, said first pseudo two-dimensional hidden Markov model representing said keyword and including a one-dimensional hidden Markov model having at least one superstate associated with a first dimension of said keyword and, for each superstate, a one-dimensional hidden Markov model having at least one state associated with a second dimension of said keyword,

storing second signals representing a second pseudo two-dimensional hidden Markov model in said computer, said second pseudo two-dimensional hidden Markov model representing a plurality of extraneous words, other than said keyword, that may appear in said text and including a one-dimensional hidden Markov model having at least one superstate associated with a first dimension of said plurality of extraneous words and, for each superstate, a one dimensional hidden Markov model having at least one state associated with a second dimension of said plurality of extraneous words,

scanning said document to generate third signals representing a pixel map for each text word in said document, said pixel map having rows and columns of pixels,

for each text word;

responsive to said third signals, comparing the pixel map for said text word with said first pseudo two-dimensional hidden Markov model, by applying the Viterbi algorithm, to generate a first comparison signal indicating a first probability that said first pseudo two-dimensional hidden Markov model represents said text word,

also responsive to said third signals, comparing the pixel map for said text word with said second pseudo two-dimensional hidden Markov model, by applying the Viterbi algorithm, to generate a second comparison signal indicating a second probability that said second pseudo two-dimensional hidden Markov model represents said text word, and

responsive to said first and second comparison signals, generating an output signal identifying said text word as said keyword if said first probability is greater than said second probability.

2. The method of claim 1 wherein the step of creating said first pseudo two-dimensional hidden Markov model comprises the step of:

estimating the parameters for said first pseudo two-dimensional hidden Markov model from a plurality of training tokens representing said keyword by applying the segmental k-means training procedure,

and wherein the step of creating said second pseudo two-dimensional hidden Markov model comprises the step of;

estimating the parameters for said second pseudo two-dimensional hidden Markov model from a plurality of training tokens representing said extraneous words by applying the segmental k-means training procedure.

3. The method of claim 1 wherein said superstates represent substantially horizontal slices through said keyword and each comparing step comprises the steps of:

in a first routine, for each combination of one of said rows in said pixel map and one of said superstates, applying the Viterbi algorithm to determine a best path for said one row through the states in said one superstate and a probability for the final state in said one superstate and

in a second routine, applying the Viterbi algorithm and the probabilities determined in said first routine to determine a best path through all said superstates and a probability for the final superstate.

4. The method of claim 1 which comprises the further steps of:

during the creation of said first pseudo two-dimensional hidden Markov model, establishing keyword shape characteristics,

before said comparing step, prechecking said text word against said keyword shape characteristics, and

eliminating text words not having substantially said keyword shape characteristics.

5. A method of using a computer to identify unknown text elements in a document, which comprises the steps of:

storing first signals representing a plurality of pseudo two-dimensional hidden Markov models in said computer, each pseudo two-dimensional hidden Markov model having at least one superstate associated with a first dimension of said known text element and, for each superstate, a one-dimensional hidden Markov model having at least one state associated with a second dimension of said known text element,

scanning said document to generates second signals representing a pixel map for each unknown text element, said pixel map having rows and columns of pixels, and

for each unknown text element;

responsive to said second signals, comparing said pixel map for said unknown text element with each pseudo two-dimensional hidden Markov model, by applying the Viterbi algorithm, to generate a comparison signal indicating the probability that said pseudo two-dimensional hidden Markov model represents said unknown text element, and

responsive to said comparision signals, generating an output signal identifying said unknown text element as the known text element represented by the pseudo two-dimensional hidden Markov model for which said probability is highest.

6. The method of claim 5 wherein the step of creating pseudo two-dimensional hidden Markov models comprises:

estimating the parameters for the pseudo two-dimensional hidden Markov model for each known text element from a plurality of training tokens representing said known text element by applying the segmental k-means training procedure.

7. The method of claim 5 wherein said superstates represent substantially horizontal slices through the text elements represented by said pseudo two-dimensional hidden Markov models and each comparing step comprises the steps of:

in a first routine, for each combination of one of said rows in said pixel map and one of said superstates, applying the Viterbi algorithm to determine a best path for said one row through the states in said one superstate and a probability for the final state in said one superstate and

in a second routine, applying the Viterbi algorithm and the probabilities determined in said first routine to determine a best path through all said superstates and a probability for the final superstate.

8. The method of claim 5 wherein said superstates represent substantially vertical slices through the text elements represented by said pseudo two-dimensional hidden Markov models and each comparing step comprises the steps of:

in a first routine, for each combination of one of said columns in said pixel map and one of said superstates, applying the Viterbi algorithm to determine a best path for said one column through the states in said one superstate and a probability for the final state in said one superstate and

in a second routine, applying the Viterbi algorithm and the probabilities determined in said first routine to determine a best path through all said superstates and a probability for the final superstate.

9. The method of claim 7 or claim 8 wherein each said pseudo two-dimensional hidden Markov model includes self-transition probabilities for the states and superstates in said model, which further comprises:

in said model-creating step, estimating a mean duration and a standard deviation for each state and superstate in said pseudo two-dimensional hidden Markov model,

in said first and second routines, maintaining a record of the best path through said states and superstates, and wherein said comparing step further comprises;

adjusting said determined probability by replacing duration densities based on said self-transition probabilities with duration densities based on the relevant mean durations and standard deviations for each state and superstate along said best path.

10. The method of claim 9 wherein said adjusting step further comprises:

during said first routine, adjusting the probability for the final state in each superstate by replacing duration densities based on self-transition probabilities with duration densities based on the relevant mean durations and standard deviations for the states in said superstate along the best path, and

during said second routine, adjusting the probability for the final superstate by replacing duration densities based on self-transition probabilities with duration densities based on the relevant mean durations and standard deviations for each superstate.

11. The method of claim 9 which further comprises:

before said adjusting step, calculating at least one adjustment parameter relating to at least one difference between said unknown text element and the known text element represented by said pseudo two-dimensional hidden Markov model, and

incorporating said at least one adjustment parameter in said adjusting step.

12. The method of claim 11 wherein at least one of said adjustment parameters is a scaling parameter relating the size of said unknown text element to the size of the known text element represented by said pseudo two-dimensional hidden Markov model.

13. The method of claim 8 wherein at least one of said adjustment parameters is a translation parameter relating to displacement of said unknown text element with respect to the position of the known text element represented by said pseudo two-dimensional hidden Markov model.

14. The method of claim 8 wherein at least one of said adjustment parameters is a slant parameter relating to the slant angle of said unknown text element with respect to the known text element represented by said pseudo two-dimensional hidden Markov model.

15. The method of claim 14 wherein said unknown text element may be rotated with respect to said known text elements, said creating step comprises, for each known text element, creating a first one of said pseudo two-dimensional hidden Markov models having superstate representing substantially horizontal slices and a second one of said pseudo two-dimensional hidden Markov models having superstates representing substantially vertical slices and said comparing, calculating, incorporating and adjusting steps are repeated for said unknown text element to obtain a slant parameter and an adjusted probability for both said first and said second pseudo two-dimensional hidden Markov models, which further comprises:

selecting the one of said first and second pseudo two-dimensional hidden Markov models having the highest adjusted probability,

deslanting the source image of the unknown text element through the angle represented by the slant parameter for said selected psuedo two-dimensional hidden Markov model,

repeating said comparing, calculating, incorporating and adjusting steps using said deslanted source image and the model not selected to determine a new probability for said unknown text element adjusted for said rotation.

16. The method of claim 9, which further comprises:

during said first routine, calculating at least one preliminary adjustment parameter relating to at least one difference between said unknown text element and the known text element represented by said pseudo two-dimensional hidden Markov model, adjusting the probability for the final state in each superstate by replacing duration densities based on self-transition probabilities with duration densities based on the relevant mean durations and standard deviations for the states along the best path in said superstate and incorporating said at least one preliminary adjustment parameter,

during said second routine, calculating at least one overall adjustment parameter relating to said at least one difference, adjusting the probability for the final superstate by replacing duration densities based on self-transition probabilities with duration densities based on the relevant mean durations and standard deviations for said superstates and incorporating said at least one adjustment parameter.

17. The method of claim 16, which further comprises:

after said second routine, readjusting said adjusted probability by substituting said overall adjustment parameter for each preliminary adjustment parameter.