（通信与信息系统专业论文）压缩感知在图像处理中的应用.pdf

摘要 论文题目： 学科专业： 研究生： 指导教师： 压缩感知在图像处理中的应用 通信与信息系统 焦铸 张志禹教授 摘要 i | i i i i i i | i i i i i i i i i i i i i i i n i i i i i | i i i i y 2 12 8 6 6 1 签名：蕉镄签名：怎萌 签名盐堕南签名：芏止幼 压缩感知理论突破传统的n y q u i s t 采样方法对数据进行处理，不仅缓解了采样设备的 压力，而且使系统的整体性能得到了显著提高。压缩感知理论前提要求数据在某个基下具 有稀疏表示，这样就可从远少于传统采样数目的测量值中，高概率地恢复重构出原始数据。 目前，压缩感知理论在学术领域被广泛关注，并在实际中得到了初步应用。 压缩感知理论研究的核心问题是随机测量和恢复重构算法，本文主要将压缩感知应用 于数字图像领域。文章首先对压缩感知理论的基本现状进行了初步的介绍；其次，介绍了 几种常用的随机测量矩阵和恢复重构算法，使用m a t l a b 进行仿真比较，通过仿真结果验 证问题的可行性；最后，结合矩阵的相关性，构造了由测量矩阵和稀疏矩阵所决定的g r a m 矩阵，并对g r a m 矩阵进行门限判决和缩放处理，进而降低矩阵间的相关性，这样就可以 通过使用优化改进后的测量矩阵获取到更多有信息量的测量值，进而完成对测量值的优化 改进，并结合不同的恢复重构算法在m a t l a b 环境下对改进方法进行仿真验证，仿真结果 证实了改进方法的正确性，具有较高的研究和应用价值。 关键字：压缩感知测量矩阵重构算法相关性 西安理工大学硕士学位论文 i i a b s t r a c t t i t l e ：a p p l i c a t i o no f c o m p r e s s e ds e n s i n go ni m a g e p r o c e s s l n g m a j o r ：c o m m u n i c a t i o na n d i n f o r m a t i o ns y s t e m n a m e ：z h uj i a o s u p e r v i s o r ：p r o f z h i y uz h a n g a b s t r a c t s i g n a t u r e ： 了i 归z 矗姨 s i g n a t u r e ： t h ec o m p r e s s e ds e n s i n gt h e o r yb r e a kt h r o u g ht h et r a d i t i o n a ln y q u i s ts a m p l i n gm e t h o di n a c c o r d a n c ew i n lt h ed a t ap r o c e s s i n g n o to n l ye a s et h ep r e s s u r eo ft h es a m p l i n ge q u i p m e n t , a n d o v e r a l lp e r f o r m a n c eo ft h es y s t e mh a sb e e ni m p r o v e ds i g n i f i c a n t l y a sl o n ga st h en e x tb a s e w h e nt h ed a t ai nas p a r s ec a i lb er e p r e s e n t e d ，i ti sf a rl e s st h a nt r a d i t i o n a ls a m p l i n gf r o mt h e n u m b e ro fm e a s u r e m e n td a t at oas m a l l e rp r o b a b i l i t yo fe r r o rr e c o v e r yr e c o n s t r u c tt h eo r i g i n a l d a t a c u r r e n t l y , t h ec o m p r e s s e ds e n s i n gt h e o r yh a sb e e nw i d e s p r e a dc o n c e r ni nt h ea c a d e m i c f i e l da n di n i t i a l l ya p p l i e di np r a c t i c e t h ec o r ei s s u e so fc o m p r e s s e ds e n s i n gt h e o r yi sr a n d o mm e a s u r e m e n ta n dr e c o v e r y r e c o n s t r u c t i o na l g o r i t h m t h ep a p e rw i l lb ea p p l i e dt od i g i t a li m a g ec o m p r e s s i o nf i e l do f p e r c e p t i o n f i r s t l y ，a ni n i t i a ls t a t u so ft h ei n t r o d u c t i o ni nt h eb a s i ct h e o r yo fc o m p r e s s e d s e n s i n g ；s e c o n d l y , i n t r o d u c e ss e v e r a lp o p u l a rr a n d o mm e a s u r e m e n tm a t r i xa n dt h 9r e c o v e r y a n dr e c o n s t r u c t i o na l g o r i t h m ，u s i n gm a t l a bs o f t w a r es i m u l a t i o na n dc o m p a r i s o n ，t h e s i m u l a t i o nr e s u l t sv e r i f yt h ef e a s i b i l i t yo ft h ep r o b l e m ；f i n a l l y , c o m b i n a t i o no fm a t r i x r e l a t e d p r o b l e m s ，c o n s t r u c t e db ) rt h em e a s u r e m e n tm a t r i xa n ds p a r s em a t r i xd e t e r m i n e db yt h eg r a m m a t r i x ，t h e nt h eg r a mm a t r i xo ft h r e s h o l dd e c i s i o na n dt h ec o r r e s p o n d i n gs c a l i n gp r o c e s s i n g ， r e d u c et h em a t r i xc o r r e l a t i o nb e t w e e n ，s ot h a tw ec a no p t i m i z et h ei m p r o v e dm e a s u r e m e n t m a t r i xf o rt h em e a s u r e m e n t so fm o r ei n f o r m a t i o n ，a n dt h e nc o m p l e t e dt h eo p t i m i z a t i o no f m e a s u r e m e n ti m p r o v e m e n t s ，c o m b i n e dw i md i f f e r e n tr e c o v e r yr e c o n s t r u c t i o na l g o r i t h mt o s i m u l a t et h ei m p r o v e dm e t h o di nm a t l a be n v i r o n m e n t , t h es i m u l a t i o nr e s u l t sp r o v et h e c o r r e c t n e s so ft h ei m p r o v e dm e t h o d 、析t hh i g hr e s e a r c ha n da p p l i c a t i o n k e y w o r d s ：c o m p r e s s e d s e n s i n g ；m e a s u r e m e n t m a t r i x ；r e c o n s t r u c t i o n - a l g o r i t h m ；c o r r e l a t i o n i i i 西安理工大学硕士学位论文 i v 目录 _ 一 目录 1 绪论l 1 1 研究背景和意义1 1 2 国内外研究现状2 1 2 1 随机测量矩阵的概述2 1 2 2 压缩感知恢复重构算法的概述3 1 3 压缩感知的应用3 1 4 主要工作和结构安排5 2 压缩感知的理论框架7 2 1 传统采样理论7 2 2 压缩感知理论7 2 2 1 信号的稀疏表示8 2 2 2 压缩感知的测量矩阵9 2 2 3 恢复重构1 1 2 3 本章总结1 2 3 压缩感知的测量矩阵研究1 5 3 1 常用测量矩阵1 5 3 1 1 随机高斯测量矩阵1 5 3 1 2 随机贝努利测量矩阵一1 6 3 1 3 其它测量矩阵1 7 3 2 对矩阵的改进1 8 3 2 1 理论描述1 8 3 2 2 实现方法1 8 3 2 3 实验仿真2 0 3 3 本章总结2 6 4 压缩感知的恢复重构算法研究2 7 4 1 算法概述2 7 4 2 正交匹配追踪算法2 7 4 2 1 匹配追踪类算法一2 7 4 2 2 正交匹配追踪算法2 8 4 3 子空间追踪算法3 2 4 4 压缩采样匹配追踪算法3 5 4 5 基追踪方法3 6 4 6 其它算法3 8 西安理工大学硕士学位论文 4 7 本章总结3 8 5 总结和展望3 9 5 1 论文工作总结3 9 5 2 后续工作展望：3 9 致谢4 1 参考文献4 3 i i 1 绪论 1 - 1 研究背景和意义 随着现代社会的日益信息化以及i n t e r n e t 技术的普遍应用，数字图像处理技术在现 实生活的作用越来越重要，该问题的研究已经成为工程学领域各学科甚至社会科学间学习 和研究的对象。图像信息凭借其他信息所不具备的诸多优点，比如信息量大、传输速度快 等j 从而成为现实生活中我们获取信息的首要选择，是处理信息的主要手段之一。因此在 信息社会中，数字图像处理技术不仅仅在理论问题研究上而且在具体问题的实践上都有着 巨大发展空间n 1 。 遵循传统方法对数据处理要满足n y q u i s t 采样定理，该理论的核心思想是对采样过程 中采样率的做了要求，也就是我们通常所说的n y q u i s t 采样率。当我们在采样端对数据进 行采样，就可以在解码端通过反变化从采样数据中高概率的恢复重构出原始数据。随着科 学技术的发展进步，人们对高带宽数据的需求日益增大，如果依照传统采样方法对数据进 行采样，这就给n y q u i s t 采样速率提出了更高的要求，相应地给采样设备提出了更大的挑 战并且对系统的整体性能造成一定影响，严重影响了信息处理领域的进步发展，基于此我 们就在想是否可以突破n y q u i s t 采样率的束缚，建立一种新的数据处理理论，以远低于传 统采样率的要求对信号采样，并且能够从采样值中高概率地恢复重构出原始数据? 如果这 个问题得以解决，就可以提高系统的整体性能，进而推动信息领域的发展。我们知道 n y q u i s t 采样率是数据准确恢复重构的充分条件，但绝不是必要条件。 以具有稀疏性或可压缩的的信号为研究对象，d d o n o h o 【2 1 和e c a n d e s l 3 1 4 j r o m b e r g 、 t t a od 1 结合信号分解、逼近论、统计理论和时谐分析等基本理论，于2 0 0 4 年提出了压 缩感知( c o m p r e s s i v es a m p li n go rc o m p r e s s i v es e n s i n g ，c s ) 的初步理论框架，并于2 0 0 6 年发表正式学术论文，在接下来的几年中，压缩感知理论得到了快速发展，从而为突破 n y q u i s t 采样率的束缚奠定了理论基础。从压缩感知理论中我们知道，当原始数据是可稀 疏表示或可压缩的，我们就可以通过合理的恢复重构算法，从远低于传统的采样率要求对 信号采样，并且可以从采样值中高概率地恢复重构出原始数据，从而将采样与压缩进行了 有效地结合。在新的框架中我们关注的重点从采样端转移到解码端，这就缓解了采集端的 压力。在实际应用中，为了确保采集数据的完整性，采样率不再单单是2 倍于信号带宽， 往往是数倍于信号带宽。因此，压缩感知对于采样理论的突破就更具有实际意义。 压缩感知核心研究问题之一是如何降低对一个信号随机测量的代价。对于研究对象， 如果按照传统信息处理理论，当数据量比较大时，系统的整体性能就会受到影响。对于压 缩感知，我们理论研究的前提条件是信号具有可稀疏表示或可压缩，那么我们就可以通过 西安理工大学硕士学位论文 一一_ 远少于数据量的测量值中高概率地恢复重构出原始数据。压缩感知理论问题的研究涵盖了 许多基础学科，应用范围也很广泛，因此得到了科学界的普遍关注和研究，在短短的时间 内，得到了较快的发展。目前而言，压缩感知的工作主要集中在以下几个方面：随机测 量矩阵的研究，该问题的研究关系到测量值的数目；恢复重构算法，如何设计合理有效 的恢复重构算法；如何提高改进系统的整体性能。 1 2 国内外研究现状 压缩感知理论是信息理论的进步发展，具有其它方法所不具备的高度信息挖掘能力， 在数字图像处理、模式识别、地质勘探、无限传感器网络等众多领域受到了高度重视。由 于压缩感知理论刚刚起步，但已取得了惊人的发展速度，并表现出强大的生命力，理论研 究工作也在逐步完善。 目前，压缩感知已成为了国内外数学领域和工程应用领域的热点研究问题，国内外的 知名大学和跨国公司都对压缩感知展开了相应地研究工作，并取得了初步成绩。与此同时， 美国政府部门和高校联合召开了压缩感知的探讨工作，对于该理论的发展扮演了重要角 色。并且，莱斯大学还成立了专门的网站对压缩感知问题进行总结研究工作1 。 压缩感知问题研究中主要涉及三个问题，信号的稀疏性是压缩感知的前提条件，非相 关测量是压缩感知的研究关键，非线性优化是压缩感知恢复重构的方法。在压缩感知的研 究过程中，构建硬件易于实现的测量矩阵和快速稳定高效的恢复重构算法是我们的主要工 作，下边就这两个问题研究工作做一简单描述。 1 2 1 随机测量矩阵的概述 我们通过随机测量矩阵获取信号的随机测量值，测量值中之所以可以包含恢复重构信 号中的重要信息，对于测量矩阵而言，就要求其满足受限等距特性( r e s t r i c t e di s o m - e t r yp r o p e r t y ，r i p ) “1 ，在实际应用工作中，研究人员将主要精力致力于研究某一个测 量矩阵对于实际问题是否可以适用以及由该测量矩阵获取的测量值数目等问题。我们将满 足特性的矩阵大致分为三类，第一类是服从高斯分布的随机测量矩阵u 1 和随机贝努利测 量矩阵阳1 ；第二类是局部傅里叶矩阵等9 1 ；第三类是近年来专家学者提出的结构随机矩 阵n 0 1 。测量矩阵的研究工作具有重要的实际意义，因为测量矩阵的硬件实现对推动压缩感 知向实际应用起到了关键作用。目前，莱斯大学的r b a r a n i u k 教授等成功研制了单像素 数码相机n ，该硬件设备也得到了相应地理论论证，该相机的缺点就是成本昂贵，并且恢 复重构算法效率低下；k r i o l o s 教授等基于压缩感知理论设计了模拟信息转化器， r b a r a n i u k 教授等在此基础上进步发展了基于随机采样的模拟信息转化器n n 钉；伊利 2 绪论 一一一 诺伊州立大学o m il e n k o v i c 教授等利用压缩感知成功设计了d n a 微阵列传感器1 5 1 等，这 些硬件设备的实现进步推动了压缩感知的实用化进程。 从上述分析我们可以看出，随机测量矩阵的研究重点是如何减少测量数据，因此我们 今后的工作重点是如何有效地解决如下问题：测量值的数据量问题；硬件实现的问题； 是否具有广泛适用性的问题。 1 2 2 压缩感知恢复重构算法的概述 压缩感知研究中的另一个重点问题就是恢复重构算法。恢复重构算法主要研究如何通 过远少于传统方法采样数量的测量值高概率地恢复重构出原始数据。压缩感知中的测量获 取过程是全局非自适应的，这样不仅可以有效减少数据采集量，同时也降低恢复重构算法 的软件成本。 目前压缩感知的恢复重构算法大致可以分为三类，每类恢复重构方法都有其自身的优 缺点，对于不同的数据表现出的性能差异也比较大，另外，有些恢复重构算法的研究中， 数据的稀疏度是一个重点研究参量，因此如何建立动态的随机测量方式和恢复重构算法是 今后研究的重点，最优化的恢复重构算法需要满足以下条件：测量值的数目越少越好； 恢复重构的速度，这将影响到系统的整体性能；具有广泛适用性。 1 3 压缩感知的应用 压缩感知理论中，我们能够从少量的非相关测量值中高概率恢复重构出原始信号，这 种非对称的数据处理模式为信号处理带来了新的热潮，具有广泛的适用范围，在压缩成像 “、模拟信息转换n 3 1 4 1 、雷达成像n 6 3 等方面都有应用，简介如下： ( 1 ) 压缩成像：对于传统硬件设计有很大局限性的领域我们可以通过有效的数学计算 方法来进行改进。传统方法采用的c c d 或c m o s 成像设备，在实际技术应用中仅局限于可 见光光谱，然而基于压缩感知理论构造的数码相机使用数字微镜( d i g i t a lm i c r o m i r r o r d e v i c e ，d m d ) 阵列就可以获取到原始数据的全部非相关测量值，比起传统的数码相机，该 器件只需要一个感光元件而不再是数百万个感光元件。图1 - 1 是单像素数码相机的简易 图，与传统数码相机的最大不同之处在于对于数据的获取方式，传统的相机利用光学传感 阵列直接获取数据，而单像素相机则借助于d m d 来完成对数据的采集工作。微镜阵列上的 反射光通过透镜聚集到单个光电二极管上，这也就是所谓的单像素，当微镜面对光电二极 管时，这就是数值1 ，而当微镜远离光电二极管时相当于时0 ，通过机械运动来调整数字 微镜与光q t - 极管的角度从而形成随机测量矩阵。其中光电二极管两端的电压值对应的是 一次有效的测量值，将此测量过程重复m 次进而获取到测量矩阵，最后在接收端通过相应 地恢复重构算法恢复重构出原始数据。这种物理实现过程验证了低像素相机拍摄高质量的 苎塞兰二! ! 翌! ! 些垒查 图像的可能性这就有效的降低了系统的整体负担，也推动了压缩感知的进步发展。 翻卜1 单像素压缩感知相机 f i g u r e l 一1s i n g l e p l x e lc o m p n s i v es e n s i n g c a m e r a ( 2 ) 模拟信息转换：我们的目标是降低传统模拟数字( a n a l o g t o - d i g i t a l ，a i d ) 转 换的压力，进而实现将模拟信号直接转化为信息，这就是所谓的模拟信息 ( a n a l o g - t o i n f o r m a t i o n ) 转换。圈卜2 是我们问题中所涉及到的模拟信号到信息转化器 ( a n a l o g - t o i n f o r m a t i o nc o v c r t c r , a i c ) 的设计框架： 圈卜2 模拟信息转换 f i g u r c l - 2 a n a l o g - t o - i n f o r m a t i o nc o l l v e i 。f e r ( 3 ) 雷达成像：文献 1 6 在压缩感知理论的基础上引入了一种新的雷达成像方法，新 的方法有在两个方面取得了显著的改善。首先在接收端消除了对于匹配滤波器的需求；其 次有效降低了接收端对于模数转换所需带宽的要求。这些措施简化了雷达的设计，使得我 们研究问题的重点由昂贵的接收端转移到设计智能的恢复重构算法。文献 17 将压缩感知 理论应用到s a r 图像处理上，使得卫星图像处理的计算复杂性得到了有效的降低。 ( 4 ) 数据压缩：在某些情况下，对于编码端而言稀疏基是未知的，或者说从数据压缩 角度看实现是不切实际的，但是，一个随机测量矩阵被认为是一种随机的编码策略，因为 它的设计构造与稀疏基是不相关的，这种稀疏性对于分布式多源编码是具有实际研究意义 的，比如无线传感器网络“”。 绪论 此外，压缩感知理论在医学图像处理m 1 、信道编码n 1 等众多领域都有相应的应用。 1 4 主要工作和结构安排 本文总体上分为5 章，各章具体布局及内容如下： 第一章：绪论。介绍了压缩感知课题的研究背景和意义，阐述了压缩感知国内外发展 现状以及主要应用，列出了本文的主要研究内容和结构安排。 第二章：压缩感知的理论框架。在传统信号编解码理论的基础上，引出了基于压缩感 知的编解码理论框架，介绍了压缩感知的基本理论思想。然后对信号的稀疏表示、随机测 量矩阵以及恢复重构算法进行了详细的总结分析，为压缩感知的应用工作奠定了理论基 础。 第三章：压缩感知的测量矩阵研究。本章对压缩感知中常用的测量矩阵进行了介绍， 并结合不同采样比率、不同恢复重构算法对几个常用的测量矩阵进行了实验仿真。然后从 随机测量矩阵和稀疏基间的相关性的角度出发，对测量矩阵进行优化改进，进而完成对测 量值的优化工作，并分别结合一维、二维数据信号进行仿真验证。 第四章：压缩感知的重构算法研究。本章对压缩感知中现有的三类算法进行了综述， 着重对几种有代表性的算法展开分析研究，对算法的原理、内容和性能进行了介绍，通过 仿真实验对结果进行分析。 第五章：总结与展望。本章对课题的整体研究工作进行了总结，并对研究工作中存在 的不足进行了分析总结，并对今后的研究工作做了进步的展望。 西安理工大学硕士学位论文 _ 二_ 二一一 6 一 垦堕壁垒竺堡鲨墨 一 _ 一一 2 压缩感知的理论框架 2 1 传统采样理论 我们按照传统方法对数据进行采集要遵循n y q u i s t 采样定理，在该理论框架下进行信 号采集、编解码需要遵照如图2 1 所示的过程执行， 篓竺钷田叫至三堕p 码匕刮采样吲变换、压缩编码p 端l j l _ 一 解 接收数据y 厂 恢复信号殳 码匕= = = 剖解压缩、反变化 = = = = = 令 端l 一 图2 - i 传统框架 f i g u r e 2 1t h et r a d i t i o n a lf r a m e w o r k 在传统的框架中，编码端先获取信号的采样值，在变换编码过程中，将变换得到的重 要系数的信息进行编码，然后将编码值进行传输或存储；解码端接收到压缩数据后进行相 应的解压缩和反变化进而恢复重构出原始数据，对处理过程进行比较我们可以看出，解码 过程就是编码过程的逆过程。但是这种方法也存在其不足之处由于受限于n y q u is t 采样 率的要求，对于采样设备就会存在过大的采样压力；在变化编码过程中，我们将舍弃不 需要的信息量，这就会给系统造成不必要的资源浪费。 2 2 压缩感知理论 科学研究发现n y q u is t 采样定理并不是采样过程中唯一最优化选择方案，压缩感知理 论的提出不是对传统方法的否定，只是一种新的信息获取方式。当我们采集的数据具有稀 疏性或可压缩性时，我们就可以从远少于n y q u i s t 采样率要求数目的测量值中高概率的恢 复重构出原始数据。图2 2 所示的是基于压缩感知理论的数据处理框架图，相比于传统方 法，不同之处在于编码端，压缩感知将数据的采集和压缩有效结合，进而获取数据的非自 适应测量值，从而完成对数据的有效降维处理。对于每个采集到的测量值，从数学角度分 析它是样本信号的组合函数。对于解码端，借助于算法实现恢复重构，这个求解过程不是 一个简单的求逆过程。由于传输或存储中的测量值的数目远少于原始数据，这样一来，传 输信道的性能就可以得到极大的提高。 7 西安理工大学硕士学位论文 羹兰当匹互 与 码匕= = = = 刮测量编码 = = = = 令 端l - j 解 接收数据y 厂 恢复信号文 码匕= = = 剖解码重构 = = = 穹 端l _ j 图2 2 压缩感知框架 f i g u r e 2 - 2t h ec o m p r e s s i v es e n s i n gf r a m e w o r k 压缩感知的研究主要涉及三个方面：信号的稀疏变换、随机测量和恢复重构算法，更 具实际研究意义的主要是后两个问题，因为这两个问题决定着压缩感知理论的发展和实用 化进程。因此，我们需要解决如何构造合理的测量矩阵以减少测量值数目和构思高效的恢 复重构算法这两个问题。压缩感知作为一种新的理论，是对传统方法的突破，有着极大的 研究价值和广阔的应用前景。下边我们就压缩感知的研究问题逐一介绍。 2 2 1 信号的稀疏表示 数据的分析方法从最早的f o u r i e r 变换再到最近几年发展的多尺度几何分析，我们研 究的目的就是寻找信号在不同基空间下简洁的分析方式，由表述方式来研究数据的稀疏程 度或者分解系数的能量集中程度。数据的稀疏表示是压缩感知研究的前提条件。自然界的 大多数信号通过不同的基函数都可以有效地稀疏表示或者说大多说信号是可压缩的，这样 二来压缩感知的研究工作就有了实际价值，因此我们的首要工作就是找到合适的基来对数 据进行稀疏分解，只要我们实现了数据的稀疏表示，就可以高效地实现压缩感知，该问题 的研究是压缩感知理论研究中的重难点。 为了简化问题，我们假令一长度为n 的离散实值信号x ，记为x ( n ) ，其中n e 1 ，2 ， n 。由调和分析理论可知x 能够用一组标准正交基y r = y 。，l f ，：，e o o 9 l f ，。，o o 9 y m 的线性组合表示，其中l f ，r 为y 的转置，即， x = y i a t = l f ，a ( 2 1 ) 七= l 式中：a _ | = ( x ，y | ) ； a n l 矩阵； x _ n 1 矩阵； y _ n n 的矩阵 当x 在某个矩阵l ，上有且仅有k 个非零系数时，则称l f ，为信号x 的稀疏基，其中k 是一个远小于n 的量。对于式( 2 1 ) ，这是信号在不同域中的等价表示，其中x 对应于时 8 压缩感知的理论框架 一一一 域，a 对应于v 域。 信号稀疏表示的目的在于提升信号的非线性函数逼近能力，稀疏基的 有效选取将对稀疏系数的数据量产生影响，当系数较少时，系统的整体性能将得到提高。 实际问题中，我们研究的对象并不都是严格稀疏的，只是近似稀疏的，当变换系数呈指数 衰减时，我们认定该信号也是稀疏的b 。 近年来，信号的稀疏性和稀疏变换基在信号处理领域得到了广泛应用，尤其是信号在 冗余字典下的稀疏表示成为该领域研究的热点问题，该方法的提出要追溯到1 9 9 3 年，由 s m a l l a t 和z z h a n g 乜3 1 首先提出，相对于传统理论中基函数的选取策略，新理论中引入 了超完备的冗余字典或冗余函数库，库中的元素称为原子，并首次提出了匹配追踪 ( m a t c h i n gp u r s u i t ，m p ) 算法来恢复重构原始数据，从理论和实验等多方面验证了方法 的可行性。冗余字典思想的提出对于信号稀疏表示是一种全新的理念，这样将基函数的选 取范围扩大到一系列具有一定相关性的基函数上而不再是某一种特定的正交基，进而实现 信号的稀疏逼近或者高度非线性逼近。 2 2 2 压缩感知的测量矩阵 压缩感知研究的重点问题之一是线性测量，通过这个过程我们可以获取到数据的随机 测量值，为了高概率的恢复重构出原始数据，就要确保随机测量值中包含原始数据中足够 的信息量。我们用数学方法对该阶段实现过程进行描述，通过构造合理的测量矩阵 妒= 【，仍，】，进而通过投影得到原始数据的测量值匕= ( x ，缈j ：) ，用矩阵形式表 一、r 不为， y = 驴x( 2 2 ) 式中：卜_ n 1 矩阵； y 一- m 1 矩阵； 西_ m n 的测量矩阵。 结合式( 2 1 ) ( 2 2 ) 有， y = x = l f ，a = o a( 2 3 ) 式中：o _ m n 的感知矩阵。 这个过程中，测量矩阵的每一行的作用看做是一个传感器，通过与信号做乘积运算 获取信号的部分信息，通过这些随机测量值和测量矩阵，我们就可以高概率地恢复重构出 原始数据。由于测量值和原始数据之间数目上的不对称性，既然可以由少量测量值中恢复 重构出原始数据，测量矩阵就应该满足某种特性，这其中就包括了不相干性瞰1 和受限等距 性两个条件。 为了实现高概率地恢复重构，压缩感知要求随机测量矩阵和稀疏矩阵之间是不相干 的，对于原始数据而言，随机测量矩阵和稀疏矩阵间的相干性定义为， 9 西簧理工大学硕士学位论文 二一 p ( ，甲) 2 孙m a x 引i ( 、妒一- ，甲剧 ( 2 4 ) 相干性是用来衡量随机测量矩阵和稀疏矩阵间任何两元素问的最大相关性。如果随机 测量矩阵和稀疏矩阵间包含了相关元素，相干性就大，反之就小，则j l l 的取值范围为： j l l ( ，甲) l1 ，刀i 。d d o n o h o 等在文献 4 1 中列出了几种满足不相干的情况。 ( 1 ) 当随机测量矩阵选取规范或者冲激函数基( r ) = 6 ( f k ) ，稀疏基选择 l f ，( f ) = 1 , i - l 2 e 口础厢的f o u r i e r 基时，由于随机测量矩阵对应于传统的时域或者空域的采样 理论，此时p ( ，甲) = l ，这也就是随机测量矩阵和稀疏基之间的最大不相干性。然而， 两者之间不仅在一维情况下表现最大不相干性，而且在二维、三维甚至多维情况下也都表 现出最大不相干性。 ( 2 ) 当随机测量矩阵选取n o i s e l e t 2 5 1 稀疏基选择小波基时，n o i s e l e t 和h a a r 小波 间的相干性为2 ，n o i s e l e t 和d a u b e c h i e sd 4 小波问的相干性是2 2 、和d a u b e c h i e sd 8 小波问的相干性是2 9 ，当然这种情况也可以扩展到维数更高的情况。我们之所以对 n o i s e l e t 感兴趣来自以下原因，首先它与提供图像数据或其他类型数据稀疏表示的系统 不相干；其次提供了快速的算法，这对于压缩感知有效地数值计算是至关重要的。实际上， n o i s e l e t 与冲击函数基和f o u r i e r 基也都具有不相干性。 ( 3 ) 随机测量矩阵和任何固定基间都有较大的不相干性。通过独立均匀的在单位球面 上采样n 个正交化向量得到的均匀随机测量矩阵，这时随机测量矩阵和稀疏基间的相干性 大约为、2 l o g 万，进一步讲，独立同随机分布的随机信号，比如服从高斯分布的随机矩阵 或者二值矩阵与任意固定基之间也都具有很低的相干性。 由于测量值数目是一个远小于信号长度的量，因此( 2 2 ) 的求解是n p h a r d 问题，即 一个非多项式难度问题，但是a 是一个稀疏的量，可以通过相应的稀疏分解算法，通过求 解( 2 3 ) 得出稀疏系数a ，进而通过式( 2 1 ) 恢复重构信号x 。这就要求随机测量矩阵不仅 仅要满足不相干性，还要满足受限等距特性( r e s t r i c t e di s o m e t r yp r o p e r t y ，r i p ) ，具体 表述为， ( 1 一以) 州- 蚓 处理后g r 是一个满秩的矩阵，我们需要对其采用s v d 分解进行降维处理，使其维数 和测量矩阵的维数相同，并通过& = 瓯来寻求哝的方根& ，& 和测量矩阵具有同样 的行列数。 通过0 & 一妒l f ，旺的最小化误差来选取九“，进而完成对测量矩阵的更新。然后令 k = k + i ，重新开始迭代，对测量矩阵进行进一步的优化处理。 3 2 3 实验仿真 依照上述对于测量矩阵的优化思路，我们选取迭代次数i t e r 为1 0 ，门限参数t 1 为 0 2 ，缩放参数t 2 为0 0 5 ，采用o m p 恢复算法，该算法保证了每步迭代的优越性，减少 了迭代的次数，同时o m p 算法保证了在每步迭代后，信号残余与以前选择的所有原子都正 交。实验结果如图3 4 所示， 2 0 压缩感知的测量矩阵研究 糌 糕 账 靛 罂 测量值数目 图3 - 4 随机高斯矩阵下的性能比较 f i g u r e 3 - 4t h ec o m p a r i s o no fp e r f o r m a n c eb yr a n d o mg a u s s i a nm a t r i x 图3 4 中的每个点是基于多次实验的平均性能，随着测量值数目的增加，恢复算法的 性能得到了提升改善，在某些测量点甚至有较大幅度的提高，从而证实了改进方法的可行 性。下边我们就一维信号、二维信号进行具体的实验分析，各具体参数依照上述实验中的 参数选取。 我们假令一组一维正弦信号为： y = 0 2s i n ( 2 z rx2 0 0 t ) + 0 4s i n ( 2 z rx5 0 t ) + 0 6s i n ( 2 7 rx4 0 0 t ) + 0 8s i n ( 2 z r l0 0 0 实验结果如图3 5 所示， 2 l 西安理工大学硕士学位论文 ( d ) 改进后误差 图3 - 5 一维信号的性能比较 f i g u r e 3 - 5t h ec o m p a r i s o no fp e r f o r m a n c eb yo n e - d i m e n s i o n a ls i g n a l 由图3 - 5 可以看出，改进后的测量矩阵对于恢复结果的误差有所减小，恢复效果也有 一定程度的提高。改进前的方法恢复重构信号与原始信号间的相对误差降一x 0 i l x 0 ：为 4 0 9 3 6 e - 0 1 4 ，改进后的的相对误差为3 0 3 8 0 e - 0 1 4 。 ” ” 对于二维图像的恢复重构，我们选取l e n a 2 5 6 x 2 5 6 图像作为实验对象进行恢复重构， 在采样比率( m n ) 分别为0 7 、o 6 、0 5 、0 4 、0 3 时，分别采用正交匹配追踪( 0 m p ) 算法、 基追踪( b p ) 算法、子空间追踪( s p ) 算法、压缩采样匹配追踪( c o s a i p ) 算法进行优化恢复重 构，实验结果如图3 6 、3 7 、3 8 、3 9 所示。 压缩感知的目4 量矩阵研究 ( d ) 采样比率为05( e ) 采样比率为0 4( n 采样比率为03 图3 7 基追踪方法f 的l e n a 2 5 6 。2 5 6 的恢复重构效果 f i g u r e 3 7 r e c o n s t r u c l i o ne f f e c t o f b p f o r l e n a u 2 5 6 x 2 5 6 西安理工大学硕士学位论文 ( d ) 采样比率为05( e ) 采样比率为0 4( o 采样比率为03 图3 - 9 子空间追踪算法下的l e n a 2 5 6 x 2 5 6 的恢复重构效果 f i g u r e 3 - 9 r e c o n s t r j c t i o n e f f e c to f s p f o r l e n a 2 5 6 。2 5 6 我们以p s n r ( 峰值信噪比) 为考量依据，以二维图像为研究对象，优化改进后的测量 矩阵相比改进前的恢复重构有3 _ 8 左右的性能提高。通过实验我们可以得知，这种对测 量矩阵的优化改进方法是可行的。参数的选取针对不同的信号会有些差别，对于不同采样 比率和不同的恢复重构算法，改进的效果也不完全相同。图3 1 0 、31 1 分别针对具体结 压缩感知的测量矩阵研究 果进行了统计， 叱 z 乱 3 j l 棼 妲 j 霉 磐? 图3 - 1 0 随机高斯测量矩阵下不同算法不同采样率下的比较 f i g u r e 3 - 1 0t h ec o m p a r i s o no fd i f f e r e n ts a m p l i n g r a t e sw i t hd i f f e r e n ta l g o r i t h m s b yr a n d o mg a u s s i a nm e a s u r e m e n tm a t r i x 一叱z酊d)蓝凿姆迥磐 一叱zd)丑凿逛趔磐 一叱zd)丑喾姆迥彗 西安k - y - 大学硕士学位论文 番b 样) a 比p g 裂n ) (法 图3 - 1 1 随机贝努利测量矩阵下不同算法不同采样率下的比较 f i g u r e 3 11t h ec o m p a r i s o no f d i f f e r e n ts a m p l i n gr a t e sw i t hd i f f e r e n ta l g o r i t h m s b yr a n d o mb e r n o u l l im e a s u r e m e n tm a t r i x 由图3 - 1 0 、3 - 11 的对比结果可以看出，优化改进后的随机测量矩阵可以比较理想地 恢复重构出原始图像，在某些采样比率下恢复重构的效果有较大幅度的提高，使用该方法 对测量矩阵进行优化改进同样存在缺点，对于不同恢复重构算法、不同采样比率下的改进 的效果不同，同时由于算法中增添了对测量矩阵的优化改进，会增加随机测量的时间，对 整体性能有所影响。 3 3 本章总结 本章首先介绍了压缩感知中常用测量矩阵的构造方法，结合不同恢复重构算法、不同 采样比率对恢复重构结果进行分析比较，对压缩感知的研究工作提供了指导作用。其次从 稀疏基和随机测量矩阵间的相关性角度出发，对随机测量矩阵进行优化改进工作，通过实 验仿真验证了方法的可行性。 一叱zd)羞凿逛姆鹫 一叱zd)丑棼逛姆彗 一叱zd)丑誉逛姆鹫一叱zd)丑凿逛姆磐 4 压缩感知的恢复重构算法研究 压缩感知恢复重构是指利用获得的测量值通过合适的算法恢复重构出原始数据。一种 实施效率高、恢复重构结果优越的恢复重构算法是压缩感知理论问题中研究的重点，该问 题的研