第45卷 第4期 2012年4月
天 津 大 学 学 报 Journal of Tianjin University
V ol.45 No.4Apr. 2012
收稿日期：2011-01-14；修回日期：2011-03-11.
基金项目：国家自然科学基金青年基金资助项目(60806010，61101226)；内燃机燃烧学国家重点实验室开放课题资助项目(k2011-11)． 作者简介：张淑芳（1979— ），女，博士，讲师． 通讯作者：张淑芳，shufangzhang@https://www.doczj.com/doc/d517500311.html,.
基于压缩感知的图像自适应编码算法
张淑芳，李 凯，徐江涛，瞿广财
(天津大学电子信息工程学院，天津 300072)
摘 要：利用压缩感知理论对图像进行固定采样率的压缩并重构时，由于图像各个块的稀疏程度不同，低采样率很难保证图像各块都具有较高的重构质量，而高采样率又会造成资源的浪费．为了解决上述问题，提出了一种基于压缩感知的图像自适应编码算法，该算法首先判断图像各块在DCT 域的稀疏度，然后根据判断结果对图像各块进行自适应的压缩采样，从而确保图像在较低采样率下能获得较高的重构质量．实验结果表明，运用所提自适应编码算法在采样率平均值为44%时，重构图像的平均PSNR 值可达到35dB 以上，并且重构图像所有块的PSNR 值分布比较集中，从而使得图像具有较好的主观质量．
关键词：压缩感知；图像自适应编码；采样率；稀疏度
中图分类号：TN919.81 文献标志码：A 文章编号：0493-2137(2012)04-0319-06
Image Adaptive Coding Algorithm Based on Compressive Sensing
ZHANG Shu-fang ，LI Kai ，XU Jiang-tao ，QU Guang-cai
(School of Electronic Information Engineering ，Tianjin University ，Tianjin 300072，China )
Abstract ：When the image is compressed and reconstructed with compressive sensing theory at the same sampling
rate ，the low sampling rate can't ensure that every block in the image obtains high reconstruction quality and the high sampling rate usually leads to resource waste because of the different sparseness degree for each block in the image. In order to solve the above problem ，an image adaptive coding algorithm based on compressive sensing was proposed in this paper. The sparseness degree in DCT domain for each block in the image was estimated first ，then the adaptive compression was applied to each block according to the estimated results ，thus a relatively high reconstruction quality was acquired for the image at a relatively low sampling rate. Experimental results showed that the proposed adaptive coding algorithm enabled the reconstructed images to obtain average PSNR values above 35dB at the average sam-pling rate of 44%. Moreover ，the PSNR values of all the blocks were quite concentrated ，giving the image a better subjective quality.
Keywords ：compressive sensing ；image adaptive coding ；sampling rate ；sparseness degree
目前对图像信号进行采集和压缩普遍采用以香农定理为准则的处理方式，即对图像信号进行高速采样后再压缩编码．该采样方式要求采样速率达到信号带宽的2倍以上才能精确重构信号，对采样设备提出了巨大挑战；同时采用传统图像编码算法对采样后的数据进行压缩时，仅对采样数据变换后少数绝对值较大的系数进行压缩编码，抛弃大量零或者接近于零的系数，从而对采样资源造成大量浪费．近年来，由Candès [1]和Donoho [2]提出的压缩感知(compressive
sensing ，CS )理论为新型图像采集和压缩处理提供了
理论支持[3]，
它首先利用随机观测矩阵Φ，把在某个正交基或紧框架上稀疏或可压缩的高维信号(x ∈R N )投影到M 维的低维空间上(得到测量值y )，然后通过求解优化问题从少量的投影中以高概率重构原始信号或图像．CS 理论的核心思想是将压缩与采样合并进行，它突破了香农采样定理的瓶颈，即只需要通过少量的样本点就能够精确地重构原始图像，它将给信号处理带来一次新的革命，对统计学、信息论和编码
·320· 天 津 大 学 学 报 第45卷 第4期
等领域产生重要的理论影响[4]．
国内外学者对压缩传感在图像编码中的应用进行了大量研究．2006年Haupt 等[5]通过实验表明如果图像是高度可压缩的，测量过程即使存在噪声，压缩感知方法仍可准确重构图像．2006年Rice 大学成功研制出“单像素相机”[6]，为低像素相机拍摄高质量图像提供了可能．2007年，Gan [7]借鉴离散余弦变换(discrete cosine transform ，DCT )块编码的巨大成功提出了基于块的压缩感知方法，每一块都采用相同的块观测矩阵，可减少观测矩阵的存储量，有效解决高维图像采集问题．由于在一幅图像中每个块在变换域的稀疏度不一样，在变换域越稀疏的块，重构图像所需要的采样点数就越少．本文鉴于此，提出了基于压缩感知的图像自适应编码算法，在对图像进行CS 压缩采样前，首先判断其在DCT 域的稀疏度，然后根据每个块的稀疏度对其进行自适应的压缩采样，从而使得在低采样率的情况下能够对图像进行高质量重构．
1 压缩感知理论
压缩感知理论由Candès 和Donoho [1-2]在2006
年正式提出．Candès 证明了只要信号在某一正交空间具有稀疏性，就能以较少的采样点数完全或者以很高概率重建该原始信号．
假设T [(1),(2),,()]x x x N =x 表示一维离散时间信号组成的列向量，其可表示为一组标准正交基的线性组合，即 1N
i i i ===∑x s s Ψψ
(1)
式中：Ψ为基矩阵，
12[,,,]N = Ψψψψ，i ψ为列向量；1N ×的列向量s 是x 的加权系数序列，即T
,i i i
==s x x ψψ．显然，x 和s 是同一个信号的等价
表示，x 是信号在时域的表示，s 则是信号在Ψ域的
表示．如果s 中只有K 个非零(或绝对值较大)的系数，其余N -K 个系数都为0(或绝对值很小)，则称s 为信号x 的稀疏表示．
假设N ∈y R 为信号x 在测量矩阵M N ×∈ΦR 下的线性测量值，即
===y x s s ΦΦΨΘ
(2)
式中：=ΘΦΨ是一个M N ×的矩阵．对于给定的测量值y 从式(2)求解s 是一个线性规划问题，但由于
K M N ≤，即方程的个数少于未知数的个数，这是
一个欠定问题．Candès 等[8]证明了信号重构可以通
过求解最小0l 范数来求解，
如果测量矩阵Φ和稀疏变换矩阵Ψ满足约束等距性(restricted isometry prop-erty ，RIP )条件，最优稀疏解?s 可以由测量值N ∈y R 重构，即
?arg min s.t.==s
s s y
Θ
(3)
式中0i 为向量的l 0范数，代表向量x 中非零元素的个数．该式为非凸优化问题，是典型的NP-hard 问
题，计算复杂度高．Candès [1]和Donoho [2]提出用l 1范
数来代替l 0范数，
把式(3)转化为一个凸优化问题来求解，即
1?arg min s.t.==s
s s y
Θ
(4)
得到信号x 在稀疏域Ψ下的最优稀疏解?s 后，信号x
的重构值?x 可表示为 ??=x
s Ψ (5)
在对图像进行稀疏变换时，常用DCT 、小波变换
和有限差分来作为变换稀疏基，在用有限差分做稀疏变换时，常用全变差(total variation ，TV )来衡量． Candès 等[9]从大量自然图像的离散梯度都是稀疏的角度出发，提出了适合二维图像压缩重构的最小全变分法，重构精确而且鲁棒性强，但是运算速度较慢． 2009年Li [10]提出了基于最小全变分法的TV AL3算法，它将全变分法和增广拉格朗日函数相结合来进行图像压缩重构，有效提高了重构速度，并且重构图像的PSNR 值也有了很大提高，其重构公式为 min grad n
i i
p
u R μ∈∑
s.t.Au b = 0u ≥
(6)
式中：p ＝1或p ＝2代表1范数或2范数；
grad i u 表示在位置i 处u 的离散梯度向量．
因此，本文在对图像进行自适应压缩编码后，利用测量值进行图像重构时选用TV AL3算法．
2 基于压缩感知的图像自适应编码算法
本文提出了基于压缩感知的图像自适应编码算法，根据图像各个块的稀疏度对其进行自适应的压缩采样，从而实现低采样率下图像的高质量重构． 2.1 图像压缩采样率对重构质量的影响
本文对图像进行基于块的压缩采样，把图像分为
3232×的块，
为了满足RIP 条件，本文使用独立同分
2012年4月 张淑芳等：基于压缩感知的图像自适应编码算法 ·321·
布的高斯随机矩阵作为测量矩阵Φ，分别对图像进行20%、40%、60%和80%的采样，并采用TV AL3算法对测量值进行重构．为了衡量图像重构效果，
采用客观图像质量评价指标PSNR 来表征重构图像块和相应原始图像块之间的差别．图1(a )和(b )分别为Lena 图像和Cameraman 图像在不同采样率下每幅图像各个块PSNR 值的分布情况，块采用从上到下，从左到右的方式进行排列，横坐标表示块的分布，纵坐标表示重构图像各个块的PSNR 值．
（a ）Lena 图像
（b ）Cameraman 图像
图1 不同采样率下重构图像PSNR 值的分布 Fig.1 PSNR distribution of reconstructed images at
different sampling rates
从图1可以看出，随着采样率的升高，各个块的PSNR 值呈上升趋势，但高采样率会导致图像压缩效率的降低，并且造成解码端图像重构复杂度的升高．因此，需要在图像采样率和PSNR 之间形成良好的折中．另外，由于图像中各个块的稀疏度不同，使得在相同采样率下重构图像中各个块的PSNR 值有较大起伏，对图像整体质量造成了很大影响．
图2为20%和80%采样率时的重构图像，其中图2(a )为采样率20%的重构图像，由于其PSNR 起伏较大，有些块PNSR 较好，有些块PSNR 较差，因此其块效应比较明显，在脸部和帽子区域可以看出明显的块效应．图2(b )为采样率80%的重构图像，虽然PSNR
起伏也较大，但由于其PSNR 值都较高，因此看不出明显的块效应，其重构时间比采样率20%时的
重构时间大约增加了50%．
因此，需要对整幅图像进行自适应的压缩采样，对稀疏性较好的块采用较低的采样率，对稀疏性较差的块采用较高的采样率，从而确保在较低的采样率下，整幅图像重构质量达到最优．如果能找到图像各个块的PSNR 和稀疏度之间的关系，就能对图像进行自适应的压缩采样．
（a ）20%采样率 （b ）80%采样率
图2 不同采样率下的重构图像
Fig.2 Reconstructed images at different sampling rates
2.2 图像稀疏度的判断准则
由于对图像进行分块二维DCT 变换后，低频系数分布在DCT 分块系数矩阵的左上角，高频系数分布在其右下角，并且低频系数的绝对值大于高频系数的绝对值．图像越稀疏，它的低频部分占的比重就会越大．本文利用α作为DCT 系数绝对值|T i , j |大小的判断阈值，如果|T i , j |小于α则判定其为较小的系数，反之则把该系数作为较大的DCT 系数．利用C 表示图像各个块DCT 变换系数中模值小于α的个数．从以上分析可知，C 值越大表示该块越稀疏，其需要较少的压缩采样点数就能得到较好的重构图像[11]．图3(a )和(b )分别给出了α＝4，采样率为40%时，Lena 和Cameraman 重构图像中各个块C 值和PSNR 值的关系．
从图3可以看出，图像各个块的C 值和PSNR 值大致服从相同的变化规律，即块的C 值越大，其 PSNR 值越高，因此可通过C 值来间接表征图像块重构时能够达到的PSNR 值．
因此，本文以C 值作为图像稀疏度的判断准则，依据C 值的大小来对图像的采样率进行自适应 选择．
2.3 基于压缩感知的图像自适应编码算法
为了在较低采样率下获得较高的图像质量，本文对C 值较大的块以较低采样率进行压缩采样，反之对C 值较小的块以较高采样率进行压缩采样，从而保证整幅图像都具有较高的重构质量．本文选用i T (i ＝
·
322· 天 津 大 学 学 报
第45卷 第4期
（a ）Lena 图像
（b ）Cameraman 图像
图3 图像各块C 值和PSNR 值之间的关系
Fig.3 Relationship between C and PSNR of each block in
the image
1，2，3)作为对原始图像进行压缩采样时采样率高低判断的阈值，且123T T T >>；用1β、2β、3β和4β分别表示对图像进行20%、40%、60%和80%的采样压缩．依
据C 和i T 的大小关系，对每个图像块进行自适应的压缩采样，即
11
2
213324
3
C T T C T T C T C T ββββ>??
(7)
i T 取值不同，则会对图像的压缩效率和重构质量
产生不同影响．当i T 取值较小时，图像可以较低的采样率进行压缩采样，从而可有效提高图像的编码效率，降低编码器的功耗，但重构图像的质量要差一
些；反之，当i T 取值较大时，图像编码效率较低，但重构图像的质量较好．大量实验表明，当T 1、
T 2和T 3的取值分别为900、800和700时，在保证重构图像质量较好的前提下，能较大幅度提高图像的编码效率．在应用本文所提算法对图像进行自适应编码时，需要根据网络带宽、编码器的功耗和对图像重构质量的要求等实际因素对i T 的取值进行相应调整．
对图像进行自适应压缩采样的流程如图4所示． 步骤1 将输入图像分成m 个n n ×的块，
并令i ＝1． 步骤2对第i 块图像进行DCT 变换并计算该块的C 值． 步骤3根据式(7)，判断C 值和图像压缩采样阈
值T 1、
T 2和T 3的关系，如果C ＞T 1，则对图像进行1β采样，转向步骤7，否则执行步骤4．
步骤4 如果C ≤T 1并且C ＞T 2，
则对图像进行2β采样，转向步骤7，否则执行步骤5．
步骤5 如果C ≤T 2并且C ＞T 3，则对图像进行3β采样，转向步骤7，否则执行步骤6．
步骤6 如果C ≤T 3，则对图像进行4β采样． 步骤7 如果i ≥m 则结束整个压缩采样过程，否则，令i ＝i ＋1，重新执行步骤2．
图4 算法流程
Fig.4 Flow chart of the proposed algorithm
为了提高压缩效率，本文在对图像块进行压缩采
样时，利用相同的种子针对各个块不同的采样率生成相应尺寸的高斯随机观测矩阵，这就与传统固定采样率的压缩方法一样，仅需向解码端传递一次产生随机观测矩阵的种子．同时，为了向解码端传递各个块压缩时所使用的采样率，本文使用标志位1、2、3和4分别表示20%、40%、60%和80%的采样率，与传统利用固定采样率对图像进行压缩采样相比，该自适应算法只需在各图像块编码码流的开始多加入一个采样率标志位即可．
2012年4月 张淑芳等：基于压缩感知的图像自适应编码算法 ·323·
3 实验结果及分析
采用Lena 、Cameraman 和Columbia 具有不同灰度和纹理细节的图像对所提算法的有效性进行验证，其中Lena 图像包含丰富的细节信息和纹理特征；Cameraman 图像前景和背景对比度较大；Columbia 为景物图像，平滑和细节区域区分较为明显.
在实验中，块的大小n 取值为32，α的取值为
4，采用TV AL3恢复算法，并且阈值T 1、T 2和T 3的取值分别为900、800和700，实验结果如表1所示．其中λ表示采样率的增加所带来的PSNR 增益，以20%
时的采样率1β和PSNR 1作为基准，其余采样率所带来的PSNR 增益可表示为
1
1
PSNR PSNR i i i λββ?=?
(8)
表1 实验结果
Tab.1 Experimental results
Lena (分辨率256×256) Came r
aman (分辨率256×256) Columbia (分辨率480×480)
采样率/% PSNR/dB 重构时间/s
λ/% 采样率/%PSNR/dB 重构时间/s λ/% 采样率/%PSNR/dB 重构时间/s λ/%
20.000,0 26.636,3 35.077,8 — 20.000,024.574,432.164,1 — 20.000,029.674,8 116.977,8 — 40.000,0 30.664,2 40.410,8 20.139,5 40.000,029.161,936.768,6 22.937,540.000,034.912,6 134.171,2 26.189,060.000,0 34.072,4 45.328,8 18.590,3 60.000,033.311,442.971,0 21.842,560.000,039.034,1 152.429,0 23.398,380.000,0 37.974,4 52.750,0 18.896,8 80.000,036.726,149.220,7 20.252,880.000,042.749,3 170.159,1 21.790,
850.000,0 35.024,7 43.398,3 30.163
,3 51.880,0
35.914,2
40.966,9 35.570,3
30.220,1
36.836,5 135.184,8 34.580
,9
从表1可以看出，固定采样率下，增加单位采样率所能提升的PSNR 值的增益在20%左右，而本文提
出的自适应采样算法增加单位采样率所能带来的图像PSNR 值平均增益达到了33%．显然，本算法对重构图像的质量有显著提高．对于Lena 和Cameraman 图像，包含的细节信息较多，采用本文所提自适应算法所需采样率大约为50%，对于前景和背景区域区分较为明显的Columbia 图像，采用自适应算法时所需采样率仅为30.22%，这是由于大部分背景区域块的稀疏性较好，采用较低的采样率就能精确重构图像． 图5给出了Lena 原始图像以及不同采样率下的重构图像．其中图5(e )为原始图像，图5(a )、(b )、(c )和(d )分别为Lena 图像在采样率20%、40%、60%和80%时的重构图像，随着采样率的增加，重构图像的主观质量越来越好．当采样率为20%和40%时，存在明显的块效应和模糊现象；当采样率达到60%时，重构图像的PSNR 值为34.07dB ，从主观效果上来看，重构图像和原始图像的差别很小．采用本文自适应采样算法，仅需要50%的采样率，重构图像(图5(f ))的PSNR 值为35.02dB ，和原始图像相比，几乎看不出差异．
为了更加直观地说明利用自适应算法进行压缩采样时图像各区域所选用的采样率，图6(a )和(b )分别给出了Lena 图像和Cameraman 图像采样率的分割示意．在图6(a )所示的Lena 图像分割图中，对于头发、面部和帽子这些包含细节信息较多的区域，图像块的稀疏性较差，采用较高采样率对此进行压缩采
（a ）20%采样率 （b ）40%采样率
（c ）60%采样率 （d ）80%采样率
（e ）原始图像 （f ）本文自适应算法
图5 Lena 原始图像以及在不同采样率下的重构图像
Fig.5 Original image and reconstructed images at different
sampling rates for Lena
·324·天津大学学报
第
45卷 第4期
样，
有效保证了重构图像的主客观质量，而对于周边
比
较
平滑的区域，图像块的稀疏性较好，
则采用20
%
的采样率，可有效提高图像的压缩效率．同样对于图
6(b
)
所示
的 Cameraman图像而言，在草坪、人的头
部和相机等部位，包含的纹理信息较多，采用了80%
的采样率进行压缩采样，而对于天空这些比较平坦的
背景区域，块的稀疏性较好，采用20%采样率进行压
缩采样．
（a）Lena图像 （b）Cameraman图像
图6图像采样率的分割示意
Fig.6Partition sketch map of image sampling rates
图7给出了Lena图像在各种固定采样率和自适
应算法下各个块的PSNR值分布，其中横坐标表示块
的分布，采用和图1相同的排列方式；纵坐标表示
PSNR值的大小．从图7可以看出，与固定采样率的
PSNR曲线相比，本文所提自适应算法的PSNR曲线
较平坦，上下起伏较小，从而保证整幅图像中各个块
的重构质量都位于一个平均水平，显著提高了重构图
像的整体质量．
图7Lena图像各个块的PSNR分布
Fig.7PSNR distribution of each block in Lena image
4 结 语
本文提出了一种基于压缩感知的图像自适应编
码算法，该算法根据图像各个块在DCT域的稀疏
度，分别对各个块进行不同采样率的压缩采样，在确
保整体图像质量较优的条件下，有效降低了图像的编
码码率．实验结果表明，本文所提算法实现复杂度较
低，重构图像主客观质量较好．
参考文献：
［1］Candès E J. Compressive sampling[C]// Proceedings of
the International Congress of Mathematicians. Madrid，
Spain，2006：1433-1452．
［2］Donoho D L. Compressed sensing[J]. IEEE Transactions
on Information Theory，2006，52(4)：1289-1306.
［3］李树涛，魏 丹. 压缩传感综述[J]. 自动化学报，
2009，35(11)：1369-1377.
Li Shutao，W ei Dan. A survey on compressive sens-
ing[J]. Acta Automatica Sinica，2009，35(11)：1369-
1377(in Chinese).
［4］石光明，刘丹华，高大化，等. 压缩感知理论及其研
究进展[J]. 电子学报，2009，37(5)：1070-1081.
Shi Guangming，Liu Danhua，Gao Dahua，et al. Ad-
vances in theory and application of compressed sens-
ing[J]. Acta Electronica Sinica，2009，37(5)：1070-
1081(in Chinese).
［5］Haupt J，Nowak R. Compressive sampling vs. conven-
tional imaging[C]// Proceedings of the IEEE Interna-
tional Conference on Image Processing. Atlanta，
Georgia，2006：1269-1272.
［6］Takhar D，Laska J N，Wakin M B，et al. A new com-
pressive imaging camera architecture using optical-
domain compression[C]// Computational Imaging IV at
SPIE Electronic Imaging. San Jose，California，2006：
43-52.
［7］Gan L. Block compressed sensing of natural images[C]//
Proceedings of the 15th International Conference on
Digital Signal Processing. W ashington DC，USA，
2007：403-406.
［8］Candès E J，Tao T. Decoding by linear programming[J].
IEEE Transactions on Information Theory，2005，
51(12)：4203-4215.
［9］Candès E J，Romberg J，Tao T. Robust uncertainty
principles：Exact signal reconstruction from highly in-
complete frequency information[J]. IEEE Transactions
on Information Theory，2006，52(2)：489-509.
［10］Li Chengbo. An Efficient Algorithm for Total Variation
Regularization with Applications to the Single Pixel
Camera and Compressive Sensing[D]. Houston：
Department of Computational and Applied Mathem-
atics，Rice University，2009.
［11］Stankovi?V，Stankovi? L，Cheng S. Compressive
video sampling[C]// Proceedings of the European Signal
Processing Conference. Lausanne，Switzerland，2008.