殷长涛，文志强，胡骏飞

　　（智能信息感知及处理技术湖南省重点实验室, 湖南 株洲 412007）

       摘要：基于分块的压缩感知算法适用于图像信号的处理，通过平滑迭代阈值投影法可以快速重构图像，但存在低采样率下重构图像质量较差的缺点。基于全变差分的分块压缩感知算法，在一定程度上能提升重构效果，但降低了运算速度。针对以上算法的不足，提出基于多尺度的自适应采样图像分块压缩感知算法。根据小波分解后不同层对重构结果影响所占权重不同的特性，自适应分配给每一层不同的采样率，并在重构时将平滑迭代阈值投影法应用到每一层的每一个子带的分块上。实验结果表明，与传统的迭代阈值投影法相比在重构质量上提高了1~3 dB，在重构速度上与迭代阈值投影法相当并优于全变差分法。

　　关键词：压缩感知；多尺度；小波变换；自适应采样；图像分块

　　中图分类号：TP391文献标识码：ADOI： 10.19358/j.issn.1674-7720.2016.24.013

　　引用格式：殷长涛，文志强，胡骏飞. 基于多尺度的自适应采样图像分块压缩感知算法［J］.微型机与应用，2016,35（24）：42-45，49.

0引言

　　压缩感知（Compresssive Sensing,CS）［1］最早是由DONOHO D等人提出的一种新的信号压缩采样方法。利用数据的冗余性，把原始信号通过观测矩阵投影到低维空间，如果原始信号稀疏或是可压缩的，则可以通过观测值，利用凸优化的方法很好地重构出原始信号。

　　目前已有研究者将CS理论运用于图像数据的获取，但是实践中发现，直接针对整幅图像数据进行压缩感知时所需要的观测矩阵会占用很大的存储空间，重构时运算量过大，并且效果不理想。针对压缩感知这个缺点，GAN L等人提出了分块压缩感知（Block Compressed Sensing，BCS）［2］理论，该理论首先将图像分割成相同大小的图像块，再对每一小块分别进行采样重构。MUN S等提出了分块迭代阈值投影算法（BCSSPL）［3］,该算法通过将BCS理论与Landweber迭代法［4］相结合，并且加入了维纳滤波过程，在加快了重构速度的同时，也消除了分块采样所带来的重构结构的快效应，很大程度上提高了分块压缩感知的可用性。蔡旭等人在文献［3］的基础上提出了基于全变差分自适应采样率分块压缩感知算法（TVBCSSPL）［5］,根据图像块全变差分的值判断其纹理复杂程度，进而自适应地分配采样率。该算法在一定程度上提高了在低采样率下的重构精度，但算法比较复杂，需要较长的运算时间。本文提出了一种改进的基于多尺度采样的分块压缩感知算法，并且利用基于光滑Landweber投影法作为重构算法，通过实验证明提出的算法不仅可以保证大多数图的重构精度优于分块迭代阈值投影算法，而且重构速度也优于基于全变差分的自适应采样率分块压缩感知算法。

1相关理论

　　1.1分块压缩感知（BCS）

　　GAN L等人在文献［2］中将基于分块图像的测量引入压缩感知理论，以降低计算量和存储器的负担。假设要对一幅Ιρ×Ic大小的图像进行采样，图像的总像素数用N=Ir×IC来表示。上分块压缩感知算法将图像分成了很多B×B大小的图像块，并对这些小块进行相同的采样操作。令Xi代表第i个图像块像素值所组成的向量，则对应的采样值为：

　　由于Φ是一个对角矩阵，因此只需要存储大小为nB×B2的ΦB，而不是存储大小为n×N的矩阵，减轻了存储器的负担，增加了算法的实时性。

　　1.2基于Landweber投影的重构方法（SPL）

　　FOWLER J E等人在2009年提出了基于Landweber投影的块压缩感知重构算法。算法将解决数学上反问题的Landweber迭代法［4］应用于图像重构过程中，提高了算法效率和重构的精度。算法步骤如下：

　　(1)如式（1）所示分块采样后，分别得到了各个图像块的采样值，将第i个图像块的采样值记为yi，并假设重构图像X(k)=Φ-1Y，令迭代次数k=0。

　　（2）对第k次迭代重构的图像进行维纳滤波，X(k)=Wienner(X(k))

　　（3）将第k次迭代得到的第j个图像块xj(k)依次执行下式：

　　(j)(k)=(k)j+ΦTB(y(k)j-ΦBx(k)j)（3）

　　(4)将第k次迭代得到的重构图像(k)投影到Ψ域，得到(k)=Ψ(k)，该矩阵为稀疏矩阵，并对(k)做阈值处理。

　　(5)将(k)作ΨT(k)变换得到时域中重构图像(k),并对重构图像块(k)j执行下式：

