基于压缩感知视频编解码的论文.docx

1、AbstractThis work aims to based on compressed sensing theory analysis, implementation of distributed video coding. According to the requirements of distributed coding complexity, combined with compressed sensing theory and the traditional video coding and decoding technology, is put forward based on

2、 compressed sensing of distributed video coding: Encoding process that high dimensional signal be projected to a lower dimensional space; decoding project is no longer under the traditional manner of coding inverse process, but through the establishment of joint sparse model, solving the underdeterm

3、ined equations. The codec is relatively simple structure, not only the desired image fewer samples, the number of samples may be different according to the coding mode is selected, and can obtain higher compression ratio and better the quality of the reconstructed image. The experiment result shows

4、that, by introducing adaptive coding mechanism, not only can optimize the performance of RD, and without feedback channel is achieved close to the traditional inter-frame coding properties of reconstruction.Keywords: CS; Distributed decoding algorithm; Encoder; Decoder目录1.绪论61.1引言61.2研究背景及发展现状71.2.1

5、压缩感知71.2.2压缩感知技术在分布式编解码内71.2.3分布式视频编解码81.3论文的主要内容和组织结构92压缩感知理论极其研究进展92.1奈奎斯特（Nyquist）采样定理92.2压缩感知理论框架及其主要进展102.2.1问题描述102.2.2信号的稀疏表示122.2.3观察矩阵的设计142.2.4信号重构162.3压缩感知理论的推广及应用222.3.1信号在冗余字典上的压缩感知理论222.3.2压缩感知理论初步应用223基于压缩感知的分布式视频编解码243.1基于压缩感知的视频编解码研究243.1.1传统的视频编解码核心技术243.1.2基于压缩感知理论的编解码器253.2帧内与帧间采

6、样率273.3分布式压缩感知研究273.4分布式视频编码(DVC)283.5分布式压缩感知编解码293.6梯度投影稀疏重建(GPSR)303.7结构化相似度(SSIM)304实验介绍324.1系统模型324.1.1压缩感知初步算法324.1.2视频模型324.2内部视频编码帧的传输335实验仿真数据375.1视频解码实验375.2无线视频传输实验375.3实验结果数据396 总结与展望431 绪论1.1 引言 随着通信技术的不断发展，在通信网络中传输视频业务变得越来越重要。而众所周知，诗篇业务的特点是本身具备很大的数据量，从而在传输过程中需要很大的带宽。与此同时，由于视频业务本身具有相当大的冗

7、余性，人们设计出各种各样的压缩办法，在视频传输之前进行大规模的压缩，现有的方法是采用MPEG系列或者H.26x系列压缩方案，将视频的序列采用预测编码和变换编码的方法进行压缩，然后将其进行信道编码而发送。这类方法在现有一些传输条件较好的网络中取得了巨大的成功。但是这种类似MPEG和H.26x方案在无线网络中传输效果并不好，究其原因，根本上是因为无线信道本身的高误码率以及误码的随机性，带宽有限等特点决定了上述编码方案并不符合无线信道本身的特性，具体来说可以分为以下两个方面：首先预测编码和变换编码的方案使得编码出来的视频帧之间具有很大的依赖性，具体来说就是假设有一关键帧在传输过程中丢失，那么后续以前

8、一帧为参考的帧都无法正确解码，这样的话会造成严重的乱码效应。其次，在视频编码工程中，编码出来的数据它们代表的意义是不一样的，也就是有一部分数据的重要性要比另一部分高很多，例如运动矢量数据就比纹理数据重要的多，当在无线信道上随机丢包的环境下，如果恰好丢的是运动矢量数据，那么在恢复的时候就难恢复出可以辨别的一帧图像出来。而当丢失的使纹理数据时，可以通过一定的算法来弥补这种丢失带来的影响。随着人们对于视频在无线信道上传输问题的不断深入，各种各样的方法也被不断地提出，其中比较典型的有以下几种：一种是编码端的改进方案，表现为在视频编码的过程中加入固定的刷新帧，以及将编码出来的码流再进行多描述编码等方案。

