基于CS的灰度图像压缩

张习民，卓东风，刘国洋，李秋果

(1.河南教育学院物理系，河南郑州450046;2.太原科技大学电子信息工程学院，山西太原 030024)

基于CS的灰度图像压缩

张习民1，2，卓东风2，刘国洋2，李秋果2

(1.河南教育学院物理系，河南郑州450046;2.太原科技大学电子信息工程学院，山西太原 030024)

采用较新的压缩感知理论，通过Harr正交稀疏变换和伯努利采样矩阵，实现了对灰度图像的低速压缩采样，并利用正交匹配追踪算法实现压缩数据的恢复.实验结果表明，此算法能较好地实现图像的感知压缩.

Harr小波;压缩感知;稀疏;非自适应;正交匹配追踪

0 引言

在传统的图像压缩采样过程中，为了避免信号失真，采样频率不得低于信号最高频率的2倍.这种高速采样再压缩的过程浪费了大量的采样资源，能否采用一种新的方法，使得在保证信息不损失的情况下，用远低于奈奎斯特采样定理要求的速率采样信号，同时又能实现信号的恢复，成为研究的热点.近年来，一种新兴的压缩感知理论为数据采集恢复技术带来了革命性的突破.该理论指出如果信号本身是可压缩的，那么可以用远低于奈奎斯特频率进行采样，并恢复原图像［1］.本文在介绍压缩传感理论知识的基础上，首先采用Harr正交变换，实现对图像的稀疏处理，运用伯努利采样矩阵实现图像的投影采样，由正交匹配追踪(Orthogonal Math Persuit，OMP)实现对图像的复原.

1 压缩传感基本原理

斯坦福大学的统计学家DAVID DONOHO(美国科学院院士)［2］、CANDES［3］及华裔数学家陶哲轩(TAO T)等人于2004年提出了一种新的信息获取指导理论［4］，即压缩感知(Compressive Sensing，或Compressed Sensing、Compressed Sampling，CS).文献直到2006年才发表.CANDES证明了只要信号在某一个正交空间具有稀疏性，就能以较低的频率采样，而且可以以高概率重构该信号.

运用压缩感知原理对信号进行压缩采样的前提是信号必须稀疏，因为并不是所用的信号都能满足该条件，但大多信号经过适当的变换条件可以满足.所以压缩感知的第一步工作就是对原始的信号进行某种正交变换，使信号在变换域中稀疏.如，我们考虑一维空间RN中一个有限长度的数字信号x，可以把它看做一个N×1的列向量.对该信号可以用一组正交基进行稀疏变换，

这里，ψ是一个正交基矩阵［ψ1ψ2…ψN］，s是N×1的列向量，权值系数si=＜x，ψi＞=ψx，显然，x和s都能代表信号，只不过x为时域(或空间域)，而s为ψ域.如果变换后的信号s含有k个较大的非零值，就可以说信号x是k稀疏的.

其次，用一个观测矩阵φ对信号x进行测量，得到观测值y，

其中φ是一个M×N的矩阵，经过变换后的信号由RN压缩到RM空间(M＜N)，实现了对原始信号的降维处理，在这个过程中采样和压缩是同时进行的.

关键是观测矩阵φ的选择，它应该是非自适应的，也就是说φ的选择是固定不变的，独立于信号x，并且观测矩阵的设计要保障信号变换前后重要的信息不会被破坏，即保证能从M个观测值y中恢复x［5］.

为此，观测矩阵应满足约束等容条件(Restricted Isometry Property，RIP)，如式(3)

即变换要保证k个重要分量的长度.Baraniuk给出约束等容性的等价条件是:测量矩阵φ和稀疏化正交矩阵ψ的基不相关，能满足约束等容条件的测量矩阵可以是独立同分布的高斯矩阵，也可以是伯努利分布的矩阵，且满足M＞cklog(N/k)能重构原信号.本文采用的是后者.

2 信号的重构算法

若已知的条件为测量矢量y，观测矩阵φ及稀疏化正交矩阵ψ，希望重构出k稀疏的信号s，信号的重构可求解如下的欠定方程组完成

该问题的求解可转化为l0范数的问题

但是解决方程(5)需要穷举出s中所有的k个非零位置值，至少需要ckN种可能，因而l0范数下的优化方法是一个NP问题.可以把问题转化为求l1范数以简化运算［6］，

该优化算法是一个凸优化的过程，可以简化为线性规划的问题.可以通过BP(Basic Pursuit)算法、MP(Match Pursuit)算法来完成.本文对图像的重构采用正交匹配追踪(OMP算法)来完成.

3 图像压缩感知及复原的步骤

本文实现的是二维灰度图形的感知压缩，所用的图像为256×256的Cameraman灰度图像，图像为bmp格式，8位位深.为便于表示，原图像用矩阵的形式记为X.

3.1 由Harr小波实现对原始图像的稀疏变换.

