Screen Content Image Segmentation Using Least Absolute Deviation Fitting

Shervin Minaee, Yao Wang

Abstract

We propose an algorithm for separating the foreground (mainly text and line graphics) from the smoothly varying background in screen content images. The proposed method is designed based on the assumption that the background part of the image is smoothly varying and can be represented by a linear combination of a few smoothly varying basis functions, while the foreground text and graphics create sharp discontinuity and cannot be modeled by this smooth representation. The algorithm separates the background and foreground using a least absolute deviation method to fit the smooth model to the image pixels. This algorithm has been tested on several images from HEVC standard test sequences for screen content coding, and is shown to have superior performance over other popular methods, such as k-means clustering based segmentation in DjVu and shape primitive extraction and coding (SPEC) algorithm. Such background/foreground segmentation are important pre-processing steps for text extraction and separate coding of background and foreground for compression of screen content images.

Introduction

Screen content images (SCIs) are ubiquitous in modern digital interfaces, ranging from web pages to remote desktop applications. Unlike natural photographs, SCIs are hybrid images containing "pictorial" backgrounds (often featuring gradients or smooth transitions) overlaid with "thin" foreground elements like text and line art.

Standard image compression standards like JPEG2000 or HEVC often struggle with these hybrid characteristics. Optimizing for smooth backgrounds typically results in blurry text, while optimizing for sharp edges causes file sizes to balloon. Effective compression and text extraction require robust segmentation—the ability to accurately peel the foreground away from the background. Traditional methods, such as k-means clustering (used in DjVu) or color counting (SPEC), frequently fail when backgrounds contain complex gradients or when foreground and background colors overlap.

Methodology: Robust Background Modeling

The proposed algorithm, developed by Minaee and Wang, shifts the paradigm by treating foreground elements not as features to be detected, but as "outliers" to a smooth background model.

1. The Smooth Model

The background of an image block is represented as a linear combination of a few low-frequency 2D Discrete Cosine Transform (DCT) basis functions. By assuming the background can be reconstructed using approximately 10 "smooth" building blocks, the algorithm establishes a baseline for what the background should look like.

2. Least Absolute Deviation (LAD)

While standard fitting algorithms use Least Squares ($L_2$ norm), which squares the error of every pixel, the proposed method utilizes Least Absolute Deviation (LAD) or the $L_1$ norm. The $L_2$ norm is highly sensitive to outliers; a single black letter on a white background would significantly distort a Least Squares fit. In contrast, the $L_1$ norm is mathematically robust. It effectively ignores the sharp "spikes" caused by text pixels, allowing the algorithm to find an accurate smooth fit for the background despite the presence of foreground elements.

3. Optimization and Hierarchy

To solve the $L_1$ optimization problem, the researchers employ the Alternating Direction Method of Multipliers (ADMM). To manage computational complexity, a hierarchical quadtree approach is used: the algorithm first checks for solid colors or simple smooth fits before applying the full LAD machinery to more complex blocks.

Experimental Results

The algorithm was evaluated using 332 image blocks from the HEVC standard test sequences, with manually labeled ground truth for comparison.

Qualitative comparison of segmentation results. Row 1: Original images; Row 2: Ground Truth; Row 3: SPEC; Row 4: DjVu; Row 5: Proposed Algorithm. Note the lack of artifacts in the proposed method compared to SPEC and DjVu.

As shown in the qualitative results above, the proposed LAD-based method produces significantly cleaner masks than industry-standard algorithms. While SPEC and DjVu often leave "ghosting" artifacts or fail entirely on complex gradients (as seen in the fourth column), the proposed method maintains sharp boundaries.

Quantitative Performance

Quantitatively, the proposed algorithm demonstrates a substantial leap in both precision and recall over existing methods.

Performance comparison table showing Precision and Recall metrics across SPEC, DjVu, and the proposed algorithm.

With a precision of 0.9147, the proposed method significantly reduces false positives compared to DjVu's 0.6491, making it a much more reliable pre-processing step for high-quality image compression and text recognition.

Conclusion

By conceptualizing text as outliers to a smooth background model, the LAD-based segmentation algorithm provides a robust solution for the challenges of screen content processing. While the iterative nature of ADMM presents some computational overhead, the hierarchical implementation ensures efficiency. Future work may extend this "smooth-plus-outlier" model to other domains, such as medical imaging or biometric recognition, where thin structures must be extracted from varying backgrounds.

Summary updated

Abstract

We propose an algorithm for separating the foreground (mainly text and line graphics) from the smoothly varying background in screen content images. The proposed method is designed based on the assumption that the background part of the image is smoothly varying and can be represented by a linear combination of a few smoothly varying basis functions, while the foreground text and graphics create sharp discontinuity and cannot be modeled by this smooth representation. The algorithm separates the background and foreground using a least absolute deviation method to fit the smooth model to the image pixels. This algorithm has been tested on several images from HEVC standard test sequences for screen content coding, and is shown to have superior performance over other popular methods, such as k-means clustering based segmentation in DjVu and shape primitive extraction and coding (SPEC) algorithm. Such background/foreground segmentation are important pre-processing steps for text extraction and separate coding of background and foreground for compression of screen content images.
BibTeX
@misc{minaee2015screen,
  author = {Shervin Minaee and Yao Wang},
  title = {{Screen Content Image Segmentation Using Least Absolute Deviation Fitting}},
  year = {2015},
  eprint = {1501.03755},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1501.03755},
}
Figure