July  2020, 16(4): 1685-1698. doi: 10.3934/jimo.2019024

An improved total variation regularized RPCA for moving object detection with dynamic background

1. 

State Key Lab for Turbulence and Complex Systems, Department of Mechanics and Engineering Science, College of Engineering, Peking University, China

2. 

Department of Computing, Curtin University, Australia

3. 

Department of Applied Mathematics, Beijing Jiaotong University, China

4. 

College of Science, Shijiazhuang University, China

* Corresponding author: Ying Yang

Received  May 2018 Revised  January 2019 Published  May 2019

Fund Project: This work was supported in part by the National Natural Science Foundation of China (61633001, 11671029, 11601348) and the 111 Project of China (B16002)

Dynamic background extraction has been a fundamental research topic in video analysis. In this paper, a novel robust principal component analysis (RPCA) approach for foreground extraction is proposed by decomposing video frames into three parts: rank-one static background, dynamic background and sparse foreground. First, the static background is represented by a rank-one matrix, which can avoid the computation of singular value decomposition because usually the dimensionality of a surveillance video is very large. Secondly, the dynamic background is characterized by $ \ell_{2,1} $-norm, which can exploit the shared information. Thirdly, the sparse foreground is enhanced by total variation, which can preserve sharp edges that are usually the most important for clear object extraction. An efficient symmetric Gauss-Seidel based alternating direction method of multipliers (sGS-ADMM) is established with convergence analysis. Extensive experiments on real-world datasets show that our proposed approach outperforms the existing state-of-the-art approaches. In fact, to the best of our knowledge, this is the first time to integrate the joint sparsity and total variation into a RPCA framework, which has demonstrated the superiority of performance.

Citation: Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024
References:
[1]

T. Bouwmans, Traditional and recent approaches in background modeling for foreground detection: An overview, Computer Science Review, 11/12 (2014), 31-66.  doi: 10.1016/j.cosrev.2014.04.001.  Google Scholar

[2]

T. BouwmansA. SobralS. JavedS. Jung and E. Zahzah, Decomposition into low-rank plus additive matrices for background/foreground separation, Computer Science Review, 23 (2017), 2-71.   Google Scholar

[3]

S. BoydN. ParikhE. ChuB. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine learning, 3 (2010), 1-122.   Google Scholar

[4]

E. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?, Journal of the ACM, 58 (2009), Art. 11, 37 pp. doi: 10.1145/1970392.1970395.  Google Scholar

[5]

E. Candès and T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory, 51 (2005), 4203-4215.  doi: 10.1109/TIT.2005.858979.  Google Scholar

[6]

X. CaoL. Yang and X. Guo, Total variation regularized RPCA for irregularly moving object detection under dynamic background, IEEE Transactions on Cybernetics, 46 (2016), 1014-1027.  doi: 10.1109/TCYB.2015.2419737.  Google Scholar

[7]

C. ChenB. HeY. Ye and X. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Mathematical Programming, 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5.  Google Scholar

[8]

L. ChenD. Sun and K. Toh, An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Mathematical Programming, 161 (2017), 237-270.  doi: 10.1007/s10107-016-1007-5.  Google Scholar

[9]

Y. ChenZ. Luo and N. Xiu, Half thresholding eigenvalue algorithm for semidefinite matrix completion, Science China Mathematics, 58 (2015), 2015-2032.  doi: 10.1007/s11425-015-5052-y.  Google Scholar

[10]

Y. ChenN. Xiu and D. Peng, Global solutions of non-Lipschitz $S_2-S_ p$ minimization over the positive semidefinite cone, Optimization Letters, 8 (2014), 2053-2064.  doi: 10.1007/s11590-013-0701-y.  Google Scholar

[11]

D. Donoho, De-Noising by soft thresholding, IEEE Transactions on Information Theory, 41 (1995), 613-627.  doi: 10.1109/18.382009.  Google Scholar

[12]

A. ElgammalR. DuraiswamiD. Harwood and L. Davis, Background and foreground modeling using nonparametric kernel density estimation for visual surveillance, Proceedings of the IEEE, 90 (2002), 1151-1163.  doi: 10.1109/JPROC.2002.801448.  Google Scholar

[13]

