周四望,刘龙康

(湖南大学 信息科学与工程学院,湖南 长沙 410082)

基于小波变换的图像零树压缩感知方法*

周四望†,刘龙康

(湖南大学 信息科学与工程学院,湖南 长沙 410082)

稀疏性是压缩感知的前提，然而，自然图像通常不是稀疏的，因此对图像直接应用压缩感知算法很难取得高压缩效率.针对图像信号，将编码思想融入压缩感知理论，提出一种简单有效的零树压缩感知方法.该方法先利用零树思想辅助压缩感知测量，在得到测量值的同时编码重要系数的位置；然后提出零树追踪重构算法，通过精确解码重要系数位置来重构原始图像小波系数，提高重构精度.实验结果表明，相比于现有匹配追踪算法和EZW算法，本文方法有更高的压缩比和更好的图像重构质量.

小波变换;图像处理;压缩感知;编码

小波变换是图像压缩的重要方法[1].当图像信号经由小波变换转换到小波域后，其小波域系数隐含多分辨的树结构，存在相关性.在图像的小波域系数中，如果父系数小于给定的阈值，则其子系数也很大概率小于此阈值，利用此相关性对小波系数做进一步的编码，可显著增加图像压缩性能.嵌入式小波零树编码(EZW)[2]是最经典的一种图像编码方法，通过设计正重要系数、负重要系数、孤立零和零树根，将小于阈值的父子小波系数组织成树结构，提高了图像压缩比.

Donoho等[3-5]认为，上述传统变换压缩方法鲁棒性差，而且压缩效率存在“自适应”的特点并且依赖信号本身的结构，进而提出了一种称为“压缩感知”的新理论，近年来吸引了越来越多研究人员的关注.设长度为N的信号x满足K-sparse特性，即x中仅有K(K≪N)个元素为非零，则可由M×N(M≪N)大小的测量矩阵φ将信号x投影到低维空间，得到测量值y：y=φx.通过求解最优化问题：min ‖x‖0s.t.φx=y即可以由φ和投影测量值y高概率地重构出原始信号，其中‖x‖0表示信号x的0范数.因为M远小于N，信号无需编码即被压缩.研究表明，上述最优化问题的求解可以转化为线性规划问题.Tropp等人[6]提出利用正交匹配追踪(OMP) 算法来重构信号，大大提高了计算的速度，且易于实现.OMP算法的本质是在K-sparse信号x中寻找关键的K个分量.其基本思想是比较测量矩阵φ的每一个列向量与测量值y的内积，每次追踪时确定1个关键分量的位置，并用最小二乘法求解此分量的值，直至找到K个关键的分量，从而重构出原始信号.Donoho等人[7-8]进一步提出了分段正交匹配追踪(StOMP)算法和压缩采样匹配追踪 (CoSaMP)算法，加快了图像重构的速度.

信号的稀疏性是实现OMP等压缩感知算法的前提.不幸的是，一般来说图像是非稀疏的二维信号，通常的做法是将图像转换为某种变换域，例如小波域，然后再做压缩感知测量[9-10].当图像转换为小波域后，幅值大的小波系数主要聚集在低频子带，而高频子带的小波系数幅值大多接近于零，具有近似稀疏的特点.图像经多级小波变换后，各子带的小波系数形成层次结构，呈现出父子对应关系.每个父系数有4个子系数；每个子系数像他们的父系数一样，又有4个子系数，依次类推.父子小波系数之间存在时空相关性，一般来说，如果父系数的幅值小，则子系数有很大概率也是小系数.Donoho等人[11]提出多尺度压缩感知 (MCS)算法，对图像小波域的低频子带采用线性传递，而对高频子带则按不同的变换级分别进行压缩感知测量，再利用OMP等算法重构原始图像.MCS算法不拘泥于经典压缩感知理论，它根据图像小波域子带的特征融合压缩感知和线性测量两种方法，获得了好的图像重构质量.值得注意的是，Baraniuk等人[12]的研究表明，如果能利用图像小波域系数层次结构所展示的相关性来设计重构算法，则能进一步提高重构精度.压缩感知重构的效率依赖于信号的稀疏性特征，然而，即使将图像变换到小波域，也仅是近似稀疏的.对OMP等现有压缩感知算法来说，若想获得高的图像重构精度，只能大幅度增加测量次数，从而造成压缩比下降.针对此问题，我们认为仅仅对图像进行压缩感知是不够的.

据此，本文将传统数据压缩的编码思想融入压缩感知的测量步和重构步，提出一种基于图像小波变换的零树压缩感知方法，利用小波系数的相关性来提高图像重构质量和压缩比.

