1. Field of the Invention
Embodiments of the present invention relate to systems and methods for compressive sampling in imaging.
2. Background Information
Conventional Sampling
Digital signal analysis requires conversion of analog signals into the discrete domain as a first step. This is governed by sampling theory which conventionally dictates that analog signals must be sampled at or above the Nyquist rate, which can be defined as twice the highest frequency component of the analog signal. For high bandwidth signals correspondingly high sampling rates can place a heavy load on the acquisition system.
Conventional Color Imaging
Images herein can be considered analog signals whose amplitude may represent some optical property such as intensity, color and polarization which may vary spatially but not significantly temporally during the relevant measurement period. In color imaging, Light intensity typically is detected by photosensitive sensor elements. Conventional image sensors are typically composed of a two dimensional regular tiling of these individual sensor elements. Color imaging systems need to sample the image in at least three basic colors to synthesize a color image. We use the term “basic colors” to refer to primary colors, secondary colors or any suitably selected set of colors that form the color space in which the imaging system represents the image. Color sensing may be achieved by a variety of means such as, for example, (a) splitting the image into three identical copies, separately filtering each into the basic colors, and sensing each of them using separate image sensors, or (b) using a rotating filter disk to transmit images filtered in each of the basic colors in turn onto the same image sensor.
However, the most popular design for capturing color images is to use a single sensor overlaid with a color filter array (“CFA”). This includes the straightforward design wherein the value of each output pixel is determined by three sensing elements, one for each basic color, usually arranged in horizontal or vertical stripes.
Other CFA designs, including the popular one described in Bayer, U.S. Pat. No. 3,971,065 entitled COLOR IMAGING ARRAY, use filters of different colors arranged mostly in regular, repeating patterns. All of these systems rely on a process called demosaicing, aka demosaicking, to reconstruct the three basic colors at each pixel location. Conventional demosaicing algorithms typically involve the use of, for example, interpolation techniques such as bilinear, demodulation and filtering and edge adaptive algorithms. Conventional demosaicing algorithms work well only if the high frequencies, corresponding to the fine detail, of images in the basic colors are correlated or have low high frequency energy content in at least one direction. In the absence of these high frequency characteristics, reconstructed images exhibit artifacts. Random CFAs have also been studied in Condat, “Random patterns for color filter arrays with good spectral properties” (Research Report of the IBB, Helmholtz Zentrum Munchen, no. 08-25, September 2008, Munich, Germany), but the reconstruction therein also relies on conventional demosaicing. As such the reconstructed images exhibit demosaicing artifacts except they are rendered visually less objectionable by randomization.
Signal Compression
Image compression is typically applied after digital image acquisition to enable reduction of the system data load during transmission and storage. Image compression is based on the observation that natural images and many synthetic ones are approximately sparse in some basis. This includes the Fourier related bases, for example, the discrete cosine transform (“DCT”), employed by JPEG and wavelets which rely on empirically observed hierarchical self similarity of natural images and underlies the JPEG2000 compression method.
Generalized Sensing
If the signal to be sampled is sparse in some basis, sampling at the Nyquist rate is an inefficient use of resources. Various attempts have been made to leverage this sparsity to reduce the sampling rate. Some techniques use restrictive signal models integrating prior knowledge of the expected structure of the signal to reduce the number of parameters required to be estimated. Adaptive multi-scale sensing uses prior knowledge of the expected multi-scale structure of the signal. This technique, while quite effective in reducing the number of measurements needed, suffers from the requirement of making serial measurements, a characteristic undesirable in imaging fast moving subjects.
Compressive Sensing
A new reduced rate sampling scheme called “compressive sensing” has been developed recently. The goal of compressive sensing reconstruction techniques is the solution of ill-posed inverse problems through the regularization scheme known as “sparsity promotion.” Ill-posed inverse problems here are concerned with reconstructing an original signal from a sampled data set of a transform of that signal, where the transform is non-invertible. Sparsity promotion uses prior statistical knowledge of the original signal's sparsity in some basis to search preferentially for solutions of ill-posed inverse problems that are also approximately sparse in that basis. See Candes et al., “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information” (IEEE Trans. on Information Theory, 52(2) pp. 489-509, February 2006), hereby incorporated by reference in its entirety. They showed that a reduced number of non-adaptive samples of an original signal in a sample basis that is incoherent with the basis in which the original signal is sparse is sufficient to recover the signal with little or no information loss. Incoherence here is a measure of dissimilarity between the two bases; more precisely, it is the largest magnitude of the inner product between any pair of basis vectors from the two respective bases. See Candes and Romberg, Sparsity and incoherence in compressive sampling. (Inverse Problems, 23(3) pp. 969-985, 2007). They derived an inverse relationship between the incoherence between the bases and the number of samples required to accurately reconstruct the original signal with high probability. Compressive sensing techniques thus reconstruct the original signal from an under-determined system of equations through a joint maximization of logical tenability and physical probability.
It was initially thought that L0 norm minimization requiring a computationally prohibitive combinatorial search would be required. Remarkably, it was later shown though that a much more computationally tractable linear programming approach would also work. This approach minimizes the L1 norm of the reconstruction in the sparse basis constrained by the known observations.
Several formulations for solving the inverse problem in compressive sensing have been proposed including “basis pursuit” and constrained and unconstrained convex quadratic programs. See Figueiredo et al., “Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems” (IEEE Journal on selected topics in Signal Processing, 2007), hereby incorporated by reference in its entirety.
One formulation consists of an unconstrained convex optimization problem
                                          min            x                    ⁢                                                                  y                -                Ax                                                    2            2                          +                  τ          ⁢                                                  x                                      1                                              Equation        ⁢                                  ⁢                  (          1          )                    where x is the solution in the sparse basis, rasterized into a single dimensioned vector, y is the observed image, also rasterized and A is the transformation matrix representing the change in basis from the sparse to the spatial domain. x, being the sparse representation, has fewer elements than y. The first term penalizes deviation from the observed data whereas the second term is an L1 norm that has been shown to penalize less sparse solutions. τ controls the relative weights of the two penalty terms.