M. FazelT. PongD. Sun and P. Tseng, Hankel matrix rank minimization with applications to system identification and realization, SIAM Journal on Matrix Analysis and Applications, 34 (2013), 946-977.  doi: 10.1137/110853996.  Google Scholar

[14]

D. Gabay, Applications of the method of multipliers to variational inequalities, In: M. Fortin, R. Glowinski (Eds.), Augmented Lagrange Methods: Applications to the Solution of Boundary-valued Problems. North-Holland, Amsterdam, The Netherlands, (1983), 299–331. Google Scholar

[15]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers and Mathematics with Applications, 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[16]

B. HeM. Tao and X. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization, 22 (2012), 313-340.  doi: 10.1137/110822347.  Google Scholar

[17]

B. He and X. Yuan, On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM Journal on Numerical Analysis, 50 (2012), 700-709.  doi: 10.1137/110836936.  Google Scholar

[18]

M. Li, D. Sun and K. Toh, A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block, Asia-Pacific Journal of Operational Research, 32 (2015), 1550024, 19pp. doi: 10.1142/S0217595915500244.  Google Scholar

[19]

X. LiM. Ng and X. Yuan, Median filtering-based methods for static background extraction from surveillance video, Numerical Linear Algebra with Applications, 22 (2015), 845-865.  doi: 10.1002/nla.1981.  Google Scholar

[20]

X. Li, D. Sun and K. Toh, A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications, Mathematical Programming, (2017), 1–24. doi: 10.1007/s10107-018-1247-7.  Google Scholar

[21]

J. Liu, S. Ji and J. Ye, Multi-task feature learning via efficient $\ell_{2, 1}$-norm minimization, Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, (2012), 339–348. Google Scholar

[22]

L. Maddalena and A. Petrosino, A self-organizing approach to background subtraction for visual surveillance applications, IEEE Transactions on Image Processing, 17 (2008), 1168-1177.  doi: 10.1109/TIP.2008.924285.  Google Scholar

[23]

B. Natarajan, Sparse approximate solutions to linear systems, SIAM Journal on Computing, 24 (1995), 227-234.  doi: 10.1137/S0097539792240406.  Google Scholar

[24]

R. Rockfellar, Convex Analysis, Princeton University Press, 1970.  Google Scholar

[25]

L. Rudin and S. Osher, Total variation based image restoration with free local constraints, Proceedings of IEEE International Conference on Image Processing, 1 (1994), 31-35.  doi: 10.1109/ICIP.1994.413269.  Google Scholar

[26]

L. RudinS. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[27]

A. Sobral and A. Vacavant, A comprehensive review of background subtraction algorithms evaluated with synthetic and real videos, Computer Vision and Image Understanding, 122 (2014), 4-21.  doi: 10.1016/j.cviu.2013.12.005.  Google Scholar

[28]

C. Stauffer and W. Grimson, Adaptive background mixture models for real-time tracking, IEEE Conference on Computer Vision and Pattern Recognition, 2 (1999), 2246. doi: 10.1109/CVPR.1999.784637.  Google Scholar

[29]

X. Xiu and L. Kong, Rank-min-one and sparse tensor decomposition for surveillance video, Pacific Journal of Optimization, 11 (2015), 403-418.   Google Scholar

[30]

L. YangT. Pong and X. Chen., Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction., SIAM Journal on Imaging Sciences, 10 (2017), 74-110.  doi: 10.1137/15M1027528.  Google Scholar

[31]

X. ZhangD. S. PhamS. VenkateshW. Liu and D. Phung, Mixed-norm sparse representation for multi view face recognition, Pattern Recognition, 48 (2015), 2935-2946.  doi: 10.1016/j.patcog.2015.02.022.  Google Scholar

show all references

References:
[1]

T. Bouwmans, Traditional and recent approaches in background modeling for foreground detection: An overview, Computer Science Review, 11/12 (2014), 31-66.  doi: 10.1016/j.cosrev.2014.04.001.  Google Scholar

[2]

T. BouwmansA. SobralS. JavedS. Jung and E. Zahzah, Decomposition into low-rank plus additive matrices for background/foreground separation, Computer Science Review, 23 (2017), 2-71.   Google Scholar

[3]

S. BoydN. ParikhE. ChuB. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine learning, 3 (2010), 1-122.   Google Scholar

