刘国庆， 林 京

（合肥工业大学 数学学院，安徽 合肥 230009）

0 引 言

在传统的信号采集过程中，为了避免信号失真及码间干扰，一般都会遵循Nyquist采样定理（又称香农采样定理），它要求针对信号的采样率不得低于信号带宽的2倍。这无疑对信号处理的能力提出了较高的要求，也给相应的硬件设备带来了极大的挑战，寻找新的数据采集和处理方法成为一种必然。文献［1］提出的压缩感知（Compressed Sensing，简称CS）理论是一种充分利用信号稀疏性或者可压缩性的全新信号获取和处理理论，利用其他变换空间描述信号，使得在保证信息不损失的情况下，用远低于采样定理要求的速率采样信号的同时，又可完全恢复信号，即将对信号的采样率转变为对信息的采样，较大地降低了信号采样频率、信号处理时间和计算成本以及数据存储和传输的代价。

目前，基于小波的图像处理技术，例如图像压缩及图像融合［2－3］等已日臻成熟，而压缩感知在图像处理方面的应用正在开展中。

文献［4］根据图像小波变换系数层的特点，提出了基于单层小波变换的压缩感知算法，处理二维图像。然而在许多实际应用中，信号的稀疏度往往未知，本文对文献［4］其算法进行了改进，提出了适应稀疏度未知情况的基于单层小波变换的自适应压缩感知算法，并进行了实验仿真。

1 压缩感知与自适应重建算法

设x∈RN×1为一维信号，则其可以由一组规范正交基Ψ＝｛ψ1，…，ψN｝展开（例如小波基）Ψ＝｛ψ1，…，ψN｝，即

其中，yk＝〈x，ψk〉，逆变换为y＝ΨHx，此处，ΨΨH＝ΨHΨ＝I，Ψ∈CN×N，I为单位矩阵。x和y是相同信号的等价表示，x是信号在时域的表示，y是信号x在Ψ域的表示。如果向量y的非零元素个数为K，则称信号x在基Ψ 下是K－稀疏（K－Sparse）的；若在基Ψ下，y按照大小排序，以近似于幂律衰减，则称信号x是可压缩的。

对于信号x，可将其投影到一组测量向量Φ＝｛φ1，…，φM｝上，得到x的M 个线性测量，即

其中，Φ∈RM×N，Φ的每一行可以看做一个传感器，它与信号相乘，拾取了信号的一部分信息，根据这M个测量和Φ，就可以重构原始信号，将（1）式代入（2）式，得

其中，Θ＝ΦΨ为M×N矩阵。由此可知，压缩感知将信号x从N 维降为M 维观测信号s，由于（2）式中未知数个数N大于方程个数M，若直接求解（2）式来重构信号不能得到确切解。而（3）式中的y是K－稀疏的，即仅有K 个非零系数，且K＜M≤N，则可通过已有的稀疏分解算法求解（3）式的逆问题得到稀疏系数y，再通过（1）式得到重构信号x。为保证算法的收敛性，（3）式的Φ必须满足有限等距准则［5］（Restricted Isometry Property，简称RIP），即对于任意具有严格K－稀疏的向量v，Φ满足：

其中，δ＞0。RIP准则的一种等价情况是测量矩阵Φ和稀疏矩阵Ψ满足不相关性的要求。对于CS理论，其逆变换重构过程为求解l0范数下的最优化（Optimization）问题，即

而l0范数的求解是个NP－Hard问题，因此可将问题转化为：

对于（6）式中l1最小范数下的最优化问题，目前的求解算法有梯度投影法（GP）［6］、基追踪法（BP）［7］、匹配类追踪法［8］等，而应用最广的则属匹配追踪类方法，具有代表性的有正交匹配追踪法（OMP）［9］、正则化正交匹配追踪法［10］等，但上述算法都要求已知信号的稀疏度，给实际应用带来很大不便。文献［11］提出了一种稀疏自适应追踪算法（SAMP），很好地解决了稀疏度未知的问题。该算法描述如下。

输入：传感矩阵Φ，采样向量y，步长s。

输出：未知输入信号x的K－稀疏的逼近＾x。

初始化：＾x＝0，残差r0＝y，支撑集F0＝∅，支撑集大小l＝s，迭代次数k＝1，索引值j＝1；

循环执行如下步骤：

（1）初测试Sk＝max（｜Φ＊rk－1｜，l）。

（2）计算候选集Ck＝Fk－1∪Sk。

（4）计算残差r＝y－ΦFy。

（5）判断是否满足停止迭代条件，若满足，则停止迭代，若不满足，执行步骤（5）。

（6）判断是否满足‖r‖2≥‖rk－1‖2，若满足，执行步骤（6）；若不满足，执行步骤（7）。

（7）进入下一阶段j＝j＋1，支撑集F的大小增加为l＝j×s。

（8）更新支撑集Fk＝F，残差rk＝r，k＝k＋1。

