A Robust Regression Approach for Background/Foreground Segmentation

Shervin Minaee, Haoping Yu, Yao Wang

Abstract

Background/foreground segmentation is a fundamental task in image and video processing, particularly for screen content where text and graphics must be separated from complex backgrounds. We propose a segmentation algorithm that models the background as a smooth function composed of basis functions, while treating foreground elements as sharp discontinuities. By employing robust regression via RANSAC, the algorithm identifies background pixels as inliers and foreground pixels as outliers. Our method demonstrates superior performance over traditional clustering-based approaches, such as the k-means algorithm used in DjVu, especially in scenarios involving smooth gradients and low-contrast foregrounds.

Introduction

The proliferation of virtual desktops and online collaboration tools has heightened the need for efficient screen content compression. Unlike natural images, screen content typically features sharp-edged text and graphics overlaid on backgrounds that are either uniform or smoothly varying. Standard compression standards like JPEG2000 often struggle with these sharp edges, producing high-frequency artifacts that consume excessive bitrate.

A common strategy is to decompose images into three layers: a smooth background, a foreground layer, and a binary mask. However, traditional segmentation techniques, notably the k-means clustering used in the DjVu algorithm, frequently fail when the background exhibits a wide dynamic range (e.g., a gradient) or when foreground colors closely match the background.

Methodology: Segmentation as Robust Regression

We shift the paradigm from color-based clustering to model-based regression.

Modeling the Background

The background is represented as a linear combination of $K$ smooth basis functions. While orthonormal polynomials were considered, Discrete Cosine Transform (DCT) basis functions were selected for their slightly lower Root Mean Square Error (RMSE) in representing typical background variations.

Robust Regression via RANSAC

To distinguish between layers, we utilize Random Sample Consensus (RANSAC). The algorithm randomly samples a subset of pixels to fit the smooth background model. Pixels that conform to this model within an adaptive threshold are classified as "inliers" (background), while those that deviate significantly are labeled "outliers" (foreground). This approach treats foreground text not as a distinct class, but as "noise" that corrupts the underlying smooth signal.

Segmentation of graphical elements from a gradient background. Left: Original. Middle: Background model. Right: Foreground mask.

Hierarchical Optimization

To manage the computational demands of RANSAC, a hierarchical multi-mode system is employed:

  1. Flat Block Detection: Identifies blocks with uniform intensity.
  2. Least-Squares Fit: Attempts a simple fit for the entire block.
  3. Histogram Analysis: Checks for text over constant backgrounds.
  4. Full RANSAC: Invoked for complex blocks.
  5. Quad-tree Decomposition: If RANSAC fails to find a consensus, the block is subdivided, and the process repeats.

Key Results and Performance

The algorithm was rigorously tested on HEVC standard test sequences ("Slideshow," "FlyingGraphics," "Programming," and "MissionControl") and palmprint images.

Comparison with Clustering Methods

In the "Slideshow" sequence, our method successfully segmented text over shaded gradients where hierarchical k-means (DjVu) failed. Traditional clustering often misclassifies parts of a gradient background as foreground, leading to significant artifacts.

Comparison of text extraction. Left: Original. Middle: DjVu (k-means) failure on gradient. Right: Proposed robust regression method.

Low-Contrast and Versatility

The method excels in detecting low-contrast foregrounds, such as small text in "MissionControl" that traditional methods often "wash out." Furthermore, its application to palmprint images demonstrates its ability to extract principal lines and creases from complex skin textures, showcasing its utility beyond screen content.

Conclusion and Future Work

By leveraging the smoothness of backgrounds as a prior, our robust regression approach provides a more resilient segmentation for screen content than color-clustering methods. While RANSAC introduces higher computational complexity, the hierarchical implementation mitigates this for practical use. Future research will explore sparse decomposition ($l_1$ optimization) as a potentially more elegant mathematical alternative for outlier detection.

Summary updated

Abstract

Background/foreground segmentation has a lot of applications in image and video processing. In this paper, a segmentation algorithm is proposed which is mainly designed for text and line extraction in screen content. The proposed method makes 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 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 fit well will be considered as background, while remaining outlier pixels will be considered foreground. This algorithm has been extensively tested on several images from HEVC standard test sequences for screen content coding, and is shown to have superior performance over other methods, such as the k-means clustering based segmentation algorithm in DjVu. This background/foreground segmentation can be used in different applications such as: text extraction, separate coding of background and foreground for compression of screen content and mixed content documents, principle line extraction from palmprint and crease detection in fingerprint images.
BibTeX
@misc{minaee2014robust,
  author = {Shervin Minaee and Haoping Yu and Yao Wang},
  title = {{A Robust Regression Approach for Background/Foreground Segmentation}},
  year = {2014},
  eprint = {1412.5126},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1412.5126},
}
Figure