Compressive Sensing Full report
Wifi Active In SP Posts: 158 Joined: Oct 2010 
30102010, 09:42 AM
ABSTRACT This report present a novel idea to capture and represent compressible signals for transmission and storage at a rate below the Nyquist rate. This method is known as compressive sampling/sensing employs non adaptive linear project and implimentationions that preserve the structure of the signal. The signal is reconstruced from these project and implimentationions using optimization techniques. Compressive Sensing.pdf (Size: 470.95 KB / Downloads: 115) TABLE OF CONTENTS 1 Introduction 1 2 Data Compression 3 2.1 Types of Data Compression . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Lossy Compression . . . . . . . . . . . . . . . . . . . . . . 5 2.1.2 Lossless Compression . . . . . . . . . . . . . . . . . . . . 6 2.2 Different Types of Data Compression . . . . . . . . . . . . . . . . 7 2.2.1 Variable Length Coding(VLC) . . . . . . . . . . . . . . . . 7 2.2.2 Runlength encoding (RLE) . . . . . . . . . . . . . . . . . 7 2.2.3 Differential coding . . . . . . . . . . . . . . . . . . . . . . 7 2.2.4 Predictive coding . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.5 Dictionary based coding . . . . . . . . . . . . . . . . . . . 8 2.2.6 Transform coding . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.7 Wavelet coding . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Transform Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Compressive Sensing 11 3.1 Steps in Compressive Sensing . . . . . . . . . . . . . . . . . . . . 11 3.2 Sparse Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 Compressible Signals . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.4 Designing a Stable Measurement Matrix . . . . . . . . . . . . . . . 15 i 3.5 Designing a Signal Reconstruction Algorithm . . . . . . . . . . . . 16 3.5.1 Different Methods of Reconstruction . . . . . . . . . . . . 17 3.5.2 Geometrical Interpretation . . . . . . . . . . . . . . . . . . 18 4 Application 20 4.1 Single Pixel Camera . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.1.1 Advantages . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.1.2 Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 Magnetic Resonance Imaging . . . . . . . . . . . . . . . . . . . . . 23 4.2.1 Rapid 3D Angiography . . . . . . . . . . . . . . . . . . . . 23 4.2.2 Whole Heart Coronary Imaging . . . . . . . . . . . . . . . 24 4.2.3 Brain Imaging . . . . . . . . . . . . . . . . . . . . . . . . 25 5 Conclusion 26 ii LIST OF FIGURES 3.1 Block diagram representation of compressive sampling [1]. . . . . . 13 3.2 (a) Compressive sensing measurement process with a random Gaussian matrix and discrete cosine transform (DCT) matrix (b) Measurement process with = [1]. . . . . . . . . . . . . . . . . . . . . 16 3.3 Geometrical interpretation (a) The subspaces containing two sparse vectors in R3 lie close to the coordinate axes. (b) Visualization of the l2 minimization © Visualization of the l1 minimization [1]. . . . . . . 18 4.1 Structure of camera [3]. . . . . . . . . . . . . . . . . . . . . . . . . 21 iii CHAPTER 1 Introduction As our modern technologydriven civilization acquires and exploits everincreasing amounts of data, ‘everyone’ now knows that most of the data we acquire ‘can be thrown away’ with almost no perceptual loss  witness the broad success of lossy compression formats for sounds, images and specialized technical data. The phenomenon of ubiquitous compressibility raises very natural questions: why go to so much effort to acquire all the data when most of what we get will be thrown away? Can’t we just directly measure the part that won’t end up being thrown away? Compressive sensing, also known as compressive sampling is a technique for acquiring and reconstructing a signal utilizing the prior knowledge that it is sparse or compressible. In this method a signal of length N is taken and converted to a signal of length M where M << N prior to storage or transmission. The ideas behind compressed sensing came together in or about 2004 when David Donoho, Emmanuel Candes, Justin Romberg and Terence Tao discovered important results on the minimum number of data needed to reconstruct an image even though the number of data would be deemed insufficient by the NyquistShannon criterion. The main idea behind compressed sensing is to exploit that there is some structure and redundancy in the majority of interesting signalsthey are not pure noise. In particular, most signals are sparse, that is, they contain many coefficients close to or equal to zero, when represented in some domain. In the report that is presented a complete analysis of compressive sensing or compressive sampling is explained. As we know, the basis behind compressive sampling is data compression. Therefore we have started with explaining what data compression is. It is followed by different methods of data compression. The most commonly used method is transform coding. Therefore there is a detailed explanation of transform coding and the inefficiencies associated with it . Then we have entered into what exactly compressive sensing is and what are the different steps involved in compressive sensing. It is followed by a detailed mathematical explanation of this method. Finally we have also explained two applications of compressive sensing that have been developed recently the single pixel camera and the magnetic resonance imaging. 2 CHAPTER 2 Data Compression Data compression is often referred to as coding, where coding is a very general term encompassing any special representation of data which satisfies a given need. Information theory is defined to be the study of efficient coding and its consequences, in the form of speed of transmission and probability of error. Data compression may be viewed as a branch of information theory in which the primary objective is to minimize the amount of data to be transmitted. A simple characterization of data compression is that it involves transforming a string of characters in some representation (such as ASCII) into a new string (of bits, for example) which contains the same information but whose length is as small as possible. Data compression has important application in the areas of data transmission and data storage. Many data processing applications require storage of large volumes of data, and the number of such applications is constantly increasing as the use of computers extends to new disciplines. At the same time, the proliferation of computer communication networks is resulting in massive transfer of data over communication links. Compressing data to be stored or transmitted reduces storage and/or communication costs. When the amount of data to be transmitted is reduced, the effect is that of increasing the capacity of the communication channel. Similarly, compressing a file to half of its original size is equivalent to doubling the capacity of the storage medium. It may then become feasible to store the data at a higher, thus faster, level of the storage hierarchy and reduce the load on the input/output channels of the computer system. One area in which data compression is of great importance is image representation and processing. There are two major reasons for this. The first is that digitized images contain a large amount of local redundancy. An image is usually captured in the form of an array of pixels whereas methods which exploit the tendency for pixels of like color or intensity to cluster together may be more efficient. The second reason for the abundance of research in this area is volume. Digital images usually require a very large number of bits, and many uses of digital images involve large collections of images. Image compression deals with reducing the amount of data required to represent a digital image by removing of redundant data. Images can be represented in digital format in many ways. Encoding the contents of a 2D image in a raw bitmap (raster) format is usually not economical and may result in very large files. Since raw image representations usually require a large amount of storage space (and proportionally long transmission times in the case of file uploads/ downloads), most image file formats employ some type of compression. The need to save storage space and shorten transmission time, as well as the human visual system tolerance to a modest amount of loss, have been the driving factors behind image compression techniques. The general problem of image compression is to reduce the amount of data required to represent a digital image or video and the underlying basis of the reduction process is the removal of redundant data. Mathematically, visual data compression typically involves transforming (encoding) a 2D pixel array into a statistically uncorrelated data set. This transformation is applied prior to storage or transmission. At some later time, the compressed image is decompressed to reconstruct the original image information (preserving or lossless techniques) or an approximation of it (lossy techniques). Several common measures of compression have been suggested: redundancy , average message length , and compression ratio. Image compression and coding techniques explore three types of redundancies: coding redundancy, interpixel (spatial) redundancy, and psychovisual redundancy. i Coding Redundancy Consists in using variablelength codewords selected as to match the statistics of the original source, in this case, the image itself or a processed version of its pixel values. This type of coding is always reversible and usually implemented using lookup tables (LUTs). Examples of image coding schemes that explore coding redundancy are the Huffman codes and the arithmetic coding technique. ii Interpixel Redundancy This type of redundancy  sometimes called spatial redundancy, interframe redundancy, or geometric redundancy  exploits the fact that an image very often contains 4 strongly correlated pixels, in other words, large regions whose pixel values are the same or almost the same. This redundancy can be explored in several ways, one of which is by predicting a pixel value based on the values of its neighboring pixels. Examples of compression techniques that explore the interpixel redundancy include: Constant Area Coding (CAC), (1D or 2D) RunLength Encoding (RLE) techniques, and many predictive coding algorithms such as Differential Pulse Code Modulation (DPCM). iii Psychovisual Redundancy Many experiments on the psychophysical aspects of human vision have proven that the human eye does not respond with equal sensitivity to all incoming visual information; some pieces of information are more important than others. The knowledge of which particular types of information are more or less relevant to the final human user have led to image and video compression techniques that aim at eliminating or reducing any amount of data that is psychovisually redundant. The end result of applying these techniques is a compressed image file, whose size and quality are smaller than the original information, but whose resulting quality is still acceptable for the application at hand. 2.1 Types of Data Compression 2.1.1 Lossy Compression Lossy or perceptual coding, is possible if some loss of fidelity is acceptable. Generally, a lossy data compression will be guided by research on how people perceive the data in question. For example, the human eye is more sensitive to subtle variations in luminance than it is to variations in color. JPEG image compression works in part by "rounding off" some of this lessimportant information. Lossy data compression provides a way to obtain the best fidelity for a given amount of compression. In some cases, transparent (unnoticeable) compression is desired; in other cases, fidelity is sacrificed to reduce the amount of data as much as possible. Lossy image compression is used in digital cameras, to increase storage capacities with minimal degradation of picture quality. Similarly,DVDs use the lossy MPEG2 Video codec for video compression. In lossy audio compression, methods of psychoacoustics are used to remove nonaudible 5 (or less audible) components of the signal. Compression of human speech is often performed with even more specialized techniques, so that speech compression" or "voice coding" is sometimes distinguished as a separate discipline from "audio compression". Different audio and speech compression standards are listed under audio codecs. Voice compression is used in Internet telephony for example, while audio compression is used for CD ripping and is decoded by audio players. A lossy compression is acceptable mainly for three reasons: The human visual system is often able to tolerate loss in image quality without compromising the ability to perceive the contents of the scene. It happens very often that the digital input of the lossy compression algorithm is, in its turn, an imperfect representation of the real image. It should be considered, indeed, that the image is reconstructed starting from a finite number of samples, which can take only discrete values. A lossless compression would never be able to grant the high levels of compression that can be obtained by using a lossy compression and that are necessary for applications in storage and/or distribution of images. 2.1.2 Lossless Compression Lossless compression algorithms usually exploit statistical redundancy in such a way as to represent the sender’s data more concisely without error. Lossless compression is possible because most realworld data has statistical redundancy. For example, in English text, the letter ‘e’ is much more common than the letter ’z’, and the probability that the letter ’q’ will be followed by the letter ‘z’ is very small. Lossless compression schemes are reversible so that the original data can be reconstructed. LempelZiv (LZ) compression methods are among the most popular algorithms for lossless storage. DEFLATE is a variation on LZ which is optimized for decompression speed and compression ratio, therefore compression can be slow. DEFLATE is used in PKZIP, gzip and PNG. LZW (LempelZivWelch) is used in GIF images. Also noteworthy are the LZR (LZRenau) methods, which serve as the basis of the Zip method. LZ methods utilize a tablebased compression model where table entries are substituted for repeated strings of data. For most LZ methods, this table is generated dynamically from earlier data in the input. The table itself is often Huffman encoded (e.g. SHRI, LZX). A 6 current LZbased coding scheme that performs well is LZX, used in Microsoft’s CAB format. Lossless compression is preferable when In medical applications, when it is difficult to choose an acceptable error level for image representation. In those cases when we deal with highly structured images (typically nonnatural ones) like texts or graphics, which are usually more easily handleable by the means of lossless compression techniques. In all those applications when images are frequently modified or recompressed: using a lossy coding, there would be too many errors in the image that would make the quality absolutely unacceptable. 2.2 Different Types of Data Compression 2.2.1 Variable Length Coding(VLC) Most entropybased encoding techniques rely on assigning variablelength codewords to each symbol, whereas the most likely symbols are assigned shorter codewords. In the case of image coding, the symbols may be raw pixel values or the numerical values obtained at the output of the mapper stage (e.g., differences between consecutive pixels, runlengths, etc.). The most popular entropybased encoding technique is the Huffman code. It provides the least amount of information units (bits) per source symbol. 2.2.2 Runlength encoding (RLE) RLE is one of the simplest data compression techniques. It consists of replacing a sequence (run) of identical symbols by a pair containing the symbol and the run length. It is used as the primary compression technique in the 1D CCITT Group 3 fax standard and in conjunction with other techniques in the JPEG image compression standard. 2.2.3 Differential coding Differential coding techniques explore the interpixel redundancy in digital images. The basic idea consists of applying a simple difference operator to neighboring pixels to calculate a difference image, whose values are likely to follow within a much narrower 7 range than the original graylevel range. As a consequence of this narrower distribution and consequently reduced entropyHuffman coding or other VLC schemes will produce shorter codewords for the difference image. 2.2.4 Predictive coding Predictive coding techniques constitute another example of exploration of interpixel redundancy, in which the basic idea is to encode only the new information in each pixel. This new information is usually defined as the difference between the actual and the predicted value of that pixel. 2.2.5 Dictionary based coding Dictionarybased coding techniques are based on the idea of incrementally building a dictionary (table) while receiving the data. Unlike VLC techniques, dictionarybased techniques use fixedlength codewords to represent variablelength strings of symbols that commonly occur together. Consequently, there is no need to calculate, store, or transmit the probability distribution of the source, which makes these algorithms extremely convenient and popular. The bestknown variant of dictionarybased coding algorithms is the LZW (LempelZivWelch) encoding scheme, used in popular multimedia file formats such as GIF, TIFF, and PDF. 2.2.6 Transform coding The techniques discussed so far work directly on the pixel values and are usually called spatial domain techniques. Transform coding techniques use a reversible, linear mathematical transform to map the pixel values onto a set of coefficients, which are then quantized and encoded. The key factor behind the success of transformbased coding schemes many of the resulting coefficients for most natural images have small magnitudes and can be quantized (or discarded altogether) without causing significant distortion in the decoded image. Different mathematical transforms, such as Fourier (DFT), WalshHadamard (WHT), and KarhunenLoeve (KLT), have been considered for the task. 8 2.2.7 Wavelet coding Wavelet coding techniques are also based on the idea that the coefficients of a transform that decorrelates the pixels of an image can be coded more efficiently than the original pixels themselves. The main difference between wavelet coding and DCTbased coding is the omission of the first stage. Because wavelet transforms are capable of representing an input signal with multiple levels of resolution, and yet maintain the useful compaction properties of the DCT, the subdivision of the input image into smaller subimages is no longer necessary. 2.3 Transform Coding Transform coding is a type of data compression for "natural" data like audio signals or photographic images. The transformation is typically lossy, resulting in a lower quality copy of the original input. In transform coding, knowledge of the application is used to choose information to discard, thereby lowering its bandwidth. The remaining information can then be compressed via a variety of methods. When the output is decoded, the result may not be identical to the original input, but is expected to be close enough for the purpose of the application. Transform coding is used to convert spatial image pixel values to transform coefficient values. Since this is a linear process and no information is lost, the number of coefficients produced is equal to the number of pixels transformed. The desired effect is that most of the energy in the image will be contained in a few large transform coefficients. If it is generally the same few coefficients that contain most of the energy in most pictures, then the coefficients may be further coded by lossless entropy coding. In addition, it is likely that the smaller coefficients can be coarsely quantized or deleted (lossy coding) without doing visible damage to the reproduced image. The energy of a pixel may be defined as the square of its value times some scaling factor. Similarly, the energy of a transform coefficient may be defined as the square of its value times some scaling factor. With the proper scaling factor, the total energy of the pixels in a picture will always equal the total energy in the transform coefficients. The transform process simply concentrates the energy into particular coefficients, generally the "low 9 frequency" ones. Many types of transforms have been tried for picture coding, including for example Fourier, KarhonenLoeve,WalshHadamard, lapped orthogonal, discrete cosine (DCT), and recently, wavelets. The various transforms differ among themselves in three basic ways that are of interest in picture coding: 1. The degree of concentration of energy in a few coefficients; 2. The region of influence of each coefficient in the reconstructed picture; 3. The appearance and visibility of coding noise due to coarse quantization of the coefficients. Fourier transforms (discrete) have good energy concentration characteristics, but become unwieldy when dealing with large images requiring large numbers of coefficients. Block transforms, which work on a small portion of the image at a time, are therefore preferred. The discrete Fourier transform may be applied to a block of pixels. Other transforms which fall in this category are WalshHadamard, and the DCT. The lapped orthogonal transforms are a special case in which the coefficients’ influence is confined to a few adjacent blocks, with a taperingoff influence toward the edges. Because of ease of hardware computation and generally very good energy concentration for a wide range of natural images, the DCT has become the transform of choice for many image coding schemes, including MPEG. The DCT, unlike the Fourier transform, is spatially variant. A portion of a sine wave coded with a Fourier transform has all the energy concentrated at the same frequency coefficients regardless of the phase of the sinusoid (although the energy will be apportioned differently between the sine and cosine components). The DCT, on the other hand, is sensitive to phase, so that an object moving across the screen will have different frequency content from frame to frame. This also means that the visibility of coding artifacts due to coefficient quantization will vary somewhat depending on the position of an object (edge) in the image. Also, because the DCT is a strictly bounded block transform, lossy coding will produce blockedge mismatch which will be visible at some level of quantization even if there is only low frequency content in that area. 10 CHAPTER 3 Compressive Sensing One of the central tenets of signal processing is the Nyquist/Shannon sampling theory: the number of samples needed to reconstruct a signal without error is dictated by its bandwidth  the length of the shortest interval which contains the support of the spectrum of the signal under study. Compressive sensing shows that superresolved signals and images can be reconstructed from far fewer data/measurements than what is usually considered necessary. Compressed sensing is a new rapidly growing research field emerging which investigates ways in which we can sample signals at roughly the "information rate" rather than the Nyquist rate. For example compressed sensing theory has already enabled a 4fold reduction in acquisition time for MRI images by allowing the undersampling of kspace. It is potentially a very disruptive technology and provides a new way of thinking about how to acquire and code signals in the most efficient manner. It has a growing number of applications that are being explored across a range of disciplines, including: 1. Medical imaging 2. Seismic imaging 3. Distributed and remote sensing 4. Analogue to Information (Digital) Conversion 3.1 Steps in Compressive Sensing There are two main components to compressed sensing: the sampling strategy and the reconstruction algorithm. i Sampling conventional sampling involves measuring a quantity at regular intervals (so as to satisfy Nyquist), the concept of sampling in compressed sensing is much more general. Sampling in compressed sensing consists of making a random linear project and implimentationion of the signal into a low dimensional space. While this is essentially what is required for the theory researchers have found empirically that the same ideas can often be used in much more conventional sampling scenarios. For example MRI scanners sample lines within the spatial Fourier domain of the image and there are already initial examples of compressed sensing techniques for MRI using randomized trajectories and even deterministic trajectories (sampling a small number of radial lines) in the Fourier space. ii Reconstruction The key difference between conventional sampling and compressed sensing is that the reconstruction operator is nonlinear. Essentially this selects the significant coefficients for the data in some sparse representation and then calculates a least squares approximation using the associated basis functions. While this sounds relatively easy it should be noted that finding the significant coefficients is a combinational search problem and in practice cannot be solved directly. Instead much of the theory of compressed sensing has concentrated on proving that near optimal performance is possible by using either a convex relaxation that boils down to solving a linear or quadratic program or greedy algorithms that iteratively select the coefficients in a greedy way one at a time or in groups. 3.2 Sparse Signals Since the 1990s, modeling signals through sparsity has emerged as an important and widely applicable technique in signal processing. Its most wellknown success is in image processing, where great advances in compression and estimation have come from modeling images as sparse in a wavelet domain. Consider an Ndimensional vector x that can be represented as x = V u, where V is some orthogonal NbyN matrix and u 2 RN has only K nonzero entries. In this case, we say that u is Ksparse and that x is Ksparse with respect to V . The set of positions of nonzeros coefficients in u is called the sparsity pattern, and we call = K=N the sparsity ratio Knowing that x is K sparse with respect to a given basis V can be extremely valuable for signal processing. For example, in compression, x can be represented by the K positions and values of the nonzero elements in u, as opposed to the N elements of x. When the sparsity ratio is small, the compression gain can be significant. Simi 12 Figure 3.1: Block diagram representation of compressive sampling [1]. larly, in estimating x in the presence of noise, one only has to estimate K as opposed to N real parameters.Another important property of sparse signals has recently been uncovered: they can be recovered in a computationally tractable manner from a relatively small number of random samples. The method, known as compressive sampling. A basic model for compressive sampling is shown in Figure 3.1. The Ndimensional signal x is assumed to beKsparse with respect to some orthogonal matrix V . The "sampling" x is represented as a linear transformation by a matrix yielding a sample vector y = x. Let the size of beMbyN, so y hasM elements; we call each element of y a measurement of x. A decoder must recover the signal x from y knowing V and , but not necessarily the sparsity pattern of the unknown signal u. Since u is Ksparse, x must belong to one of NCK subspaces in RN. Similarly, y must belong to one of NCK subspaces in RM. For almost all s with M = K + 1, an exhaustive search through the subspaces can determine which subspace x belongs to and thereby recover the signal’s sparsity pattern and values. Therefore, in principle, a K sparse signal can be recovered from as few as M = K + 1 random samples. Unfortunately, the exhaustive search described above is not tractable for interesting sizes of problems since the number of subspaces to search, NCK , can be enormous; if is held constant as N is increased, the number of subspaces grows exponentially with N. The remarkable main result of compressive sampling is to exhibit recovery methods that are computationally feasible, numerically stable, and robust against noise while requiring a number of measurements not much larger than K. 13 3.3 Compressible Signals Consider a realvalued, finitelength, onedimensional, discretetime signal x, which can be viewed as an N by 1 column vector in RN with elements x[n], n = 1; 2; : : : ;N. (We treat an image or higherdimensional data by vectorizing it into a long onedimensional vector.) Any signal in RN can be represented in terms of a basis of N1 vectors i i = 1; : : : ;N. For simplicity, assume that the basis is orthonormal. Using the N by N basis matrix = [ 1j 2j : : : j N] with the vectors i as columns, a signal x can be expressed as x = XN i=1 si i ) x = s (3.1) where s is the N by 1 column vector of weighting coefficients si =< x; i >= T i x and T denotes transposition. Clearly, x and s are equivalent representations of the signal, with x in the time or space domain and s in the domain. The signal x is Ksparse if it is a linear combination of only K basis vectors; that is, only K of the si coefficients in (3.1) are nonzero and (N CHAPTER 4 Application 4.1 Single Pixel Camera A conventional digital camera works by capturing light from an object and focusing it through a lens onto an array of sensors. Cameras used by the general public operate in the visible range, 400 to 750 nm, with CMOS sensors. They can be modified to image in a slightly wider range, from 280 to 1200 nm, if their infrared (IR) filters are removed. The bulk of the cost of an IR camera is in its sensor array and the cooling system that regulates the array’s temperature. The array alone accounts for at least onethird of any IR camera’s price. The cooling system that helps reduce background noise and the effects of pixel bleeding is similarly expensive. Unfortunately, there is no Moore’s law for these sort of components. Unlike transistors, IR sensors and their cooling systems are not likely to decrease in size or cost anytime in the near future. Thus, while the camera’s image processing chips will probably become cheaper in the next few years, no such reduction in cost can be predicted for the sensor components. In fact, as the general trend in the camera industry is toward more pixels, it is likely that soon the cost of an IR camera will be almost solely determined by the price of its sensor array and this array’s cooling system. Therefore, to create an economical IR camera, the number of sensors and cost of their cooling system would have to be dramatically reduced, without severely damaging the camera’s resolution. In principle, a compressive sensing device needs only a single sensora single pixel. This camera that captures several thousand points of light in rapid succession We can take a picture with potentially millions of pixels, but using just a single detector element. Not only does the use of a single pixel remove the price of a sensor array from the picture, but also it has the potential to reduce the cost of the sensor cooling system. Since a single pixel device does not suffer from the pixelbleeding problem that necessitates a highquality cooling system in regular IR cameras, in a singlepixel camera an inexpensive cooling alternative just for removing background noise could be used. The basic operation of a compressive sensing camera is relatively simple. Light from an object is focused by a lens onto a digital micromirror Figure 4.1: Structure of camera [3]. device (DMD). A DMD is an array of tiny mirrors that can be tilted 10o to 12o, from "on" to "off" positions. In the "on" state, these mirrors reflect light from the object to a secondary lens, which focuses this light to the sensor. A spatial light modulator (SLM) modulates the intensity of a light beam according to a control signal. A simple example of a transmissive SLM that either passes or blocks parts of the beam is an overhead transparency. The DMD consists of an array of bacteriumsized, electrostatically actuated micromirrors, where each mirror in the array is suspended above an individual static random access memory (SRAM) cell . Each mirror rotates about a hinge and can be positioned in one of two states (+10 and 10 from horizontal)according to which bit is loaded into the SRAM cell; thus light falling on the DMD can be re flected in two directions depending on the orientation of the mirrors. Data from this sensor is sent to a signal processing unit, which manipulates data points to construct an image of the original object. To generate a set of useful data points for image reconstruction, the mirrors of the DMD are flipped into a series of random configurations, in each of which approximately half of the mirrors are in their on position. 4.1.1 Advantages The key benefit of the camera is that it needs much less information to assemble an image. Massive CCD arrays collect millions of pixels worth of data, which are typically compressed to keep file sizes manageable. The single pixel camera, on the other hand, compresses the image data via its hardware before the pixels are recorded. As a 21 result, it’s able to capture an image with only thousands of pieces of information rather than millions. In addition to requiring fewer measurements, this camera can image at wavelengths where is difficult or expensive to create a large array of sensors. It can also acquire data over time to enable video reconstructionWith this sort of research is that it may make conventional digital cameras much better. If a single pixel can do the job of an array of pixels, then we could potentially get each of the pixels in a megapixel camera to do extra duty as well. Effectively, the resolution of your camera with the techniques developed in a single pixel camera can be multiplied. The technology could make cameras much cheaper by reducing the number of pixels needed, or perhaps lead (some day) to gigapixel resolution from megapixel cameras. In addition, the researchers say, the single pixel detector can be replaced with devices that register other wavelengths of light, potentially leading to images collected with light outside the ranges that CCD and CMOS detectors can handle. The singlepixel camera is an optical computer that sequentially measures the inner products y[m] = hx; mi between an N pixel sampled version x of the incident lightfield from the scene under view and a set of twodimensional (2D) test functions fmg. Each mirror corresponds to a particular pixel in x and m and can be independently oriented either towards Lens 2 (corresponding to a one at that pixel in m) or away from Lens 2 (corresponding to a zero at that pixel in m). The reflected light is then collected by biconvex Lens 2 and focused onto a single photon detector (the single pixel) that integrates the product x[n]m[n] to compute the measurement y[m] = hx; mi as its output voltage. This voltage is then digitized by an A/D converter. Values of m between zero and one can be obtained by dithering the mirrors back and forth during the photodiode integration time. To obtain m with both positive and negative values , we estimate and subtract the mean light intensity from each measurement, which is easily measured by setting all mirrors to the fullon one position. To compute CS randomized measurements y = x , we set the mirror orientations m randomly using a pseudorandom number generator, measure y[m], and then repeat the process M times to obtain the measurement vector y. Since the DMD array is programmable, we can also employ test functions m drawn randomly from a fast transform such as aWalsh, Hadamard, or noiselet transform. 22 4.1.2 Disadvantages The prototype model requires about five minutes to take a single picture. That is because the camera must blink several thousand times to capture a complete image. 4.2 Magnetic Resonance Imaging Magnetic Resonance Imaging (MRI) is an essential medical imaging tool burdened by an inherently slow data acquisition process. The application of CS to MRI has the potential for significant scan time reductions, with benefits for patients and health care economics. MRI obeys two key requirements for successful application of CS: (1) medical imagery is naturally compressible by sparse coding in an appropriate transform domain (e.g., by wavelet transform); (2) MRI scanners naturally acquire samples of the encoded image in spatial frequency, rather than direct pixel samples. The transform sparsity of MR images and the coded nature of MR acquisition are two key properties enabling CS in MRI. In MRI, we look at a special case of CS where the sampled linear combinations are simply individual Fourier coefficients (kspace samples). CS has been able to make accurate reconstructions from a small subset of kspace, rather than an entire kspace grid. Four potential applications of CS in MRI: 1. Rapid Angiography 2. WholeHeart Coronary Imaging 3. Enhanced Brain Imaging 4.2.1 Rapid 3D Angiography Angiography is increasingly popular for diagnosis of vascular disease. It attempts to image blood vessels in the body and helps to detect aneurysms, vascular occlusions, stenotic disease and tumor feeder vessels. It also serves to guide surgical procedures and to monitor the treatment of vascular disease . Often, a contrast agent is injected, significantly increasing the blood signal and enabling rapid data acquisition. In angiography, a significant portion of the diagnostic information comes from imaging the dynamics of the contrast agent bolus. This requires high spatial and temporal resolution with a very large FOV  obviously a very difficult task. Today MR angiography scans are often undersampled obtaining improved spatial resolution and temporal resolution at the 23 expense of undersampling artifacts. CS is particularly suitable for angiography. Angiograms are inherently sparse images  already sparse in the pixel representation, and are sparsified even better by spatial finitedifferences The need for rapid high temporal and spatial resolution imaging means that undersampling is almost inevitable. CS offers to improve current strategies by significantly reducing the artifacts that result from undersampling. CS is able to significantly accelerate angiography imaging, enabling better temporal resolution or alternatively improving the resolution of current imagery without compromising scan time. The nonlinear reconstruction in CS avoids most of the artifacts that appear in linear reconstruction from undersampled data. 4.2.2 Whole Heart Coronary Imaging Xray coronary angiography is the gold standard for evaluating coronary artery disease, but it is invasive. Multislice xray CT is a noninvasive alternative, but generates high doses of ionizing radiation. MRI is emerging as a noninvasive, nonionizing alternative . Coronary arteries are constantly subject to heart and respiratory motion; highresolution imaging is therefore a challenging task. Heart motion can be handled by synchronizing acquisitions to the cardiac cycle (cardiac gating). Respiratory motion can be mitigated by long scans with navigated breathing compensation , or simply by short breathheld acquisitions . However, breathheld cardiac triggered collection schemes face strict timing constraints and very short imaging windows. The number of acquisitions is limited to the number of cardiac cycles in the breathhold period. The number of heartbeats per period is itself limited  patients in need of coronary diagnosis cannot be expected to hold their breath for long! Also, each acquisition must be very short to avoid motion blurring. On top of this, many slices need to be collected to cover the whole volume of the heart. Because of these constraints, traditionally breathheld cardiac triggered acquisitions have limited spatial resolution and only partial coverage of the heart . Compressed sensing can accelerate data acquisition, allowing the entire heart to be imaged in a single breathhold . To meet the strict timing requirements, the hardware efficient spiral kspace trajectory is used. For each cardiac trigger, a single spiral in kspace is acquired for each slice. The heart does move considerably during the imaging period, but because each acquisition is very short, each slice is relatively immune to motion and interslice motion is manifested as geometric distortion across 24 the slices rather than blurring. Geometric distortion has little effect on the clinical diagnostic value of the image. Even though spirals are very efficient, the strict timing limitations make is necessary to undersample kspace 2fold. To do so, undersampled variable density spirals are used. Such spirals have an incoherent PSF. When used with linear gridding reconstruction undersampling artifacts are incoherent and appear simply as added noise. Coronary images are generally piecewise smooth and are sparsified well by finitedifferences. CS reconstruction can suppress undersamplinginduced interference without degrading the image quality. 4.2.3 Brain Imaging Brain scans are the most common clinical application of MRI; most such scans are 2D Cartesian multislice. For scan time reasons and SNR reasons, the slices are often quite thick, often with large gaps between slices. The ideas of CS promise to reduce collection time while improving the resolution of current imagery. Indeed, by significantly undersampling the existing kspace, some of the saved collection time could be used to collect data from the missing slices, and still leave a shorter collection overall. Brain images exhibit transform sparsity in the wavelet domain. If incoherence can be obtained, the application may succeed. CHAPTER 5 Conclusion Signal acquisition based on compressive sensing can be far more efficient than traditional sampling for sparse or compressible signals. Moreover compressive sensing measurements are random in that the same random matrix works simultaneously many sparstifying bases with high probability. It is also robust in that the measurements have equal priority. Thus one or more measurements can be lost without corrupting the entire reconstruction. REFERENCES [1] Compressive Sensing, Richard G. Baraniuk IEEE Signal Processing Magazine July 2007 [2] D. Donoho, "Compressed sensing," IEEE Trans. Inform. Theory, vol. 52, no. 4, pp. 12891306, Apr. 2006 [3] D. Takhar, V. Bansal, M. Wakin, M. Duarte, D. Baron, J. Laska, K.F. Kelly, and R.G. Baraniuk, "A compressed sensing camera: New theory and an implementation using digital micromirrors," in Proc. Comput. Imaging IV SPIE Electronic Imaging, San Jose, Jan. 2006. [4] R.G. Baraniuk, M. Davenport, R. DeVore, and M.B. Wakin, "A simple proof of the restricted isometry principle for random matrices (aka the JohnsonLindenstrauss lemma meets compressed sensing)," Constructive Approximation, 2007 [5] "Compressed Sensing MRI" Michael Lustig, Student Member, IEEE, David L. Donoho Member, IEEE Juan M. Santos Member, IEEE, and John M. Pauly, Member, IEEE Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



