A Decomposition in Low rank plus Additive Matrices Approach

Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset

Recent research on problem formulations based on decomposition into low-rank plus sparse matrices shows a suitable framework to separate moving objects from the background. This work aims to initiate a rigorous and comprehensive review of the similar problem formulations in robust subspace learning and tracking based on decomposition into low-rank plus additive matrices for testing and ranking existing algorithms for background/foreground separation. For this, we first provide a preliminary review of the recent developments in the different problem formulations which allows us to define a unified view that we called Decomposition into Low-rank plus Additive Matrices (DLAM). Then, we examine carefully each method in each robust subspace learning/tracking frameworks with their decomposition, their loss functions, their optimization problem and their solvers. Furthermore, we investigate if incremental algorithms and real-time implementations can be achieved for background/foreground separation. Finally, experimental results on a large-scale dataset called Background Models Challenge (BMC 2012) show the comparative performance of 32 different robust subspace learning/tracking methods.

T. Bouwmans. A. Sobral, S. Javed, S. Jung, E. Zahzah, "Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset", Computer Science Review, February 2017.

Robust Principal Component Analysis (RPCA)

Robust Principal Component Analysis for Background Subtraction: Systematic Evaluation and Comparative Analysis

Principal Component Analysis (PCA) has been used to model the background by significantly reducing the data’s dimension. To perform PCA, different Robust Principal Components Analysis (RPCA) models have been recently developped in the literature. The background sequence is then modeled by a low rank subspace that can gradually change over time, while the moving foreground objects constitute the correlated sparse outliers. However, authors compare their algorithm only with the PCA (Oliver et al. (1999)) or another RPCA model. Furthermore, the evaluation is not made with the datasets and the measures currently used in the field of background subtraction. Considering all of this, we propose to evaluate RPCA models in the field of video surveillance. Contributions of this chapter can be summarized as follows: 1) A survey regarding robust principal component analysis, and 2) An evaluation and comparison on different videosurveillance datasets.

C. Guyon, T. Bouwmans, E. Zahzah, “Robust Principal Component Analysis for Background Subtraction: Systematic Evaluation and Comparative Analysis”, INTECH, Principal Component Analysis, Book 1, Chapter 12, page 223-238, March 2012.

Robust PCA via Principal Component Pursuit: A Review for a Comparative Evaluation in Video Surveillance

Foreground detection is the first step in video surveillance system to detect moving objects. Recent research on subspace estimation by sparse representation and rank minimization represents a nice framework to separate moving objects from the background. Robust Principal Component Analysis (RPCA) solved via Principal Component Pursuit decomposes a data matrix A in two components such that A= L+S, where L is a low-rank matrix and S is a sparse noise matrix. The background sequence is then modeled by a low-rank subspace that can gradually change over time, while the moving foreground objects constitute the correlated sparse outliers. To date, many efforts have been made to develop Principal Component Pursuit (PCP) methods with reduced computational cost that perform visually well in foreground detection. However, no current algorithm seems to emerge and to be able to simultaneously address all the key challenges that accompany real-world videos. This is due, in part, to the absence of a rigorous quantitative evaluation with synthetic and realistic large-scale dataset with accurate ground truth providing a balanced coverage of the range of challenges present in the real world. In this context, this work aims to initiate a rigorous and comprehensive review of RPCA-PCP based methods for testing and ranking existing algorithms for foreground detection. For this, we first review the recent developments in the field of RPCA solved via Principal Component Pursuit. Furthermore, we investigate how these methods are solved and if incremental algorithms and real-time implementations can be achieved for foreground detection. Finally, experimental results on the Background Models Challenge (BMC) dataset which contains different synthetic and real datasets show the comparative performance of these recent method. (more information)

T. Bouwmans, E. Zahzah, “Robust PCA via Principal Component Pursuit: A Review for a Comparative Evaluation in Video Surveillance”, Special Isssue on Background Models Challenge, Computer Vision and Image Understanding, CVIU 2014, Volume 122, pages 22–34, May 2014.