9、还有一种方案是解码段的差多掩盖技术，它试图利用压缩后的视频数据之间的相关性来进行高难度的恢复。从上述方案可以看出，这些方案从某种程度上改善一些视频传输的效果，但是它们并不能从源头上解决了视频在无线环境中传输所存在的硬伤，即由于视频本身所采用的压缩方案的限制。这促使我们从源头上来寻找针对于视频在无线环境中所需的编解码方法。压缩感知是近几年信号处理理论的重大突破，它打破了传统的奈奎斯特采样定理对于采样点数的限制，采用一种数字投影的方法对信号进行整体的测量，从而能够达到以较少的采样值来进行原始信号的恢复的效果，目前这一理论已经大量的用于信号处理与通信的实践中，对于视频信号，由于本身的特点，本文将压缩

10、感知的方法融入进现有的视频编解码框架。1.2 研究背景及发展现状1.2.1 压缩感知传统方式下的信号处理，依照Shannon/Nyquist采样理论采样会产生大量的采样数据，需要先获取整个信号再进行压缩，即采样后大部分采样数据被抛弃，这就极大地增加了储存和传输的代价。由于带宽的限制，许多信号只包含少量的重要频率的信息，所以大部分信号时稀疏的可压缩的，对于这种类型的信号，我们知道，传统方式采样后的大部分冗余信息都会被抛弃，那么为什么还要获取全部数据呢？难道不能直接获取已压缩数据而不需要抛弃任何数据？于是由Cands和Donoho等人于2004年提出压缩感知理论。该理论可以理解为将模拟数据节约地转

11、换成压缩数字形式，避免了资源浪费。即，在采样信号的同时就对数据进行适当的压缩，相当于在采样过程中寻找最少的系数来表示信号，并能用适当的重构算法从压缩数据中恢复出原始信号。压缩感知的主要目标是从少量的非适应线性测量中精确有效地重建信号。核心概念在于试图从原理上降低一个信号进行测量的成本。压缩感知包含了许多重要的数学理论，具有广泛的应用前景，最近几年引起广泛关注。1.2.2 在分布式编解码内的压缩感知技术现有的视频压缩编码标准是基于传统的香农采样定理。在该定理要求下，信号的采样率必须大于信号带宽的2倍才能实现信号的准确重。因此，要实现视频图像的准确重构所需要的样本数较多。此外，视频编码过程中图像变

12、换后大部分的系数被舍弃造成了数据和系统资源的浪费近年来出现的压缩感知（Compressive Sencing，CS）理论指出在已知信号具有稀疏性或可压缩性的前提下，用于重构的样本数可以远远低于传统的香农采样定理下的样本数1。由于视频图像通常在某些变换域上具有可压缩性，而且视频残差图像具有较强的稀疏性，所以CS理论在视频编码中有着良好的应用前景。1.2.3 分布式视频编解码国际标准化组织（ISO/IEC）和国际电信联盟（ITU-T）这两个标准化组织分别领导和制定了两个视频压缩编码的系列国际标准：MPEG系列和H.26系列，它们被广泛应用于视频压缩各个领域。这些视频编码技术基于混合编码框架，编码运

13、用运动估计，充分挖掘视频信号的冗余信息，通常情况下，编码复杂度是解码复杂度的5-10倍，非常适合于视频信号的一次（一个）编码而多次（多个）解码的应用场合如：视频广播、视频点播、视频光盘存储等。然而一些视频应用场合恰恰相反，它们需要低复杂度的编码器，在解码端可以具有较高复杂度的解码器，比如计算能力、内存容量、耗电量都受限的无线视频终端：无线视频监控、无线PC相机、移动视频电话等。尤其是在无线传感网络中，视频传感节点（VSN：videa sensor node）有两个基本要求：（1）要求编码器功耗低、复杂度低：（2）由于速率限制，要求编码器具有较高的压缩效率。传统的视频编码技术不再适用于上述应用场

14、合，必须寻找新的视频压缩技术。针对这些情况，一种新的视频编码框架分布式视频编码（DVC：Distributed Video Coding）开始受到关注，这种视频编码具有编码简单，解码较复杂并且能够实现较为搞笑的压缩，抗误码特性好的特点。分布式视频编码的实现算法从2002年开始有学者进行相关领域的研究，并逐渐引起关注的。目前国内很少有分布式视频编解码的相关文献。1.3 论文的主要内容和组织结构第一章为绪论，相关内容上面已经提及。第二章为压缩感知理论及其研究进展。主要包括压缩感知理论的发展过程中产生的相关理论。第三章主要讲解基于压缩感知的分布式视频编解码，主要谈论分布式编解码的模型，原理及重构算法

