SpringerBriefs in Electrical and Computer Engineering For further volumes: http://www.springer.com/series/10059 Vishal M. Patel • Rama Chellappa Sparse Representations and Compressive Sensing for Imaging and Vision 123 Vishal M. Patel Center for Automation Research University of Maryland A.V. Williams Building College Park, MD Rama Chellappa Department of Electrical and Computer Engineering and Center for Automation Research A.V. Williams Building University of Maryland College Park, MD ISSN 2191-8112 ISSN 2191-8120 (electronic) ISBN 978-1-4614-6380-1 ISBN 978-1-4614-6381-8 (eBook) DOI 10.1007/978-1-4614-6381-8 Springer New York Heidelberg Dordrecht London Library of Congress Control Number: 2012956308 © The Author(s) 2013 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com) To my sisters Julie, Dharti and Gunjali — Vishal M. Patel Acknowledgements We thank former and current students as well as collaborators - Richard Baraniuk, Volkan Cevher, Pavan Turaga, Ashok Veeraraghavan, Aswin Sankaranarayanan, Dikpal Reddy, Amit Agrawal, Nalini Ratha, Jaishanker Pillai, Hien Van Nguyen, Sumit Shekhar, Garrett Warnell, Qiang Qiu, Ashish Shrivastava - for letting us draw upon their work, thus making this monograph possible. Research efforts summarized in this monograph were supported by the following grants and contracts: ARO MURI (W911NF-09-1-0383),ONR MURI (N00014-08- 1-0638), ONR grant (N00014-12-1-0124), and a NIST grant (70NANB11H023). vii Contents 1 Introduction 1 1.1 Outline 2 2 Compressive Sensing 3 2.1 Sparsity 3 2.2 Incoherent Sampling 5 2.3 Recovery 6 2.3.1 Robust CS 7 2.3.2 CS Recovery Algorithms 9 2.4 Sensing Matrices 11 2.5 Phase Transition Diagrams 12 2.6 Numerical Examples 15 3 Compressive Acquisition 17 3.1 Single Pixel Camera 17 3.2 Compressive Magnetic Resonance Imaging 18 3.2.1 Image Gradient Estimation 21 3.2.2 Image Reconstruction from Gradients 23 3.2.3 Numerical Examples 24 3.3 Compressive Synthetic Aperture Radar Imaging 25 3.3.1 Slow-time Undersampling 27 3.3.2 Image Reconstruction 28 3.3.3 Numerical Examples 29 3.4 Compressive Passive Millimeter Wave Imaging 30 3.4.1 Millimeter Wave Imaging System 31 3.4.2 Accelerated Imaging with Extended Depth-of-Field 34 3.4.3 Experimental Results 36 3.5 Compressive Light Transport Sensing 37 4 Compressive Sensing for Vision 41 4.1 Compressive Target Tracking 41 4.1.1 Compressive Sensing for Background Subtraction 42 ix x Contents 4.1.2 Kalman Filtered Compressive Sensing 45 4.1.3 Joint Compressive Video Coding and Analysis 45 4.1.4 Compressive Sensing for Multi-View Tracking 47 4.1.5 Compressive Particle Filtering 48 4.2 Compressive Video Processing 50 4.2.1 Compressive Sensing for High-Speed Periodic Videos 50 4.2.2 Programmable Pixel Compressive Camera for High Speed Imaging 53 4.2.3 Compressive Acquisition of Dynamic Textures 54 4.3 Shape from Gradients 56 4.3.1 Sparse Gradient Integration 57 4.3.2 Numerical Examples 59 5 Sparse Representation-based Object Recognition 63 5.1 Sparse Representation 63 5.2 Sparse Representation-based Classification 65 5.2.1 Robust Biometrics Recognition using Sparse Representation 67 5.3 Non-linear Kernel Sparse Representation 69 5.3.1 Kernel Sparse Coding 70 5.3.2 Kernel Orthogonal Matching Pursuit 72 5.3.3 Kernel Simultaneous Orthogonal Matching Pursuit 72 5.3.4 Experimental Results 74 5.4 Multimodal Multivariate Sparse Representation 75 5.4.1 Multimodal Multivariate Sparse Representation 76 5.4.2 Robust Multimodal Multivariate Sparse Representation 77 5.4.3 Experimental Results 78 5.5 Kernel Space Multimodal Recognition 80 5.5.1 Multivariate Kernel Sparse Representation 80 5.5.2 Composite Kernel Sparse Representation 81 5.5.3 Experimental Results 82 6 Dictionary Learning 85 6.1 Dictionary Learning Algorithms 85 6.2 Discriminative Dictionary Learning 86 6.3 Non-Linear Kernel Dictionary Learning 90 7 Concluding Remarks 93 References 95 Chapter 1 Introduction Compressive sampling 1 [23,47] is an emerging field that has attracted considerable interest in signal/image processing, computer vision and information theory. Recent advances in compressive sensing have led to the development of imaging devices that sense at measurement rates below than the Nyquist rate. Compressive sensing exploits the property that the sensed signal is often sparse in some transform domain in order to recover it from a small number of linear, random, multiplexed measurements. Robust signal recovery is possible from a number of measurements that is proportional to the sparsity level of the signal, as opposed to its ambient dimensionality. While there has been remarkable progress in compressive sensing for static signals such as images, its application to sensing temporal sequences such as videos has also recently gained a lot of traction. Compressive sensing of videos makes a compelling application towards dramatically reducing sensing costs. This manifests itself in many ways including alleviating the data deluge problems [7] faced in the processing and storage of videos. Using novel sensors based on this theory, there is hope to accomplish tasks such as target tracking and object recognition while collecting significantly less data than traditional systems. In this monograph, we will present an overview of the theories of sparse representation and compressive sampling and examine several interesting imaging modalities based on these theories. We will also explore the use of linear and non-linear kernel sparse representation as well as compressive sensing in many computer vision problems including target tracking, background subtraction and object recognition. Writing this monograph presented a great challenge. Due to page limitations, we could not include all that we wished. We beg the forgiveness of many of our fellow researchers who have made significant contributions to the problems covered in this monograph and whose works could not be discussed. 1 Also known as compressive sensing or compressed sensing. V.M. Patel and R. Chellappa, Sparse Representations and Compressive Sensing for Imaging and Vision, SpringerBriefs in Electrical and Computer Engineering, DOI 10.1007/978-1-4614-6381-8 1, © The Author(s) 2013 1 2 1 Introduction 1.1 Outline We begin the monograph with a brief discussion on compressive sampling in Sect. 2. In particular, we present some fundamental premises underlying CS: sparsity, incoherent sampling and non-linear recovery. Some of the main results are also reviewed. In Sect. 3, we describe several imaging modalities that make use of the theory of compressive sampling. In particular, we present applications in medical imaging, synthetic aperture radar imaging, millimeter wave imaging, single pixel camera and light transport sensing. In Sect. 4, we present some applications of compressive sampling in computer vi- sion and image understanding. We show how sparse representation and compressive sampling framework can be used to develop robust algorithms for target tracking. We then present several applications in video compressive sampling. Finally, we show how compressive sampling can be used to develop algorithms for recovering shapes and images from gradients. Section 5 discusses some applications of sparse representation and compressive sampling in object recognition. In particular, we first present an overview of the sparse representation framework. We then show how it can be used to develop robust algorithms for object recognition. Through the use of Mercer kernels, we show how the sparse representation framework can be made non-linear. We also discuss multimodal multivariate sparse representation as well as its non-linear extension at the end of this section. In Sect. 6, we discuss recent advances in dictionary learning. In particular, we present an overview of the method of optimal directions and the KSVD algorithms for learning dictionaries. We then show how dictionaries can be designed to achieve discrimination as well as reconstruction. Finally, we highlight some of the methods for learning non-linear kernel dictionaries. Finally, concluding remarks are presented in Sect. 7. Chapter 2 Compressive Sensing Compressive sensing [47], [23] is a new concept in signal processing and information theory where one measures a small number of non-adaptive linear combinations of the signal. These measurements are usually much smaller than the number of samples that define the signal. From these small number of measurements, the signal is then reconstructed by a non-linear procedure. In what follows, we present some fundamental premises underlying CS: sparsity, incoherent sampling and non-linear recovery. 2.1 Sparsity Let x be a discrete time signal which can be viewed as an N ×1 column vector in R N . Given an orthonormal basis matrix B ∈ R N×N whose columns are the basis elements {b i } N i=1 , x can be represented in terms of this basis as x = N ∑ i=1 α i b i (2.1) or more compactly x = B α , where α is an N ×1 column vector of coefficients. These coefficients are given by α i = x,b i = b T i x where . T denotes the transposition operation. If the basis B provides a K-sparse representation of x,then(2.1) can be rewritten as x = K ∑ i=1 α n i b n i , where {n i } are the indices of the coefficients and the basis elements corresponding to the K nonzero entries. In this case, α is an N ×1 column vector with only K nonzero elements. That is,  α  0 = K where . p denotes the  p -norm defined as V.M. Patel and R. Chellappa, Sparse Representations and Compressive Sensing for Imaging and Vision, SpringerBriefs in Electrical and Computer Engineering, DOI 10.1007/978-1-4614-6381-8 2, © The Author(s) 2013 3 [...]... images using total variation minimization from only 2% and 10% measurements are shown in the second and third columns of Fig 3.2, respectively V.M Patel and R Chellappa, Sparse Representations and Compressive Sensing for Imaging and Vision, SpringerBriefs in Electrical and Computer Engineering, DOI 10.1007/97 8-1 -4 61 4-6 38 1-8 3, © The Author(s) 2013 17 18 3 Compressive Acquisition Fig 3.1 Single pixel camera... Radar (SAR) imaging [103], passive millimeter wave imaging [104] and compressive light transport sensing [110] See [153] and [55] for excellent tutorials on the applications of compressive sensing in the context of optical imaging as well as analog-toinformation conversion 3.1 Single Pixel Camera One of the first physical imagers that demonstrated the practicality of compressive sensing in imaging was... of range and cross-range or azimuth The range is the direction of signal propagation and the cross-range is the direction parallel to the flight path Sometimes the range and the cross-range samples are referred to as the fast-time and the slow-time samples, respectively The range resolution of a SAR image is directly related to the bandwidth of the transmitted signal and the cross-range is inversely... Therefore, high range resolution is achieved by transmitting wide bandwidth waveforms, and high cross-range resolution is achieved by coherently processing returns transmitted from a variety of positions along a flight path to emulate a large aperture The standard methods for obtaining SAR images are basically based on using interpolation and the Fourier transform One such method is known as the Polar Format... is non-ionizing and is therefore considered safe for human use Applications of this technology include the detection of concealed weapons, explosives and contraband [4] Fig 3.10 compares a visible image and corresponding 94-GHz image of two people with various weapons concealed under clothing Note that concealed weapons are clearly detected in the mmW image However, when used for short range imaging. .. 40 60 80 100 120 140 160 180 200 Fig 2.3 1D sparse signal recovery example from random Gaussian measurements (a) Compressive measurement matrix (b) Original sparse signal (c) Compressive measurements (d) 1 recovery (e) 2 recovery (f) 1 reconstruction error (g) 2 reconstruction error 14 2 Compressive Sensing Fig 2.4 2D sparse image recovery example from random Fourier measurements (a) Original image... fails to recover the sparse signal The errors corresponding the 1 and 2 recovery are shown in Fig 2.3(f) and Fig 2.3(g), respectively In the second example, we reconstructed an undersampled Shepp-Logan phantom image of size 128 × 128 in the presence of additive white Gaussian noise with signal-to-noise ratio of 30 dB For this example, we used only 15% of the random Fourier measurements and Haar wavelets...4 2 Compressive Sensing x p ∑ | xi | = 1 p p i and the 0 -norm is defined as the limit as p → 0 of the x In general, the 0 -norm 0 = lim x p→0 p p p -norm = lim ∑ | xi | p p→0 i counts the number of non-zero elements in a vector x 0 = {i : xi = 0} (2.2) Typically, real-world signals are not exactly sparse in any orthogonal basis Instead, they are compressible... T as rows in an M × N matrix Φ and using j (2.1), the measurement process can be written as y = Φ x = Φ Bα = Aα , (2.4) 6 2 Compressive Sensing where y is an M × 1 column vector of the compressive measurements and A = Φ B is the measurement matrix or the sensing matrix Given an M × N sensing matrix A and the observation vector y, the general problem is to recover the sparse or compressible vector α... the first question is to determine whether A is good for compressive sensing Candes and Tao introduced a necessary condition on ´ A that guarantees a stable solution for both K sparse and compressible signals [26], [24] Definition 2.1 A matrix A is said to satisfy the Restricted Isometry Property (RIP) of order K with constants δK ∈ (0, 1) if (1 − δK ) v for any v such that v 0 2 2 ≤ Av 2 2 ≤ (1 + δK ) . Building University of Maryland College Park, MD ISSN 219 1-8 112 ISSN 219 1-8 120 (electronic) ISBN 97 8-1 -4 61 4-6 38 0-1 ISBN 97 8-1 -4 61 4-6 38 1-8 (eBook) DOI 10.1007/97 8-1 -4 61 4-6 38 1-8 Springer New York Heidelberg.  p -norm defined as V.M. Patel and R. Chellappa, Sparse Representations and Compressive Sensing for Imaging and Vision, SpringerBriefs in Electrical and Computer Engineering, DOI 10.1007/97 8-1 -4 61 4-6 38 1-8 2,. as compressive sensing or compressed sensing. V.M. Patel and R. Chellappa, Sparse Representations and Compressive Sensing for Imaging and Vision, SpringerBriefs in Electrical and Computer Engineering, DOI