T. Bouwmans, E. Zahzah,"Robust Principal Component Analysis via Decomposition into Low-rank and Sparse Matrices: An overview", Handbook on "Robust Low-Rank and Sparse Matrix Decomposition: Applications in Image and Video Processing", CRC Press, Taylor and Francis Group, May 2016.

Low-rank and block-sparse matrix decomposition

Background subtraction is the first step in video surveillance system to detect moving objects. Recent research on reconstructive subspace learning by Robust Principal Component Analysis (RPCA) shows a nice framework to separate moving objects from background. RPCA decomposes a data matrix A in two components such that A=L+S, where L is a low-rank matrix and S is a noise matrix. The background sequence is then modeled by a low-rank subspace that can gradually change over time, while the moving foreground objects constitute the correlated sparse outliers. In this work, we investigate how these methods can be robustly applied to detect moving objects. (more information)

C. Guyon, T. Bouwmans, E. Zahzah, "Foreground detection based on low-rank and block-sparse matrix decomposition", IEEE International Conference on Image Processing, ICIP 2012, Orlando, Florida, September 2012.

Low-rank and sparse decomposition via IRLS

This works proposes to use a low-rank matrix factorization with IRLS scheme (Iteratively Reweighted Least Squares), and to address in the minimization process the spatial connexity and the temporal sparseness of moving objects. (more information)

C. Guyon, T. Bouwmans, E. Zahzah, “Foreground Detection via Robust Low Rank Matrix Decomposition including Spatio-Temporal Constraint”, International Workshop on Background Model Challenges, ACCV 2012, pages 315-320, Daejeon, Korea, November 2012.

C. Guyon, T. Bouwmans, E. Zahzah, “Foreground Detection via Robust Low Rank Matrix Factorization including Spatial Constraint with Iterative Reweighted Regression”, International Conference on Pattern Recognition, ICPR 2012, Tsukuba, Japan, November 2012.

C. Guyon, T. Bouwmans, E. Zahzah, “Moving Object Detection via Robust Low Rank Matrix Decomposition with IRLS scheme”, International Symposium on Visual Computing, ISVC 2012,pages 665–674, Rethymnon, Crete, Greece, July 2012.

Low-rank decomposition via ADM

This works proposes to use a low-rank matrix factorization with ADM scheme (Alternating Direction Method) for moving objects detection. (more information)

C. Guyon, T. Bouwmans, E. Zahzah, “Moving Object Detection by Robust PCA solved via a Linearized Symmetric Alternating Direction Method”, International Symposium on Visual Computing, ISVC 2012, pages 427-436, Rethymnon, Crete, Greece, July 2012.

C. Guyon, T. Bouwmans, E. Zahzah, "Foreground Detection by Robust PCA solved via a Linearized Alternating Direction Method", International Conference on Image Analysis and Recognition, ICIAR 2012, pages 115-122, Aveiro, Portugal, June 2012.

Stochastic RPCA

This paper presents a robust foreground detection algorithm via Online Robust PCA (OR-PCA) using image decomposition along with continuous constraint such as Markov Random Field (MRF). OR-PCA with good initialization scheme using image decomposition approach improves the accuracy of foreground detection and the computation time as well. Moreover, solving MRF with graph-cuts exploits structural information using spatial neighborhood system and similarities to further improve the foreground segmentation in highly dynamic backgrounds. Experimental results on challenging datasets such as Wallflower, I2R, BMC 2012 and Change Detection 2014 dataset demonstrate that our proposed scheme signi.cantly outperforms the state of the art approaches and works e.ectively on a wide range of complex background scenes. (more information)

S. Javed, S. Oh, T. Bouwmans, S. Jung, "Stochastic RPCA for Background/Foreground Separation", Handbook on "Robust Low-Rank and Sparse Matrix Decomposition: Applications in Image and Video Processing", CRC Press, Taylor and Francis Group, May 2016.

S. Javed, S. Oh, T. Bouwmans, S. Jung, "Robust Background Subtraction to Global Illumination Changes via Multiple Features based OR-PCA with MRF", Journal of Electronic Imaging, 2015.