15、。第四章主要内容是对整个实验的一个概括介绍，包括模型机制，算法等。第五章主要对实验结果数据的分析。第六章为总结和展望，提出待解决的问题，分析理论的发展前景。2 压缩感知理论极其研究进展2.1 奈奎斯特（Nyquist）采样定理在进行模拟/数字信号的转换过程中，当采样频率fs.max大于信号中最高频率fmax的2倍时(fs.max2fmax)，采样之后的数字信号完整地保留了原始信号中的信息，一般实际应用中保证采样频率为信号最高频率的510倍；采样定理又称奈奎斯特采样定律。1924年奈奎斯特(Nyquist)就推导出在理想低通信道的最高码元传输速率的公式：理想低通信道的最高码元传输速率W=2B B

16、aud（其中W是理想）理想信道的极限信息速率（信道容量）C=B*log2 N (bps)。采样过程所应遵循的规律，又称取样定理、抽样定理。采样定理说明采样频率与信号频谱之间的关系，是连续信号离散化的基本依据。采样定理是1928年由美国电信工程师H.奈奎斯特首先提出来的，因此称为奈奎斯特采样定理。1933年由苏联工程师科捷利尼科夫首次用公式严格地表述这一定理，因此在苏联文献中称为科捷利尼科夫采样定理。1948年信息论的创始人C.E.香农对这一定理加以明确地说明并正式作为定理引用，因此在许多文献中又称为香农采样定理。采样定理有许多表述形式，但最基本的表述方式是时域采样定理和频域采样定理。采样定理在

17、数字式遥测系统、时分制遥测系统、信息处理、数字通信和采样控制理论等领域得到广泛的应用。2.2 压缩感知理论框架及其主要进展2.2.1 问题描述考虑一个实值的有限长一维离散时间信号X，可以看作为一个RN空间N1的维的列向量，元素Xn,n=1，2，N.RN空间的任何信号都可以用N1维的基向量的线性组合表示。为简化问题，假定这些基是规范正交的。把向量作为列向量形成NN的基矩阵：=1，2，N，于是任意信号X都可以表示为： or (1)其中，是投影系数=i=构成的N1的列向量。显然，X和是同一个信号的等价表示，X是信号在时域的表示，则是信号在域的表示。如果的非零个数比N少很多，则表明该信号是可压缩的。一

18、般而言，可压缩信号是指K个大系数很好地逼近的信号，即它在某个正交基下的展开的系数按一定量级呈现指数衰减，具有非常少的大系数和许多小系数。这种通过变换实现压缩的方法称为变换编码。变换编码在数据采样系统中，比如数码相机，发挥了重要作用。在这些系统中，采样速率高但信号时可压缩的，采样得到N点采样信号X；通过=TX变换后计算出完整的变换系数集合i；确定K个大系数位置，然后扔掉N-K个小系数；对K个大系数的值和位置进行编码，从而达到压缩的目的。图2.1 传统方法压缩过程显然，这种传统的以奈奎斯特采样定理为准则的高速采样后再压缩的过程浪费了大量的采样资源。例如数码相机具有千万像素的图像传感器，最后却只使用

19、到对图像进行变换压缩后的几Mbyte的数据5。近几年兴起的压缩感知理论表明，可以在不丢失逼近原信号所需信息的情况下，用最少的观测次数来采样信号，实现信号的降维处理，即直接对信号进行较少采样得到信号的压缩表示，且不经过进行N次采样的中间阶段，从而在节约采样和传输成本的情况下，达到了在采样的同时进行压缩的目的。压缩感知理论首先由Cands、Romberg、Tao进而Donoho等人在2004年提出，文献直到2006年才发表。Cands证明了只要信号在某一正交空间具有稀疏性，能以较低的频率(MN)信号，而且可以以高概率重构该信号。目前国内已经有科研单位的学者对其展开研究，如西安电子科技大学课题组基于

