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.
Hierarchical Optimization
To manage the computational demands of RANSAC, a hierarchical multi-mode system is employed:
- Flat Block Detection: Identifies blocks with uniform intensity.
- Least-Squares Fit: Attempts a simple fit for the entire block.
- Histogram Analysis: Checks for text over constant backgrounds.
- Full RANSAC: Invoked for complex blocks.
- 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.
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