基于隐马尔科夫树模型的压缩感知图像重构.pdf

《基于隐马尔科夫树模型的压缩感知图像重构.pdf》由会员分享，可在线阅读，更多相关《基于隐马尔科夫树模型的压缩感知图像重构.pdf（68页珍藏版）》请在三一文库上搜索。

1、 摘 要 I 摘 要 压缩感知是针对稀疏或者可压缩的信号提出的一种新理论，在信号采样的过 程中，同时对信号进行压缩，它的采样速率远远低于传统的奈奎斯特采样速率， 这使其在信号处理领域有着突出的优点和广阔的应用前景。该领域目前仍有许多 问题值得研究。重构算法是其中非常重要的一部分，它对于压缩后的信号的精确 重建以及采样过程中的准确性的验证都有着重要的意义。 本文对压缩感知理论以及现有的重构算法进行了系统的学习之后，围绕其中 的迭代加权算法在二维重构中的应用展开研究，主要完成工作如下： （1）分析了迭代加权 1 l范数重构算法的思想，提出了基于 HMT 模型训练参 数的迭代加权 1 l图像重构算法

2、。 该算法根据图像在小波域的四叉树结构， 利用 HMT 模型参数，对迭代加权算法的权值进行迭代更新，以达到更好的重构效果。 （2）提出了基于uHMT模型的迭代加权 1 l图像重构算法以及自适应的参数选 择方法。由于HMT模型参数的训练过程较为复杂，而且计算量较大，会占用大量 的时间和空间，针对这个问题，将uHMT模型参数运用到权值的更新中。此外，还 提出用自适应的方法来选择调节参数，根据迭代信号的值，对这些值进行排序， 选择其中较为合适的值作为参数，这样避免了参数的盲目选择。 关键关键词词： 压缩感知： 压缩感知 迭代加权迭代加权 隐马尔科夫树 （隐马尔科夫树 （HMT） 通用隐马尔科夫树 （

3、通用隐马尔科夫树 （uHMT ） Abstract III Abstract Compressive sensing (CS) is a novel signal sampling theory under the condition that the signal is sparse or compressible. It has the ability of compressing a signal during the process of sampling.Its sample rate is much lower than the traditional Nyquist sampli

4、ng rate. It makes that CS have outstanding advantages and broad application prospects in the signal processing area. The field is still has many problems is worth studying. Reconstruction algorithm is one of the important parts in compressive sensing. It is great significance to accurately reconstru

5、ct a signal and verify the sampling accuracy. In this paper, the properties of the existing reconstruction algorithms are firstly analyzed. Based on that, the main work is as follows: (1) Analyzes the idea of the iterative weighed 1 l-norm reconstruction algorithms, and proposed that the iterative w

6、eighed 1 l-norm reconstruction algorithms based on HMT model parameters is used in 2-d image reconstruction. This algorithm is based on the four binary tree structure of image in wavelet field. Constantly update weights, inorder to achieve better reconstruction effect. (2) Put the iterative weighed

7、1 l-norm reconstruction algorithms based on uHMT model parameters is used in 2-d image reconstruction. Because HMT model parameters training process is relatively complex, and it will take a lot of time and space. Besides， the improvement of the choice of the regulate parameters. In this section, we

8、 use adaptive way to select the parameters. To avoid the blind choose parameters and cause the difference of reconstruction effect. Keyword: compressive sensing iterative weighted Hidden Markov Tree universal Hidden Markov Tree 目 录 目 录 第一章 绪 论 . 1 1.1 研究背景及意义 1 1.2 压缩感知重构算法研究现状 3 1.3 论文的主要工作和安排 6 第二

9、章 压缩感知理论及算法 . 7 2.1 压缩感知理论框架 7 2.2 压缩感知的主要内容 10 2.2.1 信号的稀疏表示 . 10 2.2.2 观测矩阵的构造 . 11 2.2.3 重构算法的研究 . 13 2.3 本章小结 13 第三章 基于 HMT 权值的二维图像重构算法 . 15 3.1 迭代加权 1 l算法 . 15 3.1.1 加权 1 l算法 15 3.1.2 迭代算法 . 17 3.2 小波变换 18 3.2.1 简介 . 18 3.2.2 小波变换极其四叉树结构 . 19 3.2.3 小波变换的应用和优点 . 21 3.3 隐马尔科夫树模型 22 3.3.1 隐马尔科夫模型（

