Fast two-level Viterbi search algorithm for unconstrained handwriting recognition

This paper describes a fast two-level Viterbi search algorithm for recognizing handwritten words as a sequence of characters concatenated according to a lexicon. The algorithm is based on hidden Markov model (HMM) representations of characters and it breaks up the computation of word likelihood scores into two levels: state level and character level. This enables the reuse of likelihood scores of characters to decode all words in the lexicon, avoiding repeated computation of state sequences. Experimental results with an 85,000-word vocabulary indicate that the computational cost of an off-line handwritten word recognition system may be reduced by more than a factor of 20 while not introducing search errors.