S. Javed, T. Bouwmans, S. Jung, “Improving OR-PCA via Smoothed Spatially-Consistent Low-rank Modeling for Background Subtraction”, ACM Symposium on Applied Computing, SAC 2017, 2017.

S. Javed, T. Bouwmans, S. Jung, “Combining ARF and OR-PCA Background Subtraction of Noisy Videos”, International Conference in Image Analysis and Applications, ICIAP 2015, Genova, Italy, September 2015.

S. Javed, T. Bouwmans, S. Jung, "Depth Extended Online RPCA with Spatiotemporal Constraints for Robust Background Subtraction", Korea-Japan Workshop on Frontiers of Computer Vision, FCV 2015, Mokpo, South Korea, January 2015.

S. Javed, A. Sobral, T. Bouwmans, S. Jung, "OR-PCA with Dynamic Feature Selection for Robust Background Subtraction", ACM Symposium On Applied Computing, SAC 2015, Salamanca, Spain, April 2015.

S. Javed, A. Sobral, S. Oh, T. Bouwmans, S. Jung, “OR-PCA with MRF for Robust Foreground Detection in Highly Dynamic Backgrounds”, Asian Conference on Computer Vision, ACCV 2014, Singapore, November 2014.

Double-constrained RPCA

This paper, a double-constrained Robust Principal Component Analysis (RPCA), named SCM-RPCA (Shape and Confidence Mapbased RPCA), is proposed to improve the object foreground detection in maritime scenes. The sparse component is constrained by shape and confidence maps both extracted from spatial saliency maps. The experimental results in the UCSD and MarDT data sets indicate a better enhancement of the object foreground mask when compared with some related RPCA methods. (more information)

A. Sobral, T. Bouwmans, E. Zahzah, “Double-constrained RPCA based on Saliency Maps for Foreground Detection in Automated Maritime Surveillance”, ISBC 2015 Workshop conjunction with AVSS 2015, Karlsruhe, Germany,2015.

Structured RPCA

When the size of the input data grows and due to the lack of sparsity constraints, RPCA methods cannot cope with the real-time challenges and always show a weak performance due to the erroneous foreground regions. In order to address the above mentioned issues, this paper presents a superpixel based matrix decomposition method together with maximum norm (max-norm) regularizations and structured sparsity constraints. The low-rank component estimated from each homogeneous region is more perfect, reliable, and efficient, since each superpixel provides different characteristics with a reduced value of rank. Online max-norm based matrix decomposition is employed on each segmented superpixel to separate the low rank and initial outliers support. And then, the structured sparsity constraints such as the generalized fussed lasso (GFL) are adopted for exploiting structural information continuously as the foreground pixels are both spatially connected and sparse. We propose an online single unified optimization framework for detecting foreground and learning the background model simultaneously. (more information)

S. Javed, S. Oh, A. Sobral, T. Bouwmans , S. Jung, "Background Subtraction via Superpixel-based Online Matrix Decomposition with Structured Foreground Constraints", Workshop on Robust Subspace Learning and Computer Vision, ICCV 2015, Santiago, Chile, December 2015.

Structured Sparse RPCA

This works proposes a spatiotemporal structured sparse RPCA algorithm for moving objects detection, where we impose spatial and temporal regularization on the sparse component in the form of graph Laplacians. Each Laplacian corresponds to a multi-feature graph constructed over superpixels in the input matrix. We enforce the sparse component to act as eigenvectors of the spatial and temporal graph Laplacians while minimizing the RPCA objective function. These constraints incorporate a spatiotemporal subspace structure within the sparse component. Thus, we obtain a novel objective function for separating moving objects in the presence of complex backgrounds. The proposed objective function is solved using a linearized alternating direction method of multipliers based batch optimization. Moreover, we also propose an online optimization algorithm for real-time applications.

S. Javed, A. Mahmood, T. Bouwmans, S. Jung, "Superpixels based Manifold Structured Sparse RPCA for Moving Object Detection", International Workshop on Activity Monitoring by Multiple Distributed Sensing, BMVC 2017, London, UK, September 2017.