　　X(k+1)j=(k)j+ΦTB(y(k)j-ΦB(k)j)（4）

　　(6)若两次迭代返回的均方根误差之差小于0.000 1，则终止迭代，否则返回步骤（2）继续迭代。

　　由于该算法对图像进行了较多的平滑处理，因此导致图像细节变得模糊，这种现象在采样率低的情况下十分明显。

　　1.3基于全变差分的自适应采样率分块压缩感知(TV-BCS-PL)

　　针对以上算法的不足，蔡旭等人提出了基于全变差分自适应采样率分块压缩感知［5］,该算法根据图像块的全变差分值来度量其纹理的复杂程度，并根据不同的全变差分值对采样率进行自适应分配。具体算法如下。

　　假定原图像大小为M×N，分块图像大小为B×B，则整个图像中有num=M×N/B2个图像块，用I来表示整幅图像，K表示当前子块，并用(s,t)坐标表示图像块在图像中的位置，Kij代表图像块中的每个像素，初始采样率为R，则图像块K的全差分值为：

　　TVl1l2=∑DhK2+Dv K2(5)

　　式中DhK代表水平方向的前像素与后像素的差值，DvK代表下方像素与本像素的差值，并且将整幅图像分为四部分，每部分的DhK和DvK的计算方法如图1所示。

