PaperlayerView exact revision on arXiv

Source-linked AI summary

Total Variation Regularized Tensor RPCA for Background Subtraction from Compressive Measurements

Wenfei Cao, Yao Wang, Jian Sun, Deyu Meng, Can Yang, Andrzej Cichocki, Zongben Xu

arXiv:1503.01868v4cs.CV

TL;DR

Background subtraction from compressive measurements is an ill-posed inverse problem requiring video priors to recover and separate background and foreground. The paper proposes tensor RPCA models that combine Tucker decomposition, 3D total variation, and patch-group modeling, reporting superior performance over existing methods across synthetic and real-world data.

  • Problem

    Background subtraction from compressive measurements requires recovering and separating video background and foreground from undersampled measurements, an ill-posed inverse problem.

  • Method

    TenRPCA uses Tucker decomposition for spatio-temporal background correlations, 3D total variation for foreground continuity, and patch-group tensor modeling through H-TenRPCA and PG-TenRPCA.

  • Results

    The proposed models consistently outperform compared methods as sampling ratios decrease, with superior performance demonstrated on synthetic and real-world video data.

  • Takeaways & Limitations

    Tensor representations preserve video spatial-temporal structure while jointly modeling background correlations and foreground continuity for compressive background subtraction.

Abstract

from arXiv · show

Background subtraction has been a fundamental and widely studied task in video analysis, with a wide range of applications in video surveillance, teleconferencing and 3D modeling. Recently, motivated by compressive imaging, background subtraction from compressive measurements (BSCM) is becoming an active research task in video surveillance. In this paper, we propose a novel tensor-based robust PCA (TenRPCA) approach for BSCM by decomposing video frames into backgrounds with spatial-temporal correlations and foregrounds with spatio-temporal continuity in a tensor framework. In this approach, we use 3D total variation (TV) to enhance the spatio-temporal continuity of foregrounds, and Tucker decomposition to model the spatio-temporal correlations of video background. Based on this idea, we design a basic tensor RPCA model over the video frames, dubbed as the holistic TenRPCA model (H-TenRPCA). To characterize the correlations among the groups of similar 3D patches of video background, we further design a patch-group-based tensor RPCA model (PG-TenRPCA) by joint tensor Tucker decompositions of 3D patch groups for modeling the video background. Efficient algorithms using alternating direction method of multipliers (ADMM) are developed to solve the proposed models. Extensive experiments on simulated and real-world videos demonstrate the superiority of the proposed approaches over the existing state-of-the-art approaches.

I. INTRODUCTION

The paper frames background subtraction from compressive measurements as an ill-posed task requiring video-prior modeling, then introduces tensor RPCA models that preserve spatial-temporal structure and exploit background correlation, foreground continuity, and nonlocal patch similarity.

  • Background subtraction separates video backgrounds from moving objects and supports applications including moving-object detection and surveillance tracking.
  • Conventional systems separately acquire, fully sample, encode, decode, and subtract backgrounds, creating large storage requirements.
  • BSCM reconstructs video and separates moving objects from background using as few compressive measurements as possible, making it a heavily ill-posed inverse problem.
  • TenRPCA represents video frames or patches as tensors, using Tucker decomposition for background correlation and 3D TV for foreground continuity.
  • The paper identifies nonlocal 3D-patch similarity, foreground spatio-temporal continuity, and background spatiotemporal correlation as key surveillance-video priors.
  • The red and blue singular-value curves show strong temporal correlation among background frames but weak spatial correlation within individual frames.
  • H-TenRPCA models the background as one tensor, whereas PG-TenRPCA jointly decomposes groups of similar 3D patches to capture nonlocal self-similarity.
  • ADMM-based algorithms solve the proposed models, which achieve superior performance over existing methods, especially at very low sampling ratios.

III. THE GENERAL FRAMEWORK OF THE BSCM

The BSCM framework represents a video volume as a tensor, obtains compressive measurements, and reconstructs and separates background and foreground by solving a regularized inverse problem. Tensor notation and operations support the proposed TenRPCA models.

  • Video Volume: A video volume is a 3-order tensor whose height, width, and time modes contain frame matrices.It is decomposed as X0 = X1 + X2, where X1 is background and X2 is foreground.
  • Compressive Operator: Compressive measurements y are generated by applying a given operator A to the vectorized video volume x0.The measurement vector has length M.
  • Compressive Operator: The framework uses randomly permuted Walsh-Hadamard or noiselet operators, with random permutation and downsampling components.Experiments mainly use frame-by-frame encoding, which collects measurements from individual frames and concatenates them.
  • Reconstruction and Separation: Recovering the video while separating background and foreground is formulated as a heavily ill-posed inverse problem requiring prior-knowledge regularization.The regularizers model background and foreground priors, balanced by a trade-off parameter.
  • Tensor RPCA Models: The paper instantiates this framework with tensor RPCA models that use tensor algebra to encode surveillance-video priors.The proposed models include holistic and patch-based background representations.
  • Tensor Basics: The notation defines tensors, matrices, vectors, scalars, fibers, slices, vectorization, tensorization, matricization, multilinear rank, and mode-n multiplication.The Frobenius norm and tensor inner product are also included among the stated operations and quantities.

