Abstract
This research introduces a modular, generative probabilistic model designed to clean up the "noisy" output of black-box Optical Character Recognition (OCR) systems. By treating OCR as a noisy channel problem and implementing it using weighted Finite State Machines (FSMs), the authors significantly reduce word error rates and demonstrate that this correction is vital for downstream NLP tasks like automatic translation lexicon induction.
Problem Definition: The "Black Box" Challenge
Most commercial OCR systems are monolithic "black boxes" that are difficult to retrain or adapt for new languages, particularly resource-poor ones. When these systems fail, they don't just misidentify characters; they often fail at segmentation, incorrectly merging or splitting words (e.g., turning "example" into "ex ample").
For Natural Language Processing (NLP) applications—such as machine translation or information retrieval—these errors are catastrophic. A downstream tool expecting a clean vocabulary cannot handle "ex ample" as two distinct tokens. The authors tackle the challenge of post-processing this noisy output to make it "NLP-ready" without needing access to the internal workings of the OCR engine itself.
Methodology: A Generative Noisy Channel Model
The authors frame the problem using a Generative Noisy Channel Model. The goal is to find the most likely true word sequence ($W$) given the observed OCR output ($O$). This is modeled as: $$P(W|O) \propto P(O|W)P(W)$$
The core innovation lies in the decomposition of the channel model $P(O|W)$ into three distinct, modular steps:
- Words to Characters ($P(C|W)$): Maps words to their character sequences, accounting for variations like casing.
- Segmentation ($P(a|C, W)$): A probabilistic model that decides where word boundaries occur, crucial for fixing merge/split errors.
- Character Sequence Transformation ($P(O|a, C, W)$): A probabilistic string edit model handling substitutions, insertions, and deletions.
The entire pipeline is implemented using Weighted Finite State Machines (FSMs). Each step is a separate FSM; they are composed into a single large transducer, which is then inverted to perform decoding.
Experimental Setup
The researchers used the Bible in English and French as their primary corpus. To simulate the challenge of a language with poor OCR support, they ran an English OCR system on French printed text. This created a high-error baseline (18.31% Word Error Rate) to test the robustness of their correction model.
Key Results and Downstream Impact
The model showed dramatic improvements across the board:
- Error Reduction: In the English-on-French scenario, the model reduced the Word Error Rate (WER) from 18.31% to 6.75% (a 63% reduction) using a trigram language model and 2-way segmentation.
- Downstream Impact: The authors tested the corrected text by automatically extracting a French-English translation lexicon. While precision dropped sharply for uncorrected OCR, the corrected output maintained over 90% precision up to 80% recall, nearly matching the performance of error-free ground truth text.
Discussion
- Modularity: Because the model is decomposed into FSMs, components like the language model or error model can be swapped without rebuilding the entire system.
- Global Interaction: The model allows the Language Model (LM) to "overrule" the OCR system. For example, a trigram LM might recognize "la terre" as more probable than the OCR's split "la ter- re," forcing a correction.
- Complexity and Scope: Word merge/split errors cause an exponential increase in the search space, requiring limits on the number of splits/merges. Future work could include context-dependent character error models and expansion to non-Latin scripts like Arabic or Chinese, which present unique morphological and segmentation challenges.
Summary updated