张娜¹, 曹琨², 刘亚轩¹
1. 中国海洋大学 信息科学与工程学院, 山东 青岛 266100;
2. 河南牧业经济学院 信息与电子工程系, 河南 郑州 450044
收稿日期：2015-10-27
基金项目：山东省自然科学基金资助项目 (ZR2014FQ027);中央高校基本科研业务费专项资金资助项目 (201513015)。
作者简介：张娜 (1980-)，女，山东青岛人，中国海洋大学讲师，博士。

摘要：针对现有块分割压缩感知 (block compressive sensing，BCS) 算法的块效应问题，提出一种低复杂度、可消除块效应的新型块分割重构算法.在稀疏表达时，采用小波变换 (DWT) 代替离散余弦变换 (DCT)，改善图像细节分量；在测量时，依据分块图像频率特征对测量矩阵加权，提高图像质量；在重构时，采用正交匹配追踪 (orthogonal matching pursuit，OMP) 算法代替匹配追踪 (matching pursuit，MP) 算法，提高重构速度.仿真结果表明，所提出的算法可在保证重构速度的情况下，有效消除块效应，且不增加内存占用.
关键词：压缩感知小波变换正交匹配追踪算法测量矩阵块效应
New Compressive Sensing Algorithm Based on Block Segmentation
ZHANG Na¹, CAO Kun², LIU Ya-xuan¹
1. College of Information Science and Engineering, Ocean University of China, Qingdao 266100, China;
2. Department of Information and Electronic Engineering, Henan University of Animal Husbandry and Economy, Zhengzhou 450044, China
Corresponding author: ZHANG Na, E-mail: baiquanbaiquan@126.com
Abstract: To solve the blocking artifacts of prior block segment compressive sensing, a new reconstruction algorithm was proposed which could reduce the blocking artifacts at low complexity. When sparse representing, discrete wavelet transform (DWT) method was utilized instead of discrete cosine transform (DCT) to improve detail component of image. When measuring, the measurement matrix of each block was reweighted to improve the quality of image according to the difference frequency between each block. When reconstructing, the orthogonal matching pursuit (OMP) algorithm was used to speed up reconstruction rather than the matching pursuit (MP) algorithm. Simulation results demonstrated that the blocking artifacts could be effectively eliminated by the proposed algorithm without making any effects on reconstruction speed and memory requirement.
Key Words: compressive sensing (CS)wavelet transformorthogonal matching pursuit (OMP) algorithmmeasuring matrixblocking artifacts
在传统的图像采集压缩过程中，为了避免采集的图像出现失真，要求采样频率必须满足奈奎斯特采样定理.同时，在图像压缩的过程中，需先对图像进行变换，然后对变换后绝对值较大的系数进行压缩，或直接舍弃掉绝对值为零或者绝对值较小的系数.这种传统的压缩过程会造成采集到的大量数据无用而被舍弃.另外，传统的采样压缩方法在采集端数据运算量大，对传感器有很高的运算要求，在解压端的处理量比采样端要少得多.然而，在实际应用中，对图像进行采集和压缩的传感器往往运算能力较低，对图像解压的设备却运算能力很强.因此，在整个采样过程出现了一个巨大的矛盾.
近几年来，文献[1-3]提出了一种新型的压缩感知 (CS) 理论.该理论的核心思想是在采样的同时就对图像进行压缩，然后再根据重构算法对压缩后的图像进行重构.CS理论突破了奈奎斯特采样定理的瓶颈，当图像满足稀疏条件时，可以远低于Nyquist采样定理的频率进行采样，并且能够不失真地还原出原图像，同时降低了采集端的数据处理量，解决了采集端和解压端设备数据处理能力的矛盾.
为了解决解码端对高分辨率图像进行重构时对运算能力、储存能力要求高，以及重构时间长的问题，文献[4]提出块分割压缩感知技术 (BCS).该技术是将图像分成多个小块，然后分别对每个小块进行压缩感知处理.在解码端单独对每个小块进行解码，然后再将各个小块按照原有顺序排列起来就可以恢复出原有的图像.因为将图像分成小块后就不会出现由于图像过大导致解码端运算困难的问题，所以BCS可以很好地解决解码端运算量大、储存困难等问题.
但BCS同样存在缺陷，该理论通过将图像分块处理后重组完成图像的压缩重构.在重构时因为每个小块都互相独立，导致重构过程中忽略了各个小块之间的联系，致使重构出来的图像产生严重的块效应.但如果重构后通过滤波器处理消除块效应，会导致图像的边缘模糊.本文提出一种新型压缩感知算法，在BCS重构时就将块效应消除，使重构的图像质量能够大幅提升，并且不会对重构时间、重构运算量产生大的影响.
1 压缩感知理论1.1 传统压缩感知理论传统的采样压缩流程如图 1所示.
图 1(Fig. 1)

