层次存储器层次执行模式本章小结第三章基于的整图像并行重构算法引言正交匹配追踪算法及其变化算法分析并行重构算法可行性分析并行算法实现途径实现步骤实验结果及性能分析性能分析实验结果性能分析本章小结第四章多粒度并行压缩感知重构算法引言分块压缩感知以及多级并行处理技术分块压缩感知多级并行处理技术多粒度压缩感知并行重构算法实现原理实现步骤实验结果及性能分析应用多粒度并行计算架构前后对比应用和协同多粒度并行计算架构前后对比本章小结第五章基于遗传算法的压缩感知重构及其并行优化绪论遗传算法基于遗传算法的压缩感知重构及其并行化基于遗传算法的压缩感知重构万方数据基于遗传算法的压缩感知重构的并行优化实验结果及性能分析重构算法优化前后对比并行优化前后对比本章小结第六章总结与展望全文总结未来工作展望参考文献附录攻读硕士学位期间撰写的论文致谢万方数据南京邮电大学硕士研究生学位论文专用术语注释表专用术语注释表缩略词说明应用程序接口贝叶斯进化追踪算法压缩采样匹配追踪算法压缩感知统计算设备架构离散余弦变换离散小波变换进化算法快速傅里叶变换遗传算法图形处理器多指令流多数据流多指令流单数据流匹配追踪算法正交匹配追踪算法约束等距性正则化正交匹配追踪算法单指令流多数据流单指令流单数据流的特例，尽管此方案更加灵活和有效，但是由于它需要在每次迭代过程中注入随机噪声和自适应图像去噪滤波器，因此，进步加大了算法的复杂度。文献提出的方案可以获得更好的重建质量，而且可以获得更快的收敛速度，但它是通过应用多小波变换替代变换来获得的提高，并未从重构算法本身的角度出发。文献考虑到了小波系数的统计相关特性，万方数据南京邮电大学硕士研究生学位论文第三章基于的整图像并行重构算法在多元模型的基础上提出了种新的重构算法，这种方案是通过建立小波系数统计相关模型来完成的，重构质量要优化当下的大多数算法，但是重构时间并不是最优的。文献分析了重构算法的各个模块的复杂度，提出了该算法的瓶颈产生在映射阶段以及最小二乘阶段，然后分别运用不同的算法在上进行并行实现。在该算法中，还可以通过减少与之间的通信优化内存使用方式以及减少内核函数的使用数量来获得进步的提高。基于上述问题，本章在文献的基础上，针对压缩感知的三种信号重构算法以及进行了并行优化。这三种算法的结构非常适合在上进行并行实现，将其最耗时的映射阶段和矩阵求逆并行化，同时将寻找最匹配原子的过程同映射过程合并，在最小二乘阶段完成更新残差的矩阵计算部分，如此来，优化了计算结构，减少了同之间的通信开销，获得了可观的收益。正交匹配追踪算法及其变化算法分析贪婪算法由于其相对低复杂度的特性，成为比较常用的信号恢复算法，这类方法在每次迭代时得到个最优解，以此来逐步逼近原始信号。这类算法主要包括匹配追踪算法，正交匹配追踪算法，为了加速搜索过程，在这基础上衍生出了很多改进算法，包括正则化正交匹配追踪算法，它采用正则化方法对原子进行二次筛选，信号重建速度较快分段正交匹配追踪算法，相比算法，进步降低了算法复杂度，在每次迭代过程中，根据事先预设的阈值，选择部分满足条件的原子，从而提高了运行速度压缩采样匹配追踪算法，引入了回溯的顺序编码思想，在每次迭代过程中不断更新索引集，从而在定程度上提高算法的执行效率。下面简单介绍三种常见的贪婪重构算法。正交匹配追踪算法正交匹配最终算法是最早的贪婪算法之，对后续的大多数贪婪算法都产生了很深的影响。正交匹配追踪算法沿用了算法的原子选择策略，但是由于算法中，只能保证每次迭代产生的残差信号与相邻的个原子正交，而不能保证与之前所有的原子成正交关系，这就使得每次迭代得到的结果不是最优的而是次最优的。因此，要想获得收敛信号就需要进行大量的迭代运算。为了克服算法这种固有的缺陷，算法对此做了改进，在每次迭代之后，引入了施密特正交化处理，它保证了每次迭代得到的残差与之前所有的原子保持正交关系，进而保证了结果是最优解，同时大大减少了迭代次数，使收敛速度加快。算法的核心思想就是在过完备字典库中，选择尽可能少的原子的加权和来表示测量万方数据南京邮电大学硕士研究生学位论文第三章基于的整图像并行重构算法值。我们令过完备字典矩阵为感知矩阵，其中代表过完备字典中的第个原子，原始信号在稀疏基下是稀疏的，其中稀疏度为。以正交匹配追踪算法为代表的系列重构算法，通过求残差信号与字典矩阵中每个原子的内积的相关系数来选择最匹配的原子，得到信号的估计并最终得到残差信号的更新算法的具体流程可以表示为初始化各个参数残差与作内积，并找到最大值所在位置，记录更新索引集最小二乘法获得信号的估计更新残差其中，代表第次迭代时的残差向量。迭代次数加，若不满足终止条件，则返回步骤若满足终止条件，则输出重构向量。二正则化正交匹配追踪算法正则化正交匹配最终算法是和等人在算法的基础上，将正则化过程应用到已知稀疏度为信号的重构算法中，文献中指出，信号重构算法对于所有满足准则的测量矩阵以及所有稀疏性信号都能够准确地重构。它与重构算法的最大不同之处在于重构算法首先根据相关性原则对所有原子进行次筛选，选择多个原子作为候选集，此次筛选是根据局部逼近的结果，选择个原子，或选择所有的非零值。然后在候选集中，根据正则化规则，通过求残差信号与字典中所有原子之间的内积绝对值，来计算相关系数，进而对候选集中的所有原子做二次筛选，得到部分原子，并纳入支撑集中。文献提到，对于满足准则的测量矩阵，其参数满足，以及万方数据南京邮电大学硕士研究生学位论文第三章基于的整图像并行重构算法稀疏度为的维原始信号，经过压缩测量后，利用重构算法进行信号重构，最多经过次迭代即完成重构。在每次迭代过程中，能够保证至少个新的原子被选中，候选集以外的原子也有可能被找到，但是由于其相关性要低于候选集内的原子，因此被选中的概率很小。有些情况下，需要重构的信号并不是稀疏的，但在定条件下接近稀疏，比如文献提到，系数可以以定速率衰减的可压缩信号，应用时需要将停止迭代准则改为迭代次或者直至残差信号为。在整个信号重构过程中，比较耗时的步骤是鉴定阶段，也就是选择候选集的阶段，这里通常会用到合并排序堆排序等排序算法，来对相关系数进行非增排序正则化阶段次迭代阶段，因为它包含了大量的矩阵向量运算，还需要解决最小二乘问题。有些情况下，所需的迭代次数可能要超过个固定的值，此时利用正交化算法来保存分解因子会是个行之有效的方法，但是这会对存储能力提出很高的要求，因此，对于存储能力不是很高的情况下，还是选用迭代算法来进行重构。重构算法的基本步骤如下表示初始化各个参数计算局部逼近降序排序，取最小支撑集前个，或所有非零值正则化过程，对于所有子集，满足最小二乘更新残差迭代次数加，若不满足终止条件，则返回步骤若满足终止条件，则输出重构向量。三压缩采样匹配追踪算法年和等人提出压缩采样匹配追踪算法，引入了回溯顺序编码思想，它是在算法的基础上，吸收了多种算法的优势，进步提高了信号重构质量，能够得到重构算法达不到的信号重构保证。它借鉴了组合算法的思想来保证信号重构的速度并提供个严格的误差范围。算法不同于其他简单的贪婪算法，对于稀疏度为的原始信号，在每次迭代过程中，根据原子集合与残差信号的相关性，选择个原子更新原子集合，然后根据原始信号的长度来淘汰部分原子。和在文献中对万方数据南京邮电大学硕士研究生学位论文第三章基于的整图像并行重构算法等距约束性做了详细地阐述，算法利用测量矩阵的这种等距约束性保证了每步迭代中都能够成功地选择原子。对于停止准则，可以将迭代次数选为原始信号的稀疏度，也可以设定个阈值来提前终止。在信号重构算法中，般将信号的稀疏度作为已知条件，而实际中又不可能做到在信号重构之前对原始信号进行稀疏表示来得到信号的稀疏度。般有两种解决方案，最简单的方法就是根据测量值的个数来求得。文献指出，当满足时，就可以重构出绝大多数稀疏信号，因此，信号的稀疏度取是比较合理的。另外种方法就是通过多次实验得到个统计上比较合适的值，但这种方法在实际中十分受限。大部分情况下是不允许进行大量的实验操作的。算法的基本步骤如下初始化各个参数计算局部逼近，并降序排序，取前个位置根据信号长度进行支撑集合并将新选定的原子与原有的合并计算估计通过解决最小二乘问题来近似表示目标信号根据信号的信号稀疏度来更新支撑集更新残差迭代次数加，若不满足终止条件，则返回步骤若满足终止条件，则输出重构向量。并行重构算法可行性分析重构算法的核心思想就是用最少的列向量的加权和来表示测量值，的主要步骤包括映射过程求解最小二乘过程以及更新残差过程。下面对三个主要步骤进行逐分析。映射其中代表维残差信号，代表残差信号与第个原子的内积，每个原子的维数也万方数据单位代码密级硕士学位论文论文题目图像压缩感知并行重构技术研究郭睿冉宋建新教授信号与信息处理图像处理与多媒体通信工学硕士二零四年二月学号姓名导师学科专业研究方向申请学位类别论文提交日期万方数据万方数据南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人学位论文及涉及相关资料若有不实，愿意承担切相关的法律责任。南京邮电大学学位论文使用授权声明本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档允许论文被查阅和借阅可以将学位论文的全部或部分内容编入有关数据库进行检索可以采用影印缩印或扫描等复制手段保存汇编本学位论文。本文电子文档的内容和纸质论文的内容相致。论文的公布包括刊登授权南京邮电大学研究生院办理。涉密学位论文在解密后适用本授权书。研究生签名日期研究生签名导师签名日期万方数据摘要信号重构是压缩感知技术的个主要方面，它是通过求解个高度非线性的优化问题，从组线性观测数据中恢复出原始信号的过程。整个过程对硬件要求高，重构时间长，致使压缩感知技术无法在实际中被广泛应用。对此，本文