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, 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[11]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[23]

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

[24]

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

[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.

[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.

[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.

[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.

[29]

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

[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.

[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.

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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[11]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[23]

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

[24]

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

[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.

[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.

[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.

[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.

[29]

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

[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.

[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.

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]

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial & Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037

[2]

Xianchao Xiu, Lingchen Kong. Rank-one and sparse matrix decomposition for dynamic MRI. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 127-134. doi: 10.3934/naco.2015.5.127

[3]

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems & Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917

[4]

Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2019029

[5]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247

[6]

Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078

[7]

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

[8]

Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems & Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547

[9]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067

[10]

Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015

[11]

Masayuki Asaoka. Local rigidity of homogeneous actions of parabolic subgroups of rank-one Lie groups. Journal of Modern Dynamics, 2015, 9: 191-201. doi: 10.3934/jmd.2015.9.191

[12]

Konstantinos Papafitsoros, Kristian Bredies. A study of the one dimensional total generalised variation regularisation problem. Inverse Problems & Imaging, 2015, 9 (2) : 511-550. doi: 10.3934/ipi.2015.9.511

[13]

Yang Wang, Zhengfang Zhou. Source extraction in audio via background learning. Inverse Problems & Imaging, 2013, 7 (1) : 283-290. doi: 10.3934/ipi.2013.7.283

[14]

Liyan Ma, Lionel Moisan, Jian Yu, Tieyong Zeng. A stable method solving the total variation dictionary model with $L^\infty$ constraints. Inverse Problems & Imaging, 2014, 8 (2) : 507-535. doi: 10.3934/ipi.2014.8.507

[15]

Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237

[16]

Johnathan M. Bardsley. An efficient computational method for total variation-penalized Poisson likelihood estimation. Inverse Problems & Imaging, 2008, 2 (2) : 167-185. doi: 10.3934/ipi.2008.2.167

[17]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317

[18]

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

[19]

Bruno Sixou, Valentina Davidoiu, Max Langer, Francoise Peyrin. Absorption and phase retrieval with Tikhonov and joint sparsity regularizations. Inverse Problems & Imaging, 2013, 7 (1) : 267-282. doi: 10.3934/ipi.2013.7.267

[20]

Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (5)
  • HTML views (64)
  • Cited by (0)

[Back to Top]