常见的匹配追踪算法(MP)是一种非常典型的迭代贪婪算法,它实质上是一种为了减小求取最优解时所遇到的困难进而转求取次最优解的一种方法。该方法最关键之处就是在迭代的策略上,其做法是:先将信号与过完备字典中的所有原子做某种相关性运算,找出与信号最匹配的那个原子及其对应的系数,再将信号减去匹配出来的原子与他们对应系数的线性组合,我们将这个差值称为残留信号。再将残留按照上述操作,得到第二个匹配的原子及其系数……,依次递推,直到残留信号足够小时(满足要求)停止迭代。在一定条件下,我们可以用匹配出来的原子与其对应系数的线性组合来近似表示原信号。值得强调的是:每次迭代后得到的残留信号应为与原子字典中所有原子相匹配后得到的残留信号的最小值,即能量下降最快。利用匹配追踪算法得到的分解系数,虽然不如基追踪算法得到的稀疏,但是其效果已经差别不大。一般来说,对同一信号分别采用匹配追踪算法和基追踪算法两种不同的稀疏表示算法来进行分解时,前者无论是在算法的复杂度还是计算速度等方面都较后者有比较明显的优势。对于传统的匹配追踪算法而言,过完备原子字典必须是事先确定好的,过完备字典中的原子数量越大,信号分解的结构就越稀疏、但这又会给算法在计算量和存储量上提出更高的要求。随着视频和图像清晰度的提升,其数据量也越来越大,现有的计算机无论在计算速度还是存储容量等方面都无法满足对这些高清视频或图像用传统方法进行稀疏表达的要求,这大大限制了传统匹配追踪算法的推广和应用。大部分改进算法主要立足于在寻求更优的原子搜索方法或将更多多参数优化方法应用到算法中这个方面着手,通过这些改进,在一定程度上减少了算法在计算复杂度和存储空间上的要求。然而,在设计搜索策略和寻找优化算法的基础上如何充分利用字典中原子本身的特点和字典的结构特点来提高算法性能也是非常值得关注的研究方向。本文作者主要做了以下一些工作:(1)对图像信号的特点进行系统分析。由于图像信号存在着视觉、编码以及心理上的冗余,这些特征使得稀疏分解的方法相对于传统的基于基分解方法更适合于图像信号的表示和压缩。(2)稀疏表示所用的算法有很多,如框架方法、组合方法、基追踪算法和匹配追踪算法……,作者通过对图像信号特征进行分析和实验验证,总结出匹配追踪算法比较适合于图像信号的稀疏表示。(3)对稀疏表示所用的,如Gabor字典、Chirplet字典、FMmlet字典、Dopperlet字典等常用字典进行深入研究,相比于其它的原子,Gabor原子的结构决定了它的时频聚集性是最好的,表示出来的图像更加稀疏。鉴于这点,本文选择了Gabor过完备字典。(4)传统的匹配追踪算法始终采用固定不变的过完备字典,使得在匹配原子过程中每次迭代的迭代次数都是一样的,计算量很大,没有自适应性;改进后的算法中所使用的子字典是在分解过程中实时制备的,这样可以减少其所需的计算量和存储容量。(5)将字典中的原子离散化以后再通过快速傅里叶变换(FFT)可以将算法中的内积计算替换成互相关操作,从而达到显著减小匹配所需计算量的目的。(6)借助MATLAB平台,对同一图像分别用改进后的算法和传统算法进行表示,从计算机处理速度、对计算机存储量的要求以及重建图像质量等方面对比仿真结果,以验证分析的合理性。(7)将同一图像分别用本文所述方法和基于基分解的方法(JPEG和JPEG2000)表示,从不同角度对它们进行比较,得出比较结论。