20、该理论提出采用超低速率采样检测超宽带回波信号。压缩感知理论指出，设长度为N的信号X在某组正交基或紧框架上的变换系数是稀疏的，如果我们用一个与变换基不相关的观测基: MN(MN)对系数向量进行线性变换，并得到观测集合Y: M1. 那么就可以利用优化求解方法从观测集合中精确或离概率地重构原始信号X。压缩感知理论是一种新的在采样的同时实现压缩目的的理论框架，其压缩采样过程如图2所示。首先，如果信号XRN在某个正交基或紧框架上是可压缩的，求出变换系数 =TX，是的等价或逼近的稀疏表示；第二步，设计一个平稳的、与变换基不相关的MN维的观测矩阵，对进行观测得到观测集合Y= = TX，该过程也可以表示为信号

21、X通过矩阵ACS进行非自适应观测:Y= ACSX（其中ACS= T），ACS称为CS信息算子；最后，利用0-范数意义下的优化问题求解X的精确或近似逼近： (2)求得的向量在基上的表示最稀疏。压缩感知理论主要涉及以下几个方面的内容: 1) 对于信号XRN，如何找到某个正交基或紧框架，使其在上的表示是稀疏的, 即信号的稀疏表示问题。2) 如何设计一个平稳的、与变换基不相关的MN维的观测矩阵, 保证稀疏向量从N维降维到M维时重要信息不遭破坏，即信号低速采样问题。3) 如何设计快速重构算法,从线性观测Y= ACSX中恢复信号，即信号重构问题。下面将从这三个方面介绍压缩感知理论的最新发展。图2.2 压缩

22、感知理论框架2.2.2 信号的稀疏表示从傅立叶变换到小波变换再到后来兴起的多尺度几何分析（Ridgelet6，Curvelet7，Bandelet8，Contourlet9），科学家们的研究目的均是为了研究如何在不同的函数空间为信号提供一种更加简洁、直接的分析方式，所有这些变换都旨在发掘信号的特征并稀疏表示它，或者说旨在提高信号的非线性函数逼近能力，进一步研究用某空间的一组基表示信号的稀疏程度或分解系数的能量集中程度。文献给出稀疏的数学定义：信号X在正交基下的变换系数向量为=TX，假如对于0p0，这些系数满足： (3)则说明系数向量在某种意义下是稀疏的。文献给出另一种定义：如果变换系数i=的支

23、撑域i：i0的势小于等于K，则可以说信号X是K-项稀疏。如何找到信号最佳的稀疏域？这是压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Cands和Tao研究表明，满足具有幂次(power-law)速度衰减的信号，可利用压缩感知理论得到恢复，并且重构误差满足： (4)其中r=1/p-1/2，0p1。文献指出光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor系数及具有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性，可以通

24、过压缩感知理论恢复信号。如何找到或构造适合一类信号的正交基，以求得信号的最稀疏表示，这是一个有待进一步研究的问题。Peyr把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典。即在某个正交基字典里，自适应地寻找可以逼近某一种信号特征的最优正交基，根据不同的信号寻找最适合信号特性的一个正交基，对信号进行变换以得到最稀疏的信号表示。文献指出光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor系数及具有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性，可以通过压缩感知理论恢复信号。如何找到或构造适合一类信号的正交基，以求得信号的最稀疏表示，这是一

25、个有待进一步研究的问题。Peyr把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典10。即在某个正交基字典里，自适应地寻找可以逼近某一种信号特征的最优正交基，根据不同的信号寻找最适合信号特性的一个正交基，对信号进行变换以得到最稀疏的信号表示。最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。这是一种全新的信号表示理论: 用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。字典的选择应尽可能好地符合被逼近信号的结构，其构成可以没有任何限制。从冗余字典中找到具有最佳线性组合的K项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近11。目前信号在冗余字

