压缩感知算法在数字图像处理中的研究与应用

邱中杰 杜宏博 王雯 马洪 李重华

摘 要：随着压缩感知理论研究工作的深入，压缩感知在信号和图像处理领域已引起众多研究者的关注。理论已经证明自然图像本身具有稀疏的表示特性，符合人类所接触的很多信号和图像的处理。近年来，压缩感知理论已被大量应用到信号和图像处理的各个领域[1]。如何构造一个适合不同模态图像的变换字典，并设计相应的快速而有效的稀疏分解算法是本项目中稀疏分解矩阵建立研究的重要内容；提出快速、准确、鲁棒性好的CS重建算法也是本项目研究的主要内容之一。

关键词：压缩感知；稀疏表示；变化字典；鲁棒性

1 引言

目前，图像压缩技术可主要分为两大类，即有损压缩和无损压缩。无损压缩虽然严格地保证了图像质量，但是压缩率较低，仅为2～3倍，无法达到实时传输和节省存储空间的要求。为了提高压缩率，人们开始尝试有损压缩算法，主要包括区域压缩算法[2]、JPEG压缩算法[3]、基于小波变换的压缩算法[4]、面向对象的区域运动补偿算法[5]等。这些算法虽然在很大程度上压缩了图像的冗余信息，但是其压缩处理方法均基于以下几个步骤进行：即首先对可压缩信号进行高速采样、然后对采样数据进行压缩，最后把压缩过的信号进行解压缩以便恢复原始信号。众所周知，传统信号采样的准则是Nyquist采样定理，因此，在影像设备将模拟信号转成數字图像的过程中经常需要较高的采样率，而为了便于传输，又要对获得的大量信息进行数据压缩，只保留一部分必要信息。这在很大程度上浪费掉了采集、存储和计算资源。

2 压缩感知的研究背景与理论简介

压缩感知（compressive sensing，CS）技术自2006年诞生以来，就以其在图像压缩和传输领域中表现出来的独特优势，迅速引起国内外学者的高度重视，被美国科技评论评为2007年度十大科技进展。CS的核心思想是将信号采样与压缩融合在一起，即在采样的同时实现信号的压缩，以尽量地降低信号的冗余信息。CS突破了传统的Nyquist采样定理，只要信号是可压缩的或稀疏的，CS就可以以极低的采样率采样，然后又可以利用测量值精准地重构原始信号。目前，CS的理论研究主要集中在信号的稀疏分解、信号观测矩阵建立和信号重构三个方面[6]。尽管其理论研究仍出于起步阶段，但已成为信息论、图像处理、模式识别、医疗成像、地址勘探等领域的一大研究热点。在麻省理工学院、斯坦福大学等许多知名大学已专门成立CS课题组。国内关于CS的研究基本同步进行，不过研究成果较国外少些。

随着稀疏重构和新兴采样定理研究的不断发展，很多学者发现，当测量数据不完全时，甚至只有很小一部分测量数据时，利用该方法仍可以很好重构原图像。例如图1-1重现了Candes等人在核磁共振成像（Magnetic Resonance Imaging，MRI）研究中的发现。其中图1-1（a）为原图像，MRI中的测量数据可以理解为原图像的Fourier变换，一次测量可以理解为Fourier域中的某个角度下的“切片”，即如图1-1（b）图中的一条直线，传统的方法需要大量的测量，即密集的直线，才可以高质量地重构图像。当只有18个角度的测量数据时（如图1-1（b）所示，只占整个频域的7.71%），传统的后向投影（Back Projection，BP）方法重构的图像如图1-1（c）所示，如果在重构过程中引入稀疏性约束，则可以高精度地重构原图像，如图1-1（d）所示[7]。

这个发现最终诱使了压缩感知理论的产生。其后，Candes、Tao与Romberg等人，初步建立了压缩感知的理论模型[57]。压缩成像主要分为两个组成部分：数据的获取过程以及图像的重构过程。其中，前半部分在理论上需研究使得“稀疏重构”能够恢复原信号的测量矩阵性质，即重构条件；后半部分与稀疏重构的研究一脉相承，但是需要特别考虑二维图像所涉及的大规模数据情况下的保精度快速计算问题。

3 研究内容

结合本项目的主要研究内容以及综合考虑项目多研究领域的交叉性质，将研究内容分为以下几个部分：

3.1 图像的稀疏分解矩阵建立

CS理论的提出是建立的信号的稀疏性基础上的，信号的稀疏性直接影响观测个数进而影响图像的压缩率和重构的准确性，因此，图像稀疏分解矩阵的选取非常重要。