10、HMM） . 22 3.3.2 隐马尔科夫树模型（HMT） 23 3.4 小波域 HMT 模型 . 24 3.4.1 小波域 HMT 模型 24 3.4.2 HMT 的参数训练 26 3.5 基于 HMT 模型权值的迭代加权二维图像重构算法 . 27 3.6 分块压缩感知 28 3.7 实验结果及分析 29 3.8 本章小结 36 第四章 基于 uHMT 权值的二维图像重构算法 . 37 4.1 小波域 uHMT 模型 . 37 基于隐马尔科夫树模型的压缩感知图像重构 4.2 uHMT 权值的迭代加权算法 . 38 4.2.1 基于 uHMT 权值的加权算法 38 4.2.2 实验结果及分析

11、. 39 4.3 自适应参数选择的迭代算法 47 4.3.1 自适应参数选择方法 . 47 4.3.2 自适应参数选择的 uHMT+IRL1 算法 . 48 4.3.3 实验结果及分析 . 48 4.4 本章小结 53 第五章 总结与展望 . 55 5.1 总 结 55 5.2 展 望 55 参考文献 . 57 致 谢 . 61 作者在读期间的研究成果 . 63 第一章 绪 论 1 第一章 绪 论 压缩感知理论1-8作为一种全新的信息获取理论, 突破了传统奈奎斯特采样定 理的限制。压缩感知理论指出：以和实际信号的“信息率9”相当的采样速率获取 稀疏信号的非自适应线性投影，通过求解最优化问题仍能

12、准确重构原始信号。由 于压缩感知理论对处理大规模稀疏或可压缩数据具有十分重要的意义，所以该理 论提出后在许多研究领域得到了关注。国外研究人员已开始将压缩感知理论用于 天文学、压缩成像、雷达成像、医学图像、模数转换、通信等许多领域。 1.1 研究背景及意义研究背景及意义 过去的几十年间，随着信息技术的飞速发展使得人们对信息的需求量剧增， 传感系统获取数据的能力不断地得到增强，需要处理的数据量也在不断的增多， 而传统的奈奎斯特采样定理要求信号的采样率不得低于信号带宽的 2 倍以上才能 精确重构信号。然而随着人们对信息需求量的不断增加，携带信息的信号的带宽 也越来越宽，以此为基础的信号处理框架要求的

13、采样速率和处理速度也越来越高， 因而对宽带信号处理的困难在日益加剧，这无疑给信号处理的能力提出了更高的 要求，也给相应的硬件设备带来了巨大的挑战。另一方面，在实际生活应用中， 为了降低存储、传输和处理的成本，人们常常采用压缩方式表示信号，许多不是 很重要的数据被抛弃。为了方便对数字信号的保存和传输，首先我们就需要对被 采样的数字信号进行一定的压缩，即通过某种变换把要采样的数字信号从时域转 换到其相应的变换域，如傅里叶域、DCT 域，小波域等，然后舍弃大量的零值或 者接近零值的系数，对剩余少数大系数的值和位置进行编码处理，通过这样的方 法来实现数字信号的压缩。这种高速采样再压缩的过程中，大量的采

14、样资源被浪 费。像这种传统的编解码方法，它存在两个明显的缺点： （1）由于信号的采样速 率不得低于原始信号带宽的 2 倍，这样高的采样速率使得硬件系统面临着很大的 压力； （2）在压缩和编码的过程中，大量变换计算得到的小系数被丢弃，造成了 数据计算和计算机内存资源的浪费。于是，大家就提出一个问题，是否可以在其 它的变换空间来描述信号，建立一个新的信号描述和处理的理论框架，使得在保 证信息不丢失的情况下，使用远低于奈奎斯特采样定理要求的速率采样信号，同 时又可以完全恢复信号？即能否把对信号的采样转变成对信息的采样。 在 2004 年， 由 Donoho 和 Candes 等人提出一种新颖的信号采

15、集理论压缩 感知（Compressed Sensing 也称 Compressive sampling）理论，也简称 CS 理论。压 2 基于隐马尔科夫树模型的压缩感知图像重构 缩感知理论突破了传统的奈奎斯特采样定理的约束和限制，彻底改变了大家对信 号采样的传统思路，该理论指出，对于连续的信号，可以通过一个较低的速率对 它进行随机观测，具体的过程是：选用一个随机观测矩阵，用这个矩阵对连续的 信号进行测量或观测，得到一组观测值，得到的每一个观测数据都是对信号整体 的一个测量或观测，得到的观测数据的数量远远地小于奈奎斯特采样定理规定的 采样数目。因此，压缩感知理论在对信号进行采样的同时也实现了对信