26、典下的稀疏表示的研究集中在两个方面： 1) 如何构造一个适合某一类信号的冗余字典；2) 如何设计快速有效的稀疏分解算法。这两个问题也一直是该领域研究的热点，学者们对此已做了一些探索，其中，以非相干字典为基础的一系列理论证明得到了进一步改进。笔者也对稀疏表示问题进行了认真研究，并基于多组正交基级联而成的冗余字典提出一种新的稀疏分解方法。 从非线性逼近角度来讲，信号的稀疏逼近包含两个层面: 一是根据目标函数从一个给定的基库中挑选好的或最好的基；二是从这个好的基中挑选最佳的K项组合。从冗余字典的构成角度来讲，文献中提出使用局部Cosine基来刻画声音信号的局部频域特性；利用bandlet 基来刻画图

27、像中的几何边缘。还可以把其它的具有不同形状的基函数归入字典，如适合刻画纹理的Gabor基、适合刻画轮廓的Curvelet 基等等。从稀疏分解算法角度来讲，在音视频信号处理方面，基于贪婪迭代思想的MP(MatchingPursuit) 算法表现出极大的优越性12，但不是全局最优解。Donoho等人另辟蹊径，提出了基追踪(basis pursuit, BP) 算法。BP算法具有全局最优的优点，但计算复杂度极高，例如对于长度为8192的信号，采用小波字典分解，等价于求解一个长度为8192212992的线性规划。MP算法虽然收敛速度较BP快，但不具备全局最优性，且计算复杂度仍然很大。之后又出现了一系列

28、同样基于贪婪迭代思想的改进算法，如正交匹配追踪算法(OMP)12，树形匹配追踪(TMP)13，分段匹配追踪(StOMP)14 算法等。2.2.3 观察矩阵的设计压缩感知理论中，通过变换得到信号的稀疏系数向量=TX后，需要设计压缩采样系统的观测部分，它围绕观测矩阵展开。观测器的设计目的是如何采样得到M个观测值，并保证从中能重构出长度为N的信号X或者基下等价的稀疏系数向量。显然，如果观测过程破坏了X中的信息，重构是不可能的。观测过程实际就是利用MN观测矩阵的M个行向量对稀疏系数向量进行投影，即计算和各个观测向量之间的内积，得到M个观测值yj=(j=1,2, .,M)，记观测向量Y=(y1,y2,y

29、M)，即 (5)图3(a)是(5)式的形象描述。这里，采样过程是非自适应的，也就是说，无须根据信号X而变化，观测的不再是信号的点采样而是信号的更一般的K线性泛函。对于给定的Y从式(5)中求出是一个线性规划问题，但由于MN, 即方程的个数少于未知数的个数，这是一个欠定问题，一般来讲无确定解。然而，如果具有K-项稀疏性(KM)，则该问题有望求出确定解。此时，只要设法确定出中的K个非零系数i的合适位置，由于观测向量Y是这些非零系数i对应的K个列向量的线性组合，从而可以形成一个MK的线性方程组来求解这些非零项的具体值。对此，有限等距性质(Restricted Isometry Property, RI

30、P)给出了存在确定解的充要条件。这个充要条件和Cands、Tao等人提出的稀疏信号在观测矩阵作用下必须保持的几何性质相一致。即，要想使信号完全重构，必须保证观测矩阵不会把两个不同的K-项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。从中可以看出，问题的关键是如何确定非零系数的位置来构造出一个可解的MK线性方程组。然而, 判断给定的ACS是否具有RIP性质是一个组合复杂度问题。为了降低问题的复杂度，能否找到一种易于实现RIP条件的替代方法成为构造观测矩阵的关键。文献指出如果保证观测矩阵和稀疏基不相干，则ACS在很大概率上满足RIP性质。不相干是指向量

31、j不能用j稀疏表示。不相干性越强，互相表示时所需的系数越多；反之, 相关性则越强。通过选择高斯随机矩阵作为即可高概率保证不相干性和RIP性质。例如，可以生成多个零均值、方差为1/N的随机高斯函数，将它们作为观测矩阵的元素j，使得ACS以很高的概率具有RIP性质。随机高斯矩阵具有一个有用的性质：对于一个MN的随机高斯矩阵，可以证明当McKlog(N/K)时T=ACS在很大概率下具有RIP性质（其中c 是一个很小的常数）。因此可以从M个观测值Y= (y1, y2, . . . ,yM)中以很高的概率去恢复长度为N的K-项稀疏信号。总之，随机高斯矩阵与大多数固定正交基构成的矩阵不相关，这一特性决定了