A. Tensor Basics

The section introduces tensor representations and the decomposition of video background into ideal low-rank content and disturbance. This decomposition separates modeling the foreground from modeling background structure.

  • Tensor Basics: A tensor is a multi-index numerical array, with order equal to its number of modes or dimensions.Vectors and matrices are tensors of order one and two, respectively.
  • General Decomposition Model: The video background is decomposed into an ideal low-rank component L and disturbance E, so X0 = X2 + E + L.This refines the assumption that the background is strictly low rank when dynamic disturbances are present.
  • General Decomposition Model: The model assigns prior terms to foreground and background and focuses on specifying these terms from video structure.The foreground and background priors are represented by Ω2(x2) and Φ(L).

C. Foreground Modeling

Foreground modeling uses spatio-temporal continuity to distinguish contiguous moving objects from disconnected background disturbances. A 3D total-variation regularizer measures differences across spatial and temporal directions.

  • Foreground Prior: Foreground objects commonly occupy contiguous spatial regions and follow temporally smooth motion traces.These structures are termed the spatio-temporal continuity prior.
  • 3D Total Variation: The proposed 3D-TV quantity measures absolute intensity differences between a foreground voxel and neighboring voxels across spatial and temporal directions.Summing this quantity over all voxels yields the 3D-TV regularizer.
  • 3D Total Variation: Video boundaries are treated as circular so that 3D-TV is defined for boundary voxels.This is an explicit modeling assumption of the formulation.
  • 3D Total Variation: The 3D-TV construction uses horizontal, vertical, and temporal difference operators and concatenates their outputs.The vectorized formulation represents these differences through Dx.

D. Background Modeling

Background modeling captures spatio-temporal correlations with Tucker decompositions in either a holistic tensor or groups of similar 3D patches. The patch-group model shares temporal factors while exploiting within-group similarity.

  • Holistic Background Modeling: Strong temporal correlation and weaker spatial correlations motivate low-rank tensor-unfolding models for video background.The holistic representation uses Tucker factors and a core tensor to reconstruct the ideal background.
  • Holistic Background Modeling: Tensor modeling captures both spatial and temporal background correlations, unlike matrix modeling after frame vectorization.The paper states that this can reconstruct more accurate video backgrounds.
  • Patch-Based Background Modeling: Patch-based modeling extends nonlocal self-similarity to 3D patches for approximately reconstructing the ideal video background.Similar patches are grouped because their structures imply correlation.
  • Patch-Based Background Modeling: For nonoverlapping patches, reconstructing the background does not require the averaging operation used for overlapping patches.The nonoverlapping case reduces the relevant operator product to an identity matrix.
  • Patch-Based Background Modeling: Each patch cluster is collected into a 4-order tensor whose temporal and patch modes are expected to be low rank.The tensor contains patches of size w × w × D × N, where N is the cluster size.
  • Patch-Based Background Modeling: Joint Tucker decompositions model patch groups with a shared temporal factor matrix across clusters.The shared temporal factor ensures low rank in the temporal mode for the whole background.

E. Reconstruction and Separation Models

The paper instantiates BSCM with two tensor RPCA models: H-TenRPCA uses a holistic tensor background, while PG-TenRPCA models groups of similar patches. Both combine foreground modeling with tensor-based background reconstruction, but the optimization is non-convex.

  • H-TenRPCA: H-TenRPCA integrates the video-foreground model with a Tucker-based holistic tensor background model.The factor matrices are constrained to have orthogonal columns.
  • PG-TenRPCA: PG-TenRPCA integrates the video-foreground model with a patch-based tensor background model for groups of similar patches.Its factor matrices are likewise constrained to have orthogonal columns.
  • Optimization scope: Both proposed models are non-convex, so the algorithms can only seek local solutions.This motivates the subsequent development of iterative optimization algorithms.

V. OPTIMIZATION ALGORITHMS