图 1 传统的采样压缩流程图Fig.1 Frame of traditional sampling and compression

CS理论^[5]与传统采样压缩完全不同，它是一种全局的采样形式，该理论中其采样和压缩过程是同时完成的，利用图像的稀疏性可以降低采样频率^[6].因为利用了稀疏性，CS理论的采样值并非原始信号，而是对信号在低维的投影值进行采样，如图 2所示.从数学角度分析，就是每个低维的投影值包含了原始信号中的少量信息.在重构时不能通过简单的解压、反变换得到原始信号，需要通过近似重构的方法对其进行重构，也就是让重构的信号与原信号在误差上小于所需要的值^[7].
图 2(Fig. 2)

图 2 CS理论的压缩感知流程图Fig.2 Frame of compressive sensing

CS理论的基本公式为

(1)

式中：f为采集的自然信号；Θ是测量矩阵；y为测量向量，也可以认为是压缩后的信号.假设f是一个N×1的向量信号，将其投影到大小为M×N的测量矩阵上，这样可得到M×1的测量结果.如果N远大于M，那么压缩后的信号大小就会远小于原信号，这样给信号的传输带来了极大的方便.
从数学角度来看，式 (1) 是欠定方程，在解码端无法恢复出原始信号.但如果该信号是稀疏信号，即信号中只存在有限个大系数，其余小系数都可以近似看成零时，该方程式可以有解.为了分析稀疏性，将信号表示为

(2)

式中：φ_t为原始信号的稀疏基；x_t为稀疏导数.将式 (2) 代入式 (1) 中，可得

(3)

式中：Ω=Θφ，称为传感矩阵.在解压端，利用传感矩阵和y可以恢复出原始信号.但是由于M远小于N，因此想要解其逆问题必须要求信号满足绝对稀疏性.Candes等^[2]提出如果能够严格地满足稀疏条件，则可以无失真地恢复出原始信号，但是在实际情况中很难严格满足稀疏条件.因此一般情况下都需要选择合适的稀疏基，以保证信号能够最大限度地满足稀疏条件.
CS理论中信号的重构算法是该理论的核心内容.重构过程是指从长度为M(M远小于N) 的测量向量y中重构出长度为N的原始信号的过程.当传感矩阵满足受限等距特性 (RIP) 准则时，CS理论可以通过先求解稀疏系数，然后利用最优化求解的方法从长度为M的测量向量中恢复出原始信号.
1.2 块分割压缩感知理论由于CS理论重构过程中需要用到迭代算法，如果待重构信号维度很高，在采集端需要非常大的硬件存储空间，在重构时需要大量的运算，从而耗费很久的时间，对于需要迅速将结果回馈给传感器的实时应用，CS理论不能满足要求.后来发展出现的块分割压缩感知 (BCS)^[8]技术可以很好地解决这些问题，该技术主要用来处理自然图像.BCS^[9]的核心思想是把原始图像分成多个单独的小块，然后对每一个小块进行独立的CS操作.
假设一幅图像一共有N=p×q个像素点，运用BSC理论时，首先将图像分成若干个B×B的小块图像，对每个小块图像进行单独的CS处理，经过CS处理后的测量值可以表示为