32、选它作为观测矩阵，其它正交基作为稀疏变换基时，ACS满足RIP性质. 为进一步简化观测矩阵，在某些条件下，以随机1为元素构成的Rademacher矩阵也可以证明具有RIP性质和普适性。目前，对观测矩阵的研究是压缩感知理论的一个重要方面。在该理论中，对观测矩阵的约束是比较宽松的，Donoho在文献中给出了观测矩阵所必需具备的三个条件，并指出大部分一致分布的随机矩阵都具备这三个条件，均可作为观测矩阵，如：部分Fourier集、部分Hadamard集、一致分布的随机投影(uniformRandom Projection)集等，这与对RIP性质进行研究得出的结论相一致。但是，使用上述各种观测矩阵进行观

33、测后，都仅仅能保证以很高的概率去恢复信号，而不能保证百分之百地精确重构信号。对于任何稳定的重构算法是否存在一个真实的确定性的观测矩阵仍是一个有待研究的问题。文献则从信息论角度描述了信息论与CS之间的联系。它指出，在模拟系统中，观测噪声也是影响观测次数的重要因素，为说明这一点，作者从信息论的角度研究了稀疏信号的率失真函数，给出了观测噪声对信号重建效果的影响。图2.3 (a)随机高斯矩阵作为观测矩阵，稀疏域选择DCT变换域，对信号X进行DCT变换后再进行观测。(b)(a)图的另一种表达，变换后的系数向量是稀疏的，K=3，观测得到的Y是非零系数i对应的四个列向量的线性组合。（注：黑色方块表示非零大系

34、数，白色表示零系数，浅灰色表示接近零的小系数）2.2.4 信号重构在压缩感知理论中，由于观测数量M远小于信号长度N，因此不得不面对求解欠定方程组Y= ACSX的问题。表面上看，求解欠定方程组似乎是无望的，但是，文献中均指出由于信号X是稀疏的或可压缩的，这个前提从根本上改变了问题，使得问题可解，而观测矩阵具有RIP性质4也为从M个观测值中精确恢复信号提供了理论保证。为更清晰地描述压缩感知理论的信号重构问题，首先定义向量X=x1,x2,xn的p-范数为： (6)当p=0时得到0-范数，它实际上表示X中非零项的个数。于是，在信号X稀疏或可压缩的前提下，求解欠定方程组Y=ACSX的问题转化为最小0-范

35、数问题： (7)但是，它需要列出X中所有非零项位置的种可能的线性组合，才能得到最优解。因此，求解式(7)的数值计算极不稳定而且是NP难度问题。注意，这和稀疏分解问题从数学意义上讲是同样的问题。于是稀疏分解的已有算法可以应用到CS重构中。Chen,Donoho和Saunders指出，求解一个更加简单的l1优化问题会产生同等的解（要求和不相关）： (8)稍微的差别使得问题变成了一个凸优化问题，于是可以方便地化简为线性规划问题，典型算法代表：BP算法。尽管BP算法可行，但在实际应用中存在两个问题: 1) 即使是常见的图像尺寸，算法的计算复杂度也难以忍受，在采样点个数满足McK，c log2(N/K+

36、1)时，重构计算复杂度的量级在O(N3)；2) 由于1-范数无法区分稀疏系数尺度的位置，所以尽管整体上重构信号在欧氏距离上逼近原信号，但存在低尺度能量搬移到了高尺度的现象，从而容易出现一些人工效应，如一维信号会在高频出现振荡。基于上述问题, 2005年1月Cands和Romberg提出了不同的信号恢复方法，该方法要求对原信号具有少量的先验知识，同时也可以对所求结果施加适当的期望特性，以约束重构信号的特性。通过在凸集上交替投影(Projections ontoConvexSets)的方法，可以快速求解线性规划问题。Tropp和Gilbert提出利用匹配追踪(MP)和正交匹配追踪(OMP)算法来求

