（信号与信息处理专业论文）压缩感知算法改进及其在图像和视频编码中的应用.pdf

improvement of compressed sensing algorithm and its application in image and video coding thesis submitted to nanjing university of posts and telecommunications for the degree of master of engineering by tianchuan wang supervisor: prof. jianxin song february 2013 i 摘要摘要 图像与视频信号是当今社会中最主要的信息载体，而最近兴起的压缩感知理论突破了传 统奈奎斯特准则的限制，可以在对信号采样的同时实现信息的压缩，从而大大节省了信号的 存储空间。本文针对压缩感知理论重构算法及其在图像与视频编码的应用中所存在的问题， 在以下三个方面做了深入研究工作： 首先，针对将随机采样的空间域信号作为全变差算法的迭代初值所存在的迭代次数多且 图像不清晰等问题，我们重构算法做了以下的改进：首先改进算法的迭代初值，取频域信号 的逆变换作为迭代初值；其次，为了测量更多的低频系数，在传统的测量矩阵基础上加以改 进，使其可以更多的测量频域的低频系数；最后，实验证明本文所改进的重构算法能减少信 号重构次数且在低采样率也能重构出较好的原始信号。 然后，针对基于压缩感知理论的图像编码方法中所存在的不能自适应选择编码方法的问 题，提出了一种基于图像边缘的自适应选择算法：由于图像边缘与梯度具有一定的耦合性， 将含有边缘信息比较多的图像块用压缩感知方法编码，将含有边缘信息比较少或者没有边缘 信息的图像块则采用传统的编码方法，从而实现对于不同图像内容的自适应编码。实验证明 本文所提出的自适应算法能有效的提高图像的重建质量； 最后，针对基于压缩感知理论视频编码方法中，帧间编码方面存在的码率太高、残差信 号稀疏度不高等问题，提出一种对残差图像的自适应编码方法：将图像组第一帧图像用第四 章提出的自适应方法做帧内编码，引入运动估计与补偿技术求出视频帧间残差图像，并对自 适应算法的阈值设置方法加以改进，实现对帧间残差图像的自适应编码。实验证明本文所提 方法能更加提高视频的重建质量。 关键词关键词： 图像编码, 图像重构, 离散余弦变换, 压缩感知, 最小全变差 ii abstract the image and video signal is the most important information carrier in the contemporary life. compressed sensing theory has broken the nyquist criterion which can sample the signal at the same time compress the signal and save the storage space. in this paper, we focus on the compressed sensing reconstruction algorithm and its application in image and video coding. we made thorough research works in the following three aspects. first of all, there are several questions of the total variation algorithm such as blurred image and excessive number of iterations which use the random sampling of the time-domain signal as the initial iterative value. the reconstruction algorithm was improved as follows: we take the inverse transform of the frequency domain signal as initial iterative value. the measurement matrix was designed to capture more low frequency coefficients. experiments show that our method can improve the quality of the reconstructed image. then, there are some questions with the image coding method which was based compression sensing theory such as disable to adaptive choosing coding methods. so we propose an adaptive selection algorithm which was based on edge information of image. for the edges of the image is basically the same with the image gradient, the image blocks was coded with compressed sensing theory which contains more image edge information. the others were coded with the traditional methods which contain few edge information. so we get the goal that the image block can adaptively choose the coding methods. experiments show that our adaptively choosing coding method can improve the quality of the reconstructed image. finally, there also exits shortcomings in the inter-frame coding of video. the adaptive coding method of residual image was proposed to solve these questions. the first frame of the gop was coded as the intra-frame with adaptive coding method based on compressive sensing. the motion estimation was introduced into the methods which were to obtain the residual image. we use the adaptive coding method to code the residual image. experiments show that our method can improve the quality of the reconstructed video. keywords：image coding, image reconstruction, discrete cosine transform (dct), compressed sensing (cs), minimum total variation (tv) iii 目录目录 第一章 绪论 . 1 1.1 课题背景 . 1 1.2 国内外研究现状 . 3 1.3 论文工作及组织结构 . 6 第二章 压缩感知理论介绍 . 8 2.1 信号的稀疏性 . 8 2.2 测量矩阵 . 11 2.2.1 不相干性 . 11 2.2.2 限制等容性 . 12 2.3 重构算法介绍 . 14 2.3.1 稀疏信号的重构 . 14 2.3.2 最小范数模型 . 15 2.3.3 匹配追踪类算法 . 16 2.3.4 最小范数模型 . 17 2.4 本章小结 . 20 第三章 信号重构算法与测量矩阵改进 . 22 3.1 梯度算法简介 . 22 3.2 基于梯度的二维信号重构算法 . 23 3.2.1 二维信号的 tv 算法介绍 . 23 3.2.2 初值的选择 . 24 3.2.3 迭代阈值 . 26 3.2.4 迭代过程 . 27 3.3 测量矩阵的设计 . 28 3.3.1 二维频域测量矩阵 . 28 3.3.2 测量矩阵的改进 . 31 3.4 改进算法的实验分析 . 33 3.5 本章小结 . 35 第四章 压缩感知在图像编码中的应用 . 36 4.1 基于压缩感知的图像编码介绍 . 36 4.2 图像边缘与梯度的耦合性 . 37 4.3 cs 编码与传统编码对不同图像重建质量的影响 . 40 4.4 基于图像边缘的自适应算法 . 44 4.4.1 边界的确定 . 44 4.4.2 自适应算法描述 . 46 4.5 自适应的图像重建实验 . 48 4.6 本章小结 . 51 第五章 压缩感知算法在视频编码中的应用 . 52 5.1 基于压缩感知理论的视频编码方法研究现状 . 52 5.2 基于压缩感知的自适应视频编码方法 . 53 5.2.1 自适应视频编码基本原理 . 53 5.2.2 残差图像的自适应编码 . 56 5.2.3 阈值的选取 . 59 5.3 实验验证与比较 . 60 iv 5.4 本章小结 . 63 第六章 总结与展望 . 64 6.1.论文总结 . 64 6.2 工作展望 . 65 参考文献 . 66 攻读硕士学位期间发表的论文 . 69 攻读硕士学位期间参加的科研项目 . 70 致谢 . 71 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章第一章 绪论绪论 1.1 课题课题背景背景 当今社会网络应用日益广泛，视频与音频逐渐成为多媒体信息的主要载体，同时二者也 占用了网络中大量的带宽资源。传统的信号采样方式是以奈奎斯特准则为基础，为了重建出 完整的信号，每个信号周期都至少以两倍最大带宽进行采样，虽然可以完美重构出原始信号， 但此过程同时产生了大量的冗余数据。在网络中不可能传输如此庞大的数据量，因而需要对 所采集的数据进行压缩，即剔除其中的冗余数据和不影响视觉体验的高频数据。如果能有一 种方法可以直接采集有用的信号，丢弃人们不感兴趣或者冗余的数据则能节省大量的硬件资 源，降低采样的成本。 随着社会的发展，当今图像与视频信号处理方面出现了很多问题，亟待人们投入精力去 解决这些问题，现在简单描述如下： 首先，由于网络技术与信号处理技术的广泛发展与应用， 使我们完全置身于网络世界中， 比如，我们有一个智能终端，可以将我们身边发生事情以视频、音频或图像形式上传至网络 与大家分享，或者有一个在恶劣的环境下工作的传感器网络，也或者是有一个复杂的视频监 控系统，这些应用都有一个基本的共同点：采集数据的终端都比较简单或者它们本身的能量 非常有限。传统的视频编解码系统为了减小码率节省传输带宽，通过编码端复杂的去冗余操 作实现信号的压缩编码，接收端的解码操作则要简单许多。如果编码过程都在简单终端完成， 则会大大的缩短简单终端的可使用时间。如果能够降低简单终端的编码操作，将复杂的去冗 余操作移动到大型服务器或云端，则即能降低编码端复杂度也不会增大解码端的复杂度，可 以延长终端的使用时间。那么怎样才能够降低编码端的复杂度呢？ 然后，经典的视频编码方法如 mpge 系列与 h.26x 系列等的视频编码方法基本相同，对 分块的视频帧进行 dct 变换然后进行量化，编码低频系数舍弃高频信息，从而实现原始信息 的压缩。一帧图像中有的区域比较平坦，有的区域具有明显的边界，有的区域有复杂的图像 内容，dct 变换并不完全适合于图像中所有的内容，在图像内容复杂区域在量化后会损失一 部分内容。所以在处理的过程中，我们希望能够对不同内容的图像块进行自适应处理，从而 才能达到更高的图像质量，所以就应该找到一种能够和 dct 变换互补的重建算法！ 最后，无线网络已经应用到生活的方方面面，但无线信道有其固有的特点，如信道误码 南京邮电大学硕士研究生学位论文 第一章 绪论 2 率高、带宽资源有限和带宽波动性等，这就要求编码出的信号要具有很强的抗干扰能力，比 如，由于 h.264 编码出的视频信息，如果接收端不能正确接收到 i 帧数据，则所有已接收到 的图像组数据都失去了意义，并且可能影响到其它数据帧的重建。由于无线信道具有开放性 的特点，所以信号在传输过程中可能会受到自然噪声的影响，在信号中引入噪声甚至改变原 始信号，接收端收到的数据就存在比较大的失真，必须找到一种抗干扰能力强的编码方法， 尽量减小由于噪声污染引起的信号失真，或者即使在误码率很大的时段同样可以重建出比较 好的帧图像（哪怕时间会长一些） ，保证数据传输的完整性，从而改善无线视频的传输质量。 以上所述为传统编码方法的固有缺陷所遗存的问题，如果要从根本上解决上述问题则需 要一种新理论，那有这样的理论存在吗？当然有-即现在成为多个领域研究热点的压缩感知 理论 2006 年由陶轩哲提出的压缩感知理论将一种全新理念引入编码领域，并迅速在多个领域 延展开来，如在医学的核磁共振成像，信道的编码、雷达信号处理及图像信号的处理等方面。 压缩感知理论最初起源于医学图像的处理领域，由于其在编码方面的卓越性能而促使多个领 域专家投入精力研究，那压缩感知技术到底具有什么样的特点呢？ 压缩感知技术主要由三个方面组成，信号的稀疏性、测量矩阵与重构算法。信号的稀疏 性是指被处理的信号必须是稀疏的，即只有少部分的信号具有较大数值其它数据是零值或者 趋近于零值。有的信号在空间域是具有稀疏性，而有的信号需在其变换域中才具有稀疏性， 现实生活中大多数图像都是在其变换域中才具有稀疏性。常用的稀疏变换有离散余弦变换、 傅利叶变换和小波变换，如果信号不稀疏则不能用压缩感知技术处理。测量矩阵的本质是对 稀疏信号进行编码，这种编码具有很大的随机性（给所测量信号分配随机的权重） ，从而测量 出每个信号值含有测量前信号的全部信息，所以每个测量信号分量具有相同的重要性，对重 构原始信号所做的贡献也相同。重构算法相当于传统信号处理中的解码器，但这种重构算法 具有非常高的复杂度，即通过多次的迭代近似重构出原始信号，迭代的次数越多则可能重构 出的信号质量就越高。重构算法是以信号稀疏性为基础，由于现实生活中图像都具有相关性， 例如，有两个完全相同的信号但在它们之间有一段区域并没有测量，可以直接用这两个相同 的信号去填补这块空白区域，这就是在压缩感知技术中相关性的应用，所以每次迭代出的信 号都会有很多不同的结果，而压缩感知就认为最稀疏的一组信号为正确结果，就可以通过多 次迭代重构出原始信号。 由上所述可知，压缩感知理论编码简单，用测量矩阵直接测量稀疏信号，将测量出的数 据传输到接收端，相比于传统的编码方法其编码复杂度降低了很多。虽然其重构算法比较复 南京邮电大学硕士研究生学位论文 第一章 绪论 3 杂，但可以利用一个大型服务器或者云端对所测量数据解码重构出原始信号，将所得信号再 发送至接收端。由于其编码端操作很简单所以能增大简单终端的电池可持续时间，延长使用 寿命。 重构算法是压缩感知中最重要的环节之一，比较经典的重构算法有凸优化算法、贪婪算 法和 tv 算法。前两种方法现在一般用于重建一维信号，虽然也可以重建图像等二维信号，但 其本质还是一维信号的重建方法。 由于测量信号的重构质量一定程度上取决于信号的稀疏度， 即信号越是稀疏重建出的信号质量也就越高。对于图像等二维信号利用二维的稀疏变换比一 维的稀疏变换更能增大信号的稀疏度，文献 29,17 中所用的 tv 算法可以直接用于二维信号重 构，相对于前两种方法则能重构出更高质量的图像。tv 算法本质是基于梯度的去噪声方法， 如果信号具有比较强的边界或者具有梯度稀疏性，用此方法可以达到更高的重建质量，所以 可以将此方法与传统的编码方法融合，实现对不同内容的图像块自适应编码。 压缩感知具有先天的抗干扰特性，用测量矩阵编码出信号，其每个信号中都含有编码前 信号的全部信息，所以测量出的每个信号的重要程度都相同，即接收任何一个信号都可以用 于重建原始的信号。在无线信道传输过程中，由于无线信道本身特点，在传输过程中引入比 较多的误码。 通过我们对压缩理论所具有性质的简单分析，可知压缩感知理论可以完美的解决上述所 在的问题，下面就对压缩感知理论做详细的阐述，并将其与传统的图像与视频编码相结合以 弥补其不足，提高其重建质量。 1.2 国内外研究现状国内外研究现状 由于压缩感知理论的优越性能，使得其为解决图像编码方面的问题提供了全新的解决方 案。国内外涌现了大量的优秀文献介绍压缩感知理论与图像编码之间的互补关系，并且为图 像编码提供了全新的方法，弥补了传统编码方法所固有的内在缺陷，提高图像重建的质量。 由于压缩感知理论编码的信号的抗噪声能力要高于传统编码方法，所以可以将其与传统 编码方法相结合，提升信号在无线网络环境中抗误码的能力，文献 8将压缩感知技术与传统 的jpeg编码方法相结合，根据最小率失真优化函数选择重构图像块，这种方法能够提高图像 的重建质量，但是重建的复杂度比较高，因为需要以两种方法分别重建出图像，选择最优块 用于重构图像,这个算法的缺点是消耗时间太长。文献 13所用方法与文献8基本相同，也是用 压缩感知编码方法与传统的视频编码方法相结合，用信噪比作为判断的标准，缺陷也是需要 重建出两种方法会浪费重建时间。文献 3提出了一种新的视频重建算法，首先提取出需要重 南京邮电大学硕士研究生学位论文 第一章 绪论 4 建图像的边缘信息，因为此边缘图像只包含二者元素0和1，对相邻两帧的边缘信息进行压缩 感知算法重建，根据二者之间的差异程度确定对应方块的采样率，从而满足对各个复杂图像 的精确重建，缺点是需要用cs重建两次，延长了重建时间。 以上三篇文献所介绍的内容，代表了当今关于传统编码方法与cs编码方法结合应用的整 体方向。但是各个方法都有其自身问题，即由于不能引入自适应的重建算法而延长了重建时 间。由于传统的编码方法与cs编码方法所重建的图像质量并不相同，文献 13中指出压缩感知 算法在具有强边界或者强梯度区域有着比较好的重建效果，而传统编码方法对平坦区域的重 建效果要好一些。众所周知，图像的边缘信息恰好包含了图像的强边界和梯度区，所以可以 尝试根据图像的边缘信息实现自适应的图像编码。 文献 9中将图像先进行dct变换，并选取出其中的低频系数，然后再对其原始图像与低频 图像的残差做cs采样再重建图像。这种算法最大的缺陷是将一幅图像当作了一个整体处理， 这样在重建时会很困难并且没有针对性，重建出的图像质量也不好，容易淹没重建的细节信 息。信号的稀疏性是cs重建的基础，由于图像是二维信息，经典的重建算法都是针对一维图 像信号的，对二维信号应用一维的稀疏变换不能完全去除图像的空域相关性。文献 12为了去 除图像的相关性，首先将图像进行分块，然后再将块的内容排成列再进行稀疏变换，从而增 大图像的稀疏度提高重建质量。但是这种方法只是在一定程度上去除了图像之间的相关性， 并没有做到极致！在文献 8,4中提供了一个很好的思路：对图像等二维信号直接进行二维的稀 疏变换，以此最大程度的去除图像信号的相关性，再用相应的测量矩阵选取其中重要的频率 分量，从而可以针对性的重要出高质量的图像。文献 13中提出了一种解决不同图像内容的方 法，对于图像平坦部分用dct作为稀疏基，对图像的边界部分则用owt作为稀疏基，从而可以 实现对细节部分的重建。 在以上介绍的方法中表明，如果要用cs理论重建出好的图像，首先需要将图像进行分块 处理，一是这样可以实现对复杂的信息块的特殊处理，二是这样可以降低重建时的复杂度与 提高重建时的精确程度。稀疏性是压缩感知理论的基础，去除图像等二维信号的相关性最好 的做法就是对其进行二维稀疏变换。在文献 4中用二维的fft变换作为稀疏基，但fft变换所 测量的数据会含有实部与虚部信息，在传输时会占用两倍的带宽，需要对此稀疏变换进行改 进。综合以上论文所述方法，可以在处理图像内容时，首先将图像进行分块对图像块整体稀 疏变换，然后再测量出其中重要的系数分量，重构出原始信号。 由以上文献所述表明，将压缩感知理论应用于图像编码中可以明显提高图像重建质量， 同理，也可以将此理论应用于视频编码中，是否同样可以提升视频的重建质量呢？研究基于 南京邮电大学硕士研究生学位论文 第一章 绪论 5 压缩感知理论的视频编码文献都证明同样可以提高重建视频的质量。在文献 1,2所提出的视频 重建方法相似，都是根据相邻两帧图像块测量值的差值来确定图像的采样率，设定两个阈值， 根据不同阈值选择不同的采样率。在该方法中只适用于相对运动比较小的视频，其中没有考 虑到图像的相对运动的问题，由于cs重建很费时，所以此方法会消耗大量的时间；由于视频 不但具有空域相关性，也具有空间域相关性，如果能再去除视频的空间域相关性则更有利于 cs方法重建图像。文献 7提出了用三维dct变换作为视频块的稀疏基，不仅可以去除视频的空 域相关性，也能去除空间域相关性。同样此方法只适应于运动量很小视频，对于运动剧烈的 视频块则不再具有相关性。文献 5将运动估计与运动补偿技术应用到基于cs理论的视频重建 过程中， 对i帧用传统的方法进行编码， 对预测帧首先用运动估计与补偿技术求出其残差图像， 对此残差图像再用cs理论编码，最后恢复出图像。这种方法是单纯为利用压缩理论而设计的， 由于残差具有很大的稀疏性，可以采用压缩感知理论。不好原因有两方面，一是残差可以用 cs理论编码，但并不是最好的方法；二是全部用cs算法重建会消耗很长时间 ，对能量有限或 者对实时性要求较高的环境而是不适用的。 综合以上文献所提算法的优势与缺陷，我们提出一种新的基于cs理论的视频重建算法， 将视频分成图像组，用图像组中第一帧作为参考帧，引入运动估计与运动补偿技术求出其残 差帧，提取残差图像的边缘，对残差图像的不同内容进行自适应编码，从而即提高了视频重 建质量，也节省了时间。 重构算法是压缩理论中最为重要的组成部分，重构算法的性能直接影响到重建图像的复 杂度与准确性。随着压缩感知理论的发展出现很多经典的重构算法，但是各有优缺点，有的 算法的图像重构质量比较好，但消耗时间太长，而有的算法正好相反。凸优化算法的主要思 想是通过解决凸优化问题通过极小化算法高概率逼近目标函数，从而重构原始信号。凸优化 算法主要有内点法 27、迭代阈值法28和迭代硬阈值法29。而贪婪算法则是通过对采样信号支 撑域的连续迭代重构原始信号。贪婪算法主要有mp 25算法以及在其基础上优化改进得到的 omp 24 (正交匹配追踪)算法和romp28(正则化的正交匹配追踪)算法。这些算法都可以实现信 号的重构，但有一个共同点，它们最初的设计是基于对一维信号的重建，而对二维信号重建 的效果不好。全变差(tv)算法可以完美实现信号的去噪声处理,tval3 26是经典的tv算法，在 文献 4445分别对该算法进行了改进， 将其引入到二维信号的处理过程并取得了比较好的效果。 在文献 44所采用的是梯度算法，搜索到最匹配点所用的迭代次数比较多，而文献45中的测量 矩阵的设计不适合在信道中传输信号，迭代初始值采用随机值，其收敛效果不好。 优化测量矩阵的设计，使其能够测量出图像等二维信息的关键信息，提高信号的压缩比。 南京邮电大学硕士研究生学位论文 第一章 绪论 6 tv算法具有良好的重建图像的性能，但不同的搜索算法所重构图像的时间有很大的差别，如 何确定迭代时搜索算法与迭代的初值是提高算法性能的关键所在！在算法改进章节，我们将 对算法尝试进行以上性能的优化。 1.3 论文工作及组织结构论文工作及组织结构 本文主要研究了基于压缩感知理论的无线视频传输方面的问题，压缩感知（cs）理论编 码非常简单，解码却很复杂并且其抗干扰能力很强；主要由三部分组成：测量矩阵、稀疏变 换和重构算法。本文对测量矩阵与重构算法都做了相关的研究，以提高重构图像的质量并降 低消耗时间。将cs编解码方法与传统的编码方法有机混合使用，可以融合两种算法的优点弥 补两者的不足。在本文中首先将此混合方法用于图像处理中，在验证了此方法有效时，根据 视频的特点将其用于视频处理中。 全文共分为六个大的章节，各章节内容及编排形式如下所示： 第一章：首先介绍了本课题所处在的大背景，介绍了传统的图像与视频编码方法所存在 的问题及简要介绍了压缩感知理论与传统编码方法之间具有的互补关系，然后介绍了国内最 新文献在研究这方面内容上所取得的成就及其所存在的问题，并提出了相应的解决方法。 第二章：详细介绍了压缩感知理论的理论基础与及约束条件。压缩感知理论由稀疏基、 测量矩阵及重构算法等三部分构成，稀疏基与测量矩阵需要满足不相干性及限制等容性，并 对其原因做了比较详细的论述。 第三章：首先介绍了重构算法的理论基础及将其简化后详细的理论分析；然后针对图像 等二维信号的特点对现有的测量矩阵及稀疏变换做了相应的改进，使其能够适应图像等信息 的稀疏化及能够测量出关键的频域系数。 最后本文对经典的tv算法的初始值做了相应的改进， 使用低频系数所包含的图像信息作为迭代初始值， 降低图像重建时间与提高重建图像的质量。 第四章：首先介绍了图像的边缘算法与图像梯度之间的耦合关系，为基于图像边缘信息 的自适应选择算法提供理论依据；然后，验证普通编码算法与cs编码算法所适用图像块的差 异性，传统的编码方法适应平坦的图像块，而cs编码方法适合在具有强边界与强梯度的图像 块；最后，根据提取的图像边缘信息实现图像的自适应编码方法，即根据图像内容的差异性 自适应选择与之相适应的编码方法，并用验证了所提出自适应算法的有效性！ 第五章：首先对基于压缩感知理论的视频编码方法作了简单的介绍，并引出本文阐述的 混合视频编码方法；然后，介绍了本文所提出的基于压缩感知理论的自适应视频重建算法， 用第四章的混合视频编码方法编码视频的i帧，通过对非参考帧的预测求出稀疏的残差帧，设 南京邮电大学硕士研究生学位论文 第一章 绪论 7 定两个阈值 与，根据选定的阈值信息自适应选择不同的采样率；最后，对本章节所提出的 算法进行实验验证。 第六章：对本文所做的工作做了提纲性的总结，并指出了本课题研究内容仍然存在的问 题及以后的研究方向。 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论介绍 8 第二章第二章 压缩感知理论介绍压缩感知理论介绍 在上一章节中，介绍了压缩感知理论在图像和视频处理中的重要意义，下面我们对压缩 感知理论的基本原理与需要满足的性质做详细的阐述。压缩感知理论主要由三部分组成：稀 疏基、测量矩阵与重构算法，由这三部分所组成的视频编解码系统与传统的编码系统有着明 显的区别。传统编码系统主要是根据奈奎斯特准则进行采样，得到大量的数据，然后再丢弃 其中不重要的系数。即是一个先采样再压缩的过程；而压缩感知理论则是在采样的过程中同 时进行了压缩，从中选取出重要的系数进行传输。下面就以一个框图来表示压缩感知理论的 理论框架及三个组成部分所处的位置。 可压缩信号 测量矩阵 线性测量 重构 特征提取 重构信号 信号特征 传输 存储 y= 信号的压缩测量 信号的重构 重构算法 图2.1 压缩感知理论框架 2.1 信号的稀疏性信号的稀疏性 压缩感知理论告诉我们，如果要利用压缩感知理论对信号进行编码，则此信号必需具有 一定的稀疏性，稀疏性是指一个空间域信号其本身或者在其特定的变换域内，非零元素个数 或者比较大的元素个数比较少，而其他元素为零值，或者以指数冥递减趋于零。稀疏性是压 缩感知理论的基础。 稀疏信号大致分为两种：一种是信号在空间域就稀疏，例如医学图像中“肝” 、 “肺”等 灰度值单一的图像；一种是信号在空间域并不稀疏，但其在特定的投影空间的分量是稀疏的， 我们现实中的自然图像大都属于此类，虽然在空间域信号分量都是非零值，但在变换域内信 号则具有很好的稀疏性。 设有一维空间域信号 ，是由l个离散信号组成的一个一维列向 量，如果在此l个信号分量中有k个系数分量为零值或者以指数幂递减趋于零则可认 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论介绍 9 为此信号具有稀疏性，是可进行压缩的。 存在一个高度随机化的矩阵，对信号进行直接测量 (2.1) 如下图中所示，信号x是一个稀疏的信号，通过随机测量矩阵对信号x做线性组合运算， 形成测量值,由于从数学理论上分析不可能恢复出原始信号x，但应用压缩 感知理论则可以近似重构出原始信号x：因为信号x是稀疏信号，其中只有k个重要系数分量， 可以认为测量值y中的系数分量是原始信号x重要系数的分量的组合。如图2.1所示： 图2.2空间域稀疏信号测量过程 在测量过程中，所选取的测量矩阵的行向量数目m大于测量值k，则可以在一定程度上认 为是由m个方程去求解k个系数的问题，这在低维运算中是完全可以实现的；如果此信号是高 维信号，则不可能直接求解，需要借助高效的近似算法才能实现。e. cands 等人在压缩感 知理论初问世之时，就从理论上严格证明了当满足条件时，可以用求解 范数最小化方法高概率的重构出原始信号。 (2.2) 虽然对于在空间域内稀疏的信号无论是对信号的测量还是对信号重构都会比较容易，但 是满足此条件的自然图像毕竟极少。为了使描述的问题具有普施性，下面我们介绍图像在变 换域中稀疏的条件。 设 是由一维的离散信号组成的列向量，其中元素的值大都不 为零，即在空间域中不满足稀疏性条件，如果对其采用压缩感知理论则需要对其进行相应的 变换。 对于任意的一组 维向量可以用一个 维的向量基表示： ， 假设这个向量基 正交，则以矩阵为基，信号可以表示成： 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论介绍 10 (2.3) 在上式中，, 是其原始信号x在基 下的投影系数， 和 是 维矩 阵，基 为维矩阵，如果 中仅仅有 个非零的系数（或取较大的值） ，而 其他个系数全部为零（或取值很小） ，( 是足够小的正数)，则称 x 是 k- 稀疏的，则可以认为基 为信号 x 的稀疏基。在通常情况下，所选取的稀疏变换并不能完全 的将信号稀疏到只有k个系数。所以根据信号的特点选择相应的稀疏变换就显得至关重要，最 主要的衡量标准就是原始信号x在稀疏基下的投影系数是否具有稀疏性！ 从最初的傅里叶变换至后来兴起的离散余弦变换及小波变换与k-l变换， 还是在当前正处 于研究热点的超小波变换，这些都可以作为将原始信号x的稀疏基，以上各种变换的优缺点， 我在这里不再详细阐述。在应用中只要根据信号的特点选择相应的稀疏基，就可以达到最优 稀疏性。 如果信号具有稀疏性， 则可以对信号进行随机的测量， 其测量方式与2.1.1小节方式相同， 不同的只是需要将信号变换到稀疏域。 (2.4) 在上式中可将测量矩阵 与稀疏基 相合并成新的矩阵 ，则有一个相似测量公式： (2.5) 可以将上式中的矩阵看作是新测量矩阵，只要测量矩阵 与稀疏矩阵满足rip性质， 则同样可以重构出原始图像。在重建图像过程中同样可以采用与上一小节同样的方法，即最 小 范数法。公式如下所示： (2.6) 可以从式(2.6）中重构出稀疏域的近似信号，由于稀疏基有固定形势，所以可以应用 稀疏基直接进行逆变换，得到近似的原始信号。 (2.7) 重构信号即是对原始信号的最优逼近，对于在变换域稀疏的信号其重构过程与在空域 稀疏的信号相比，要添加一步逆变换的过程，即由重构出来的稀疏信号再逆变换得到原始的 近似信号。 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论介绍 11 2.2 测量矩阵测量矩阵 在压缩感知理论中，并非直接对具有稀疏性的信号测量，而是先投影到一个稀疏空间， 得到相应的稀疏系数，然后再投影到一个与观测基不相干的低维观测基上，从而实现信号的 压缩。测量矩阵要能够保留原始信号的绝大多数的重要信息，观测矩阵 与稀疏基 之间必须 满足不相关性与限制等容性，才能高效的重建出原始信号。 2.2.1 不相干性 相干性最初起源于物理学中的谐波理论，是指两个同种性质谐波具有相同的频率和固定 的相位差，当两波相遇时所产生的干涉现象；不相干是指两个谐波信号的频率不同，两者之 间不会产生任何稳定的干涉现象。众所周知，两个不相干的波所具有的数据性质即是他们的 内积为零，只有两个频率不同的谐波分别为与,则此二波 在一个周期内的内积为零即：；如果两个谐波相干其内积为“1” ； 由以上的基础分析可以很容易的得出：在压缩感知理论中，测量矩阵与稀疏基之间的不 相干性可以由二者之间的内积空间进行定义，在统一的定义基础上，如果测量矩阵与稀疏基 的内积数值越小则说明二者之间的相干性越小，否则，则认为二者之间的相关性则越大。 文献 46定义了相干性度量方法，同样采取上一小节中的定义方式：原始信号为 ， 表 示随机投影矩阵且是正交矩阵即， 表示稀疏基且是正交矩阵即 ，将测量 矩阵与稀疏基都定义成正交矩阵，有利于我们对相干性理论的解释。通过以上的分析，可以 认为 和 之间的相干性等价于： (2.8) 由于测量矩阵与稀疏矩阵都是正交矩阵，由矩阵理论可知，其内积空间同样是一个正交 矩阵记为。当是个单位矩阵时，两矩阵分量的相干值 为,说明测量矩阵与稀疏基是严 格相关的，是相同的两个矩阵，其内积的能量完全集中在一点上，同时也证明此时其中一个 矩阵是完全可以用另一矩阵进行表示，没有存在的意义。此时所对应的信号测量值y仅仅包含 所对应稀疏域的前m个信号分量，不具有信号的随机性，更不会包含全局的信号信息分量。当 两个矩阵完全不相关时，也即是其内积空间的能量分布是平均分布的，没有任何的能量集中， 是严格平坦矩阵。矩阵中每个元素分量都是，此时的相干值 取最小值“1” ，说明此时两 个矩阵是完全不相干的。此时所对应的测量值y中的m个分量是所有原始信号的线性组合，每 南京邮电大学硕士研究生学位论文 第二章 压缩感知理论介绍 12 个信号分量都包含了一部分原始信号的信息，可能通过迭代算法重构出原始信号。 以上是两个矩阵间相关性的衡量，当该值较大时，两矩阵的相关性较大，反之则相关性 较小。相干性的取值范围为： 。 本小节对相干做了定量的分析，并给出了其表达式。但是，在实际的实现过程，并不能 找到完全符合最小值条件的测量矩阵，因为不可能将测量矩阵设计的完全满足正交的条件， 但可以通过对测量矩阵的不断改进以最大程度的降低与稀疏基的相干性。 2.2.2 限制等容性 限制等容性为压缩感知理论的稀疏重构问题提供了一个充分条件，可以用此性质判断所 选取的测量矩阵是否满足条件。 对原始信号随机测量会得到包含全局信息的观测值， 是需要测量的原始信号， 是一个的矩阵，观测值 的维数远远小于信号 的维数，因此的性质决定了通过少量 观测值 重构原始信号的稳定性。文献 47 提出了一种方法，即要使