1 基于小波变换的零树压缩感知方法

本节首先介绍零树的定义，然后将零树的思想融入压缩感知理论，提出基于图像小波变换的零树压缩感知方法，包括基于小波零树的测量算法和零树匹配追踪重构算法两部分.测量算法在测量步运行，图像被压缩；重构算法在重构步运行，图像被恢复.

1.1 零树和零树根

文献[2]中定义了零树根和零树的概念.

定义1(零树根) 在图像小波域中，对于一个值为零的小波系数，如果它的父系数是重要系数，而子孙系数均为零，则称之为零树根.

定义2(零树) 零树根和它的子孙系数称为零树.

零树体现了小波系数的相关性.已知初始阈值，若小波系数的绝对值大于该阈值，则称之为重要系数，反之则是不重要系数.在对图像进行多级小波变换后，小波系数呈现出相互关联的统计特性.若父系数是不重要系数，则其子孙有很大概率也是不重要系数.零树即是利用这种特性定义的一种数据结构.文献[2]基于零树设计一种称为EZW的编码算法，实现了图像压缩.

本文将对零树编码加以改造，使之与压缩感知理论相融合，进而提出一种新的零树压缩感知方法.

1.2 基于小波零树的测量算法

测量算法的核心是两符号零树编码子算法和测量子算法.在两符号零树编码子算法中，我们设计两个符号T和P来编码小波系数，基于零树挖掘多级小波系数之间的相关性.同时基于此编码子算法的结果来设计测量子算法.设扫描遍i的初值为1，图像扫描总次数为L.测量算法总体流程如图1所示.

图1 测量算法

首先，设定初始阈值T0，即第一次扫描的阈值.考虑到将要进行的多遍扫描，初始阈值取2的幂次，其幅值由最大的小波系数确定：

(1)

Ti=Ti-1/2 ,i=2,…,L

(2)

依据阈值对图像小波系数进行扫描，若小波系数的绝对值大于阈值，则为重要小波系数，予以保留；否则为不重要系数，本轮扫描用零替代，但并不舍弃，而留待下一次扫描.

然后，对扫描结果进行编码和测量，即设计零树编码子算法和测量子算法.

将小波系数分为2类：一类是零树，包括零树根和它的子孙系数；其他小波系数则归结为另一类.相应地，设计2个符号T和P来编码小波系数，其中：

T：编码零树根；

P：编码除零树根与其子孙系数外的小波系数.

基于符号P和T，我们提出一种编码算法，称之为两符号编码子算法，其算法流程如图2所示.

图2 两符号零树编码子算法流程

设第i次扫描得到的小波系数矩阵为ci，阈值为Ti-1，编码子算法描述如图3所示.

两符号零树编码子算法输入：ci，Ti-1输出：编码符号表Clisti(1)按Z型顺序扫描ci，设读到的系数为ci(m，n)；(2)如果ci(m，n)>Ti-1，则在Clisti中写入符号P；(3)如果ci(m，n)是零树根，则在Clisti中写入T，并在ci中将其子孙系数标记为N；(4)如果ci(m，n)的标记是N，则不编码；(5)如果ci(m，n)是ci中的最后一个系数，则算法终止，否则返回第(1)步；

图3 零树编码子算法

Fig.3Zerotreeendoing

测量子算法对小波系数矩阵ci进行投影，得到测量值.设测量矩阵为φi，测量子算法叙述如图4所示.在测量子算法的第2)步中，φi的维数由零树编码子算法和向量xi共同确定.其中由xi的维数来确定φi的列数，而编码子算法中符号P的个数来确定φi的行数.在本文中，测量矩阵中的数值为高斯随机数.

测量子算法输入：ci输出：测量值yi(1)对ci做Z型扫描一维化，得到向量xi；(2)确定ϕi的维数；(3)测量：yi=ϕixi；

图4 测量子算法

Fig.4Measuresub-algorithm

1.3 零树追踪重构算法

重构算法首先利用L次扫描得到的零树编码符号表追踪“重要系数”的位置，然后利用测量值来还原“重要系数”的值，从而重构小波系数矩阵.再经过小波逆变换重构原始图像.零树追踪算法的输入是包括L个编码符号表和L组测量值.由图3和图4不难看出，这正是测量算法的输出.

设原始图像的大小为M×N，算法描述如图5所示.

