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

R. Schinghal, D. Rosenberg, Godfried T. Toussaint

Authors and Affiliations

Introduction

In the field of optical character recognition (OCR) during the late 1970s, systems primarily focused on identifying characters in isolation. However, human reading is inherently contextual; the presence of certain character sequences significantly influences the probability of subsequent letters. To bridge this gap, researchers employed Markov models—specifically first-order Markov sources—to estimate character probabilities based on bigrams. While Raviv’s recursive Bayes algorithm provided a rigorous mathematical framework for this, its computational intensity was a significant barrier for the hardware of the era. This paper proposes a simplified heuristic version of Raviv’s algorithm that maintains performance while reducing computational overhead.

Methodology

The study evaluates four distinct approaches to text recognition:

  1. No Context: A standard Bayes classifier analyzing only the current character's features.
  2. Raviv’s Recursive Bayes Algorithm: A recursive method calculating character probability based on the entire preceding sequence.
  3. Modified Viterbi Algorithm: A global optimization approach that identifies the most likely character sequence for an entire word based on observed features.
  4. Proposed Heuristic: A local shortcut that classifies the current character by maximizing probability based on the current feature vector and the specific decision made for the immediately preceding character, rather than maintaining a full recursive probability distribution.

The researchers also compared Word-Position-Independent (WPI) n-grams (general statistics) against Word-Position-Dependent (WPD) n-grams, which account for a letter's position within a word (beginning, middle, or end).

Experimental Setup

The evaluation utilized a language corpus of over 500,000 words to estimate n-gram probabilities. Character images were sourced from Ryan’s dataset, comprising 13,337 mixed-font machine-printed letters converted into 36-dimensional feature vectors. Testing was conducted on two passages: an "Old Passage" (internal to the training subjects) and a "New Passage" (external source).

Key Results and Discussion

The experimental results, summarized in the table below, demonstrate that the proposed heuristic performs remarkably well compared to the more complex recursive method.

Table 1: Comparison of error rates across different classification methods and n-gram probability models.

Performance Insights

  • Heuristic Efficiency: The most significant finding was that the "greedy" heuristic decision-making process achieved error rates nearly identical to Raviv’s mathematically rigorous method (e.g., 14.09% vs. 14.08% on the New Passage with WPD probabilities). This suggests that for first-order Markov models, the simpler local decision is sufficient.
  • Positional Advantage: Utilizing Word-Position-Dependent (WPD) probabilities consistently outperformed position-independent models, highlighting the importance of structural context in English text.
  • The Markov Ceiling: Despite the inclusion of context, error rates only decreased by approximately 1–3%. This indicates that a first-order Markov model is a relatively weak representation of the complexities of the English language.
  • Viterbi Superiority: The Modified Viterbi algorithm remained the most accurate (12.50% error on the New Passage), though it requires the computational cost of processing entire words before making final decisions.

Conclusion

The proposed heuristic offers a computationally efficient alternative to Raviv's algorithm without sacrificing accuracy. However, the modest improvements in error rates suggest that future OCR research should move toward higher-order models, such as trigrams or whole-word recognition, to more effectively capture the nuances of human language processing. Additionally, future work must address the assumption of perfect "blank" (space) recognition, which remains a challenge in practical OCR applications.

Summary updated

BibTeX
@inproceedings{schinghal1977simplified,
  author = {R. Schinghal and D. Rosenberg and Godfried T. Toussaint},
  title = {{A Simplified Heuristic Version of Raviv's Algorithm for Using Context in Text Recognition}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}
Figure