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

TL;DR

This paper introduces a simplified heuristic algorithm for text recognition that achieves comparable accuracy to a more complex recursive Bayes approach while significantly reducing computational cost. This is achieved by leveraging word-position-independent and dependent n-gram probabilities estimated from a large English corpus, demonstrating that effective text recognition can be done with less computational overhead.

What Problem Does This Paper Address?

Recognizing text from images, especially when dealing with variations in fonts and styles, is a challenging problem. Many existing approaches rely on complex statistical models that assume English text follows a Markov source of a certain order. These models often require significant computational resources to estimate probabilities and make decisions. The authors aim to investigate and propose a more computationally efficient method for text recognition that still leverages contextual information from the language. Specifically, they explore how to use n-gram probabilities (probabilities of sequences of characters) to improve recognition accuracy without incurring the full computational burden of more sophisticated algorithms like Raviv's recursive Bayes or the modified Viterbi algorithm.

Methods

The paper compares four methods for text recognition:

  • Classification Without Contextual Information: This is a baseline method that uses only the feature vector of a character and its prior probability of occurrence.
  • Raviv's Recursive Bayes Algorithm: A well-established algorithm that uses a recursive approach to estimate the posterior probability of a character sequence.
  • Modified Viterbi Algorithm: An adaptation of the Viterbi algorithm that considers only the d most probable alternatives for each character, reducing computation compared to a full Viterbi search.
  • Proposed Heuristic Approximation to Raviv's Algorithm: This is the novel contribution. It classifies a pattern by maximizing a probability that incorporates information from the current feature vector and the decision made on the previous pattern. This approach aims to capture context without the full recursive computation.

The core of the method involves estimating n-gram probabilities from a large English corpus. These probabilities are categorized into:

  • Word-position-independent unigram probabilities: The probability of a single character appearing, regardless of its position in a word.
  • Word-position-independent transition probabilities: The probability of a character appearing given the previous character, irrespective of their positions.
  • Word-position-dependent unigram probabilities: The probability of a character appearing at a specific position within a word.
  • Word-position-dependent transition probabilities: The probability of a character appearing given the previous character, considering their specific positions within a word.

These probabilities are then used in the different classification methods.

Datasets

  • English Language Corpus: A multi-authored corpus comprising over half-a-million words from ten different subject matters was used to estimate n-gram probabilities.
  • Ryan's Data Set: Images of 24x24 arrays of mixed-font machine-printed letters were used. This dataset was split into a training set (6,651 patterns) and a testing set (6,686 patterns).
  • Old Passage and New Passage: Two passages were compiled for evaluating the text recognition system. The "Old Passage" (2,521 words) was compiled from segments of the corpus used for probability estimation, while the "New Passage" (2,256 words) was compiled from external sources to test generalization.

Key Insights and Ideas

  • Context is Crucial, but Not Always Simple: The experiments suggest that while context improves recognition, the Markov assumption (where the probability of the next state depends only on the current state) might be an oversimplification for modeling English language context.
  • Heuristic Efficiency: The proposed heuristic approximation to Raviv's algorithm performs as well as the more complex recursive Bayes approach but requires significantly less computation. This highlights the potential for developing efficient yet accurate text recognition systems.
  • Word-Position Dependence Matters: The paper investigates both word-position-independent and word-position-dependent probabilities, suggesting that considering character positions within words can offer additional benefits for recognition.

Key Results

The paper presents results in Table 1, showing the percentage probability of error for each method under different conditions (using word-position-independent vs. word-position-dependent n-grams, and on the "Old Passage" vs. "New Passage").

  • The Modified Viterbi Algorithm generally achieved the lowest error rates, with errors ranging from 12.40% to 13.10%.
  • Raviv's Recursive Bayes Algorithm performed comparably, with errors ranging from 13.87% to 14.20%.
  • The Proposed Heuristic Approximation also performed very well, with errors ranging from 13.89% to 14.25%, closely matching Raviv's algorithm.
  • Classification Without Contextual Information had the highest error rates, ranging from 15.00% to 15.50%.

Crucially, the heuristic approximation achieved performance comparable to Raviv's algorithm while requiring "far less computation."

Limitations and Future Work

  • Markov Assumption: The authors acknowledge that the differing results between the Old and New Passages suggest that the Markov assumption may not fully capture the nuances of English language context.
  • Computational Reduction: While the heuristic algorithm significantly reduces computation, the paper doesn't quantify the exact reduction factor.
  • Future Work: The paper implies that further exploration into more sophisticated context modeling beyond simple Markov chains could lead to even better recognition performance. The success of the heuristic approach also opens avenues for exploring similar simplified methods for other pattern recognition tasks.

Summary updated

BibTeX
@inproceedings{1977simplified,
  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