零树追踪重构算法输入：Clist1-ClistL，y1-yL输出：重构图像(1)初始化M×N大小的矩阵C；(2)fori=1toL(3)初始化M×N大小的临时矩阵Ci(4)读表Clisti，读到编码符号d；(5)若d=P，则将P按Z型扫描顺序填入Ci，否则在对应位置填T，同时在其子孙系数位置也填T；(6)如果d是Clisti的最后一个符号，则返回(6)，否则返回(3)；(7)对Ci做Z型扫描，依据符号P的位置选取ϕi的列向量，得到矩阵ϕPi；(8)x′i=(ϕTPiϕPi)-1ϕTPiyi，并将x′i按Z型扫描回写入C；(9)对C做小波逆变换，得到重构图像；

图5 零树追踪重构算法

Fig.5Zerotreepursuitreconstrution

性质 零树追踪重构算法具有嵌入式特征.

从图5所述零树追踪算法的第(2)步(for循环步)可以看出，我们提出的重构算法分为L小步，每一步重构出一部分小波系数xi'.随着重构步数向L步逼近，矩阵C与原始图像小波系数矩阵的距离越来越小.也就是说，对C做小波逆变换，得到重构图像的误差越来越小，即具有嵌入式重构的特征.

具有嵌入式特征的零树追踪算法鲁棒性强，在此L小步循环中的任意步退出循环，算法依然能够正常重构，得到相应精度的重构图像，循环的次数越多，图像重构的精度就越高.

1.4 复杂度分析与示例

本小节先从计算复杂度的角度对小波零树压缩感知方法做简要分析，然后以一个8×8的数据矩阵为例，给出算法运行的示例.

接下来，针对一幅8×8的图像经过3级分解后得到的小波系数矩阵(如图6所示)，以一次Z型扫描为例(即L=1)，给出一个算法实现的示例.

图6 小波系数矩阵图

首先运行测量算法.依据初始阈值公式(1)可计算出T0=8.第1次扫描后，得到如图7所示的小波系数矩阵.对此矩阵做两符号零树编码，得到编码符号表Clist1={PPPTPTTTTPTTTTTTTPTT}.测量子算法则对小波系数矩阵执行Z型扫描一维化，得到向量x1：x1=(15,10,0,0,-12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,14,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0)T.

在Clist1中，符号P的个数为6，x1的长度为64，因此测量矩阵φ1的大小为6×64.根据测量公式y1=φ1x1，可计算出测量结果y1=(61.91, 4.807 0,-1.476 3, 25.718 9,11.608 6, 8.516 8)T.从图7可以看出，大系数的个数是4个，但编码中符号P的个数是6.这是因为在测量算法中，我们将零树以外的系数均视为大系数的缘故.

图7 第1次扫描后小波系数矩阵

然后运行重构算法.重构算法的输入是测量算法的输出，也就是说，输入是Clist1和y1.先由Clist1恢复出大系数的位置，得到矩阵C1，如图8所示.

图8 矩阵C1

图9 矩阵C

1.5 讨 论

在OMP,StoMP和CosaMP等经典压缩感知重构算法中，追踪重要系数的位置带来了很大的计算复杂度，而且因此引起的位置误差造成重构精度严重下降.本文的基本思路是利用编码思想来精确追踪重要系数的位置，然后再基于最小二乘重构重要系数的值，从而提高重构精度.

在测量算法中，编码的目的是追踪重要系数的位置，而无需如EZW算法一样编码重要系数的值，因此我们只简洁地设计了两个符号P和T，既能充分利用小波系数相关性，又能提高压缩比.然而在该子算法中，除零树根和相应的零树元素外的其他系数均被编码成P.这造成我们将孤立的零系数也看成了重要系数，带来了额外的计算开销.但因为小波相关性的缘故，这样的思路不会影响到算法的效率，我们将在实验部分加以验证.

多遍扫描提高了稀疏度，也使得我们的方法具有鲁棒性.图像的小波域系数不是严格的稀疏信号，通过多遍扫描，不仅提高了每一次参与压缩感知的子信号稀疏度，而且，多遍扫描具有嵌入式特点，即便是算法意外终止，也会获得相应精度的重构图像，具有鲁棒性.

2 实验与分析

本节测试小波图像零树压缩感知方法的性能，并与OMP，StOMP和CoSaMP等压缩感知算法以及EZW等编码压缩算法进行对比.实验的硬件环境是配置Intel(R)Xeon(r)E4028 四核 2.0GHzCPU和4G内存的PC机，软件环境是Windows7和Matlab7.0.选取128×128大小的Lena，Shepp-LoganPhantom和Mondrian图像进行测试.这3个图像具有很好的代表性，标准测试图像Lena是平滑的自然图像，Mondrian属于简单图像，而Shepp-LoganPhantom则是介于两者之间的医学图像.在实验中，对上述3种图像信号采用Daubechies9/7进行3层小波分解.