信号的稀疏性是指信号中的元素绝大多数为零元素，只有少数是非零的，稀疏性是进行压缩传感的前提条件。信号在某一适合的基下均能稀疏表示。例如图2-1（a）中的图像和其小波变换图2-1（b）。由两幅图像可看出，原始图像中几乎所有像素均为非零值，但是当对其进行小波变换时，得到的小波系数却提供了一种简明的表示方法：大多数小波系数的值都很小，只有很少的小波系数其值较大，这些大的小波系数携带了图像绝大多数的信息。

用数学语言可描述为，对于一个N维向量x∈R（如图1中有n个像素）可由一个正交基（如小波基）Ψ=[Ψ1，Ψ2，…Ψn]展开为如下式：

其中αi是x的系数序列，αi=〈x，Ψ1〉。上式可很方便的将x表示为Ψ（其中Ψ为N×N）的矩阵，Ψ1，Ψ2，…Ψn是它的列）。这样信号的稀疏性的含义就很清楚了：当一个信号可以稀疏表示时，人们可以丢弃小的系数，并感觉不到信息的丢失。在形式上可表示为，xs（t）是由展开式（1-1）中αi只保留S个最大值得到的。定义xs（t）=Ψαs，其中αs为xi中除了S个最大值，其它均设为0的系数向量。由于这个向量除了少数几个元素均为0，因此它是严格稀疏的；这种只有S个非零元素的对象称为我们称之为S-稀疏。如果是稀疏的或可压缩的，即（αi）按幅值排列迅速递减，则α与αs近似；又由于Ψ是正交基，我们有||x-xs||12=||α-αs||12，那么||x-xs||12的差很小。通俗的表述为，人们可“扔掉”大部分的稀疏而不会丢失很多信息。图2-1（c）给出这种例子，图像在扔掉97.5%的系数后，仍很难察觉到信息的丢失。

图2-1（a）原始图像的像素值范围为[0，255]；（b）图像的小波变换系数，只有少数小波系数携带有绝大多数信号的能量，这种图像具有高可压缩性；（c）仅用25000个较大的小波系数对图像进行重构的结果（图像像素范围为[0，255]），它与原始图像的差别很难觉察到。目前常用的稀疏变换基有离散小波变换（DWT），离散余弦变换（DCT），过完备原子分解等。当目标信号在标准正交基构成的空间中不具有稀疏性时，可采用过完备原子法进行信号的稀疏化表达[8]。

3.2 快速、准确、鲁棒性好的CS重建算法研究

信号重构算法是压缩感知理论关键的一部分，对于压缩信号的精确重构以及采样准确性的验证均具有重要的意义。现有的CS重建算法有很多种，例如贪婪追踪算法、松弛算法、范数优化算法、组合算法及最小变分算法等。每种重建算法都有其固有的缺点，无法同时兼顾算法复杂度、计算时间、观测数目、重构质量等多个目标。以下例举正交匹配追踪算法与梯度追踪算法。

（1）正交匹配追踪算法（OMP）。正交匹配追踪算法时常用的恢复算法，是属于贪婪算法一类的，来源于匹配追踪算法（MP）。MP是一种迭代算法，每次迭代的过程中选取观测矩阵中与信号残差最相关的列向量进行逼近，反复迭代计算残差，当残差值小于某一预设的数值或者达到最大迭代次数是停止，所得到的重构信号的迭代结果即为重构得到的原始信号。

OMP是MP的改进，差距体现在OMP算法过程中每次迭代计算后的残差值都是和观测矩阵的所选的列向量是正交的，重构信号则通过观测信号和所选列向量求伪逆的结果求得。因为在迭代过程中，计算的残差均与所选的列向量正交，使得每次都进行最优的迭代运算，使得重构算法达的迭代次数减少、重构信号跟接近于原始信号。

（2）梯度追踪算法。正交匹配追踪算法中需要进行求伪逆预算，一般的情况下伪逆运算采用QR分解或Cholesky分解实现，运算量很大，为了提升运算速度，Blumensath等人提出了梯度追踪算法（GP）。

该算法通过构造目标函数并求其梯度的极小值代替求方程组解，该算法的步骤如下：

重构算法输入：观测矩阵Ф，观测结果y，稀疏度k。

重构算法的输出：逼近与原始信号x的稀疏解向量 。

重构算法初始化：残差r0=y，所选列向量的索引集Λ= ，迭代次数t=1， =0。

3.3 CS观测矩阵构造