16、号的压缩， 极大地减少了硬件资源的消耗。压缩感知理论是一个充分利用信号稀疏性或可压 缩性的新理论，是一种全新的信号采集编解码理论2,9，该理论表明，当信号具有 稀疏性或可压缩性时，通过采集少量的信号投影值就可实现信号的准确或近似重 构。因此，压缩感知理论一出现，就受到信号处理领域学者们的广泛关注，它在 信号处理领域具有十分广阔的应用前景。到目前为止，Rice 大学的科学家们已经 成功研制出了基于压缩感知理论的单像素相机10；同时，在医学成像方面，它可 以显著减少 MRI 的成像时间，极大地提高 MRI 的成像质量；另外，在图像多描述 编码、传输方面，压缩感知理论也有着直接的应用8，它有生产渐进

17、描述以及网络 的抗干扰、抗丢包等优点。 由于压缩感知理论的优点和特点，从它诞生之日起，就吸引了国内外无数学 者的关注和研究。然而，压缩感知理论虽然可以极大地减少信号采集的样本数目， 能够在对信号进行采样的同时实现对信息的压缩，一边采样，一边压缩，但是， 如何从获取的较少的观测样本中，来准确恢复原始信号是一个艰巨的任务。压缩 感知理论从理论上能够保证，在满足一定条件下，它能够近似无失真地重构或恢 复原始信号。但是，大多数的自然信号在空域中并不是都是稀疏的，因此，我们 需要将信号进行变换，将其转换到到一个变换域，这样该信号才能够具有稀疏的 特性。接下来一个关键的问题就是怎样来确定信号在哪个变换域是

18、稀疏的，即为 信号选择一个稀疏域，选择合适的稀疏空间是十分重要的，这将会直接影响到信 号观测矩阵的设计，以及信号恢复算法的设计。我们知道常用的稀疏空间，如傅 里叶域、DCT 域和小波变换域等。压缩感知理论主要包括三个方面：信号的稀疏 表示，即稀疏域的选择；观测矩阵的设计；信号重构算法。在合适的稀疏和采样 条件下，选择较好的信号重构算法，也是非常重要的。如果没有选择正确的重构 算法，即使有很好的采样数据，我们也可能无法准确地重构或恢复原始信号。 因此，针对现有压缩感知理论在实际应用中存在的问题，根据图像在稀疏域 （小波域）的特有结构，本论文提出了基于隐马尔科夫树模型的迭代加权二维图 像重构算法，

19、根据上一次的图像的信息，不断的调整权值，来确定图像的系数的 大小，以达到更好的重构效果。通过实验证明，该算法比传统的权值固定的迭代 算法在二维图像的重构效果有了一定的提高。 第一章 绪 论 3 1.2 压缩感知重构算法研究现状压缩感知重构算法研究现状 下面，我对压缩感知理论及其重构算法做一个简要的介绍，并指出目前主要 的压缩感知重构算法以及存在的问题。 压缩传感理论是信息处理领域的一个十分重大突破，多年来，人们对信号采 样过程的研究一直局限在奈奎斯特采样定理的框架中，而该理论从根本上改变了 这一传统的信息获取的观念和过程。压缩传感理论是将信号稀疏性表示的先验知 识和信号的具体重构过程相结合，从

20、少数的远远小于奈奎斯特采样率的采样点中 恢复原始信号，这就是它的核心思想过程。 压缩感知理论的基本思想如下：对于一个 N 维的原始信号 N xR，我们可以 通过一个MN维的随机观测矩阵 M N R 对其进行观测，得到 M 个观测值，其 中，M 远远的小于 N，即yx，其中观测矩阵和所测量的信号是相互独立的， 因此，压缩感知理论的采样过程具有非自适应性和普遍性。但是，由于 MN，从 原始信号 x 得到观测值 y 是一个从高维到低维的降维过程，从 M 个观测值 y 中来 恢复原始信号 x 是求解一个欠定的线性方程的问题，大家都知道，这样的方程组 具有无穷多个解，因此，按照一般道理来说，我们无法精确

