An iterative graph cut optimization algorithm for a double mrf prior

Christian Wolf2008

TL;DR

This paper introduces a novel graph-cut based optimization algorithm for document restoration, specifically addressing ink bleed-through in historical documents. By employing a "double MRF" model that separately regularizes the recto and verso sides of a page, the method significantly improves character recognition accuracy compared to existing techniques.

What Problem Does This Paper Address?

Historical documents, especially those from earlier centuries, often suffer from "ink bleed-through," where ink from one side of the page is visible on the other. This phenomenon severely degrades the legibility of the text and poses a significant challenge for Optical Character Recognition (OCR) systems. Previous approaches often used a single Markov Random Field (MRF) model or simpler segmentation methods, which struggled to accurately disentangle the recto and verso text. This paper tackles the problem of effectively separating and restoring these two layers of text from a single scanned image, aiming to improve the performance of subsequent OCR.

Methods

The core of this work lies in an efficient optimization algorithm derived from a previously proposed "double MRF" model. This model treats the recto and verso sides of the document as two distinct hidden label fields, allowing for independent regularization of each. The key innovation is demonstrating that this model naturally leads to an optimization strategy based on graph cuts, specifically the minimum cut/maximum flow algorithm.

The paper reformulates the problem as minimizing an energy function. While standard MRF optimization can be computationally expensive (e.g., simulated annealing) or approximate (e.g., loopy belief propagation), the specific structure of their double MRF model allows for an exact solution using graph cuts. They adapt the a-expansion move algorithm, a technique for multi-label problems, by iteratively solving binary subproblems. A crucial aspect is identifying "regular" and "non-regular" sites based on the observation likelihood, which guides the iterative optimization process. The algorithm iteratively refines estimates for both recto and verso labels by fixing one set and optimizing the other, leveraging the graph cut formulation for efficient computation.

Datasets

The primary dataset used for evaluation consists of 104 scanned pages from the "Gazettes de Leyde," a historical French newspaper from the 18th century. This dataset is characterized by low-quality printing and significant ink bleed-through, making it a challenging benchmark for restoration methods. The authors note that obtaining ground truth for such documents is difficult, and their evaluation relies on the performance of an OCR system on the restored images.

Key Insights and Ideas

  • Decoupled Recto/Verso Regularization: The most significant insight is that treating the recto and verso sides as separate but interacting MRF fields allows for more effective regularization. This separation enables the model to better handle cases where verso text bleeds through to the recto side, and vice-versa.
  • Graph Cuts for Exact Optimization: The paper demonstrates that a specific double MRF formulation can be efficiently optimized using graph cuts, providing an exact solution that is computationally feasible. This is a powerful result, as graph cuts are a well-established and efficient technique for many computer vision problems.
  • Iterative Binary Optimization: The adaptation of the a-expansion move algorithm, by iteratively solving binary subproblems based on the regularity of sites, is a clever way to handle the multi-label nature of the problem within the graph cut framework.
  • Improved OCR Performance: The ultimate validation of the method is its impact on OCR accuracy. The paper shows that by effectively restoring the document images, the recognition performance of an OCR system is significantly boosted.

Key Results

The proposed double MRF method, optimized via graph cuts, achieved the highest OCR performance among the tested methods. Specifically, it yielded:

  • Recall: 83.23%
  • Precision: 74.85%

This represents a substantial improvement over:

  • No restoration: 65.65% recall, 49.91% precision.
  • Single MRF: 81.99% recall, 72.12% precision.
  • Source separation methods (Tonazzini et al.): Generally performed poorly, with some results being "blank or gibberish."
  • Adaptive thresholding methods (Niblack, Sauvola): Performed better than no restoration but were significantly outperformed by the MRF-based approaches.

The execution time of the proposed method was comparable to that of a single MRF with graph cut optimization, making it computationally efficient.

Limitations and Future Work

  • Dataset Specificity: While the "Gazettes de Leyde" dataset is challenging, it represents a specific type of historical document. The performance on other types of historical documents or with different bleed-through characteristics might vary.
  • Manual Parameter Tuning: Although not explicitly detailed as a limitation, MRF models often require careful parameter tuning, which can be a manual and time-consuming process.
  • Future Work: The authors suggest that the formulation could be extended to handle more complex scenarios, such as documents with multiple layers of text or more intricate bleed-through patterns. Further exploration of different prior models and optimization techniques could also be beneficial.

Summary updated

Abstract

In a previous publication we presented a double MRF model capable of separatly regularizing the recto and verso side of a document suffering from ink bleed through. In this paper we show that this model naturally leads to an efficient optimization method based on the minimum cut/maximum flow in a graph. The proposed method is evaluated on scanned document images from the 18th century, showing an improvement of character recognition results compared to other restoration methods.
BibTeX
@misc{wolf2008iterative,
  author = {Christian Wolf},
  title = {{An iterative graph cut optimization algorithm for a double mrf prior}},
  year = {2008},
}
Figure