基于压缩感知的正交匹配算法图像重建.pdf
《基于压缩感知的正交匹配算法图像重建.pdf》由会员分享,可在线阅读,更多相关《基于压缩感知的正交匹配算法图像重建.pdf(45页珍藏版)》请在咨信网上搜索。
1、 基于压缩感知的正交匹配算法图像重建 摘要:压缩感知理论是由 Donoho 和 Candes 提出的一种充分利用信号稀疏性的全新的信号采样理论。该理论表明,用远低于 Nyquist采样定理要求的频率对信号进行采样也能实现信号的精确重构。该理论突破了传统的以 Nyquist定理为基准的信号处理方法,实现了在获取数据的同时对其进行适当的压缩,克服了采样数据量大,采样时间长及数据存储空间浪费严重的问题,因此进一步降低了信号处理的时间和器件成本。压缩感知理论有三个核心方面:(1)稀疏变换,即对一个非稀疏的信号,找到一个合适的正交基使该信号在它上可以稀疏表示;(2)测量矩阵,与变换基不相干且平稳的矩阵;
2、(3)重构算法,利用数学算法完成对信号的精确重构,该过程可看为求解一个优化问题。本文介绍了主要介绍了压缩感知原理和目前最为成熟的压缩感知重建算法正交匹配追踪算法,通过 MATLAB平台设计实现了基本的正交匹配追踪算法,对一维、二维信号进行了重建仿真。关键词:压缩感知;稀疏变换;正交匹配;图像重建 Based On Compressed Sensing Of Orthogonal Matching Algorithm Image Recovery Abstract:Compressed sensing is a novel sampling theory which is proposed by
3、 Donoho and Cand s.This theory is under the condition that the signal is compressible or sparse.In this case,using far less than the required sampling frequency of the Nyquist theory to sample the signal is able to accurately reconstruct the signal.Compressed theory breaks though the traditional Nyq
4、uist sampling theory,which overcomes a lot of problems such as a great number of sampling data,time wasting,data storage space wasting and so on.As a result,it reduces signal processing cost and device cost.The compressed theory has three key sides:(1)Sparse transformation,for a non-sparse signal,we
5、 need to find a proper orthogonal basis on which the signal has a sparse representation;(2)Observation matrix,it is irrelevant with the orthogonal basis;(3)reconstruction algorithms,using a reconstruction algorithm to ensure the accuracy of the signal reconstruction,the whole process can be consider
6、ed as the solve to a optimization problem.This paper introduces CS and most mature compression perception algorithm at present-Orthogonal matching algorithm.Through the MATLAB design realize basic orthogonal matching algorithms,Through the MATLAB design realize basic orthogonal matching algorithm of
7、 one-dimensional,two-dimensional signal processing simulation.Key words:Compressed sensing;Sparse transform;Orthogonal matching;Image recovery.西安文理学院本科毕业设计(论文)第1页 目 录 第一章 绪论.2 1.1 选题的背景及意义.2 1.2 本课题在国内外的发展现状.2 1.3 本论文的结构安排.3 第二章 压缩感知理论相关知识.4 2.1 压缩感知理论框架.4 2.2 压缩感知的基本理论及核心问题.5 2.2.1 信号的稀疏表示.6 2.2.2
8、信号的观测矩阵.8 2.2.3 信号重构.9 2.3.压缩感知的应用.11 2.4 压缩感知有待研究的几个问题.13 第三章 正交匹配追踪重建算法.16 3.1 最小 L0范数模型.16 3.2 匹配追踪算法.16 3.3 正交匹配追踪算法(OMP).17 3.3.1 OMP 算法原理.17 3.3.2 OMP 算法实现步骤.17 3.3.3 OMP 算法的 Matlab 语言实现.17 第四章 基于 MATLAB 的压缩感知图像重建仿真.20 4.1 不同采样率下的仿真结果.20 4.1.1 一维信号在不同采样率下的 OMP 仿真.20 4.1.2 二维信号在不同采样率下的 OMP 仿真.2
9、2 4.2(OMP)算法与多种压缩感知算法的仿真比较.24 4.3 结论.26 结束语.27 致谢.28 参考文献.29 附录一 源程序清单.30 附录二 英文文献翻译.37 西安文理学院本科毕业设计(论文)第2页 第一章 绪论 1.1 选题的背景及意义 众所周知,传统的信号采样以奈奎斯特(Nyquist)采样定理为基础。为了不丢失信号的信息,精确重构信号,在获取信号时,采样频率要大于信号中最高频率的两倍。但是随着各种信号处理系统获取能力的不断增强,需要后期处理的数据量也快速增加,奈奎斯特定理的局限性给系统的处理能力提出了更高的要求,同时也给相应的硬件设施的设计带来了极大的挑战。如何高效处理这
10、些数据并且最大限度的节省存储空间及传输成本已成为目前信息领域进一步向前发展的主要瓶颈之一。实际上,奈奎斯特采样定理是信号精确重构的充分条件而不是必要条件,奈奎斯特采样定理并不是唯一、最优的采样理论。因此研究如何突破以奈奎斯特采样定理为基础的信息的提取、处理、融合、存储、及传输是推动信息领域发展的关键。在 2004 年 Donoho 等人针对稀疏性信号,提出了压缩感知(Compressive sensing,简称 CS)理论。在随后的几年间该理论迅速发展,为解决上述问题奠定了基础。与传统信号处理方式不同,压缩感知理论以空间变换为基础,随机观测矩阵作为手段,优化求解作为恢复信号的方法。压缩感知理论
11、在获取信号的同时对数据进行适当的压缩,其采样频率低于奈奎斯特采样频率,减少了采样数据,节省了存储空间,同时又包含了足够的信息量,能通过合适的重建算法对特定的图像或者信号进行精确重构。它将传统的数据采集和压缩合二为一,并且不需要复杂的数据编码算法,非常适合于要求采用小型器件的实现场合。信号的稀疏重建与压缩感知理论有重大的实用价值和应用前景,已经成为信号领域中一个新的研究方向1。1.2 本课题在国内外的发展现状 1国外研究状况及发展趋势 目前,CS 理论与应用研究正在如火如荼地进行:在美国、欧洲等许多国家的知名大学如麻省理工学院、莱斯大学、斯坦福大学、杜克大学等都成立了专门课题组对 CS 进行研究
12、;2008 年,贝尔实验室,Intel,Google等知名公司也开始组织研究CS;2009 年,美国空军实验室和杜克大学联合召开了 CS 研讨会,美国国防先期研究计划署(DARPA)和国家地理空间情报局(NGA)等政府部门成员与数学、信号处理、微波遥西安文理学院本科毕业设计(论文)第3页 感等领域的专家共同探讨了 CS 应用中的关键问题;第二次以压缩感知和高维数据分析为主题的研讨会也将在 2011 年的 7 月 26 至 28 日在杜克大学召开2。2国内研究状况及发展趋势 在国内,一些高校和科研机构也开始跟踪 CS 的研究,如清华大学、中科院电子所、西安交通大学和西安电子科技大学等。自从 20
13、06 年 CS 的提出,在 IEEE 的信号处理汇刊、信号处理快报汇刊、信号处理杂志、信息论汇刊等国际知名期刊上开始涌现出上百篇关于CS 理论与应用方面的文献。2010 年,IEEE Journal of Selected Topics in Signal Processing 专门出版了一期关于 CS 的专刊,促进了 CS 理论在各个领域应用成果的交流。2011 年 4 月,第一本关于 CS 的专著 Compressed Sensing:Theory and Applications出版,不仅系统的介绍了 CS 的概念,而且汇集了世界各国学者在 CS 理论和应用上的观点和成功范例。国家自然科
14、学基金委也自 2009 年起资助了多项压缩感知方法的研究,涉及认知无线电、雷达成像、信号稀疏表示、多媒体编码、人脸识别等领域。1.3 本论文的结构安排 本文在对压缩感知理论以及现有的重构算法进行系统的研究之后,围绕正交匹配追踪重建算法展开研究来实现信号的重建,基于上述工作,本文内容分为四章,具体结构安排如下:第一章:绪论。首先介绍了压缩感知理论的研究背景及意义,然后介绍了国内外研究背景和现状,最后整理出全文内容的结构安排。第二章:压缩感知理论相关知识。首先介绍了压缩感知的框架,进而对信号的稀疏变换、观测矩阵的设计以及信号的重构三个主要方面的内容展开进一步详述,最后详细介绍了压缩感知理论在不同领
15、域的应用及有待解决的几个问题。第三章:正交匹配追踪重建算法。这一章着重分析了正交匹配追踪算法的原理、实现步骤和 Matlab的语言实现。第四章:基于 MATLAB的压缩感知图像重建仿真。首先介绍了 OMP算法的思想以及算法步骤,然后再 matlab 上进行试验仿真,得出实验数据。最后将 OMP算法与其他算法进行比较研究做出总结分析。西安文理学院本科毕业设计(论文)第4页 第二章 压缩感知理论相关知识 2.1 压缩感知理论框架 传统的信号采集、编解码过程如图 2.l 所示。编码端先对信号进行采样,再对所有采样值进行变换,并将其中重要系数的幅度和位置进行编码,最后将编码值进行存储或传输:信号的解码
16、过程仅仅是编码的逆过程,接收的信号经解压缩、反变换后得到恢复信号。采用这种传统的编解码方法,由于信号的采样速率不得低于信号带宽的 2 倍,使得硬件系统面临着很大的采样速率的压力。此外在压缩编码过程中,大量变换计算得到的小系数被丢弃,造成了数据计算和内存资源的浪费。图 2.1 传统编解码理论的框图 压缩感知理论对信号的采样、压缩编码发生在同一个步骤如下图 2.2 所示,利用信号的稀疏性,以远低于 Nyquist 采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身,而是从高维到低维的投影值,从数学角度看,每个测量值是传统理论下的每个样本信号的组合函数,即一个测量值已经包含了所有样本信号的
17、少量信息。解码过程不是编码的简单逆过程,而是在盲源分离中的求逆思想下利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构。解码所需测量值的数目远小于传统理论下的样本数。西安文理学院本科毕业设计(论文)第5页 图 2.2 缩感知理论的编解码框图 2.2 压缩感知的基本理论及核心问题 压缩感知,也被称为压缩传感或压缩采样,是一种利用稀疏的或可压缩的信号进行信号重构的技术3。或者可以说是信号在采样的同时被压缩,从而在很大程度上降低了采样率。压缩感知跳过了采集N个样本这一步骤,直接获得压缩的信号的表示。CS 理论利用到了许多自然信号在特定的基上具有紧凑的表示。即这些信
18、号是“稀疏”的或“可压缩”的。由于这一特性,压缩感知理论的信号编解码框架和传统的压缩过程大不一样,主要包括信号的稀疏表示、编码测量和重构算法等三个方面。对于一个实值的有限长一维离散时间信号X,可以看作为一个NR空间N1的维的列向量,元素为 n,n,=1,2,N。NR空间的任何信号都可以用N1维的基向量 1iNi的线性组合表示。为简化问题,假定这些基是规范正交的。把向量 1iNi作为列向量形成NN的基矩阵=12,N,于是任意信号X都可以表示为:X (式2.1)其中是投影系数,=,iiX 构成的N1的列向量。显然,X和是同一个信号的等价表示,X是信号在时域的表示,则是信号在域的表示。如果的非零个数
19、比N小很多,则表明该信号是可压缩的。一般而言,可压缩信号是指可以用K个大系数很好地逼近的信号,即它在某个正交基下展开的系数按一定量西安文理学院本科毕业设计(论文)第6页 级呈现指数衰减,具有非常少的大系数和许多小系数。这种通过变换实现压缩的方法称为变换编码。在数据采样系统中,采样速率高但信号是可压缩的,采样得到N点采样信号X;通过TX变换后计算出完整的变换系数集合i;确定K个大系数的位置,然后扔掉NK个小系数;对K个大系数的值和位置进行编码,从而达到压缩的目的。由Candes、Romberg、Tao和Donoho 等人在2004年提出的压缩感知理论表明,可以在不丢失逼近原信号所需信息的情况下,
20、用最少的观测次数来采样信号,实现信号的降维处理,即直接对信号进行较少采样得到信号的压缩表示,且不经过进行N次采样的中间阶段,从而在节约采样和传输成本的情况下,达到了在采样的同时进行压缩的目的4。Candes证明了只要信号在某一个正交空间具有稀疏性,就能以较低的频率MN采样信号,而且可以以高概率重构该信号。即,设长度为N的信号X在某正交基或框架上的变换系数是稀疏的,如果我们可以用一个与变换基不相关的观测基:MNMN对系数向量进行线性变换,并得到观测集合:1YM。那么就可以利用优化求解方法5从观测集合中精确或高概率地重构原始信号X。图2.3 是基于压缩感知理论的信号重构过程框图。图 2.3 基于压
21、缩感知理论的信号重构过程 2.2.1 信号的稀疏表示 压缩感知的第一步,即对于信号XNR,如何找到某个正交基或紧框架,使其在上的表示是稀疏的,即信号的稀疏表示问题。所谓的稀疏,就是指信号X在正交基下的变换系数向量为TX,假如对于02p 和0R,这些系数满足:1/PPiPiR (式2.2)则说明系数向量在某种意义下是稀疏的。如何找到信号最佳的稀疏域?这是压缩感知理论应用的基础和前提,只有选择合适的基表示信号才能保证信号的稀疏可压缩信号 稀疏变换 TX 观测得到的M维向量Y 重构信号 0minTX满足CSAXY 西安文理学院本科毕业设计(论文)第7页 度,从而保证信号的恢复精度。在研究信号的稀疏表
22、示时,可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candes和Tao研究表明,满足具有幂次速度衰减的信号,可利用压缩感知理论得到恢复,并且重构误差满足:62(/log)rrEXXCKN (式2.3)其中r=1/p1/2,0p1.文献6指出光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor系数及具有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性,可以通过压缩感知理论恢复信号。如何找到或构造适合一类信号的正交基,以求得信号的最稀疏表示,这是一个有待进一步研究的问题。Peyre把变换基是正交基的条件扩展到了由多个正交基构成的正交基字典。即
23、在某个正交基字典里,自适应地寻找可以逼近某一种信号特征的最优正交基,根据不同的信号寻找最适合信号特性的一个正交基,对信号进行变换以得到最稀疏的信号表示。对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。这是一种全新的信号表示理。用超完备的冗余函数库取代基函数,称之为冗余字典,字典中的元素被称为原子。字典的选择应尽可能的符合被逼近信号的结构,其构成可以没有任何限制。从冗余字典中找到具有最佳线性组合的K项原子来表示一个信号,称作信号的稀疏逼近或高度非线性逼近。从非线性逼近角度来讲,信号的稀疏逼近包含两个层面:一是根据目标函数从一个给定的基库中挑选好的或最好的基;二是从这个好的基中挑选最佳的K
24、项组合。因此,目前信号在冗余字典下的稀疏表示的研究集中在两个方面:(1)如何构造一个适合某一类信号的冗余字典;(2)如何设计快速有效的稀疏分解算法。在构造冗余字典方面,文献7中提出使用局部Cosine基来刻画声音信号的局部频域特性;利用bandlet基来刻画图像中的几何边缘;还可以把其它的具有不同形状的基函数归入字典,如适合刻画纹理的Gabor基、适合刻画轮廓的Curvelet基等等。在稀疏分解算法的设计方面,基于贪婪迭代思想的MP(Matching Pursuit)算法表现出极大的优越性,但不是全局最优解。Donoho等人之后提出了基追踪(basis pursuit,BP)算法。BP算法具有
25、全局最优的优点,但计算复杂度极高。之后又出现了一系列同样基于贪婪迭代思想的改进算法,如正交匹配追踪算法(OMP),分段匹配追踪(STOMP)算法等。西安文理学院本科毕业设计(论文)第8页 2.2.2 信号的观测矩阵 如何设计一个平稳的、与变换基不相关的MN维的观测矩阵,保证稀疏向量从N维降到M维时重要信息不遭破坏,是第二步要解决的问题,也就是信号低速采样问题。压缩感知理论中,通过变换得到信号的稀疏系数向量TX后,需要设计压缩采样系统的观测部分,它围绕观测矩阵展开。观测器的设计目的是如何采样得到M个观测值,并保证从中能重构出长度为N的信号X或者基下等价的稀疏系数向量。显然,如果观测过程破坏了X中
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 压缩 感知 正交 匹配 算法 图像 重建
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。