The optimization algorithms solve H-TenRPCA through multi-block ADMM, alternating updates for the reconstruction, Tucker factors, foreground, background, and auxiliary variables. Several subproblems exploit standard numerical routines, including conjugate gradients, HOOI, soft shrinkage, and 3D FFT diagonalization.

  • ADMM formulation: H-TenRPCA is optimized using a multi-block ADMM formulation that alternately minimizes over its variables.The constrained model is converted to an augmented-Lagrangian problem with alternating variable updates.
  • Subproblem updates: The x0 update solves a linear system using conjugate gradients, with a closed-form solution when AA* = I.The system incorporates the measurement operator and the Tucker-reconstructed background.
  • Subproblem updates: The Tucker core and factor updates form a separate subproblem handled through HOOI.This update targets the low-dimensional tensor representation of the background.
  • Subproblem updates: The e update uses a soft shrinkage operator, while the x2 update is solved through a 3D FFT-based diagonalization.The FFT denominator can be pre-calculated outside the main loop to avoid extra computational cost.
  • Subproblem updates: The f subproblem is solved by soft shrinkage within the ADMM iteration.This update applies the foreground regularization through a standard proximal operation.

6) updating multipliers:

The H-TenRPCA algorithm alternates primal-variable and multiplier updates until convergence, using adaptive penalty parameters. Its initialization specifies Tucker ranks, an adjoint-measurement reconstruction, and zero initialization for remaining variables.

  • Adaptive penalties: The penalty parameters use an adaptive updating scheme based on the current and previous measurement residuals.βy is initialized from the measurements and then updated according to the residual change.
  • Algorithm 1: Algorithm 1 updates x0, the Tucker variables, e, x2, f, multipliers, and related parameters in an iterative loop.The loop terminates when the algorithm converges.
  • Initialization: The algorithm initializes r1 and r2 as ceil(H × 0.65) and ceil(W × 0.65), respectively.The third Tucker rank r3 is supplied as an algorithm parameter.
  • Initialization: The initial background approximation uses a Tucker approximation of Ten(A*(y)), with x2 set to the residual and other variables set to zero.The outputs are x0, x2, and x1 = Vec(L).

B. Optimization Algorithm for PG-TenRPCA

PG-TenRPCA modifies the H-TenRPCA algorithm by replacing its Tucker update with a patch-group optimization solved by joint HOOI. Patch clustering is periodically refreshed, but the resulting non-convex, non-separable problem has local-minimum and convergence limitations.

  • Model-specific modification: PG-TenRPCA replaces H-TenRPCA’s Tucker subproblem with an optimization over patch-group tensor decompositions.The modified update is inserted at step 3 of Algorithm 1.
  • Joint HOOI: The patch-group optimization alternately updates the tensor cores and factor matrices until convergence.The updates include Gp, U1p, U2p, U4p, and the shared U3.
  • Joint HOOI: Joint HOOI is the iterative procedure used to minimize the PG-TenRPCA patch-group objective.Algorithm 2 takes initialized factor matrices and patch-group data as input and returns updated factors and cores.
  • Patch grouping: Patch clustering is updated periodically, for example every 8 iterations, with the first clustering performed on an initialized background.The clustering updates the patch-group assignments Rp.
  • Limitations: The PG-TenRPCA optimization is non-convex and non-separable, so many local minimizers may exist and suitable initialization is important.Convergence of multi-block ADMM for this problem class is not guaranteed according to the authors.

C. Implementation Issues

The experiments specify parameter settings for the proposed models, evaluate foreground detection and reconstruction, and use synthetic and real-world video datasets. Real videos span static, shadow, and dynamic-background scenes.

  • Parameter settings: The H-TenRPCA algorithm uses r1 and r2 for spatial redundancy, r3 for temporal redundancy, and λ to trade off disturbance and foreground modeling.The experiments set r1 = ceil5(H × 0.65) and r2 = ceil(W × 0.65).
  • Parameter settings: The PG-TenRPCA algorithm requires patch, search-window, similar-patch, sliding-distance, rank, and trade-off parameters.Empirical settings include w = 8, d = 7, S = 36, and N = 45; r1 and r2 are set to 8.
  • Evaluation measures: Foreground detection is evaluated with F-measure, while reconstruction accuracy is evaluated with PSNR and SSIM averaged over video frames.Higher F-measure, PSNR, and SSIM values indicate better performance.
  • Datasets: Synthetic data are constructed from SABS background and foreground sequences, with 128 frames scaled to 128×128 grayscale video volumes.The original volume combines a true background with transformed foreground intensity values.
  • Datasets: Real-world videos come from CAVIAR, I2R, UCSD, and CD.net and cover static background, shadow, and dynamic background categories.Each tested video contains 128 grayscale frames.

B. Empirical Analysis for Algorithm Convergence

