2023年7月29日发(作者：)

文献引用格式:石曼曼ꎬ李雷ꎬ徐静妹.基于模糊阈值的回溯分段弱正交匹配追踪算法[Ｊ].电视技术ꎬ２０１８ꎬ４２(２):５－９.ＳＨＩＭＭꎬＬＩＬꎬＸＵＪＭ.Ｂａｃｋｔｒａｃｋｉｎｇｓｔａｇｅｗｉｓｅｗｅａｋｏｒｔｈｏｇｏｎａｌｍａｔｃｈｉｎｇｐｕｒｓｕｉｔａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｆｕｚｚｙｔｈｒｅｓｈｏｌｄ[Ｊ].中图分类号:ＴＮ９１１.７　　　　文献标志码:Ａ　　　　ＤＯＩ:１０.１６２８０/ｊ.ｖｉｄｅｏｅ.２０１８.０２.００２Ｖｉｄｅｏｅｎｇｉｎｅｅｒｉｎｇꎬ２０１８ꎬ４２(２):５－９.基于模糊阈值的回溯分段弱正交匹配追踪算法石曼曼ꎬ李　雷ꎬ徐静妹(南京邮电大学理学院ꎬ江苏南京２１００２３)摘要:为提高分段弱正交匹配追踪(ＳｔａｇｅｗｉｓｅＷｅａｋＯｒｔｈｏｇｏｎａｌＭａｔｃｈｉｎｇＰｕｒｓｕｉｔꎬＳＷＯＭＰ)算法的重构质量ꎬ改进ＳＷＯＭＰ算法的重构性能ꎬ提出一种基于模糊阈值的回溯分段弱正交匹配追踪(ＢａｃｋｔｒａｃｋｉｎｇＳｔａｇｅｗｉｓｅＷｅａｋＯｒｔｈｏｇｏｎａｌＭａｔｃｈｉｎｇＰｕｒｓｕｉｔＡｌ￣ｇｏｒｉｔｈｍｂａｓｅｄｏｎＦｕｚｚｙＴｈｒｅｓｈｏｌｄꎬＦＴＢ－ＳＷＯＭＰ)算法ꎮ该算法首先通过采用ＳＷＯＭＰ算法初始化选取一些大于门限的原子ꎬ在每次迭代过程中引入回溯ꎬ采用基于模糊阈值的回溯方式删掉个别错误原子ꎬ实现自适应的选取原子来更新支撑集ꎬ每次迭代的过程不断更新扩大支撑集ꎬ逐步逼近信号的稀疏度ꎮ实验结果表明ꎬ相同实验条件下ꎬ新算法能够以高概率恢复原始一维信号ꎬ且重构误差小ꎻ对于在二维图像上的应用ꎬ新算法仍保证重构时间短的优势ꎬ并比原算法具有更好的重构精度ꎮ关键词:模糊阈值ꎻ压缩感知ꎻ回溯ꎻ分段弱正交匹配追踪ꎻ图像重构Ｂａｃｋｔｒａｃｋｉｎｇｓｔａｇｅｗｉｓｅｗｅａｋｏｒｔｈｏｇｏｎａｌｍａｔｃｈｉｎｇｐｕｒｓｕｉｔａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｆｕｚｚｙｔｈｒｅｓｈｏｌｄ(ＣｏｌｌｅｇｅｏｆＳｃｉｅｎｃｅꎬＮａｎｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓａｎｄＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓꎬＮａｎｊｉｎｇ２１００２３ꎬＣｈｉｎａ)ＳＨＩＭａｎｍａｎꎬＬＩＬｅｉꎬＸＵＪｉｎｇｍｅｉＡｂｓｔｒａｃｔ:Ｆｏｒｔｈｅｐｕｒｐｏｓｅｏｆｉｍｐｒｏｖｉｎｇｔｈｅｒｅｃｏｎｓｔｒｕｃｔｉｏｎｅｆｆｅｃｔａｎｄｐｅｒｆｏｒｍａｎｃｅｏｆｓｔａｇｅｗｉｓｅｗｅａｋｏｒｔｈｏｇｏｎａｌｍａｔｃｈｉｎｇｐｕｒｓｕｉｔ(ＳＷＯＭＰ)ａｌｇｏｒｉｔｈｍꎬａｂａｃｋｔｒａｃｋｉｎｇｓｔａｇｅｗｉｓｅｗｅａｋｏｒｔｈｏｇｏｎａｌｍａｔｃｈｉｎｇｐｕｒｓｕｉｔａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｆｕｚｚｙｔｈｒｅｓｈｏｌｄ(ＦＴＢ－ＳＷＯＭＰ)ｗａｓｐｒｏｐｏｓｅｄ.ＡｔｂｅｇｉｎｎｉｎｇꎬＳＷＯＭＰａｌｇｏｒｉｔｈｍｉｓａｄｏｐｔｅｄｔｏｓｅｌｅｃｔｉｎｉｔｉａｌａｔｏｍｓｓｅｌｅｃｔｉｏｎｉｎｔｈｉｓｎｅｗａｌｇｏｒｉｔｈｍꎬｔｈｅｎｂａｃｋｔｒａｃｋｉｎｇｂｅｉｎｇｅｎｌａｒｇｅｄｇｒａｄｕａｌｌｙｉｎｅｖｅｒｙｉｔｅｒａｔｉｏｎꎬｓｏｉｔｃａｎａｐｐｒｏｘｉｍａｔｅｔｈｅｓｐａｒｓｉｔｙｏｆｓｉｇｎａｌ.Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔꎬｕｎｄｅｒｔｈｅｓａｍｅｃｏｎｄｉｔｉｏｎꎬｔｈｅｎｅｗａｌｇｏｒｉｔｈｍｒｅｃｏｖｅｒｓｔｈｅｏｒｉｇｉｎａｌｏｎｅｄｉｍｅｎｓｉｏｎｓｉｇｎａｌｗｉｔｈｈｉｇｈｐｒｏｂａｂｉｌｉｔｙａｎｄｓｍａｌｌｒｅｃｏｎｓｔｒｕｃｔｉｏｎｅｒｒｏｒ.Ｆｏｒｔｉｃａｂｉｌｉｔｙꎬｗｈｉｃｈｓｔｉｌｌｈａｓｔｈｅａｄｖａｎｔａｇｅｏｆｈｉｇｈｒｅｃｏｎｓｔｒｕｃｔｉｏｎｓｐｅｅｄ.ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｉｍａｇｅｓｉｇｎａｌꎬｃｏｍｐａｒｅｄｗｉｔｈＳＷＯＭＰａｌｇｏｒｉｔｈｍꎬｔｈｅｎｅｗａｌｇｏｒｉｔｈｍｈａｓｈｉｇｈｅｒｒｅｃｏｎｓｔｒｕｃｔｉｏｎｅｆｆｅｃｔａｎｄｈｉｇｈｅｒｐｒａｃ￣Ｋｅｙｗｏｒｄｓ:ｆｕｚｚｙｔｈｒｅｓｈｏｌｄꎻｃｏｍｐｒｅｓｓｅｄｓｅｎｓｉｎｇꎻｂａｃｋｔｒａｃｋｉｎｇꎻｓｔａｇｅｗｉｓｅｗｅａｋｏｒｔｈｏｇｏｎａｌｍａｔｃｈｉｎｇｐｕｒｓｕｉｔꎻｉｍａｇｅｒｅｃｏｎｓｔｒｕｃｔｉｏｎｍｅｔｈｏｄｂａｓｅｄｏｎｆｕｚｚｙｔｈｒｅｓｈｏｌｄｉｓｕｓｅｄｔｏｄｅｌｅｔｅｓｏｍｅｗｒｏｎｇａｔｏｍｓｉｎｅａｃｈｉｔｅｒａｔｉｏｎ.Ｔｈｅｓｕｐｐｏｒｔｓｅｔｉｓａｄａｐｔａｂｌｅｕｐｄａｔｅｄｗｈｉｌｅｉｔｉｓ１　引言性ꎬ摆脱了采样两倍带宽的要求ꎬ节省了计算机硬件系统的存储空间ꎬ并减少了元件损耗ꎬ被广泛应用ꎮ观测矩阵怎样选取和重构算法如何设计ꎮ其中ꎬ重构作为ＣＳ的最后一步ꎬ其性能的好坏将直接影响ＣＳ的结果ꎬ因此研究设计出快速鲁棒的重构方法十分必要ꎮ当前的重构方法主要有三大类[４]:组合算法ꎬ基于最小ｌ１范数的凸优化方法与贪婪算法ꎮ这三类算法中ꎬ贪婪算法基于最小ｌ０范数ꎬ经由迭代选取出局ＣＳ有关键的三个技术[３]ꎬ即信号进行稀疏分解、新颖的采样理论ꎬ一经提出ꎬ就迅速成为现代信息方面的热门研究方向ꎮ该理论和奈奎斯特采样相比ꎬ发掘和利用原信号更多的性质ꎬ避免了资源浪费ꎬ提高了硬件的利用效率ꎮＣＳ理论提出ꎬ只要信号是稀疏的或可压缩的ꎬ就能够满足采样压缩一体化ꎬ且能够精确地恢复出信号ꎮＣＳ利用信号的稀疏性和相干压缩感知[１－２](ＣｏｍｐｒｅｓｓｅｄＳｅｎｓｉｎｇꎬＣＳ)作为一种基金项目:国家自然科学基金(６１３７３１３７ꎬ６１５０１２５１)ꎻ南京邮电大学引进人才科研启动基金资助项目(ＮＹ２１４１９１)投稿网址ｈｔｔｐ:∕∕ｗｗｗ.ｖｉｄｅｏｅ.ｃｎ｜«电视技术»第４２卷第２期(总第４９９期)　５部最优解的方式ꎬ来逐渐逼近信号ꎬ计算速度快使其被广泛研究应用ꎮ有很多经典的贪婪算法ꎬ如正则化的正交匹配追踪[５](ＲｅｇｕｌａｒｉｚｅｄＯｒｔｈｏｇｏｎａｌＭａｔｃｈｉｎｇＰｕｒｓｕｉｔꎬＲＯＭＰ)算法、稀疏度自适应匹配追踪[６](ＳｐａｒｓｉｔｙＡｄａｐｔｉｖｅＭａｔｃｈｉｎｇＰｕｒｓｕｉｔꎬＳＡＭＰ)算法、分段正ＳｔＯＭＰ)算法和分段弱正交匹配追踪[８](ＳｔａｇｗｉｓｅＷｅａｋＯｒｔｈｏｇｏｎａｌＭａｔｃｈｉｎｇＰｕｒｓｕｉｔꎬＳＷＯＭＰ)算法等ꎮＣＳ理论知ꎬ信号的测量过程表示为ｙ＝Φｘ(３)其中ꎬΦ∈ＲＭ×Ｎ为观测矩阵ꎬｙ∈ＲＭ×１为观测向量ꎬ且Ｍ≪Ｎꎬ而这些线性投影拥有足够多信息来恢复出信号ｘꎮ式(３)是欠定方程ꎬ没有唯一解ꎬ但ｘ在Ψ变换下的Θ是Ｋ稀疏的ꎬ且Ｋ≪Ｍ≪Ｎꎬ故结合(１)式ꎬ将(３)式转化为:ｙ＝Φｘ＝ΦΨΘ其中ꎬ记Ａ＝ΦΨ为压缩传感矩阵ꎬ即ｙ＝ＡΘ(５)ＣＳ理论证明ꎬ只要观测矩阵Φ符合约束等距特性(ＲｅｓｔｒｉｃｔｅｄＩｓｏｍｅｔｒｙＰｒｏｐｅｒｔｙꎬＲＩＰ)[２]ꎬ就可以从Ｍ个观测值中解出Ｋ个稀疏投影ꎮ若信号ｘ是Ｋ稀疏的ꎬΨ取单位矩阵即可ꎮ(４)交匹配追踪[７](ＳｔａｇｗｉｓｅＯｒｔｈｏｇｏｎａｌＭａｔｃｈｉｎｇＰｕｒｓｕｉｔꎬ其中ꎬＳｔＯＭＰ算法一步迭代可以挑选多个原子ꎬ计算时间相比ＯＭＰ与ＲＯＭＰ有明显的优势ꎬ但其重构精度差、鲁棒性低ꎮＳｔＯＭＰ算法无需已知信号稀疏度ꎬ其门限阈值和余量相关ꎬ并需要设置多个参数ꎬＳＷＯＭＰ算法对其改进ꎬ将原子的门限设计为关于原子和余量相关性的函数ꎬ以此降低对测量矩阵的要求ꎬ制定出更合适的原子选择标准[９]ꎬ且稀疏度自适应ꎮ除此之外ꎬ仍然有很多对贪婪算法的改进和应用[１０－１２]ꎬＳＷＯＭＰ算法相对于ＳｔＯＭＰ算法ꎬ虽降低了对测量矩阵的要求ꎬ但是重构效果并未有所提高ꎮ本文针对ＳＷＯＭＰ算法重构效果不好这一缺点ꎬ提出基于模糊阈值的回溯分段弱正交匹配追踪算法ꎬ实验结果表明ꎬ本文算法重构误差小ꎬ且重构效果明显优于原算法ꎮ３　基于模糊阈值的分段弱正交匹配追踪算法３.１　分段弱正交匹配追踪算法且可以自适应的选择原子ꎬ它们唯一不同的是选择原子时的门限设置ꎬ相对于ＳｔＯＭＰ算法只和当前残差相关ꎬ且对阈值的依赖较大ꎬ门限设置与测量矩阵有密切的关系ꎬ对于不同的观测矩阵要设置不同的门限ꎬ而ＳＷＯＭＰ算法的原子筛选准则更合适ꎬ该算法将原子的门限设计为原子与残差相关系数相关的阈值ꎬ称之为“弱选择”[７]ꎬ以此降低对测量矩阵的要求ꎮＳＷＯＭＰ算法延续了ＳｔＯＭＰ的优点ꎬ重构速度快ꎬ但其重构精度不高ꎬ有些情况略差于ＳｔＯＭＰ算法ꎬ有较大的改进空间ꎮ３.２　基于模糊阈值的分段弱正交匹配追踪算法该算法无需信号的稀疏度已知为前提ꎬ重构时间短ꎬ但其重构质量差ꎬ无法较好的逼近原始信号ꎬ考虑ＳＷＯＭＰ算法仅以门限值来更新原子库ꎬ随着迭代的增加ꎬ这个过程会导致加入原子的个数太多ꎬ故本文提出基于模糊阈值的回溯分段弱正交匹配追踪算法ꎬ以此实现重构精度的提升ꎮ新算法引入回溯思想ꎬ将解的支撑集里的原子再次筛选ꎬ剔除贡献较小的原子ꎬ以此提高ＳＷＯＭＰ算法的重构效果ꎬ并结合模糊阈值机制ꎬ自适应的选取前βＬ个较大元素构成ＳＷＯＭＰ的门限设置降低对测量矩阵的要求ꎬ且ＳＷＯＭＰ算法是ＳｔＯＭＰ算法的一种改进算法ꎬ２　压缩感知基本理论一体化ꎬ在很多领域有很广阔的应用前景ꎬ如应用到雷达成像[１３]、遥感成像[１４－１５]以及机器学习中的压缩追踪[１６－１８]ＣＳ理论采用高效的获取信息的方式ꎬ采样压缩等ꎮ设ｘ是一维稀疏随机信号ꎬ长度为Ｎꎬ即ｘ∈ＲＮ×１ꎬ由于ｘ是稀疏的ꎬ不妨假设其在一组正交基{φｉｉ＝１ꎬ２ꎬ...ꎬＮ}下的变换表示为:ｘ＝向量ꎬΨ＝其中ꎬΘ＝[θ１ꎬθ２ꎬ...ꎬθＮ]Ｔ∈Ｒ[φ１θｉφｉ∑ｉ＝１Ｎ＝ΨΘ(１)Ｎ×１是稀疏系数字典矩阵ꎬθｉ＝‹ｘꎬφｉ›＝φｉＴｘ(ｉ＝１ꎬ２ꎬ