TL;DR
This paper introduces a novel rate-distortion optimized segmentation algorithm for Mixed Raster Content (MRC) compression. By jointly optimizing segmentation and compression, the method achieves significantly higher subjective quality than state-of-the-art methods like JPEG-2000, especially for text and graphics, at comparable bitrates.
What Problem Does This Paper Address?
High-quality document compression is crucial for efficient storage and transmission of scanned documents, which often contain a mix of text, graphics, and continuous-tone images (Mixed Raster Content or MRC). Traditional compression algorithms, like JPEG, struggle with MRC because they assume spatial homogeneity. Existing MRC compression methods often segment documents into regions and compress them separately, but the segmentation process itself can introduce artifacts, especially when misclassifications occur. The challenge is to segment the document in a way that not only separates different content types but also minimizes the overall distortion for a given bitrate, considering the specific compression methods used for each region.
Methods
The core of this paper is a rate-distortion optimized segmentation algorithm designed for the 3-layer MRC model (foreground, mask, background). Instead of directly segmenting the image based on visual features, this approach works in a closed loop:
- Block-based Segmentation: The image is divided into 8x8 blocks.
- Class Assignment: For each block, the algorithm considers five possible classes: Two-color, One-color Background (OnB), One-color Foreground (OnF), Foreground (Fgd), and Background (Bgd).
- Rate-Distortion Optimization: For each class, the algorithm estimates the bit rate required for compression and the resulting distortion. This estimation is crucial and is done using approximations for the actual coding methods (JPEG for foreground/background, JBIG2 for mask).
- Dynamic Programming: A dynamic programming approach is used to find the optimal sequence of class assignments for all blocks that minimizes the total rate-distortion cost, controlled by a user-defined parameter ($\lambda$). This ensures that the segmentation is tailored to the compression outcome.
- Class-Specific Distortion: A key insight is the use of class-dependent distortion measures. For instance, text regions (Two-color blocks) are more sensitive to distortion than background regions. The distortion for Two-color blocks is specifically designed to penalize sharpening artifacts while allowing for some flexibility in color combinations.
Datasets
The authors evaluated their algorithm on a database of 30 scanned document images (from sources like ASEE Prism and IEEE Spectrum) and one synthetic test image. The scanned documents were captured at 400 dpi with 24 bits per pixel and included images with halftone backgrounds and ghosting artifacts. The synthetic image was designed to have a complex layout and multiple colors to test the algorithm's robustness.
Key Insights and Ideas
- Joint Optimization is Key: The most significant insight is that optimizing segmentation and compression together (rate-distortion optimization) leads to superior results compared to optimizing them independently.
- Class-Dependent Distortion Matters: Recognizing that different image regions have different sensitivities to distortion is crucial for achieving high subjective quality. The paper's specific distortion measure for "Two-color" blocks is a prime example of this.
- Robustness through Exhaustive Testing: By evaluating each block against all possible classes and their associated compression costs, the algorithm inherently avoids severe misclassifications that can lead to noticeable artifacts.
- Flexibility via $\lambda$: The rate-distortion parameter $\lambda$ allows users to control the trade-off between compression ratio and visual quality, making the algorithm adaptable to different application needs.
Key Results
Experimental results demonstrate that the proposed rate-distortion based MRC compression achieves significantly higher subjective quality than JPEG-2000 at similar bitrates. For example, one experiment achieved a 221:1 compression ratio (0.1085 bpp) with excellent visual quality on a synthetic document image. The paper highlights that the algorithm excels particularly in preserving the quality of text and graphic regions, which are often degraded by other compression methods.
Limitations and Future Work
- Approximations in Rate/Distortion Modeling: The paper acknowledges that the rate and distortion terms are approximations, especially for complex coders like JBIG2. While experimental results show these approximations are effective, more precise modeling could potentially yield further improvements.
- Computational Complexity: While the use of dynamic programming and block-based processing improves efficiency, the rate-distortion optimization process itself can be computationally intensive.
- Future Work: The authors suggest that further research could explore more sophisticated rate-distortion models and potentially extend the approach to other MRC compression standards or more complex document types.
Summary updated