Screen Content Image Segmentation Using Sparse Decomposition and Total Variation Minimization

Shervin Minaee, Yao Wang

Abstract

Sparse decomposition has been widely used for different applications, such as source separation, image classification, image denoising and more. This paper presents a new algorithm for segmentation of an image into background and foreground text and graphics using sparse decomposition and total variation minimization. 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 can be modeled with a sparse component overlaid on the smooth background. The background and foreground are separated using a sparse decomposition framework regularized with a few suitable regularization terms which promotes the sparsity and connectivity of foreground pixels. This algorithm has been tested on a dataset of images extracted from HEVC standard test sequences for screen content coding, and is shown to have superior performance over some prior methods, including least absolute deviation fitting, k-means clustering based segmentation in DjVu and shape primitive extraction and coding (SPEC) algorithm.

Introduction

Segmenting "screen content"—images containing computer-generated text and graphics—presents a distinct challenge compared to natural scenes. In applications such as Screen Content Coding (SCC) for video compression or automated text extraction, it is critical to accurately separate the foreground (text and lines) from the background (often smooth gradients or solid colors).

Existing methodologies frequently encounter two primary issues:

  1. Color Overlap: Traditional clustering techniques, such as the k-means algorithm used in DjVu, often fail when foreground and background elements share similar color intensities.
  2. Isolated Noise: Simple sparse decomposition models tend to treat foreground pixels as independent entities. This lack of spatial awareness leads to "salt-and-pepper" noise, where isolated pixels are incorrectly identified as foreground.

This paper proposes a model that recognizes foreground elements as both sparse and connected structures.

Methodology

The proposed framework represents an image block ($f$) as the sum of a smooth background ($P\alpha$) and a foreground component ($s$): $$f = P\alpha + s$$

Background and Foreground Modeling

  • Smooth Background ($P\alpha$): The background is modeled as a linear combination of 2D Discrete Cosine Transform (DCT) basis functions. To prevent the background model from absorbing foreground pixels, an $\ell_1$ penalty is applied to the coefficients ($\alpha$), ensuring a sparse representation using only essential bases.
  • Sparse Foreground ($s$): An $\ell_1$ penalty is applied to the foreground component $s$, reflecting the assumption that text and graphics occupy a relatively small portion of the image.
  • Total Variation (TV) Minimization: To address the issue of isolated noise, a TV penalty is added to the foreground component ($TV(s)$). This encourages the algorithm to form connected structures, such as the strokes of a letter, by penalizing isolated pixel transitions.

Optimization via ADMM

The resulting optimization problem is solved using the Alternating Direction Method of Multipliers (ADMM). This approach breaks the complex, non-convex problem into smaller, iterative sub-problems that can be solved efficiently through techniques like soft-thresholding.

The ADMM-based optimization algorithm for sparse decomposition and TV minimization.

Experimental Evaluation

The algorithm was evaluated on a specialized dataset consisting of 332 image blocks (64x64 pixels) extracted from standard HEVC test sequences. Ground truth labels were manually generated and independently refined to ensure high accuracy. The authors have made both the dataset and the MATLAB implementation publicly available.

Results and Discussion

The proposed method was compared against three benchmarks: SPEC, Hierarchical Clustering (DjVu), and Least Absolute Deviation (LAD) fitting.

Quantitative Performance

Algorithm Precision Recall F1 Score
SPEC 50% 64% 56.1%
Hierarchical Clustering 64% 69% 66.4%
Least Absolute Deviation 91.4% 87% 89.1%
Proposed Algorithm 94.3% 88% 90.9%

The proposed method achieves a significant improvement in Precision, indicating a substantial reduction in false positives (noise) while maintaining high recall.

Qualitative Analysis

The inclusion of the TV norm proves to be the critical factor in performance. By enforcing connectivity, the algorithm effectively filters out the "noisy" results common in previous sparse models. Unlike intensity-based methods like k-means, this approach leverages the smoothness of pixel groups, providing robustness in cases where text and background colors are similar.

Visual comparison of segmentation results across different algorithms. The bottom row demonstrates the proposed method's ability to produce clean, connected foreground masks.

Conclusion

While the proposed algorithm demonstrates superior performance, it relies on manual hyperparameter tuning for $\lambda_1, \lambda_2,$ and $K$. Future work will focus on automating parameter selection and reducing computational complexity to better suit real-time video encoding applications. Additionally, exploring learned dictionaries instead of fixed DCT bases could further enhance adaptability to diverse UI elements and font styles.

Summary updated

Abstract

Sparse decomposition has been widely used for different applications, such as source separation, image classification, image denoising and more. This paper presents a new algorithm for segmentation of an image into background and foreground text and graphics using sparse decomposition and total variation minimization. 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 can be modeled with a sparse component overlaid on the smooth background. The background and foreground are separated using a sparse decomposition framework regularized with a few suitable regularization terms which promotes the sparsity and connectivity of foreground pixels. This algorithm has been tested on a dataset of images extracted from HEVC standard test sequences for screen content coding, and is shown to have superior performance over some prior methods, including least absolute deviation fitting, k-means clustering based segmentation in DjVu and shape primitive extraction and coding (SPEC) algorithm.
BibTeX
@misc{minaee2016screen,
  author = {Shervin Minaee and Yao Wang},
  title = {{Screen Content Image Segmentation Using Sparse Decomposition and Total Variation Minimization}},
  year = {2016},
  eprint = {1602.02434},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.02434},
}
Figure