第1期 赵春晖，等：压缩感知理论及其在成像技术中的应用 29 叶变换矩阵中随机地选择M行构成Φ，并对Φ的 到目前为止出现的主要重构算法可以分为以下3 每一列进行归一化.部分傅里叶矩阵的一个突出优 类n556 点是可以利用快速傅里叶变换进行快速计算，大大 1)凸松弛法.这类方法通过将非凸优化问题转 降低了采样系统的复杂性，然而由于其通常只与时 化为凸优化问题求解，找到信号的逼近，代表算法包 域稀疏的信号不相关，所以应用范围受到了限制. 括基追踪算法(basis pursuit,BP)[]、内点法(interi- 5)局部Hadamard观测矩阵o):从W维矩阵中 or-point method)I]、梯度投影法(gradient projec- 随机选择M行得到.如果用B表示分块的大小， tion)s】、迭代阈值法(iterative thresholding algo- 那么当M≥S√W/Bn(W)2时，置乱块Hadamard矩 rithm)[s]和迭代硬阈值法(ierative hard thresholding 阵可以以极大概率精确重构信号. algorithm,IHT)【6o] 6)Toeplitz观测矩阵和循环矩阵[g]:当M≥C× 2)贪婪算法.这类方法通过每次迭代时选择一 M×ln(N/M)时，这2种矩阵使观测矩阵以很大概 个局部最优解来逐步逼近原始信号.代表算法包括 率满足P条件，并且可以直接应用快速傅里叶变 匹配追踪算法(maching pursuit,MP)[o]、正交匹配 换得到快速的重构算法，能够明显降低高维问题的 追踪算法(orthogonal matching pursuit,OMP)[6]、分 计算和存储复杂度，因而对高维问题特别有效， 段正交匹配追踪算法(stagewise orthogonal matching 在性能表现方面，Y.Tsaig等对一致球面观测矩 pursuit,SOMP)[、正则化正交匹配追踪算法(reg 阵、二值随机观测矩阵、局部Hadamard观测矩阵以 ularized orthogonal matching pursuit,ROMP)3 及部分傅里叶观测矩阵的性能进行了比较，实验表 缩感知匹配追踪算法(compressive sampling matching 明使用这几类矩阵作为观测矩阵时，CS重建信号的 pursuit,CoSaMP)[s5] 误差都比较小，并且随着观测样本数量的增加误差 3)组合算法.这类方法要求对信号进行高度结 将会进一步减小9)，该结论对于现有已被验证的所 构化地采样，通过分组测试快速重建.代表算法包括 傅里叶采样[6]、链式追踪s]和HHS(heavy hitters 有观测矩阵都是成立的.文献[54]也通过实验对比 on steroids)追踪[]等 了常用观测矩阵的性能优劣程度，在信号稀疏度和 CS观测数均相同的条件下，局部Hadamard观测矩 上述3类算法各有其固有的优缺点，其中凸松 阵的性能优于其他观测矩阵，且稀疏度越大效果越 弛法在重建时需要的观测值最少，精度最高，但是计 算复杂度也最高；组合算法的运行效率最高，但是其 明显，其次是Toeplitz观测矩阵，而随机高斯观测矩 需要的观测值数量最多：贪婪算法则是在运行效率 阵、二值随机观测矩阵在各种稀疏度下重建效果皆 对观测值的需求和重建精度方面都取得了折衷的效 ·致，重建效果最差的是部分傅里叶观侧矩阵 果.目前CS应用中使用较多的主要是前2类算 对于CI技术来说，最理想的观测矩阵是只包含 法1 0和1的二值矩阵，而且其中0与1的比例越高观 由于图像的特殊性，其重建可以采用TV最小 测效率就越高，这也同样适用于CS的其他应用领 化方法「]对像素间梯度进行优化，这种算法的优势 域。一方面来说，二值矩阵具有的状态最少，因而最 是在重建过程中不必提供稀疏分解矩阵，并且可以 容易实现；另一方面来说，获得观测值后一般要通过 求解出精确结果；其缺点在于计算复杂，求解效率非 量化才能进行编码操作，如果采用诸如高斯观测矩 常低，在处理尺寸较大的图像时可能需要若干天的 阵、一致球面观测矩阵或部分傅里叶观测矩阵等作 时间.令‖I‖v表示二维图像I的全变差，若图像 为观测手段的话，那么量化过程会导致更大的信息 的每一个像素为I(t1,t2),0≤t,t2≤N-1,则 丢失并直接影响图像的重建效果.因此如何构造满 足RP并且O、1比例高的二值观测矩阵将是CI技 I1lw=∑√D1(1,2)2+1D2l(4,2) 术今后发展中的热门问题之一 式中：D为有限差分， 4.3重建算法 D1I(t1,2)=I(61,2)-I(t1-1,2), 设计稳定有效的重建算法是实现CS的关键问 D2I(t1,2）=I(t1,2)-I(61,2-1). 题之一，也是当前CS研究中最热门的方向之一.由 通过求解式(10)即可精确重建原始图像I. 于从观测值中重建出原始信号的方式不是惟一的， '=min‖I‖w满足=y. (10) 因此构造重建算法的手段也多种多样.目前已有大 5 量的文献从不同的角度设计出了许多行之有效的方 结束语 案来解决稀疏信号的重建问题，这些算法在求解精 CS理论从出现至今短短的数年内已经得到了 度、运行效率和适用范围都不各相同，但归纳起来， 长足的发展，新的理论层出不穷；而CI作为CS理论