A. C. Sankaranarayanan, C. Studer, and R. G. Baraniuk, “CS-MUVI: Video Compressive Sensing for Spatial-Multiplexing Cameras“, IEEE International Conference on Computational Photography, Seattle, WA, April, 2012.

Abstract:  Compressive sensing (CS)-based spatial-multiplexing cameras (SMCs) sample a scene through a series of coded projections using a spatial light modulator and a few optical sensor elements. SMC architectures are particularly useful when imaging at wavelengths for which full-frame sensors are too cumbersome or expensive. While existing recovery algorithms for SMCs perform well for static images, they typically fail for time-varying scenes (videos). In this paper, we propose a novel CS multi-scale video (CS-MUVI) sensing and recovery framework for SMCs. Our framework features a co-designed video CS sensing matrix and recovery algorithm that provide an efficiently computable low-resolution video preview. We estimate the scene’s optical flow from the video preview and feed it into a convex-optimization algorithm to recover the high-resolution video. We demonstrate the performance and capabilities of the CS-MUVI framework for different scenes.

The CS-MUVI concept:  The key challenge with sensing videos with cameras such as the single pixel camera (SPC) is that the scene changes with every compressive measurement obtained. Traditional L1-recovery methods fail in the presence of rapid motion. We circumvent this problem by designing special measurement matrices that enable a two-step recovery process; the first step is to estimate motion in the scene and the second step is to recover the scene in full spatial and temporal resolution.

CS-MUVI project page

CS-MUVI demo video

Welcome to Open Educational Resources (OER) Week!  The Connexions and OpenStax College teams will be speaking several times this week about our recent progress on free, open-source textbooks.

• OpenStax College
• Connexions

C. Hegde and R. G. Baraniuk, “Signal Recovery on Incoherent Manifolds,” preprint, February 2012.

Abstract:  Suppose that we observe noisy linear measurements of an unknown signal that can be modeled as the sum of two component signals, each of which arises from a nonlinear sub-manifold of a high-dimensional ambient space. We introduce Successive Projections onto INcoherent manifolds (SPIN), a first-order projected gradient method to recover the signal components. Despite the nonconvex nature of the recovery problem and the possibility of underdetermined measurements, SPIN provably recovers the signal components, provided that the signal manifolds are incoherent and that the measurement operator satisfies a certain restricted isometry property. SPIN significantly extends the scope of current recovery models and algorithms for low-dimensional linear inverse problems and matches (or exceeds) the current state-of-the-art in terms of performance.

The above example illustrates SPIN recovery of two manifold-modeled components from compressive measurements of a noisy N=64×64 image.  The clean image consists of the linear superposition of a disk and square of fixed sizes but unknown locations. Additive Gaussian noise (SNR = 14dB) has been added to the image prior to taking M=50 compressive measurement (M/N = 1.2%).  (a) Original noisy image.  (b) Reconstructed disk.  (c) Reconstructed square.  The extension to more than two manifolds is straightforward.

A simple SPIN software toolbox is available.

The Fourth-Annual Connexions Conference was held 14-18 February 2012 at Rice University.  A great time was had by all!  Attendance roughly doubled from last year, to 155 on-site and 60 webcast attendees.  Additionally, 56 hardy souls toiled 16-18 February on a range of technical and content sprints.

Highlights included:

• Launch of OpenStax College
• Partnership announcements with Sapling Learning, WebAssign, Consolidated Graphics, and others
• Siyavula‘s amazing progress (South Africa is printing 2.5 million high school science and math textbooks – one for every student in the country)
• A technical sprint that helped define a componentized architecture for Connexions that will greatly increase its reach and scalability
• A content sprint that input an entire Siyavula Life Sciences textbook into Connexions in two days!

These are exciting times for open education in general and Connexions in particular.  With this kind of momentum, we are planning to hold the Fifth Annual Conference on our moon base (under construction).

OpenStax College is a nonprofit organization committed to improving student access to quality learning materials.  Today we announce the first 5 of a library of 20+ free, open-source textbooks for the highest-impact college courses: College Physics, Introduction to Sociology, Anatomy and Physiology, Biology, and Concepts in Biology.  College Physics and Introduction to Sociology will be available in early Spring 2012 for adoption in Fall 2012; the other three books will follow in Fall 2012.

