２００8年第32卷第12期（总第322期）
电视技术
Y 解码端
接收数据
Y 解码重构
恢复信号
X
赞文章编号：１００２－８６９２（２００8）12-0016-03
压缩感知理论简介*
喻玲娟1，谢晓春2，3
（1.华南理工大学电子与信息学院，广东广州510640；2.赣南师范学院物理与电子信息学院，江西赣州341000；
3.中国科学院空间科学与应用研究中心，北京100190）
【摘
要】压缩感知（CS ）理论是在已知信号具有稀疏性或可压缩性的条件下，对信号数据进行采集、编解码的新理论。主要阐述了
CS 理论框架以及信号稀疏表示、CS 编解码模型，并举例说明基于压缩感知理论的编解码理论在一维信号、二维图像处理上的应用。
【关键词】压缩感知；稀疏表示；编码；解码；受限等距特性【中图分类号】TN919.81
【文献标识码】A
Brief Introduction of Compressed Sensing Theory
YU Ling-juan 1，XIE Xiao-chun 2,3
（1.School of Electronic and Information Engineering,South China University of Teconology,Guangzhou 510640,China ;
2.School of Physics and Electronic Information,Gannan Normal University,Jiangxi Ganzhou 341000,China ;
3.Center for Space Science and Applied Research,Chinese Academy of Sciences,Beijing 100190,China ）
【Abstract 】Compressed Sensing(CS)theory is a novel data collection and coding theory under the condition that signal is sparse
or compressible.In this paper,the CS framework,CS coding model are introduced,after which the application of CS theory in one-dimensional signal and two-dimension image are illustrated.
【Key words 】compressed sensing;sparse presentation;encoding;decoding;restricted isometry property
·综述·
1
引言
过去的几十年间，传感系统获取数据的能力不断地
得到增强，需要处理的数据量也不断增多，而传统的
Nyquist 采样定理要求信号的采样率不得低于信号带宽的2倍，这无疑给信号处理的能力提出了更高的要求，也给相应的硬件设备带来了极大的挑战。寻新的数据采集、处理方法成为一种必然。2004年，由Donoho 与
Candes 等人提出的压缩感知（Compressed Sensing ，CS ）理论是一个充分利用信号稀疏性或可压缩性的全新信号采集、编解码理论
[1-2]
。该理论表明，当信号具有稀疏性或
可压缩性时，通过采集少量的信号投影值就可实现信号的准确或近似重构。CS 理论的提出是建立在已有的盲源分离和稀疏分解理论基础上的。盲源分离为CS 理论提供了在未知源信号的情况下，通过测量编码值实现信号重构的思路；稀疏分解中的具体算法已直接被CS 解码重构所用。
2CS 理论框架
CS 理论是编解码思想的一个重要突破。传统的信号
采集、编解码过程如图1所示：编码端先对信号进行采样，再对所有采样值进行变换，并将其中重要系数的幅度和位置进行编码，最后将编码值进行存储或传输；信
号的解码过程仅仅是编码的逆过程，接收的信号经解压缩、反变换后得到恢复信号。这种传统的编解码方法存在两个缺陷：1）由于信号的采样速率不得低于信号带宽的2倍，这使得硬件系统面临着很大的采样速率的压力；2）在压缩编码过程中，大量变换计算得到的小系数被丢弃，造成了数据计算和内存资源的浪费。
CS 理论的信号编解码框架和传统的框架大不一样，如图2所示。CS 理论对信号的采样、压缩编码发生在同一个步骤，利用信号的稀疏性，以远低于Nyquist 采样率的速率对信号进行非自适应的测量编码。
测量值并非信号本身，而是从高维到低维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的
*江西省教育厅青年科学基金项目（GJJ09581）
图1传统编解码理论的框图
编
码端X 采样变换、压缩编码
信号
Y
解码端
接收数据
Y
解压缩、反变换
恢复信号
X
赞16
ＶＩＤＥＯＥＮＧＩＮＥＥＲＩＮＧ
Ｎｏ．12Vol.32２００8（Sum Ｎｏ．322）少量信息。解码过程不是编码的简单逆过程，而是在盲源分离中的求逆思想下，利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构[1]，解码所需测量值的数目远小于传统理论下的样本数。
3
信号的稀疏表示
由于CS 理论的前提条件是信号具有稀疏性或可压
缩性，为使模型简单化，只考虑长度为N 的离散实值信号x ，记为x （n ），n ∈[1，2，…，N ]。由信
号理论可知x 能够用一组基ΨT
=[ψ1，ψ2，…，ψm ，…，ψM ]的线性组合表示（其中ΨT
代表Ψ的转置），则
x =N
k =1
ΣΨk αk =Ψα
（1）
式中：αk =<x ，Ψk >，α与x 是N ×1矩阵，Ψ是N ×N 矩阵。当信号x 在某个基Ψ上仅有K 垲N 个非零系数（或远大于零的系数）αk 时，称Ψ为信号x 的稀疏基。
信号在稀疏基上只有K 个非零系数属于严格稀疏的情况，多数情况下信号无法满足严格稀疏的要求，但仍具有可压缩性，即信号的变换系数经排序后可以指数级进行衰减趋近于零时，信号也是可以近似稀疏表示的。合理地选择稀疏基Ψ，使得信号的稀疏系数个数尽可能少，不仅有利于提高采集信号的
速度，而且有利于减少存储、传输信号所占用的资源。常用的稀疏基有：正（余）弦基、小波基、chirplet 基以及curvelet 基等。
4CS 测量编码的模型
在CS 编码测量模型中，并不是直接测量稀疏信号
x 本身，而是将信号x 投影到一组测量向量Φ＝[φ1，φ2，…，φm ，…，φM ]上，而得到测量值y m =<x ，φm T >。写成矩阵形式为
y=Φx
（2）
式中：x 是N ×1矩阵，y 是M ×1矩阵，Φ是M ×N 的测量矩
阵。将式（1）代入（2），有稀疏编码
y=Φx=ΦΨα=Θα（3）
式中：Θ=ΦΨ是M ×N 矩阵。
由于测量值维数M 远远小于信号维数N ，求解式（2）的逆问题是一个病态问题，所以无法直接从y 的M 个测量值中解出信号x 。而由于式（3）中α是K 稀疏的，即仅有K 个非零系数，而且K<M 垲N ，那么利用信号稀疏分解理论中已有的稀疏分解算法，可以通过求解式（3）的逆问题得到稀疏系数α，再代回式（1）进一步得到信号x 。Candes 等人在文献[3]中指出，为了保证算法的收
敛性，使得K 个系数能够由M 个测量值准确地恢复，式（3）中矩阵Θ必须满足受限等距特性（RIP ）准则，即对于任意具有严格K 稀疏（可压缩情况时，要求是3K ）的矢量v ，矩阵Θ都能保证如下不等式成立
1-ε≤‖Θv ‖2‖v ‖2
≤1+ε
（4）
式中ε>0。RIP 准则的一种等价的情况是测量矩阵Φ和
稀疏矩阵Ψ满足不相关性的要求[1，3-4]。
实际测量中稀疏基Ψ可能会因信号的不同而改变，因此希望到对任意的稀疏基Ψ都能满足和测量基Φ
不相关。对一维信号而言，测量矩阵Φ选取服从高斯分布的基矢量能保证和任意稀疏基Ψ不相关的概率很高，类似的矩阵还有Bernouli 矩阵等[2]。对二维图像，有文献
提出了能快速计算随机扰动的部分傅立叶变换矩阵[5]、随机扰动的Hadamard 矩阵[6]等。
5CS 解码重构的模型
当式（3）中的矩阵Θ满足RIP 准则时，CS 理论能够
通过对式（3）的逆问题先求解稀疏系数α=ΨT
x ，后代入式（1）将稀疏度为K 的信号x 从M 维的测量投影值y 中正确地恢复出来[1-2]。解码的最直接方法是通过l 0范数下求解式（3）的最优化问题
min a
‖α‖l
s.t .y =ΦΨα（5）
从而得到稀疏系数的估计。由于（5）式的求解是个
NP-hard 问题，而该最优化问题与信号的稀疏分解中的十分类似，所以有学者从信号稀疏分解的相关理论中寻更有效的求解途径。文献[7]表明，l 1最小范数下在一定条件下和l 0最小范数具有等价性，可得到相同的解。那么（5）式转化为l 1最小范数下的最优化问题
min a
‖α‖l
1
s.t .y =ΦΨα（6）
l 1最小范数下最优化问题又称为基追踪（BP ），其常用实现算法有：内点法和梯度投影法。内点法速度慢，但得到的结果十分准确；而梯度投影法速度快，但没有内点法得到的结果准确[8]。二维图像的重构中，为充分利用图像的梯度结构，可修正为整体部分（Total Variation ，
TV ）最小化法。由于l 1最小范数下的算法速度慢，新的快速贪婪法被逐渐采用，如匹配追踪法（MP ）[9]和正交匹配追踪法（OMP ）[4]。此外，有效的算法还有迭代阈值法[10]以及各种改进算法。
6
CS 理论的应用举例
6.1
一维信号情况下的实验仿真
源信号是一维离散稀疏信号，长度N =256，选余弦基
17
２００8年第32卷第12期（总第322期）
电视技术
为稀疏基，得到稀疏个数K ＝30。在基于CS 理论的编解码框架中，编码端采用高斯测量矩阵，解码端采用OMP 法进行恢复重构。仿真实验首先观察CS 理论下测量值数量对信号重建效果的影响。由图3可知，当测量值的
数量M 增加时，信号成功恢复的概率同步增加。而且当样本数目达到M =110时，信号已经能够准确恢复。此时由图4可以看出信号得到了准确的解码重构。
6.2二维图像情况下的实验仿真
源图像为256×256的boat 图，选小波基为稀疏基。
基于CS 理论的编解码框架中，测量编码端采用分块（块大小为32×32）Hadamard 测量矩阵，解码端基于TV 最小化的梯度投影法进行恢复重构。图像的测量样本数M =
25000，其重构结果如图5a 所示。在传统的编解码理论下，对图像小波变换后保留其中的25000个大系数进行编码，后进行解码、反变换重建，其结果如图5b 所示。仿真结果表明，在编码端的测量值个数相同的情况下，CS 理论下的恢复图像PSNR 达到27.9dB ，远远高于传统编
解码的15.49dB 。
7
小结
笔者主要阐述了CS 理论框架，以及基于CS 理论的
编解码模型。通过对一维信号、二维图像进行编解码的仿真实验说明了CS 理论是一种能够使用少量测量值实现信号准确恢复的数据采集、编解码理论。由于CS 理论对处理大规模稀疏或可压缩数据具有十分重要的意义，所以该理论提出后在许多研究领域得到了关注。目前，国外研究人员已开始将CS 理论用于压缩成像、医学图像、模数转换、雷达成像、天文学、通信等领域。作为国外刚出现的新理论，CS 理论的研究方兴未艾，将有着更广泛的应用前景。参考文献
[1]DONOHO D.Compressed sensing[J].IEEE Trans.Information The -
ory,2006,52(4):1289-1306.
[2]CANDES E.Compressive sampling[C]//Proceedings of the Interna -tional Congress of Mathematicians.Madrid,Spain:[s.n.],2006:1433-1452.
[3]CANDES E,ROMBERG J,TAO T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency informa -tion[J].IEEE Trans.Information Theory,2006,52(4):489-509.[4]TROPP J,GILBERT A C.Signal recovery from random measure -ments via orthogonal matching
pursuit [J].
IEEE Trans.
Information
Theory,2007,53(12):4655-4666.
[5]ZOU J,GILBERT A C,STRAUSS M J,et al.Theoretical and ex -perimental analysis of a randomized algorithm for sparse Fourier trans -form analysis[J].Journal of Computational Physics,2006,211(2):572-595.
[6]GAN Lu.Block compressed sensing of natural images[C]//Proceed -ings of the International Conference on Digital Signal Processing.[S.l.]:IEEE Press,2007:403-406.
[7]DONOHO D,TSAIG Y.Extensions of compressed sensing[J].Signal Processing,2006,86(3):533-548.
[8]FIGUEIREDO M A T,NOWAK R D,WRIGHT S J.Gradient pro -jection for sparse reconstruction:application to compressed sensing and other inverse problems[J].IEEE J-STSP,2007,1(4):586-598.
[9]TROP J A.Greed is good:algorithmic results for sparse approxi -mation[J].IEEE Trans.Information Theory,2004,50(10):2231-2242.[10]FORNASIER M,RAUHUT H.Iterative thresholding algorithms[J].Applied and Computational Harmonic Analysis,2008,25(2):187-208.
笕
作者简介：
喻玲娟（1982－），硕士生，研究方向为视频图像处理；
谢晓春（1975－），副教授，从事信号与信息处理方面的研究。责任编辑：哈宏疆
收稿日期：2008-11-11
图5CS 与传统编解码boat 图恢复效果比较
（a ）CS 方式（b ）传统方式
图4源信号、解码重构稀疏系数、解码重构信号图
（a ）源信号，长度N =256
（b ）CS 解码重构得到K =30个稀疏系数
（c ）CS 解码重构后信号，长度N =25618
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议