[4]

E. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?, Journal of the ACM, 58 (2009), Art. 11, 37 pp. doi: 10.1145/1970392.1970395.  Google Scholar

[5]

E. Candès and T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory, 51 (2005), 4203-4215.  doi: 10.1109/TIT.2005.858979.  Google Scholar

[6]

X. CaoL. Yang and X. Guo, Total variation regularized RPCA for irregularly moving object detection under dynamic background, IEEE Transactions on Cybernetics, 46 (2016), 1014-1027.  doi: 10.1109/TCYB.2015.2419737.  Google Scholar

[7]

C. ChenB. HeY. Ye and X. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Mathematical Programming, 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5.  Google Scholar

[8]

L. ChenD. Sun and K. Toh, An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Mathematical Programming, 161 (2017), 237-270.  doi: 10.1007/s10107-016-1007-5.  Google Scholar

[9]

Y. ChenZ. Luo and N. Xiu, Half thresholding eigenvalue algorithm for semidefinite matrix completion, Science China Mathematics, 58 (2015), 2015-2032.  doi: 10.1007/s11425-015-5052-y.  Google Scholar

[10]

Y. ChenN. Xiu and D. Peng, Global solutions of non-Lipschitz $S_2-S_ p$ minimization over the positive semidefinite cone, Optimization Letters, 8 (2014), 2053-2064.  doi: 10.1007/s11590-013-0701-y.  Google Scholar

[11]

D. Donoho, De-Noising by soft thresholding, IEEE Transactions on Information Theory, 41 (1995), 613-627.  doi: 10.1109/18.382009.  Google Scholar

[12]

A. ElgammalR. DuraiswamiD. Harwood and L. Davis, Background and foreground modeling using nonparametric kernel density estimation for visual surveillance, Proceedings of the IEEE, 90 (2002), 1151-1163.  doi: 10.1109/JPROC.2002.801448.  Google Scholar

[13]

M. FazelT. PongD. Sun and P. Tseng, Hankel matrix rank minimization with applications to system identification and realization, SIAM Journal on Matrix Analysis and Applications, 34 (2013), 946-977.  doi: 10.1137/110853996.  Google Scholar

[14]

D. Gabay, Applications of the method of multipliers to variational inequalities, In: M. Fortin, R. Glowinski (Eds.), Augmented Lagrange Methods: Applications to the Solution of Boundary-valued Problems. North-Holland, Amsterdam, The Netherlands, (1983), 299–331. Google Scholar

[15]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers and Mathematics with Applications, 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[16]

B. HeM. Tao and X. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization, 22 (2012), 313-340.  doi: 10.1137/110822347.  Google Scholar

[17]

B. He and X. Yuan, On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM Journal on Numerical Analysis, 50 (2012), 700-709.  doi: 10.1137/110836936.  Google Scholar

[18]

M. Li, D. Sun and K. Toh, A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block, Asia-Pacific Journal of Operational Research, 32 (2015), 1550024, 19pp. doi: 10.1142/S0217595915500244.  Google Scholar

[19]

X. LiM. Ng and X. Yuan, Median filtering-based methods for static background extraction from surveillance video, Numerical Linear Algebra with Applications, 22 (2015), 845-865.  doi: 10.1002/nla.1981.  Google Scholar

[20]

X. Li, D. Sun and K. Toh, A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications, Mathematical Programming, (2017), 1–24. doi: 10.1007/s10107-018-1247-7.  Google Scholar

[21]

J. Liu, S. Ji and J. Ye, Multi-task feature learning via efficient $\ell_{2, 1}$-norm minimization, Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, (2012), 339–348. Google Scholar

[22]

L. Maddalena and A. Petrosino, A self-organizing approach to background subtraction for visual surveillance applications, IEEE Transactions on Image Processing, 17 (2008), 1168-1177.  doi: 10.1109/TIP.2008.924285.  Google Scholar

[23]

B. Natarajan, Sparse approximate solutions to linear systems, SIAM Journal on Computing, 24 (1995), 227-234.  doi: 10.1137/S0097539792240406.  Google Scholar

[24]

R. Rockfellar, Convex Analysis, Princeton University Press, 1970.  Google Scholar

[25]