OpenStax College free textbooks are developed and peer-reviewed by educators to ensure they are readable, accurate, and meet the scope and sequence requirements for college courses.  Through our partnerships with companies and foundations committed to reducing costs for students, OpenStax College is working to improve access to higher education for all.  OpenStax College is an initiative of Rice University and is made possible through the generous support of the Hewlett, Gates, 20 Million Minds, and Maxfield Foundations.

For more information, see the OpenStax College website and press release.

OpenStax College is proudly powered by Connexions.

The Fourth Annual Connexions Conference will be held on 15 February 2012 at Rice University.  Each year the Connexions Conference brings together more than 100 education thought leaders from around the world.  This year’s conference promises to be especially exciting, as we launch large scale initiatives on open textbooks and open education technology.

Please visit conference.cnx.org to register + find out more about the conference and software and content sprints on 16, 17 February 2012.  (Register before 17 January 2012 and take advantage of the early bird discount.)

“The problem with a mini-deal is we have a maxi-problem,” said John Cornyn, Senator from Texas, recently.  Indeed, minimax analysis is all over the news of late.  Our response consists of two new papers.  The first shows that the popular nonlocal means (NLM) image denoising algorithm is sub-optimal for images with sharp edges from the so-called Horizon class.  The second develops an enhanced anisotropic nonlocal means (ANLM) algorithm that is near-optimal for Horizon class images.

A. Maleki, M. Narayan, and R. G. Baraniuk, “Suboptimality of Nonlocal Means for Images with Sharp Edges,” preprint, 2011.

Abstract:  We conduct an asymptotic risk analysis of the nonlocal means image denoising
algorithm for the Horizon class of images that are piecewise constant with a sharp edge discontinuity.  We prove that the mean square risk of an optimally tuned nonlocal means algorithm decays according to n^(-1)log^(1/2)(n), for an n-pixel image.  This decay rate is an improvement over some of the predecessors of this algorithm, including the linear convolution filter, median filter, and the SUSAN filter, each of which provides a rate of only n^(-2/3).  It is also within a logarithmic factor from optimally tuned wavelet
thresholding.  However, it is still substantially lower than the the optimal minimax rate of n^(-4/3).

A. Maleki, M. Narayan, and R. G. Baraniuk, “Anisotropic Nonlocal Means Denoising,” preprint, 2011.

Abstract:  It has recently been proved that the popular nonlocal means (NLM) denoising algorithm does not optimally denoise images with sharp edges.  Its weakness lies in the isotropic nature of the neighborhoods it uses in order to set its smoothing weights.  In response, in this paper we introduce several theoretical and practical anisotropic nonlocal means (ANLM) algorithms and prove that they are near minimax optimal for edge-dominated images from the Horizon class.  On real-world test images, an ANLM algorithm that adapts to the underlying image gradients outperforms NLM by a significant margin, up to 2dB in mean square error.

Andrew E. Waters, Aswin C. Sankaranarayanan, Richard G. Baraniuk, “SpaRCS: Recovering Low-Rank and Sparse Matrices from Compressive Measurements,” in Advances in Neural Information Processing Systems (NIPS), Granada, Spain, December 2011.

Abstract:  We consider the problem of recovering a matrix M that is the sum of a low-rank matrix L and a sparse matrix S from a small set of linear measurements of the form Y = A(M) = A(L+S).  This model subsumes three important classes of signal recovery problems:  compressive sensing, affine rank minimization, and robust principal component analysis.  We propose a natural optimization problem for signal recovery under this model and develop a new greedy recovery algorithm called SpaRCS.  SpaRCS inherits a number of desirable properties from the state-of-the-art CoSaMP and ADMiRA algorithms, including exponential convergence and efficient implementation.  Simulation results with video compressive sensing, hyperspectral imaging, and robust matrix completion data sets demonstrate both the accuracy and efficacy of the algorithm.

An example from the paper illustrating the efficacy of SpaRCS for video compressive sensing (CS).  (a) Several 128×128 pixel image frames from a 201 frame ground truth video.  These were sensed by a simulated single-pixel CS camera that operates independently on each image frame.  (b) The recovered low-rank component L captures the static background.  (c) The recovered sparse component S captures the people walking in the foreground. The total recovery SNR is 31.2 dB at a measurement rate of 15% of the total number of video voxels.