(4)

式中：φ_B是一个n_B×B²的正交高斯随机矩阵，即该矩阵中每一个元素都独立地满足均值为零及方差等于1/n_B的正态分布，其中.因此很容易得到对整幅图像进行采样时所需要的矩阵：

(5)

在BCS中，只需保存一个大小为n_B×B²的矩阵即可，无需像CS一样保存一个大小为M×N的矩阵.当B减小时，储存的矩阵所占的内存更小，处理速度也更快，但图像质量会有一定的影响；当B增大时计算量会增大，同时占用的储存空间也会增加，但是图像质量会提高.因此，必须找到一个合适的B值^[10].
2 两种稀疏表示下的重构效果比较为了探索块效应产生的原因，分别采用DCT^[11]和DWT对图像进行处理，然后利用OMP算法进行重构.图 3为待处理的原始图像，其分辨率为256×256.
图 3(Fig. 3)

图 3 原始图像Fig.3 Original image

将图像分块，图像块的分辨率分别为16×16，32×32及64×64，采用0.8的采样率，通过对比三种不同分块分辨率下DCT和DWT重构图像的信噪比和重构时间，分析两种变换对于分块重构的影响.实验结果如图 4所示.
图 4(Fig. 4)

图 4 采样率0.8下两种变换重构图像比较Fig.4 Comparison of reconstructed images with DCT and DWT at 0.8 sampling rate (a)—DCT, 分辨率16×16；(b)—DWT, 分辨率16×16; (c)—DCT, 分辨率32×32；(d)—DWT, 分辨率32×32; (e)—DCT, 分辨率64×64；(f)—DWT, 分辨率64×64.

由图 4可以很直观地看出DCT重构出来的图像质量较差，块效应明显，完全不能使用；而DWT重构后的图像没有块效应，在视觉效果上更好.在三种不同块分辨率情况下，DWT重构效果均远优于DCT重构.统计采样率为0.8时，DCT和DWT重构图像的信噪比和重构时间如表 1和表 2所示.
表 1(Table 1)

表 1 重构图像的信噪比比较Table 1 Comparison of SNR for reconstructed images dB 块大小 DCT DWT 16×16 10.551 4 40.243 5 32×32 11.699 3 41.465 5 64×64 15.114 1 43.022 8

表 1 重构图像的信噪比比较 Table 1 Comparison of SNR for reconstructed images

表 2(Table 2)

表 2 重构时间比较Table 2 Comparison of reconstruction time s 块大小 DCT DWT 16×16 29.292 3 5.392 5 32×32 424.330 5 42.514 5 64×64 13 803.544 6 776.128 0

表 2 重构时间比较 Table 2 Comparison of reconstruction time

分析表 1的数据可知，在采样率相同的情况下，采用同样的重构算法，在分割图像块分辨率相同时，DWT重构后的图像信噪比很高，噪声很小；而DCT的信噪比相当低，图像噪声非常大，无法在实际中使用.
由表 2可知，在同样的采样率下，分块数目相同时，DCT的重构时间要比DWT的重构时间长很多，并且图像块分辨率越大，DWT在重构时间上优势越明显.综合上述分析，相比较DCT，DWT性能更好，重构后信噪比较高，重构时间较短，能更好地运用在实际中.
3 测量矩阵加权的匹配追踪算法在传统的BCS重构过程中，每个小块重构时所使用的测量矩阵都是一样的.根据人眼的视觉特性，人眼对于整幅图像中的低频分量有着很强的敏感性.此外，根据图像质量的评价标准，重建后的图像质量与中低频分量在重构时的误差值有着直接联系.因此可以通过对每个观测矩阵中的各个元素进行加权处理，使低频分量的比重增大，然后利用加权后的观测矩阵对图像进行重构，提高图像质量.
该方法的主要思想是低频分量权值较大，高频分量权值较小.因此在重构后的图像中中低频分量占有较高的精度；高频分量所占用的权值比较小，重构出的图像中高频分量的精度就会较低.由于中低频分量对图像质量产生的影响更大，因此这样重构出来的图像质量较好.
该方法是通过牺牲高频分量的精度来增加低频分量的精度，权值的主要计算式为

