A Simplified Heuristic Version of Raviv's Algorithm for Using Context in Text Recognition

1. Introduction

Some of the contextual text-recognition al­ gorithms invoke the assumption that English lan­ guage is a Markov source of order r~l[l]. Having made these assumptions these algorithms use either sequential or nonsequential decision theory.

This paper describes an ex­ perimental investigation of text-recognition by four methods: without contextual information, Raviv's recursive Bayes algorithm [2], the modi­ fied Viterbi algorithm [5 ], and a proposed heuristic approximation to Raviv's algorithm. The objective of the experiments was to compare

the above methods.

It was assumed that English language is a Markov source of order - r=l . To conduct the experiments, it was necessary that unigram (sin­ gle-letter) and first-order transition probabili­ ties be estimated from the English language. The probabilities are collectively referred to as the n-gram probabilities.

2. Estimation of N-gram Probabilities From the English Language

A multi-authored English language corpus written on ten different subject matters [4] comprising over half-a-million words was compiled. Probability estimates were obtained from this corpus for the following:

• (i) Word-position-independent unigram pro­ babilities P(Ci) ·
• (ii) Word-position-independent transition probabilities P(cilcj) .
• (iii) Word-position-dependent unigram proba­ bilities Pm(Ci) for position m (1;5m;59) .
• (iv) Word-position-dependent transition pro­ babilities P (cilc.) for 0~~9 .
• m J

Pm(cilcj) is the probability of occurrence of character ci in position (m+l) of a word given that character c. occurs in position m.

J

Since the corpus was large, it was assumed that P(Ci) , P(cilcj), Pm(Ci), Pm(cilcj) estimated from the corpus, reflect closely the true n-gram probabilities of the English language for the 27-character set, ~ and the letters A to Z. Each experiment described in Section 4 was re­ peated twice: once, by using the word-position­ independent (WPI) n-gram probabilities and a second time, by using word-position-dependent (WPD) n-gram probabilities.

3. Simulation of the Text-Recognition Problem

Images on 24 x 24 arrays of mixed-font machine printed letters were taken from Ryan's* data set. The images were size-normalized and a 36-dimensional feature-vector X=(x 1 ,x 2 , ·.. ,x 36 ) was extracted from each image [4).

The total number of patterns available was 13,337. These were divided into two sets: a training set of 6,651 patterns and a testing set of 6,686 patterns. The classifier was trained, and P(xlck)--the probability distribution of X

conditioned on Ck--was estimated.

A passage, called the Old Passage, was com­ piled from ten segments, such that each segment was arbitrarily chosen from one of the ten sub­ ject matters in the corpus (described in Section 2). Another passage, called the New Passage, was similarly compiled but from sources outside the corpus [4]. The Old Passage consisted of 2,521 words and the New Passage of 2,256 words. These two passages were used as text to be recog­ nized in the experiments described in Section 4.

4. The Text-Recognition Problem and the Experiments Conducted

Patterns of the passages were presented sequentially to the classifier. It was assumed that all blanks were perfectly recognizable. Let

be the pattern-sequence input to the classifier such that x 0 and Xn+l are blanks. Thus, x 1 to X n is a word of patterns, and a text is recognized one word at a time.

t This research was supported by the National Research Council of Canada under grant number

NRC-A9293.

* Pattern Recognition Data Base No. 1.1.1 A, IEEE Computer Society

Let P(xii=Z) denote the probability of X conditioned on X=Z , the sequence of classes

taking on the values

Thus z 0 and Zn+l are ~ and z 1 each take on any of the values of the of the English alphabet. Let c 1 to to Z can n 26 letters c26 refer to the 26 letters of the ·English alphabet.

4.1 Classification Without Contextual Informatfun

In this case, the class of pattern Xi was decided by a Bayes classifier such that

was maximized over the values of Zi . Here we

use the information present in the feature vector and the apriori knowledge of the probability of occurrence of a particular letter in the English language.

4.2 Raviv's Recursive Bayes Algorithm

In this method pattern Xm(lsrnsn) is classi­ fied by maximizing the P( Am~cklxl,x2, ... ,Xm) a posteriori probability for lsk~26 . Raviv [2] showed that this a posteriori probability can be expressed as follows:

4.3 The Modified Viterbi Algorithm

In this algorithm a decision is made on a whole word by maximizing

Forney [3) showed that expression (4.3-1) can be maximized by the Viterbi algorithm. Toussaint and Chung [5 ) proposed a modification where in­ stead of considering all 26 alternatives for every pattern Xi , only the d (l~d~26) most probable alternatives using P(XiiAi=Zi)P(Zi) are con­ sidered for each letter. In [4) a formal algo­ rithmic implementation of the modified Viterbi algorithm is described. It is shown experimen­ tally in [4) that the modified Viterbi algorithm reduces computation without increasing the error-rate. In the experiment described in this paper, the modified Viterbi algorithm was used to maximize expression (4.3-1). Thus a decision on classifying a word is made after con­ sidering all the feature-vectors in the word.

4.4 A Heuristic Approximation to Raviv's Algorithm

In this proposed method, pattern Xi (l~i<n) is classified by maximizing P(xiTAi=Zi)P(Ai=ziiAi-l=Zi-l) over the values of Zi · Here we use information present in the feature vector Xi and in the decision that was made on the pattern just before

5. Conclusions

An unexpected result is the fact that the heuristic approximation of Raviv's algorithm performed just as well as Raviv's recursive Bayes approach and yet requires far less compu­ tation as is evident from Section 4.4.

It is, of course, also realized that the different results in Table 1 suggest that context in English is not well-modelled by the Markov assumption.