本实验的评价指标是运行时间t，压缩比CR和峰值信噪比PSNR.运行时间t用于评估算法的计算复杂度.图像压缩比CR用于评价测量与编码算法的压缩效率，定义为原始图像的数据量Data_image与传输数据量Data_trans的比值.传输数据量即测量算法输出到重构算法的数据量.CR用公式表示如下：

(3)

PSNR则用于评价重构算法恢复图像的精度.对于大小为M×N的图像，PSNR定义为：

(4)

图10给出了在传输数据量相同的情况下，Lena，Shepp-LoganPhantom和Mondrian等 3类图像信号在不同方法下重构的视觉效果.其中Lena图像，Shepp-LoganPhantom图像和Mondrian图像的数据传输量分别为9 060字节，6 460字节和5 020字节，相应的压缩比分别为1.8,2.5和3.3.从视觉效果看，本文提出的小波图像零树压缩感知方法远优于OMP算法，同时也好于EZW算法.然而，和原始图像相比，Lena图像的视觉效果还不能满足人们对图像质量的需求.压缩感知理论将采样和压缩结合起来，提高了压缩成像的速度，但要将其应用于自然图像压缩，还需更加深入的研究.

图10 图像恢复视觉效果

在相同的传输数据量下，图11和图12分别比较了各算法的图像重构质量和运行时间.在本实验中，我们用运行时间来评估算法的计算复杂度.从图11可以看出，在重构质量方面，小波零树压缩感知方法优于OMP,StOMP,CoSaMP以及EZW算法，究其原因，是因为我们提出的重构算法通过解码可以精确恢复出大系数的位置，而且，只要采样次数等于符号P的个数，就能完全重构出大系数的值.从图12可以看出，我们提出的重构算法运行时间少于OMP算法；对于Shepp-LoganPhantom图像，本文方法的运行时间与StOMP,CoSaMP以及EZW算法相当，而对于Mondrian和Lena图像，则要花费更长的运行时间.这是因为相比于OMP算法，本文方法无需逐个追踪重要系数，因而降低了复杂度，节省了运行时间.然而，本文方法需要解码和重构两个过程，相应地带来了额外的时间开销.

图11 图像恢复质量

图12 重构时间对比

图13比较了各种方法的压缩效率.可以看出，我们提出的小波零树压缩感知方法比其他方法有更高的压缩比.和EZW算法相比，本文方法采用简洁的两字符零树编码，这样，后续的算术熵编码有更高的效率，因而有更高的压缩比.和OMP，StOMP和CoSaMP等算法相比，本文方法编码了大系数的位置，因而测量次数显著减少.特别是在低重构精度的前提下，本文方法的压缩比远大于其他算法.

图14给出了在图像重构质量相同的情况下，各压缩感知测量算法消耗缓存的对比结果.可以看出，相对于OMP，StOMP和CoSaMP等压缩感知匹配追踪算法，本文方法有最少的缓存数据量.这是因为在我们提出的测量算法中，零树编码子算法精确编码了重要系数的位置，因此重构算法可以据此重构重要系数的值.这样，测量矩阵φi的行数就会大大减少，因此比其他算法节省了更多的缓存.

图13 压缩比结果对比

图14 缓存花费

3 结 论

图像的小波域系数不是严格稀疏的，因此匹配追踪等压缩感知重构算法很难正确追踪重要系数的位置，从而降低了图像压缩感知的效率.鉴于此，本文将编码思想融入压缩感知的测量步与重构步，提出了一种基于图像小波变换的零树压缩感知方法，包括两符号零树编码子算法、测量子算法和零树追踪重构算法等.针对Lena,Shepp-LoganPhantom和Mondrian等3类测试图像的实验结果表明，在重构时间方面，本文方法的运行时间优于OMP算法；在压缩效率方面，本文方法的压缩比远高于OMP,StOMP和CoSaMP等匹配追踪算法以及EZW编码压缩算法；在重构质量方面，本文方法也有最好的图像恢复精度；同时，本文方法也比OMP,StOMP,CoSaMP等算法消耗更少的缓存.

本文提出的零树压缩感知方法具有嵌入式特征，如何利用它来提高顺序压缩感知算法[13]的效率是我们将要进行的下一步工作.

[1]DAUBECHIESI.Tenlecturesonwavelets[M].Philadelphia:SLAM,1992: 105-108.