2 基于单层小波变换的压缩感知算法

在原有CS算法的图像处理中，将N×N的图像首先进行某种变换，如DCT变换、小波变换等，然后构造测量矩阵Φ，利用Φ对全部的小波变换系数进行测量，得到M×N大小的测量系数。恢复图像的时候，根据Φ和M×N大小的测量系数，通过OMP等算法恢复出原图像。

由于小波分解将原图像分为高频子带和低频子带，高频子带可以认为是稀疏的，但低频子带是原图像在不同尺度下的逼近信号，不能认为是稀疏的，而将低频与高频系数一起与测量矩阵Φ相乘则会破坏低频逼近分量系数之间的相关性，导致重构效果变差。当小波分解层次只有1层时，重构的图像已经看不出原貌。因此，小波变换层次应该尽可能大，一般对256×256的图像分解层次应该在4层以上。

文献［4］提出了基于单层小波变换的CS改进算法，首先只对原图像进行单层小波变换，然后只对第1层高频子带进行测量，对低频逼近子带则保留小波分解的系数，最后对高频系数测量值利用OMP算法进行重构，并与低频子带一起进行小波反变换得到恢复的图像。

3 单层小波变换的自适应压缩感知算法

在许多实际应用中，图像的稀疏度往往是未知的，因此本文在此基础上提出了一种改进算法，适应稀疏度未知的情况。由于单层小波变换后高频子带具有如下特点：低高块（垂直方向高频子带）具有行稀疏性，高低块（水平方向高频子带）具有列稀疏性，因此本文在图像恢复的过程中对低高块逐行、高低块逐列及高高块（对角方向高频子带）整体处理，利用SAMP算法进行自适应重构图像。

（1）对N×N的图像进行一层小波分解，得到｛LL1，LH1，HL1，HH1｝4个小波子带系数，其大小记为×。

（3）利用SAMP算法对LH′1逐列进行重构得，对 HL′1逐行进行重构得，对 HH′1整体进行重构得，将L、、与LL1一起进行小波逆变换得到恢复的图像。

4 仿真结果

对256×256的Lena图像进行试验，选取小波函数bior4.4对图像进行一层小波分解，则＝128，分别取 M／＝0.1、0.2、0.3、0.4、0.5进行仿真。这里为简便起见，采用的测量矩阵为随机矩阵（在实际应用中，可以采用结构化测量矩阵［12］来代替随机矩阵），因此在仿真实验时，每次生成的测量矩阵均不相同，为更真实地重构图像，均运行多次取均值，峰值信噪比见表1所列。其中，I＿OMP代表基于单层小波变换的压缩感知算法，I＿SAMP代表本文的改进算法。

表1 算法性能比较 dB

图1 256×256图像在M／＝20%时的恢复图像

5 结束语

本文首先简要介绍了压缩感知理论和稀疏自适应追踪算法，在单层小波变换压缩感知的基础上，根据图像小波分解系数中低频子带的特点和高频子带的排列特征，提出了基于单层小波变换的自适应压缩感知改进算法，很好地解决了稀疏度未知的问题，仿真结果表明，本文算法取得了较好的效果，与单层小波变换的非自适应压缩感知算法相比，保证了重构图像效果，图像质量也得到很好的保证，PSNR相差不过2dB。

［1］ Donoho D.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52（4）：1289－1306.

［2］ Candès E.Compressive samplingg［C］／／Proceedings of the International Congress of Mathmaticians，Madrid，Panin，2006：1433－1452.

［3］ 张晶晶，方勇华，陈晓宁.基于小波的偏振图像融合算法及性能评价［J］.合肥工业大学学报：自然科学版，2009，32（7）：1101－1105.

［4］ 岑翼刚，陈晓方，岑丽辉，等.基于单层小波变换的压缩感知图像处理［J］.通信学报，2010，31（8A）：52－55.

［5］ Candès E，Romberg J，Tao T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transactions on Information Theory，2006，52（2）：489－509.

［6］ Figueiredo M，Nowak R，Wright S.Gradient projection for sparse reconstruction：application to compressed sensing and other inverse problems［J］.IEEE Journal of Selected Topics in Signal Processing，2007，1（4）：586－597.

［7］ Chen S B，Donoho D L，Saunders M A.Atomic decomposition by basic pursuit［J］.SIAM Journal on Scientific Computing，1998，20（1）：33－61.

［8］ Mallat S，Zhang Z.Matching pursuits with time－frequency dictionaries［J］.IEEE Transactions on Signal Processing，1993，41（12）：3397－3415.

［9］ Tropp J，Gilbert A.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2008，53（12）：4655－4666.

［10］ Needell D，Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit［J］.Foundations of Computational Mathematics，2009，9（3）：317－334.

［11］ Do T T，Lu Gan，Nguyen N，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing［C］／／Asilomar Conference on Signals，Systems，and Computers，Pacific Grove，California，2008：581－587.