分块子空间追踪算法

庄燕滨王化程

摘要：压缩传感理论是一种充分利用信号稀疏性或者可压缩性的全新信号采样理论。该理论表明，通过采集少量的信号测量值就能够实现可稀疏信号的精确重构。本文在研究现有经典重构算法的基础上，提出结合图像分块思想和回溯思想的分块子空间追踪算法（Block Subspace Pursuit， B_SP）用于压缩传感信号的重构。该算法以块结构获取图像，利用回溯过程实现支撑集的自适应筛选，最终实现图像信号的精确重构。实验结果表明，在相同测试条件下，该算法的重构效果无论从主观视觉上还是客观数据上都有不同程度的提高。

关键词：信号处理；压缩传感；稀疏表示；重构算法；匹配追踪

中图分类号：TP301.6文献标识码：A

1引言

在传统采样中，为了避免信号失真，采样频率不得低于信号带宽的2倍，这就是著名的香农（Shannon）采样定理。那么对于数字图像、视频数据的采样，如果按照香农定理采样必定会产生大量数据，数据的存储和传输将面临巨大挑战[1]。在2006年，由美国科学院院士D.Donoho和斯坦福大学的E.Candès提出的压缩传感（Compressive Sensing，CS）理论为解决这一问题带来了曙光。其核心思想是将压缩与采样过程合二为一，首先以随机投影方式采集稀疏信号的测量值，在采样的同时完成了信号的压缩，最终通过求解一个最优化问题由测量值重构出原始信号[2]。它突破了传统香农采样定理的限制，在信号采样的同时对数据进行适当的压缩，提高数据的使用效率，缓解了信号采样、处理、传输和存储过程中所面临的越来越大的压力，为信号获取与传输带来了革命性的进展。自从压缩传感理论提出以后就引起了信号领域相关研究人员广泛地关注，其突出的优点和广阔的应用前景使得它在信号处理领域展现出了旺盛的生命力。压缩传感理论为信号的采集提供了全新的视角，目前已被广泛应用于压缩成像、模拟/信息转换、信号采集、医学图像处理和压缩雷达成像等众多领域[3]。

信号重构算法作为压缩传感理论的核心内容，通过求解一个最优化问题从低维数据中最大程度地恢复原始高维数据，这对于信号的精确重构及采样过程中的准确性验证均具有重要意义[4]。本文将重构算法中的分块思想与回溯思想相结合，提出一种分块子空间追踪法（Block Subspace Pursuit， B_SP），实验结果表明，该算法能够显著地提高图像的重构质量、降低重构时间，因而具有良好的应用前景。2压缩传感与重构算法

4实验结果及分析

为了检验分块子空间追踪算法（B_SP）的正确性和有效性，使用MATLAB仿真软件对本文算法进行各项测试。采用像素为256×256的cameraman图像作为测试对象，并与OMP算法，SP算法，ROMP算法，CoSaMP算法进行对比。

实验中，采用离散轮廓波变换对图像进行稀疏化表示，能够有效捕捉图像的轮廓和边缘信息，计算复杂度较低，在高维图像重构质量上具有较大优势。测量矩阵选用分块广义轮换测量矩阵，编码时不用对整个图像进行测量，只需对每一块进行线性测量后即可进行后续的处理，不仅提高了测量效率，且能使重构图像的均方差更小。

图1给出了cameraman图像在采样率（M/N）为0.1，0.2，0.3，0.4，0.5时，得到B_SP算法的重构结果。

从五种不同采样率下得到cameraman（256×256）图像的重构效果可以看出，当采样率M/N=0.1时，仅仅能分清人物的基本轮廓，重构后图像模糊不堪。在低采样率下，分块重构思想割裂了块与块之间的相关性，块与块之间的重构图像会出现明显的“割裂”现象，严重影响了重构效果。当采样率不断地提高M/N=0.2，0.3时，这种想象会逐步地得到改善。当采样率提高到M/N=0.4，0.5时，块与块之间的“割裂”现象会明显消除，从直观视觉上来看，重构质量明显提高。当采样率M/N=0.5时，重构算法OMP，SP，StOMP，CoSaMP，ROMP，B_SP算法对cameraman（256×256）图像的重构效果对比。