The proposed H-TenRPCA and PG-TenRPCA algorithms were empirically assessed for convergence on synthetic and real videos, alongside reconstruction and separation performance under varying sampling ratios. The algorithms stabilized at higher iteration counts, while tensor models remained effective at low sampling ratios and PG-TenRPCA generally outperformed H-TenRPCA.

  • B. Empirical Analysis for Algorithm Convergence: Convergence was evaluated using relative change and relative error for video volume X0 and foreground X2 under sampling ratios 0.04 and 0.05.Real-video foreground relative error was omitted because its ground truth is unavailable.
  • B. Empirical Analysis for Algorithm Convergence: The assessment curves stabilized at relatively high iteration counts, indicating empirical convergence of both proposed algorithms.Relative change approached zero while relative error decreased toward a stable value.
  • B. Empirical Analysis for Algorithm Convergence: A foreground relative-change jump between iterations 60 and 100 coincided with a substantial relative-error decrease, indicating sudden improvement in foreground estimation.This behavior was observed for the synthetic and real-video convergence results.
  • 1) Comparison with Batch-Based Methods:: PG-TenRPCA generally exceeded H-TenRPCA, consistent with its use of correlated groups of similar 3D patches to model video-background structure.This advantage was reported on synthetic and ShoppingMall videos, both quantitatively and visually.
  • 1) Comparison with Batch-Based Methods:: At sampling ratio 1/25, PG-TenRPCA produced clearer reconstructions than competing approaches in the synthetic-video visual comparison.H-MatRPCA, H-TenRPCA, and PG-TenRPCA remained satisfactory, but H-MatRPCA was less sharp.
  • 1) Comparison with Batch-Based Methods:: At low sampling ratios, H-TenRPCA and PG-TenRPCA maintained high PSNR, SSIM, and F-measure values while competing methods degraded or failed.The proposed methods also performed well at higher sampling ratios, where competing methods could reconstruct and separate satisfactorily.

2) Comparison with the Online Method ReProCS:

The proposed methods are compared with ReProCS for reconstruction and foreground separation under different sampling ratios and compressive operators. PG-TenRPCA generally provides stronger reconstruction, while 3D-TV supports foreground detection, with computational costs differing substantially across models.

  • Reconstruction and separation: The proposed methods almost outperform ReProCS in F-measure for video separation, consistent with the role of 3D total variation in favoring spatio-temporal foreground continuity.The comparison covers synthetic and real videos at sampling ratios 0.75, 0.5, and 0.25.
  • Reconstruction and separation: PG-TenRPCA is superior to H-TenRPCA and ReProCS in video reconstruction according to PSNR and SSIM.At very low sampling ratios, ReProCS can outperform H-TenRPCA on some videos because it uses a pretrained background, whereas the proposed methods do not require pre-training.
  • Computational speeds: The running times for SpaRCS, SpLR, ReProCS, H-TenRPCA, and PG-TenRPCA are 14.4606, 2147.6, 995.9870, 93.3779, and 1015.5 seconds, respectively.SpaRCS is fastest, H-TenRPCA is relatively fast, and PG-TenRPCA is slower because patch search and joint Tucker decomposition are computationally costly.
  • Different compressive operators: Performance deteriorates as the sampling ratio decreases across PSNR, SSIM, and F-measure for the tested compressive operators.WHT-h and WHT-f are comparable to Noiselet-h and Noiselet-f in the reported synthetic and ShoppingMall experiments.
  • Overall comparison: The experiments report superiority of the proposed approaches over existing state-of-the-art methods on synthetic and real-world data sets.The conclusion frames the proposed approach around Tucker modeling of background correlations and 3D-TV characterization of foreground smoothness.

APPENDIX A

The appendix derives alternating-minimization updates for Tucker factors in the patch-group model. Core and factor matrices are updated by solving least-squares objectives using eigenvector or singular-vector computations.

  • Core update: With orthogonal factor matrices fixed, the core tensor is updated by minimizing the Tucker reconstruction error.The resulting update uses the transposed factor matrices in the least-squares reconstruction objective.
  • Optimization scheme: The alternating direction method approximately solves the optimization problem through successive updates of the core and factor matrices.The derivation uses eigs(A, r) for the top r eigenvectors and SVD(A, r) for the top r singular vectors.
  • Factor updates: The factor matrix U1p is estimated by maximizing projected reconstruction energy and is obtained from the top singular vectors of the corresponding matrix.The same procedure is stated to apply to U2p and U4p.
  • Factor updates: The factor matrix U3 is estimated by maximizing the Tucker reconstruction energy with respect to U3.The appendix presents this as the final factor-matrix update after U1p, U2p, and U4p.
Loading 1503.01868v4…