(6)

式中：i, j=0, 1, …n_B-1；q是常数.由式 (6) 可知，权值是根据行和列的增加而不断地减小，如果i和j代表图像中每个元素的位置，那么由式 (6) 可知权值在中低频分量时值比较大，在高频分量时值比较小.对测量矩阵进行加权：

(7)

将其作为新的观测矩阵对图像进行重构，这样就可以增加中低频分量的权值，减少高频分量的权值，提高图像质量.
4 仿真及实验结果首先观察使用DWT时，不同采样率和不同的分块大小对重构后图像质量的影响.在块分辨率为32×32时，采样率不同时的重构图像见图 5.
图 5(Fig. 5)

图 5 DWT的重构图像Fig.5 Reconstructed images with DWT (a)—采样率0.8；(b)—采样率0.6; (c)—采样率0.4；(d)—采样率0.2.

由图 5可知，即使使用很小的采样率，重构出来的图像也没有块效应.不同采样率下DWT变换时的重构性能如表 3所示.
由表 3可以看出，当块分辨率一定时，重构时间和信噪比都随着采样率的增加而增加，其中重构时间增加幅度较大.为了平衡二者，在实际操作时需要选择一个合适的采样率.
表 3(Table 3)

表 3 不同采样率下DWT的重构性能Table 3 Reconstruction performance with DWT under different sampling rates 采样率 信噪比/dB 重构时间/s 0.8 41.465 5 42.514 5 0.6 38.146 6 15.738 9 0.4 35.490 4 3.751 2 0.2 29.668 5 1.167 6

表 3 不同采样率下DWT的重构性能 Table 3 Reconstruction performance with DWT under different sampling rates

采样率为0.6，块分辨率对图像质量的影响如图 6所示.由图 6可知，在采样率不变的情况下，改变块分辨率的大小对图像质量影响较小.即使图像分的块数很多，重构出来的图像也没有块效应.不同块分辨率下的重构性能如表 4所示.
图 6(Fig. 6)

图 6 块分辨率对DWT图像质量的影响Fig.6 Effect of block resolution on reconstructed images with DWT (a)—分辨率16×16；(b)—分辨率32×32; (c)—分辨率64×64.

表 4(Table 4)

表 4 不同块分辨率下DWT的重构性能Table 4 Reconstruction performance with DWT under different block resolution 块分辨率 信噪比/dB 重构时间/s 16×16 36.828 0 3.496 9 32×32 38.146 6 15.738 9 64×64 39.160 7 328.816 9

表 4 不同块分辨率下DWT的重构性能 Table 4 Reconstruction performance with DWT under different block resolution

由表 4可知，当块分辨率增加，即分块数量减少时，所需要的重构时间会大幅增加，同时重构出来的图像信噪比也会小幅增加.
综合上述分析可知，当运用DWT对图像进行处理时，随着分块数量的减少和采样率的增加，重构图像的信噪比和重构时间都会增加.也就是说想要重构后的图像有更好的质量，就必须花费大量的重构时间.因此，在实际应用中，必须找到适合当时情况的采样率和分块大小.
采样率为0.8时，块分辨率对DCT重构图像质量的影响如图 7所示.
图 7(Fig. 7)

图 7 块分辨率对DCT重构图像质量的影响Fig.7 Effect of block resolution on reconstructed images with DCT (a)—分辨率64×64；(b)—分辨率128×128; (c)—分辨率256×256.

