（电路与系统专业论文）基于二分图邻接矩阵的压缩传感图像重建算法研究.pdf

l 一一 摘要 iyiitllllllll119llllll1llllllllllll6llll14llllll6lly 19 116 4 6 在传统的信号采样中，为了避免信号失真，尼奎斯特香农采样 定理指出采样频不得低于信号最高频率的2 倍，随着科技的发展，信 号的频率越来越高，按照尼奎斯特香农定理会导致海量采样数据，大 大增加了存储和传输负担。最近d o n o h o 和c a n d 色s 等提出的压缩传感 ( c o m p r e s s e ds e n s i n g ) 理论为数据采集带来了革命性的突破。该理 论利用原始信号可稀疏表示这一先验知识，通过合适的优化算法，能 从远低于尼奎斯特采样率的少量非自适线性投影中精确重构原始信 号。压缩传感理论主要包括三方面内容：信号稀疏表示，量测采样和 信号重构。目前压缩传感的研究尚处初级阶段，理论研究主要集中在 量测采样所用的量测矩阵和信号重构的恢复算法。 压缩传感在编解码过程中存在大量高维投影计算，而普通的随机 测量矩阵由于其稠密性使得计算量大，运行时间长，降低了压缩传感 的性能。本文基于量测矩阵的研究，提出了一种基于二分图邻接矩阵 的非常稀疏压缩传感量测矩阵。利用该矩阵的稀疏性与二值性，证明 了该矩阵满足压缩传感量测矩阵的的必要条件。并利用该矩阵的稀疏 性特征，对编解码算法中的投影计算使用稀疏矩阵乘法完成，使得投 影计算复杂度从o ( n l o g n ) 降低到o ( n ) ，并将该稀疏矩阵乘法应用到 重构算法s t o m p 中，得到一种改进的s t o m p 快速重构算法。 压缩传感打破了多年来信号处理领域一直遵循的尼奎斯特香农 采样定理，带来了革命性的突破，具有广泛的应用前景，本文在最后 对压缩传感的应用进行了探讨。 关键字：压缩传感；信号重构；二分图邻接矩阵；s t o m p ；图像重构 a b s t r a c t i nt h et r a d i t i o n a ls i g n a ls a m p l i n gp r o c e s s ，n y q u i s t s h a n n o ns a m p - l i n gt h e o r e mi n d i c a t e dt h a tt h es a m p l i n gf r e q u e n c ym u s t a tl e a s tt w i c et h e h i g h e s tf r e q u e n c yo f t h es i g n a lf o rp r e v e n t i n gd i s t o r t i o n , a st h et e c h n o l o g y d e v e l o p i n g ，f r e q u e n c yo fs i g n a lb e c o m i n gm o r ea n dm o r eh i g h , a st h e n y q u i s t s h a n n o ns a m p l i n gt h e o r e mw i l lr e s u l tm a s sd a t a ，s u b s t a n t i a l l y i n c r e a s et h es t o r a g ea n dt r a n s m i s s i o nc o s t s r e c e n t l yd o n o h oa n dc a n d 6 s h a v ep r o p o s e dan e w t h e o r yc a l l e dc o m p r e s s e ds e n s i n gw h i c hb ec o n s i d e r e da san e wb r e a k t h r o u g hi nd a t as a m p l i n g t h en e w t h e o r yu s et h ep r i o r o fs p a r s i t y , c a nr e c o n s t r u c ts i g n a lf r o mal i t t l en o n - a d a p t i v el i n e a rp r o j 。 e c t i o n sb ya p p r o p r i a t eo p t i m i z a t i o nm e t h o d c o m p r e s s e ds e n s i n gh a s t h r e em a i ne l e m e n t s ：s p a r s i t yr e p r e s e n t a t i o n , m e a s u r e m e n ta n d r e c o n s t r u c t i o n a tp r e s e n tt h es t u d yo fcsi ss t i l li nt h ef i r s ts t a g e ，m o s to f t h et h e o r e t i c a lr e s e a r c ha r ea b o u tm e a s u r e m e n tm a t r i xa n dr e c o n s t r u c t a l g o r i t h m i nt h i sp a p e r , w ep r o p o s e dan e w s e n s i n gm a t r i xb a s e do nt h ea d j a c - e n c ym a t r i xo fb i p a r t i t eg r a p h a st h en e ws e n s i n gm a t r i xi sv e r ys p a r s e ， w eu s es p a r s m a t r i x m u l t i p l i c a t i o nf o rt h ep r o j e c t i o no p e r a t i o ni n e n c o d i n ga n dd e c o d i n ga l g o r i t h m , w h i c hg r e a t l yr e d u c et h ec o m p u t et i m e ， w h i c hd o w nt o0 f n ) f r o m0 ( n l o g n ) w es h o wt h a t ，t h i sn e ws e n s i n g m a t r i c e sn o to n l yr e d u c e de n c o d i n ga n dd e c o d i n gt i m eb u ta l s og e tm o r e i r a c c u r a c yr e c o n s t r u c t i o nr e s u l t s k e yw o r d s ：c s ；s i g n a lr e c o n s t r u c t i o n ；b i p a r t i t eg r a p h ；a d j a c e n c y m a t r i x ；s t o m p ；i m a g er e c o n s t r u c t i o n 目录 中文摘要i 英文摘要i 第l 章绪论1 1 1 研究背景和意义1 1 2 研究现状2 1 3 压缩传感的应用5 1 4 本文主要工作与结构安排8 第2 章压缩传感基本原理1 1 2 1 压缩传感基本理论框架1 1 2 2 信号的稀疏表示或可压缩性1 2 2 3 量测采样1 6 2 3 1 约束等矩阵性( 砒p ) 1 6 2 3 2 观测矩阵1 8 2 4 本章小结21 第3 章信号重构2 3 3 1 信号重构概述2 3 3 2 贪婪算法2 6 3 3 最小化l l 范数算法3 0 3 3 1g p s r 算法3l v 3 3 2 加权最小化l l 范数算法( w l t ) 3 3 3 3 3l 1 l s 算法3 4 3 3 4i s d 算法3 4 3 4 最小全变分法3 5 基于二分图邻接矩阵的压缩传感图像重构 1 1 研究背景和意义 第1 章绪论 传统的数据获取与处理一般要经过采样，量化，编码，压缩， 存储，解压缩，处理等几个过程，如图1 1 1 如示。半个多世纪来信 号采样一直遵循着尼奎斯特香农采样定理，该定理指出为了准确重构 信号，采样频率不得低于模拟信号最高频的2 倍。近年来随着科技的 进步，信号频率向着更高频的迈进，需要处理的带宽也越来越大，按 照尼奎斯特香农采样定理采得的数据成倍增长，带来海量采样结果， 给数据传输与存储带来了巨大挑战。在实际应用中，为了节省存储空 间，对采集的原始数据进行压缩，例如在声音、图像等方面取得成功 应用的j p e g 2 0 0 0 与m p e g 等压缩算法，压缩后的数据远远小于采样 数据，而且并不影响听觉或视觉效果。这种可压缩现象引起了人们的 思考：既然采集的大部分数据都要“丢”掉，而且并不影响我们的处 理结果，那么为什么我们要花大价钱去采集这么多并不需要的数据呢， 可以不可以直接采集那些在压缩保留下来的、对我们有用的数据呢? 2 0 0 4 年美国斯坦福大学的d o n o h o 教授正式撰文对该问题做出了 回答【l 】，他在前人研究的基础上从信号分解与逼近理论提出了压缩传 感( c o m p r e s s e ds e n s i n g ) 的概念。压缩传感理论指出：可稀疏表示的 高维信号能够通过随机量测矩阵非自适应地投影到到低维空间( 相对 于前面的高维) ，并证明利用信号的稀疏性( 或可压缩性) 这一先验条 硕士学位论文 件，通过l o 最优化模型以很高的概率重建原始信号。压缩传感理论 将信号采样与压缩同时完成，信号能否恢复取决于原始信号能否稀疏 表示，而与信号带宽无关。这一理论打破了传统尼奎斯特香农采样定 理的瓶颈，具有巨大的研究价值和广泛的应用前景，该理论一经提出 引起了全世界各国学者的高度关注，掀了起信号处理领域的又一研究 热潮。 基于二分图邻接矩阵的压缩传感图像重构 共努力下压缩理论框架正式建立，压缩压缩的研究从此拉开了序幕。这 一打破传统尼奎斯特香农采样定理的新方法，一经提出就引起了全世 界各地学者的高度关注，信息处理、图像视频处理、医学成像、雷达 成像、无线通信、模式识别等各研究领域的学者纷纷加入到压缩传感 的研究大潮中。2 0 0 7 年，被美国科技评论评为年度十大科技进展。在 美国、法国、以色列、英国、德国等许多国家的知名大学( 例如斯坦 福大学，莱斯大学，杜克大学，希伯来大学，爱丁堡大学，慕尼黑工 业大学) 专门成立了压缩传感研究小组。在最初的压缩传感理论基础 上又发展出了分布式压缩传感，变形压缩传感，频谱压缩传感，贝叶 斯压缩传感，l b i t 压缩传感等分支理论【l 】o 虽然才短短的几年，压缩 传感研究尚处初始阶段，但已表现出非常强大的生命力，掀起了世界 各地对这一新领域的研究热潮。 压缩传感主要包括信号的稀疏表示，随机投影与信号重构等几大 主要内容。经过几年的深入研究，取得了一些成果【4 1 ，主要的奠基性 工作有，t a o 、c a n d e s 、d o n h o 等人给出了传感矩阵必须满足的充分条 件，即r i p 原则；传感矩阵行数m 与信号稀疏度k 之间的关系必须 满足m k l o g ( n ) 等等，为压缩传感打好良好的研究基础。目前压缩 传感理论方面的研究主要集中在随机投影使用的观测矩阵与信号重构 的恢复算法上，研究者们希望能找出更好的量测矩阵与恢复算法，使 得采样的数据量更小，计算复杂度更低，恢复效果更好，将其推广到 更多的实际应用中去。硬件方面，莱斯大学的b a r a n i u k 等人基于压缩 传感基本原理提出了一种新的压缩图像照相机框架，并制造出了单像 硕士学位论文 数数码相机它使用一个数字微镜来执行图像随机投影，它的特点在于 使用一个单独的探测器来获取采样数少图像像素的图像，因为只有一 个单独的光探测器，所以它能够适应各种波长的图像，这是当前的c c d 和c m o s 不可能实现的阳1 。随后，其他科研单位也相继有硬件方面的消 息报道，如麻省理工学院的llw a l d 教授等研制出的m r ir f 脉冲设 备n ，麻省理工学院wtf r e e m a n 教授等研制的编码孔径相机，伊 利诺伊州立大学0m il e n k o v i c 等人研制的d n a 微阵列传感器n 幻等等。 随着压缩传感研究热潮的掀起，在国外学者大量研究的基础上， 近年来国内许多学者也纷纷进入这一研究领域，在理论方面与应用方 面均有文献报道。例如上海大学的傅迎华基于量测矩阵的研究，通过 近似q r 分解改变量测矩阵的奇异值，提高算法的重构效率。安徽 大学的方红、章权后等人将亚高斯随机投影引入压缩传感，并给出了 两种新类型的压缩僵硬测量矩阵，提高了重建速度，并得到较好的恢 复效果。四川大学的肖龙帅、黄华等人将压缩传感引入到方位估计 中，在不考虑噪声理想情况下，不仅可以准确的恢复出原始信源的方 位，而且精确的得到了各个信源的强度1 5 】。中科院的余慧敏、方广才 将压缩传感理论应用到控地雷达三维成像中，该方法比较比传统后向 投影算法所需数据量小，且成像效果更好【1 6 】。燕山大学的练秋生等提 出了一种基于两步迭代收缩法和复数小波的压缩传感图像重构方法， 得到较好的图像视觉较好【1 7 1 。 基于二分图邻接矩阵的压缩传感图像重构 1 3 压缩传感的应用 压缩传感理论打破了传统的数据采集方式，是信号采样理论的重 大变革带来了新的数据获取方法。具有广泛的应用前景，包括压缩成 像，生物传感，信号编码，错误校正等 ( 1 ) 压缩成像运用压缩传感原理，r i c e 大学成功研制了“单像 素( s i n g l e p i x e l ) 数码相机【1 8 】。该相机包含一个数字微镜装置( d m d ) ， 二个镜头( 1 e n ) ，一个光敏( p h o t o n ) 探测器和一个模数转换器( a d ) 。首 先通过光路系统将成像目标投影到d m d 上，其反射光由透镜聚焦到 单个光敏探测器上，光敏探测器两端的电压值即为一个测量值y ，将 此投影操作重复m 次，得到测量向量y ，然后使用具有重构能力的数 字信号处理器恢复原始图像。数字微镜装置由数字电压信号控制镜片 的机械运动来实现对入射光线的调整，相当于观测矩阵。该相机只使 用一个光敏探测器，这正是“单像素 的由来。单像素照相机的优点 在于它不受带宽限制，可以处理更宽的频谱。 n 硕士学位论文 图1 - 3 1 s i n g l e p i x e lc a m e r a 原理图 图1 - 3 2 s i n g l e p i x e lc a m e r a 实物图 ( 2 ) 医学成像医学上常用的磁共振成像( m r i ) ，通过将人体置于 特殊的磁场中，对氢原子核释放的能量进行记录，最后合成图像。由 于测量次数必须很多，整个过程对患者来说太过漫长。压缩传感技术 可以显著减少测量次数，加快成像( 甚至有可能做到实时成像，也就 是核磁共振的视频而非静态图像) 。此外我们还可以以测量次数换图像 质量，用与原来一样的测量次数可以得到好得多的图像分辨率。目前 已有许多算法专门针对m r i 进行处n t l 9 】【2 0 】。 ( 3 ) 雷达成像传统的雷达系统非常复杂，造价昂贵，且成像分辨 率低，效果较差。b h a t t a c h a r y a 等将压缩传感理论引入到合成孔径雷 达成像系统中，解决了海量数据采集和存储的问题，大大降低了卫星 图像处理的计算代价。设计重点从传统的造价昂贵的接收端硬件转移 到快速高效的信号恢复算法，简化了雷达成像系统【2 1 】【2 2 1 。 ( 4 ) 误差校正压缩传感理论中关于稀疏性、随机性和凸优化的 结论可以应用到设计快速误差校正编码中，这种编码方式在实时传输 基于二分图邻接矩阵的压缩传感图像重构 过程中不受误差的影响。误差校正是编码理论中的一个经典问题，当 信号从信道的一端传送到另一端的时候，通常被干扰，造成误差。设 计一种可以校正误差的编解算法是非常必要的。在实际应用中，误差 往往比较小，因此使用稀疏重构方法可以从受损的编码中重构出原始 信号。h a u p t 等通过实验表明如果图像是高度可压缩的或者s n r 充分 大，即使测量过程存在噪声，压缩传感方法仍可以准确重构图像伫3 1 。 w a k i n 等研究了基于压缩传感理论的视频序列表示和编码方法口4 】； s t a n k o v i c 以及m a r c i a 分别发展了视频压缩采样和压缩视频编码孔径 重建问题【2 5 1 1 2 6 1 ；c e v h e r 等利用源图像与背景差图像更加稀疏的性质， 进行背景抽取，可直接对图像中的关注目标成像2 7 1 。 ( 5 ) 生物传感传统d n a 芯片能平行测量多个有机体，但能识别 的有机体总类却非常少，大量测量值对识别没有用，却消耗了大量的资 源。s h e i k h 等人将压缩传感理论引入该领域，并结合群组检测原理 设计出了压缩传感d n a 芯片，该芯片中的每个探测点都能识别一组 目标，从而明显减少了所需探测点数量。基于生物体基因序列稀疏特 性，s h e i k h 等人证明可以通过置信传播的方法实现压缩传感d n a 芯片 中的信号重构【2 8 】【2 9 1 。 ( 6 ) 模拟信息转换对于高带宽的信号，例如雷达信号和无线通 信涉及的射频信号，为了能重构原始信号，根据香农采样定理，采样频 率必须大于信号最高频率的二倍，所采用的模数转换器必须要有很强 的处理能力，这对硬件是一个极大的挑战。由于传感器及转换硬件性 能的限制，能采集的信号的带宽远远低于实际信号的带宽，获得的数 7 硕士学位论文 据信息不完整，存在着较大的误差。压缩传感随机采样，不受信号带 宽限制，可以很好的解决高带宽信号采集问题。k r i o l o s 等基于压缩传 感理论设计了一种新的模拟信息转换器，首先获得原始信号的线性测 量，再利用后端d s p 重构原始信号【3 0 】。l a s k a 等进一步发展了基于随 机采样系统的模拟信息转换器，并给出了随机抽样系统的两种实现模 型【3 1 1 。 压缩传感是一个理论框架，具有严谨的数据基础，可以应用到多 个领域。由于压缩传感的研究只有短短的几年时间，处在初级阶级， 许多应用还停留在理论阶段，更多的应用还需要进一步的探索、完善。 除了上述几种应用之外，压缩传感在信号检测和分类，数据通信，地 震数据分析，无线传感器网络等众多领域的应用已有学者在研究。了 解更多应用方面的消息，可以参考莱斯大学压缩传感资源主页【1 】。 1 4 本文主要工作与结构安排 本文对压缩传感理论框架进行了详细介绍，探讨了压缩传感的应 用前景。并基于观测矩阵的研究，提出一种新的观测矩阵构造算法。 压缩传感在编码过程中存在着大量观测矩阵与一维信号之间的高维投 影计算，目前常用的随机观测矩阵都是稠密矩阵，从而使得编解码过 程运算量大、重构时间长，降低了压缩传感的性能。本文将二分图理 论引入压缩传感，根据其邻接矩阵的特点提出了一种新的非常稀疏的 观测矩阵构造算法，并用m a t l a b 平台做了仿真实验，取得了较好的效 果。 对信号稀疏表示和量测采样做了具体阐述，介绍了观测 矩阵所需的基本性质和目前常用的观测矩阵。 第3 章：信号重构。介绍了信号重构的基本原理，并对常用的重 构算法做了具体介绍。 第4 章：基于二分图邻接矩阵的压缩传感观测矩阵。基于二分图 原理，提出了种非常稀疏的观测矩阵构造算法了，证明 了其满足所需的基本特性，对进行了仿真实验。 第5 章：压缩传感技术应用探讨。根据压缩传感的特点并结果目 前的应用发情况，探讨了压缩传感技术的应用前景。 在文章的最后总结了课题的整体工作，提出了本文工作的不足 之处并对下一步研究工作提出了设想。 硕士学位论文 基于二分图邻接矩阵的压缩传感图像重构 第2 章压缩传感基本原理 2 1 压缩传感基本理论框架 压缩传感( c o m p r e s s i v es e n s i n g 或c o m p r e s s e ds e n s i n g ) 又称压缩抽 样( c o m p r e s s i v es a m p l i n g ) 它的基本思想是将信号采样与压缩同时完 成，采样只与信号能否稀疏表示相关而与信号带宽无关。 设x 是一长度为n 的稀疏信号，稀疏度为k ( k n ) 即x 中只 有k 个系数为非零值，给定随机测量矩阵中r m n ( m n ) 。则压 缩采样可表示为： y = o x( 2 1 1 ) 其中y er m 。 芗= ，z | - 黼宜 目 目 图2 - 1 - 1 传统采样过程( 左图) 与压缩传感采样过程( 右图) 对比【3 3 1 图2 1 1 为传统采样过程与压缩传感采样过程的对比，右图中压 缩传感采样后的结果明显少于采样前的信号，这表明了压缩传感在采 样的同时压缩了信号这一基本思想。方程( 2 1 1 ) 可以看作是原信号x 在下的线性投影。很显然，由于y 的维数远远低于x 的维数，根据线 性代数基础知识可知这是一个欠定方程，因此该方程有无穷多个解， 即信号稀疏表示，量测采样，信号重构。信号的稀疏表示是压缩传感 的前提条件，这是保证压缩采样的信号能恢复的基础。量测采样或投 影，是压缩传感的编码过程，量测矩阵的选择决定了编解码的计算复 杂速和最后恢复效果。信号重构即解码的过程，对压缩采样的结果进 行恢复，得到采样前的原始信号。本章将对信号稀疏表示和量测采样 进行介绍，信号重构在下章讨论。 2 2 信号的稀疏表示或可压缩性 稀疏信号是指“长度为n 的信号x 中有且仅有k ( k ，x 与厂是n x l 的列向量，、王，是n x n 的矩阵。 如果x 中仅有k ( k ，n ) 个非零系数，则称x 为信号厂的自由度为k 的稀疏表示，甲为的稀疏基。信号在稀疏基上仅有k 个非零系数属 于严格稀疏情况，多数情况下信号无法满足严格稀疏的要求，只是逼 近的认为是稀疏的，将这种信号称为是可压缩的( c o m p r e s s i b l e ) 3 2 1 ，即将 x 按幅值降序排列时，系数呈指数衰减： lx 门s i 。1 h f = 卜一。， ( 2 2 2 2 ) 式中f 表示排序后的系数编号。 由于这些系数呈指数形式快递衰减，厂可由前k 个系数很好的近似表 示。溉x 表示x 排序后的前k 个系数，则用瓢近似表示的误差为： 吒p 鸭曾卜硎p = 卜垓忆 ( 2 2 3 ) 其中表示向的p 范数，即： j 1 i x h p - - ( z l x ，l p ) po p 二。为正交向量或者紧支撑的，则信号x 可 表示为： x = 口，y ，或者矩阵形式x = y a ( 2 2 6 ) 式中y = 他l ，”y ) 表示基矩阵，q 孓五w 净x 。则前k 个最大系数 的最佳逼近可表示为： k x = q y ，= 蚵a = ( q ，0 2 ，a 3 ， 晖爹，尼口n ( 2 2 7 ) 其中逼近误差为： c r y ( x ) = i i x 一；1 1 po p ( 2 2 8 ) 图2 2 1 给了原始图像与前k 个系数逼近图像的对比效果图，图( a ) 为 原始图像，图( b ) 为对其使用哈尔小波进行二层变换的系数( 顺序已打 乱) ，从图( b ) 中可以看出，大部分系数接近o ，说明该图像是“可压缩 的”，图( c ) 为使用前2 5 个最大小波系数逼近的效果图( 其它系数设 为o ) ，虽然少了7 5 的系数，但从图像上根本看不出什么差异。 该误差值随便着k 的增加呈指数递减，当k 等到n 时，误差为o 。 基于二分图邻接矩阵的压缩传感图像重构 2 1 5 1 o 5 o 加5 - 1 w a v e l e l x10 4 c o e f f i c i e n t s l ml 土腿“ f f 1 1 1叩耵 r 一一r l q2 48 81 0 xl o s 图2 - 2 1 原始图像与前2 5 个系数的逼近图像对比【3 4 】 信号在某一变换域具有可稀疏表示的特性在许多方面得到成功 应用，例如j p e gj p e 9 2 0 0 0 1 3 引。这些应用的工作模式大概是这样的： 首先获取信号x 的全部n 个采样，然后计算信号在某一变换基下的系数， 再找出用个近似逼近原信号的前k 个最大系数及他们的位置，进行编 码，而剩下的n k 个系数丢掉。这是我们常用的处理方法，但是它存 在着二个严重的问题：首先，我们需要对信号全部采样，虽然我们最 后只用到了k 个系数，可能k 的比例还非常小，这造成了采样浪费； 另一方面，要对整个采信信号做基变换，虽然大部分系数都丢掉了， 这里造成了计算浪费。正是在这种背景下，d o n o h o 提出了“我们能不 能只采样在压缩后保留下面的那些采样”，压缩传感从此诞生。 在音频、图像和视频处理中常用的稀疏变换是余弦变换和小波变 换等非冗余的正交变换。例如j p e g 使用的是离散余弦变换, j p e 9 2 0 0 0 使用的离散小波变换。近几年来，研究者们在信号稀疏表示方面又取 得了新的进步，理论指出使用称之为原子库的过完备的冗余函数做为 基函数可以获得更好的稀疏逼近，原子库的选择尽可能好的符合被逼 硕士学位论文 近信号的结果，其构成可以没有任何限制，原子库中的元素被称为原 子。新出现的脊波，曲波，轮郭波等都可以做基函数进行稀疏变换3 4 1 。 虽然能得到更加稀疏的表示，但计算量会比非冗余的正交变换要大得 多。 2 3 量测采样 量测采样是压缩传感的重要内容之中，一般使用观测矩阵与待采 样信号相乘来实现，即y = 出，x 为一n 长的待采样信号，彳是m x n ( m i ti k ，为中由索引 丁所指示的相关列构成的大小为k l 州的子，则称矩阵满足约束等 基于二分图邻接矩阵的压缩传感图像重构 距性。 他们同时还指出，对于一个k 稀疏信号x ( 非零值所在的位置并不 知道) ，从较小量测采样精确恢复出x 的充分条件是矩阵满足3 k 阶 约束等距性，即对于3 k 稀疏信号x 和常数ke ( o ，1 ) ，有 ( 1 - 3 3 七) l l x l l 主- i 丁i 3k 。 从上节的分析可知压缩传感直接作用在稀疏信号上，而非直接稀 疏的自然信号需要通用某种基变换得到稀疏表示后才适用。例如，非 稀疏的自然信号x 在稀疏基甲下的稀疏系统为s 即x ：u s ，则量测矩阵 对信号x 进行量测采样的过程可表示为： y = x = v s ( 2 3 3 ) 即先对信号做稀疏变换，取得稀疏表示后，再对稀疏系统进行量 测采样。b a m n i u k 在论文 3 6 】中指出，在这种情况下( 其实大部分情 况都是这样) 量测矩阵与稀疏基矩阵必须满足不相关性( i n c o h e r e n c e ) ， 即的行向量 谚) 不能由甲的列向量l f ，稀疏表示，反之亦然。这是对非 直接稀疏信号进行量测采的r i p 等价条件。b a r a n i u k 同时指出，可以 将量测矩阵与稀疏基矩阵进行合并直接构造一个量测量矩阵，既满足 r i p 又同时满足不相关性原则，直接对非稀疏信号进行采样。即式 ( 2 3 3 ) 可以描述为： ， y = 甲s = o s ( 2 3 4 ) 其中o ：甲。 硕士学位论文 基于二分图邻接矩阵的压缩传感图像重构 或非相关性，那么哪些矩阵满足这些条件，以及如何准确的构造一个 较好的量测矩阵呢? 虽然对观测矩阵的研究取得了很大进步，但到目 前为止还没有通用的办法可主动构造一个满足r i p 条件的矩阵做为压 缩传感的量测矩阵，我们只能被动地判断某一具体的矩阵是否满足量 测矩阵所需条件然后再决定是否能做为量测矩阵。经过几年的研究， 学者们已经找到许多满足条件的量测矩阵。 常见的能做为压缩传感观测矩阵的有高斯随机矩阵( g a u s s i a n r a n d o m m a t r i x ) 、伯努力矩阵( b e r n o u l l im a t r i x ) 、局部傅利叶矩阵( p a r t i a l f o u r i e rm a t r i x ) 、局部哈达玛矩阵( p a r t i a lh a d a m a r dm a t r i x ) 、一致球矩 阵( u n i f o r ms p h e r i c a lm a t r i x ) 以及托普利兹矩阵( t o e p l i t zm a t r i x ) 等。大 小为n x n ，且每一个元素都满足n ( o ，l n ) 独立正态分布的高斯矩阵， 任意抽取m ( m ，n ) 行形成m x n 的矩阵就可以做为观测矩阵，因为 高斯矩阵几乎与任何稀疏信号都不相关，所以它不仅满足3 k 阶的r i p ， 而且所需要的测量次数最小，但由于矩阵元素所需存储空间大以及非 结构化的本质导致计算复杂。伯努力观测矩阵即矩阵中每个元素都服 从对称的伯努力分布： 1 瓦( k , t ) ：= 赤删尸( = 1 ) = 1 2 ( 2 3 5 ) 式中“彳表示独立同分布。 研究表明当k l o g ( n m ) 时能以较高的概率重构原始信号，并且 速度很快3 8 1 。局部傅利叶观测矩阵是从傅立叶矩阵中随机抽取m 行， 然后再对每列进行单位正则化而得例。因傅立利矩阵可由快速傅利叶 变换计算而得，因此其计算量大大降低，减少了采样系统的复杂性， 硕士学位论文 但因为通常只与时域稀疏信号不相关，其应用范围受到一定的限制。 同上面三种量测矩阵一样，局部哈达玛矩阵是从n 维哈达玛矩阵中随 机抽取m 行而得到。而一致球观测矩阵则是指矩阵的每列在球s 川上 独立同分布且随机一致的，使用该矩阵进行量采样时，当 m o ( k l o g ( n ) ) 时能以较高的概率重构原始信号。t s a i g 在论文中对伯 努力矩阵、局部傅利叶矩阵，局部哈达玛部分以及一致球矩阵进行了 性能比较，实验表明这几天矩阵作为观测矩阵时信号重构的误差都比 较小，并且随着量测数m 的增强进一步缩小m 】。 b a j w a 等人提出了固定形和循环形式的托普利兹矩阵，他们发现 当k , 叠g c g m 3 l n ( n m ) 时，这两种形式的观测矩阵都能以很大的概率 r i p ，并且可以利用快速傅立叶变换得到快速的重构算法，能明显减 少高维投影计算和存储复杂度，对解决高维问题比较有效m 。此外， d o 等还提出了结构化随机矩阵，这类矩阵几乎与所有其他正交矩阵不 相关，可以分解成定点、结构化分块对角矩阵与随机置换向量或伯努 力向量点积的形式，可以看成是随机高斯矩阵、伯努力矩阵以及傅立 叶矩阵的混合模型【4 2 1 。 国内的方红等人将亚高斯随机投影理论引入压缩传感，给了稀疏 投影矩阵和非常稀疏投影矩阵，并利用亚高斯分布尾部的有界证，证 明这两种矩阵满足量测矩阵所需的r i p 条件1 4 】。由于这两种矩阵构成 元素的稀疏性可以简化图像重建过程中的投影计算，从而提高重建速 度。傅迎华基于对重构算法的研究，提出对现有的观测矩阵进行q r 分解，通过改变观量矩阵的奇异值可提高算法的重构效率，提高图像 基于二分图邻接矩阵的压缩传感图像重构 质量1 13 1 。 2 4 本章小结 本章介绍了压缩传感的基本理论框架，并按照压缩传感的处理流 程，对信号稀疏表示和量测采样进了具体介绍。信号可稀疏表示是可 压缩传感的先决条件，虽然自然信号并非直接稀疏，但经常某种基变 换即可稀疏表示，并章在第二节介绍了常见的稀疏变换。观测矩阵对 信号能否重构致关重要，第三节介绍观量矩阵所需具备的r i p 和非相 关性以及满足该条件的常见的观量矩阵，为后面的内容打下基础。 硕士学位论文 基于二分图邻接矩阵的压缩传感图像重构 3 1 信号重构概述 第3 章信号重构 与传统数据采集相比，压缩传感将采样与压缩同时实现，大大简 化了数据采集的过程，减轻了数据传输与存储的负担，但是信号重构 的任务却加重了，再好的采样方法，如果不能重构原始信号，那么得 到的只是一堆垃圾。能否准确重构原始信号决定了整个压缩传感理论 的好坏，信号重构是压缩传感理论的核心部分。 信号重构就是从压缩采样得到的y 值恢复出原始信号z 的过程， 即求解方程( 3 1 ) 。 y = x或y = 帆 ( 3 1 1 ) 由于观测矩阵的行数少于列数( m n ) ，方程个数远少于未知量个 数，从线性代数角度来讲，这是一个欠定问题，无定解。但是我们拥 有原始信号具有稀疏表示这一前提条件，c a n d 色s 等证明在这个前提条 件下，可以通过求解最小l o 范数问题加以解决，如式( 3 1 2 ) 所示， 因为l o 范数最小化可以使得结果尽可能地稀疏，信号越稀疏重构效果 越好。 x = a r gm i n ( 1 x 1 i o ) s f 少= f x 或 x = a r g m i n ( l s 1 l o ) 盯 - - fy s ( 3 1 2 ) 硕士学位论文 但d o n o h o 等指出，求解最小l o 范数是一个n p h a r d 问题，从n 个位 置中确定k 个非零项或k 个最大值项的位置，有种不同的排列结 一 果，计算量非常大且结果不稳定；因此很难直接求解瞄3 1 。同时，他们 指使用l l 范数代替l o 会产生同等的解，因此式( 3 1 2 ) 变为： x = a r gm i n ( 1 x 1 1 1 ) s 矿y = f x 或 s = a r g m i n ( 1 l s | | 1 ) 盯y = f y s ( 3 1 3 ) 该式使得n p h a r d 问题变成了一个凸优化问题上，可以简化为线性规 划问题进行求解。考虑重构误，上述可进一步转化，如式( 3 1 4 ) 如 示，该问题可以利用二阶圆锥规划求解。 x = a r g m i n ( 1 l x t l l l ) 眠t s = min(1lsargm m ( 1 l s t i l l ) s t s= 1 1 1 ) 1 l y fx 1 1 2 口e 或 iy fy s 1 1 2 口p ( 3 1 4 ) 其中e 为设定的可接受最大误差值。 为什么选择1 范数呢? 式( 3 1 2 ) 从方程角度来讲，即是求解 y f x = o 或y f y s = 0 ，由于m n 使得方程无穷个解，从几何意义 上来说y f x = o 或少f y s = 0 是一个超平面，o 一范数是三维坐标轴， 其外侧是六个点( 范数最小值) ，和平面的交点落在坐标轴上，所以它 和直接的交点必然在坐标轴上，即会使得解x 或s 包含更多的0 ，这正 是我们想要的“稀疏 解，所以求最小化l o 范数得到的解是最优的解， 但因其求解是复杂的n p h a r d 问题，不容易得到，只能退而求次。1 范数是一个菱形，六个角都在坐标轴上，所以和平面的交点以很高的 基于二分图邻接矩阵的压缩传感图像重构 概率落在坐标轴上，也会使得解比较，另外，1 范数的求解有许多现 成的算法。2 范数是一个球，球和平面的交点( 即是切点) 落在坐标轴 上的概率非常小，所以解是稀疏的概率很小，这不符合我们的要求。 因此，综合分析比较，选择1 范数代替o 范数恢复原始信号是可行的， 即能得到满意的结果，又能在有限的计算内求出解。事实上，对于p 范数，当o p t ) ，s u p p _ s e t = s u p p _ s e tup o s 4 抽出观测矩阵的p o s 列添加到扩展矩阵中，e x 步e x t t u p o s ； 5 把观测矩阵的第p o s 列清空，p o s = o ； 6 运用最小二乘法求解第t i m e 次估计值，x t i m e = ( e x t t t 木e x t _ t ) 1 木 e x tt 1 却： 一，7 硕士学位论文 7 更新残差：r e s = y e x t _ t 木y ； 8 t i m e = t i m e + 1 ； 9 判断是否满达到最大迭代次数，是则输出x t i m e ，算法结束，否则 第2 步。 m p 算法和o m p 算法是贪婪算法的典型代表，也是最早的贪婪 迭代算法，后来的种种算法都是在些基础上进行改变，有的为了得到 更快的速度，有的为了得到更高的精度。然而，计算速度和恢复精度 往往是相悖的，不可兼得，实际应用中应根据具体需要选择合适的算 法。 3 3 最小化l 1 范数算法 d o n o h o 等指出使用1 一范数代替式( 3 1 2 ) 中的0 一范数，可以解决 n p h a r d 难题，且能得到同等的结果，这一替换使得信号重构问题变 成一个线性规划问题，这种方法也称为基追踪方法( b a s i sp u r s u i t ，b p ) 。 倘若考虑重构误差，该问题还可以利用二阶圆锥规划求解。当信号中 存在噪声时，问题还可进一步转换为求解一个凸优化问题，即： m j i n ( i 陟一x 哐+ zl l x 0 - ) 或m 。i n ( 1 l y 一甲s 哐+ a 怙i i ) ( 3 3 1 ) 其中，为误差与解之间的非平衡因子。 使用l - 范数代替式( 3 1 2 ) 中的o 范数，将问题进行转化，不仅可 以取得同等的效果，更主要的是经过这一转变，可以利用许多现成的 算法进行求解，如内点法、同伦算法、梯度投影法。内点法引进惩罚 基于二分图邻接矩阵的压缩传感图像重构 函数在可行域的边界上设置障碍，求解的失代过程始终在可行域的内 部进行，求解精确度高，但速度较慢。同伦算法是一个全局收敛算法， 搜索范围比较大，因此计算量相当大，只适应于小尺度问题求解。相 比而言，梯度投影法运算速度较快，且有不错的重建效果。此外，为 了减少噪声对重构算法的影响，加快收敛，获得更加稀疏的解，c a n d 色s 等人在最在最小化l l 范数的基础上提出加权最小化l l 范数算法。 3 3 1g p s r 算法 梯度投影法( g p s r ) 是基于l l 范数最小化进行求解的算法，是解 决形如： m n 钿y 一彳x 哐+ fi l x l l 。 ( 3 3 2 ) 的目标优化问题，即式( 3 3 1 ) 类型的问题，将目标解进行拆分，进一 步将其转化为一个边界受约束的二次规划问题( b o u n d c o n s t r a i n e d q u a d r a t i cp r o g r a m , b c q p ) 1 4 9 1 。首先向目标向量x 拆分成正负两部分， 即： x = 铭一u 0 ，v 0 ( 3 3 3 ) 且满足对所有分量i = 1 ，2 1 1 玛为x 中大于0 的分量，k 为x 中小 于0 的分量。由此可由得： i l = 1 ：“+ 1 ：v ( 3 3 4 ) 其中1 。= 【l ，1 ，1 】7 。由此目标问题表达式( 3 3 2 ) 可以转化为： n i n ， i l y - 却一诫+ r ( 卅( 1 ，豇掰o v o ( 3 3 5 ) v 么 、 7 硕士学位论文 式( 3 3 5 ) 还可以改写成更加标准的b c q p 形式： m i nc t z + 去z r b z 兰f ( z ) ，“z 0 ( 3 3 6 ) 热z 料r 刊一阱b _ ( 羔铆 梯度投影法在可行域内迭代搜索最优解，设定一个初始迭代值 z 0 r ，r 为可行域，沿着它的负梯度方向一v f ( z o )