（信号与信息处理专业论文）基于边缘检测的压缩传感重构算法研究.pdf

浙江工业大学硕士学位论文 基于边缘检测的压缩传感重构算法研究 摘要 近年来，以稀疏信号表示和处理为基础发展而来的压缩传感理论受到高度关注和 应用。压缩传感理论充分利用信号的稀疏性或可压缩性，将数据采集与数据的压缩合 二为一，实现了在采样的同时进行压缩的目的。该理论首先采集信号的非自适应线性 投影值来保持信号的原始结构，然后通过求解一个最优化问题从投影值中重构出原始 信号。发展至今，压缩传感理论仍有许多问题值得研究，其中设计高效的信号恢复算法 成为应用压缩传感理论急需解决的关键问题。 本文深入分析了压缩传感的基本理论，围绕压缩传感理论的重构算法展开了研究 和讨论。分析了基于i 、几1 l 2 模型的快速r e c p f 算法，给出了算法描述、收敛条件、性 能分析以及仿真实验结果。立足于r e c p f 算法的模型，将图像边缘信息应运于重构算 法中，采用压缩传感重构算法与边缘检测算法相互利用交替迭代优化的方法，提出边 缘压缩传感算法。基于迭代支撑检测理论，给出了算法的理论证明。同时针对边缘压缩 传感算法二维重构实现过程中的耗时过长问题对其提出改进方案，改进的算法是将原 来固定不变的代价参数值随迭代次数增加而增大，即在进行下一次迭代之前，代价参 数将呈某一固定的倍数而增大。 本文利用m a t l a b 仿真软件进行了大量的仿真实验，以重构相对误差和收敛速度 为性能指标，将提出的算法与已有的快速重构算法进行比较。实验表明在卡兀同的条件 下基于边缘检测的压缩传感算法的主观重构效果要优于现有的同类算法，并且改进的 边缘压缩传感算法不仅提高了重构精度，而且具有更快的收敛速度，同时仿真实验结 果表明，本论文提出的边缘压缩传感算法对观测噪声具有较高的鲁棒性。另一方面，提 出的算法在迭代的过程中也优化了边缘检测算法，因此它已不仅仅是种重构算法， 而是将压缩传感理论运用到图像处理之中，丰富了应用前景。 关键词：压缩传感，加权全变分，边缘检测，迭代支撑检测，重构算法，相对误差 浙江工业大学硕士学位论文 c o m p r e s s e i v es e n s i n g r e c o n s t r u c t i o na l g o r i t h m sb a s e d o ne d g ed e t e c t i o n a b s t r a c t c o m p r e s s i v es e n s i n g ( c s ) h a sb e c o m ean e w l ye m e r g e db r a n c hg e n e r a t e df r o ms p a r s e s i g n a lr e p r e s e n t a t i o na n dp r o c e s s i n g ，a n da t t r a c t sal o to fa t t e n t i o n t h et h e o r yo fc o m p r e s s i v e s e n s i n gc o m b i n e st h es a m p l i n ga n dc o m p r e s s i n go fs i g n a l sw h i c ha r es p a r s eo rc o m p r e s s i b l e t o g e t h e r i tf i r s t l ye m p l o y sn o n a d a p t i v el i n e a rp r o j e c t i o n st h a tn e a r l yp r e s e r v ea l lt h ei n f o r - m a r i o no ft h es i g n a l s ，a n dt h e nr e c o n s t r u c t st h e mb ya l lo p t i m i z a t i o np r o c e s s a tp r e s e n t ，t h e r e a r es t i l lh a v em a n yq u e s t i o n st ob ew o r t hs t u d y i n g ，a n dt h ed e s i g no fe f f i c i e n tr e c o n s t r u c t i o n a l g o r i t h m si sb e c a m eo n eo ft h ek e yi s s u e si nt h ea p p l i c a t i o no fc s t h i st h e s i si n t r o d u c e st h et h e o r e t i c a lf r a m e w o r ko fc o m p r e s s i v es e n s i n g ，a n dm a i n l yc o n - c e n t r a t e so nt h eo p t i m i z a t i o no fr e c o n s t r u c t i o na l g o r i t h m si nc s w eh a v ea n a l y z e dt h er e c p f a l g o r i t h mw h i c hb a s e dt h et v l 1 l 2m o d e la n dg i v e nt h ea l g o r i t h md e s c r i p t i o n c o n v e r g e n c e c o n d i t i o n s ，p e r f o r m a n c ea n a l y s i sa n ds i m u l a t i o nr e s u l t s b a s e do nt h i sa l g o r i t h m ，t h i st h e s i s p r o p o s e dt h ee d g eg u i d e dc o m p r e s s i v es e n s i n gr e c o n s t r u c t i o nt h a tt a k e sf u l l yu s e o ft h ei m a g e e d g ei n f o r m a t i o n i ta l t e r n a t i v e l yp e r f o r m sc sr e c o n s t r u c t i o na n de d g ed e t e c t i o ni naw a y t h a t e a c hb e n e f i t sf r o mt h el a t e s ts o l u t i o no ft h eo t h e r m e a n w h i l e ，w ea l s op r e s e n t e dt h et h e o - r e t i c a lp r o o fo ft h en e wa l g o r i t h mb a s e do nt h ei t e r a t i v es u p p o r td e t e c t i o n t oo v e r c o m et h e p r o b l e mt h a tt h er e c o n s t r u c t i o no fi m a g e si st i m e c o n s u m i n g ，w ep r o p o s e da ni m p r o v e m e n t s c h e m ef o ro u ra l g o r i t h m i nt h ei m p r o v e da l g o r i t h m ，t h eo r i g i n a lf i x e dc o s tp a r a m e t e rv a l u e i n c r e a s e sa st h ei t e r a t i o ne n l a r g e s ，i e i nt h en e x ti t e r a t i o n ，t h ep a r a m e t e rv a l u e sw i l lb es o m e c e r t a i nt i m e sa st h ef o r m e ro n e n u m e r i c a le x p e r i m e n t sh a v e b e e nc a r d e do u to nm a t l a bp l a t - f o r mt oc o m p a r et h ep e r - f o r m a n c eb e t w e e no u ra l g o r i t h ma n ds o m ec u r r e n tf a s tr e c o n s t r u c t i o na l g o r i t h m so nr e l a t i v e e r r o ra n dc o n v e r g e n c er a t e t h es i m u l a t i o nr e s u l t sh a v es h o w nt h a tt h er e c o n s t r u c t i o np e r f o r - m a n c ea t t a i n e db yt h ea l g o r i t h mw h i c hb a s e do ne d g ei n f o r m a t i o nd e t e c t i o ni sm u c hb e t t e r t h a nt h eo t h e r s i np a r t i c u l a r , t h ei m p r o v e de d g eg u i d e dc o m p r e s s i v es e n s i n gr e c o n s t r u c t i o n a l g o r i t h ma c h i e v e sm u c hh i g h e rp e r f o r m a n c ei nt e r m so fb o t hc o n v e r g e n c es p e e da n dq u a l i t y t h a nt h eu n i m p r o v e d i ti sa l s os h o w nt h a to u ra l g o r i t h mh a sb e t t e rr o b u s t n e s so ft h em e a s u r e - m e n tn o i s e o nt h eo t h e ra s p e c t ，o u ra l g o r i t h mh a so p t i m i z e dt h ee d g ed e t e c t i o na l g o r i t h m i i i 浙江工业大学硕士学位论文 d u n n gi t e r a t i o n t h u si ti sn o to n l yan e wr e c o n s t r u c t i o na l g o r i t h m ，b u ta l s ot a k i n gu s eo f c o m p r e s s i v es e n s i n gi n t oi m a g ep r o c e s s i n g ，a n dt h e ne n l a r g et h ef u t u r ea p p l i c a t i o np r o s p e c t k e yw o r d s ：c o m p r e s s i v es e n s i n g ，w e i g h t e dt o t a lv a r i a t i o n ，e d g ed e t e c t i o n ，i t e r a t i v es u p - p o r td e t e c f i o n ，r e c o n s t r u c t i o na l g o r i t h m ，r e l a t i v ee r r o r i v 浙江工业大学硕士学位论文 m p o m p i h i i s t t v r e c p f w t v n s p t n s p m r e r r 符号说明 s a m p l i n gf r e q u e n c y p 。n o r m c o m p r e s s i v es e n s i n g r e s t r i c t e di s o m e t r yp r o p e r t y 腑e l e t 砌n s f o r m d i s c r e t ef o u r i e rt h n s f o r m d i s c r e t ec o s i n et r a n s f o r m b a s i sp u r s u i t l e a s ta b s o l u t es h r i n k a g ea n d s e l e c t i o no p e r a t o r m a t c h i n g p u r s u i t o r t h o g o n a lm a t c h i n gp u r s u i t i t e r a t i v eh a r dt h r e s h o l d i n g i t e r a t i v es o f tt h r e s h o l d i n g t o t a lv 撕a t i o n f a s tt v l1 l 2m i n i m i z a t i o n a l g o r i t h mf o rs i g n a lr e c o n - s t r u c t i o nf r o mp a r t i a lf o u r i e r d a t a w e i g h t e dt o t a lv a r i a t i o n n u l ls p a c ep r o p e r t y t r u n c a t e dn u l ls p a c ep r o p e r t y m a g n e t i cr e s o n a n c ei m a g i n g r e l a t i v ee r r o r 采样频率 p 范数 压缩传感 约束等距性 小波变换 离散傅立叶变换 离散余弦变换 基追踪 最少绝对缩减和变量选择 算子 匹配追踪 正交匹配追踪 迭代硬阈值算法 迭代软阈值算法 全变分 局部傅立叶数据的一种快 速最d x t v l l l 2 重构算法 加权全变分 零空间性 截断零空间性 核磁共振成像 相对误差 s 口 门 鏖： 岍 p 獬五3肿嘲叱即k 浙江工业大学硕士学位论文 插图 2 1 传统压缩变换编码过程 9 2 2 压缩传感理论框架 1 0 3 1 r e c p f 算法框图 2 5 3 2l e n a 的r e c p f 算法重构图：第一排左边是原始图像，右边是k = o 1 3 7 的重构图 像；第二排左边是k = o 1 6 6 、右边是k = 0 2 2 的重构图像 2 7 3 3m r i 图的r e c p f 算法重构图：第一排左边是原始图像，右边是k = 0 1 3 7 的重构图 像；第二排左边是k = 0 1 6 6 、右边是k = 0 2 2 的重构图像 2 8 4 1 边缘的分类 4 2 边缘检测算法的基本步骤 4 3 一维边缘压缩传感算法框架 4 4 实线、破折线和虚线分别表示像素的4 连通、8 连通、1 6 连通各向异性全变分 4 5 e d g e - c s r e c 算法框架 5 1原始信号“和跳跃点位置 5 21 次迭代加权全变分重构 5 32 次迭代重构图 5 4 上排的迭代次数依次为3 、4 ，下排的迭代次数依次为5 、6 5 5 b p 算法重构图 5 6 迭代值为4 ，参数卢分别为3 、5 重构图 5 7 左边为r e c p f 算法重构图、右边为e d g e c s r e c 算法重构图 5 8 上排为e d g e c s r e c 算法重构图、下排为r e c p f 算法重构图 5 9 左边为改进的r e c p f 算法重构图、右边为改进的e d g e c s r e c 算法重构图 5 1 0 上排为改进的e d g e - c s r e c 算法重构图、下排为改进的r e c p f 算法重构图 1 4 6 7 8 2 3 4 4 5 6 8 8 0 1 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 浙江工业大学硕士学位论文 表格 4 1 边缘点的分类3 2 5 1 一维边缘压缩传感算法实验数据4 5 5 - 2 r e c p f 算法与e d g e c s r e c 算法重构数据 4 9 5 3 改进的r e c p f 算法与改进的e d g e c s r e c 算法重构数据 5 1 浙江工业大学硕士学位论文 1 1 选题背景和意义 第1 章绪论 信息数字化是我们当今社会的重要标志，它得益于数字技术，特别是数字信号处 理理论和技术的飞速发展，但与此同时也给信号处理的能力提出了更高的要求和挑战。 众所周知，在传统采样过程中，要使采样过程完整地保留信号的重要信息，采样频率必 须大于信号最高频率的2 倍。将这一最低采样频率定义为奈奎斯特采样率。传统的信号 采集、编解码过程正是依照奈奎斯特采样定理进行的。该过程首先对信号进行奈奎斯 特高速采样，再对采样值进行某种变换，变换稀疏化后对重要系数的幅度值和位置进 行编码，舍弃小系数点到达压缩的目的。解码端，对接收的信号经过简单的解压缩、反 变换之后得到恢复信号。 传统的编解码方法明显存在两个缺陷【1 】：一是在数据获取和处理时，由于信号的 采样速率不得低于信号带宽的2 倍，导致采样数据量太大，所以在许多实际应用中，例 如超宽带通信和信号处理、核磁共振、空间探测等等，高速率采样将成为硬件系统发展 的瓶颈，这不仅导致硬件成系统的成本昂贵、获取效率低下，在某些实际应用场合甚至 无法实现；另外，也会影响数据存储和传输能力，通常数据获取模式是先进行奈奎斯特 采样，然后对获得的采样数据进行变换压缩后存储或传输。显而易见，这样的处理方式 造成很大程度的资源浪费，同时又浪费时间和存储空间。 而且，我们都知道奈奎斯特采样率是信号精确复原的充分条件，但绝不是必要条 件。因此，奈奎斯特采样理论其实并不是唯一的、最优的采样理论，如何突破以奈奎斯 特采样理论为基础的信号处理框架的信息获取、处理、融合、存储及传输等的方式是信 号与信息处理中急需解决的问题之一。 近几年来，由d d o n o h o 、e c a n d 芑s 、及华裔科学家t t a o 等人提出了一种新的 信息获取指导理论- 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 e n s i n g ，”压缩传感”) 2 】- 【4 】。 压缩传感理论与传统的采样定理不同，它指出，只要信号是可压缩的或者在某个变换 域是稀疏的，采用一个观测矩阵将高维信号投影到一个低维度空间上，然后对所得投 影值通过求解一个最优化问题就可以以高概率重构出原始信号。在压缩传感理论框架 下，信号的采样速率不再决定于带宽，而是决定于信号中包含的信息的结构和内容。即 将对信号的采样转变成对信息的采样。压缩传感理论的核心思想是将压缩与采样合并 浙江工业大学硕士学位论文 进行，首先采集信号的非自适应线性投影测量值，然后根据相应重构算法由测量值重 构出原始信号。 压缩传感与经典采样理论在三个重要方面有所不同： 1 采样理论通常考虑的是无限长度的连续时间信号。相比之下，压缩传感是一门重 点对有限维向量测量的数学理论。 2 压缩传感系统通常是通过信号与更一般的测量函数两者之间的内积形式获得测量 值，而不是在某些特殊的时间点，直接对信号进行采样所得到的。这实际上也是 现代采样方法的本质，只是后者的测量信号是通过更一般的线性测量而得到的。 在压缩传感中，随机性通常对测量函数的设计起着至关重要的作用。 3 这两个框架对于它们处理信号的恢复方式也不同。例如，对于从压缩的测量值中 恢复出原始信号这一问题，在奈奎斯特一香农框架中，信号的恢复是通过正弦插值 方法得到的，正弦插值是一个简单的线性过程，需要少量的计算量。然而，在压缩 传感框架中，信号的恢复通常是通过高度非线性方法得到的。 因为压缩传感将传统的数据采集与数据压缩合二为一，极大的降低了信号的采样 频率及数据存储和传输的代价，显著降低了信号处理所需时间且又无需复杂的数据编 码算法，因此，压缩传感理论被称为继小波变换理论之后信息处理界最重大的突破，具 有非常广阔的应用前景。 1 2 国内外的研究现状及趋势 以稀疏信号处理和表示为基础发展而来的压缩传感理论，打破了传统采样定 理的瓶颈，实现了低采样数率，将信号处理带入了一个新的革命时代。自2 0 0 6 年， c a n d 色s 、t a o 、d o n o h o 有正式论文发表之后，迅速成为众多领域的一大研究热点，引起 国内外众多科研机构从多种角度展开深入研究。对于压缩传感理论的研究基本上都是 以信号的稀疏表示、观测矩阵的设计以及信号重构算法这三要素展开的。 目前，压缩传感理论的研究工作主要是对理论层面展开研究，主要集中在构建 观测矩阵与设计稀疏信号重构算法两大具体方面。对于观测矩阵这一问题，t a o 、 c a n d 乏s 、d o n o h o 等人给出压缩传感的理论模型的同时证明了传感矩阵须满足约束等距 性( 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 ) 【4 】这一充分条件，随后r b a r a n i u k 在文献 1 1 证 明了如果保证观测矩阵和稀疏基不相干则很大程度上满足r i p 性质。对稀疏信号重建 2 浙江工业大学硕士学位论文 问题，在压缩传感诞生之前已经有基追踪( b a s i sp u r s u i t ，b p ) 等求解欠定线性方程的 方法。随着压缩传感理论的不断推进，又涌现出多种新的重构算法。目前主要有基于迭 代逼近的贪婪追踪算法、将非凸问题转化为凸优化算法以及组合算法等算法。近几年 来，基于自然图像的离散梯度的稀疏性提出的最小全变分法使其有效地解决了图像压 缩重构问题。最小权变分法是由c a n d 乏s 等人提出的【1 3 】，随后d i a s 等人对其改进，提 出了两步收缩迭代算法( t w o s t e pi t e r a t i v et h r e s h o l d i n ga l g o r i t h m ，t w i s t ) 4 0 ，在这个 算法中，采用二维收缩阈值函数对其迭代求最优解；另外，y a n g 等人在文献 3 3 1 中基于 t v l l 一l 2 模型提出了r e c p f 算法，该算法将其优化函数的各自变量分离为独立的变量， 变量之间采用交替迭代优化方法，算法具有较高恢复精度和收敛速度。信号重构算法 研究的主要目的就是提高恢复精度和速度，是压缩传感理论能够得到更广泛应用的关 键之处。因此，重构算法的研究一直是压缩传感领域的热点之一。 压缩传感领域的先驱者代表有加州大学洛杉矶分校的t e r e n c et a o 、加州理工 大学的e m m a n u e lc a n d 乏s 、斯坦福大学的d a f i dd o n o h o 、以及莱斯大学的r i c h a r d b a r a n i u k 等。该理论公开发表后，诸如美国、英国、德国、法国等许多国家的知名大学 成立专门课题组对压缩传感理论进行研究，如麻省理工学院、赖斯大学、普林斯顿大 学、爱丁堡大学等等。逐渐成熟的压缩传感理论同样引起了商业界的广泛关注，西雅 图i n t e l 、g o o g l e 、贝尔实验室等知名公司也开始组织研究压缩传感理论；莱斯大学建立 了专门的压缩传感网站。我国科学工作者关于压缩传感理论的研究才则刚刚起步，发 表论文甚少，但自2 0 0 9 年以来，在许多高校迅速展开了研究，其中以西安电子科技大 学、西安交通大学、中科院等单位为代表的一些研究组已经取得了不少可喜的成绩。 目前压缩传感理论己发展成由b a r o n 等提出分布式压缩传感理论、b a r a n i u k 等提 出的1 - b i t 压缩传感理论、c a r i n 提出的贝叶斯压缩传感理论、e l a d 提出的无限维压缩 传感理论等等，现已成为数学领域和工程应用领域的一大研究热点。压缩传感理论的 应用研究现己涉及到信息论、信号图像处理、地质勘探、光学雷达成像、医疗成 像、模式识别、生物传感、无线通信等领域。 除此之外，在硬件实现上，r i c e 大学r b a r a i l i u k 教授等成功研制了单像素相机， 不过该硬件成本昂贵，重构算法效率低。随后，麻省理工学院许多科研者在硬件上展开 研究，l w a l d 教授等人成功研制出m r ir f 脉冲设备【5 】、w f m e m a n 教授等人研制了 编码孔径相机【6 】。伊利诺伊州立大学m i l e n k o v i c 等人研制的d n a 微阵列传感器 7 】将 压缩传感理论实现于医疗成像领域。但是由于缺乏有效的压缩传感矩阵判别理论，这 些硬件均缺乏严格的理论分析。 3 浙江工业大学硕士学位论文 1 3 研究目标和内容 1 3 1 研究目标 本论文的研究目标可以总结为以下四点： 1 基于r e c p f 算法提出的加权t v l l 一l 2 模型，结合图像边缘信息，采用压缩传感重 构算法和边缘检测算法相互利用交替迭代优化的方法，提出了一种新的快速高效 重构算法。 2 对提出的边缘压缩传感算法进行算法建模，并基于迭代支撑检测理论给出了边缘 压缩传感算法的理论证明。 3 基于m a t l a b 平台对提出的算法进行仿真实现，给出了边缘压缩传感算法在不 同观测噪声、采样率上的实验结果，并与b p 算法、r e c p f 算法在重构精度、耗时 方面进行性能分析。 4 针对二维重构实现过程中的耗时过长问题对其提出改进方案，改进的算法是将原 来固定不变的代价参数值随迭代次数增加而增大，对改进的算法进行仿真实验， 给出了实验结果及性能分析。 1 3 2 研究内容 根据设定的研究目标，本论文的大体内容可以分为五大部分，具体的研究工作包 括以下几点： 1 通过对压缩传感理论系统的了解，以及查阅大量的文献，学习并介绍信号的稀疏 表示、观测矩阵的设计及其满足的必要条件、稀疏信号重构算法以及压缩传感理 论的应用。 2 分析总结目前己有的各类重构方法，包括基追踪算法、最少的绝对缩减和变量选 择算子、正交匹配追踪算法、迭代阈值算法，分析了它们的算法模型和存在的不 足，并重点研究了基于t v l l l 2 模型的快速r e c p f 算法，给出了算法描述、收敛 条件、性能分析以及仿真实验结果。 3 立足r e c p f 算法，将图像压缩传感重构算法和图像边缘检测相结合，提出了边缘 压缩传感算法。算法在不满足迭代停止条件下，第一步调用改进的r e c p f 算法得 4 浙江工业大学硕士学位论文 到迭代解，第二步对所得的迭代解进行亚像素边缘检测，据此更新加权系数，并 跳转到第一步继续循环直至满足迭代停止条件，算法结束。 4 对提出的边缘压缩传感算法进行算法建模和理论证明，并对该算法在不同采样 率、观测噪声条件下进行m a t l a b 仿真，对收敛速度、重构相对误差进行性能分 析。 5 为了提高e d g e c s r e c 算法二维重构的收敛速度对其提出改进算法，给出了改进 算法在不同参数下的实验结果以及性能分析。 1 3 3 章节安排 文章的具体章节安排如下： 第1 章：绪论。首先介绍了本文的研究背景和意义，压缩传感理论国内外的研究现 状及趋势，最后对本文的研究目标及全文的内容安排进行了说明。 第2 章：压缩传感理论。本章首先介绍了压缩传感理论的几个基本知识概念，并简 单的介绍了压缩感知理论的框架，最后着重从信号稀疏变换、观测矩阵设计这两方面 介绍压缩传感理论的相关知识。 第3 章：压缩传感重构算法。本章介绍了压缩传感理论另一核心研究内容：稀疏 重构算法。首先介绍目前已有的各类重构方法，并对其典型代表性算法作简短的介绍。 重点介绍r e c p f ( af a s t ，r v l l 一l 2m i n i m i z a t i o na l g o r i t h mf o rs i g n a lr e c o n s t r u c t i o nf r o m p a r t i a lf o u r i e rd a t a ) 算法，给出了算法描述、收敛条件、性能分析以及仿真实验结果。 第4 章：基于边缘检测的压缩传感算法。首先从图像边缘的分类、经典边缘检测算 子介绍了边缘检测相关基础知识。基于加权全变分模型，将图像压缩传感重构算法和 图像边缘检测相结合，提出了边缘压缩传感算法。分别就一维信号和二维信号对算法 进行算法建模，基于迭代支撑检测理论给出了边缘压缩传感算法的理论证明。 第5 章：基于m a t l a b 平台，对提出的算法在不同观测噪声、采样率上进行了仿 真实验，并与b p 算法、r e c p f 算法做对比进行性能分析。针对二维重构实现过程中的 耗时过长问题对其提出改进方案，改进的算法是将原来固定不变的代价参数值随迭代 次数增加而增大，对改进的算法进行仿真实验，给出了实验结果及性能分析。 第6 章：总结与展望。对本文的工作进行了总结，并对下一步的研究方向进行了展 望。 5 浙江工业大学硕士学位论文 2 1 基础知识介绍 第2 章压缩传感理论 在进行压缩传感的讨论之前，为讨论方便，先将其中用到的几个基本知识概念在 此进行简单的介绍。 2 1 1 奈奎斯特采样定律 在信号与系统分析中，采样定理是最重要的依据之一，它是构成连续时间信号与 离散时间信号之间关系的基础。如果已知信号s ( f ) 的傅里叶变换s ( 厂) ，其所含最高频 率为w 。如果对i f i w 有s ( f ) - - 0 ，则称信号5 ( f ) 为带限信号。为保证采样之后的数 字信号完整地保留了原始信号中的信息，只要采样频率疋大于信号中最高频率的2 倍就 可以用所取得的样本值来表示原始信号。这一最低采样频率，即疋= 2 w 称为临界频率 或奈奎斯特采样率。 2 1 2 向量易范数的定义 向量范数是用来刻画向量大小的一种度量。为方便起见，以后本论文中所讨论的 向量，一般都是维向量空间默中的向量，且对冀采用标准正交基。向量x 的乙一范 数定义： 恻p = ( 啪坳0 p o o l - l 删。= m a x 。，l x i i ( 2 1 ) l = 对于p 1 ，我们方程( 2 1 ) 定义的范数并不满足三角不等式这一性质，实际上， 0 p 1 的乙范数是一个拟范数。通常，我们用范数来表示信号的长度或者误差的大 小。这里需要特别指出的是，向量x 的l o 范数即是向量中非零元素的个数。 2 1 3 基和框架的定义 在线性代数中，基或基底是其线性组合可以表示在给定向量空间中的所有向量的 集合，并使得这个集合元素不能由其他元素的线性组合表示。换句话说，基是线性无关 6 浙江工业大学硕士学位论文 生成集。数学表示是：若一个集合 以1 丝1 是线性空间冀中的线性无关向量组，且冀中 任一向量石r 都是集合 咖毽1 的唯一确定的线性组合，即： z = s i 沙i i = 1 我们则称 以l 墨1 为空间冀的一个基。 如果我们用nxn 维的矩阵甲= 【沙l ，忆“】表示这个集合，其中列向量1 王，l 是n 1 的向量。设n x1 维的向量s 为s = 【s 1 ，s 2 一s n t ，则我们可以得到上式更简洁的表示： x = 甲s 在维欧式空间中，n 个向量构成的正交向量组称为正交基；由单位向量组成的 正交基称为标准正交基。通常，对一个正交基进行单位化就得到一个标准正交基。具体 表示为，设沙，砂2 c n 是一个标准正交基，由定义有 = 1 江办 l 0 ， f 工 在标准正交基下，向量的坐标系数可以通过内积简单的计算出来，即 或者 s i - - s = t i l t x 对于可能线性相关向量集合，我们引入了框架的概念。框架的定义为：设向量集合 机 丝】，其中帆r d 且d n ，对应的矩阵形式为l 壬，冀d x ，对于所有的向量x 民d ，存在常数0 毫芎 0 0 ，满足： l l x l l ； l l 妒x l l ；芎l l x l l ； ( 2 - 2 ) 我们称向量集合 呶堪】为一个框架。注意，这里要求o s i l l 1 i = q j s ( 2 - 3 ) 百 s i = ( z ，帆) = 甲k ，可见，s 是信号x 的等价表示，只是x 是信号在时域的表示，j 为信 号在甲域的表示。 如果向量s 的0 范数，即向量s 中非零个数为k ，k n 时，我们则称信号x 为稀 疏基甲下的稀疏信号。定义a = 纠n 为稀疏比。稀疏信号的一个重要性质就是它们可 以从相对少量的随机采样中通过有限的计算步骤恢复。这也就是为什么压缩传感理论 的必要条件是信号为可稀疏信号。 文献【2 给出稀疏的数学定义：对于某一正交基、王，信号x 在其上的变换系数向量 s = t t x ，如果对于参数0 的支 撑域 i ：s f 0 ) 的势小于等于k ，即s 冀仅有k 个非零项，那么定义信号x 关于 甲是k 一稀疏的。对于一个信号，非零项的个数反映的是信号中固有的自由度。也就是 说，信号的稀疏度是度量构成信号的系数中非零分量个数的一个尺度。通常，信号表示 的稀疏度用该表示向量的0 范数来量化。 严格意义上的稀疏信号在实际中很少，通常信号中很多位置的值非常小，但并不 完全为零，于是引入可压缩信号( c o m p r e s s i b l es i g n a l ) 的概念。 信号x 在正交基甲下的展开系数，如果展开系数按一定数量级呈现指数衰减，具 有非常少的大系数( k 个) 和许多小系数。当k 远小于时，则表明信号x 是可压缩 的，称为可压缩信号。一般而言，可压缩信号是指可以用k 个大系数很好地逼近的信 号。 通常，我们采用两种方式量化一个信号的可压缩性，一是通过计算逼近此信号时 所带来的误差；二是通过考虑信号系数的衰减速率。对于许多重要类的信号，存在一组 基使得坐标系数服从幂次速度衰减，在这种情况下，该信号就是高度可压缩的。具体表 8 浙江工业大学硕士学位论文 示是，如果工= t s ，我们对系数s 进行排序使得i s l i i s 2 i i s i ，如果存在常数 p ，q 0 使得 i s i i p i 一口 我们称系数s 呈指数衰减。常数g 越大的，则幅度值衰减的速度就越快，信号的可压缩 性就越好。由于系数的幅度衰减得如此之快，因此可压缩信号可以通过k n 个系数 准确表示出来。 2 2 压缩传感理论的基本框架 在介绍压缩传感理论的基本框架之前，我们回顾一下传统的以奈奎斯特采样定理 为准则的信号压缩变换编码，其传统压缩变换过程框架如图2 。1 所示。 第一步第二步第三步 图2 1传统压缩变换编码过程 传统的信号压缩变换编码过程由高速采样、变换、压缩、传输和信号的重构五步骤 完成。首先使用奈奎斯特采样定理对其进行高速采样，再对海量的采样样值进行某种 变换编码，现在一般是离散余弦变换、离散傅立叶变换或小波变换，然后将稀疏化后的 少数幅度绝对值大的系数进行压缩编码，舍弃小的系数，从而达到压缩的目的。我们将 压缩后信号进行传输，节省大量的通信资源，在接收端，接收到压缩信号后对其进行解 压缩、反变换重构出原始信号。显然，此过程浪费了大量的采样资源，同时高速采样率 对采样设备也是高挑战。 近年来提出的压缩传感理论表明，只要信号是可压缩的或者在某个变换域是稀疏 的，采用一个观测矩阵将高维信号投影到一个低维度空间上，然后对所得投影值通过 求解一个最优化问题就可以以高概率重构出原始信号。压缩传感理论中，将数据的采 样与压缩同步进行，无需传统系统中高速采样这一中间步骤。该理论框架过程如图2 2 所示。 首先，对于信号x 冀，若在某个正交基或紧框架甲上是可压缩的，那么就可以 求出变换系数s = 甲t x ，我们称s 是t 的等价或逼近的稀疏表示；其次，设计一个平 稳的、与变换基、王，不相关的mxn 维的观测矩阵，然后用观测矩阵对信号x 直接进 行观测得到观测集合y = o x = o q s ，该过程也可以表示为稀疏信号s 通过矩阵a 进行 9 浙江工业大学硕士学位论文 第一步第二步第三步 、厂j 低速压缩桑样；，= a s 图2 2 压缩传感理论框架 非自适应观测y = a s ，其中定义a 皇甲，a 称为传感矩阵；最后为信号的重构，利用 o 一范数意义下的优化问题求解x 的精确或近似逼近解全： m i ni i 甲t x l i oj ta s = 甲s = y ( 2 5 ) 所得到的向量工a 在甲变换基上的表示是最稀疏的。最后再通过逆变换重构出原始信号 的逼近信号。 根据压缩传感理论框架，压缩传感主要涉及以下几个方面的内容 9 】： ( 1 ) 对于任何信号x r ，虽然理论上一定存在某个基使信号在该基下是稀疏表 示的，但是如何高效的找到该正交基或紧框架l 壬，是压缩传感理论必须解决的问题，即 信号的稀疏表示问题。 ( 2 ) 如何设计一个m n 维的平稳观测矩阵，使其保证稀疏信号x 的重要信息 在从维降维到m 维的过程中不遭破坏，也就是说所得观测值包含了重构算法精确恢 复出原始信号所需的全部信息量，即观测矩阵的设计问题。 ( 3 ) 如何设计出快速精确的重构算法，从线性观测值y = x 中恢复出原始信号， 即信号重构问题。 本章下面的部分将从第一、第二方面介绍压缩传感理论的相关知识。因为本论文 就是围绕信号重构问题进行的研究并且重点是针对图像信号的快速重构算法，所以关 于第三方面我们将作为单独的一章，在第三章进行介绍。 2 2 1 信号的稀疏表示 压缩传感理论的两大核心任务是观测值的获取和信号重构，而压缩传感理论的提 出是基于信号的稀疏性或可压缩性，因此信号稀疏表示是压缩传感理论前提和必备条 件。信号稀疏的研究可以追溯到上世纪六十年代，相续研究出现了离散傅立叶变换、离 散余弦变换，上世纪末出现的小波变换再到近年兴起的多尺度几何分析理论，所有这 些变换的最终目的均是为了在不同的函数空间中如何找到信号最简洁明了的分析方法， 也就是说所有的这些变换都是在发掘信号的特征并稀疏表示它。 】0 浙江工业大学硕士学位论文 对于一个未知信号x ，为了简化我们的表示，将二维的图像或多维数据向量转 化成一维向量。在大多数情况下，少量信号的主要特征信息就可以表示出该信号， 也就是意味着x 在某个合适的变换域下是稀疏的或者可压缩的。设信号x 俄， 、王，= 【缈l ，忱，l 】为默的一个正交基，咖为n 1 的列向量，存在唯一的ser ， 使得x 可以表示为一组标准正交基的线性组合： x = l & 以= 甲s ( 2 - 6 ) 冒 s 产 x ，以) - - v ? x ，可见，s 是信号x 等的价表示。如果向量s 的o 范数，即向量s 中非 零个数为k ( k ) ，则称信号x 为稀疏基甲下的稀疏信号，s 是信号x 的k 稀疏表 示。如果向量s 只有很少的大系数( 幅度值) ，则称信号x 是可压缩的。另外，当正交基 不能稀疏表示信号时，采用冗余字典稀疏表示。 信号的稀疏表示是压缩传感理论应用的基础和前提。选择信号合适的变换基表示 信号，不仅有利于提高采集信号的速度、减少资源，更重要的是将会影响信号的恢复精 度。在研究信号的稀疏表示时，通常是通过变换系数衰减速度来衡量变换基的稀疏表 示能力。c a n d 色s 、t a o 9 】等人通过研究表明，满足具有幂次速度衰减的信号，可以利用 压缩传感理论对其进行恢复，并且重构误差满足： e = 峪一x l l 2 c r ( 别( 1 0 9