由图 7可知，DCT重构的图像质量较差.在实验中采用了较大的采样率，但重构的图像还是有较为明显的块效应.只有在图 7c中，图像从直观上看质量较好.但是该图像只是将原始图像分成四块进行BCS处理，这种分块方式在实际应用中并不适用.不同块分辨率下DCT的重构性能如表 5所示.
表 5(Table 5)

表 5 不同块分辨率下DCT的重构性能Table 5 Reconstruction performance with DCT under different block resolution 块分辨率 信噪比/dB 重构时间/s 64×64 15.114 1 13 803.554 6 128×128 31.557 6 37 447.266 9 256×256 36.523 0 79 749.695 0

表 5 不同块分辨率下DCT的重构性能 Table 5 Reconstruction performance with DCT under different block resolution

由表 5可知，运用DCT得到的重构图像质量较差，且重构时间很长.在实际情况中，这么大的重构时间无法满足要求.
在相同块分辨率下，分析图像采样率对重构图像质量的影响.当块分辨率为128×128时，结果如图 8所示.
图 8(Fig. 8)

图 8 图像采样率对DCT重构图像质量的影响Fig.8 Effect of sampling rate on reconstructed images with DCT (a)—采样率0.8；(b)—采样率0.6; (c)—采样率0.4；(d)—采样率0.2.

由图 8可知，随着采样率的降低，重构图像的质量下降十分明显，并且块效应也越来越明显.这组仿真中只将图像分为16块，分块的数量很少，但是重构图像的质量已经不能达到要求.不同采样率下DCT的重构性能如表 6所示.
表 6(Table 6)

表 6 不同采样率下DCT的重构性能Table 6 Reconstruction performance with DCT under different sampling rates 采样率 信噪比/dB 重构时间/s 0.2 9.925 7 6 604.456 2 0.4 23.063 5 13 686.866 6 0.6 28.149 7 26 558.156 0 0.8 31.557 6 37 447.266 9

表 6 不同采样率下DCT的重构性能 Table 6 Reconstruction performance with DCT under different sampling rates

由表 6可知，提高采样率可以使重构图像的质量提高，但是会使重构时间延长.上面采用了较大的分块进行试验，但是重构出的图像质量仍然非常低，基本不能使用.另外，通过前面的分析可知，当分块的大小增加时，图像重构的质量也会提高.因此如果想要利用DCT处理得到较高质量的图片，就不得不保证很高的采样率，同时还要减少分块的数量.但是这样就会导致花费大量的重构时间来保证高采样率以及对较大的分块进行重构.这在实际运用中是不会被采用的.
通过对以上两种稀疏表示得到的重构图像进行深入分析，可以看出DWT处理后的图像在各个方面都要优于DCT处理后的图像.DWT处理后的图像能够消除块效应，这正是改良BCS重构算法的原因.同时，DWT处理后的图像比DCT处理后的图像信噪比高很多，采用DWT对图像重构所用的时间比采用DCT所需要的时间少很多.因此本文利用DWT代替DCT达到改善重构效果的目的.
下面分析比较对测量矩阵加权后得到的重构图像和不加权时得到的重构图像.便于直观分析，本文采用噪声较大的DCT对原图像进行处理，然后对测量矩阵进行加权，最后通过OMP算法得到重构图像.采样率为0.8时，实验结果如图 9、图 10所示.
图 9(Fig. 9)

图 9 不加权重构图像Fig.9 Image reconstructed by unweighted algorithm

图 10(Fig. 10)

图 10 加权重构图像Fig.10 Image reconstructed by reweighted algorithm