压缩传感理论具有稀疏或可压缩的特性，经过非相干的随机投影可直接获取的系数虽然不多，却包含信号中的绝大部分信息，继而实现采样与压缩的同步。因此，构建合适的投影矩阵也即观测矩阵是本项目的主要研究内容。

⑴自适应随机观测矩阵设计。目前观测矩阵的设计主要包括随机观测矩阵、确定性观测矩阵和自适应观测矩阵三种。自适应随机观测矩阵是最近新兴起的CS观测矩阵构造方法，可以同时降低计算复杂度和相关性。

⑵基于多观测向量和稀疏贝叶斯学习的CS重建算法研究。大多数现有的CS重建算法都是针对一维信号进行处理，这些算法可以看成是基于单观测向量的重建算法。在处理图像信号时，如果能直接对图像信号进行处理，将提高算法的计算效率，同时也将克服将图像信号转换成一维信号处理对重构图像质量所造成的影响。相关研究表明，基于稀疏贝叶斯学习（SBL）方法能够在重构过程中获得全局最优解，因此本项目拟将SBL算法应用到CS图像重构中。同时为了克服传统算法针对单观测向量模型处理图像信号所出现的问题，将由图像信号观测得到的观测矩阵的每一列看作是一个观测向量，则观测矩阵被看成是由多观测向量（MMV）组成的矩阵。本项目结合MMV和SBL研究一种有效的CS重建算法，以缩短图像重建的时间并提高图像重建质量。

⑶利用自适应基追踪去噪方法重构CS图像。基于CS对含噪声的图像进行采样重构，其误差主要来源于两个方面。第一是无噪声情况下CS压缩重构本身带来的噪声。第二与信号本身含有的噪声大小有关。本项目将两类情况综合起来，把CS采样和自适应基追踪去噪运用到含噪声的图像压缩与重构中，既能减少存储、传输所占用的资源，又能在重构过程实现图像增强，保证接收端能够获得高质量的图像。

5 总结与展望

压缩感知理论的提出，将K-SVD字典和稀疏编码的思想与压缩感知相结合并运用于图像压缩编码中以代替传统的图像编码方法是本文的中心内容。然而，由于压缩感知理论是一个新颖的理论，其相关应用还不成熟，因此取代JPEG及JPEG2000算法在图像压缩编码领域的地位还有很长的路要走[10]。

本文在压缩感知的理论基础上，致力研究图像易于存储和计算的CS观测矩阵，尽可能地降低重建所需要的观测数目，提高图像压缩率；研究CS图像重构算法，降低其计算复杂度，同时缩短重构时间并提高图像的重构质量。同时，通过大量实验，观察不同参数下图像的重构质量和压缩比，得到参数控制结果的规律，并经过统计和总结，得到最优的参数值，使得图像在高压缩比的基础上同时拥有较好的重构质量。在编程实现的基础上验证了算法的可行性，然而实践是检验真理的唯一标准，这种算法是否能够真正投入到实际应用中，还需要进一步经过实践的考验。

[参考文献]

[1]邹伟.压缩感知在图像处理中的应用研究[D].上海交通大学硕士学位论文，2012.

[2]DEMOS G.High quality wide-range multi-layer image compression coding system[J].Google Patents，2011.

[3]SINGH P，SINGH P，SHARMA R K.JPEG image compression based on Biorthogonal，Coiflets and Daubechies Wavelet Families[J].Int J Comput Appl，2011，13（1）：1–7.

[4]TALUKDER K H，HARADA K.Haar wavelet based approach for image compression and quality assessment of compressed image[J].arXiv preprint arXiv：1010.4084，2010.

[5]DING J-J，LIN P-Y，HUANG J-D，et al.Morphology-based shape adaptive compression[G].Advances in Multimedia Modeling. Springer，2011：168–176.

[6]CAND?S E J，WAKIN M B.An introduction to compressive sampling[J].Signal Processing Magazine，IEEE，IEEE，2008，25（2）： 21–30.

[7]馮鑫.多尺度分析与压缩感知理论在图像处理中的应用研究[D].上兰州理工大学博士学位论文，2012.

[8]丁伟.基于压缩感知的水下图像处理[D].中国海洋大学硕士学位论文，2013.

[9]崔佳鹏.基于压缩感知的图像压缩技术研究与实现[D].哈尔滨工业大学工程硕士学位论文，2013.

[10]郎彦昆.压缩感知技术及其在数字图像压缩编码中的应用研究[D].北方工业大学硕士学位论文，2013.