Screen Content Image Segmentation Using Robust Regression and Sparse Decomposition

Shervin Minaee, Yao Wang

Abstract

This paper addresses the challenge of separating text and graphics from smooth backgrounds in screen content and mixed document images. We propose two novel segmentation approaches based on the observation that backgrounds typically vary smoothly and can be modeled by a linear combination of basis functions, whereas foreground elements create sharp discontinuities. The first method utilizes robust regression (RANSAC) to identify background pixels as inliers and foreground pixels as outliers. The second method employs a sparse decomposition framework, modeling the image as a sum of a smooth background and a sparse foreground component. Evaluated on HEVC standard test sequences, these methods significantly outperform traditional clustering techniques like k-means, offering superior accuracy for applications in text extraction and screen content compression.

Introduction

As digital displays become the primary medium for information consumption, the prevalence of "screen content"—images containing a mix of naturalistic backgrounds, text, and computer-generated graphics—has grown. Traditional image processing algorithms often struggle with these hybrid images. For instance, standard k-means clustering fails when background gradients overlap with foreground colors. To address this, we move beyond simple pixel-intensity grouping toward a structural model that exploits the mathematical properties of the image layers: backgrounds are "smooth" (low-frequency), while foregrounds are "sparse" and "sharp" (high-frequency).

Proposed Methodology

1. Robust Regression (RANSAC)

In this framework, we treat the segmentation task as a model-fitting problem. We assume the background in a local image block can be represented by a smooth function (a linear combination of 2D Discrete Cosine Transform bases). Using the Random Sample Consensus (RANSAC) algorithm, we iteratively select a subset of pixels to fit this smooth model. Pixels that deviate significantly from the model are classified as foreground "outliers," while those that fit are labeled as background "inliers."

2. Sparse Decomposition (SD)

Alternatively, we frame the problem as a decomposition: $f = P\alpha + s$, where $P\alpha$ represents the smooth background and $s$ represents the sparse foreground. To solve this, we minimize an objective function that penalizes both the number of basis functions used and the density of the foreground. A Total Variation (TV) penalty is included to ensure the foreground pixels are spatially connected, reflecting the structured nature of text and graphics.

Visual decomposition of different screen content types into smooth background and sparse foreground layers.

Basis Function Selection

Both methods rely on choosing an appropriate set of basis functions to represent the background. We compared the performance of Polynomial bases against Discrete Cosine Transform (DCT) bases. Our analysis shows that DCT bases generally provide a lower reconstruction Root Mean Square Error (RMSE) for a given number of bases ($K$), making them more efficient for modeling smooth background gradients.

Reconstruction RMSE for background modeling using DCT vs. polynomial bases.

Experimental Results

We evaluated our algorithms on a dataset of 328 image blocks extracted from HEVC test sequences. The proposed methods were compared against industry standards, including DjVu (hierarchical k-means) and SPEC (shape primitive extraction).

Method F1 Score Average Time (per 64x64 block)
Sparse Decomposition 90.5% 962 ms
RANSAC 90.4% 20 ms
DjVu (k-means) 66.0% -
SPEC 56.0% -

While both proposed methods achieve high accuracy, the RANSAC-based approach is significantly faster, making it more suitable for real-time applications. The Sparse Decomposition method, though slower due to the iterative nature of the ADMM solver, provides slightly better spatial consistency thanks to the Total Variation regularization.

Conclusion

By leveraging the structural differences between smooth backgrounds and sharp foregrounds, our proposed methods achieve a substantial leap in segmentation accuracy over color-based clustering. These techniques are highly effective for screen content coding and can be extended to other domains, such as medical imaging, where separating structured objects from varying backgrounds is critical.

Summary updated

Abstract

This paper considers how to separate text and/or graphics from smooth background in screen content and mixed document images and proposes two approaches to perform this segmentation task. The proposed methods make use of the fact that the background in each block is usually smoothly varying and can be modeled well by a linear combination of a few smoothly varying basis functions, while the foreground text and graphics create sharp discontinuity. The algorithms separate the background and foreground pixels by trying to fit background pixel values in the block into a smooth function using two different schemes. One is based on robust regression, where the inlier pixels will be considered as background, while remaining outlier pixels will be considered foreground. The second approach uses a sparse decomposition framework where the background and foreground layers are modeled with a smooth and sparse components respectively. These algorithms have been tested on images extracted from HEVC standard test sequences for screen content coding, and are shown to have superior performance over previous approaches. The proposed methods can be used in different applications such as text extraction, separate coding of background and foreground for compression of screen content, and medical image segmentation.
BibTeX
@article{minaee2016screen,
  author = {Shervin Minaee and Yao Wang},
  title = {{Screen Content Image Segmentation Using Robust Regression and Sparse Decomposition}},
  journal = {IEEE Journal on Emerging and Selected Topics in Circuits and Systems},
  year = {2016},
  doi = {10.1109/jetcas.2016.2597701},
}
Figure