21、地从观测值 y 中恢复 原始信号 x。但是，压缩感知理论指出，当观测矩阵满足一定的条件时，我们就 能够从观测值 y 中无失真地重构原始信号 x。 压缩感知理论指出，当观测矩阵满足 RIP 有限等距性质（Restricted Isometry Property）1-8, 11时，我们就可以从 M 个观测值中无失真地重构原始信号。通常大 多数的随机矩阵基本上都具有较高的概率来满足 RIP 条件，例如，矩阵中各元素 都服从独立同分布，均值为零，方差为 1/N 的高斯随机观测矩阵，或者是独立同 分布的 Bernoulli 分布的随机矩阵，它们都基本上符合该 RIP 条件。除此之外，一 些随机抽取的标准

22、正交基，如 Noiselet 变换基，傅立叶变换基和 Walsh-Hadamard， 它们各自的行向量随机构成的观测矩阵也都基本上满足 RIP 条件。由 Noiselet 变 换基构成的观测矩阵还具有快速实现算法。 前面已经提到过，从 M 个观测值 y 中重构出原始信号 x 是一个高度欠定的线 性系统，它具有无穷多个解。显然，传统的最小二乘算法是无法准确地重构原始 信号。为了能够精确地重构原始信号，我们需要一些额外的先验知识，在压缩感 知理论的重构过程中中，信号的稀疏性是我们需要的最重要的先验知识。根据信 号的稀疏性，我们可以通过求解如下所示的优化问题来重构原始信号 x： 0 a r g m

23、i n s . t . y= T x xxx （1-1） 其中，为信号 x 的稀疏基，也称为稀疏空间，即信号 x 在变换基下可以稀疏 表示， 0 |.|表示 0 l-范数，即向量中非零元素的个数。根据上面的公式，对于稀疏 4 基于隐马尔科夫树模型的压缩感知图像重构 度为 K 的稀疏信号 x，即 Tx 只具有 K 个非零的系数，在理论上，用 2K 个观测 值，我们就能完全重构原信号 x。但是，由于上述式子是一个 NP 难的组合优化问 题，所以我们无法对它进行准确求解，只能使用一些现有的贪婪搜索算法，通过 每次迭代时选择一个局部最优解来逐步逼近原始信号，寻找近似解。如：匹配追 踪（Matching

24、 pursuit,MP）算法12-15，OMP（Matching pursuit，OMP）算法16， 分段 OMP (StOMP) 算法17和正则化 OMP(ROMP)算法18 ，19。为了避免这种复 杂的组合优化问题，压缩感知理论指出，可以通过求解下列 1 l-范数最小化优化来 近似重构原始信号 x： 1 argmin s.t. y= T x xxx （1-2） 文献20给出了式(1-2)与式(1-1)等价的具体证明, 式(1-2)是凸优化问题, 可 以将其转化为线性规划问题求解21。 压缩感知理论指出，我们可以通过求解 1 l-范数最小优化问题，从N个随机观测 值中以较高的概率恢复出K稀疏

