Abstract
Classical principal component analysis (PCA) is not robust when the data contain sparse outliers. The use of the $\ell_1$ norm in the Robust PCA (RPCA) method successfully eliminates this weakness of PCA in separating the sparse outliers. Here we propose a weighted low rank (WLR) method, where a simple weight is inserted inside the Frobenius norm. We demonstrate how this method tackles often computationally expensive algorithms that rely on the $\ell_1$ norm. As a proof of concept, we present a background estimation model based on WLR, and we compare the model with RPCA method and with other state-of-the-art algorithms used for background estimation. Our empirical validation shows that the weighted low-rank approximation we propose here can perform as well as or better than that of RPCA and other state-of-the-art algorithms.
Introduction
Background estimation—the task of separating static or slow-moving backgrounds from moving foreground objects—is a fundamental challenge in computer vision. While Principal Component Analysis (PCA) is a standard tool for low-rank subspace modeling, its sensitivity to outliers (moving objects) necessitates more robust approaches. Robust PCA (RPCA) addresses this by employing the $\ell_1$ norm to isolate sparse outliers. However, RPCA is computationally intensive and often suffers from "ghosting" artifacts where stationary foreground objects are incorrectly absorbed into the background model.
Proposed Methodology: Weighted Low Rank (WLR)
We propose a Weighted Low Rank (WLR) framework that replaces the expensive $\ell_1$ penalty with a weighted Frobenius norm. The objective is to minimize: $$\min_{X} \|(A - X) \odot W\|_F^2 \quad \text{subject to} \quad \text{rank}(X) \le r$$ where $W$ is a weight matrix that prioritizes background-heavy data.
Algorithmic Innovations
- Iterative Optimization: Since no closed-form solution exists for the weighted low-rank problem, the researchers developed an efficient algorithm based on the alternating direction method. This approach decomposes the problem into sub-problems that are solved explicitly and quickly.
- Automatic Weight Learning: A key contribution is a heuristic to automatically learn the weight matrix $W$. By analyzing frame-wise statistics, the algorithm identifies frames with minimal foreground activity and assigns them higher weights to "lock in" the background model.
Experimental Results
The WLR method was evaluated against state-of-the-art RPCA solvers (e.g., APG, iEALM) across several benchmarks, including the Stuttgart Synthetic Video and Wallflower datasets.
Performance and Efficiency
WLR demonstrates a significant speed advantage, achieving a 5x to 7x speedup over standard RPCA solvers. For a 600-frame sequence, WLR completed in approximately 23 seconds, compared to 107 seconds for APG and 160 seconds for iEALM. In terms of accuracy, WLR achieved a 3.25% gain in the Area Under the ROC Curve (AUC) over APG in the "Basic" Stuttgart scenario.
Qualitative Advantages
WLR effectively handles "static foreground" traps. While RPCA methods often allow stationary objects to fade into the background (creating "ghosts"), WLR maintains a clean background estimate by leveraging learned weights.
Conclusion
The Weighted Low Rank approach offers a computationally efficient alternative to $\ell_1$-based robust methods. By incorporating learned weights into the Frobenius norm, the algorithm achieves superior background subtraction quality and significant speed improvements. Future work will focus on automating parameter selection for rank and weight distribution to enhance generalizability across diverse video scenarios.
Summary updated