J. N. Laska and R. G. Baraniuk, “Regime Change: Bit-Depth versus Measurement-Rate in Compressive Sensing,” to appear in IEEE Transactions on Signal Processing, 2012.

Abstract:  The recently introduced compressive sensing (CS) framework enables digital signal acquisition systems to take advantage of signal structures beyond bandlimitedness.  Indeed, the number of CS measurements required for stable reconstruction is closer to the order of the signal complexity than the Nyquist rate.  To date, the CS theory has focused on real-valued measurements, but in practice, measurements are mapped to bits from a finite alphabet.  Moreover, in many potential applications the total number of measurement bits is constrained, which suggests a tradeoff between the number of measurements and the number of bits per measurement.  We study this situation in this paper and show that there exist two distinct regimes of operation that correspond to high/low signal-to-noise ratio (SNR).  In the measurement compression (MC) regime, a high SNR favors acquiring fewer measurements with more bits per measurement; in the quantization compression (QC) regime, a low SNR favors acquiring more measurements with fewer bits per measurement.  A surprise from our analysis and experiments is that in many practical applications it is better to operate in the QC regime, even acquiring as few as 1 bit per measurement.

Regime change in action:  Consider the CS acquisition of a length N=1000 signal that is K=10 sparse subject to the fixed bit budget B=MB, where M is the number of measurements and B is the number of bits per measurement. In each experiment, we varied the input SNR (ISNR) between 5dB and 45dB and searched for the (M,B) pair that maximized the reconstruction SNR given (a) B=N, (b) B=2N, (c) B=5N.  The solid line (blue) corresponds to the number of measurements M, while the dashed line (green) corresponds to the bit-depth B.  The left side of each plot corresponds to the QC regime, while the right side corresponds to the MC regime. In each plot there is a sharp transition between optimal bit-depth being high (B>5) and and low (B<2).  Moreover, for moderate to low ISNR, the best performance is achieved by taking just 1 bit per measurement.

A. C. Sankaranarayanan, C. Hegde, S. Nagaraj, and R. G. Baraniuk, “Go with the flow: Optical flow-based transport operators for image manifolds,” Allerton Conference on Communication, Control and Computing, Allerton, IL, USA, September, 2011.

S. Nagaraj, A. C. Sankaranarayanan, and R. G. Baraniuk, “A Theory for Optical Flow-based Transport on Image Manifolds,” preprint, November, 2011.

Abstract:  Image articulation manifolds (IAMs) play a central conceptual role in a host of computer vision and image understanding problems. The core premise is that we can view a collection of images, each of which is indexed by a small number of degrees of freedom (3D camera pose, motion/deformation, etc.), as a low-dimensional nonlinear manifold. In order to perform parameter estimation and navigation on an IAM, we require a transport operator that traverses the manifold from image to image. The two current approaches to manifold transport suffer from major shortcomings that have limited the practical impact of manifold methods. First, algebraic methods require that the IAM possess an unrealistic algebraic structure. Second, locally linear methods based on a tangent plane approximation cannot cope with the non-differentiability of IAMs containing images with sharp edges. In this paper, we demonstrate that the optical flow between pairs of images on an IAM is a valid transport operator with a number of attractive properties. In particular, we establish that the optical flow forms a low-dimensional smooth manifold. Several experiments involving novel-view synthesis, geometric clustering, and manifold charting validate that the optical flow manifold approach both offers performance significantly superior to current approaches and is practical for real-world applications.

An example from the paper illustrating the efficacy of OFM based image synthesis.  We compare classical locally linear modeling of an IAM versus optical flow-based transport for synthesizing new images on an IAM. We aim to synthesize images on the IAM that lie “between” two given input images. The non-differentiability of IAMs cannot be accurately captured by locally linear tangent spaces and transport; hence the corresponding synthesized images exhibit severe blurring and cross-fading artifacts. In contrast, optical flow-based transport results in sharp, realistic images.  (Click on the image to zoom in.)

Another example from the paper illustrating the efficacy of OFM based manifold learning.  We generated an IAM by cropping 200×200 pixel patches at random from a larger image, thereby generating a 2D translation manifold. (a) Sample images from the IAM showing several images at various translations. (b) Sampling of the
parameter space. 2D embeddings obtained on (c) the IAM vs. (d) the OFM. Note the near perfect isometry to the parameter space in (d).