《压缩感知理论及OMP算法.ppt》由会员分享，可在线阅读，更多相关《压缩感知理论及OMP算法.ppt（21页珍藏版）》请在三一办公上搜索。
1、2011-01-25,The Compressive Sensing Theory And Practice of OMP Algorithm,An Overview of Compressive Sensing,For 1-D signal XRN1,mostly，the information is redundant.。We can compress it by orthogonal transformation.,coding：make orthogonal matrix,transformation y=x,remain the most important K components
2、 of y and the corresponding positions.decoding：put K components back to the corresponding positions,let other positions be zero,make H，inverse transformation x*=Hy*.,Coding,Sampling,Transformation,Signal x,y,Decoding,Received data y,Inverse transformation,Reconstructed signal x*,An Overview of Compr
3、essive Sensing,But there are some flaws of this method:1)Considering the Shannon sampling theorem，the sampling interval will be very narrow to gain better signal resolution，which will make the original signal very long,so the processing of transformation costs lots of time.2)The positions of K compo
4、nents required to remain vary while the signal changes.Therefore,this strategy is self-adaptive,and we need to allocate more space to store these positions.3)Poor anti-interference.Once one of the K components lost in transmission,the output will be changed greatly.,An Overview of Compressive Sensin
5、g,In 2004,Donoho and Candes put forward the theory of compressive sensing.This theory indicates that when the signal is sparse or compressible,the signal can be reconstructed accurately or approximately by gathering very few projective values of the signal.,The measured value is not the signal itsel
6、f,but the projective value from higher dimension to lower dimension.,Coding,Sparse signal x,Measurement,coding,y,Decoding,Received signal y,Decoding,reconstruction,Constructed signal x*,An Overview of Compressive Sensing,The advantages of compressive sensing:1)Non-adaptive,break through the limitati
7、on of Shannon sampling theorem.2)Strong Anti-interference ability,every component of the measurement is important,or unimportant.It can still be reconstructed while some components are lost.The application prospect of compressive sensing is broad:digital camera and audio acquisition device with low
8、cost;astronomy(stars are sparse);network;military.,An Overview of Compressive Sensing,Suppose x(n)is a digital signal,if its a K-sparse(has K non-zero values)or compressible signal,then we can estimate it with few coefficients by linear transformation.By compressive sensing we get the signal y(m)(mK
9、log(n)and has restricted isometry property(RIP),x(n)can be rebuilt.,An Overview of Compressive Sensing,The definition of norm:For a vector x,if there is a corresponded real function|x|,which fits such conditions:1)|x|0,only if x=0,|x|=0;2)for any number a,|ax|=|a|x|;3)for any vector x and y,|x+y|x|+
10、|y|;Then we call|x|the norm of x.RIP:for K(0,1)(1-K)|x|22|x|22(1+K)|x|22,An Overview of Compressive Sensing,But few of natural signal is sparse.According to compressive sensing theory,signal x can be sparse by some reversible transformation,that is x=s,so we havey=x=sBaraniuk indicates that the equi
11、valent condition of RIP is that the measurement matrix and the sparse base is irrelevant.Its confirmed that when is Guass random matrix,the condition is well fitted.,OMP Algorithm,In some circumstance,we can replace l0 norm with l1 norm,that is x*=min|x|1 s.t.y=xThe problem above can be solved by gr
12、eed iterative algorithm,one of the most commonly used algorithm is the orthogonal matching pursuit(OMP)method.The main idea of the OMP algorithm:choose the column of by greed iterative method,which makes the chosen column and the present redundant vector related to the greatest extent,we subtract th
13、e related part from measurement vector,repeat the procedure above until the number of iterations up to K.,OMP Algorithm,Input:sensing matrix,sampling vector y,sparse degree K;Output:the K-sparse approximation x*of x;Initialization:the residual r0=y,index set 0=,t=1;,OMP Algorithm,Execute steps 1 to
14、5 circularly:Step 1:find the maximum value of the inner product of residual r and the column of sensing matrix j,the corresponding foot mark is;Step 2:renew the index set t=t-1,the sensing matrix t=t-1,;Step 3:solve x*t=min|y-tx*|2 by least-square method;Step 4:renew the residual rt=y-tx*t,t=t+1;Ste
15、p 5:if tK,stop the iteration,else do step 1.,Simulation Results of OMP,Write programs of OMP in matlabFor 1-D signal,x=0.3sin(250t)+0.6sin(2100t),Simulation Results of OMP,For images which are 2-D signals,we first execute discreet wavelet transformation,changing image signal into the sparse coeffici
16、ents of corresponding basis(here we use Haar basis),for each column of the coefficients matrix,we execute OMP method.Then we execute wavlet inverse transformation on the OMP results,and the reconstructed image has been gained.,Simulation Results of OMP,There are two images adopted in the simulation,
17、one is a remote sensing image,and the other is lena.The size of images is both 512512 pixels.,Simulation Results of OMP,For the remote sensing image,here are images reconstructed at different sampling rate.,Simulation Results of OMP,The PSNR of each image at different sampling rate,Simulation Result
18、s of OMP,For the lena image,Simulation Results of OMP,The PSNR of each image at different sampling rate,Simulation Results of OMP,In order to decrease the running time,we try to divide images into small blocks,here is the graph of running time and numbers of blocks.For the remote sensing image,Simulation Results of OMP,For the lena image,Thank you,
