一种基于最小二乘优化的压缩感知图像快速重建方法
一种基于最小二乘优化的压缩感知图像快速重建方法
【技术领域】
[0001] 本发明涉及一种压缩感知图像重建方法，具体地涉及一种面向图像的、基于最小 二乘优化的压缩感知采样快速重建方法。
【背景技术】
[0002] 基于稀疏表示理论和泛函分析-逼近理论的压缩感知（compressed sensing or compressive sampling，CS)是一种新型的采样方法，在对可压缩信号采样时能够突破著名 的Shannon-Nyquist采样定理的限制，以远低于两倍信号最大带宽的采样率对信号采样，从 而减少了采集的数据量。以其用少量采样值表示全长的信号的优点，压缩感知在出现之初 就吸引了信号、通信、电子信息、统计理论、编解码理论和计算机等众多领域的研究热情，被 认为是信息科学近年来最重大的研究成果。压缩感知基本原理如下：
[0003] 假设一维离散信号seRNxl是可压缩的(这是前提条件），压缩感知方法的信号采样 是利用特别设计的观测矩阵〇￡R MXN(这里M<<N)将可压缩信号s从N维投影到Μ维，即：y = Φ8;这里的yeRMxl是信号s的压缩采样，而采样y的长度Μ与信号 S的长度N与之比M:N就是在 压缩感知框架下的采样率，该采样率一定小于1。由于y=?s是欠定方程组，无法直接求解， 压缩感知方法从近似重构的角度来考虑求解问题。
[0004] 考虑信号s可压缩的前提和稀疏表示理论，对于可压缩信号s-定存在某稀疏变换 基Ψ ERNXN，使得s在该变换基上的表示0eRNxl是稀疏的，即：
[0005] (1)8 = ΨΘ，
[0006] 式中Θ的大部分元素为〇或接近于〇;通常Θ中非〇元素的个数Κ(Κ<<Μ<<Ν)被称 为Θ的稀疏度。从而有y = C>s = Φ ΨΘ=ΑΘ;这里的Α= Φ Ψ被称为信息算子或感知矩阵。y = ΑΘ可以通过0-范数优化问题求解
[0007] (2)min | | Θ | | 〇 s · t .y = A90
[0008] 而根据D〇noho、CandgS等人研究提出的压缩感知理论，在感知矩阵A具有有限等距 性质(Restricted Isometry Property，RIP)的条件下，0-范数优化可以转化为1-范数优化 问题：
[0009] (3)min| |θ| |i s.t.y = A0，
[0010] 其中，A具有RIP性质的等价条件是观测矩阵Φ与稀疏变换基ψ不相干，这一点在 设计观测矩阵Φ时已得到保证。
[0011] 由于Θ是稀疏的，通过（2)和（3)式可以得到其精确或近似逼近解古，然后利用（1) 式得到原始信号s的精确或近似逼近解5。常用压缩感知算法主要包括针对(2)式的贪婪算 法和针对(3)式的凸松弛算法。最经典的压缩感知算法就是凸松弛算法中的基追踪(Basis Pursuit,BP)算法，所需的观测值数目少（即采样率低）、计算精度高；匹配追踪(Matching Pursuit，MP)、正交匹配追踪（Orthogonal ΜΡ,ΟΜΡ)及其改进算法都是贪婪算法的代表，收 敛速度快、计算复杂度较低，实际应用较多。
[0012]压缩感知方法的信号重建是近似优化重构，非常适合于处理图像信号，目前其已 在磁共振、X-射线扫描、雷达成像、遥感图像处理、超频谱图像分析等方面有了很多应用，并 已开发出单像素相机。压缩感知算法的提出都是以一维信号为处理对象的，对于二维信号 一般以列或行向量为重建单位分别重建，当每一个列或行信号都被重建后，整个二维信号 也就重建成功了，图像信号的重建通常也是按列处理的。我们把图像信号S记为[ S1，S2，···， Sn]，其中Sl(i = l，2,…，η)为信号的第i列，在处理中每一个81分别进行重构。
[0013]压缩感知方法具有采样数目少的优点，但其应用仍然有很多难题等待解决，较长 的信号重构时间是其中的一个关键。如BP算法的计算复杂度高达0(N3)，收敛速度较快的 0ΜΡ算法的计算复杂度也达到了0(ΝΚ 2)。在配置为Intel(R)Core(TM)2Duo CPU E46000 2.4GHz、3GB内存、Windows 7、Mat 1 ab R2011 b的个人计算机上的重构不同大小信号时的重 构时间如表1和2所示。
[0014]表1 0ΜΡ和BP算法重构一维信号时，信号大小每增加1倍重构时间的变化 [0015]
[0016]表2 0ΜΡ和BP算法重构二维信号时，信号大小每增加1倍重构时间的变化
[0017]
[0018] 压缩感知算法重构信号所需的时间较长，并随信号增大以远大于信号增幅的速率 增长，而且这个速率随信号的增大还在不断增长。对比表1和表2可以发现，二维信号的重构 时间远远大于一维信号，且其增长幅度也较大;如大小为1024 XI的信号重构时间是512 XI 的5.55倍，而大小为1024X1024的信号重构时间是512X512的11.76倍。
[0019]我们在压缩感知算法及其应用的研究中，利用日渐普及的高性能计算设备和云计 算平台加速压缩感知算法，以提高算法的执行速度，验证了压缩感知方法在物联网数据采 集中的应用，实现了压缩感知算法的并行化、多/多核CPU加速、GPU加速和云平台加速等，加 速后的算法执行时间如图1和表3所示。
[0020] 表3 0ΜΡ算法重构信号时，不同数量计算资源的云加速效果(编程语言Python，云 平台）
[0021]
[0022] 从图1和表3中可知，压缩感知算法的并行化及加速虽然能显著减少算法的执行时 间，但不能改变算法随信号增大而以极高的速率增长的趋势。压缩感知算法的重构时间高 速增长，且增长趋势不断扩大，使重构算法的执行时间无法估计，不利于在云平台加速时的 自动资源分配。
【发明内容】
[0023] 针对上述技术问题，本发明目的是:提供一种基于最小二乘优化的压缩感知图像 快速重建方法FBWRFI，它采用最小二乘优化方法实现图像的重建，以保证收敛速度和重构 精度；以每一个原子和二维残差之间的整体相关度测量取代原子与一维残差之间的相关度 测量，以减少迭代次数、降低计算复杂度；引入块压缩感知理论并重新设计快大小和测量矩 阵，以降低优化迭代中的参数规模。该方法能够显著降低从压缩的采样中重建原始图像的 时间，并使图像的重构时间由随信号增大而以极高速率增加变为线性增长，提高了重构时 间的可预估性，有利于使用云资源加速时的资源智能分配。
[0024]本发明的技术方案是：
[0025] -种基于最小二乘优化的压缩感知图像快速重建方法，其特征在于，包括以下步 骤：
[0026] SO 1:把原始图像信号S: N X N基于压缩感知方法的压缩采样Y: Μ X N，根据块测量矩 阵Φ β :Mb X Β划分为"=「W/5下个互不重叠的块Yi:Mb X Β，其中|是基于压缩感知方法进 行压缩采样时的采样率：
[0027] S02:利用WRFI重构每个块St: B X B，压缩采样为Yt: Mb X B，稀疏系数记Θ t: B X B，其 过程如下：
[0028] S02-01:计算块感知矩阵Αβ=ΦβΨβ:ΜβΧΒ中每一个原子€4(丨=1，2，."，8)与当前 二维残差R(k-1):Mb X B的整体相关度A = ??< -屮 >卜其中k表示当前是第k次迭 Μ 代，<^是48的第i列，二维残差R(k-l)的初始值为1并在每次迭代后更新，R(k-lh是R(k-l) 的第j列，Ψb : B X B是稀疏变换基且Ψb和Φ b线性无关；
[0029] S02-02:通过对比Pi(i = 1，2，…，B)，在序号不包含在原子序号集合Λ k-:的原子中 选出与当前残差最大相关原子的序号4 = 11^11=1,2,...^(0〇;其中八1{-1是前面卜1次迭代中选 择的最相关原子的序号组成的集合，Ak表示第k次迭代选出的最相关原子的序号；
[0030] 302-03:把人1{并入集合人1{-1，把原子％并入集合4卜1得到 ：人1{=[人1{-1，人1{]， 為=[為、ι，α%];:其中气是Ab的第4列，Ak-i是前面k_l中得到的最相关原子的集合；
[0031] S02-04:基于Ak和最小二乘优化方法获取本次迭代的近似逼近解Θ tk; Θ tk是第k次 迭代得到的稀疏系数? t的近似逼近；
[0032] S02-05:判断迭代条件:达到设定的重构精度或设定的最大迭代次数K，则结束重 建块St的迭代计算并跳转到S02-07; ?tk是St的稀疏表示系数?*的近似逼近解Θ,;
[0033] S02-06:更新参数R(k)=Y-Ak?tk和k = k+l，跳转至S02-01继续迭代;这里k是新的 迭代次数，R(k)是新的二维残差；
[0034] S〇2_〇7:利用St= ΨΒ Θ t得到St的近似逼近解4;
[0035] S02-08:判断是否每个块St都已经重建：即当t 2 η则跳至S03，否则跳至S02重构下 一个块St+i;
[0036] S03:将所有的重构信号戋拼接得到完整的重构信号|。
[0037] 优选的，在重构过程之前还包括采样过程，采样过程包括以下步骤：
[0038] S11:把原始图像信号S:NXN分割为《 个大小为BXB的块，若原始信号边 缘的分块大小不足B X B，将不足的部分的元素填充为0;
[0039] S12 :对于每一个分块Si :BXB(i = l，2,…，n)，使用相同的稀疏变换基ΨΒ: B X B进 行稀疏变换Si= ΨΒθ?，其中?i:BXΒ是Si的稀疏系数；
[0040] S13:对于每一个分块Si:BXB(i = l，2,…，n)，使用相同的测量矩阵Φβ:ΜβΧΒ进行 u 投影变换Yi = φ BSi，其中Yi: Mb X Β是Si的压缩采样，γ就是采样率或压缩比，而Yi = Φ BSi =ΦΒΨΒΘ i可记为Yi = AB? i，AB就是压缩感知方法的感知因子；
[0041 ] S14:把每一个Yi (i = 1，2，…，η)拼接起来组成Γ X # )X ΛΓ, Y就是原始图像 信号S的压缩采样，^就是采样率或压缩比。 B
[0042] 优选的，所述块测量矩阵Φb的大小为Mb X B，分块大小大于等于256 X 256，在分块 时当原始信号边缘的分块大小不足256X 256,将不足的部分的元素填充为0;当重构完成 后，将填充部分的值去掉。
[0043] 与现有技术相比，本发明的优点是：
[0044] 本发明采用最小二乘优化方法实现图像的重建，以原子和二维残差之间的整体相 关度测量取代原子和一维残差之间的相关度测量，减少了迭代次数、降低计算复杂度，引入 块压缩感知理论降低优化迭代中的参数规模和计算规模，并使重构时间随信号增大呈线性 增长，提高了重构时间的可预估性。
【附图说明】
[0045] 下面结合附图及实施例对本发明作进一步描述：
[0046] 图1为0ΜΡ算法重构信号时，多CPU并行的加速效果图；
[0047] 图2为本发明基于最小二乘优化的压缩感知图像快速重建方法的整体重构设计的 流程图；
[0048]图3为本发明基于最小二乘优化的压缩感知图像快速重建方法的原理图；
[0049] 图4为使用本发明方法重构不同图像的效果图；
[0050] 图5为在不同采样率下重构图像的效果图；
[0051] 图6为重构不同大小图像的效果图。
【具体实施方式】
[0052]为使本发明的目的、技术方案和优点更加清楚明了，下面结合【具体实施方式】并参 照附图，对本发明进一步详细说明。应该理解，这些描述只是示例性的，而并非要限制本发 明的范围。此外，在以下说明中，省略了对公知结构和技术的描述，以避免不必要地混淆本 发明的概念。
[0053] 实施例：
[0054]本发明主要包括两部分:整体重构设计WRFI和基于分块压缩感知的快速重建方法 FBWRFI，它们之间的关系是:WRFI是以原子和二维残差之间的整体相关性测量取代原子和 一维残差之间的相关性测量后，面向图像整体的、较少迭代次数的快速重建方法;FBWRFI是 对需要重建的图像分块后，每一个图像块均采用WRFI方法进行重建，在保证较少迭代次数 的前提下降低迭代中的参数规模和计算量，以获取更快的重建速度和可预估的重构时间。
[0055] WRFI在重构过程中将二维信号作为一个整体来处理，而不是按列分别处理。为了 测量二维信号残差与测量矩阵各列（原子)之间的相关度，就需要定义新的相关度测量参 数，称之为二维信号的整体相关度(》11〇16-(301'代131：；[011)。
[0056] 定义1(整体相关度）.向量aeRmX1和矩阵Φ eRmXn的整体相关度（whole- η correlation)为Ρ = Σ?< ?肩>1，其中Ρ为整体相关度，灼是是矩阵Φ的第i列。 Μ
[0057] 对原始信号S:NXN(为了简单，假设S的行和列相同），设压缩采样Υ:ΜΧΝ，测量矩 阵Φ :ΜΧΝ，稀疏变换基Ψ:ΝΧΝ，记Α=ΦΨ:ΜΧΝ且有S = A?，θ :ΝΧΝ是稀疏的。WRFI的主 要思想是：在每次迭代时（第t次迭代），首先计算感知矩阵A中的每一个原子(A的每一列） ai:MXl(i = l，2，-_，N)与当前二维残差R(t-1):MXN(第t-Ι次迭代时更新的残差，初始值R (〇)=￥)的整体相关度01，并选出最大相关度/11.=〇^\.=1._，..._、,（八），这里最相关原子的序号 是&，最相关原子是心,；然后将和At-i合并为4 这里的At-i是前t-Ι次迭代 选出的最相关原子组成的矩阵；接着基于At和最小二乘优化方法获取本次迭代的近似估 计：
[0058]
[0059] 当近似估计執达到设定的精度或迭代计数器k达到设定的最大迭代次数K时，迭代 结束，本次迭代的近似估计氣就是Θ的重建结果;否则更新残差和增量t，并继续迭代。WRFI 的算法流程如图2所示。
[0060] 在本发明方法中，对信号S: NX N，其稀疏变换基ψ :N XN和测量矩阵Φ :Μ X N是线 性无关，这是前提条件。在S=w Θ和Υ=Φ5=ΦΨ θ =ΑΘ中，Υ:ΜΧΝ、θ :ΝΧΝ、Α=ΦΨ:Μ X Ν;对于 S的每一列 Si :NX1 都有Si=W9i(i = l，2,…N)和}^=Φ8?=ΦΨΘ? = Αθ?(? = 1， 2,…，Ν)，因 Ψ和Φ是线性无关的，根据压缩感知理论所有的Sl(i = l，2，-_，N)都可以被高 概率地重构，从而作为整体的S也就可以被高概率精确重构，也即本方法理论上是可行的。
[0061] WRFI通过将选择原子用于二维信号整体重建降低了原子选择和重构操作中的迭 代次数，但并不能改变重构时间的随信号增大而带来的高增长率。这主要是因为随着信号 规模的增加，算法中使用的稀疏变换基、观测矩阵及其它一些中间参数的规模也随之增大， 从而带来了优化算法中每一次迭代的计算量呈指数级增加。为了降低重构算法所需的存储 和计算的规模，将信号的大小保持在一个相对较小的程度是必须的。在面向图像的二维整 体重构得到WRFI的基础上，引入了块压缩感知(block compressed sensing)，并最终形成 了基于最小二乘优化的快速图像重建压缩感知方法FBWRFI方法。
[0062] FBWRFI首先把原始图像S:NXN被分割成若干个大小为BXB的小块(图像）。基于压 缩感知理论，图像S的稀疏变换就是对每一个块图像Si: B X B使用相同的稀疏变换基ΨΒ: B X Β进行操作Β就是块图像&的稀疏系数;图像S采样就是使用相同的测量 矩阵Φβ:ΜβΧΒ对每一个块图像Si进行投影变换Yi=〇 BSi;若记Αβ=ΦβΨβ:ΜβΧΒ，则Yi = AB Θ i，其中Mb : B可表示采样率/压缩比。因为设计测量矩阵① b:Mb X β时总是Mb< <B，采样率也 就小于1，实现了压缩采样。对于整个信号S来说，稀疏变换基Ψ : N XN和观测矩阵Φ :Μ X N(M =Mb X k，=「嫁/)分别如(5)式所示。
[0063] FBWRFI方法的（整体重构设计WRFI)原理与过程如图3所示。FBWRFI方法中设计的 块测量矩阵Φβ的大小为Mb XB，综合考虑重构时间和重构精度后把分块大小定义为256 X 256,这个分块大小是可以调整的，调整的原则基于实际应用中对重构图像精度的需求，分 块越大则重建图像的精度越高。在分块时，原始信号边缘各个分块大小可能不足B X B，需要 将不足部分的元素值填充为〇;当重构完成后，再将这部分的值去掉即可。
[0064]本发明的具体实现步骤，包括：
[0065] 输入:
[0066] 原始信号S: N X N，压缩采样Y: Μ X N，块测量矩阵Φ b : Mb X 256，块稀疏变换基ΨΒ: B \8，块稀疏度1(;
[0067] 输出:
[0068] 重构信号 [0069] 算法过程:
[0070] (1) FBWRFI 的初始化
[0071] 1)把压缩采样Y根据Φ b分块Yi: Mb X 256 (i = 1，2，…，η)，《 =「嫁/ 5下为块数量；
[0072] 2)t = l，t为块计数器；
[0073] 3)存放重构信号的参数糸
[0074] 4)最大块数η;
[0075] (2)使用WRFI重构每一个块图像5*:256\256(其压缩采样为￥*4 = 1，2，~，11)
[0076] 1)WRFI的初始化
[0077] a)残差;R〇 = Yt
[0078] b)已选出原子序号集合Λβ =0;
[0079] c)已选择的原子组成的矩阵Λ =01
[0080] d)迭代次数计数器k = 1;
[0081] 2)获取块图像St稀疏表示系数的0t:256X256近似解的迭代过程
[0082] a)计算块感知矩阵Αβ=ΦβΨβ:ΜβΧ256中每一原子€4(丨=1，2，."，256)与当前二维 256 残差R(k-1) :Μβ X 256的整体相关度a = Σ?< -丨)/ >1，R(k-l)j是R(k-1)的第j列； j=]
[0083] b)通过对比Pi(i = l，2,…，256)，在序号不包含在集合的原子中选出与当前 残差最大相关的原子序号4:入1< = 11^1=1,2,...,256(0土）；
[0084] c )把人!^并入集合Λ k -i、把原子％k并入集合Ak-1得到：λ k = [ Λ k -i ]， 4 = [4: I，t J;
[0085] d)利用Ak和最小二乘优化方法得到本次迭代的近似逼近解Θ tk;
[0086] e)判断迭代结束条件：?tk达到设定重构精度或迭 代计数器k达到最大迭代次数K， 则结束块St的重建迭代并跳转至步骤(2)_5)，这时最后一次迭代中得到的? tk就是St的稀 疏表示系数Θ t的近似逼近解;否则更新参数R(k) =Y-Ak? tk和k = k+l，并返回步骤(2)-2)-a)继续迭代；
[0087] 5)利用St= ΨΒ Θ t得到St的近似逼近解瓦
[0088] (3)保存重建的块表并使t指向下一个需要重构的块
[0089] 1)把第t块重构信号4存入左；
[0090] 2)t = t+l；
[0091] (4)判断循环结束条件
[0092] 1)如果t>n，退出循环；
[0093] 2)否则，返回步骤(2)继续循环；
[0094] (5)得到完整的重构信号夂
[0095]计算复杂度和空间复杂度
[0096] 对于图像S: N X N，稀疏变换基Ψ : N X N，测量矩阵Φ : Μ X N，稀疏表示系数Θ : N X N， 压缩采样Υ : Μ X Ν，如果采用按列重构的方法，0 Μ Ρ的计算复杂度为 0( ,ν X /V( /C+ # + …+ 人'())二 a iv?·(人？ + < + …+ 人1))，假设这里的Ki (i = 1，2，…，N)相 等或接近，并设K=!1^问,2,..,N(Ki)，那么〇( /VK +人1 +…+ c))可以记为0(N2K2) 〇
[0097] 不同于0ΜΡ方法，WRFI利用原子与二维信号之间相关度的测量，在每次迭代时，选 出针对当前二维残差R(t-1):MXN的最大相关原子，并利用该原子更新矩阵A t及直接计算 二维系数Θ的近似估计?t:NXN，最终可以直接得到二维的最佳近似逼近解文WxW,而 不是信号S某列s 1:NXl的重构信号从而将迭代次数减少为0ΜΡ算法的1/N，即0 (NK2)，有效地降低了计算复杂度。
[0098] FBWRFI方法进一步通过分块重构的方式降低了优化操作中的参数规模，降低了优 化方法的计算量。它设计每个分块大小B = 256,这样一个分块的计算复杂度为0(2561^ 2)， f是分块的最大稀疏度。对图像S: N X N，其分块数位=「N/2561·「M2561，其计算复杂度可 表示为0(256111^ 2);且相对于0ΜΡ和WRFI方法的优化重建过程中使用的矩阵和Φ :MXN， FBWRFI在优化重建中使用Ψβ : 256 X 256和Φ :Mb X 256。也就是说，0ΜΡ和WRFI的优化迭代中 以N X N矩阵为计算对象，随着图像的增大，其计算时间的增长率将以指数级增加;而FBWRFI 的优化迭代中以256 X 256矩阵为计算对象，随着图像的增加，只是相应增加了几个基本运 算的循环，其计算时间的增长率理论上可以实现线性增加。FBWRFI与现有压缩感知方法的 计算复杂度对比如表4所示。
[0099] 表4筧法计筧复杂度对比
[0100]
[0101] FBWRFI方法效果
[0102] 重建不同图像，本组实验验证FBWRFI方法对不同图像的作用效果，实验结果表6和 图4证明了算法的有效性(这里的测试图像大小为512X512)。
[0103] 表6 FBWRFI对不同图像的重构时间和重构质量
[0104]
[0105] 不同采样率下重建图像效果，本组实验验证不同采样率下FBWRFI方法重建图像的 效果，实验结果表7和图5证明了算法的有效性(这里的测试图像大小为512X512)。
[0106] 表7不同采样率下FBWRFI重建图像的时间和质量
[0107]
[0108]不同大小图像的重建效果，本组实验验证FBWRFI方法重建大同大小的图像的效 果，实验结果表8和图6证明了算法的有效性(这里的测试图像大小为256 X256、512X 512和 1024X1024)。
[0109] 表8 FBWRFI和0ΜΡ重建不同大小图像的时间和质量对比
[0110]
[0111]快速重构算法的研究一直都是压缩感知理论研究的热点，我们提出面向图像重建 的快速压缩感知方法FBWRFI方法，它采用最小二乘优化方法实现图像的重建，基于图像的 整体相关度实现原子和二维残差之间的相关度测量以减少迭代次数、降低计算复杂度，弓丨 入块压缩感知降低优化迭代中的参数规模以降低计算量，并使重构时间随信号增大而呈线 性增长，提高了重构时间的可预估性。
[0112]应当理解的是，本发明的上述【具体实施方式】仅仅用于示例性说明或解释本发明的 原理，而不构成对本发明的限制。因此，在不偏离本发明的精神和范围的情况下所做的任何 修改、等同替换、改进等，均应包含在本发明的保护范围之内。此外，本发明所附权利要求旨 在涵盖落入所附权利要求范围和边界、或者这种范围和边界的等同形式内的全部变化和修 改例。
【主权项】
1. 一种基于最小二乘优化的压缩感知图像快速重建方法，其特征在于，包括以下步骤： SOI:把原始图像信号S:NXN基于压缩感知方法的压缩采样Y:MXN，根据块测量矩阵 Φβ:ΜβΧΒ划分为个互不重叠的块Yi:MBXB，其中是基于压缩感知方法进行 压缩采样时的采样率，S02:利用WRFI重构每个块St: B X B，压缩采样为Yt: Mb X B，稀疏系数记Θ t: B X B，其过程 如下： S02-01:计算块感知矩阵Ab = 一个原子ai(i = 1，2，…，B)与当前二维 残差R(k_l):MBXB的整体相关度其中k表示当前是第k次迭代,Ct1 是Ab的第i列，二维残差R(k-l)的初始值为￥1并在每次迭代后更新，R(k-l)」是R(k-l)的第j 列，Ψβ:ΒΧΒ是稀疏变换基且ΨΒ和ΦΒ线性无关； S02-02:通过对比Pi(i = l，2,…，Β)，在序号不包含在原子序号集合Ak-:的原子中选出 与当前残差最大相关原子的序号4 = 11^11=1,2,...^(0〇;其中人卜1是前面1^-1次迭代中选择 的最相关原子的序号组成的集合，Ak表示第k次迭代选出的最相关原子的序号； S02-03:把入集合Ak-:，把原子K并入集合Ak-1得到：Ak=[ Ak -， 馬_=[為];.其中0是六8的第Xk列，Ak-i是前面k_l中得到的最相关原子的集合； S02-04:基于Ak和最小二乘优化方法获取本次迭代的近似逼近解Θ tk; Θ tk是第k次迭代 得到的稀疏系数? t的近似逼近； S02-05:判断迭代条件:达到设定的重构精度或设定的最大迭代次数K，则结束重建块St 的迭代计算并跳转到S02-07; ?tk是St的稀疏表示系数?*的近似逼近解0,; S02-06:更新参数R(k) = Y-Ak Θ tk和k = k+l，跳转至S02-01继续迭代;这里k是新的迭代 次数，R(k)是新的二维残差； S02-07:利用St = ΨB Θ t得到St的近似逼近解 S02-08:判断是否每个块St都已经重建：即当t 2 η则跳至S03，否则跳至S02重构下一个 块 St+i; S03:将所有的重构信号袁:拼接得到完整的重构信号5。2. 根据权利要求1所述的基于最小二乘优化的压缩感知图像快速重建方法，其特征在 于，在重构过程之前还包括采样过程，采样过程包括以下步骤： S11:把原始图像信号S:NXN分割为暴=「iV75l2个大小为BXB的块，若原始信号边缘的 分块大小不足B X B，将不足的部分的元素填充为0; Sl2:对于每一个分块Si: B X B(i = 1，2，. . .，η)，使用相同的稀疏变换基ΨB: B X B进行稀 疏变换Si = ΨΒθ?，其中?i:BXB是Si的稀疏系数； 313:对于每一个分块3^8\8(1 = 1，2，...，11)，使用相同的测量矩阵〇8:1&\8进行投 影变换Yi = φ BSi，其中Yi: Mb X B是Si的压缩采样，就是采样率或压缩比，而Yi = φ BSi = 〇8屯8?河记为丫1 =厶8^^就是压缩感知方法的感知因子； S14:把每一个Yi(i = l，2, . . .，n)拼接起来组成Y :J就是原始图像信号 S的压缩采样，就是采样率或压缩比。3.根据权利要求1所述的基于最小二乘优化的压缩感知图像快速重建方法，其特征在 于，所述块测量矩阵Φβ的大小为MbXB，分块大小大于等于256X256,在分块时当原始信号 边缘的分块大小不足256 X 256，将不足的部分的兀素填充为O;当重构完成后，将填充部分 的值去掉。
【专利摘要】<b>本发明公开了一种</b><b>基于最小二乘优化的压缩感知图像快速重建方法，基于最小二乘方法实现信号的优化重构，利用新定义的整体相关性度量参数-整体相关度，选择针对图像信号的最相关原子，减少迭代次数,引入分块重构理论并重新设计分块大小和测量矩阵,降低了重构操作的计算规模；基于最小二乘方法实现信号的优化重构,保证了重构精度和收敛速度。实验结果表明,FBWRFI算法也可以显著降低信号的重构时间，并使随信号增大而高速增长的重构时间的增长趋势变为线性,证明了算法的有效性。</b>
【IPC分类】G06T5/50, G06T5/00
【公开号】CN105488767
【申请号】CN201510856958
【发明人】张永平, 王涛, 皋军, 邵星, 陈伟
【申请人】盐城工学院
【公开日】2016年4月13日
【申请日】2015年11月30日
【技术领域】
[0001] 本发明涉及一种压缩感知图像重建方法，具体地涉及一种面向图像的、基于最小 二乘优化的压缩感知采样快速重建方法。
【背景技术】
[0002] 基于稀疏表示理论和泛函分析-逼近理论的压缩感知（compressed sensing or compressive sampling，CS)是一种新型的采样方法，在对可压缩信号采样时能够突破著名 的Shannon-Nyquist采样定理的限制，以远低于两倍信号最大带宽的采样率对信号采样，从 而减少了采集的数据量。以其用少量采样值表示全长的信号的优点，压缩感知在出现之初 就吸引了信号、通信、电子信息、统计理论、编解码理论和计算机等众多领域的研究热情，被 认为是信息科学近年来最重大的研究成果。压缩感知基本原理如下：
[0003] 假设一维离散信号seRNxl是可压缩的(这是前提条件），压缩感知方法的信号采样 是利用特别设计的观测矩阵〇￡R MXN(这里M<<N)将可压缩信号s从N维投影到Μ维，即：y = Φ8;这里的yeRMxl是信号s的压缩采样，而采样y的长度Μ与信号 S的长度N与之比M:N就是在 压缩感知框架下的采样率，该采样率一定小于1。由于y=?s是欠定方程组，无法直接求解， 压缩感知方法从近似重构的角度来考虑求解问题。
[0004] 考虑信号s可压缩的前提和稀疏表示理论，对于可压缩信号s-定存在某稀疏变换 基Ψ ERNXN，使得s在该变换基上的表示0eRNxl是稀疏的，即：
[0005] (1)8 = ΨΘ，
[0006] 式中Θ的大部分元素为〇或接近于〇;通常Θ中非〇元素的个数Κ(Κ<<Μ<<Ν)被称 为Θ的稀疏度。从而有y = C>s = Φ ΨΘ=ΑΘ;这里的Α= Φ Ψ被称为信息算子或感知矩阵。y = ΑΘ可以通过0-范数优化问题求解
[0007] (2)min | | Θ | | 〇 s · t .y = A90
[0008] 而根据D〇noho、CandgS等人研究提出的压缩感知理论，在感知矩阵A具有有限等距 性质(Restricted Isometry Property，RIP)的条件下，0-范数优化可以转化为1-范数优化 问题：
[0009] (3)min| |θ| |i s.t.y = A0，
[0010] 其中，A具有RIP性质的等价条件是观测矩阵Φ与稀疏变换基ψ不相干，这一点在 设计观测矩阵Φ时已得到保证。
[0011] 由于Θ是稀疏的，通过（2)和（3)式可以得到其精确或近似逼近解古，然后利用（1) 式得到原始信号s的精确或近似逼近解5。常用压缩感知算法主要包括针对(2)式的贪婪算 法和针对(3)式的凸松弛算法。最经典的压缩感知算法就是凸松弛算法中的基追踪(Basis Pursuit,BP)算法，所需的观测值数目少（即采样率低）、计算精度高；匹配追踪(Matching Pursuit，MP)、正交匹配追踪（Orthogonal ΜΡ,ΟΜΡ)及其改进算法都是贪婪算法的代表，收 敛速度快、计算复杂度较低，实际应用较多。
[0012]压缩感知方法的信号重建是近似优化重构，非常适合于处理图像信号，目前其已 在磁共振、X-射线扫描、雷达成像、遥感图像处理、超频谱图像分析等方面有了很多应用，并 已开发出单像素相机。压缩感知算法的提出都是以一维信号为处理对象的，对于二维信号 一般以列或行向量为重建单位分别重建，当每一个列或行信号都被重建后，整个二维信号 也就重建成功了，图像信号的重建通常也是按列处理的。我们把图像信号S记为[ S1，S2，···， Sn]，其中Sl(i = l，2,…，η)为信号的第i列，在处理中每一个81分别进行重构。
[0013]压缩感知方法具有采样数目少的优点，但其应用仍然有很多难题等待解决，较长 的信号重构时间是其中的一个关键。如BP算法的计算复杂度高达0(N3)，收敛速度较快的 0ΜΡ算法的计算复杂度也达到了0(ΝΚ 2)。在配置为Intel(R)Core(TM)2Duo CPU E46000 2.4GHz、3GB内存、Windows 7、Mat 1 ab R2011 b的个人计算机上的重构不同大小信号时的重 构时间如表1和2所示。
[0014]表1 0ΜΡ和BP算法重构一维信号时，信号大小每增加1倍重构时间的变化 [0015]
[0016]表2 0ΜΡ和BP算法重构二维信号时，信号大小每增加1倍重构时间的变化
[0017]
[0018] 压缩感知算法重构信号所需的时间较长，并随信号增大以远大于信号增幅的速率 增长，而且这个速率随信号的增大还在不断增长。对比表1和表2可以发现，二维信号的重构 时间远远大于一维信号，且其增长幅度也较大;如大小为1024 XI的信号重构时间是512 XI 的5.55倍，而大小为1024X1024的信号重构时间是512X512的11.76倍。
[0019]我们在压缩感知算法及其应用的研究中，利用日渐普及的高性能计算设备和云计 算平台加速压缩感知算法，以提高算法的执行速度，验证了压缩感知方法在物联网数据采 集中的应用，实现了压缩感知算法的并行化、多/多核CPU加速、GPU加速和云平台加速等，加 速后的算法执行时间如图1和表3所示。
[0020] 表3 0ΜΡ算法重构信号时，不同数量计算资源的云加速效果(编程语言Python，云 平台）
[0021]
[0022] 从图1和表3中可知，压缩感知算法的并行化及加速虽然能显著减少算法的执行时 间，但不能改变算法随信号增大而以极高的速率增长的趋势。压缩感知算法的重构时间高 速增长，且增长趋势不断扩大，使重构算法的执行时间无法估计，不利于在云平台加速时的 自动资源分配。
【发明内容】
[0023] 针对上述技术问题，本发明目的是:提供一种基于最小二乘优化的压缩感知图像 快速重建方法FBWRFI，它采用最小二乘优化方法实现图像的重建，以保证收敛速度和重构 精度；以每一个原子和二维残差之间的整体相关度测量取代原子与一维残差之间的相关度 测量，以减少迭代次数、降低计算复杂度；引入块压缩感知理论并重新设计快大小和测量矩 阵，以降低优化迭代中的参数规模。该方法能够显著降低从压缩的采样中重建原始图像的 时间，并使图像的重构时间由随信号增大而以极高速率增加变为线性增长，提高了重构时 间的可预估性，有利于使用云资源加速时的资源智能分配。
[0024]本发明的技术方案是：
[0025] -种基于最小二乘优化的压缩感知图像快速重建方法，其特征在于，包括以下步 骤：
[0026] SO 1:把原始图像信号S: N X N基于压缩感知方法的压缩采样Y: Μ X N，根据块测量矩 阵Φ β :Mb X Β划分为"=「W/5下个互不重叠的块Yi:Mb X Β，其中|是基于压缩感知方法进 行压缩采样时的采样率：
[0027] S02:利用WRFI重构每个块St: B X B，压缩采样为Yt: Mb X B，稀疏系数记Θ t: B X B，其 过程如下：
[0028] S02-01:计算块感知矩阵Αβ=ΦβΨβ:ΜβΧΒ中每一个原子€4(丨=1，2，."，8)与当前 二维残差R(k-1):Mb X B的整体相关度A = ??< -屮 >卜其中k表示当前是第k次迭 Μ 代，<^是48的第i列，二维残差R(k-l)的初始值为1并在每次迭代后更新，R(k-lh是R(k-l) 的第j列，Ψb : B X B是稀疏变换基且Ψb和Φ b线性无关；
[0029] S02-02:通过对比Pi(i = 1，2，…，B)，在序号不包含在原子序号集合Λ k-:的原子中 选出与当前残差最大相关原子的序号4 = 11^11=1,2,...^(0〇;其中八1{-1是前面卜1次迭代中选 择的最相关原子的序号组成的集合，Ak表示第k次迭代选出的最相关原子的序号；
[0030] 302-03:把人1{并入集合人1{-1，把原子％并入集合4卜1得到 ：人1{=[人1{-1，人1{]， 為=[為、ι，α%];:其中气是Ab的第4列，Ak-i是前面k_l中得到的最相关原子的集合；
[0031] S02-04:基于Ak和最小二乘优化方法获取本次迭代的近似逼近解Θ tk; Θ tk是第k次 迭代得到的稀疏系数? t的近似逼近；
[0032] S02-05:判断迭代条件:达到设定的重构精度或设定的最大迭代次数K，则结束重 建块St的迭代计算并跳转到S02-07; ?tk是St的稀疏表示系数?*的近似逼近解Θ,;
[0033] S02-06:更新参数R(k)=Y-Ak?tk和k = k+l，跳转至S02-01继续迭代;这里k是新的 迭代次数，R(k)是新的二维残差；
[0034] S〇2_〇7:利用St= ΨΒ Θ t得到St的近似逼近解4;
[0035] S02-08:判断是否每个块St都已经重建：即当t 2 η则跳至S03，否则跳至S02重构下 一个块St+i;
[0036] S03:将所有的重构信号戋拼接得到完整的重构信号|。
[0037] 优选的，在重构过程之前还包括采样过程，采样过程包括以下步骤：
[0038] S11:把原始图像信号S:NXN分割为《 个大小为BXB的块，若原始信号边 缘的分块大小不足B X B，将不足的部分的元素填充为0;
[0039] S12 :对于每一个分块Si :BXB(i = l，2,…，n)，使用相同的稀疏变换基ΨΒ: B X B进 行稀疏变换Si= ΨΒθ?，其中?i:BXΒ是Si的稀疏系数；
[0040] S13:对于每一个分块Si:BXB(i = l，2,…，n)，使用相同的测量矩阵Φβ:ΜβΧΒ进行 u 投影变换Yi = φ BSi，其中Yi: Mb X Β是Si的压缩采样，γ就是采样率或压缩比，而Yi = Φ BSi =ΦΒΨΒΘ i可记为Yi = AB? i，AB就是压缩感知方法的感知因子；
[0041 ] S14:把每一个Yi (i = 1，2，…，η)拼接起来组成Γ X # )X ΛΓ, Y就是原始图像 信号S的压缩采样，^就是采样率或压缩比。 B
[0042] 优选的，所述块测量矩阵Φb的大小为Mb X B，分块大小大于等于256 X 256，在分块 时当原始信号边缘的分块大小不足256X 256,将不足的部分的元素填充为0;当重构完成 后，将填充部分的值去掉。
[0043] 与现有技术相比，本发明的优点是：
[0044] 本发明采用最小二乘优化方法实现图像的重建，以原子和二维残差之间的整体相 关度测量取代原子和一维残差之间的相关度测量，减少了迭代次数、降低计算复杂度，引入 块压缩感知理论降低优化迭代中的参数规模和计算规模，并使重构时间随信号增大呈线性 增长，提高了重构时间的可预估性。
【附图说明】
[0045] 下面结合附图及实施例对本发明作进一步描述：
[0046] 图1为0ΜΡ算法重构信号时，多CPU并行的加速效果图；
[0047] 图2为本发明基于最小二乘优化的压缩感知图像快速重建方法的整体重构设计的 流程图；
[0048]图3为本发明基于最小二乘优化的压缩感知图像快速重建方法的原理图；
[0049] 图4为使用本发明方法重构不同图像的效果图；
[0050] 图5为在不同采样率下重构图像的效果图；
[0051] 图6为重构不同大小图像的效果图。
【具体实施方式】
[0052]为使本发明的目的、技术方案和优点更加清楚明了，下面结合【具体实施方式】并参 照附图，对本发明进一步详细说明。应该理解，这些描述只是示例性的，而并非要限制本发 明的范围。此外，在以下说明中，省略了对公知结构和技术的描述，以避免不必要地混淆本 发明的概念。
[0053] 实施例：
[0054]本发明主要包括两部分:整体重构设计WRFI和基于分块压缩感知的快速重建方法 FBWRFI，它们之间的关系是:WRFI是以原子和二维残差之间的整体相关性测量取代原子和 一维残差之间的相关性测量后，面向图像整体的、较少迭代次数的快速重建方法;FBWRFI是 对需要重建的图像分块后，每一个图像块均采用WRFI方法进行重建，在保证较少迭代次数 的前提下降低迭代中的参数规模和计算量，以获取更快的重建速度和可预估的重构时间。
[0055] WRFI在重构过程中将二维信号作为一个整体来处理，而不是按列分别处理。为了 测量二维信号残差与测量矩阵各列（原子)之间的相关度，就需要定义新的相关度测量参 数，称之为二维信号的整体相关度(》11〇16-(301'代131：；[011)。
[0056] 定义1(整体相关度）.向量aeRmX1和矩阵Φ eRmXn的整体相关度（whole- η correlation)为Ρ = Σ?< ?肩>1，其中Ρ为整体相关度，灼是是矩阵Φ的第i列。 Μ
[0057] 对原始信号S:NXN(为了简单，假设S的行和列相同），设压缩采样Υ:ΜΧΝ，测量矩 阵Φ :ΜΧΝ，稀疏变换基Ψ:ΝΧΝ，记Α=ΦΨ:ΜΧΝ且有S = A?，θ :ΝΧΝ是稀疏的。WRFI的主 要思想是：在每次迭代时（第t次迭代），首先计算感知矩阵A中的每一个原子(A的每一列） ai:MXl(i = l，2，-_，N)与当前二维残差R(t-1):MXN(第t-Ι次迭代时更新的残差，初始值R (〇)=￥)的整体相关度01，并选出最大相关度/11.=〇^\.=1._，..._、,（八），这里最相关原子的序号 是&，最相关原子是心,；然后将和At-i合并为4 这里的At-i是前t-Ι次迭代 选出的最相关原子组成的矩阵；接着基于At和最小二乘优化方法获取本次迭代的近似估 计：
[0058]
[0059] 当近似估计執达到设定的精度或迭代计数器k达到设定的最大迭代次数K时，迭代 结束，本次迭代的近似估计氣就是Θ的重建结果;否则更新残差和增量t，并继续迭代。WRFI 的算法流程如图2所示。
[0060] 在本发明方法中，对信号S: NX N，其稀疏变换基ψ :N XN和测量矩阵Φ :Μ X N是线 性无关，这是前提条件。在S=w Θ和Υ=Φ5=ΦΨ θ =ΑΘ中，Υ:ΜΧΝ、θ :ΝΧΝ、Α=ΦΨ:Μ X Ν;对于 S的每一列 Si :NX1 都有Si=W9i(i = l，2,…N)和}^=Φ8?=ΦΨΘ? = Αθ?(? = 1， 2,…，Ν)，因 Ψ和Φ是线性无关的，根据压缩感知理论所有的Sl(i = l，2，-_，N)都可以被高 概率地重构，从而作为整体的S也就可以被高概率精确重构，也即本方法理论上是可行的。
[0061] WRFI通过将选择原子用于二维信号整体重建降低了原子选择和重构操作中的迭 代次数，但并不能改变重构时间的随信号增大而带来的高增长率。这主要是因为随着信号 规模的增加，算法中使用的稀疏变换基、观测矩阵及其它一些中间参数的规模也随之增大， 从而带来了优化算法中每一次迭代的计算量呈指数级增加。为了降低重构算法所需的存储 和计算的规模，将信号的大小保持在一个相对较小的程度是必须的。在面向图像的二维整 体重构得到WRFI的基础上，引入了块压缩感知(block compressed sensing)，并最终形成 了基于最小二乘优化的快速图像重建压缩感知方法FBWRFI方法。
[0062] FBWRFI首先把原始图像S:NXN被分割成若干个大小为BXB的小块(图像）。基于压 缩感知理论，图像S的稀疏变换就是对每一个块图像Si: B X B使用相同的稀疏变换基ΨΒ: B X Β进行操作Β就是块图像&的稀疏系数;图像S采样就是使用相同的测量 矩阵Φβ:ΜβΧΒ对每一个块图像Si进行投影变换Yi=〇 BSi;若记Αβ=ΦβΨβ:ΜβΧΒ，则Yi = AB Θ i，其中Mb : B可表示采样率/压缩比。因为设计测量矩阵① b:Mb X β时总是Mb< <B，采样率也 就小于1，实现了压缩采样。对于整个信号S来说，稀疏变换基Ψ : N XN和观测矩阵Φ :Μ X N(M =Mb X k，=「嫁/)分别如(5)式所示。
[0063] FBWRFI方法的（整体重构设计WRFI)原理与过程如图3所示。FBWRFI方法中设计的 块测量矩阵Φβ的大小为Mb XB，综合考虑重构时间和重构精度后把分块大小定义为256 X 256,这个分块大小是可以调整的，调整的原则基于实际应用中对重构图像精度的需求，分 块越大则重建图像的精度越高。在分块时，原始信号边缘各个分块大小可能不足B X B，需要 将不足部分的元素值填充为〇;当重构完成后，再将这部分的值去掉即可。
[0064]本发明的具体实现步骤，包括：
[0065] 输入:
[0066] 原始信号S: N X N，压缩采样Y: Μ X N，块测量矩阵Φ b : Mb X 256，块稀疏变换基ΨΒ: B \8，块稀疏度1(;
[0067] 输出:
[0068] 重构信号 [0069] 算法过程:
[0070] (1) FBWRFI 的初始化
[0071] 1)把压缩采样Y根据Φ b分块Yi: Mb X 256 (i = 1，2，…，η)，《 =「嫁/ 5下为块数量；
[0072] 2)t = l，t为块计数器；
[0073] 3)存放重构信号的参数糸
[0074] 4)最大块数η;
[0075] (2)使用WRFI重构每一个块图像5*:256\256(其压缩采样为￥*4 = 1，2，~，11)
[0076] 1)WRFI的初始化
[0077] a)残差;R〇 = Yt
[0078] b)已选出原子序号集合Λβ =0;
[0079] c)已选择的原子组成的矩阵Λ =01
[0080] d)迭代次数计数器k = 1;
[0081] 2)获取块图像St稀疏表示系数的0t:256X256近似解的迭代过程
[0082] a)计算块感知矩阵Αβ=ΦβΨβ:ΜβΧ256中每一原子€4(丨=1，2，."，256)与当前二维 256 残差R(k-1) :Μβ X 256的整体相关度a = Σ?< -丨)/ >1，R(k-l)j是R(k-1)的第j列； j=]
[0083] b)通过对比Pi(i = l，2,…，256)，在序号不包含在集合的原子中选出与当前 残差最大相关的原子序号4:入1< = 11^1=1,2,...,256(0土）；
[0084] c )把人!^并入集合Λ k -i、把原子％k并入集合Ak-1得到：λ k = [ Λ k -i ]， 4 = [4: I，t J;
[0085] d)利用Ak和最小二乘优化方法得到本次迭代的近似逼近解Θ tk;
[0086] e)判断迭代结束条件：?tk达到设定重构精度或迭 代计数器k达到最大迭代次数K， 则结束块St的重建迭代并跳转至步骤(2)_5)，这时最后一次迭代中得到的? tk就是St的稀 疏表示系数Θ t的近似逼近解;否则更新参数R(k) =Y-Ak? tk和k = k+l，并返回步骤(2)-2)-a)继续迭代；
[0087] 5)利用St= ΨΒ Θ t得到St的近似逼近解瓦
[0088] (3)保存重建的块表并使t指向下一个需要重构的块
[0089] 1)把第t块重构信号4存入左；
[0090] 2)t = t+l；
[0091] (4)判断循环结束条件
[0092] 1)如果t>n，退出循环；
[0093] 2)否则，返回步骤(2)继续循环；
[0094] (5)得到完整的重构信号夂
[0095]计算复杂度和空间复杂度
[0096] 对于图像S: N X N，稀疏变换基Ψ : N X N，测量矩阵Φ : Μ X N，稀疏表示系数Θ : N X N， 压缩采样Υ : Μ X Ν，如果采用按列重构的方法，0 Μ Ρ的计算复杂度为 0( ,ν X /V( /C+ # + …+ 人'())二 a iv?·(人？ + < + …+ 人1))，假设这里的Ki (i = 1，2，…，N)相 等或接近，并设K=!1^问,2,..,N(Ki)，那么〇( /VK +人1 +…+ c))可以记为0(N2K2) 〇
[0097] 不同于0ΜΡ方法，WRFI利用原子与二维信号之间相关度的测量，在每次迭代时，选 出针对当前二维残差R(t-1):MXN的最大相关原子，并利用该原子更新矩阵A t及直接计算 二维系数Θ的近似估计?t:NXN，最终可以直接得到二维的最佳近似逼近解文WxW,而 不是信号S某列s 1:NXl的重构信号从而将迭代次数减少为0ΜΡ算法的1/N，即0 (NK2)，有效地降低了计算复杂度。
[0098] FBWRFI方法进一步通过分块重构的方式降低了优化操作中的参数规模，降低了优 化方法的计算量。它设计每个分块大小B = 256,这样一个分块的计算复杂度为0(2561^ 2)， f是分块的最大稀疏度。对图像S: N X N，其分块数位=「N/2561·「M2561，其计算复杂度可 表示为0(256111^ 2);且相对于0ΜΡ和WRFI方法的优化重建过程中使用的矩阵和Φ :MXN， FBWRFI在优化重建中使用Ψβ : 256 X 256和Φ :Mb X 256。也就是说，0ΜΡ和WRFI的优化迭代中 以N X N矩阵为计算对象，随着图像的增大，其计算时间的增长率将以指数级增加;而FBWRFI 的优化迭代中以256 X 256矩阵为计算对象，随着图像的增加，只是相应增加了几个基本运 算的循环，其计算时间的增长率理论上可以实现线性增加。FBWRFI与现有压缩感知方法的 计算复杂度对比如表4所示。
[0099] 表4筧法计筧复杂度对比
[0100]
[0101] FBWRFI方法效果
[0102] 重建不同图像，本组实验验证FBWRFI方法对不同图像的作用效果，实验结果表6和 图4证明了算法的有效性(这里的测试图像大小为512X512)。
[0103] 表6 FBWRFI对不同图像的重构时间和重构质量
[0104]
[0105] 不同采样率下重建图像效果，本组实验验证不同采样率下FBWRFI方法重建图像的 效果，实验结果表7和图5证明了算法的有效性(这里的测试图像大小为512X512)。
[0106] 表7不同采样率下FBWRFI重建图像的时间和质量
[0107]
[0108]不同大小图像的重建效果，本组实验验证FBWRFI方法重建大同大小的图像的效 果，实验结果表8和图6证明了算法的有效性(这里的测试图像大小为256 X256、512X 512和 1024X1024)。
[0109] 表8 FBWRFI和0ΜΡ重建不同大小图像的时间和质量对比
[0110]
[0111]快速重构算法的研究一直都是压缩感知理论研究的热点，我们提出面向图像重建 的快速压缩感知方法FBWRFI方法，它采用最小二乘优化方法实现图像的重建，基于图像的 整体相关度实现原子和二维残差之间的相关度测量以减少迭代次数、降低计算复杂度，弓丨 入块压缩感知降低优化迭代中的参数规模以降低计算量，并使重构时间随信号增大而呈线 性增长，提高了重构时间的可预估性。
[0112]应当理解的是，本发明的上述【具体实施方式】仅仅用于示例性说明或解释本发明的 原理，而不构成对本发明的限制。因此，在不偏离本发明的精神和范围的情况下所做的任何 修改、等同替换、改进等，均应包含在本发明的保护范围之内。此外，本发明所附权利要求旨 在涵盖落入所附权利要求范围和边界、或者这种范围和边界的等同形式内的全部变化和修 改例。
【主权项】
1. 一种基于最小二乘优化的压缩感知图像快速重建方法，其特征在于，包括以下步骤： SOI:把原始图像信号S:NXN基于压缩感知方法的压缩采样Y:MXN，根据块测量矩阵 Φβ:ΜβΧΒ划分为个互不重叠的块Yi:MBXB，其中是基于压缩感知方法进行 压缩采样时的采样率，S02:利用WRFI重构每个块St: B X B，压缩采样为Yt: Mb X B，稀疏系数记Θ t: B X B，其过程 如下： S02-01:计算块感知矩阵Ab = 一个原子ai(i = 1，2，…，B)与当前二维 残差R(k_l):MBXB的整体相关度其中k表示当前是第k次迭代,Ct1 是Ab的第i列，二维残差R(k-l)的初始值为￥1并在每次迭代后更新，R(k-l)」是R(k-l)的第j 列，Ψβ:ΒΧΒ是稀疏变换基且ΨΒ和ΦΒ线性无关； S02-02:通过对比Pi(i = l，2,…，Β)，在序号不包含在原子序号集合Ak-:的原子中选出 与当前残差最大相关原子的序号4 = 11^11=1,2,...^(0〇;其中人卜1是前面1^-1次迭代中选择 的最相关原子的序号组成的集合，Ak表示第k次迭代选出的最相关原子的序号； S02-03:把入集合Ak-:，把原子K并入集合Ak-1得到：Ak=[ Ak -， 馬_=[為];.其中0是六8的第Xk列，Ak-i是前面k_l中得到的最相关原子的集合； S02-04:基于Ak和最小二乘优化方法获取本次迭代的近似逼近解Θ tk; Θ tk是第k次迭代 得到的稀疏系数? t的近似逼近； S02-05:判断迭代条件:达到设定的重构精度或设定的最大迭代次数K，则结束重建块St 的迭代计算并跳转到S02-07; ?tk是St的稀疏表示系数?*的近似逼近解0,; S02-06:更新参数R(k) = Y-Ak Θ tk和k = k+l，跳转至S02-01继续迭代;这里k是新的迭代 次数，R(k)是新的二维残差； S02-07:利用St = ΨB Θ t得到St的近似逼近解 S02-08:判断是否每个块St都已经重建：即当t 2 η则跳至S03，否则跳至S02重构下一个 块 St+i; S03:将所有的重构信号袁:拼接得到完整的重构信号5。2. 根据权利要求1所述的基于最小二乘优化的压缩感知图像快速重建方法，其特征在 于，在重构过程之前还包括采样过程，采样过程包括以下步骤： S11:把原始图像信号S:NXN分割为暴=「iV75l2个大小为BXB的块，若原始信号边缘的 分块大小不足B X B，将不足的部分的元素填充为0; Sl2:对于每一个分块Si: B X B(i = 1，2，. . .，η)，使用相同的稀疏变换基ΨB: B X B进行稀 疏变换Si = ΨΒθ?，其中?i:BXB是Si的稀疏系数； 313:对于每一个分块3^8\8(1 = 1，2，...，11)，使用相同的测量矩阵〇8:1&\8进行投 影变换Yi = φ BSi，其中Yi: Mb X B是Si的压缩采样，就是采样率或压缩比，而Yi = φ BSi = 〇8屯8?河记为丫1 =厶8^^就是压缩感知方法的感知因子； S14:把每一个Yi(i = l，2, . . .，n)拼接起来组成Y :J就是原始图像信号 S的压缩采样，就是采样率或压缩比。3.根据权利要求1所述的基于最小二乘优化的压缩感知图像快速重建方法，其特征在 于，所述块测量矩阵Φβ的大小为MbXB，分块大小大于等于256X256,在分块时当原始信号 边缘的分块大小不足256 X 256，将不足的部分的兀素填充为O;当重构完成后，将填充部分 的值去掉。
【专利摘要】<b>本发明公开了一种</b><b>基于最小二乘优化的压缩感知图像快速重建方法，基于最小二乘方法实现信号的优化重构，利用新定义的整体相关性度量参数-整体相关度，选择针对图像信号的最相关原子，减少迭代次数,引入分块重构理论并重新设计分块大小和测量矩阵,降低了重构操作的计算规模；基于最小二乘方法实现信号的优化重构,保证了重构精度和收敛速度。实验结果表明,FBWRFI算法也可以显著降低信号的重构时间，并使随信号增大而高速增长的重构时间的增长趋势变为线性,证明了算法的有效性。</b>
【IPC分类】G06T5/50, G06T5/00
【公开号】CN105488767
【申请号】CN201510856958
【发明人】张永平, 王涛, 皋军, 邵星, 陈伟
【申请人】盐城工学院
【公开日】2016年4月13日
【申请日】2015年11月30日
最新回复(0)