25、的信号，其中M(log(/)O KN M。上式对应的是 一个典型的线性规划问题，它是一个凸优化问题，可以利用多种优化算法对其进 行求解，如基追踪算法（Basis pursuit，BP）22， Bregman分裂算法28 、迭代阈 值算法（Iterative shrinkage）23-27等。如果考虑到观测噪声等不确定外界因素的影 响，压缩感知重构算法通常也表示成下列优化问题： 1 argmin s.t. |y-| T x xxx （1-3） 其中表示观测噪声的方差。在实际求解过程中，式（1-3）的优化问题也可以表 示成下列拉格朗日乘子的形式： 2 2 1 argmin|y-| T x xxx

26、（1-4） 其中为正则参数，对观测误差进行调节。 通过上述的优化算法，给定一个信号 x，它具有严格稀疏的特性，我们就可 以近似无失真地重构出原始信号 x。但是，在实际应用中，时域中的大多数的自然 信号并不具备有稀疏的特性，更不具有严格稀疏的特性。那么，为信号寻找一个 最好的变换域或者稀疏域，压缩感知图像重构算法重要的部分，也就我们通常所 说的变换矩阵。目前，常用的压缩感知恢复算法使用 DCT 域，小波域以及全变 差 (Total Variation)域来作为稀疏域，分段光滑的信号在这些稀疏域上具有很好的 近似稀疏的效果。 到目前为止，主要的信号重构算法基本上都可以归为以下三类35： (1)贪婪

27、算法：它是通过选择合适的原子并经过一系列的逐步递增的方法实现 信号矢量的逼近， 此类算法主要包括匹配跟踪 （MP） 算法12-15、 正交匹配追踪 OMP 算法16、 补空间匹配追踪算法、 分段 OMP 算法(StOMP)17和正则化 OMP(ROMP) 第一章 绪 论 5 算法18,19等。 (2) 凸优化算法： 它是把 0 范数放宽到 1 范数通过线性规划求解的， 例如 BP 算 法22，内点法2 ,28、梯度投影方法29和迭代阈值法30等。 (3)组合算法：它是把信号的采样过程通过分组测试快速重建，如链式追踪33， HHS(Heavg Hitters on Steroids)追踪34和傅

28、立叶采样31,32等。 凸优化算法算法比贪婪算法所求的解更加精确，但是需要更高的计算复杂度。 基于 1 范数最小的重构算法计算量巨大，对于大规模信号无法应用；贪婪算法虽 然重建速度快，但是在信号重建质量上还有待提高。 下面介绍一下上面提到的几种算法的思想： MP 算法12-15：MP 算法的基本思想是基于信号的可分解和重构，通过在过完 备的库（即观测矩阵）中自适应地搜索匹配能够表达信号局部特征的时频原子， 最终将信号表示为时频原子的线性组合。 MP 算法是一个迭代过程， 它通过不断地 将信号残差投影到原子库中一个最匹配它的向量上，从而继续对它进行分解。将 上述分解过程一直执行到 n 阶，就可以

29、得到逼近原始信号的信号。MP 算法在实际 中的应用的范围非常广泛，例如：图像表示、分析和编码；视频编码和视频压缩； 特征提取与目标识别领域；语音与音频信号处理；医学信号处理领域；电磁信号 处理等。 OMP 算法16： OMP 算法原子选择的准则和 MP 算法中的基本相同， 在重建时 每次迭代得到x 的支撑集 F 的一个原子， 选择一个原子集合， 通过递归对选择的原 子集合来进行正交化， 保证迭代过程的最优性， 从而减少迭代的次数。 参考文献36 对固定的稀疏度K的N维离散信号x，用高斯矩阵观测时，只要满足 M(log(/)O KN M，OMP 算法能够以非常大概率精确的重构原始信号，而且比 最

30、小 1 l-范数算法速度更快。但是，OMP 算法精确重构信号的理论支持比最小 1 l-范 数法弱，它并不是对所有信号都能够精确重构，而且对于观测矩阵的要求比约束 等距性更加严格37。 迭代阈值法30：Kingsbury 等人提出了求解 0 l优化问题（1-1）的迭代阈值法， 然而由于(1-2)式具有非凸的特性，该类算法不能保证收敛到全局最优解，有可能 得到的是局部最优解，而且得到的解并不一定是稀疏的，因而对信号的初值对迭 代阈值算法是非常重要的，该类算法对信号初值的准确性要求很高，很难直接应 用于信号重构。然而如果我们能够找到一个合适的初值，迭代阈值法还是可以找 到式（1-2）的全局最优解。因

31、此，该算法可以和其他算法相结合，如 MP 算法， 由这些算法提供初值。参考文献38证明这种方法能够提供比单独使用 MP 算法得 到更好的结果。 6 基于隐马尔科夫树模型的压缩感知图像重构 1.3 论文的主要工作和安排论文的主要工作和安排 本文主要针对压缩感知的重构算法展开了研究工作。主要包括如下内容 ： 第一章介绍了本文研究课题的研究背景和意义，简述了现有的压缩感知重构 算法及研究的发展现状，指出了现有方法存在的一些问题，此后描述了本论文的 研究目标，并给出了论文的结构安排。 第二章主要是对本文研究课题的基础理论的介绍，包括压缩感知理论的基础 知识和压缩感知的主要内容，包括信号的稀疏表示，观测

32、矩阵的构造，重构算法 的选择，并对这三方面内容做了详细介绍。 第三章分析了迭代加权 1 l范数重构算法的思想，提出了将基于 HMT 模型训练 参数的迭代加权 1 l二维图像的重构算法。该算法根据图像在小波域的四叉树结构， 利用 HMT 模型参数，对迭代加权算法的权值进行迭代更新，以达到更好的重构效 果。实验表明，该算法比一般的迭代加权算法的重构效果有一定的提高。 第四章主要介绍了基于uHMT模型的迭代加权二维图像重构算法以及自适应 参数选择方法。第三章中所述的HMT模型参数的训练过程较为复杂，而且计算量 较大，会占用大量的时间和空间，针对这个问题，将uHMT模型参数运用到权值的 更新中。此外，

33、针对权值更新过程中的一个调节参数的选择进行了改进。选取自 适应的方法来选择调节参数，根据上一次信号的值，对这些值进行排序，选择其 中较为合适的值作为参数，这样避免了盲目的选择参数而导致重构效果的差异。 第五章对本论文的工作进行总结，并对今后的可以继续深入发展的研究方向 进行展望。 第二章 压缩感知理论及算法 7 第二章 压缩感知理论及算法 压缩感知理论的信号编解码过程和传统的信号采集、编解码过程有本质上的 区别。本章介绍了压缩感知理论基本框架和具体过程，主要详细介绍了它的三个 重要方面：信号的稀疏表示，观测矩阵的构造，重构算法的选择。 2.1 压缩感知理论框架压缩感知理论框架 与传统的奈奎斯特

34、采样定理不同，压缩感知理论是近年来提出的一种新的信 号采集理论。该理论指出，图像的采样和压缩过程可以同时进行，并且只需非常 低的采样速率，这样，传感器的采样率和计算成本都将会大大降低。该理论还指 出，如果一个信号它本身是稀疏的或者它在某个变换域里具有稀疏性，将稀疏变 换得到的高维信号进行投影处理，来完成对稀疏信号的采样和观测，得到一个低 维空间的信号，通过求解一个简单的优化问题来重构原始信号，这样就可以从得 到的少量投影信息中以较高的概率重构出原始信号，实验证明按照上述方法投影 得到的信号包含了重构所需要的所有信息。压缩感知理论在对信号进行采样的时 候，就对信号进行了适当的压缩，而传统的信号采

35、样和压缩的过程是分开的，一 般主要包括四个部分：采样、压缩、传输和解压缩，其中采样过程中必须遵循奈 奎斯特采样定理，这样采样所需的数据量大，而且先采样后压缩，浪费了大量的 资源，相比之下，压缩感知理论则要简单的多，它针对信号的稀疏性或可压缩性， 能够将数据采样和压缩两个过程合二为一，这使得其在信号处理领域有着非常广 阔的应用前景。 传统信号的采集、编解码过程如图 2.1 所示： 编码端 解码端 图 2.1 传统信号的采集、编解码过程 压缩感知理论的信号编解码框架和传统的信号框架大不一样，如图 2.2 所示： 解压缩、反变换 采样 变换、压缩解码 8 基于隐马尔科夫树模型的压缩感知图像重构 编码

36、端 解码端 图 2.2 压缩感知理论的信号编解码框架 接下来我们将具体的介绍一下压缩感知理论的内容。 假设有一个长度有限，并且离散的时间信号 N xR，我们可以将它看作为是 一个空间长度为 N 的一维列向量，它的元素可以记为 ,1,2,.,x n nN。对于图像 以及其它更高维的数据，我们可以将它拉成一个长的一维矢量信号。在 N R空间上 的任意一个信号，都可以用一个基向量集合中的矢量 1 N ii 重新表示。一般情况下 我们所选取的基都是规范正交基。 将这个基上所有的矢量 i 排列成一个NN维 的基矩阵 12 : . n ， 这样信号 x 就可以表示为基与在该基上系数的线性组 合： 1 N

37、ii i xs 或xs （2-1） 其中，s 是一个列向量，它的长度为 N，它的值可以由式, T iii sxx确定。x 和 s 是等价的，二者是对同一信号在不同域上的不同表示，x 是在时域的表示，s 是在域的表示。 压缩感知理论研究的注意力主要是集中在能够被稀疏表示或者可压缩的信号 上。信号通过一定的稀疏基稀疏得到的 N 个稀疏系数，这些系数中只有 K 个是非 零的，其余的 N-K 个系数的值都为零。这个信号是由 K 个基矢量的线性组合组成 的，其中 KN，也就是所谓的稀疏信号，K 为稀疏度。但是在实际应用中，基 本上所有的自然信号都不是严格意义上的稀疏信号，而是存在某个域使得其大 系数个数

38、很少，其余是许多小系数（接近零值） ，这样的信号称作是可压缩的信号， 也可由 K 稀疏度很好的逼近， 压缩感知理论对于稀疏和可压缩的信号都是适用的。 压缩感知理论将信号从时域中的 N R空间投影到了 M R空间，对于信号中信息 的获取，它不需要经过中间 N 点的采样步骤。这个数据获取的具体过程是按如下 步骤进行的 首先，如果原始信号在某个变换域上是稀疏或者可压缩的，计算 x 和该正交 基中某一正交基 1 M jj 的内积（MN） ，求它的变换系数： T sx (2-2) 其次，用一个MN维观测矩阵，该矩阵与变换基互不相关，对变换得到 的系数 s 进行观测，与式(2-1)结合，上述过程可以表示为

39、下列式子： T ysxx (2-3) 解码重构 测量编码 第二章 压缩感知理论及算法 9 其中， T ，是MN维的矩阵，是压缩感知的观测算子，压缩感知的观测 过程可以用下面的图来具体表示： (a) (b) 图 2.3 压缩感知理论的采样过程，为高斯随机矩阵作，为稀疏字典。(a)压缩感知中 观测过程的随机观测矩阵和变换矩阵，s 是稀疏度为 4 的稀疏信号。 (b) T 表示 信号观测的具体过程，其中黑框部分的 4 列对应着非零系数 i s。观测向量 y 是这 4 列非零元 素的线性表示。 最后，我们通过求解以下优化问题： 0 argmin s.t. y= TT s sxxsx （2-4） 得到我

40、们需要的重构信号s ，然后利用的逆矩阵重建原始信号 x ： 1 xs 。 综上所述，压缩感知理论的步骤可以总结为： （1） 原始信号 x 在基底()NN下是稀疏的， 则信号可稀疏表示为 s，xs； （2）通过观测矩阵()MN，获得观测值： yxss （3）已知, y ，选择合适的算法恢复 s： ss满足y的最稀疏解 （4）利用的逆矩阵重建原始信号x ： 1 xs 。 上式（2-4）所求解的优化问题是一个 0 l范数优化问题，它是一个组合优化问 题，理论上是一个 NP 难问题，它有很多个解，是很难用计算机来实现求解的。因 此，这些年来，在对信号的优化重构算法的研究中，主要是把需要优化的目标函 数

41、式（2-4）做一定的处理，使它能够在计算机上进行求解成为可能。Donoho2在 提出 CS 理论时，把目标函数的 0 l范数优化问题转化为 1 l范数优化问题，利用线性 规划的方法来求解 1 l范数优化问题，比如：内点法，BP 算法22等。 10 基于隐马尔科夫树模型的压缩感知图像重构 2.2 压缩感知的主要内容压缩感知的主要内容 从上节所描述的压缩感知的具体步骤中，我们可以看出，压缩感知主要包括 三个方面的内容：信号的稀疏表示，观测矩阵的构造，重构算法的选择。下面对 这三方面的内容作详细的介绍。 2.2.1 信号的稀疏表示信号的稀疏表示 从最早期的傅里叶变换到小波变换， 再到后来的多尺度几何

42、分析 (Ridgelet39， Curvelet40，Bandelet41，Contourlet42)，科学家们研究的目的均是为了研究出一 种更加简洁、直接的方法，利用信号的特征，对信号进行稀疏表示，也可以说是 利用某种方式来提高信号的非线性函数的逼近能力，更进一步的研究信号在某个 空间的稀疏表示程度或者是能量的集中程度。经典的稀疏化的方法有离散余弦变 换（DCT） 、傅里叶变换（FFT） 、离散小波变换（DWT）等。 所以，在压缩感知理论中，信号在某种表示方式下的稀疏性，是压缩感知理 论能够之所以能够得以应用的基础，因为我们需要将这些先验知识用数学公式表 示后，才能转化为目标函数的约束项来正

43、则信号的重构。只有选择合适的变换空 间来表示信号才能保证信号的稀疏度，从而保证信号的精度重构。压缩感知理论 也表明，变换域的选择的好坏直接关系到信号的重构质量，信号表示的越稀疏， 信号重构质量就越好。但是，对于具有复杂特征的信号如自然图像来说，信号的 边缘、轮廓、纹理等特征是随着像素空间位置的变化而变化的，选用固定不变的 正交基是不能足够的捕获信号多种多样的特征，从而使图像在变换域可以足够的 稀疏。比如，框架理论(Method of Frame，MOF)就给出了在过完备的字典集中来寻 找信号最优表示的方法，但是，稀疏表示的过程中，需要大量的字典原子，所以 该方法在理论上，缺少寻找最优表示的稳定

44、性，在技术上，存在计算量大，计算 过程复杂的问题；而小波变换也存在一定的问题，不能很好的压缩图像，比如缺 乏平移和旋转不变性。针对上面存在的问题，最近几年，对稀疏表示研究的另一 个热点问题是信号在冗余字典下的稀疏分解。这是一种全新的信号表示理论：把 基函数用超完备的冗余函数库取代，将它称为冗余字典，字典中的元素是原子。 目前信号在冗余字典下的稀疏表示的研究集中在两个方面：一是如何构造一个适 合某一类信号的冗余字典，二是如何设计快速有效的稀疏分解算法。目前常用的 稀疏分解算法大致可分为匹配追踪（Matching Pursuit）和基追踪（Basis Pursuit） 两大类。为了能够更准确的获得

45、信号的先验知识，更准确的描述信号的特征，所 以分析信号在稀疏变换域的表示是十分重要的，将得到的先验知识作为正则项， 来约束目标函数，恢复原始信号。 第二章 压缩感知理论及算法 11 2.2.2 观测矩阵观测矩阵的构造的构造 在压缩感知理论中，通过变换得到信号的稀疏系数向量 T sx后，需要设计 压缩采样系统的观测部分，它主要是围绕着观测矩阵来展开的，所以，观测矩阵 的选择也是压缩感知理论的另一个主要方面。 该理论对信号进行观测的最终目的 是获得原始信号的观测向量 y， 并且最后能够从所得到观测向量中稳定的重构原始 信号 x 或者它在稀疏空间上的稀疏系数 s。 如果我们在观测过程中丢弃了原始信号

46、 x 的一些重要信息，想要完全重构 x 是基本上不可能完成的。根据压缩感知的基础 理论知识，众所周知，对原始信号 x 的观测过程是一个线性过程，这个线性过程 是以观测矩阵和稀疏基定义的。根据前面的讲述，从所得到的观测向量 y 恢复 原始信号 x 实际上就是式(2-4)表示的求解优化问题，该优化问题是一个线性方程 组。但是，在这个方程组中，方程的个数 M 远远小于未知数的个数 N，这是一个 典型的 ill-posed 逆问题的求解，也就是我们所说的病态问题，它的解是不唯一确 定的，而是有无数多个解，因此我们需要增加原始信号的一些先验知识来作为正 则项约束优化问题，进而进行求解。 对于上述所提到的

47、问题，我们利用稀疏变换所得到的系数 s 的特有特征来解 决。 观测得到是观测向量 y 仅仅是观测过程中变换系数不等于零的那 K 列元素 的线性表示（如图 2.3（b）所示） 。因此，如果我们能够事先知道变换所得系数 s 中的哪 K 个元素为非零，哪些元素为零，即确定信号中不为零的元素的位置，这 样我们就能够构造一个MK的线性方程组，来直接求解 K 个非零的系数，但是 此时方程组中方程的数量大于或者等于未知量的个数 K，这时方程的解就是能够 唯一确定的。要确保MK该线性系统有解的充要条件是观测矩阵满足 RIP 有限 等距性质1-8。满足了这个性质，这个问题就可以看做是一个可求解的稳定的逆问 题。

48、 有限等距性质 （Restricted Isometry Property， RIP） 1-8： 对于任意一个矢量 v ， 它所有的元素中有 K 个元素是非零的，则： 222 1| |1| |vvv （）（） （2-5） 对于任意的0，上式都成立。换言之，稀疏度为 K 的矢量的长度必须能够被 矩阵所保持。 在一般情况下，我们是无法知道稀疏系数 s 中哪 K 个元素为非零值，哪些元 素为零，即无法确定 K 个非零元素的具体位置。但是，对于一个稀疏度为 K 的信 号或可压缩信号有稳定解的充分条件是：需要满足式（2-5）的所述的条件。除 了上面的这个条件之外，能够使信号稳定重构的另外一个重要条件就是要确保观 测矩阵与稀疏基是不相关的，即稀疏基的列 i 不能够由观测矩阵的行 T j 12 基于隐马尔科夫树模型的压缩感知图像重构 线性表示，反之，观测矩阵的行 T j 也不能由稀疏基的列 i 线性表示。不相关 性越强，互相表示时所需的系数越多；反之，相关性则越强。但是，怎样构造一 个观测矩阵，使得 T 满足有限等距条件，这是很难实现的。直接去验证给 定的矩阵