Image Decomposition Using a Robust Regression Approach

Shervin Minaee, Yao Wang

Abstract

This paper considers how to separate text and/or graphics from smooth background in screen content and mixed content images and proposes an algorithm 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. This algorithm separates the background and foreground pixels by trying to fit pixel values in the block into a smooth function using a robust regression method. The inlier pixels that can be well represented with the smooth model will be considered as background, while remaining outlier pixels will be considered foreground. We have also created a dataset of screen content images extracted from HEVC standard test sequences for screen content coding with their ground truth segmentation result which can be used for this task. The proposed algorithm has been tested on the dataset mentioned above and is shown to have superior performance over other methods, such as the hierarchical k-means clustering algorithm, shape primitive extraction and coding, and the least absolute deviation fitting scheme for foreground segmentation.

Introduction

Screen content images (SCIs), such as those found on computer desktops or mobile interfaces, differ significantly from natural photographs. They typically consist of two distinct layers: a pictorial, smoothly varying background and a foreground composed of sharp text and line graphics. Standard image compression techniques like JPEG or HEVC intra-coding are often suboptimal for SCIs because they are not designed to handle the sharp discontinuities characteristic of text.

To improve compression efficiency, it is necessary to decompose these images into their constituent layers. However, traditional segmentation methods like k-means clustering often struggle when foreground and background colors overlap or when sub-pixel rendering introduces color variations in text. This paper proposes a robust regression framework to address these challenges by treating foreground pixels as outliers to a smooth background model.

Methodology

The proposed approach reframes image segmentation as a regression problem rather than a simple clustering task.

The Smooth Model and Robust Regression

The background in a small image block ($N \times N$) is assumed to be smooth, representable by a few low-frequency 2D Discrete Cosine Transform (DCT) basis functions. Instead of using standard Least Squares fitting—which is sensitive to outliers—the authors employ RANSAC (Random Sample Consensus). RANSAC iteratively selects a random subset of pixels to fit the smooth model, identifying the model that maximizes the number of "inlier" pixels. Pixels that fit the model are classified as background, while outliers are classified as foreground.

Computational Efficiency

To mitigate the computational cost of RANSAC, a hierarchical pipeline is implemented:

  1. Variance Check: If a block has very low variance, it is classified entirely as background.
  2. Least Squares Fit: If a simple Least Squares fit yields a low error for all pixels, the block is classified as background.
  3. Color Count: Blocks with very few colors (typical of flat backgrounds) are handled with simpler logic.
  4. RANSAC: The full robust regression is only applied to complex blocks that fail the previous steps.

Results

The algorithm was evaluated using a custom dataset of 332 image blocks ($64 \times 64$) extracted from HEVC standard test sequences, with manually created ground-truth masks. This dataset has been made publicly available to serve as a benchmark for the research community.

Visual comparison of various segmentation algorithms on screen content images.

Qualitative analysis (see Figure 4) demonstrates that the RANSAC-based method excels at preserving thin text characters and handling complex background gradients where other methods produce artifacts like "ghosting" or holes.

Quantitative performance comparison of segmentation algorithms.

Quantitatively, the proposed method significantly outperforms existing standards. As shown in the performance table, the RANSAC-based approach achieved an F1-score of 90.7%, compared to 66% for Hierarchical Clustering and 56% for SPEC. It maintains a high balance between precision (91.5%) and recall (90.0%).

Conclusion

This paper presents a robust regression approach for screen content image segmentation that treats foreground elements as outliers to a smooth background model. By utilizing spatial relationships rather than just color information, the method achieves superior accuracy over traditional clustering techniques. Future work will focus on further optimizing computational complexity for real-time applications and exploring adaptive parameter tuning for diverse content types.

Summary updated

Abstract

This paper considers how to separate text and/or graphics from smooth background in screen content and mixed content images and proposes an algorithm 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. This algorithm separates the background and foreground pixels by trying to fit pixel values in the block into a smooth function using a robust regression method. The inlier pixels that can be well represented with the smooth model will be considered as background, while remaining outlier pixels will be considered foreground. We have also created a dataset of screen content images extracted from HEVC standard test sequences for screen content coding with their ground truth segmentation result which can be used for this task. The proposed algorithm has been tested on the dataset mentioned above and is shown to have superior performance over other methods, such as the hierarchical k-means clustering algorithm, shape primitive extraction and coding, and the least absolute deviation fitting scheme for foreground segmentation.
BibTeX
@misc{minaee2016image,
  author = {Shervin Minaee and Yao Wang},
  title = {{Image Decomposition Using a Robust Regression Approach}},
  year = {2016},
  eprint = {1609.03874},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1609.03874},
}
Figure