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

Xianchao Xiu; Ying Yang; Wanquan Liu; Lingchen Kong; Meijuan Shang

doi:10.3934/jimo.2019024

Article Contents

2020, Volume 16, Issue 4: 1685-1698. Doi: 10.3934/jimo.2019024

This issue Previous Article Minimizing almost smooth control variation in nonlinear optimal control problems Next Article Fast calibration of the Libor market model with stochastic volatility and displaced diffusion

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
^* Corresponding author: Ying Yang

Received: May 2018

Revised: January 2019

Early access: May 2019

Published: May 2020

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

Abstract Full Text(HTML) Figure(3) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

Dynamic background extraction,
rank-one matrix,
joint sparsity,
total variation,
alternating direction method of multipliers.

Mathematics Subject Classification: Primary: 90C25, 90C90; Secondary: 65K10.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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 $

Download: Full-size image PowerPoint slide

Figure 3. Visual Comparisons on both Synthetic and Real-world Data Sets

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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. Bouwmans, A. Sobral, S. Javed, S. Jung and E. Zahzah, Decomposition into low-rank plus additive matrices for background/foreground separation, Computer Science Review, 23 (2017), 2-71.
[3]	S. Boyd, N. Parikh, E. Chu, B. 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. Cao, L. 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. Chen, B. He, Y. 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. Chen, D. 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. Chen, Z. 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. Chen, N. 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. Elgammal, R. Duraiswami, D. 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. Fazel, T. Pong, D. 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. He, M. 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. Li, M. 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. Rudin, S. 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. Yang, T. 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. Zhang, D. S. Pham, S. Venkatesh, W. 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.