IntroductionMathematical BackgroundSetup and CompressionSoftware ArchitectureHardware DesignMatrix-Vector MultiplierLFSR-Based Random Number GeneratorVGA ControllerDaubechie Wavelet TransformResultsConclusionWho Did WhatLessons LearnedMatLab CodeCompression and DecompressionSolveOMPCompression DecompressionDaubechie Wavelet Transform and Inverse Transform1d Daubechie Wavelet Transform2d Daubechie Wavelet TransformFull Image Daubechie Wavelet Transform1d Inverse Daubechie Wavelet TransformCPV code2d Inverse Daubechie Wavelet TransformFull Image Inverse Daubechie Wavelet TransformC CodeDaubechie Wavelet Inverse TransformDriverHeaderDecompression functionsCPV CodeTranspose Code1d Inverse Daubechie Wavelet Transform2d Inverse Daubechie Wavelet TransformFull Image Inverse Daubechie Wavelet TransformVHDL CodeMatrix Vector MultiplierColumn ModuleAccumulatorLFSRSingle-Port RAMVGA RasterHardware Decompresssion for CompressedSensing ApplicationsKeith Dronson Frank Zovko Samuel SubbaraoFederico GarciaMay 16, 2009Contents1 Introduction 22 Mathematical Background 23 Setup and Compression 44 Software Architecture 45 Hardware Design 55.1 Matrix-Vector Multiplier . . . . . . . . . . . . . . . . . . . . . . . 55.2 LFSR-Based Random Number Generator . . . . . . . . . . . . . 65.3 VGA Controller . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Daubechie Wavelet Transform 67 Results 98 Conclusion 108.1 Who Did What . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108.2 Lessons Learned . . . . . . . . . . . . . . . . . . . . . . . . . . . 11A MatLab Code 11A.1 Compression and Decompression . . . . . . . . . . . . . . . . . . 11A.1.1 SolveOMP . . . . . . . . . . . . . . . . . . . . . . . . . . . 11A.1.2 Compression Decompression . . . . . . . . . . . . . . . . . 15A.2 Daubechie Wavelet Transform and Inverse Transform . . . . . . . 17A.2.1 1d Daubechie Wavelet Transform . . . . . . . . . . . . . . 17A.2.2 2d Daubechie Wavelet Transform . . . . . . . . . . . . . . 17A.2.3 Full Image Daubechie Wavelet Transform . . . . . . . . . 17A.2.4 1d Inverse Daubechie Wavelet Transform . . . . . . . . . 17A.2.5 CPV code . . . . . . . . . . . . . . . . . . . . . . . . . . . 181A.2.6 2d Inverse Daubechie Wavelet Transform . . . . . . . . . 18A.2.7 Full Image Inverse Daubechie Wavelet Transform . . . . . 18B C Code 19B.1 Daubechie Wavelet Inverse Transform . . . . . . . . . . . . . . . 19B.1.1 Driver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19B.1.2 Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21B.1.3 Decompression functions . . . . . . . . . . . . . . . . . . . 21B.1.4 CPV Code . . . . . . . . . . . . . . . . . . . . . . . . . . 28B.1.5 Transpose Code . . . . . . . . . . . . . . . . . . . . . . . . 28B.1.6 1d Inverse Daubechie Wavelet Transform . . . . . . . . . 29B.1.7 2d Inverse Daubechie Wavelet Transform . . . . . . . . . 30B.1.8 Full Image Inverse Daubechie Wavelet Transform . . . . . 30C VHDL Code 31C.1 Matrix Vector Multiplier . . . . . . . . . . . . . . . . . . . . . . . 31C.2 Column Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41C.3 Accumulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43C.4 LFSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44C.5 Single-Port RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . 46C.6 VGA Raster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 IntroductionMost conventional approaches to sampling a signal are based on Shannon’ssampling theorem: the sampling rate should be twice the maximum frequencyin the signal (aka Nyquist rate). When it comes to pictures, which are not band-limited the sampling rate is determined by the desired resolution of the picture.Compressive sensing (CS) provides a way to recover an image from far fewersamples than would normally be necessary. CS relies on two basic principles:Sparsity and Incoherence[1]. Sparsity is the idea that the bandwidth of a signalmay be larger the actual number of “information” samples. This leads to thefact that if these samples were represented in the right basis Ψ they would beless sparse (more compressed). Incoherence extends the duality between timeand frequency: something that is compressed in Ψ will be spread out in thedomain that it was acquired in.2 Mathematical BackgroundThe typical approach to sensing is the following:yk= hf, φki (1)where f is the image to be sampled, φkis the sensing waveform, and ykisthe sampled data. If the φk’s are indicator functions of pixels, then the yk’s2are the typical image data collected from a camera. The complexity arises fromthe number of dimensions of y, which we’ll call n. One could try to take nmeasurements (more pixels in a CCD) or one could be clever and find a solutionthat allows them to undersample; say collect m samples instead of n. In thatcase one could create an m × n sensing matrix, A, composed of n rows of theφk’s: φ∗1, φ∗2, . . . , φ∗m(where a∗denotes the complex transpose). Since f is ndimensional, but y is of dimension m and y = Af, there are an infinite numberof possibilities for f . However in some cases there is a way out of this.SPARSITY: If f ∈ Rnand sampled in an n dimensional basis (φ1, φ2, . . . , φn),then we have the following relationship:f =nX1xiφi(2)However, if some of those xi’s are small there may be a subset of the φi’sthat almost add up to f . In that case:f =sX1xiφi(3)orf = Φxs(4)where Φ is an n × n matrix …
View Full Document
Unlocking...