37、解优化问题重构信号，大大提高了计算的速度，且易于实现。树形匹配追踪(TMP)算法是2005年La和N Do提出的。该方法针对BP、MP和OMP方法没有考虑信号的多尺度分解时稀疏信号在各子带位置的关系，将稀疏系数的树型结构加以利用，进一步提升了重构信号的精度和求解的速度。匹配追踪类算法都是基于贪婪迭代算法，以多于BP算法需要的采样数目换取计算复杂度的降低。例如OMP算法，需要McK，c2ln(N)个采样点数才能以较高的概率恢复信号，信号重构的计算复杂度为O(NK2)。2006年Donoho等人提出了分段正交匹配追踪(StOMP，stagewiseOMP)算法。它将OMP进行一定程度的简化，以逼近

38、精度为代价进一步提高了计算速度(计算复杂度为O(N)，更加适合于求解大规模问题。Hale, Yin基于分裂( Operator-Splitting) 算子和同伦算子( Homotopy Algorithms)，提出了求解最小1-范数大规模问题的方法，适用于求解纠错编码、磁共振成像、NMR波谱研究等领域的大规模问题。在上述各种方法中，观测矩阵中的所有值都非零，这样信号采样过程的计算量是O(MN)，在大规模的数据面前，这个量级还是非常大的。因此一类利用稀疏矩阵作为观测矩阵进行采样的方法出现了。Cormode等人，提出利用分组测试和随机子集选取来估计稀疏信号的非零系数的位置和取值，该方法需要的采样数

39、为M=O(Klog2N)，信号重构的计算复杂度为O(Klog2N)，得到重构信号的速度更快。Gilbert等人在2006年4月提出了链式追踪(CP,Chaining Pursuit )方法来恢复可压缩信号。 利用O(Klog2N)个采样观测重构信号，需要计算量为O(Klog2Nlog2K)，该方法对特别稀疏信号的恢复计算性能较高，但当信号的稀疏度减少，需要的采样点数会迅速增加，甚至超过信号本身的长度，这就失去了压缩采样的意义。总之，目前为止出现的重构算法都可归入以下三大类：1) 贪婪追踪算法：这类方法是通过每次迭代时选择一个局部最优解来逐步逼近原始信号。这些算法包括MP算法，OMP算法，分段O

40、MP算法( StOMP)和正则化OMP(ROMP)算法。2) 凸松弛法：这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，如BP算法，内点法，梯度投影方法和迭代阈值法。3) 组合算法：这类方法要求信号的采样支持通过分组测试快速重建，如傅立叶采样，链式追踪和HHS(HeavgHitters onSteroids)追踪等。可以看出，每种算法都有其固有的缺点。凸松弛法重构信号所需的观测次数最少，但往往计算负担很重。贪婪追踪算法在运行时间和采样效率上都位于另两类算法之间。由上面的分析可知，重构算法和所需的观测次数密切相关。当前，压缩感知理论的信号重构问题的研究主要集中在如何构造稳定的、计算复杂度较

41、低的、对观测数量要求较少的重构算法来精确地恢复原信号。2.2.4.1 MMV-SBL图像重建算法根据上一节介绍的压缩感知理论，将一幅NN自然图像表示成X（实际上图像的行数和列数不需要相等，这里只是为了表述上的方便），其对应的NN加权系数矩阵为S，MN噪声矩阵为E，MN观测矩阵为Y，则对于图像信号式可以写为下式。 (1)其中S=s.1|s.2|s.N，Y= y.1|y.2| y.N，E=1|2|N。为了表述方便，分别用s.j 和si.来表示S的第j个列向量和第i个行向量。Y中的每一列对应一个一维的观测向量，因此上式是一个多观测向量模型，其与单观测向量式对应的形式可以写成下式。 (2)在以前的压缩

42、感知理论研究中，大多数学者在实际处理图像信号时都会将二维的图像信号转换成一维信号处理。比如将NN图像的每一列首尾相接组成一个N21的列向量，这样相当于在单观测向量下处理一个长的一维信号，如上式所示，但是这种情况下测量矩阵的尺度非常大，将显著增加计算量和存储空间，处理时间会很长。为了不增加的尺度，可以将图像的每一列作为一个N1的一维信号单独处理，如式(2)所示得到一个M1的观测向量，重建图像的每一列后再重组成二维的图像，这样做比前一种方法大幅度的减少了计算量和存储空间，是目前实际应用中用得比较多的方法，但是算法运行仍然需要较多时间。与上述两种方法不同，本文采用多观测向量模型式(1)，观测矩阵Y的