为了便于分析，实验中使用了噪声很大的DCT，并且将每一块图像都分得很小，这样重构出来的图像如图 9所示.在图中可以直观地看到噪声十分明显，图像质量很差.对测量矩阵加权后得到的重构图像如图 10所示.可以看到加权后得到的重构图像在图像质量和主观感觉上都有了明显的提高，虽然还是存在一些噪声，但是相比图 9中的图像，噪声减小了很多，图像的信噪比也有了很大的提升.经测量，不加权重构图像信噪比为18.606 1 dB，加权重构图像信噪比为21.285 9 dB.在重构时间方面，不加权耗时14.234 1 s，加权后耗时14.231 5 s，对测量矩阵加权的重构方法在重构时间上几乎没有变化.由以上分析可以看出，通过对测量矩阵加权，可以在不影响重构时间的前提下，提高重构图像的去噪能力.
由以上两个方面的实验结果来看，本文所提出的BCS算法性能优于原有的分块压缩感知算法.首先利用DWT代替原有的DCT，这样可以保证在图像质量提高的前提下，减少重构时间，并且可以降低采样率.同时，利用DWT消除了BCS重构中的块效应.其次，对测量矩阵加权，采用OMP算法对图像进行重构，这样可以进一步提高图像质量.由此来看，本文提出的重构算法在自然图像的重构上有着很大的优势.这种算法能够显著地减少重构时间，并且还可以在保证图像质量不下降的前提下极大地降低采样率.
5 结论针对现有块分割压缩感知算法的块效应问题，本文提出一种新型块分割压缩感知算法.该算法不仅具有传统分块压缩感知算法的优点，还能有效消除块效应.仿真结果表明，采用本文算法重构的图像，即使在采样率和分辨率较低的情况下，也无明显的块效应，且在信噪比和重构时间方面也有一定改善.
参考文献

[1]	Candes E J, Romberg J, Tao T. Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory, 2004, 52(2): 489–509.
[2]	Candes E J, Romberg J K, Tao T. Stable signal recovery from incomplete and inaccurate measurements[J].Communications on Pure & Applied Mathematics, 2006, 59(8): 1207–1223.
[3]	Donoho D L. Compressed sensing[J].IEEE Transactions on Information Theory, 2006, 52(4): 1289–1306.DOI:10.1109/TIT.2006.871582
[4]	Lu G.Block compressed sensing of natural images[C]// International Conference on Digital Signal Processing.Cardiff:IEEE, 2007:403-406.
[5]	Rauhut H, Schnass K, Vandergheynst P. Compressed sensing and redundant dictionaries[J].IEEE Transactions on Information Theory, 2008, 54(5): 2210–2219.DOI:10.1109/TIT.2008.920190
[6]	Yang Y, Au O C, Fang L, et al.Reweighted compressive sampling for image compression[C]// Picture Coding Symposium.Chicago:IEEE, 2009:1-4.
[7]	Stankovic L, Stankovic S, Amin M. Missing samples analysis in signals for applications to L-estimation and compressive sensing[J].Signal Processing, 2014, 94(1): 401–408.
[8]	Gutiérrez I M, Fuentes H A. Overlapped block-based compressive sensing imaging on mobile handset devices[J].Revista Facultad de Ingeniería Universidad de Antioquia, 2014(70): 173–184.
[9]	李然, 干宗良, 朱秀昌. 基于分块压缩感知的图像全局重构模型[J].信号处理, 2012, 28(10): 1416–1422. ( Li Ran, Gan Zong-liang, Zhu Xiu-chang. A global reconstruction model of images using block compressed sensing[J].Signal Processing, 2012, 28(10): 1416–1422.DOI:10.3969/j.issn.1003-0530.2012.10.009)
[10]	罗琦, 魏倩, 缪昕杰. 基于压缩感知思想的图像分块压缩与重构方法[J].中国科学:信息科学, 2014, 44(8): 1036–1047. ( Luo Qi, Wei Qian, Miao Xin-jie. Blocked image compression and reconstruction algorithm based on compressed sensing[J].Scientia Sinica Informationis, 2014, 44(8): 1036–1047.)
[11]	Kapoor A, Dhir R. Image compression using fast 2-D DCT technique[J].International Journal on Computer Science & Engineering, 2011, 3(6): 2415–2419.