Constrained convex optimization problem formulations also exist which minimize just the first or second term while constraining the other below a threshold.
Orthogonal matching pursuit (“OMP”) and its many variations such as Simultaneous Orthogonal Matching Pursuit, Staged Matching Pursuit, Expander Matching Pursuit, Sparse Matching Pursuit and Sequential Sparse Matching Pursuit form a popular class of algorithms that obtain an approximate solution quickly. Total variation (“TV”) minimization has been shown to produce improved reconstructions. See Candes et al., “Practical signal recovery from random projections” (IEEE Trans. Signal Processing, 2005), hereby incorporated by reference in its entirety. Yet another class of reconstruction algorithm is motivated by de-noising methods and includes iterated thresholding in a transform domain. Subsequent developments continue to further improve reconstruction quality and reduce the computational burden.
Compressive sensing is information scalable, i.e., even if too few samples exist to do an exact reconstruction, various levels of information can be extracted depending on the number of measurements.
As used herein “compressive sensing” (also known as “compressed sensing”) means reconstructing a signal using prior statistical knowledge of the original signal's approximate sparsity in some basis to search preferentially for solutions of an ill-posed inverse problem, based on samples of a transform of the original signal, that are also approximately sparse in that basis.
Numerous sparsity promoting solvers are available. A few salient ones are listed below:
GPSR: This solves a bound-constrained quadratic programming formulation using gradient projection algorithms. It is described in Figueiredo, Nowak, Wright, “Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems” (IEEE Journal on selected topics in Signal Processing, 2007), hereby incorporated by reference in its entirety, and is currently available at http://www.1x.it.pt/˜mtf/GPSR/.
l1-Magic: This solves a “linear programming” or second-order “cone programming” formulation. It is currently available at http://www.acm.caltech.edu/l1magic/ or may be obtained by request from the author Emmanuel Candes, Stanford University Department of Mathematics, 450 Serra Mall, Bldg. 380.
Sparsify: This contains a number of algorithms including several variants of OMP. It is currently available at http://www.personal.soton.ac.uk/tb1m08/sparsify/sparsify.html.
l1_ls: This solves the convex quadratic programming formulation of equation (1) using interior-point methods. It is currently available at http://www.stanford.edu/˜boyd/l1s/.
Compressive Imaging
Unfortunately, application of compressive sensing to imaging has suffered from drawbacks. Implementation of arbitrary sampling bases to achieve incoherence with any particular sparse basis would require each measurement to be a linear combination of all pixel values. Since acquiring all pixel values and then computing their linear combinations would defeat the purpose of compressive sensing, techniques have been developed that implement the projection into an arbitrary basis in either the optical domain before being sensed by the photosites or in the analog electrical domain before being digitized.
In one such technique, projection onto a different basis is done using a digital mirror device (“DMD”) and multiple samples are acquired serially. See Duarte et al., “Single-pixel imaging via compressive sampling.” (IEEE Signal Processing Magazine, 25(2), pp. 83-91, March 2008). Serial measurement is a characteristic undesirable in real-time imaging. Besides the additional cost of a DMD is justifiable only if the savings in sensor cost is significant. This is sometimes the case for detectors measuring beyond the edge of the visible spectrum but typically not for the visible spectrum itself.
Other techniques of implementing the projection into an arbitrary basis in the optical domain include replicating the image multiple times using micro-optomechanical devices or birefringent structures and filtering each replica differently before measurement. See Brady, U.S. Pat. No. 7,532,772, entitled CODING FOR COMPRESSIVE IMAGING. While these techniques do not require serial measurement, the optical processing adds significantly to the cost. Moreover, they do not capture color images.
Another technique discussed in Jacques, L., Vandergheynst, P., Bibet, A., Majidzadeh, V., Schmid, A., and Leblebici, Y., “CMOS compressed imaging by Random Convolution”, IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Apr. 19-24, 2009, does random convolutions of the image in the sampling step itself by interconnecting the outputs of various sensor elements electrically, effectively sampling in a basis different from the spatial basis. This affects a non-diagonal transformation in the spatial basis. Besides the cost of specialized hardware to do convolutions in hardware, this scheme suffers from the disadvantage of having to make serial measurements.
Accordingly, there is a need for a method and system for using compressive sensing in image processing in a computationally feasible, practical and economical way.