（信号与信息处理专业论文）匹配追踪算法在图像压缩中的研究与应用.pdf

南京邮电学院坝j 研究生学位论史摘赛 摘要 信号的稀疏表示在信号处理领域有着重要的意义，如何得到信号的稀疏表示 以利于后续的压缩、去噪、分析等应用，一直是人们关注和研究的热点。近年来， 以迭代的贪婪算法为核心的匹配追踪算法，作为一种有效的信号稀疏表示方法， 受到越来越多学者的重视，并出现了许多工程应用。 本论文围绕着匹配追踪算法，对它的一些核心问题进行了论述，并对其在图 像信号压缩方面的应用进行了研究。 全文共分六个部分。第一章，介绍信号的稀疏表示问题；第二章，介绍匹配 追踪算法的基本原理：第三章，从不同角度介绍匹配追踪算法的一些改进算法： 第四章，着重讨论匹配追踪算法中的字典问题；第五章，研究匹配追踪算法在图 像信号压缩方面的应用，在f 交匹配追踪算法的基础上进行了算法改进，并给出 了仿真结果：最后一章，提出改进的字典训练算法，并给出了仿真结果。 关键词：稀疏表示、匹配追踪算法、字典、图像压缩 南京邮l 乜学院坝i ：研究生学位论史 a b s t r a c t a b s t r a c t t h es p a r s er e p r e s e n t a t i o np l a y sa l li m p o r t a n tr o l ei nt h es i g n a lp r o c e s s i n g ，s o t h e r eh a sb e e na ne x p l o s i o no fi n t e r e s ti nh o wt og e ti t ，w h i c hi su s e f u lt ot h et a s k so f c o m p r e s s i o n ，d e n o i s e ，a n da n a l y s i s ，o v e rt h el a s td e c a d e ，m o r ea n dm o r es c h o l a r sp u t t h e i ri n t e r e s t si nt h em a t c h i n gp u r s u i tb a s e do ng r e e d yi t e r a t i v ea l g o r i t h m ，a n ds o m e e n g i n e e r i n ga p p l i c a t i o n sa p p e a r e d t h et h e s i s ，f o c u s e so nm a t c h i n gp u r s u i ta l g o r i t h m ，a n dc a r r i e so u ti n v e s t i g a t i o n s i ns e v e r a le s s e n t i a lp r o b l e m sf o ri t st h e o r ya n d a p p l i c a t i o n t h et h e s i sc o n s i s t so fs i xp a r t s i nt h ef i r s tc h a p t e r , t h es p a r s er e p r e s e n t a t i o ni s i n t r o d u c e d t h es e c o n dc h a p t e r , f o u n d a t i o nt h e o r yo fm a t c h i n gp u r s u i ta l g o r i t h mi s p r e s e n t e d t h et h i r dc h a p t e r ，s o m ei m p r o v e dv e r s i o n so fm a t c h i n gp u r s u i ta l g o r i t h m a r ed i s c u s s e d t h ef o u r t hc h a p t e rf o c u s e so nt h ed i c t i o n a r yu s e di nm a t c h i n gp u r s u i t a l g o r i t h mt h ef i f t hc h a p t e r ，i m a g ec o m p r e s s i o nb a s e dm a t c h i n gp u r s u i ti sd i s c u s s e d ， a n da ni m p r o v e da l g o r i t h mi sp r e s e n t e da n dd i s c u s s e d ，a n dt h er e s u l to fs i m u l a t i o ni s g i v e n a n di nt h el a s tc h a p t e r , a ni m p r o v e da l g o r i t h mo fd i c t i o n a r yt r a i n i n g i s p r e s e n t e da n dd i s c u s s e d ，a n dt h er e s u l to fs i m u l a t i o ni sg i v e n k e y w o r d s ：s p a r s er e p r e s e n t a t i o n ，m a t c h i n gp u r s u i t ，d i c t i o n a r y , i m a g ec o m p r e s s i o n i l 南京邮电学院学位论文独创性声明 7 6 4 9 9 8 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电学院或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：超坠日期：翌型：! ! 少 南京邮电学院学位论文使用授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电学院研究生部办理。 研究生签名：地立k 导师签名：建墨盔日期、生! ：望 南京揶1 乜学院倾l ：f o f 究生学位论卫硝一帝绪论 第一章绪论 在信号与信息处理中，如何有效地对信号进行表达，是一个很重要的问题。 建立信号模型，常常是我们要做的第一步。在信号的数学模型中，应用最普 遍、影响最深刻的，就是信号的线性模型。 旦 厂( f ) = 0 i ，g ，( f ) ( 1 ，1 ) i = l 这里，信号被分解成展开函数的线性组合，式( 1 1 ) 中的系数2 ，和展开函数 g ，就构成了信号模型。通常情况下，我们总是希望用尽可能简单的方式来描述 现象，对信号的表示同样如此。如果模型是紧凑的或者况“稀疏”的，那么这个 分解就显示出信号的有效性与简捷性，有利于信号的分析、修正、去噪、压缩或 者增强等后续处理。紧凑的模型意味着要求展开函数和信号有着高的相关性。 传统的信号表示方法是基于“基”的展开，如f o u r i e r 函数或者小波函数等。 这些基函数都有着较强的物理意义，而且对于某些特定类型的信号能取得很好的 表示效果。但当用这。类性质特定的基函数来表达任意信号时，一旦基函数确定， 对于一个信号的展开也就随之确定，往往不总能够达到好的稀疏表示效果，尤其 是对于时频变化范围很广的信号，效果更差。一种更好的信号分解方式应该是根 掘信号的特点，自适应地选择合适的基函数，来完成信号的分解。 如何得到信号的稀疏表示，近十几年来受到人们的广泛关注和研究，并已经 在某些领域得到应用。关于信号稀疏表示的研究应用最早可以追溯到统计学领域 中搜索最优回归的问题。在数据压缩领域中，信号的稀疏表示意味着信号可以表 示为很少的几项叠加，也就是说可以用很少的数据来表征个输出信号，得到压 缩的目的。目前这类方法已经在图像压缩 7 、视频压缩 4 3 、音频 4 4 和心电 图( e c g ) 信号压缩 4 5 等领域得到成功的应用。 在模式识别领域，信号的识别分两个步骤完成：第一步是特征提取，第二步 是识别。而通过信号的稀疏表示，可以将信号的特征有效地从大量数据中提炼出 来，这样可以提高第二阶段使用支持向量机( s u p p e rv e c t o rm a c h i n e ， s v m ) 南京邮电学院硕f 研究生学位论文第一章绪论 或神经网络进行识别的性能 4 6 4 7 。稀疏表示在视觉模式识别中的应用具体有 轮廓识别 4 8 3 ，人脸识别 8 等。 特别值得注意的是，近年来对灵长类动物的视觉研究表明，视觉皮层对负责 刺激的表达是采用稀疏表示原则的 9 。实验证明，皮层v 1 区的简单细胞检测的 是细胞感受某一特定位置上的方位信息，比起从外侧膝状体( l g n ) 传输过来时信 息得到进步的加工和提炼，且在视网膜和l g n 内的神经节细胞数远远小于皮 层v l 区第四层的细胞数。因此v 1 区细胞对l g n 细胞发放输出信息的特征表达存 在超定性质，它的编码表达空间的维数大于其输入空间的维数。这说明使用超完 备基稀疏表示是神经信息群体分布式表达的种有效策略 4 9 。 此外，信号的稀疏表示也应用于其他一些领域如自动控制 1 0 、地震数据的 处理【1 1 、系统识别 1 2 、股市分析 1 3 1 4 、盲信号分离等。 信号稀疏表示的算法研究主要从以下两条路进行：一条是基于统计学的研究 方法，主要代表是独立分量( i n d e p e n d e n tc o m p o n e n ta n a l y s i s ) 分析；另一条 是基于组合优化的研究方法，以匹配追踪( m a t c h i n gp u r s u i t ) 算法为代表。 为了提高匹配追踪算法的效率和精度，出现了很多改进的匹配追踪算法，主 要有币交匹配追踪算法( o m p - - o r t h o g o n a lm a t c h i n gp u r s u i t ) 1 2 2 8 2 1 、高 分辨率匹配追踪算法( h i g hr e s o l u t i o nm p ) 3 0 、竞争匹配追踪算法( c o m p e t e m p ) 1 6 和其他一些算法 3 1 3 2 3 3 等。所有这些算法将求解最优逼近式问题 转换为按照各自的准则或代价函数来求解满足式( 1 1 ) 的信号分解式的问题。 本论文在详细介绍匹配追踪算法及其改进算法的基础上，研究匹配追踪算法 在图像压缩中的应用，并提出了改进算法，仿真结果证明，这种改进能一定程度 上提高图像稀疏表示后的重建效果；研究字典的训练方法，并提出了改进的方法， 仿真结果证明，这种改进可以在一定程度上提高字典的训练效率。 本论文的安排如下：第一章，绪论，简单介绍信号的加法模型，稀疏表示及 其应用：第二章，详细分析匹配追踪算法的核心思想，收敛性及缺点；第三章， 介绍从不同方面着手对匹配追踪算法的改进；第四章，讨论有关匹配追踪算法中 字典的若干问题：第五章，介绍匹配追踪算法在图像压缩中的应用及算法改进， 并给出了仿真结果；第六章，提出改进的字典训练方法，并给出了仿真结果。最 后，是结束语、致谢、参考文献等。 南京船1 乜学院倾f 硎。究生学位论史 第一章匹配追踪算法的相关理论皋础 第二章匹配追踪算法的相关理论基础 匹配追踪算法最早由g , d a v i s ，s m a l l a t ，z z h a n g 等人提出，它的出现带给 了人们一种新的信号表示手段一抛开传统的基于完备正交变换的信号表示模 型，代之以分析综合的思维方式，用组合优化的方法来得到信号的稀疏表示。 近几年柬，这个领域发展迅速，改进算法不断涌现，具有各釉背景的匹配问题不 断进行探讨。 简单地讲，使用匹配追踪算法对信号进行稀疏表示，就是从一组超完备的向 量( 这里称为字典) 中选取恰当的几个，用它们的线性加权来逼近目的信号。因为 有更多的向量可选( 相对于完备j 下交基) ，所以就有机会用尽量少的向量的线性组 合来很好的逼近目的信号。一般，这罩要求字典是已知的，而且超完备( 向量的 个数多于空间的维数) 。对于有限维空间，任何可以张成空间的超完备的向量集 合，称之为“框架” 1 5 5 3 。 因为字典中的向量是线性相关的，所以信号的展开式不再是唯一的，在压缩 应用中，就要求使得展开式中非零的系数尽量地少。但前人已经证明找到全局最 优的向量组合，是一个n p ( 非多项式难度) 问题，解决的代价非常巨大。因此 有关超完备字典信号表示的研究重点就是研究如何从字典中挑选出合适的向量 来表示信号。 2 1 最优逼近与匹配追踪算法 绪论中的模型( 1 1 ) 也可写成矩阵形式 f = 1 ) s = 聃 ( 2 1 ) i 其中f = ( z ，五，厶) 7 是观测信号，d 是已知或未知的矩阵，包含分解信号的基 向量。若d 已知，则式( 2 ，1 ) 是不带参数的分解；若d 未知，则式( 2 1 ) 为带参数的 分解。s = ( 5 ，s 2 ，) 7 1 为分解系数。 在使用式( 2 1 ) 的模型时，稀疏表示的研究主要沿着这样两条路径进行f 3 4 】： 南京邮咀学院倾1 研究生学位论文 第二章匹月l 追踪算法的相关理论摧础 一条是以独立分量分析( i n d e p e n d e n tc o m p o n e n ta n a l y s i s ) 为代表的基于统计学的 研究方法：另一条则是以匹配追踪算法( m a t c h i n gp u r s u i t ) 为代表的基于组合优化 的研究方法。 沿着后一种路径的研究最早可以追溯到小波领域中的最优正交基( b e s t o r t h o g o n a lb a s i s ) 选择 4 7 1 ，而匹配追踪算法的提出才真f 推动了组合优化思想 的发展。 设字典为d ，需要用m 项来表示信号厂，基于组合优化的方法求信号稀疏 表示的目标则是在字典d 中选出一个包含m 个向量的子集g = g 。，g 。) ，使 得在同样使用m 项来逼近信号的情况下误差信号最小，即 m 一1 1 1 2 ( s ，g ) = a r gc ；恕，0 卜善0 乳5 川 q 2 1 c ，) ，r ”j = 满足式( 2 2 ) 的逼近式称为信号厂的历项最优逼近式。gd a v i s 在文献中证 明寻找能量有限信号的脚项最优逼近式问题是p 难度问题 1 7 。这说明，如果 是直接根据( 2 2 ) 式来求解信号的胛项最优逼近式的代价十分巨大以至于几乎不 可能实现。因此有关超完备字典信号表示的研究重点就是研究如何从字典中挑选 合适的向量来表示信号。这些算法虽然只能搜索到次最优的逼近式，但搜索所花 费的时间不再随字典中向量个数的增加呈指数形式增加。 当前使用超完备字典求解信号分解式的算法大致可分为两大类：一类是并行 选择算法，如基于小波包或余弦包 3 6 的最优j 下交算法 4 7 、f o c u s s ( f o c a l u n d e r d e t e r m i n e ds y s t e ms o l v e r ) 算法 3 7 4 9 以及基追踪算法( b a s i sp u r s u i t ) 1 2 等等。另一类是顺序选择算法，主要是匹配追踪算法( m a t c h i n gp u r s u i t ) 2 8 及其 一些变体，所有这些算法将求解最有逼近式问题转换为按照各自的准则或代价函 数柬求解满足式( 2 1 ) 的信号分解式的问题。 这些方法都有各自的优点和缺点。例如，最优正交基算法在某些情况下能给 出近似于最优的稀疏表示式，但如果信号是由一些非正交的分量构成的，使用此 算法反而得不到稀疏的表示式。另外，由于这种算法对字典的构成有特殊的要求， 以至于无法使用一些性能好的词典。使用f o c u s s 算法或基追踪算法分解信号 所得到的分解式系数比较稀疏，效果较好。而且，d l d o n o h o 和x h u o 已经证 明，当信号是由足够稀疏的时间或频率向量构成时，使用基追踪算法分解信号得 4 南京邮l u 学院坝i 。 i f 究生学位论文笫章旺虬追踪算法的相关理论枯础 到的分解系数与满足式( 2 2 ) 的1 7 1 项最有逼近式的分解系数相同。但这两种算法 计算量太庞大了，许多工程领域中无法应用，s m a l l a i 和z z h a n g 提出了匹配追 踪算法，将求肺项最优逼近式的问题通过迭代的贪婪算法( g r e e d ya l g o r i t h m ) ，化 简为求用个单项最优逼近式的问题。这种近似方法得到的系数虽然不及基追踪算 法和f o c u s s 算法稀疏，但效果接近，更可贵的是计算复杂度大大降低。因此， 匹配追踪算法是求解项最优逼近式问题的一个很好的折衷方案。正是由于这个 原因，该算法才得以应用在多个工程领域 7 8 9 3 8 4 8 。 2 2 匹配追踪算法的基本原理 匹配追踪算法的核心是迭代的贪婪算法。 设在有限维h i l b e r t 空间h 中，d 为此空间的超完各字典，设，首先 按照某种规则选定了个向量g 。d ，则可将 厂分解成沿着g 。方向的分量和与 它垂直方向的分量的迭加： 厂= g h + 足厂 ( 2 3 ) 其中可是分解后的余项，由勾股定理可知： 2 = i 1 2 + l l 可1 1 2 ( 2 4 ) 为了使j i 彤0 达到最小，应该选取，使得i j 尽可能大，即 l 卜辈l f ( 2 5 ) 这样得到分解式( 2 3 ) 。匹配追踪使用迭代算法，对于余项足厂同样在字典d 中 找出与之最匹配的向量乳，进行同样的分解。记矗o = f ，假设已经计算出第胛 次分解后的残余信号r “厂，按照上述步骤选取与只”厂最匹配的基向量邑ed ， 它满足 l i = s u 到 l ( 2 6 ) ，e 于是残余信号r “f 被分解为 尺”，= g ，l + r 肿1 厂 ( 2 7 ) 南京邮也学院倾_ - 研究生学位论文 第一章匹配追踪算法的相关理论茄础 尺”_ 厂与r ”厂的能量关系同样满足 忖硎2 = l 1 硎2 ( 2 8 ) 重复上述的分解过程，直到分解的项数达到预先设定值，或者余项的能量小于预 先设定的值才停止迭代。经过7 次迭代，信号厂被分解为 = g 。+ r ”， ( 2 9 ) 而且尽管访。；t = o ，1 ，m 一1 未必两两正交，但是其系数仍然遵循能量守恒的性 质： l l 厂1 1 2 = 篆1 1 2 + o r ”，1 1 2 ( 2 1 。) 如果在第所步停止计算，并且记录下来二元序列 ( 吼，_ y + ) ；= o ，1 ，州一1 ) ，就可 以出( 2 9 ) 式恢复出的近似值，其逼近误差为r ”f 。 2 3 匹配追踪算法的余项能量收敛性 式( 2 1 0 ) 给出了信号的逼近形式。l k j o n e s 在文献 5 2 】中证明了对任意 厂h ，误差能量收敛到零，即 因此有 能量 l i m r “列= 0 ，= g h 2 = 妻 1 2 ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 在无限维空间中，误差的收敛率一般相当慢，而在有限维空间中，可以证明 误差呈指数收敛 1 7 。这收敛性是匹配追踪算法应用的基础和保证。 南京邮i u 学院倾 研究生学位论文 笫一章匹目l 追踪算法的相关理论桀础 2 4 匹配追踪算法的缺点 应用匹配追踪算法得到信号的稀疏表示，能够得到比较好的应用。但这种方 法也存在一些缺点； 最主要的问题是计算量过于庞大。从上面的介绍中不难看出，在对信号的每 一步分解中，都需要进行大量的内积运算，以决定应该选出字典中的哪一个向量 来做分解。假设在维h i l b e r t 空间中，字典d 包含吖个基向量，每次内积计算 需要做次乘法及- j 次加法，完成一次分解则需要进行m n 次乘法和m 伊 次加法，如果要得到一个尸项的分解式则需要p m n 次乘法和p m ( n - i ) 次加法。 而在使用匹配追踪算法的场合。为了追求较高的性能。字典的规模通常取得比较 大，这样使得匹配追踪算法在应用中计算代价很大。这样巨大的计算量严重限制 了匹配追踪算法在许多领域里的应用。如何降低匹配追踪算法的计算复杂度，是 匹配追踪算法研究领域的一个热点，有许多学者在这方面做了很多工作，提出了 许多快速算法，取得了很大的进展。 在信号表示精度方面，由于匹配追踪算法中所用的字典中的向量不要求相互 正交( 线性无关) ，这样在使用匹配追踪算法进行信号分解后，残余信号中会包含 一些已经选择出的向量的分量，如果能够消除这些分量，就能够进一步提高匹配 追踪算法表示信号的精度。此外由于匹配追踪算法使用的是贪婪算法，在每一步 迭代都尽量捕捉信号的能量，在大多数情况下，它的性能还不错，但是由于贪婪 算法的“短视”，当信号中包含“成对结构”的分量时，又或者在其他特定场合 下，这时匹配追踪算法的性能就会有较大程度的下降，一般不能得到信号的稀疏 表示。因此，如何提高匹配追踪算法信号表示的精度也是匹配追踪算法研究的一 个重要问题。 在字典的选用和设计方面，由于珏配追踪算法的性能直接受制于字典向量与 所要表示信号的相关程度，因此，如果可以设计出与所表示信号相关程度很高的 字典，就可以用更少的向量来逼近目的信号，得到较高的表示精度和付出较少的 计算代价。如何构建这样的字典，便成为匹配追踪算法研究的另一个重要问题。 南京邮电学院硕 ：研究生学位论文第一二章匹配追踪算法的相关理论基础 2 5 本章小结 在本章，介绍了有关匹配追踪算法的理论基础，优势以及缺点等。在第三章 中，将从减少计算量，改变搜索策略等几个方面讨论对匹配追踪算法的改进。 8 南京f 蚶叱学院埘f j 研究生学位论空第= 章几种改进的匹削追踪算法 第三章几种改进的匹配追踪算法 匹配追踪算法能通过简单的迭代计算有效地找出信号的分解式，从而得到信 号的稀疏表示，现已成功应用于时频表示、视频压缩等领域。但巨大的计算量却 严重阻碍了这有效方法的进一步应用，尤其是对算法计算效率要求严格的场 合，针对这一问题许多学者提出了对匹配追踪算法的改进版本，取得了很好的成 果。 由于匹配追踪算法中所用的字典中的向量不要求相互正交( 向量线性 己关) 这样在使用匹配追踪算法进行信号分解后，残余信号中会包含一些已经选择出的 向量的分量，通过一定的算法，可以消除这些分量，进一步提高逼近效果。 出于匹配追踪算法每次迭代都使用“贪婪”原则，简单的通过比较信号与字 典向量的内积大小来找出这一步的最优向量，这种“短视”的作法有时会得不到 最佳的效果。如何减小这种情况的发生，也是一项很有意义的工作。 本章将从减少计算量、改变搜索策略等几个方面出发，讨论对匹配追踪算法 的改进。 3 1 从内积计算上对匹配追踪算法的改迸 从快速算法减少内积运算的方式来看，匹配追踪算法基本上可以分为两大 类：第一类方法是通过改变搜索策略，以达到减少内积运算次数的目的，如 m b a n h a m 在文献 5 0 中提出的用于视频压缩的分层匹配追踪算法，j b y e u n g w o o 和o s e o k b y e u n g 在文献 1 8 1 9 提出的适用于图像压缩或视频压缩的快速算法 等。第二类方法是通过增加存储空间或使用特殊设计的字典来达到减少单次内 积的运算量的目的。 3 1 1 基于减少单次内积的运算量的- 映速算法 这类方法大致可以分为两类。一种算法通过修改匹配追踪算法所使用的字典 来达到减少单次内积运算量的目的。例如，文献 4 6 5 1 提到通过选择字典里的 9 南京邮【乜学院倾i 研究生学位论史第三章几种改进的匹6 l 追踪算泣 向量，使这些向量在满足应用要求的前提下包含尽可能多的0 ，这样自然就能减 少计算内积值时候的运算量。文献 4 0 4 1 5 1 中提出了构造树结构的字典来减 少运算量。一般字典旱的向量之间是没有关系的，而如果可以构造出带有树结构 的字典来，那么信号与字典里的些向量作内积得到的结果，能在计算信号与字 典旱其他向量内积时被使用，从而减少一部分的运算。 通过采用特殊字典的匹配追踪算法，可以有效地减少单次内积计算时的运算 量。但由于对字典的这些特殊要求，使得对字典向量的选择比较严格，增加了构 造字典的难度。同时由于对字典向量的诸多限制，使得一些性能优秀的字典不一 定能满足这类算法的要求。 另一种减少单次内积运算量的快速算法，由s m a l l a t 和z z h a n g 在文献 2 8 中首次提出。它巧妙地利用了前一步内积计算的结果，来进行后面的计算，从而 减少计算量。 假设匹配追踪算法已经迭代到第n 步，在这一步迭代中，已经计算了所有的 内积值 ( g d ) ，这时可以从字典d 中选出最优向量g 。为求出下一 步迭代的最优向量既同样需要计算内积值 ( ge d ) 。由式子( 2 7 ) 可以直接得到 = 一 ( 3 1 ) 由于 ( g ，d ) 已经在上一步迭代中计算出来，那么计算 ( 毋d ) ，只需要计算 。而在实际应用中一般字典旦确 定就不再更改。因此可以将h = ( ) 。吐2 。事先计算好并保存下来。这样 对于在维h i l b e r t 空间中包含m 个向量的字典d ，除了第一步迭代过程中的内 积运算外，计算一次内积仅需要1 次乘法和1 次加法，完成一次分解则仅仅需要 m 次乘法和m 次加法。这比原始的匹配追踪算法分解一次所需要的计算量降低 了很多。 这种快速算法从本质上说，是一种以增加存储空间来减少计算复杂度的方 法。不过这种算法也有很大的局限性。首先在第一次迭代中， ( g ，d ) 只 能直接计算出来，这一步的计算量仍然很大，尤其是在某些对实时性要求很高的 o 南京邮i b 学院硕i + 研究生学位论史第三章几种改进的匹配追踪算法 场合仍然无法接受。如果要得到个p 项的分解式则需要( p 一1 ) n + m n 次乘法 和( p 一1 ) m + m ( n 1 ) 次加法。 其次，当字典规模很大时，矩阵h 所需要的存储空间将十分庞大，总共需要 存储m ( m 一1 ) 2 个内积值。不过，在实际应用中，字典中的大多数向量是由 些基本向量经过平移构成的，只有少数向量相互直接的内积值不为0 ，这种情况 下所需要的存储空间也还可以接受了。 3 1 2 基于减少内积运算次数的快速算法 m b a n h a m 在文献 5 0 中提出的使用分层搜索快速算法可以应用于视频压缩 领域中，提高匹配追踪算法运算速度。这种算法把匹配追踪算法的计算分成两个 阶段进行，其关键的地方就是对各个阶段字典的定义。首先需要定义一个字典 g = ( ) 。，它可咀是原来字典d 的子集，也可以不是，但都要求字典g 中向 量的个数m 要远远少于字典d 中向量的个数m 。同时，需要构造出若干规模较 小的子字典见= ( 毋) 心。d ，这些字典分别对应于字典g 中的各个向量。这 样匹配追踪算法中每一个匹配搜索过程都转变为两步匹配的过程。即，先在字典 g 中找到与信号f 最匹配的向量k i 卜翟l l = 麓l l 3 - 3 设系列字典( 见) 。中向量的平均个数为m ：，要使用匹配追踪算法得到一个p 项的分解式则需要p ( m 。+ ) 次乘法以及p ( m l + 鸩) ( 一1 ) 次加法。当 m 。+ m ：远远小于m 时，分层匹配追踪算法能够极有效地降低匹配追踪算法的 计算复杂度。 不过分层的匹配追踪算法的主要缺点是，这个方法的第二阶段所需要的字典 南京邮i u 学院坝i l j | _ 究生学位论史 第二章几种改进的蛆酊追踪算法 ( b ) 。中的向量不容易选择，一般情况下采用较为近似的选择方法。这种近似 的方法虽然不是最优的，但却容易定义。这时候，使用分层匹配追踪算法每一步 迭代搜索到的向量既并不一定与直接使用匹配追踪算法搜索到的向量相同。 从已知的实际效果来看，分层的匹配追踪算法一般会降低匹配追踪算法的信 号表示精度。 3 2 正交匹配追踪算法 假设按照匹配追踪算法在某一步迭代中选择除了向量占。在一般情况下由 于向量g h 不会与已经选择出来的向量( g 。) 。相正交，这样在残余信号尺，中 减去g h 的分量后，新的残余信号又将引入( 既) 。；。的分量。为了消除这些分量， sm a l l a t 在文献1 2 8 】中提出了在匹配追踪算法后使用共轭梯度算法来分解残余信 号，而目前更多的学者倾向于使用正交匹配追踪算法来分解信号，并提出了一些 正交匹配追踪算法的快速算法 2 0 1 1 2 1 1 1 2 2 1 。另外文献【5 还提出了一种投影分解 算法。 使用共轭梯度算法来分解残余信号的主要思想是：将月f 中可由( g 。) 。+ 线 性迭加表示的部分通过使用共轭梯度法求解方程的方法分离出来，从而使得新的 残余信号不包含( 邑) 。的分量。 然而当空问维数较高时，使用匹配追踪算法来分解信号，就需要使用较多的 向量，这时方程的系数矩阵就会十分庞大，使用共轭梯度法来分解残余信号会变 得十分困难。而诈交的匹配追踪算法则更为常用。 3 2 1 正交匹配追踪算法的基本原理 求解最优逼近的问题可以用数学语言描述为：定义d = g ，g ：，g 。) 亡h ” 为字典，匹配追踪算法的目的就是要寻找一个有着最小m 的子集 d = 妇g g ，。 c d ，1 n ，2 ，m ，和相应的系数慨，口2 ，口。) 使得 南京邮电学院坝i 一卅究生学位论文第= 章几种改进的匹d l 追踪算法 如果表示 ( 口1 9 1 + 口2 9 q + + 口。g ) 一，1 1 - s ( 3 4 ) d = 【g ng n g r 。】。 ， ( 3 5 ) d = 【1 2 1 口2 d 。 7 ( 3 6 ) 厂= 口l g h + 口2 9 ，：+ + 口。g h = d 口 ( 3 7 ) 则( 3 4 ) 式可以写成| | 厂一州e 。 f 交匹配追踪算法的基本原理是通过使用g r a m s c h m i d t 程序，对选择出的 字典向量实施f 交化。这样虽然从字典中选择出来的向量不相互正交，但经过 g r a m s c h m i d t f 变化程序，这些向量就会相互f 交。这样在每一步分解信号时， 残余信号中就不会引入其他向量的分量了。由于每次迭代都使用正交基分解信 号，因此在分解的过程中，残余信号r ”，内也不会引入己选择向量的分量。 讵交匹配追踪算法具体如下： 算法3 - 1o m p 正交匹配追踪算法 输入： 维h i l b e r t 空间内信号厂，字典d = 昏；j f ) ，其中f = 1 , 2 ，m ， 迭代次数m ，逼近误差s 输出： 系数a = 陋lt 2 2 口。】7 和索引7 = ，y ：，】7 1 初始化：k = 1 ，可= ， 2 f o rk = 1t omf 3 w h i l ei l 最厂l p 占 4 f o ra l l i f 5 - c f - 南小r f ，护i ) 6 寻找心，使得c r k2 吧笋c f 7 f o ra l ir 已经选出的向量下标集合7f 南京邮1 u 学院坝i j 研究生学位论文 第兰章几种改进的匹配追踪算法 8 g “2g “一 木g 9 1 0 1 1 1 既2 研巩 c 唯2 矽= r f c 卑g 3 2 3 正交匹配追踪算法与匹配追踪算法在残余量收敛方面的比较 上面一节提到的f 交匹配追踪算法，通过g r a m s c h m i d t 过程，实现了消除 残余信号中已选向量分量的目的。 让我们先回顾匹配追踪算法。 d = g ， 是h i l b e r t 空间内组给定的向量集合，定义v 为d 中向量张成的空 削，w 为v 的f 交补空问，即 v = s p a n g r ) ( 3 8 ) w = v 1 ( i nh ) ( 3 9 ) 这罩的d 也就是前面我们讲的字典，假设向量毋已经单位化( 0 毋0 = 1 ) 。匹配追 踪算法可以表示成如下信号重构形式： p v f = 。t r g r ( 3 1 0 ) r e r 其中p v 是对v 空间的正交投影算子。这样，假设匹配追踪算法进行到第k 步迭 代，则有 女 厂= 掰，g + 胄，= 五+ f ( 3 1 1 ) 假如我们取【1 1 个向量进行逼近，则 南京邮电学院顿1 研究生学位论文第三章几种改进的匹配追踪算法 = g 。 ( 3 1 2 ) 类似上面定义的v 空间，我们定义k = s p a n g r , ，g ，g h a 如果有厶= p “厂， 则称厶为一个最优项逼近，也就是说厶是用从字典d 中选出的向量子集 培g ，g 。) 构建出的最优逼近( 值得注意的是，这里不涉及如何选择出这个 最优子集的问题) 。这样，厶是一个最优项逼近，当且仅当月”f ev ：。而前 面的匹配追踪算法只能得到r ”f 上g 。，所以由第二章提到的匹配追踪算法得到 的 只能是次优的。也f 因为是这样，每步迭代产生的残余信号能量虽可以 保证收敛，当收敛速度会比较慢。这里重复文献目的作者举的一个简单例子，形 象地说明这一缺点。 蜀和g ：是二维实空间内两个向量，f 也是二维空间内一个信号，如图3 - 2 - 1 ( a ) 所示。图3 2 一l ( b ) 示出了忙卅随着k 增加的变化曲线，也就是残余信号能量的 收敛曲线。 7 泛 j ， 国 、，枣： 乡丽! g 。 ： 一： j j j j 、， j 、 、 ， 7 一。 一，p _ 4 ， c a ) 南京艄l 也学院坝l 训究生学位论文 第二带几种改进豹匹醚追踪算珐 ( b ) 图3 2 1 二维空间内的匹配追踪算法例子 从这个例子中，我们不难看出，残余信号能量确实能够收敛，但在有限步迭 代之后，能量仍然比较大。如果能够使匹配追踪算法每一步都能满足r ，v ， 则可以使每一步迭代的残余信号能量都尽可能小，达到更好的逼近性能。而这正 是前文提出的f 交匹配追踪算法的思想。 为了和非f 交的匹配追踪算法作对比，我们重做图3 2 1 中的例子，只是这 挈采用陋交匹配追踪算法来进行。图3 2 2 给出了两种不同方法的残余信号能量 衰减状况。图中的星号为采用非f 交匹配追踪算法得到的残余信号能量衰减曲 线，实现为采用j 下交匹配追踪算法得到的残余信号能量衰减曲线。很明显，采用 正交的匹配追踪算法，可以使得残余信号能量迅速较小。 迭代状披n 图3 - 2 - 2 正交匹配追踪算法和非正交匹配追踪算法对比 1 6 蝴蝼荦，目1 南京邮 乜学院碗上研究生学位论文第三章几种改进的匹d d 追踪算法 3 3 竞争匹配追踪算法 胁面讨论的匹配追踪算法以迭代方式分解信号，并且每一步迭代时都采用贪 婪算法寻找能使信号能量下降最快的向量。与其他在超完备基中找出信号的稀疏 表达式的算法相比，匹配追踪算法计算复杂度比较小，而且在各种正交匹配追踪 算法及其快速算法提出后，其性能更优。但是正由于匹配追踪算法采用的贪婪算 法，它找到的分解向量，只是单步最优的。这样，当某些特定场合，比如信号中 含有对称结构的分量时，它就无法分辩出这些分量。这时使用匹配追踪算法来分 析此信号就无法得到该信号的稀疏表示了。 文献 1 6 的作者举了一个对双峰函数进行逼近的例子。如图3 - 3 1 所示 在这个例子中，匹配追踪算法完全没有能分辩出这个对称结构，而且由于第 一次的错误，使得原先特征明显的信号变得混乱，使得后面需要额外付出许多项 来纠f 这个错误。对于其他类似的有对称结构的信号，匹配追踪算法都有这个缺 点。 要解决这类问题，就必须使得匹配追踪算法能“看”得更远一些。 南京帅l u 学院顺l 。究生学位论奠第_ 三章几种改进的匹配追踪算法 图3 - 3 1 匹配追踪算法处理双峰函数的过程 ( a ) 双峰函数以及由匹配追踪算法选择出的第一个基向量 ( b ) 经过一次匹配追踪后的残余信号 文献 1 6 提出，通过将匹配追踪算法在每次迭代中所求解的单项最优逼近 式，提高到求解二项最优逼近式，并取得了较好的分解效果。 3 3 1 竞争匹配追踪算法基本原理 竞争匹配追踪算法与匹配追踪算法基本类似，不同的是竞争匹配追踪算法在 每一步迭代时不仅尝试在信号内积最大的向量方向上分解，同时也尝试在信号内 积次最大的向量方向上分解，通过比较残余信号能量的大小从而确定用哪一个向 量分解。以下具体介绍竞争匹配追踪算法的步骤。 第步计算出信号，与字典d 中所有向量的内积，与匹配追踪算法不同的 是，挑选出与信号内积最大的和次最大的两个向量，设为“和怯，上标表示此 向量是在第几次迭代中选择出来的。 l 窖 南京n 学院硕j ：研究生学位论文第三章几种改进的匹配追踪算法 w l = a r g 罂a x l f e d ，毋) 1m w 2 i = a r g 。，璺嚣以i i 按照这两个方向分别对信号厂进行分解，相应得到两个残余信号r f 乖l 趟， r ：s = f 一 州 尺! = 厂一 i 第二步，对于r ：s 同样从字典d 中选择两个与之内积最大的和次大的向量 嵋和吨，并分别按这两个方向对叫，进行分解。按照同样的方法选择出向量k 2 ， 和心2 ：以分别对尺；厂进行分解。这样共可以得到4 个残余信号，分别是r , l f ， r i 厂，霹厂和砭，。 第三步，计算出这4 个残余信号的能量，并且选出能量最小的和次最小的残 余信号，分别将它们赋值给e 2 s 和霹厂。同样将与这两个残余信号相对应的向 量分别赋值为衍和谚。在以后的迭代分解中，只使用这两个残余信号，而不再 考虑另外两个残余信号了。 第四步，若是信号的分解已经满足要求，则分解结束。否则，重新回到第 二步继续分解。 除了第一步之外，整个竞争匹配追踪算法实际上是分两路做匹配追踪，因 此将上述算法又称为双分支竞争匹配追踪算法。该算法的计算量基本上是匹配追 踪算法的两倍。 很容易将双分支竞争匹配追踪算法扩展为多分支竞争匹配追踪算法，从而得 到竞争匹配追踪算法的一般算法。具体算法流程由于篇幅所限，不再赘述。 有一点需要指出，n 分支竞争匹配追踪算法的计算量是匹配追踪算法计算量 的 倍。实际上匹配追踪算法可以看作是, 1 1 分支竞争匹配追踪算法在”= l 时的 情况。 1 9 南京幛电学院颂卜研究生学位论史第三章几种改进的匹配追踪算法 3 3 2 竞争匹配追踪算法与匹配追踪算法的比较 图3 3 2 ( a ) 双峰函数及由双分支竞争匹配追踪算法选择出的前两个向量 ( b ) 双峰函数及由四分支竞争匹配追踪算法选择出的前两个向量 图3 3 2 显示出了在信号含有对称结构时，竞争匹配追踪算法所选择出的向 量。其中，图3 3 2 ( a ) 中的实线是由双分支竞争匹配追踪算法得到的，图3 3 2 ( b ) 则是采用四分支竞争匹配追踪算法得到的。对比图3 - 3 1 ，可以看出竞争匹配追 踪算法的优点。当采用双分支时，可以基本分辨出此信号的结构，当不够准确； 而当迸一步增加分支数，在采用四分支时，基本上可以正确地将图中虚线所示的 双峰函数结构分辨出来了。 文献 1 6 给出的算法性能比较也得出了这样的结论，即采用多分支的竞争匹 配追踪算法，可以提到匹配追踪算法的精度。但这是用高出数倍的计算量换取的。 南京邮i u 学院坝l ：t 0 f g 生学位论义第三章几种改进的匹配追踪算 上 3 4 基于匹配追踪算法的数据压缩算法框架 在前面对匹配追踪算法理论研究的基础上，下面就匹配追踪算法在图像信号 的数据压缩方面应用进行论述。 基于匹配追踪算法的数据压缩技术，虽然有其特点，但它仍然属于变换编码 的范畴，因此其实现框架和其他基于正交变换的数据压缩方法( 如d c t 、d w t ) 类似。图3 - 4 1 给出了其实现框架。 再 图3 - 4 - 1 匹配追踪算法数据压缩框架图 这罩假设输入数据是经过预处理的离散值，然后经过分帧，以帧为单位进行 处理和压缩。如图所示，第i 帧置输入后，运用匹配追踪算法( f 交的或非证交 的) 对信号进行逼近，当满足逼近准则( 如小于逼近误差或达到最大可选向量个 数) 后，就可以用一系列的字典向量下标和相应的系数来表示输入信号x 。之后， 对输出的系数进行量化，然后经过熵编码输出。因为对信号的处理是分帧的，为 了区分不同帧的输出，还需要在每帧数据后加上特定的标记符，并记录下选用的 向量个数。接受方则依靠标记符来区分数据并恢复信号。 需要指出的是，由于量化和熵编码部分在其他基于j 下交变换的数据压缩方法 中都有讨论和应用，因此在在本论文的后续实验中，为了突出重点，没有考虑量 化、熵编码和标记符部分。但必须指出的是，量化和熵编码部