S. Javed, A. Mahmood, S. Al-Maadeed, N. Rajpoot, T. Bouwmans, S. Jung,"Moving Object Detection in Complex Scene using Spatio-temporal Structured-Sparse RPCA", IEEE Transactions on Image Processing, 2018.

Graph Regularized Spatiotemporal RPCA

This works investigates the performance of online Spatiotemporal RPCA (SRPCA) algorithm for moving object detection using RGB-D videos. SRPCA is a graph regularized algorithm which preserves the low-rank spatiotemporal information in the form of dual spectral graphs. This graph regularized information is then encoded into the objective function which is solved using online optimization.

S. Javed, T. Bouwmans, M. Sultana, S. Jung, "Moving Object Detection on RGB-D Videos using Graph Regularized Spatiotemporal RPCA", International Workshop on Background learning for detection and tracking from RGBD videos, ICIAP 2017, Catani, Italy, September 2017.

Spatio-temporal Sparse Subspace Clustering

This works proposes to incorporate the spatial and temporal sparse subspace clustering into the RPCA framework. To that end, we compute a spatial and temporal graph for a given sequence using motion-aware correlation coefficient. The information captured by both graphs is utilized by estimating the proximity matrices using both the normalized Euclidean and geodesic distances. The low-rank component must be able to efficiently partition the spatiotemporal graphs using these Laplacian matrices. Embedded with the RPCA objective function, these Laplacian matrices constrain the background model to be spatially and temporally consistent,both on linear and nonlinear manifolds. The solution of the proposed objective function is computed by using the LADMAP optimization scheme. (more information)

S. Javed, A. Mahmood, T. Bouwmans, S. Jung, "Background-Foreground Modeling Based on Spatio-temporal Sparse Subspace Clustering", IEEE Transactions on Image Processing, Volume 26, No. 12, pages 5840-5854, December 2017

Robust Matrix Completion (RMC)

Evaluation of Robust Matrix Completion for Background Initialization

This work aims to investigate the background model initialization as a matrix completion problem. Thus, we consider the image sequence (or video) as a partially observed matrix. First, a simple joint motiondetection and frame-selection operation is done. The redundant frames are eliminated, and the moving regions are represented by zeros in our observation matrix. The second stage involves evaluating nine popular matrix completion algorithms with the Scene Background Initialization (SBI) data set, and analyze them with respect to the background model challenges. The experimental results shows the good performance of LRGeomCG method over its direct competitors. (more information)

A. Sobral, T. Bouwmans, E. Zahzah, "Comparison of Matrix Completion Algorithms for Background Initialization in Videos”, SBMI 2015 Workshop in conjunction with ICIAP 2015, Genova, Italy, September 2015.

Spatio-temporal Low-rank Matrix Completion for Background Initialization

This work presents a spatio-temporal low-rank modeling method on dynamic video clips for estimating the robust background model. The proposed method encodes spatio-temporal constraints by regularizing spectral graphs. Initially a motion-compensated binary matrix is generated using optical flow information to remove redundant data and to create a set of dynamic frames from the input video sequence. Then two graphs are constructed, one between frames for temporal consistency and the other between features for spatial consistency, to encode the local structure for continuously promoting the intrinsic behavior of the low-rank model against outliers. These two terms are then incorporated in the iterative matrix completion framework for improved segmentation of background. Rigorous evaluation on severely occluded and dynamic background sequences, demonstrates the superior performance of the proposed method over state-of-the art approaches. (more information)

S. Javed, A. Mahmood, T. Bouwmans, S. Jung, “Spatiotemporal Low-rank Modeling for Complex Scene Background Initialization", IEEE Transactions on Circuits and Systems for Video Technology, November 2016.

S. Javed, S. Jung, A. Mahmood, T. Bouwmans, "Motion-Aware Graph Regularized RPCA for Background Modeling of Complex Scenes", Scene Background

Modeling Contest, International Conference on Pattern Recognition, ICPR 2016, December 2016.