×

An improved total variation regularized RPCA for moving object detection with dynamic background. (English) Zbl 1449.90295

Summary: 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.

MSC:

90C25 Convex programming
90C90 Applications of mathematical programming
65K10 Numerical optimization and variational techniques
Full Text: DOI

References:

[1] T. Bouwmans, Traditional and recent approaches in background modeling for foreground detection: An overview, Computer Science Review, 11/12, 31-66 (2014) · Zbl 1296.68170 · doi:10.1016/j.cosrev.2014.04.001
[2] T. Bouwmans; A. Sobral; S. Javed; S. Jung; E. Zahzah, Decomposition into low-rank plus additive matrices for background/foreground separation, Computer Science Review, 23, 2-71 (2017) · Zbl 1398.68572
[3] S. Boyd; N. Parikh; E. Chu; B. Peleato; J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine learning, 3, 1-122 (2010) · Zbl 1229.90122
[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. · Zbl 1327.62369
[5] E. Candès; T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory, 51, 4203-4215 (2005) · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979
[6] X. Cao; L. Yang; X. Guo, Total variation regularized RPCA for irregularly moving object detection under dynamic background, IEEE Transactions on Cybernetics, 46, 1014-1027 (2016) · doi:10.1109/TCYB.2015.2419737
[7] C. Chen; B. He; Y. Ye; X. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Mathematical Programming, 155, 57-79 (2016) · Zbl 1332.90193 · doi:10.1007/s10107-014-0826-5
[8] L. Chen; D. Sun; K. Toh, An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Mathematical Programming, 161, 237-270 (2017) · Zbl 1356.90105 · doi:10.1007/s10107-016-1007-5
[9] Y. Chen; Z. Luo; N. Xiu, Half thresholding eigenvalue algorithm for semidefinite matrix completion, Science China Mathematics, 58, 2015-2032 (2015) · Zbl 1327.90107 · doi:10.1007/s11425-015-5052-y
[10] Y. Chen; N. Xiu; D. Peng, Global solutions of non-Lipschitz \(S_2-S_p\) minimization over the positive semidefinite cone, Optimization Letters, 8, 2053-2064 (2014) · Zbl 1326.90063 · doi:10.1007/s11590-013-0701-y
[11] D. Donoho, De-Noising by soft thresholding, IEEE Transactions on Information Theory, 41, 613-627 (1995) · Zbl 0820.62002 · doi:10.1109/18.382009
[12] A. Elgammal; R. Duraiswami; D. Harwood; L. Davis, Background and foreground modeling using nonparametric kernel density estimation for visual surveillance, Proceedings of the IEEE, 90, 1151-1163 (2002) · doi:10.1109/JPROC.2002.801448
[13] M. Fazel; T. Pong; D. Sun; P. Tseng, Hankel matrix rank minimization with applications to system identification and realization, SIAM Journal on Matrix Analysis and Applications, 34, 946-977 (2013) · Zbl 1302.90127 · 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. · Zbl 0525.65045
[15] D. Gabay; B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers and Mathematics with Applications, 2, 17-40 (1976) · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1
[16] B. He; M. Tao; X. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization, 22, 313-340 (2012) · Zbl 1273.90152 · doi:10.1137/110822347
[17] B. He; X. Yuan, On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method, SIAM Journal on Numerical Analysis, 50, 700-709 (2012) · Zbl 1245.90084 · 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. · Zbl 1327.90214
[19] X. Li; M. Ng; X. Yuan, Median filtering-based methods for static background extraction from surveillance video, Numerical Linear Algebra with Applications, 22, 845-865 (2015) · Zbl 1349.94023 · 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.
[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; A. Petrosino, A self-organizing approach to background subtraction for visual surveillance applications, IEEE Transactions on Image Processing, 17, 1168-1177 (2008) · doi:10.1109/TIP.2008.924285
[23] B. Natarajan, Sparse approximate solutions to linear systems, SIAM Journal on Computing, 24, 227-234 (1995) · Zbl 0827.68054 · doi:10.1137/S0097539792240406
[24] R. Rockfellar, Convex Analysis, Princeton University Press, 1970. · Zbl 0193.18401
[25] L. Rudin; S. Osher, Total variation based image restoration with free local constraints, Proceedings of IEEE International Conference on Image Processing, 1, 31-35 (1994) · doi:10.1109/ICIP.1994.413269
[26] L. Rudin; S. Osher; E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60, 259-268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[27] A. Sobral; A. Vacavant, A comprehensive review of background subtraction algorithms evaluated with synthetic and real videos, Computer Vision and Image Understanding, 122, 4-21 (2014) · 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.
[29] X. Xiu; L. Kong, Rank-min-one and sparse tensor decomposition for surveillance video, Pacific Journal of Optimization, 11, 403-418 (2015) · Zbl 1352.90095
[30] L. Yang; T. Pong; 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, 74-110 (2017) · Zbl 1364.90278 · doi:10.1137/15M1027528
[31] X. Zhang; D. S. Pham; S. Venkatesh; W. Liu; D. Phung, Mixed-norm sparse representation for multi view face recognition, Pattern Recognition, 48, 2935-2946 (2015) · doi:10.1016/j.patcog.2015.02.022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.