COMPRESSIVE SENSING OF IMAGE AND COMPARISON WITH JPEG AND JPEG 2000 Name SANIL FULANI Student Id 1000645167 EE 5359 Multimedia Processing Note This report is just a proposal report for the project It should not be considered as final report Sanil Fulani TOPICS COVERED OVERVIEW OF COMPRESSIVE SAMPLING PROCESS OF CONVENTIONAL COMPRESSION COMPRESSIVE SENSING CONCEPT FOR IMPLEMENTATION COMPARISON WITH JPEG IMAGE COMPRESSION CHALLENGE APPLICATION PROGRESS CHART Overview Technological 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 camera courtesy RICE UNIVERSITY Physical Implementation of the camera courtesy RICE UNIVERSITY Introduction 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 N K x Sample Transform N Encoder Compress K Transmit Store Doing more work than needed 6 Conventional 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 storage Compressive 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 T The block selected as reference for Compressing Sampling Compressive Sensing Fig Compressive sensing based data acquisition system Concept 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 atleast M K 1 samples needed for reconstruction It even fails when M is too low or all DCT coefficients are zero or if division by zero in OMP algorithm appears Other approach 1 L0 norm L0 sparsest coefficients Unfortunately its complex hence fails 2 L2 norm Pros simple mathematically involving only a matrix multiplication by the pseudo inverse of the basis sampled in Cons poor results for most practical applications as the unknown not sampled coefficients seldom have zero 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 be expressed relatively easily as a linear program for which efficient solution methods already exist This leads to comparable results as using the L0 norm often yielding results 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 Baseline CHALLENGE CS replaces conventional sampling and reconstruction linear measurement scheme However will work ONLY IF SOURCE IS SPARSE Challenge to predict which sources are sparse in a particular domain Applying CS whole image ineffective Hence split image small non overlapping blocks of equal size apply CS on blocks found to be sparse APPLICATION Analog to Digital Conversion a fundamental aspect of Wireless Communications Eg CDMA voice msg 4096 hertz standard freq spreads over radio spectrum span thousands of hertz Here signal still sparse so detector recover signal more rapidly then Shannon s theorem Other Applications Data Acquisition Data Compression Image and Video Compression PROGRESS CHART February 28 2010 Research Reading on compressive sensing and information gathering March 20 2010 complete research reading and jpeg simulation part April 10 2010 complete compressive sensing coding April 20 2010 Final touch and documentation report References 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 12071223 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 compressive sampling IEEE Signal Processing Magazine 25 2 pp 14 20 March 2008 Emmanuel Cand s and Justin Romberg Sparsity and incoherence in compressive sampling Inverse Problems 23 3 pp 969 985 2007 Albert Cohen Wolfgang Dahmen and Ronald DeVore Compressed sensing and best k term approximation Preprint 2006 Formerly titled Remarks on compressed sensing www jpeg org http faculty ksu edu sa hedjar Documents MATLAB Educational Sites htm http dsp rice edu cs Compressive Sensing Resources END THANK YOU
View Full Document
Unlocking...