omp 算法图像处理_omp算法图像处理 - CSDN
  • 压缩感知重构算法之OMP算法python实现 压缩感知重构算法之CoSaMP算法python实现 压缩感知重构算法之SP算法python实现 压缩感知重构算法之IHT算法python实现 压缩感知重构算法之OLS算法python实现 压缩感知重构...

    压缩感知重构算法之OMP算法python实现
    压缩感知重构算法之CoSaMP算法python实现
    压缩感知重构算法之SP算法python实现
    压缩感知重构算法之IHT算法python实现
    压缩感知重构算法之OLS算法python实现
    压缩感知重构算法之IRLS算法python实现

    本文主要简单介绍了利用python代码实现压缩感知的过程。

    压缩感知简介

    【具体可以参考这篇文章
    假设一维信号x长度为N,稀疏度为K。Φ 为大小M×N矩阵(M<<N)y=Φ×x为长度M的一维测量值。压缩感知问题就是已知测量值y和测量矩阵Φ的基础上,求解欠定方程组y=Φ×x得到原信号x。Φ的每一行可以看作是一个传感器(Sensor),它与信号相乘,采样了信号的一部分信息。而这一部分信息足以代表原信号,并能找到一个算法来高概率恢复原信号。 一般的自然信号x本身并不是稀疏的,需要在某种稀疏基上进行稀疏表示x=ψs,ψ为稀疏基矩阵,S为稀疏系数。所以整个压缩感知过程可以描述为

    y=Φx=ΦΨs=Θs

    重建算法:OMP算法简析

    OMP算法
    输 入:测量值y、传感矩阵Phi=Φψ、稀疏度K
    初始化:初始残差 r0=y,迭代次数t=1,索引值集合index;
    步 骤:
    1、找到残差r和传感矩阵的列积中最大值对应下标,也就是找到二者内积绝对值最大的一个元素对应的下标,保存到index当中
    2、利用index从传感矩阵中找到,新的索引集Phit
    3、利用最小二乘法处理新的索引集和y得到新的近似值θ=argmin||yPhitθ||2
    4、计算新的残差rt=yPhitθ,t=t+1
    5、残差是否小于设定值,小于的话 退出循环,不小于的话再判断t>K是否成立,满足即停止迭代,否则重新回到步骤1,继续执行该算法。
    输 出:θ的K-稀疏近似值


    实验

    要利用python实现,电脑必须安装以下程序

    • python (本文用的python版本为3.5.1)
    • numpy python包(本文用的版本为1.10.4)
    • scipy python包(本文用的版本为0.17.0)
    • pillow python包(本文用的版本为3.1.1)

    python代码

    #coding:utf-8
    #%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    # DCT基作为稀疏基,重建算法为OMP算法 ,图像按列进行处理
    # 参考文献: 任晓馨. 压缩感知贪婪匹配追踪类重建算法研究[D]. 
    #北京交通大学, 2012.
    #
    #%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    # 导入所需的第三方库文件
    import  numpy as np
    import math
    from PIL import Image
    
    #读取图像,并变成numpy类型的 array
    im = np.array(Image.open('lena.bmp')) #图片大小256*256
    
    #生成高斯随机测量矩阵
    sampleRate=0.7  #采样率
    Phi=np.random.randn(256*sampleRate,256)
    
    #生成稀疏基DCT矩阵
    mat_dct_1d=np.zeros((256,256))
    v=range(256)
    for k in range(0,256):  
        dct_1d=np.cos(np.dot(v,k*math.pi/256))
        if k>0:
            dct_1d=dct_1d-np.mean(dct_1d)
        mat_dct_1d[:,k]=dct_1d/np.linalg.norm(dct_1d)
    
    #随机测量
    img_cs_1d=np.dot(Phi,im)
    
    #OMP算法函数
    def cs_omp(y,D):    
        L=math.floor(3*(y.shape[0])/4)
        residual=y  #初始化残差
        index=np.zeros((L),dtype=int)
        for i in range(L):
            index[i]= -1
        result=np.zeros((256))
        for j in range(L):  #迭代次数
            product=np.fabs(np.dot(D.T,residual))
            pos=np.argmax(product)  #最大投影系数对应的位置        
            index[j]=pos
            my=np.linalg.pinv(D[:,index>=0]) #最小二乘,看参考文献1           
            a=np.dot(my,y) #最小二乘,看参考文献1     
            residual=y-np.dot(D[:,index>=0],a)
        result[index>=0]=a
        return  result
    
    #重建
    sparse_rec_1d=np.zeros((256,256))   # 初始化稀疏系数矩阵    
    Theta_1d=np.dot(Phi,mat_dct_1d)   #测量矩阵乘上基矩阵
    for i in range(256):
        print('正在重建第',i,'列。')
        column_rec=cs_omp(img_cs_1d[:,i],Theta_1d) #利用OMP算法计算稀疏系数
        sparse_rec_1d[:,i]=column_rec;        
    img_rec=np.dot(mat_dct_1d,sparse_rec_1d)          #稀疏系数乘上基矩阵
    
    #显示重建后的图片
    image2=Image.fromarray(img_rec)
    image2.show()

    matlab代码

    %这个代码是网上某位大哥写的,在此谢过了~
    function Demo_CS_OMP()
    %------------ read in the image --------------
    img=imread('lena.bmp');     % testing image
    img=double(img);
    [height,width]=size(img);
    %------------ form the measurement matrix and base matrix -------
    Phi=randn(floor(0.7*height),width);  % only keep one third of the original data  
    Phi = Phi./repmat(sqrt(sum(Phi.^2,1)),[floor(0.7*height),1]); % normalize each column
    
    mat_dct_1d=zeros(256,256);  % building the DCT basis (corresponding to each column)
    for k=0:1:255 
        dct_1d=cos([0:1:255]'*k*pi/256);
        if k>0
            dct_1d=dct_1d-mean(dct_1d); 
        end;
        mat_dct_1d(:,k+1)=dct_1d/norm(dct_1d);
    end
    
    %--------- projection ---------
    img_cs_1d=Phi*img;  
    
    %-------- recover using omp ------------
    sparse_rec_1d=zeros(height,width);  
    Theta_1d=Phi*mat_dct_1d;%测量矩阵乘上基矩阵
    for i=1:width
        column_rec=cs_omp(img_cs_1d(:,i),Theta_1d,height);
        sparse_rec_1d(:,i)=column_rec'; %  稀疏系数
    end
    img_rec_1d=mat_dct_1d*sparse_rec_1d;  %稀疏系数乘上基矩阵
    
    
    %------------ show the results --------------------
    figure(1)
    subplot(2,2,1),imshow(uint8(img)),title('original image')
    subplot(2,2,2),imagesc(Phi),title('measurement mat')
    subplot(2,2,3),imagesc(mat_dct_1d),title('1d dct mat')
    psnr = 20*log10(255/sqrt(mean((img(:)-img_rec_1d(:)).^2)));
    subplot(2,2,4),imshow(uint8(img_rec_1d));
    title(strcat('PSNR=',num2str(psnr),'dB'));
    
    %*******************************************************%
    function hat_x=cs_omp(y,T_Mat,m)
    % y=T_Mat*x, T_Mat is n-by-m
    % y - measurements
    % T_Mat - combination of random matrix and sparse representation basis
    % m - size of the original signal
    % the sparsity is length(y)/4
    
    n=length(y);
    s=floor(3*n/4); %  测量值维数
    hat_x=zeros(1,m); %  待重构的谱域(变换域)向量                     
    Aug_t=[];        %  增量矩阵(初始值为空矩阵)
    r_n=y;  %  残差值 
    
    for times=1:s; %  迭代次数(稀疏度是测量的1/4)
    
        product=abs(T_Mat'*r_n);    
        [val,pos]=max(product);   %最大投影系数对应的位置
        Aug_t=[Aug_t,T_Mat(:,pos)];   %矩阵扩充
        T_Mat(:,pos)=zeros(n,1); %选中的列置零
        aug_x=(Aug_t'*Aug_t)^(-1)*Aug_t'*y;  % 最小二乘,看参考文献1
        r_n=y-Aug_t*aug_x;   %残差
        pos_array(times)=pos;   %纪录最大投影系数的位置
    
    end
    hat_x(pos_array)=aug_x;  %  重构的向量 
    
    
    

    参考文献

    1、最小二乘法介绍 (wiki链接
    2、任晓馨. 压缩感知贪婪匹配追踪类重建算法研究[D]. 北京交通大学, 2012.(OMP算法介绍)

    欢迎python爱好者加入:学习交流群 667279387

    展开全文
  • # DCT基作为稀疏基,重建算法为OMP算法图像按列进行处理 # 导入所需的第三方库文件 import numpy as np import math from PIL import Image #读取图像,并变成numpy类型的 array im = np.array(Image.open('/...
    #coding:utf-8
    # DCT基作为稀疏基,重建算法为OMP算法 ,图像按列进行处理
    # 导入所需的第三方库文件
    import  numpy as np
    import math
    from PIL import Image
    
    #读取图像,并变成numpy类型的 array
    im = np.array(Image.open('/Users/sanfordzhu/Desktop/lena.bmp')) #图片大小256*256
    
    #生成高斯随机测量矩阵
    sampleRate=0.5  #采样率
    Phi=np.random.randn(int(256*sampleRate),256)
    
    #生成稀疏基DCT矩阵
    mat_dct_1d=np.zeros((256,256))
    v=range(256)
    for k in range(0,256):
        dct_1d=np.cos(np.dot(v,k*math.pi/256))
        if k>0:
            dct_1d=dct_1d-np.mean(dct_1d)
        mat_dct_1d[:,k]=dct_1d/np.linalg.norm(dct_1d)
    
    #随机测量
    img_cs_1d=np.dot(Phi,im)
    
    #OMP算法函数
    def cs_omp(y,D):#传入参数为y和传感矩阵
        L=math.floor(y.shape[0]/4)
        residual=y  #初始化残差
        index=np.zeros((L),dtype=int)
        for i in range(L):
            index[i]= -1
        result=np.zeros((256))
        for j in range(L):  #迭代次数
            product=np.fabs(np.dot(D.T,residual))
            pos=np.argmax(product)  #最大投影系数对应的位置
            index[j]=pos
            tmp=[]
            for tt in range(len(index)):
                if (index[tt]>0)or(index[tt]==0):
                    tmp.append(tt)
            tmp1=D[:,tmp]
            my = np.linalg.pinv(D[:,tmp])  # 最小二乘
            a=np.dot(my,y) #最小二乘
            residual=y-np.dot(D[:,tmp],a)
        result[tmp]=a
        return  result
    
    #重建
    sparse_rec_1d=np.zeros((256,256))   # 初始化稀疏系数矩阵
    Theta_1d=np.dot(Phi,mat_dct_1d)   #测量矩阵乘上基矩阵
    for i in range(256):
        print('正在重建第',i,'列。')
        column_rec=cs_omp(img_cs_1d[:,i],Theta_1d) #利用OMP算法计算稀疏系数
        sparse_rec_1d[:,i]=column_rec;
    img_rec=np.dot(mat_dct_1d,sparse_rec_1d)          #稀疏系数乘上基矩阵
    
    #显示重建后的图片
    image2=Image.fromarray(img_rec)
    image2.show()

     

    展开全文
  • 浅谈压缩感知(二十):MP算法、OMP算法及其在人脸识别的应用 主要内容: 1、MP算法 2、OMP算法 3、OMP算法的matlab实现 4、OMP在压缩感知和人脸识别的应用   一、MP(Matching Pursuits)与OMP(Orthogonal ...

    浅谈压缩感知(二十):MP算法、OMP算法及其在人脸识别的应用

    主要内容:

    1、MP算法

    2、OMP算法

    3、OMP算法的matlab实现

    4、OMP在压缩感知和人脸识别的应用

     

    一、MP(Matching Pursuits)与OMP(Orthogonal Matching Pursuit)算法

      内容:稀疏信号的表示(字典、稀疏系数)、MP算法、MP算法的缺点、OMP、OMP的实现

      参考文章:http://blog.csdn.net/scucj/article/details/7467955

    二、OMP的matlab实现

    %A-稀疏系数矩阵
    %D-字典/测量矩阵(已知)
    %X-测量值矩阵(已知)
    %K-稀疏度
    function A=OMP(D,F,X,L)
    X=double(X);
    [n,P]=size(X);
    [n,K]=size(D);
    %按列操作,分别求出每一列对应的最相关的基
    for k=1:P 
    %a:每一列对应的相关基的系数
    a=[];
    %取二维信号的每一列信号
    x=X(:,k);
    %初始残差
    residual=x; 
    %indx:索引集,L:测量次数
    indx=zeros(L,1); 
    for j=1:L
    %D转置与残差residual相乘,得到residual与每一列的内积值
    residual=double(residual);
    D=double(D);
    proj=D'*residual; 
    %找内积值最大值的位置,即最相关基的position
    pos=find(abs(proj)==max(abs(proj)));
    %若最大值不止一个,取第一个
    pos=pos(1); 
    %位置存入索引集的第j值
    indx(j)=pos; 
    %indx(1:j)表示第一列前j个元素
    %pinv:Pseudoinverse伪逆矩阵,一般用于处理长方形矩阵的求逆
    %得到其相关基的对应系数,AD=X,A=inv(D)*X
    %一般应该通过最小二乘来求
    a=pinv(D(:,indx(1:j)))*x; 
    %继续求残差
    residual=x-D(:,indx(1:j))*a; 
    end
    %通过上面的循环,得到第k列的相关基对应的索引位置
    temp=zeros(K,1);
    temp(indx)=a; 
    %只显示非零值及其位置
    %最终求得整个A,代入AD=X,即可求解
    A(:,k)=temp; 
    end
    R=A'*D';
    R=uint8(R);
    imshow(R);

    三、OMP在压缩感知和人脸识别的应用

    参考以下文章:

    http://wenku.baidu.com/view/4e67448302d276a200292e53.html

    http://wenku.baidu.com/link?url=IVn0mBapYDtCfj_mVma6AU8C9ClbGYU4Y5u4Kq0-F-8vhMN_73fcjLrTwzidA1KtQkqj6FvPS6-YkALppqr_Z_8TDlUV2wKEIsdqPs-my1m

    http://blog.csdn.net/celerychen2009/article/details/9257275

    展开全文
  • 透过这10种算法,应该可以找出写论文的一点儿规律吧:我们基于OMP算法,有对原子正则化的ROMP、有使用回溯思想的CoSaMP和SP、有采用门限选择选子的StOMP及弱选择标准的SWOMP、还有稀疏度自适应的SAMP,以及我们国内...

    题目:正交匹配追踪(OMP)其它改进算法

    下面介绍10篇文献中的OMP改进算法,首先给出这10篇参考文献:

    [1]杨成,冯巍,冯辉,杨涛,胡波.一种压缩采样中的稀疏度自适应子空间追踪算法[J]. 电子学报,2010,38(8):1914-1917.

    [2]高睿,赵瑞珍,胡绍海.基于压缩感知的变步长自适应匹配追踪重建算法[J]. 光学学报,2010,30(6):1639-1644.

    [3]刘亚新,赵瑞珍,胡绍海,姜春晖.用于压缩感知信号重建的正则化自适应匹配追踪算法[J]. 电子与信息学报,2012,32(11):2716-2717.

    [4]刘哲,张鹤妮,张永亮,郝珉慧.基于弱选择正则化正交匹配追踪的图像重构算法[J]. 光子学报,2012,41(10):1217-1221.

    [5]吴迪,王奎民,赵玉新,王巍,陈立娟.分段正则化正交匹配追踪算法[J]. 光学精密工程,2014,22(5):1395-1402.

    [6]徐泽芳,刘顺兰.一种自适应正则化子空间追踪算法[J]. 计算机工程与应用,2015,51(3):208-211.

    [7]王芳星,刘顺兰.一种改进的正则化自适应匹配追踪算法[J]. 机州电子科技大学学报(自然科学版),2015,35(1):79-83.

    [8]GuilingSUN, Yuhan ZHOU, Zhihong WANG, Wei DANG, Zhouzhou LI. Sparsity AdaptiveCompressive Sampling Matching Pursuit Algorithm Based Compressive Sensing[J].Journal of Computational Systems8: 7(2012): 2883-2890.

    [9]XueBi, Xiangdong Chen, Yu Zhang. Variable Step size Stagewise Adaptive MatchingPursuit Algorithm for Image Compressed Sensing[C]. 2013 IEEE InternationalConference on Signal Processing, Communication and Computing(ICSPCC)[A],2013:1-4.

    [10]HuangWeiqiang, Zhao Jianlin, Lv Zhiqiang, Ding Xuejie. Sparsity and Step-sizeAdaptive Regularized Matching Pursuit Algorithm for Compressed Sensing[C]. 2014IEEE 7th Joint International Information Technology and ArtificialIntelligence Conference(ITAIC)[A], 2014: 536-540.

    ===========================分割线==============================

    [1]杨成,冯巍,冯辉,杨涛,胡波.一种压缩采样中的稀疏度自适应子空间追踪算法[J]. 电子学报,2010,38(8):1914-1917.

            正如文中所说,稀疏度自适应子空间追踪(Sparsity Adaptive Subspace Pursuit, SASP) “使用一种新的稀疏度估计方法得到稀疏度的初始估计值,然后通过迭代进行估计的更新。在每次迭代中采用弱匹配原则选取新原子,再通过子空间追踪改善结果并重建信号”。有关稀疏度估计在文中2.1节进行了数学证明,这个给作者点赞。在估计出信号的稀疏度之后,以SP为主体,然后在第(11)步中又融入了SAMP的思想,但不同于SAMP的是步长并不是直接选定的,而是在第(12)中通过弱选择(类似于SWOMP)的方法增加的。

    [2]高睿,赵瑞珍,胡绍海.基于压缩感知的变步长自适应匹配追踪重建算法[J]. 光学学报,2010,30(6):1639-1644.

            其中停止迭代条件1和停止迭代条件2分别如下:

            有关停止迭代条件中两个阈值的取值,在文中有如下交代:

            正如文中所说:结合 SAMP方法自适应的思想和StOMP方法分阶段的思想,针对SAMP固定步长所带来的精度不够以及过度估计问题,提出了一种新的变步长自适应匹配追踪(Variable step size Adaptive Matching Pursuit,VssAMP)算法。

            VssAMP相比于SAMP的不同之处在于:VssAMP算法中将SAMP的停止迭代条件分为了两个阶段,即依次判别停止迭代条件1和停止迭代条件2是否成立;如果同时满足停止迭代条件1和停止迭代条件2即停止迭代;如果停止迭代条件1不满足则剩余步骤与SAMP相同(即文中所说的“通过大步长快速接近了重建目标信号”阶段);如果停止迭代条件1满足而停止迭代条件2不满足则将步长减小一半后继续迭代(即文中所说的“通过小步长逐步逼近”阶段)。

            关于停止迭代条件2的“或”后面的条件我有一点疑问:随着迭代的进行,稀疏度越来接近信号的真实稀疏度,信号x的估计不应该本就是越迭代越大么,k-1次迭代时的估计原本不就应该小于第k次迭代时的估计么?难道进入“通过小步长逐步逼近”阶段后信号x的估计会越迭代来越小直到某次迭代变大则意味着可以停止迭代了?

            学习研究该算法还可以拜读作者的硕士学位论文“高睿.基于压缩传感的匹配追踪重建算法研究[D]. 北京交通大学硕士学位论文,2009.”。

    [3]刘亚新,赵瑞珍,胡绍海,姜春晖.用于压缩感知信号重建的正则化自适应匹配追踪算法[J]. 电子与信息学报,2012,32(11):2716-2717.

            其中ε1与ε2分别为控制迭代次数与阶段转换的阈值,为达到较好的重建精度以及严格控制阶段转换的目的,根据所处理信号的具体信息适当地选择阈值的大小(但文中仿真部分并未给这两个值的取值方法,个人并未对此进行仿真,感觉应该是取类似10-6的比较小的值),式(3)(4)(5)(6)如下:



            正如文中所说,正则化自适应匹配追踪(Regularized Adaptive Matching Pursuit,RAMP)算法是一种结合了ROMP算法正则化思想以及SAMP算法自适应思想的新的重建算法,保证了全局优化的同时提高了算法的运算速度。它与SAMP的不同之处在于:SAMP直接从u中选择了size个最大值,而RAMP是先选择size个最大值,再按正则化标准筛选一遍;而stage转换标准中SAMP是rnewr,这里是rnewr差的2范数小于ε2,文中并未提及如何ε2取值,但如前述应该是一个较小的值,SAMP中其实大部分情况应该取rnew=r(即不会再有新的列被选中,参见SAMP此处的相关分析),所以二者基本是一致的。

    [4]刘哲,张鹤妮,张永亮,郝珉慧.基于弱选择正则化正交匹配追踪的图像重构算法[J]. 光子学报,2012,41(10):1217-1221.


            算法中的式(3)为:

            弱选择正则化正交匹配追踪是一种结合了文中的参考文献[10]弱选择策略(即SWOMP的弱选择)及ROMP的改进算法,与ROMP的区别主要在于候选集J,ROMP是取迭代余量和观测矩阵的内积值中的最大的K个,而此处是按式(3)选择原子,因此本算法不需要已知信号的稀疏度K,其余部分基本一样。

    [5]吴迪,王奎民,赵玉新,王巍,陈立娟.分段正则化正交匹配追踪算法[J]. 光学精密工程,2014,22(5):1395-1402.

            正如文中所说“结合以上两种算法(即ROMP与StOMP),本文提出分段正则化正交匹配追踪算法,以保证贪婪迭代类算法在信号稀疏度未知的情况下重构信号的可靠性和有效性”,本算法的另一个创新点在于“加入了阈值的可靠性验证阶段。具体为:根据当前残差量设定阈值,选取相关系数大于阈值的原子,若满足条件的原子个数大于零,表明所设阈值合理,对选出的原子进行正则化;若依据以上条件无法选出原子,则表明阈值设定的不合理,此时自动将最大相关系数对应的原子选出,由于只有一个原子,所以无需正则化,直接将此原子加入支撑集。阈值的可靠性验证保证了支撑集持续更新,使算法能可靠、有效地完成信号重构。”本算法相比于StOMP的区别在于:StOMP根据阈值选出候选集后直接使用,而本算法根据阈值选择后还要进行正则化;StOMP若无新原子被选中则跳出循环,而本算法加入了阈值的可靠性验证阶段。

    [6]徐泽芳,刘顺兰.一种自适应正则化子空间追踪算法[J]. 计算机工程与应用,2015,51(3):208-211.


            算法中的式(5)、式(6)及rnew分别为:


            正如文中所说,自适应正则化子空间追踪(Adaptive Regularized Subspace PursuitARSP)算法是在“ROMP,SAMP和SP算法的基础上,将SAMP算法的自适应思想、ROMP 算法的正则化思想和SP 算法相结合”提出的一种新的改进算法。算法第(6)步前半部分及以前与SP算法类似,第(6)步后半部分融入了SAMP,然后在选择原子时先得到候选集再进行正则化。

    [7]王芳星,刘顺兰.一种改进的正则化自适应匹配追踪算法[J]. 机州电子科技大学学报(自然科学版),2015,35(1):79-83.


            算法中的式(3)\式(4)、式(5)分别为:


            正如文中所说,改进的正则化自适应匹配追踪 (ModifiedRegularization Adaptive Matching Pursuit, MRAMP)算法是“将信号的稀疏度估计、SAMP算法的自适应、SP算法的回退筛选和ROMP算法的正则原子选择相结合”提出的一种新的改进算法。算法首先通过第(2)(3)步,估计出信号稀疏度初始估计值 K0,并将其作为初始支撑集长度,然后以SP算法为主体,并在最后的(10)(11)步融入SAMP,在原子选择时加入正则化过程。第(11)步与SAMP不同的是这里的步长一直在减半。信号的稀疏度估计来源为这里我所介绍的十种算法中的第1种“[1]杨成,冯巍,冯辉,杨涛,胡波. 一种压缩采样中的稀疏度自适应子空间追踪算法[J].电子学报,2010,38(8):1914-1917.”。

            我对算法中的第(3)步有一点疑问:通过第(2)(3)步,估计出信号稀疏度初始估计值 K0,但在第(3)步中有一句“step1=step1”,这句话有意义么?step1在第(1)步中初始化为step后,在第(2)步没有任何更新,那么第(3)步的“step1=step1”意义何在?

    [8]GuilingSUN, Yuhan ZHOU, Zhihong WANG, Wei DANG, Zhouzhou LI. Sparsity AdaptiveCompressive Sampling Matching Pursuit Algorithm Based Compressive Sensing[J].Journal of Computational Systems8: 7(2012): 2883-2890.


            正如文中所说,sparsity adaptive compressive sampling matching pursuit(CSAMP)是在“takingadvantages of SAMP sparsity adaptive, introducing backtracking method to lowercomplexity and adopting compressive sampling to improve noise robustness”的一种新的改进算法,它具有“fast, high precision, high stability and sparsity adaptive”的优点。算法主体上与SAMP类似,不同的是第(2)步CSAMP取2L个,而SAMP取L个,文中对此做法给出理由:“Assumethe moment the size of SS isL,adopt compressive sampling which ensures Candidate Sets has less than 3Latoms, and SS has 2L atoms in each iteration, so reject lessthan L atoms to make optimizationimprovement which realizes high precision reconstruction under the signal withnoise situation.”,也就是说采用了CoSaMP的思想(CoSaMP选2K个,而SP选K个);然后就是第(5)步的停止迭代条件,一般来说我们都是以残差r的2范数为标准,这里用的是相邻两次迭代最小二乘解的差的2范数为标准,文中对此改进给出了依据:


            还有一点要说明的是,第(1)步初始化时Λ=Φ,Ω=Φ,这里的Φ代表空集的意思,与文中前面的Φ并不是一个意思。

    [9]Xue Bi, Xiangdong Chen, Yu Zhang. Variable Step size Stagewise Adaptive MatchingPursuit Algorithm for Image Compressed Sensing[C]. 2013 IEEE International Conference on Signal Processing, Communication and Computing(ICSPCC)[A],2013:1-4.

            Variable Step size StagewiseAdaptive Matching Pursuit(VSStAMP)主体上与SAMP类似,变步长的实现在于第(2)步,在第(2)步判断候选集中包含原子的个数,并以u*M为界限,当原子个数小于界限时采用大步长2*s,而当原子个数小于界限时采用小步长s。因此u的取值比较关键,文中仿真部分u取为1/8,而文中对此也有分析:


    [10]Huang Weiqiang, Zhao Jianlin, Lv Zhiqiang, Ding Xuejie. Sparsity and Step-sizeAdaptive Regularized Matching Pursuit Algorithm for Compressed Sensing[C]. 2014IEEE 7th Joint International Information Technology and ArtificialIntelligence Conference(ITAIC)[A], 2014: 536-540.



            文中对Sparsity and Step-size Adaptive Regularized Matching Pursuit (SSARMP)算法的提出背景有如下阐述:

            算法首先采用文中第(III)(A)部分所述的Numerical Sparsity Estimation(NSE)方法估计信号的稀疏度,然后将NSE估计出的结果应用于SAMP,为了提高恢复概率,又加入了变步长和正则化。从程序流程中可以看出,程序主体上类似SAMP,初始化选择原子的个数为采用NSE方法估计出来的稀疏度,即Initialization阶段的I=K0,不同于SAMP的是选择完后进行了正则化,然后在后面条件判断时又不同于SAMP,分为变步长条件和停止迭代条件,有关这两个条件在文中做了如下阐述:


            这里步长的变化采用的方法是在满足变步长条件时给步长s乘以一个大于0小于1的数α,有关α的取值在文中最后(IV)(E)部分专门对此做了仿真,仿真表明α趋于0时重构概率会变大但迭代次数也会变大,当α趋于1时重构概率会变小但同时迭代次也会减少。

    结语:

            本想把查到的有关OMP的改近算法都详细的仿真一遍,但发现实在是太多了,没有时间一个一个的去仿真。所以这里介绍了自己查到的国内有关OMP的10种改近算法。透过这10种算法,应该可以找出写论文的一点儿规律吧:我们基于OMP算法,有对原子正则化的ROMP、有使用回溯思想的CoSaMP和SP、有采用门限选择选子的StOMP及弱选择标准的SWOMP、还有稀疏度自适应的SAMP,以及我们国内改近算法中引入的稀疏度估计方法、变步长判断标准等等,所以尽情的把这些方法进行排列组合再加入自己的一些新想法得出新的改进算法吧……

            还有一篇改进算法后查到的,所以这里没写,大家可以自己看看:An improved sparsity adaptive matching pursuit algorithm for compressive sensing based on regularized backtracking 。

            另外,如果哪位童鞋有兴趣可以把这些改近算法仿真对比一下……

    展开全文
  • 最近发现网上压缩感知中用OMP算法重构图像的代码很多,但很少有应用OMP算法来重构整个视频序列的,代码是自己写的,希望对初入门压缩感知的有帮助。由于重构时间的原因,程序中只对前8帧进行了重构。
  • 压缩感知中OMP算法的C/C++实现 背景介绍 算法实现部分 总结 阅读之前注意: 本文阅读建议用时:30min 本文阅读结构如下表: 项目 下属项目 测试用例数量 背景介绍 ...
  • OMP算法

    2014-03-30 20:47:20
    function [A]=OMP(D,X,L);  %============================================= % Sparse coding of a group of signals based on a given  % dictionary and specified number of atoms to use.  % input ...
  • OMP算法介绍 OMP的MATLAB实现 OMP中的数学知识 一、OMP算法介绍 来源:http://blog.csdn.net/scucj/article/details/7467955 1、信号的稀疏表示(sparse representation of signals) 给定一个过完备字典
  • MP算法原理: 算法假定输入信号与字典库中的原子在结构上具有一定的相关性,这种相关性通过信号与原子库中原子的内积表示,即内积越大,表示信号与字典库中的这个原子的相关性越大,因此可以使用这个原子来近似...
  • BP,OMP,StOMP对比

    2020-07-30 23:32:45
    三种算法的对同一副图像处理的对比,很直观的可以看出几种算法的处理效果!
  • 一、前言 稀疏表示是自上世纪90年代开始,从人眼的视觉感受野获得启示,逐渐被人们所研究。现在已经发展为一种重要的信息表示方法。所谓稀疏表示是指,一个信号在...在这种情况下,我们常用贪婪算法去获得该模型的次最
  • 即通过求余量r与感知矩阵Φ中原子之间内积的绝对值来选择最佳原子组合,不同的是OMP在分解的每一步中对所选择的全部原子进行正交化处理,这使得在精度要求相同的情况下,OMP算法的收敛速度更快。 OMP算法与MP算法的...
  • 论文原文: % Signal Recovery From Random Measurements Via Orthogonal Matching % Pursuit,IEEE TRANSACTIONS ON INFORMATION THEORY, VOL....def cs_omp(y,Phi,N,K): residual=y #初始化残...
  • 正交匹配追踪算法OMP

    2019-09-01 22:34:08
    浅谈压缩感知(九):正交匹配追踪算法OMP </h1> <div class="clear"></div> <div class="postBody"> 主要内容: OMP算法介绍 OMP的MATLAB实现...
  • 主要介绍MP(Matching Pursuits)算法OMP(Orthogonal Matching Pursuit)算法[1],这两个算法虽然在90年代初就提出来了,但作为经典的算法,国内文献(可能有我没有搜索到)都仅描述了算法步骤和简单的应用,并未对其...
  • 压缩感知图像处理

    2020-07-29 14:20:42
    压缩感知图像处理 DCT稀疏 JND测量矩阵 OMP重建算法
  • 前天,列举对单一向量OMP算法的求解,这个向量是离散的。 但是我们知道自然界中的信号是模拟(连续)信号。学过一些信号系统的同学应该知道,自然界的信号(光信号,声信号)是连续的。 比如下图的信号 假设要保存...
1 2 3 4 5 ... 20
收藏数 566
精华内容 226
热门标签
关键字:

omp 算法图像处理