Image analysis – Pattern recognition – On-line recognition of handwritten characters
Reexamination Certificate
1998-04-30
2001-09-04
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
On-line recognition of handwritten characters
Reexamination Certificate
active
06285786
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a text recognizer and a method of recognition of handwritten input, for example for use in a user interface for a computer or other data device.
BACKGROUND OF THE INVENTION
Research in speech and handwriting recognition—the translation of a person's voice or writing into computer readable text has been ongoing since at least the 1960's. The two problems share many common characteristics: processing of a signal with inherent temporal structure, recognition of a well-defined and finite set of symbols (i.e., characters and phonemes), composition of these basic symbols to form words and phrases, and presence of the co-articulation effect. Because of these similarities, techniques developed to solve one problem can often be applied to the other.
In an existing speech recognizer, an unknown waveform is converted by a front-end signal processor into a sequence of acoustic vectors, Y=y
1
, y
2
, . . . , y
T
. Each of these vectors is a compact representation of the short-time speech spectrum covering a uniform period of typically 10 milliseconds. With this input representation, the job of the recognition system is formulated as that of determining the most probable word, or word sequence, W* given the observed vector sequence Y. That is,
Find
W
*
such
that
W
*
=
argmax
P
(
W
|
Y
)
W
(
1
)
The naive way of finding W* is to enumerate all possible word sequences and compute P(W|Y) for each of them. This approach is impractical when the number of possible words is large. Instead, potential word sequences are explored in parallel (i.e., in a breadth-first fashion), discarding hypotheses as soon as they become improbable. This search process is referred to in the speech literature as the “beam search”. See, for example: R. Haeb-Umbach and H. Ney, “Improvements in time-synchronous beam search for 1000-word continuous speech recognition”, IEEE Trans. Speech and Audio Processing, Vol 2, pp 353-356, 1994; or J. J. Odell, V. Valtchev, P. C. Woodland, S. J. Young, “A one pass decoder design for large vocabulary recognition” Proc. Human Language Technology Workshop, Plainsboro, N.J., March, 1994.
To further understand the search process, let D={W
1
, W
2
, . . . , W
K
} be a dictionary consisting of the K words known to the system. Each of these words W
i
is represented as a sequence of phone models W
i
=C
i
1
C
i
2
. . . C
i
L
corresponding to its pronunciation (in handwriting recognition there are character models instead). The dictionary is represented in a tree-based structure: at the start there is a branch to every possible start model C
j
1
; all first models are then connected to all possible follow models C
j
2
and so on. The tree is extended deep enough until all words in D are represented. Word sequences are represented in a compact way by allowing the tree to be reentrant: it is possible to have a path from the start node to some point in the tree corresponding to an end of word, and continuing at the start of the tree again.
The dictionary tree is used by the search to generate a set of initial hypotheses or theories. At each time step, the observed input y
t
is compared against the set of open theories, and a probability of each theory generating the input is multiplied into the theory's ongoing score. At any time, a theory is a product of n probabilities, one for each time step. The theories can be directly compared, and some subset may be selected for further evaluation. Each theory has the possibility of propagating to generate a set of new theories that encode possible completions of the utterance from the current point in time. By carefully controlling the rate of new theory propagation and the destruction of obsolete theories, the exponential growth of the search space can be controlled. In particular, the standard formulation of the search algorithm follows a score-prune-propagate pattern, in which theories are scored, poorly scoring theories are destroyed, and then a subset of the survivors are allowed to propagate.
Probabilities are generated using an HMM representation of each phone model, for example as described in L. R. Bahl, F. Jelinek and R. L. Mercer, “A maximum likelihood approach to continuous speech recognition”, IEEE Trans. On Pattern Analysis and Machine Intelligence, pp 179-190, 1983. Phonetic HMMs are finite-state machines with a simple left-right topology, and typically, three emitting states. An HMM changes states once every time unit, and every time that a state, q
j
, is entered, an acoustic vector, y
t
, is produced as output with probability density b
q
j
(y
t
). In addition, the transition from state q
i
to state q
j
is also probabilistic and governed by the discrete probability a
q
i
q
j
(see FIG.
1
).
FIG. 1
shows a 3 state phoneme model. It is shown connected on the left and right to other models. Associated with each state q
i
there is an “emission” probability distribution b
q
j
(y
t
) and associated with each arc (q
i
, q
j
) there is a “transition” probability a
q
i
q
j
.
The problem of computing P(W|Y) in (1) is simplified by using Bayes'rule which expresses this probability as
P
(
W
|
Y
)
=
P
(
W
)
P
(
Y
|
W
)
P
(
Y
)
(
2
)
In Eq. (2), P(W) corresponds to the a priori probability of observing W in the language or application of interest, and thus this probability is determined by a language model. P(Y|W) represents the probability of observing the vector sequence Y given some specified word sequence W. Alternatively, P(Y|W) is a measure of similarity between a model for W and the unknown speech Y. A model for W is constructed by concatenating word models which, in turn, are composed of concatenated phonetic HMM models. Note that P(Y) may be neglected (during recognition) since it has no effect on the chosen word sequence.
The required probability P(Y|W) can be computed by summing over all possible state sequences of length T, Q=q
0
. . . q
T
, through the states of the given model:
P
(
Y
|
W
)
=
∑
Q
P
(
Y
,
Q
|
W
)
=
∑
Q
∏
t
=
1
T
b
q
t
(
y
t
)
·
a
q
t
-
1
q
t
(
3
)
For computational efficiency, P(Y|W) is often approximated by finding the sequence of states most likely to have generated the given observations Y, without having to search all possible sequences:
P
(
Y
|
W
)
∼
Max
Q
P
(
Y
,
Q
|
W
)
=
Max
Q
∏
t
=
1
T
b
q
t
(
y
t
)
·
a
q
t
-
1
q
t
(
4
)
Efforts to apply this framework to the problem of handwriting recognition have focused on formulating input representation schemes that view the handwriting process as a function of a single independent variable, such as time or one dimensional positioning. In existing handwriting recognition schemes, the pen trajectory {(X(t),Y(t)} is transformed into a continuous-time feature vector sequence F=f
1
, f
2
, . . . , f
t
where each vector f
t
encodes local information (e.g., writing direction and curvature) for a data point P(t)=(X(t),Y(t)). Reference can be made, for example to J. Makhoul, T. Starner, R. Schwartz and G. Chou, “On-line cursive handwriting recognition using hidden markov models and statistical grammars”, IEEE Conf. on Acoustics, Speech and Signal Processing, Australia, 1994; M. Schenkel, I. Guyon and D. Henderson, “On-line cursive script recognition using time-delay neural networks and hidden markov models”, IEEE Conf. on Acoustics, Speech and Signal Processing, Australia, 1994; or S. Manke, M. Finke and A. Waibel, “A fast search technique for large vocabulary on-line handwriting recognition”, Fifth International Workshop on Frontiers in Handwriting Recognition (IWFHR5), England, 1996.
With this kind of representation, these systems were able to preserve, with almost no modification, the HMM and tree
Seni Giovanni
Seybold John
Azarian Seyed
Bose Romi N.
Johns Andrew W.
Motorola Inc.
Watanabe Hisashi D.
LandOfFree
Text recognizer and method using non-cumulative character... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Text recognizer and method using non-cumulative character..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Text recognizer and method using non-cumulative character... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2484592