COMPRESSIVE SENSING OF IMAGE AND COMPARISON WITH JPEG AND JPEG 2000Name: SANIL FULANIStudent Id: 1000645167EE 5359 : Multimedia ProcessingNote: This report is just a proposal report for the project. It should not be considered asfinal report. ©Sanil FulaniTOPICS COVERED• OVERVIEW OF COMPRESSIVE SAMPLING• PROCESS OF CONVENTIONAL COMPRESSION• COMPRESSIVE SENSINGCONCEPT FOR IMPLEMENTATION• COMPARISON WITH JPEG IMAGE COMPRESSION• CHALLENGE• APPLICATION• PROGRESS CHARTOverviewTechnological development• Exploded since 2006• Pixel growing crunch size better compression algorithm rise of “ COMPRESSIVE SENSING (CS)” • Compressive sensing below Nyquist rate Against Shannon’s Theory• CS enables ‘Design of Digital Acquisition devices’• Measurements Inter-products with some random ‘basis’ functions.• Hardware single- pixel camera• Signals are sparse.Schematic of Rice 1-pixel cameracourtesy RICE UNIVERSITYPhysical Implementation of the cameracourtesy RICE UNIVERSITY6Introduction to Data Acquisition• Shannon/Nyquist Sampling Theorem– Must sample more than twice the signal bandwidth,– Might end up with a huge number of samples Need to Compress!– Doing more work than needed?SampleCompressxNKTransmit/StoreN > KTransformEncoderConventional Process of Compression• After data acquisition DCT • Many coefficients zero discarded before quantization • This makes Compressive Sampling applicable where Nyquist rate is high where compressing sheer volume of samples problem for transmission and storageCompressive Sensing• Split image small non-overlapping blocks of equal size apply DCT on blocks found to be sparse.• Sparse blocks selection: Let C – a small positive constant.T – an integer threshold i.e. representative of avg no. of non-significant DCT coefficients over all blocks• No. of DCT coefficients less than C larger than TThe block selected as reference for Compressing SamplingCompressive SensingFig. Compressive sensing based data acquisition systemConcept• Let x = {x[1], . . . ,x[N]} be a set of N pixels of an image. Let s be the representation of ‘x’ in the transform domain, that is:• Let y be an M-length measurement vector given by: , where is a M N measurement matrix(independent identically distributed (i.i.d.) Gaussian matrix). The above expression can be written in terms of s as:• K < M << N Reduce Redundancy by selecting M-samples of signal.Signal Recovery• Orthogonal Matching Pursuit (OMP) algorithm– Where, all sampled coefficients less than C set to zero– Hence, for C>0, sampling process always ‘lossy’– i.e. if N-K , non-significant samples then atleastM=K+1 samples needed for reconstruction– It even fails when M is too low, or all DCTcoefficients are zero or if division by zero in OMPalgorithm appears.• Other approach1) L0 norm• L0 sparsest coefficients• Unfortunately its complex hence fails2) L2 norm• Pros: simple mathematically (involving only a matrixmultiplication by the pseudo-inverse of the basissampled in).• Cons: poor results for most practical applications, asthe unknown (not sampled) coefficients seldom havezero energy.• Hence, following Tao, the L1 norm, or the sum of the absolute values, is usually what is minimized. • Finding the candidate with the smallest L1 norm can beexpressed relatively easily as a linear program, for whichefficient solution methods already exist. This leads tocomparable results as using the L0 norm, often yieldingresults with many coefficients being zero.• This optimization also known as BASIS PURSUIT• excellent approximation via the L1 norm minimization is given by:Block Diagram of JPEG BaselineCHALLENGE• CS replaces conventional sampling andreconstruction linear measurement scheme• However , will work ‘ONLY IF SOURCE IS SPARSE’• Challenge to predict which sources are sparse in aparticular domain.• Applying CS whole image ineffective• Hence, split image small non-overlappingblocks of equal size apply CS on blocks foundto be sparseAPPLICATION• Analog to Digital Conversion - a fundamentalaspect of Wireless Communications.• Eg. CDMA voice msg 4096 hertzstandard freq spreads over radio spectrum span thousands of hertz• Here signal still sparse so detectorrecover signal more rapidly then Shannon’stheorem.Other Applications• Data Acquisition• Data Compression• Image and Video CompressionPROGRESS CHART• February 28, 2010 – Research Reading oncompressive sensing and informationgathering• March 20, 2010 – complete research readingand jpeg simulation part• April 10, 2010 – complete compressivesensing coding• April 20, 2010 – Final touch anddocumentation reportReferences• Emmanuel Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. (IEEE Trans. on Information Theory, 52(2) pp. 489 - 509, February 2006)• Madhu Krishnan, Compressive sensing for video acquisition, University of Texas at Arlington.• Emmanuel Candès and Justin Romberg, Quantitative robust uncertainty principles and optimally sparse decompositions. (Foundations of Compute. Math., 6(2), pp. 227 - 254, April 2006)• David Donoho, Compressed sensing. (IEEE Trans. on Information Theory, 52(4), pp. 1289 - 1306, April 2006) • Emmanuel Candès and Justin Romberg, Practical signal recovery from random projections. (Preprint, Jan. 2005)References• Emmanuel Candès, Justin Romberg, and Terence Tao, Stable signal recovery from incomplete and inaccurate measurements. (Communications on Pure and Applied Mathematics, 59(8), pp. 1207-1223, August 2006)• Emmanuel Candès and Terence Tao, The Dantzig Selector: Statistical estimation when p is much larger than n (To appear in Annals of Statistics) • Holger Rauhut, Karin Schass, and Pierre Vandergheynst, Compressed sensing and redundant dictionaries. (IEEE Trans. on Information Theory, 54(5), pp. 2210 - 2219, May 2008)• Albert Cohen, Wolfgang Dahmen, and Ronald DeVore, Compressed sensing and best k-term approximation. (Preprint, 2006) [Formerly titled "Remarks on compressed sensing"]References• Emmanuel Candès and Michael Wakin, An introduction to compressive sampling. (IEEE Signal Processing Magazine, 25(2), pp. 21 - 30, March 2008) • Justin Romberg, Imaging via
View Full Document
Unlocking...