基于StOMP算法的压缩感知技术研究.doc
《基于StOMP算法的压缩感知技术研究.doc》由会员分享,可在线阅读,更多相关《基于StOMP算法的压缩感知技术研究.doc(43页珍藏版)》请在沃文网上搜索。
1、 西南交通大学本科毕业设计(论文) 第II页基于步移正交匹配追踪算法的图像压缩感知技术研究 西南交通大学本科毕业设计(论文) 第V页摘 要压缩感知理论是由Donoho和Candes提出的一种充分利用信号稀疏性的全新的信号采样理论。该理论表明,用远低于Nyquist 采样定理要求的频率对信号进行采样也能实现信号的精确重构。压缩感知理论利用原始图像或信号的稀疏性先验知识,通过适当的优化算法,可以由少量的观测值或采样值对信号进行精确重建。该理论突破了传统的以Nyquist定理为基准的信号处理方法,实现了在获取数据的同时对其进行适当的压缩,克服了采样数据量大,采样时间长及数据存储空间浪费严重的问题,因
2、此进一步降低了信号处理的时间和器件成本。 压缩感知理论有三个核心方面:(1)稀疏变换,即对一个非稀疏的信号,找到一个合适的正交基使该信号在它上可以稀疏表示;(2)测量矩阵,与变换基不相干且平稳的矩阵;(3)重构算法,利用数学算法完成对信号的精确重构,该过程可看为求解一个优化问题。 本文研究的主要内容是重构算法,它是压缩感知理论核心中的关键部分,直接决定着重构信号的质量及重构速度、应用效果。重构算法的关键在于如何从压缩感知得到的低维数据中准确地恢复出原始的高维数据。目前看来重构算法主要可以归结为三大类,即贪婪算法,凸优化算法和组合算法。三种算法各有优势,但作为基础算法,贪婪算法中的正交匹配追踪算
3、法对后来陆续提出和改良的算法具有重要的指导意义。 本文通过对压缩感知理论及国内外现有的重建算法进行了学习之后,选择步移正交匹配追踪算法进行重点研究,主要完成工作如下:在总结现有的各种算法及模型如最小L0范数模型,OMP算法,StOMP算法的基础之上,分别从一维信号和二维可压缩信号的角度考察StOMP算法的相对误差、匹配度及运行时间。利用matlab m语言与C语言搭建了仿真平台,对StOMP算法进行了仿真研究。此外对比了几种典型贪婪算法的性能和复杂度。关键词:压缩感知;稀疏变换;匹配追踪;重建算法AbstractCompressed sensing is a novel sampling th
4、eory which is proposed by Donoho and Cands. 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. For sparse and compress
5、ive signal, it can be reconstructed exactly by using the appropriate reconstruction algorithms. Compressed theory breaks though the traditional Nyquist 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
6、 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 need to find a proper orthogonal basis on which the signal has a sparse representation; (2) Observation matrix, it is irrelevant with the ort
7、hogonal basis; (3) reconstruction algorithms, using a reconstruction algorithm to ensure the accuracy of the signal reconstruction, the whole process can be considered as the solve to a optimization problem. The main content of this thesis is reconstruction algorithm. The key of reconstruction algor
8、ithm is how to accurately recover the original high-dimensional data from low dimensional samples. For now, the reconstruction algorithm can be attributed to three main categories: the greedy algorithm, convex relaxation and the combination algorithm. Three algorithms have their own advantages. As t
9、he basal algorithm, the orthogonal matching pursuit algorithm has important guiding significance for improved and new algorithms. In this thesis, properties of the existing reconstruction algorithms are firstly analyzed. We choose the stagewise orthogonal matching pursuit algorithm as the key resear
10、ch. Based on this, the main contributions of this thesis are summarized as follows. This thesis has reviewed the existing reconstruction algorithms such as L0 minimization, OMP, StOMP and done a large number of experiments on them. The simulation platform based on Matlab m and c language are constru
11、cted. We analyze the results such as PSNR, relative error,matching ratio and running time of these algorithms from one-dimensional sparse signals and two-dimensional compressible signals respectively. Keyword: Compressed sensing; sparse transform; matching pursuit; reconstruction algorithm 目 录摘 要IVA
12、BSTRACTV目 录VI第1章 绪 论11.1 本论文的背景和意义11.2 本论文的主要方法和研究进展11.3 研究背景及意义31.3.1 研究背景31.3.2 研究意义41.4 本论文的结构安排4第2章 压缩感知理论与应用62.1 压缩感知原理62.2 压缩感知主要内容72.2.1 信号的稀疏变换72.2.2 测量矩阵82.2.3 信号的重构102.3 压缩感知的应用102.3.1 压缩成像112.3.2 信道编码112.3.3 模拟/信息转换122.3.4 生物传感12第三章 压缩感知重构算法133.1 最小L1范数法133.2 匹配追踪算法143.3 最小全变分法143.4 迭代阈值法
13、15第四章 STOMP算法164.1 STOMP算法及其实现164.1.1 StOMP算法步骤164.1.2 StOMP算法的Matlab语言实现174.1.3 StOMP算法的C语言实现184.1.4 Matlab与C的混合编程194.2 StOMP算法的仿真与结果分析224.2.1 不同采样率下的仿真结果224.2.2 不同阈值下的仿真结果254.2.3 加噪情况下的仿真结果274.2.4 算法性能分析30结 论345.1 全文总结345.2 工作的的不足与展望34致 谢36参考文献37 西南交通大学本科毕业设计(论文) 第38页第1章 绪 论1.1 本论文的背景和意义众所周知,传统的信号
14、采样以奈奎斯特(Nyquist)采样定理为基础。为了不丢失信号的信息,精确重构信号,在获取信号时,采样频率要大于信号中最高频率的两倍。但是随着各种信号处理系统获取能力的不断增强,需要后期处理的数据量也快速增加,奈奎斯特定理的局限性给系统的处理能力提出了更高的要求,同时也给相应的硬件设施的设计带来了极大的挑战。如何高效处理这些数据并且最大限度的节省存储空间及传输成本已成为目前信息领域进一步向前发展的主要瓶颈之一。 实际上,奈奎斯特采样定理是信号精确重构的充分条件而不是必要条件,奈奎斯特采样定理并不是唯一、最优的采样理论。因此研究如何突破以奈奎斯特采样定理为基础的信息的提取、处理、融合、存储、及传
15、输是推动信息领域发展的关键。 在2004年Donoho等人针对稀疏性信号,提出了压缩感知(Compressive sensing,简称CS)理论。在随后的几年间该理论迅速发展,为解决上述问题奠定了基础。与传统信号处理方式不同,压缩感知理论以空间变换为基础,随机观测矩阵作为手段,优化求解作为恢复信号的方法。压缩感知理论在获取信号的同时对数据进行适当的压缩,其采样频率低于奈奎斯特采样频率,减少了采样数据,节省了存储空间,同时又包含了足够的信息量,能通过合适的重建算法对特定的图像或者信号进行精确重构。它将传统的数据采集和压缩合二为一,并且不需要复杂的数据编码算法,非常适合于要求采用小型器件的实现场合
16、。信号的稀疏重建与压缩感知理论有重大的实用价值和应用前景,已经成为信号领域中一个新的研究方向。1.2 本论文的主要方法和研究进展从2004年提出压缩感知理论至今,该理论得到了飞速的发展。现有的压缩感知理论的研究成果大多来自于外国的学者,国内对于压缩感知的研究还处于起步阶段。作为一个新的理论,有关压缩感知的学术论文还主要在于理论上的证明和完善。目前,压缩感知理论在信号重建优化问题求解,稀疏变换及采样观测矩阵的设计方面取得了一定的进展。 在信号重构方面,目前常用的重构算法主要是以下两大类,即针对最小L0范数提出的一系列贪婪算法及由最小L1范数提出的凸优化算法。 凸优化算法的计算量大但是重建效果较好
17、,它主要针对最小L1范数进行求解。其求解模型主要为 s.t. (1-1)或者将上式转化为无约束问题 (1-2)其中,是松弛因子,它控制着重建误差和信号稀疏度之间的平衡。这一类算法主要有梯度投影法(GPSK, Gradient Projection for Sparse Reconstruction)、基追踪算法(BP, Basis Pursuit)、最小角度回归法(LARS,Least Angle Regression)、同伦算法(Homotopy Algorithm)等。凸优化算法重构误差小,重构效果较好,但是这类算法的复杂度高,对于大规模数据问题难以应用,实用性较差。 相比而言,由于计算量
18、小,重建效果较好且较容易实现,贪婪算法的应用最为广泛。这类算法是针对最小L0范数进行求解,它允许一定的重构误差存在,求解模型如下 s.t. (1-3)其中为一个很小的常数。这类算法的代表是匹配追踪(MP, Matching Pursuit)算法1和正交匹配追踪(OMP,Orthogonal Matching Pursuit)算法2。此外还包括基于OMP算法的一系列改进算法主要包括正则化匹配追踪(ROMP,Regularize OMP)、步移正交匹配追踪(StOMP,stagewise orthogonal matching pursuit)、稀疏自适应匹配追踪(SAMP, Sparse Ada
19、ptive MP)、压缩采样匹配追踪法(CoSaMP, Compressed Sampling MP)等。Blumensath和Davie提出了针对贪婪算法的方向追踪法(DP, Directional Pursuit),这类算法在选取合适的原子之后不采用耗时的最小二乘法求解,通过选择合适的方向和步长来搜索最优解,这种方式比最小二乘法求解要快很多,其搜索方向通常采取负梯度,共轭梯度方向等。这类算法有梯度追踪(GP, Gradient Pursuit)、共轭梯度追踪(CGP,Conjugate GP)等。梯度追踪算法在压缩感知中的信号重构过程中应用到最优化理论中的快速下降法,并且结合了匹配追踪算法
20、,在计算量上尽量逼近MP算法,在重建效果上逼近OMP算法,这是一种可行的信号重建算法。 最近,Rath和Gulllemot提出了一种新的解决方法,弥补空间匹配追踪(CMP, Complementary MP)。以上介绍的算法都是通过M维的观测信号y和观测矩阵来求解N维的原始信号x,而CMP算法则是直接在原始信号x所在的N维空间中求解。这种求解方式不仅收敛速度快,信号的重构质量好,而且重构出的信号更加稀疏。 另外还有Byesian类得统计优化算法,最小(0p1)范数的迭代聚焦算法(FOCUSS, Focal Underdetermined System Solver)等,这些方法的性能介于贪婪算
21、法和凸优化算法之间。 迭代阈值法(ISA, Iterative threshold algorithm)在实际中也得到了广泛的应用,这类算法较易实现,计算量适中,在最小L1范数的贪婪算法和最小L1范数的凸优化算法中都有应用。但是迭代阈值算法对于迭代初值和阈值的选取都比较敏感,而且不能保证求出的解是稀疏的。 由于压缩感知理论有着广泛的应用前景,接下来的工作便是相关理论的完善和实践应用的成果,理论上包括图像视频压缩、信号恢复、分布式压缩感知理论、超宽带雷达系统、医学影像系统和光谱图像处理等方面。在硬件实现上,美国的Rice大学已研制出了单像素相机,它具备传统成像器件不具有的对图像波长的自适应能力。
22、1.3 研究背景及意义1.3.1 研究背景传统的信号获取,编译码过程如图1-1所示:信号X变换压缩解码采样编 Y码端恢复信号X解压缩反变换解 接受数据码 端 Y 图1-1 传统信号采集、编码过程 Figure 1-1 Traditional signal acquisition,encoding process编码端先对信号进行采样,然后对所有的采样值进行变换,压缩编码,即将其中重要数据的幅度和位置进行编码,再将编码值进行储存或者传输。解码端是编码的逆过程,接收到的信号经解压缩、反变换之后得到恢复信号。这种传统的以奈奎斯特定理为基础的编译码方式存在两个缺陷:(1)数据的获取及处理,在实际的应用
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
20 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 StOMP 算法 压缩 感知 技术研究
