OCR Post-Processing for Low Density Languages

Okan Kolak, Philip ResnikEMNLP 2005

TL;DR

This paper introduces a lexicon-free statistical post-processing method for Optical Character Recognition (OCR) that significantly improves accuracy, especially for low-density languages. By treating OCR errors as a noisy channel problem, the approach can adapt existing OCR systems to new languages or enhance commercial ones with minimal resources.

What Problem Does This Paper Address?

Rapidly adapting Natural Language Processing (NLP) technologies to new languages is crucial, but many languages lack sufficient digital text resources ("low-density languages"). Converting printed text to digital form often relies on Optical Character Recognition (OCR). However, OCR systems are imperfect, and their errors can severely degrade the performance of downstream NLP applications. Furthermore, for many low-density languages, dedicated OCR systems may not even exist. This paper tackles the challenge of improving OCR accuracy for these languages, either by building new capabilities or enhancing existing systems, without requiring extensive language-specific resources like large lexicons.

Methods

The core of the paper is a lexicon-free statistical post-processing method that reframes OCR error correction as a noisy channel problem. The generative process is modeled as: a correct character sequence $C$ is generated (with probability $P(C)$), and then the OCR system converts it into an observed sequence $O$ (with probability $P(O|C)$). The goal is to find the most probable original sequence $\hat{C}$ given the observed sequence $O$, using Bayes' theorem: $\hat{C} = \text{argmax}_C P(C|O) = \text{argmax}_C P(O|C)P(C)$.

Key methodological innovations include:

  • Lexicon-Free Approach: Unlike many previous methods, this approach does not rely on a pre-existing lexicon. This is crucial for low-density languages where lexicons are scarce.
  • Character-Level Modeling: The model operates at the character level, treating word merge/split errors as character insertion/deletion errors involving spaces. This simplifies the model and removes the need for explicit segmentation models.
  • Weighted Finite State Machines (WFSM): The implementation leverages WFSMs, providing a strong theoretical foundation and efficient implementation, allowing for easy integration with other FSM-based NLP tools.
  • Probabilistic Channel Models: Two types of probabilistic models for the OCR channel are explored: single-character (SC) and multi-character (MC) edit distance models.
  • Chunking Strategy: To handle long lines of text efficiently, a chunking strategy is employed. This involves breaking lines into smaller, independently correctable chunks, using probabilities from the source model to guide chunk boundaries and minimize split errors.

Datasets

The paper evaluates its method on several languages and scenarios:

  • Igbo: Used for creating new OCR capabilities. Data was derived from two sources: "Juo Obinna" (a novel) and "Akuko Ife Nke Ndi Igbo" (short stories). OCR data was generated using a commercial English OCR system.
  • Cebuano: Used for dictionary acquisition. A Cebuano hardcopy dictionary was converted to electronic form. OCR data was generated using a commercial OCR system.
  • Arabic: Used for acquiring parallel text and evaluating a native commercial OCR system. Data was derived from the Bible. OCR data was generated using a commercial Arabic OCR system.
  • Spanish: Used for evaluating machine translation performance.

Key Insights and Ideas

  • Lexicon-free is the key for low-density languages: The ability to perform OCR correction without a lexicon is a major breakthrough for languages with limited digital resources.
  • OCR errors are a significant bottleneck for NLP: The paper demonstrates that OCR errors substantially degrade performance in downstream tasks like machine translation.
  • Post-processing is a practical and effective solution: The proposed method offers a way to improve OCR accuracy without the need for expensive and time-consuming development of new OCR systems from scratch.
  • Chunking is essential for scalability: Breaking down text into manageable chunks is critical for applying the model to real-world text lengths, and the proposed probabilistic chunking strategy is effective.
  • Character-level modeling can handle complex errors: Treating word merge/split errors as character-level operations simplifies the model and allows for effective correction.

Key Results

The post-processing method consistently improved OCR accuracy across various scenarios:

  • Igbo: Achieved relative error reductions of 30% to 80%, resulting in Word Error Rates (WER) as low as 7.11% for a new language. Even when post-processing an Igbo-trained OCR system, WER was reduced by 50%.
  • Cebuano: Demonstrated substantial WER reductions (20% to 50%), achieving a WER of 3.97% in a dictionary acquisition scenario.
  • Arabic: Reduced the error rate of a native commercial OCR system by nearly 30%.
  • Machine Translation (MT): For Arabic, post-processing brought MT performance significantly closer to that of clean text. For Spanish, similar improvements were observed, though with higher absolute scores due to more available resources.

Limitations and Future Work

  • Reliance on an existing OCR system: The method requires an existing OCR system that supports the script of the language of interest. For languages with no OCR support, trainable OCR systems are an option, but training them can be tedious.
  • Computational Complexity: While WFSMs are efficient, handling very long lines or allowing a high number of errors per token can still be computationally demanding. Iterative correction is suggested as a way to potentially improve results but doesn't guarantee optimality.
  • Training Data: The performance of the error and language models is dependent on the availability of training data. While the method is designed to require minimal resources, more data generally leads to better results.
  • Future Work: The authors suggest exploring more advanced translation systems for extrinsic evaluations and investigating how to combine their post-processing method with script-independent OCR systems for better adaptation to new languages. They also note the potential for using variable memory length Markov models as language models to handle higher-order n-grams.

Summary updated

BibTeX
@inproceedings{kolak2005ocr,
  author = {Okan Kolak and Philip Resnik},
  title = {{OCR Post-Processing for Low Density Languages}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
}
Figure