# American Institute of Mathematical Sciences

May  2012, 6(2): 201-214. doi: 10.3934/ipi.2012.6.201

## Surveillance video processing using compressive sensing

 1 Bell Labs, Alcatel-Lucent, 700 Mountain Ave, Murray Hill, NJ 07974, United States 2 Dept. of Computational and Applied Math., Rice University, Houston, TX 77005, United States 3 Dept. of Math., National Univ. of Singapore, 119076, Singapore

Received  December 2011 Revised  February 2012 Published  May 2012

A compressive sensing method combined with decomposition of a matrix formed with image frames of a surveillance video into low rank and sparse matrices is proposed to segment the background and extract moving objects in a surveillance video. The video is acquired by compressive measurements, and the measurements are used to reconstruct the video by a low rank and sparse decomposition of matrix. The low rank component represents the background, and the sparse component is used to identify moving objects in the surveillance video. The decomposition is performed by an augmented Lagrangian alternating direction method. Experiments are carried out to demonstrate that moving objects can be reliably extracted with a small amount of measurements.
Citation: Hong Jiang, Wei Deng, Zuowei Shen. Surveillance video processing using compressive sensing. Inverse Problems & Imaging, 2012, 6 (2) : 201-214. doi: 10.3934/ipi.2012.6.201
##### References:
 [1] Y. Benezeth, P. M. Jodoin, B. Emile, H. Laurent and C. Rosenberger, Comparative study of background subtraction algorithms,, J. Electron. Imaging, 19 (2010). doi: 10.1117/1.3456695. [2] J.-F. Cai, E. J. Candès and Z. Shen, A singular value thresholding algorithm for matrix completion,, SIAM Journal on Optimization, 20 (2010), 1956. doi: 10.1137/080738970. [3] J.-F. Cai, S. Osher and Z. Shen, Split Bregman methods and frame based image restoration,, Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal, 8 (): 337. [4] E.-J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?,, Journal of ACM, 58 (2011). [5] E. J. Candès, J. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements,, Comm. Pure Appl. Math., 59 (2006), 1207. doi: 10.1002/cpa.20124. [6] V. Cevher, A. Sankaranarayanan, M. Duarte, D. Reddy, R. Baraniuk and R. Chellappa, Compressive sensing for background subtraction,, Computer Vision-ECCV 2008, (2008), 155. [7] I. Daubechies, B. Han, A. Ron and Z. Shen, Framelets: MRA-based constructions of wavelet frames,, Applied and Computational Harmonic Analysis, 14 (2003), 1. doi: 10.1016/S1063-5203(02)00511-0. [8] W. Deng, W. Yin and Y. Zhang, "Group Sparse Optimization by Alternating Direction Method,", TR11-06, (2011), 11. [9] B. Dong and Z. Shen, "MRA-Based Wavelet Frames and Applications,", IAS Lecture Notes Series, (2010). [10] Y. Dong, G. N. DeSouza and T. X. Han, Illumination invariant foreground detection using multi-subspace learning,, International Journal of Knowledge-based and Intelligent Engineering Systems, 14 (2010), 31. [11] D. Donoho, Compressed sensing,, IEEE Trans. on Information Theory, 52 (2006), 1289. doi: 10.1109/TIT.2006.871582. [12] M. Fornasier and H. Rauhut, Recovery algorithms for vector-valued data with joint sparsity constraints,, SIAM J. Numer. Anal., 46 (2008), 577. doi: 10.1137/0606668909. [13] H. Gao, J. F. Cai, Z. Shen and H. Zhao, Robust principal component analysis-based four-dimensional computed tomography,, Physics in Medicine and Biology, 56 (2011). doi: 10.1088/0031-9155/56/11/002. [14] R. Glowinski and P. Le Tallec, "Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics,", SIAM Studies in Applied Mathematics, 9 (1989). doi: 10.1137/1.9781611970838. [15] T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems,, SIAM J. Imaging Sci., 2 (2009), 323. doi: 10.1137/080725891. [16] H. Jiang, Chengbo Li, Raziel Haimi-Cohen, Paul Wilford and Yin Zhang, Scalable video coding using compressive sensing,, Bell Labs Technical Journal, 16 (2012). [17] H. Jiang, B. Mathews and P. Wilford, Compressive sensing for sound localization in wireless sensor network,, accepted for presentation at SENSORNET2012, (2012), 24. [18] H. Jiang, Z. Shen, W. Deng and P. Wilford, Adaptive low rank and sparse decomposition in compressive sensing of surveillance video,, submitted, (2011). [19] C. Li, H. Jiang, P. A., Wilford and Y. Zhang, Video coding using compressive sensing for wireless communications,, IEEE Wireless Communications and Networking Conference (WCNC), (2011), 2077. doi: 10.1109/WCNC.2011.5779474. [20] V. Mahadevan and N. Vasconcelos, Spatiotemporal saliency in highly dynamic scenes,, IEEE Trans. on Pattern Analysis and Machine Intelligence, 32 (2010), 171. doi: 10.1109/TPAMI.2009.112. [21] M. Piccardi, Background subtraction techniques: A review,, IEEE International Conference on Systems, 4 (2004), 3099. [22] A. Ron and Z. Shen, Affine systems in $L_2(R^d)$: The analysis of the analysis operator,, Journal of Functional Analysis, 148 (1997), 408. doi: 10.1006/jfan.1996.3079. [23] M. Rudelson and R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements,, Communications on Pure and Applied Mathematics, 61 (2008), 1025. doi: 10.1002/cpa.20227. [24] Z. Shen, Wavelet frames and image restorations,, Proceedings of the International Congress of Mathematicians, IV (2010), 2834. [25] C. Stauffer and W. E. L Grimson, Adaptive background mixture models for real-time tracking,, Computer Vision and Pattern Recognition, 2 (1999), 252. [26] E. Sutter, The Fast $m$-Transform: A fast computation of cross-correlations with binary $m$-sequences,, SIAM J. Comput., 20 (1991), 686. doi: 10.1137/0220043. [27] , EC Funded CAVIAR project/IST 2001 37540,, 2003. Available from: \url{http://homepages.inf.ed.ac.uk/rbf/CAVIAR/}., ().

show all references

##### References:
 [1] Y. Benezeth, P. M. Jodoin, B. Emile, H. Laurent and C. Rosenberger, Comparative study of background subtraction algorithms,, J. Electron. Imaging, 19 (2010). doi: 10.1117/1.3456695. [2] J.-F. Cai, E. J. Candès and Z. Shen, A singular value thresholding algorithm for matrix completion,, SIAM Journal on Optimization, 20 (2010), 1956. doi: 10.1137/080738970. [3] J.-F. Cai, S. Osher and Z. Shen, Split Bregman methods and frame based image restoration,, Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal, 8 (): 337. [4] E.-J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?,, Journal of ACM, 58 (2011). [5] E. J. Candès, J. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements,, Comm. Pure Appl. Math., 59 (2006), 1207. doi: 10.1002/cpa.20124. [6] V. Cevher, A. Sankaranarayanan, M. Duarte, D. Reddy, R. Baraniuk and R. Chellappa, Compressive sensing for background subtraction,, Computer Vision-ECCV 2008, (2008), 155. [7] I. Daubechies, B. Han, A. Ron and Z. Shen, Framelets: MRA-based constructions of wavelet frames,, Applied and Computational Harmonic Analysis, 14 (2003), 1. doi: 10.1016/S1063-5203(02)00511-0. [8] W. Deng, W. Yin and Y. Zhang, "Group Sparse Optimization by Alternating Direction Method,", TR11-06, (2011), 11. [9] B. Dong and Z. Shen, "MRA-Based Wavelet Frames and Applications,", IAS Lecture Notes Series, (2010). [10] Y. Dong, G. N. DeSouza and T. X. Han, Illumination invariant foreground detection using multi-subspace learning,, International Journal of Knowledge-based and Intelligent Engineering Systems, 14 (2010), 31. [11] D. Donoho, Compressed sensing,, IEEE Trans. on Information Theory, 52 (2006), 1289. doi: 10.1109/TIT.2006.871582. [12] M. Fornasier and H. Rauhut, Recovery algorithms for vector-valued data with joint sparsity constraints,, SIAM J. Numer. Anal., 46 (2008), 577. doi: 10.1137/0606668909. [13] H. Gao, J. F. Cai, Z. Shen and H. Zhao, Robust principal component analysis-based four-dimensional computed tomography,, Physics in Medicine and Biology, 56 (2011). doi: 10.1088/0031-9155/56/11/002. [14] R. Glowinski and P. Le Tallec, "Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics,", SIAM Studies in Applied Mathematics, 9 (1989). doi: 10.1137/1.9781611970838. [15] T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems,, SIAM J. Imaging Sci., 2 (2009), 323. doi: 10.1137/080725891. [16] H. Jiang, Chengbo Li, Raziel Haimi-Cohen, Paul Wilford and Yin Zhang, Scalable video coding using compressive sensing,, Bell Labs Technical Journal, 16 (2012). [17] H. Jiang, B. Mathews and P. Wilford, Compressive sensing for sound localization in wireless sensor network,, accepted for presentation at SENSORNET2012, (2012), 24. [18] H. Jiang, Z. Shen, W. Deng and P. Wilford, Adaptive low rank and sparse decomposition in compressive sensing of surveillance video,, submitted, (2011). [19] C. Li, H. Jiang, P. A., Wilford and Y. Zhang, Video coding using compressive sensing for wireless communications,, IEEE Wireless Communications and Networking Conference (WCNC), (2011), 2077. doi: 10.1109/WCNC.2011.5779474. [20] V. Mahadevan and N. Vasconcelos, Spatiotemporal saliency in highly dynamic scenes,, IEEE Trans. on Pattern Analysis and Machine Intelligence, 32 (2010), 171. doi: 10.1109/TPAMI.2009.112. [21] M. Piccardi, Background subtraction techniques: A review,, IEEE International Conference on Systems, 4 (2004), 3099. [22] A. Ron and Z. Shen, Affine systems in $L_2(R^d)$: The analysis of the analysis operator,, Journal of Functional Analysis, 148 (1997), 408. doi: 10.1006/jfan.1996.3079. [23] M. Rudelson and R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements,, Communications on Pure and Applied Mathematics, 61 (2008), 1025. doi: 10.1002/cpa.20227. [24] Z. Shen, Wavelet frames and image restorations,, Proceedings of the International Congress of Mathematicians, IV (2010), 2834. [25] C. Stauffer and W. E. L Grimson, Adaptive background mixture models for real-time tracking,, Computer Vision and Pattern Recognition, 2 (1999), 252. [26] E. Sutter, The Fast $m$-Transform: A fast computation of cross-correlations with binary $m$-sequences,, SIAM J. Comput., 20 (1991), 686. doi: 10.1137/0220043. [27] , EC Funded CAVIAR project/IST 2001 37540,, 2003. Available from: \url{http://homepages.inf.ed.ac.uk/rbf/CAVIAR/}., ().
 [1] 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 [2] Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems & Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925 [3] Zhouchen Lin. A review on low-rank models in data analysis. Big Data & Information Analytics, 2016, 1 (2&3) : 139-161. doi: 10.3934/bdia.2016001 [4] Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems & Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761 [5] Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems & Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601 [6] Simon Foucart, Richard G. Lynch. Recovering low-rank matrices from binary measurements. Inverse Problems & Imaging, 2019, 13 (4) : 703-720. doi: 10.3934/ipi.2019032 [7] 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 [8] 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 [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] 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 [11] Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems & Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002 [18] 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 [19] Kang-Yu Ni, Shankar Rao, Yuri Owechko. Foveated compressive imaging for low power vehicle fingerprinting and tracking in aerial imagery. Inverse Problems & Imaging, 2017, 11 (1) : 177-202. doi: 10.3934/ipi.2017009 [20] Jian-Wu Xue, Xiao-Kun Xu, Feng Zhang. Big data dynamic compressive sensing system architecture and optimization algorithm for internet of things. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1401-1414. doi: 10.3934/dcdss.2015.8.1401

2018 Impact Factor: 1.469