基于多尺度的自适应采样图像分块压缩感知算法*

殷长涛，文志强，胡骏飞

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

基于多尺度的自适应采样图像分块压缩感知算法*

殷长涛，文志强，胡骏飞

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

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

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

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个图像块像素值所组成的向量，则对应的采样值为：

yi=ΦBxi

(1)

(2)

由于Φ是一个对角矩阵，因此只需要存储大小为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)依次执行下式：

(3)

(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的全差分值为：

(5)

图1 TV值算法示意图

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

(1)第一部分图像块为1≤s

(2)第二部分图像块为s=M/B且1≤t

(3)第三部分图像块为1≤s

(4)第四部分图像块为1≤s

(6)

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

(7)

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

(8)

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

2.1 多尺度自适应采样

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

y=Φ′Ωx

(9)

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

(10)

(11)

其中1≤l≤L。

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

Sl=WlS′

(12)

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

(13)

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

(14)

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

Wl=16L-l+1

(15)

2.2 多尺度重构

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

forl++ (1≤l≤L)

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

forj++

endfor

endfor

endfor

k=0

do

forl++ (1≤l≤L)

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

forj++

endfor

endfor

endfor

forl++ (1≤l≤L)

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

forj++

endfor

endfor

endfor

k=k+1

enddo

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

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的性能提升。

表1 lena图像上实验结果比较 (dB)

表2 peppers图像上实验结果比较 (dB)

表3 goldhill图像上实验结果比较 (dB)

表4是当采样率为0.3时对lena图的重构时间比较。

表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.

[8] SCHNITER P, POTTER L C, ZINIEL J. Fast Bayesian matching pursuit: model uncertainty and parameter estimation for sparse linear models[J]. IEEE Transactions on Signal Processing, 2009:399-405.

[9] DABHOLE S H, GUNDALE V A, POTGIETER J. An efficient modified structure of CDF 9/7 Wavelet based on adaptive lifting with SPIHT for lossy to lossless image compression[C]. International Conference on Signal Processing Image Processing & Pattern Recognition, IEEE, 2013,17(5):269-274.

Block-based image compressive sensing algorithm with adaptive sampling based on multiscale

Yin Changtao, Wen Zhiqiang, Hu Junfei

(Key Laboratory of Intelligent Information Perception and Processing Technology (Hunan Province), Zhuzhou 412007, China)

The block based compressive sensing algorithm can be applied to the image signal processing, and the image can be reconstructed quickly by using the method of smoothed projected landweber. Due to the algorithm display a poor reconstruction quality under the low sampling rate, someone propose the algorithm based on the total variation, which is called TV algorithm. Despite a certain improvement was made on the reconstruction effect, the algorithm decreased the operation speed on the other hand. In view of the deficiency of the two algorithms, we propose an adaptive sampling block based compressive sensing algorithm based on multiple scales. According to the difference in wavelet decomposition layers on the reconstruction results, we adaptively allocat each layer of different sampling rate, and apply the Smoothed Projected Landweber algorithm to each layer of each sub zone block. Experimental results reveal that the proposed algorithm improves the reconstruction quality by one to three dB, and the method is superior to the total variation method in the reconstruction speed .

compressed sensing; multiscale; wavelet transform; adaptive sampling; image blocking

国家自然科学基金(61170102)

TP391

A

10.19358/j.issn.1674- 7720.2016.24.013

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

2016-07-23)

殷长涛(1990-)，男，在读硕士研究生，主要研究方向：图像处理。

文志强(1973-)，男，教授，主要研究方向：图像处理、模式识别。

胡骏飞(1990-)，男，在读硕士研究生，主要研究方向：图像处理。