[2]SHAPIROJM.Embeddedimagecodingusingzerotreesofwaveletcoefficients[J].IEEETransactiononSignalProcessing, 1993, 41(12): 3446-3462.

[3]DONOHOD.Compressingsensing[J].IEEETransactionsonInformationTheory, 2006, 52(4): 1289-1306.

[4] 罗琦,魏倩,缪昕杰.基于压缩感知思想的图像分块压缩与重构方法[J].中国科学:信息科学, 2014, 44(8): 1036-1047.

LUOQi,WEIQian,MIAOXinjie.Blockedimagecompressionandreconstructionalgorithmbasedoncompressedsensing[J].ScienceChina:InformationScience, 2014, 44(8): 1036-1047.(InChinese)

[5] 吴光文,张爱军,王昌明.一种用于压缩感知理论的投影矩阵优化算法[J].电子与信息学报,2015,37(7):1681-1687.

WUGuangwen,ZHANGAijun,WANGChangming.Noveloptimizationmethodforprojectionmatrixincompresssensingtheory[J].JournalofElectronics&InformationTechnology,2015,37(7):1681-1687.(InChinese)

[6]TROPPJ,GILBERTA.Signalrecoveryfromrandommeasurementsviaorthogonalmatchingpursuit[J].IEEETransactiononInformationTheory, 2007, 53(12): 4655-4666.

[7]DONOHODL,TSAIGY,DRORII,et al.Sparsesolutionofunderdeterminedsystemsoflinearequationsbystagewiseorthogonalmatchingpursuit[J].IEEETransactiononInformationTheory, 2012, 58(2): 1094-1121.

[8]NEEDELLD,VERSHYNINR.Signalrecoveryfromincompleteandinaccuratemeasurementsviaregularizedorthogonalmatchingpursuit[J].IEEEJournalofSelectedTopicsinSignalProcessing, 2010, 4(2): 310-316.

[9] 周四望,罗梦儒.顺序小波包图像压缩感知方法[J].湖南大学学报:自然科学版,2015,42(4):130-135.

ZHOUSiwang,LUOMengru.Sequentialimagecompressedsensingbasedonwaveletpacket[J].JournalofHunanUniversity:NaturalSciences, 2015, 42(4): 130-135.(InChinese)

[10]HOUY,ZHANGY.Effectiveimageblockcompressedsensingwithquantizedmeasurement[C]//IEEEDataCompressionConference.Snowbird：IEEEComputerSociety,2014: 407-411.

[11]DONOHODL,TSAIGY.Extensionsofcompressedsensing[J].SignalProcessing, 2006, 86(3): 533-548.

[12]BARANIUKR,CEVHERV,DUARTEM,et al.Model-basedcompressivesensing[J].IEEETransactionsonInformationTheory, 2010, 56(4): 1982-2001.

[13]WEID,HEROAO.Multistageadaptiveestimationofsparsesignals[J].IEEEJournalofSelectedTopicsinSignalProcessing, 2013, 7(5):783-796.

Image Zerotree Compressed Sensing Based on Wavelet Transform

ZHOU Siwang†,LIU Longkang

(College of Information Science and Engineering,Hunan University, Changsha 410082,China)

The basic principle of Compressed Sensing (CS) theory is that if a signal is sparse, CS promises to deliver a full recovery of this signal with high probability from far fewer measurements than the original signal. Unfortunately, image signals usually are not sparse, and thus it is difficult to obtain high compression performance for image compressed sensing.This paper proposed a simple and efficient zerotree compressed sensing method for images. In the proposed scheme, the classical zerotree coding is integrated into the process of measure to encode the precise locations of significant elements, which is used to restore the original image by the proposed pursuit reconstruction algorithm to improve the quality of the reconstructed image. The experimental results show that, compared with the existing matching pursuit algorithms and Embedded Zerotree Wavelet (EZW) coding algorithm, the proposed algorithm achieves much higher compression ratio and better image quality.

wavelet transform；image processing； compressed sensing； encoding

1674-2974(2017)02-0129-08

10.16339/j.cnki.hdxbzkb.2017.02.019

2016-02-28

国家自然科学基金资助项目(61472131), National Natural Science Foundation of China (61472131)；湖南省自然科学基金资助项目(14JJ2051), Natural Science Foundation of Hunan Province of China(14JJ2051)

周四望(1971-)，男，湖南岳阳人，湖南大学副教授，博士

†通讯联系人，E-mail:swzhou@hnu.edu.cn

TP37

A