　　(1）第一部分图像块为1≤s<M/B且1≤t<N/B的块:

　　根据式（6）计算出每个图像块的TV值，并利用下式自适应分配对各块的采样率：

　　其中μ为采样率控制因子，文献［5］中将其设为0.35，代表根据TV值分配采样率的权重占总采样率的35%。为了防止过采样或欠采样，对ri值进行阈值处理：

　　文献［5］中取γ为1.9用来控制最小采样率，并且为了保证总采样数保持不变，令K=R/ri，对采样率的分配进行多次迭代直到|K－1|<0.001，跳出迭代后得到的ri就是每个子块对应的采样率。

2基于多尺度自适应采样的块压缩感知算法

　　2.1多尺度自适应采样

　　对于基于平滑投影的多尺度分块压缩感知来说，采样算子A分为两部分，第一部分是多尺度变换Ω（例如离散小波变换等）和多尺度分块观测矩阵Φ′,所以A=Φ′Ω,于是可以通过下式对整幅图像采样：

　　y=Φ′Ωx（9）

　　假设Ω对图像进行了L层小波分解，因此Φ′是L个不同的基于块的采样算子分别与L层中每一层小波分解对应。x的小波变换可表示为：

　　=Ωx（10）

　　的第l层小波分解中子带s被分割为Bl×Bl的小块，并用一个与之大小对应的Φ观测矩阵对其采样。假设用l,s,j表示小波分解中第l层的子带s中的第j个子块，那么采样过程可以用下式表示：

　　yl,s,j=Φll,s,j（11）

　　其中1≤l≤L。

　　对图像采样过程中的采样率进行了自适应分配。对低频部分进行全部采样，即s0=1,对于其他层的采样率可用sl表示并可由（12）式求出：

　　Sl=WlS′（12）

　　由此可得图像总采样率为：

　　通过将总采样率S和小波分解每层所占比重wl带入式（13）求出S′,通过S′可以求出每层分配到的采样率。然而求出的采样率有可能有一个或多个Sl>1，因此需调整算法使得对于所有的Sl都必须符合Sl≤1。具体做法是，假设Sl>1，则令Sl=1，相应的（13）式需要调整为：

　　再根据式(14)求出其他层采样率，如果求出的结果中依然有Sl>1则可以重新迭代上述过程，直至所有Sl都小于等于1。通过实验对比发现对于每层所占比重采用式(15)得出的结果最好：

　　Wl=16L-l+1(15)

　　2.2多尺度重构

　　多尺度重构采用的重构算法包括对于整幅图像利用维纳滤波器进行平滑的过程和为达到图像更加稀疏的效果将整幅图像映射到稀疏域的阈值化处理过程。在这两个操作之间是Landweber迭代过程，用x←x+ΦT(y－Φx)来表示，其中Φ是观测矩阵，下面的伪代码描述了如何将多尺度变换加入基于平滑投影的Landweber算法中。

　　function =MultiScale-BCS (y,{Φl,1≤l≤L},Ψ,Ω)

　　forl++ (1≤l≤L)

　　fors++ (s∈{H,V,D})

　　for  j++

　　(0)l,s,j=ΦTlyl,s,j

　　endfor

　　endfor

　　endfor

　　k=0

　　do

　　x(k)=Ω-1(k)

　　(k)=Wiener(x(k))

　　^k=Ω(k)

　　forl++ (1≤l≤L)

　　fors++(s∈{H,V,D})

　　for  j++

　　^^(k)l,s,j=^(k)l,s,j+ΦTl(yl,s,j－Φl^(k)l,s,j)

　　x︶︶(k)=ΨΩ-1^^(k)

　　x︶(k)=Threshold(x︶︶(k))

　　(k)=ΩΨ-1x︶(k)

　　endfor

　　endfor

　　endfor

　　forl++ (1≤l≤L)

　　fors++ (s∈{H,V,D})

　　for  j++

　　endfor

　　endfor

　　endfor

　　(k)l,s,j=(k)l,s,j+ΦTl(yl,s,j－Φl(k)l,s,j)

　　D(k+1)=(k+1)－^^(k)2

　　k=k+1

　　enddo

　　While(|D(k)－D(k-1)|>10－2)

　　=(k)

　　endwhile

3实验结果与比较

　　3.1实验环境

　　实验平台是搭载了双核2.3 GHz CPU和4 GB内存的笔记本电脑，实验环境为Windows 7操作系统，并在MATLAB 2014a上运行。算法使用了小波工具箱和l1magic工具箱。

　　3.2实验结果

　　采用三张大小为512×512的图像处理领域常用灰度图像来验证所提出算法的性能。实验将提出的算法分别对比三种算法在不同采样率下重构图像的质量（PSNR），对比算法包括基于平滑投影迭代分块压缩感知算法（BCSSPL）［6］、基于全变差分的压缩感知算法（TV）［7］以及一个多尺度变换的衍生算法GPSR［8］。所提出算法与BCSSPL算法均采用双树离散小波变换作为稀疏变换。其中本文算法采用3层离散小波变换，并采用9/7双正交小波［9］作为采样域的变换。对于小波变换的第l层，每个大小为B×B的分块被分别采样。实验采用分块大小为16、32以及64，分别对应层为l=1,2,3。传统的BCSSPL算法和TV算法采用分块大小为32。

　　表1、表2和表3分别是在三种不同图像下的重构效果比较。通过以上实验结果可以看出，在多数情况下与传统的BCSSPL相比，本文提出的算法重构结果的峰值信噪比要高出1~3 dB，并且在低采样率时提出算法相对于TV算法有1~2 dB的性能提升。

　　表4是当采样率为0.3时对lena图的重构时间比较。根据表4可知，本文提出的算法比BCSSPL快了17 s，而MSGPSR和TV两种算法则相当耗时。其中TV算法尽管采用了快速SRM采样算子，依然将近要用2个小时才可以完成对图像的重建。

4总结

　　本文将多尺度分解应用于平滑投影的Landweber分块压缩感知算法并在小波域进行采样。提出的重构算法是将BCSSPL算法应用到小波分解后对每一层上每个子带的分块再分别重构每一个分块。实验结果显示，在重构效果的对比上，提出的算法比原始BCSSLP算法在时域上进行采样和重构时，重构质量普遍要高1~3 db。由此得出，提出的算法在提高图像重构效果的同时，依旧保持了BCSSPL算法的运算速度。基于分块的压缩感知算法的优点在于降低了采样和重构算法的计算复杂度，同时提高了算法的实时性。提出的算法在小波域对图像进行分块的采样和重构，虽然保留了BCS算法的优点，但是在对小波分解的观测过程中，A=Φ′Ω，小波变换破坏了观测矩阵Φ′分块对角的结构特性，产生了一个稠密的A矩阵，这就给压缩感知在硬件实现上带来了很大的挑战。因此，提出算法在提升重构效果的同时，也带了算法硬件实现上的挑战，如何解决观测矩阵结构问题是之后工作的重点。

　　参考文献

　　［1］ DONOHO D. Compressed sensing ［J］ . IEEE Transactions on Information Theory, 2006,52(4):1289 1306.

　　［2］ GAN L. Block compressed sensing of natural images ［C］. 2007 15th International Conference on Digital Signal Processing,IEEE,2007:403 406.

　　［3］ MUN S, FOWLER J E . Block compressed sensing of natural images［C］. 2009 16th IEEE International Conference on Image Processing (ICIP),IEEE,2009:30213024.

　　［4］ 王兵贤, 胡康秀, 王泽文. 反问题的Landweber迭代法及其应用研究进展［J］. 计算机应用研究, 2013, 30(9):25832586.

　　［5］ 蔡旭, 谢正光, 黄宏伟,等. 一种自适应低采样率图像分块压缩感知算法［J］. 小型微型计算机系统, 2016,37(3):612 616.

　　［6］ MUN S, FOWLER J E. Block compressed sensing of images using directional transforms［C］. IEEE International Conference on Image Processing, 2009:3021 3024.

　　［7］ CANDS E J, ROMBERG J K, TAO T. Stable signal recovery from incomplete and inaccurate measurements［J］. Communications on Pure & Applied Mathematics, 2005, 19(5):410 412.