L. Rudin and S. Osher, Total variation based image restoration with free local constraints, Proceedings of IEEE International Conference on Image Processing, 1 (1994), 31-35.  doi: 10.1109/ICIP.1994.413269.  Google Scholar

[26]

L. RudinS. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[27]

A. Sobral and A. Vacavant, A comprehensive review of background subtraction algorithms evaluated with synthetic and real videos, Computer Vision and Image Understanding, 122 (2014), 4-21.  doi: 10.1016/j.cviu.2013.12.005.  Google Scholar

[28]

C. Stauffer and W. Grimson, Adaptive background mixture models for real-time tracking, IEEE Conference on Computer Vision and Pattern Recognition, 2 (1999), 2246. doi: 10.1109/CVPR.1999.784637.  Google Scholar

[29]

X. Xiu and L. Kong, Rank-min-one and sparse tensor decomposition for surveillance video, Pacific Journal of Optimization, 11 (2015), 403-418.   Google Scholar

[30]

L. YangT. Pong and X. Chen., Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction., SIAM Journal on Imaging Sciences, 10 (2017), 74-110.  doi: 10.1137/15M1027528.  Google Scholar

[31]

X. ZhangD. S. PhamS. VenkateshW. Liu and D. Phung, Mixed-norm sparse representation for multi view face recognition, Pattern Recognition, 48 (2015), 2935-2946.  doi: 10.1016/j.patcog.2015.02.022.  Google Scholar

Figure 1.  Illustrations of the importance associated with the joint sparsity. For the left side, the first row is the foreground frames, the second and third row are the corresponding dynamic background frames and dynamic foreground frames, respectively. For the right side, the column represents the frames of the dynamic background, and it is not hard to conclude that this matrix has dense elements row-wise and sparse elements column-wise
Figure 2.  Some frames of tested surveillance videos. (a) The left two columns: $ noncamouflage $ and $ noisynight $. (b) The middle two columns: $ snowfall $ and $ skating $. (c) The right two columns: $ fall $ and $ fountain $
Figure 3.  Visual Comparisons on both Synthetic and Real-world Data Sets
Table 1.  Quantitative Results on both Synthetic and Real-world Data Sets
Videos RPCA Ours Ours
$ \; $ R P F R P F R P F
noncamouflage 0.64 0.35 0.45 0.65 0.36 0.47 0.69 0.78 0.73
noisynight 0.50 0.20 0.29 0.40 0.19 0.26 0.45 0.67 0.54
snowfall 0.74 0.37 0.49 0.75 0.41 0.53 0.87 0.92 0.89
skating 0.72 0.51 0.60 0.75 0.66 0.70 0.74 0.86 0.80
fall 0.68 0.13 0.21 0.69 0.13 0.21 0.83 0.94 0.88
fountain 0.84 0.02 0.04 0.74 0.03 0.06 0.74 0.08 0.14
Videos RPCA Ours Ours
$ \; $ R P F R P F R P F
noncamouflage 0.64 0.35 0.45 0.65 0.36 0.47 0.69 0.78 0.73
noisynight 0.50 0.20 0.29 0.40 0.19 0.26 0.45 0.67 0.54
snowfall 0.74 0.37 0.49 0.75 0.41 0.53 0.87 0.92 0.89
skating 0.72 0.51 0.60 0.75 0.66 0.70 0.74 0.86 0.80
fall 0.68 0.13 0.21 0.69 0.13 0.21 0.83 0.94 0.88
fountain 0.84 0.02 0.04 0.74 0.03 0.06 0.74 0.08 0.14
[1]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83

[2]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[3]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[4]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[5]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[6]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109

[7]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021035

[8]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[9]

Madalina Petcu, Roger Temam. The one dimensional shallow water equations with Dirichlet boundary conditions on the velocity. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 209-222. doi: 10.3934/dcdss.2011.4.209

[10]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409

[11]

Daoyuan Fang, Ting Zhang. Compressible Navier-Stokes equations with vacuum state in one dimension. Communications on Pure & Applied Analysis, 2004, 3 (4) : 675-694. doi: 10.3934/cpaa.2004.3.675

[12]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[13]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018

[14]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002

[15]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263

[16]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

[17]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[18]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (166)
  • HTML views (588)
  • Cited by (0)

[Back to Top]