Abstract
Subspace learning is an important problem, which has many applications in image and video processing. It can be used to find a low-dimensional representation of signals and images. But in many applications, the desired signal is heavily distorted by outliers and noise, which negatively affect the learned subspace. In this work, we present a novel algorithm for learning a subspace for signal representation, in the presence of structured outliers and noise. The proposed algorithm tries to jointly detect the outliers and learn the subspace for images. We present an alternating optimization algorithm for solving this problem, which iterates between learning the subspace and finding the outliers. This algorithm has been trained on a large number of image patches, and the learned subspace is used for image segmentation, and is shown to achieve better segmentation results than prior methods, including least absolute deviation fitting, k-means clustering based segmentation in DjVu, and shape primitive extraction and coding algorithm.
Introduction
Subspace learning is a fundamental technique in signal processing and computer vision, aimed at finding low-dimensional representations of high-dimensional data. While methods like Principal Component Analysis (PCA) are effective for clean data, they are highly sensitive to outliers. In many practical scenarios, such as screen content processing, outliers are not merely random noise but possess significant structure—for example, sharp text or graphics overlaid on a smooth background. This paper proposes a robust algorithm that jointly learns a signal subspace and identifies these structured outliers.
Methodology
The authors model an observed image patch $x$ as a combination of three distinct components: $$x = P\alpha + s + \epsilon$$ where $P\alpha$ represents the clean signal within a learned subspace $P$, $s$ denotes the sparse structured outliers (foreground), and $\epsilon$ is additive Gaussian noise.
To effectively separate these components, the model incorporates three key regularization priors:
- Smoothness Prior: A penalty on the gradient of the subspace representation ($\nabla P\alpha$) ensures the learned background remains spatially smooth.
- Sparsity: An $\ell_1$-norm penalty on $s$ reflects the assumption that foreground elements occupy a relatively small portion of the image.
- Group-Sparsity: By penalizing groups of pixels, the model encourages the connectivity of detected outliers, matching the physical structure of text and icons.
Optimization via Alternating Minimization
The resulting non-convex optimization problem is solved using an alternating approach. The algorithm iteratively updates the subspace $P$, the coefficients $\alpha$, and the outlier mask $s$ while keeping the other variables fixed. This joint estimation allows the model to leverage its understanding of the background to better isolate the foreground, and vice versa.
Experimental Evaluation
The algorithm was trained on approximately 8,000 overlapping 32x32 patches from screen content images to learn a 64-dimensional subspace. Performance was evaluated against established benchmarks including DjVu (hierarchical k-means), SPEC (shape primitive extraction), and Robust PCA (RPCA).
Key Results
- Precision and Accuracy: The proposed method achieved a precision of 93%, significantly outperforming SPEC (50%) and Hierarchical Clustering (64%). It also reached an F1 score of 89.3%.
- Qualitative Performance: The algorithm excels in scenarios where background and foreground colors overlap, a common failure point for traditional clustering methods.
Conclusion
By integrating group-sparsity and smoothness constraints into a joint subspace learning framework, this work provides a robust solution for image segmentation in the presence of structured outliers. The approach demonstrates superior performance on complex screen content, offering a more reliable alternative to standard clustering and PCA-based techniques.
Summary updated