为了更好地实现压缩，对原图进行四级Harr正交变换，以增加其稀疏性，同时应用结构简单的Harr小波基也能简化运算.本文使用Matlab编制了子函数HarrMatrix()实现对原图像的四级Harr变换.变换后的矩阵记为Z，原图及变换后的结果见图1.

图1 Cameraman原图及Harr变换图Fig.1Original image of Cameraman and its Harr transforming images

3.2 测量矩阵的选择

在满足约束等容条件时，采用伯努利对称分布形式的测量矩阵C以简化运算.生成该矩阵的Matlab语句为“C=binornd(1，.5，M，b);”，M，b分别为测量矩阵的大小，M代表行，b代表列.因为变换域图像一列的较大系数值(k值)处于30～40(相对于256)之间，根据公式M＞cklog(N/k)，为3～4倍的k值，所以M取为192.这样，便能生成满足条件的测量矩阵，其大小为192×256.

3.3 利用正交匹配追踪算法恢复Harr变换后图像

利用测量矩阵同时完成对变换域图像(四级Harr变换后的图像)的采样和压缩，若采样后的数据用矩阵Y表示，则

该过程对大小为256×256图像实现了192×256的低速采样.

利用OMP算法［7］对信号进行恢复时，已知的条件为:采样观测值Y，观测矩阵C，需要恢复的信号为Z.数据恢复采用的方法是逐列形式，即用Y中的第n列，通过观测矩阵用OMP算法恢复出Z中对应的第n列.

对于Z中第n列的恢复方法如下:

(1)令残差向量r=Yn，Yn代表观测值中的第n列;

(2)用观测矩阵C各行与r进行内积运算＜r，Ci＞，i=1，…，256，找出内积最大一列(相似度与r最强)Cl，列号为l;

(3)用最小二乘法获得Z中第n列第l位置上的元素值

(4)修正残差值

在观测矩阵C中剔除掉Cl列，返回第2步确定Z的第n列中下一个待定元素值及位置，直到待定出该列全部的k个元素，该列其余位置置0.

此时，即完成Z矩阵一列数据的恢复.其他各列的恢复亦如此.待Z矩阵成功恢复后，可以通过Harr逆变换恢复出原图像矩阵X.

4 实验结果对比

我们利用上面所说的方法实现对Cameraman的压缩采样，复原后的结果见图2.图2(b)是用本文方法得到的恢复图像，可以看出恢复质量已较好，虽然低速采用中存在一定的噪声.复原后图像的峰值信噪比为30.9，和同等条件下用sym8小波、高斯观测矩阵下复原图(图2(c))相比，复原图像的质量明显优于后者，而后者的峰值信噪比为27.8.

图2 压缩感知前后图像对比Fig.2Comparisons of images before and after CS

5 总结

压缩感知理论以一种非自适应实现对图像的低速采样，打破了Nyquist香浓采样定理的极限，并能较好地实现信号的恢复.但压缩感知理论在降低采样率的同时，却是以较高的运算复杂度为代价的.作为一种较新的理论，压缩感知理论正被广泛地关注着，新的思路、新的算法不断出现，正以旺盛的生命力向前发展.

［1］RICHARD G.B Compressive sensing［J］.IEEE Signal Processing Magazine，2007，24(4):118－121.

［2］DONOHO D L.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52(4):1289－1306.

［3］CAND E'S E.Compressive sampling［C］//EMAMNUEL J C.Proceedings of International Congress of Mathematicians.Switzerland:European Mathematical Society Publishing House，2006:1433－1452.

［4］CAND E'S E，ROMBERG J，TAO T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transactions on Information Theory，2006，52(2):489－509.

［5］MARCO F D，MARK A D，DHARMPAL T，et al.Single-pixel imaging via compressive sampling［J］.IEEE Signal Processing Magazine，2008: 83－91.

［6］李树涛，魏丹.压缩传感综述［J］.自动化学报:2009，35(11):1369－1375.

［7］MALLAT S，ZHANG Z.Matching pursuit with time-frequency dictionaries［J］.IEEE Trans On Signal Processing，1993，41(12):3397－3415.

Gray Image Compression Based on CS

ZHANG Xi-min1，2，ZHUO Dong-Feng2，LIU Guo-yang2，LI Qiu-guo2

(1.Department of Physics，Henan Institute of Education，Zhengzhou 450046，China; 2.School of Electronic Information Engineering，Taiyuan University of Science and Technology，Taiyuan 030024，China)

By new theory of compression sensing，realizes compressing gray image at a lower sampling rate through Harr sparse orthogonal transformation and Bonuli observation matrix，and restores compressed data by algorithm of orthogonal match pursuit.The experiments show that this method realizes compression sensing quite well.

Harr wavelet;compression sensing;sparse;non-adaptive;orthogonal match pursuit

TP391.41

A

1007－0834(2011)03－0037－03

10.3969/j.issn.1007－0834.2011.03.013

2011－04－27

河南省教育厅自然科学研究计划项目(2009B510007)

张习民(1972—)，男，河南宝丰人，河南教育学院物理系讲师、太原科技大学电子信息工程学院在读硕士研究生.