43、每一列对应一个观测向量，通过稀疏贝叶斯算法对所有的观测向量同时进行处理以重建图像的每一列，从而提高了算法效率。对于一幅非稀疏的自然图像，通过小波变换基矩阵可以得到其加权系数矩阵S，选取固定的测量矩阵，如式(1)所示，得到观测矩阵Y.根据稀疏贝叶斯算法，假设式(1)中的噪声为均值为零，方差为2的高斯噪声，si.的先验分布是方差为Y.i的高斯分布，则式(2)中y.j的似然函数和si.的先验分布分别为式(3)和式(4)。对于加权系数矩阵S，则有式(5)。 (3) (4) (5)其中，=1,2,NT是N维的超参数向量。S.j的后验分布为式(6)。 (6)其均值和方差分别为 (7)， (8)其中，均值M

44、作为加权系数矩阵S的一个点估计，即= M。为了求得均值，需要求得超参数向量的估计，它可以通过最大化p(Y;)获得。 (9)其中，为了方便求解，对上式进行适当转化，利用最大似然估计求解超参数向量等价于最小化-2logp(Y,)，则式(9)可以写为 (10)定义求解超参数向量的代价函数为 (11)根据文献中附录部分的方法，对式(11)求偏导数，得到超参数的迭代方程式 (12)在实际的求解运算中，很多超参数Yi都会收敛于零。当i=0时，p(si.,i,=0)=(si.), 使得后验分布满足Prob(si.=0|Y,i=0)= (si.)，从而满足了解的稀疏性要求。利用式(12)对超参数向量进行更新，

45、求得超参数向量的固定解后, 就能够根据式(13)求出S的最大后验概率估计，并由得到重建图像。 (13)2.2.4.2 GPSR重构算法梯度投影法(GPSR)是基于l1范数最小进行求解的算法，它解决的是一个受约束的二次规划(Bound-Constrained Quadratic Programming，BCQP)问题。在目前已有的算法中，它以高运算速度和良好的重建效果著称。它的主要策略是从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点。当迭代出发点在可行域内部时，沿负梯度方向搜索。当选代出发点在某些约束的边界上时，将该点处的负梯度投影到矩阵的零空间，该空间是以起作用约束

46、或部分起作用约束的梯度为行所构造成的。GPSR算法具有良好的重建效果采样率(MN)较高时，它与SAMP不相上下。随着采样率(MN)的下降，重建出图像的PSNR值下降也较快。该算法最显著的优点是运算时问，重建一幅512x512的图像仅需几十秒。在大规模应用时，相对于其他算法，该算法不需要过多调整即可应用，而且时间优势更为明显。总地来说，该算法在重建效果和运算时间上均有着不可忽视的优点。2.3 压缩感知理论的推广及应用2.3.1 信号在冗余字典上的压缩感知理论在压缩感知理论中，信号越稀疏，恢复信号就越准确。而对于具有复杂特征的信号如自然图像、声音信号来说，固定的正交基有时不足以捕获信号的多种特征，

47、使图像在变换域足够稀疏。例如，正交小波变换由于缺乏平移旋转不变性而不能有效压缩几何图像。目前对于压缩感知理论的研究还大多集中在固定的正交基空间，压缩感知理论的一个重要前提要找到信号的稀疏域，它直接关系到压缩感知的重构精度。对于信号的稀疏表示问题，大量的研究表明超完备冗余字典下的信号稀疏表示更加有效，而这方面的研究也有了一定的进展。于是，能否将压缩感知理论中的稀疏表示从固定的正交基扩展到冗余字典，引起了人们巨大的研究兴趣。文献表明如果信号在冗余字典而不是正交基下稀疏，且某些类型的随机矩阵和确定性的字典组合而成的矩阵具有很小的有限等距常量（满足RIP性质），则在冗余字典下稀疏的信号就可以通过BP算法从少量的随机观测值中恢复出来。该文献还指出将稀疏变换替换为冗余字典之后，在保持信号在冗余字典上的稀疏特性的条件下，现有的大多数重构算法（如BP和OMP）仍然适用，并进一步