由图2可以直观看出，在采样率同为M/N=0.5的情况下，B_SP算法的重构质量明显优于其他经典的匹配追踪系列算法，重构后图像的细节部分较为完整的呈现出来。从直观的视觉感觉上来说，cameraman的头部、远处建筑等重构效果都有很大程度的提高。

通过表1中七种算法在采样率为50%时，得到运行时间、峰值性噪比（PSNR）、匹配度相关参数的对比。统一选取cameraman（256×256）作为处理对象，在运行时间上，最快的是ROMP算法，最慢的是CoSaMP算法，这是因为算法运行过程中引入回溯的思想，耗时较长；在峰值信噪比方面，显然B_SP算法具有绝对优势，在处理对象的时候采用分块的思想，不仅可以减少重构算法运行过程中所需的存储量同时重构图像块更易实现；在匹配度方面，B_SP算法也是这几种算法中的最高值，达到了0.9999。

6结论

本文在研究了各种压缩传感经典重构算法的基础上，提出结合了分块和自适应筛选思想的B_SP算法，具有相对运行时间较短、重构质量高的特点。该算法以块结构获取图像，可以实现图像实时传输和提高计算速度。然后再采用子空间追踪算法对每一个图像块进行重构，该算法是一种两阶段的回溯性贪婪算法，沿用了匹配追踪算法一贯的原子选择准则，首先选择高度可靠的原子作为原始原子集，每次迭代的过程中选择K（稀疏度）个原子加入原始原子集，但也会删除同样数量的原子，不断更新原子集，数量始终保持为K个，当最后完成迭代时用K个原子进行稀疏逼近原始信号，实现对原子的最优化选择。实验结果表明，在相同的测试条件下，该算法的重构效果无论从主观视觉上还是客观数据上都得到了较为满意的结果，具有一定的应用前景。

参考文献

[1]李树涛，魏丹. 压缩传感综述[J]. 自动化学报， 2009， 35（11）：1369-1377.

[2]MENG J， LI H，HAN Z. Sparse event detection in wireless sensor networks using compressive sensing[C]. Information Sciences and Systems， 2009. CISS 2009. 43rd Annual Conference on， IEEE， 2009：181-185.

[3]高睿. 基于压缩传感的匹配追踪重建算法研究[D]. 北京： 北京交通大学硕士论文， 2009，

[4]傅迎华. 可压缩传感重构算法与近似 QR 分解[J]. 计算机应用， 2008， 28（9）：2300-2302.

[5]MALLAT S G，ZHANG Z. Matching pursuits with time-frequency dictionaries[J]. Signal Processing， IEEE Transactions on， 1993， 41（12）：3397-3415.

[6]RAUHUT H，SCHNASS K，VANDERGHEYNST P. Compressed sensing and redundant dictionaries[J]. Information Theory， IEEE Transactions on， 2008， 54（5）：2210-2219.

[7]范晓维， 刘哲，刘灿. 分块可压缩传感的图像重构模型[J]. 计算机工程与应用， 2009， 45（29）：153-155.

[8]DUARTE M F，DAVENPORT M A，TAKHAR D，LASKA J N，SUN T， KELLY K F，Baraniuk R G. Singlepixel imaging via compressive sampling[J]. Signal Processing Magazine， IEEE， 2008， 25（2）：83-91.

[9]李波， 谢杰镇，王博亮. 基于压缩传感理论的数据重建[J]. 计算机技术与发展， 2009， 19（5）：23-25.

[10]刘丹华， 石光明，周佳社. 一种冗余字典下的信号稀疏分解新方法 [J]. 西安电子科技大学学报， 2008， 35（2）：228-232.