（信号与信息处理专业论文）基于匹配追踪算法的心电图和语音信号压缩技术研究.pdf

南京邮电学院硕士论文 摘要 信号的稀疏表示在信号处理领域有着重要的意义，如何得到信号的稀疏表示 以利于后续的压缩、去噪、分析等应用，一直是人们关注和研究的热点。近年来， 以迭代的贪婪算法为核心的匹配追踪算法，作为一种有效的信号稀疏表示方法， 受到越来越多学者的重视，并出现了许多工程应用。 本论文围绕着匹配追踪算法，对它的一些核心问题进行了论述，并对其在心 电图信号和语音信号压缩方面的应用进行了研究。 全文共分五个部分。第一章，介绍信号的稀疏表示问题；第二章，介绍匹酝 追踪算法的基本原理：第三章，从不同角度介绍匹配追踪算法的一些改进算法； 第四章，着重讨论匹配追踪算法中的字典问题：最后一章，研究匹配追踪算法在 心电图和语音信号压缩方面的应用，然后结合信号的特点进行了算法改进，并鲐 出了仿真结果。 关键词：稀疏表示、框架、匹配追踪算法、心电图信号压缩、语音压缩 壹塞坚皇兰墼堡主堡塞 a b s t r a c t t h es p a r s e r e p r e s e n t a t i o np l a y sa ni m p o r t a n tr o l e i nt h e s 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 i n g ，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 s p u tt h e i ri n t e r e s t si n t 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 d s o m ee 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 ff i v ep a r t s i nt h ef i r s t p a r t ，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 dp a r t ，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 e t h i r dp a r t ，s o m ei m p r o v i n gv e r s i o n so f m a t c h i n gp u r s u i t a r ed i s c u s s e d t h ef o u r t hp a r ti sf o c u so nt h ed i c t i o n a r yu s i n gi nm a t c h i n gp u r s u i t a n di nt h el a s t p a r t ，e c g a n d s p e e c hc o m p r e s s i o n b a s e d m a t c h i n gp u r s u i t i s d i s c u s s e d ，a n d m o d i f i c a t i o n sb a s e do ns o m ec h a r a c t e r so ft h ee c gs i g n a l a r e p r e s e n t e d a n d d i s c u s s e d ，a n dt h er e s u l to f s 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 ，f r a m e ，m a t c h i n gp u r s u i t ，e c gc o m p r e s s i o n ， s p e e c hc o m p r e s s i o n 南京邮电学院学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电学院或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：皇盎日期：! 竺：! ! 南京邮电学院学位论文使用授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电学院研究生部办理。 研究生签名：导师签名： 日期 南京邮电学院碾士论文 第一章绪论 在信号处理和数据分析中，如何对信号进行表达，是一个很有意义的问题。 建立信号模型，常常是我们要做的第步。在信号的数学模型中，应用最 普遍、影响最深刻的。就是信号的加法模型 1 0 。用公式可以表示成 卫 厂( f ) = a 。g ，( f )( 1 1 ) i = 1 在这里，信号被分解成展开函数的线性组合，式( 1 1 ) 中的系数口和展开函数g 就 构成了信号模型。通常情况下，我们总是希望用尽可能简单的方式来描述现象， 对信号的表示同样如此。如果模型是紧凑的或者说“稀疏”的，那么这个分解就 显示出信号的基本特性，也就可以用于信号的分析、修正、去噪、压缩或者增强 等后续处理。值得注意的是，紧凑的模型也就意味着要求展开函数和信号有着高 的相关性 1 1 。 传统的信号表示方法基于“基”的展开，尤其是正交完备基，如f o u r i e r 函数或者小波函数等。这些基函数都有着较强的物理意义，而且对于某些特定类 型的信号能取得很好的表示效果。但当用这一类性质特定的基函数来表达任意信 号时，一旦基函数确定，对于一个信号的展开也就随之确定，往往不总能够达到 好的稀疏表示效果，尤其是对于时频变化范围很广的信号，效果更差。一种更好 的信号分解方式应该是根据信号的特点，自适应地选择合适的基函数，来完成信 号的分解。 如何得到信号的稀疏表示，近十几年来受到人们的广泛关注和研究，并已经 在某些领域得到应用。关于信号稀疏表示的研究应用最早可以追溯到统计学领域 中搜索最优回归的问题 i 2 1 3 1 4 。在数据压缩领域中，信号的稀疏表示意味 着信号可以分解为很少的几项叠加，也就是说可以用很少的系数来表征一个输出 信号，得到压缩的目的。目前这类方法已经在图像压缩r 1 5 、视频压缩 1 6 、音 频 1 7 和心电图( e c g ) 信号压缩 1 8 等领域得到成功的应用。 在模式识别领域，信号的识别分两个步骤完成：第一步是特征提取，第二步 是识别。而通过信号的稀疏表示，可以将信号的特征有效地从大量数据中提炼出 第1 页 南京邮电学院硬士论文 来，这样可以提高第二阶段使用支持向量机( s u p p e r v e c t o r m a c h i n e ， s v m ) 或神经网络进行识别的性能 1 9 2 0 。稀疏表示在视觉模式识别中的应用具体有 轮廓识别 2 1 】，人脸识剐 2 2 等。 特别值得注意的是，近年来对灵长类动物的视觉研究表明，视觉皮层对负责 刺激的表达是采用稀疏表示原则的 2 3 。实验证明，皮层v l 区的简单细胞检测 的是细胞感受野某一特定位置上的方位信息。比起从外侧膝状体( l g n ) 传输过来 时信息得到进一步的加工和提炼，且在视网膜和l g n 内的神经节细胞数远远小 于皮层v l 区第四层的细胞数。因此v 1 区细胞对l g n 细胞发放输出信息的特征表 达存在超定性质，它的编码表达空间的维数大于其输入空间的维数。这说明使用 超完备基稀疏表示是神经信息群体分布式表达的一种有效策略 2 4 。 此外，信号的稀疏表示也应用于其他一些领域如自动控制 2 5 、地震数据的 处理 2 6 、系统识别 2 7 、股市分析 2 8 2 9 、盲信号分离等。 信号稀疏表示的算法研究主要从以下两条路进行：一条是基于统计学的研究 方法，主要代表是独立分量( 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 r t h o g o n a lm a t c h i n gp u r s u i t ，o m p ) 2 7 5 0 3 8 、高 分辨率匹配追踪算法( h i g hr e s o l u t i o nm p ) 5 2 、竞争匹配追踪算法( c o m p e t e m p ) 3 2 和其他一些算法 5 3 5 4 5 5 等。这些方法的出现，大大提升了匹配追 踪算法的计算性能，从而为它在工程实践上的应用拓展了道路。因此，目前该方 法_ 已经出现在视频压缩、心电图压缩、模式识别等场合。 在匹配追踪算法的诸多应用领域中，本论文着重关心其在数据压缩方面的应 用。沦文在详细介绍匹配追踪算法及其改进算法的基础上，研究匹配追踪算法在 心电图( e c g ) 信号和语音信号压缩中的应用。 本沦文的安排如下：第一章，绪论，简单介绍信号的加法模型、稀疏表示等 概念介绍稀疏表示在信号处理中的重要意义。第二章，详细分析匹配追踪算法 的核心思想、收敛性及缺点。第三章，介绍从不同方面着手对匹配追踪算法的改 进，主要目的就是如何加快运算速度、减少运算量、提高计算精度。第四章，讨 论有关匹配追踪算法中字典的若干问题：首先讨论了最优字典的分布规律并给 第2 页 南京邮电学院硕士论文 出了可以得到近似最优字典的数值方法：然后给出了一种更为常用的g a b o r 时频 原子字典；晟后讨论了针对某类信号的基于矢量量化的字典训练方法。第五章， 介绍匹配追踪算法在心电图信号和语音信号压缩中的应用及算法改进，先简要介 绍了心电图信号和语音信号的特点；然后给出了使用匹配追踪算法进行信号压缩 的算法框架：之后通过一系列实验研究了实际应用中几个重要参数的意义和影 响，并给出了仿真结果。针对心电图信号中不同构成波组的重要性差异，提出了 区分精度的压缩方法，对重要波组信息采用高精度的压缩，而对于次要部分采用 较低精度的压缩。仿真结果证明，采用这种区分精度的方法，可以在一定程度牺 牲重构信号精度的前提下，有效提高压缩性能。最后，是结束语、致谢、参考文 献等。 第3 页 南京邮电学院硬士论文 第二章匹配追踪算法 匹配追踪算法最早由g d a v i s ，s , m a l l a t ，zz h a n g 等人提出，它的出现带给 人们一种新的信号表示手段一抛开传统的基于完备正交变换的信号表示模型， 代之以分析一综合的思维方式，用组合优化的方法来得到信号的稀疏表示。近几 年来，这个领域发展迅速，改进算法不断涌现，使得实际应用成为可能。 简单讲，使用匹配追踪算法对信号进行稀疏表示，就是从一组超完备的向量 ( 这里称为字典) 中选取恰当的几个，用它们的线性加权来逼近目的信号。因为有 更多的向量可选( 相对于完备正交基) 。所以就有机会用尽量少的向量的线性组合 来很好地逼近目的信号。一般，这里要求字典是已知的，而且超完备。对于有限 维空问，任何可以张成空问的超完备的向量集合，称之为“框架” 3 0 ，3 1 。 因为字典中的向量是线性相关的，所以信号的展开形式= = f = = 再是唯一的在压 缩应用中，就要求使得展开式中非零的系数尽量地少。但前人已经证明找到全局 最优的向量组合是一个n p ( 非多项式难度) 问题，解决的代价非常巨大。因此 有关超完备字典信号表示的研究重点就是研究如何从字典中挑选出合适的向量 来表示信号。 2 1 最优逼近与匹配追踪算法 绪沦中的模型( 1 1 ) 也可写成矩阵形式 f = d s = g ( 2 1 ) 其中f = ( ， ，厶) 7 是观测信号，d 是已知或未知的矩阵，包含分解信号的基 向量。若d 已知，则式( 1 2 ) 是不带参数的分解：若d 未知，则式( 1 2 ) 为带参数的 分解。s = ( 5 。，s ：，s 。) 7 为分解系数。 在使用( 2 1 ) 的模型下，稀疏表示的研究主要沿着这样俩条路径进行【5 6 1 ：一 条是以独立分量分析( 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 ) 为代表的基于组合优化的 薷4 页 角京邮屯学院砸士论文 研究方法。 沿着后一种路径的研究最早可以追溯n d , 波领域中的最优正交基fb e s t o r t h o g o n a lb a s i s ) 选择 2 0 】，而匹配追踪算法的提出才真正推动了组合优化思想 的发展。 设字典为d ，需要用m 项来表示信号，基于组合优化的方法求信号稀疏表 示的目标则是在字典d 中选出一个包含m 个向量的子集g = g ，d ，g 。) ，使得 在同样使用m 项来逼近信号的情况下误差信号最小，即 0m i1 1 2 。 g ) _ a r g 。盛卜荟g j s j 0 心2 ) 6 o ，强r ，- o 满足式( 2 2 ) 的逼近式称为信号，的m 项最优逼近式。gd a v i s 在文献中证明 寻找能量有限信号的项最优逼近式问题是n p 难度问题 3 4 。这说明，如果直 接根据( 2 2 ) 式来求解信号的口项最优逼近式，其代价十分巨大以至于几乎不可 能实现。因此有关超完备字典信号表示的研究重点就是研究如何从字典中挑选合 适的向量来表示信号。这些算法虽然只能搜索到次最优的逼近式。但搜索所花费 的时问不再随字典中向量个数的增加呈指数形式增加。 当前使用超完备字典求解信号分解式的算法大致可分为两大类：一类是并行 选择算法，如基于小波包或余弦包 5 8 的最优正交算法 2 0 、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 ) 算法 2 4 ，5 9 以及基追踪算法( b a s i sp u r s u i t ) 2 7 等等。另一类是顺序选择算法，主要是匹配追踪算法( m a t c h i n gp u r s u i t s ) 5 0 3 及其 一些变体，所有这些算法将求解晟优逼近式问题转换为按照各自的准则或代价函 数来求解满足式( 2 1 ) 的信号分解式的问题。 这些方法都有各自的优点和缺点。例如，最优正交基算法在某些情况下能给 出近似于最优的稀疏表示式，但如果信号是由一些非正交的分量构成的，使用此 算法反而得不到稀疏的表示式。另外，由于这种算法对字典的构成有特殊的要求， 以至于无法使用些性能好的字典。使用f o c u s s 算法或基追踪算法分解信号 所得到的分解式系数比较稀疏，效果较好。而且，dl d o n o h o 和x h u o 已经证 明，当信号是由足够稀疏的时间或频率向量构成时，使用基追踪算法分解信号得 到的分解系数与满足式( 2 2 ) 的埘项最优逼近式的分解系数相同。但这两种算法 的计算量太庞大了，以至于无法应用于很多工程领域。s m a l l a t 和z z h a n g 提出 第5 页 南京邮电学院硕上论文 了匹配追踪算法，将求m 项最优逼近式的问题通过迭代的贪婪算法( g r e e d v a l g o r i t h m ) ，化简为求1 1 7 个单项最优逼近式的问题。这种近似方法得到的系数虽 然不及基追踪算法和f o c u s s 算法稀疏，但效果接近，更可贵的是计算复杂度 大大降低。因此，匹配追踪算法是求解项最优逼近式问题的一个很好的折衷方 案。正是由于这个原因，该算法才得以席用在多个工程领域 1 5 2 1 2 2 2 3 6 1 。 2 2 匹配追踪算法的基本原理 匹配追踪算法的核心是迭代的贪婪算法。 设在有限维h i l b e r t 空问日中，d 为此空间的超完各字典，设厂h ，首先 按照某种规则选定了一个向量g 。d ，则可将厂分解成沿着g 。方向的分量和与 它垂直方向的分量的迭加： ，= f ，g h g h + r u ( 2 3 ) 其中月r 是分解后的余项，由勾股定理可知： 2 = f c 厂，g 。，酬2 ( 2 4 ) 为了使j | 缈 j 达到最小，应该选取民，使得j c ，g 。，j 尽可能大，即 1 c 厂，g 。爿2 洲c 厂，昌爿 ( 2 5 ) 这样得到分解式( 2 ，3 ) 。匹配追踪使用迭代算法，对于余项可同样在字典d 中 找出与之最匹配的向量g 。，进行同样的分解。记月o ，= 厂，假设已经计算出第” 次分解后的残余信号尺”，按照上述步骤选取与r ”，最匹配的基向量乳6 d ， 它满足 i c 尺”厂，g 。，l = 刊 g ， + r - * l f 啦- 1 1 第6 撕 南京邮电学院硕士沦文 r ”f 与r ”1 厂的能量关系同样满足 p 州2 = 1 c r ”厂帆，1 州2 ( 2 8 ) 重复上述的分解过程，壹到分解的项数达到预先设定值，或者余项的能量小于预 先设定的值才停止迭代。经过口次迭代，信号- r 被分解为 j r = r 厂g g h + r 厂 ( 2 9 ) 而且尽管k 。；t = 0 , 1 ，m 一1 未必两两正交，但是其系数仍然遵循能量守恒的性 质： 2 ：窆i cr ，既，l2 + i i r i l l 2 ( 2 1 0 ) 如果在第m 步停止计算，并且记录下二元序列娅。，；) ；= o , 1 ，m 一1 ，就可以 由( 2 9 ) 式恢复出厂的近似值，其逼近误差为r “，。 2 3 匹配追踪算法的余项能量收敛性 式( 2 1 0 ) 给出了信号，的逼近形式。l k j o n e s 在文献 3 3 中证明了对任意 f h ，误差能量收敛到零，即 因此有 能量 熙j l l = o 厂= 0 = 1 ，一，m ，被用来存放一些正的标量值，这相当 于内积值的量化值的集合。对信号，的量化过程是：先从形状码书c 。一中找出 与厂内积最大的向量吕，再在增益码书中选出一个值满足1 吼一f 7 吕l 。这两 种算法的不同之处在于匹配追踪算法每次迭代寻找的是内积绝对值最大的向量， 并可以做多次迭代；而形状增益矢量量化对每一个信号或分块信号只找出一个内 积值最大的向量。 实际上可以将匹配追踪算法的量化版本看作是形状增益矢量量化方法的 扩展，形状增益矢量量化方法也可以看作匹配追踪算法的一步迭代版本。 2 5 匹配追踪算法的缺点 应用匹配追踪算法得到信号的稀疏表示，可以有比较好的应用。但这种方 法也存在一些缺点； 最主要的问题是计算量过于庞大。从上面的介绍中不难看出，在对信号的 每一步分解中，都需要进行大量的内积运算，以决定应该选出字典中的哪一个向 量来做分解。假设在维h i l b e r t 空间中，字典d 包含m 个基向量，每次内私蚓+ 算需要做次乘法及- j 次加法，完成一次分解则需要进行m n 次乘法和m 伊 次加法，如果要得到一个尸项的分解式则需要p m n 次乘法和尸肼r u 次加法。 而在使用匹配追踪算法的场合，为了追求较高的性能，字典的规模通常取得比较 大，这样使得匹配追踪算法在应用中计算代价很大。这样巨大的计算量严霞限制 了匹配追踪算法在许多领域里的应用。如何降低匹配追踪算法的计算复杂度t 是 匹配追踪算法研究领域的一个热点，有许多学者在这方面做了很多_ t 作，提出了 许多快速算法，取得了很大进展。 羹8 丽 南京邮电学院砸士论文 在信号表示精度方面，由于匹配追踪算法中所用的字典中的向量不要求相 互正交( 线性无关) ，这样在使用匹配追踪算法进行信号分解后，残余信号中会包 含一些已经选择出的向量的分量，如果能够消除这些分量，就能进一步提高匹配 追踪算法表示信号的精度。此外由于匹配追踪算法使用的是贪婪算法，在每一步 迭代都尽量捕捉信号的能量，在大多数情况下，它的性能还不错，但是由于贪婪 算法的“短视”，当信号中包含“成对结构”的分量时，又或者在其他特定场合 下，这时匹配追踪算法的性能就会有较大程度的下降，一般不能得到信号的稀疏 表示。因此，如何提高匹配追踪算法信号表示的精度也是匹配追踪算法研究的一 个重要问题。 在字典的选用和设计方面，由于匹配追踪算法的性能直接受制于字典向量 与所要表示信号的相关程度，因此，如果可以设计出与所表示信号相关程度很高 的字典，就可以用更少的向量来逼近目的信号，付出较少的计算代价且得到较高 的表示精度。如何构建这样的字典，便成为匹配追踪算法研究的另一个重要问题。 在量化方面，t 程应用中对信号的表示必须经过量化，而在匹配追踪算法 巾，超完备向量空间的信号分解的量化问题要远远复杂丁完备正交基空间中的情 况。如何构建适合匹配追踪算法特点的量化器也是这一领域的一个研究重点。 在第三章中，将从减少计算量，改变搜索策略等几个方面讨论对匹配追踪 算法的改进。第四章，着重讨论匹配追踪算法的字典问题。第五章，讨论匹配追 踪算法在心电图信号和语音信号压缩中的应用。 第9 页 南京邮电学院硕士论文 第三章改进的匹配追踪算法 匹配追踪算法能通过简单的迭代计算有效地找出信号的分解式，从而得到信 号的稀疏表示，现己成功应用于时频表示、视频压缩等领域。但巨大的计算量却 严重阻碍了这一有效方法的进一步应用，尤其是对算法计算效率要求严格的场 合，针对这一问题许多学者提出了对匹配追踪算法的改进版本，取得了很好的成 果。 由于匹配追踪算法中所用的字典中的向量不要求相互正交( 向量线性相关) ， 这样在使用匹配追踪算法进行信号分解后，残余信号中会包含一些已经选择出的 向量的分量，通过一定的算法，可以消除这些分量，进一步提高逼近效果。 由于匹配追踪算法每次迭代都使用“贪婪”原则，简单地通过比较信号与字 典向量的内积大小来找出这一步的最优向量，这种“短视”的做法有时会得不到 最佳的效果。如何减小这种情况的发生，也是一项很有意义的工作。 本章将从减少计算量、改变搜索策略等几个方面讨论对匹配追踪算法的改 进。 3 1 从内积计算上对匹配追踪算法的改进 从快速算法减少内积运算的方式来看，匹配追踪算法基本上可以分为两大 类：第一类方法是通过改变搜索策略，以达到减少内积运算次数的目的，如 mb a n h a m 在文献 6 4 中提出的用于视频压缩的分层匹配追踪算法，j , b y e u n g w o o 和0 s e o k b y e u n g 在文献 3 5 3 6 提出的适用丁图像压缩或视频压缩的快速算法 等。第二类方法是通过增加存储空问或使用特殊设计的字典，来达到减少单次内 积的运算量的目的。 3 1 1 基于减少单次内积的运算量的快速算法 这类方法大致可以分为两类。一种算法通过修改匹配追踪算法所使用的字典 来达到减少单次内积运算量的目的。例如，文献 1 9 6 5 提到通过选择字典里的 向量，使这些向量在满足应用要求的前提下包俞尽可能多的欠这样自然就能减 1 钱 第1 0 页 南京邮电学院硕士论文 少计算内j ! ! = 值时候的运算量。文献 6 5 6 6 6 7 6 8 中提出了构造树结构的字典 来减少运算量。一般字典里的向量之间是没有关系的，而如果可以构造出带有树 结构的字典来，那么信号与字典里的一些r n 量作内积得到的结果，能在计算信号 与字典里其它向量内积时被使用，从而减少一部分的运算。 通过采用特殊字典的匹配追踪算法，可以有效地减少单次内积计算时的运算 量。但由于对字典的这些特殊要求，使得对字典向量的选择比较严格，增加了构 造字典的难度。同时由于肘字典向量的诸多限制，使得一些性能优秀的字典不一 定能满足这类算法的要求。 另一种减少单次内秘运算量的快速算法，由s m a l l a t 和z z h a n g 在文献 5 0 中首次提出。它巧妙地利用了前步内积计算的结果，来进行后面的计算，从而 减少计算量。 假设匹配追踪算法已经迭代到第n 步，在这一步迭代中，已经计算了所有的 内秘值 ( 3 1 ) 由于 ( 毋d ) 已经在上一步迭代r r 计算出来，那么计算 ( 昌5 d ) ，只需要计算黾，毋。而在实际应用中一般字典旦确 定就不再更改。因此可以将h = ( 昌，毋lh ：事先计算好并保存下来。这样 对丁在维h i t b e 九空间中包含 个向量的字典d ，除了_ 第一步迭代过程巾的内 秋运算外，讣算一次内秋仅需要1 次乘法和1 次加法，完成一次分解则仅仅需要 m 次乘法和m 次加法。这比原始的匹配追踪算法分解一次所需要的计算量降低 了很多。 这种快速算法从本质上说，是一种以增加存储空间来减少计算复杂度的方 法。1 i 过这种算法也有很大的局限性。首先在第一次迭代中t ( 毋d ) 只 能直接计算出来，这一步的计算量仍然很大，尤其是在某些对实时性要求很高的 第1 i 页 南京邮电学院硕士论文 场合仍然无法接受。如果要得到一个尸项的分解式则需要( p 1 ) + m n 次乘法 和( p i ) m + m ( n 一1 ) 次加法。 其次，当字典规模很大时，矩阵h 所需要的存储空间将十分庞大，总共需要 存储m ( m 一1 ) 2 个内积值。不过，在实际应用中，字典中的大多数向量是由一 些基本向量经过平移构成的，只有少数向量相互直接的内积值不为0 ，这种情况 下所需要的存储空间也还可以接受了。 3 1 2 基于减少内积运算次数的快速算法 m b a n h a m 在文献 6 4 中提出的分层搜索快速算法可以应用于视频压缩领域 中，提高匹配追踪算法运算速度。这种算法把匹配追踪算法的计算分成两个阶段 进行，其关键的地方就是对各个阶段字典的定义。首先需要定义一个字典 g = ( ) m ，它可以是原来字典d 的子集，也可以不是，但都要求字典g 中向 量的个数 正要远远少于字典d 中向量的个数m 。同时，需要构造出若干规模较 小的子字典b = ( 毋) ，e r ；d ，这些字典分别对应于字典g 中的各个向量。这 样匹配追踪算法中每一个匹配搜索过程都转变为两步匹配的过程。即，先在字典 g 中找到与信号，最匹配的向量h a 1 cr “，p 1 = 瓣i cj r ”，d i ( 3 _ 2 ) 然后再在与向量相对应的字典d 中搜索与信号最匹配的向量g 。 l c 彤厂，驴i 。艘弦，g ，i 3 3 设系列字典( 岛) 。中向量的平均个数为 ，要使用匹配追踪算法得到一个， 项的分解式则需要尸( m + 鸠) v 次乘法以及p ( m ，+ 鸠) ( 一1 ) 次加法。当 m + 一m 2 m 时，分层匹配追踪算法能够极有效地降低匹配追踪算法的计算复杂 度。 1 i 过分层的匹配追踪算法的主要缺点是，这个方法的第二阶段所需要的字典 ( 见) 。中的向量不容易选择，一般情况下采用较为近似的选择方法。这种近似 第1 2 酉 的方法虽然不是最优的，但却容易定义。这时候，使用分层匹配追踪算法每一步 迭代搜索到的向量g 。并不一定与直接使用匹配追踪算法搜索到的向量相同。 从已知的实际效果来看，分层的匹配追踪算法一般会降低匹配追踪算法的信 号表示精度。 3 2 正交匹配追踪算法 假设按照匹配追踪算法在某一步迭代中选择出了向量g 在一般情况下由 于向量既不会与已经选择出来的向量( 乳) 。相正交，这样在残余信号r k f 中 减去黾的分量后，新的残余信号又将引入( 占。) 。的分量。为了消除这些分量， s m a l l a t 在文献 5 0 】中提出了在匹配追踪算法后使用共轭梯度算法来分解残余信 号，而目前更多的学者倾向于使用正交匹配追踪算法来分解信号，并提出了一些 正交匹配追踪算法的快速算法 3 7 3 8 1 1 3 9 1 。另外文献 9 还提出了一种投影分解 算法。 使用共轭梯度算法来分解残余信号的主要思想是：将舻厂中可由( ) 。：。线 性迭加表示的部分通过使用共轭梯度法求解方程的方法分离出来，从而使得新的 残余信号不包含( g ，) 。的分量a 然而当空间维数较高时，使用匹配追踪算法来分解信号，就需要使用较多的 向量，这时方程的系数矩阵就会十分庞大，使用共轭梯度法来分解残余信号会变 得十分困难。而正交的匹配追踪算法则更为常用。 3 2 1 正交匹配追踪算法的基本原理 求解最优逼近的问题可以用数学语言描述为：定义d = g t , g ：，g 。 c r ”为 字典，匹配追踪算法的目的就是要寻找一个有着最小m 的子集 d = 轧，g ，：，g j ) c d ，1 一i i ，l m ，和相应的系数 口l ，口2 ， 使 得 第1 3 页 南京邮电学院硕士论文 如果表示 i l ( a ，g ，：+ a ：g ，：+ 一+ o t g 厶) 一f l l - 6 k = k + 1 7f o ra l li t 8 q ：上( ) g ， 第1 4 页 南京邮电学院硕士论文 b f i n dj k 镘碍c i 。2 m a x c i 1 0 t = t 一 以) 1 1 k = g j + 他 旷去鼠 1 3 - r f = r f 一。 g 1 4 f o ra l l f t f 1 5 - “。2 1 6 g ，= g 一“，g j , 1 7 g i = i ) ) 1 8 m = k 1 9 = ( d 叮d + ) 一d 叮f ( 其中= a k ；k = 1 ，) ，d = 乩；七= 1 ，m ) 3 2 2 快速正交匹配追踪算法 上面提到的正交匹配追踪算法在每一步从字典中选择向量后，通过进行 g r a m s c h m i d t 程序，达到了消除残余信号中已选向量分量的目的。然而它将巨 大的运算量花费在向量运算上。我们假设1 m n sf 1 5 1 6 1 8 1 9 2 0 2 l 以j 。2 9 s , 如r a l l i t 托，= f 鼽怎， 5 c i2c l g i c j t 7 t i i e l = el y ；? g 。2 q e 。 c = c ? f g 、 第1 6 页 、“=_ n 咿 h 南京邮电学院硕士论文 2 2 k = k + 1 2 3 伽d j k 3 u c ht h a t 勺2 _ 野。 2 4 t = t 一 以) 2 5 可= 肜2 c ，2 。) 2 6 m = k ，j ly 1 止 7 1 j 。 0 斗 算法3 2 中其加快速度的关键在于f 面几点； 1 ) 定义如下表示可圭0 r 刮，则在正交化进行到第步时，吕和肜能通过前面 计算的结构得到，而不必直接从g i 和r f 计算得到： r f = 可2 一c 2 ( 3 8 ) g = 9 2 ，一y 2 ， ( 3 9 ) 2 ) 通过一定的推导 3 7 ，得出算法3 1 中第1 3 行r f = r f 一。 gj 和第1 6 行 g ，= g ，一以。g 的计算可以省略。 3 ) 算法3 1 的最后一行，计算满足最小平方的系数向量n 。 通过矩阵d 的q r 分解得到，即 d 。= q 。r 。 其中矩阵q 的列满足彼此正交，矩阵r 为上三角阵。那么 = ( d ”d ) 。d ”f 而这样的计算可以 ( 3 1 0 ) = ( ( q r ) 7 ( q r ) ) “( q r ) 7 f r 3 1 1 ) = r 。q 7 f 而上三角阵r 和向量q f 可以直接在向量选择的过程中计算出来： 第1 7 页 南京邮电学院硕士论文 r y i ，l ， 。 一厶 托，j 2儿j 。 0 y m j m ( 3 1 2 ) p 2 q 7 f = f t q r ( 3 ，1 3 ) 又因为r 是一个上三角阵，所以在算法3 2 最后一步计算r 。p 时，求逆所需的运 算代价很小，而且可以采用回代的技巧得到： 力，i = m d o w n t ol 如r ，= m d o w n t of + 1 c 1 2 c i y f j c i e n d c 。2 c 。| 7 j e n d 这样，在字典向量选定之后，计算系数n 的运算量就减小很多。 另外需要说明的是，矩阵q 的列是矩阵d 的列经过g r a m - s c h m i d t 过程得到 的。里的元素是用d 逼近f 所用的系数，而p 里的元素则是用q 逼近f 的系数， 即 i = d = q p ( 31 4 ) 矩阵r 可以看作是从到p 的映射矩阵。 3 2 3 从构建正交补空间角度出发的正交匹配追踪算法 上面一节提到的正交匹配追踪算法和它的快速算法，通过g r a m - s c h m i d t 过 程，实现了消除残余信号中已选向量分量的目的。y c p a t i 和r r e z a i i f a r 等人提 出的正交匹配追踪算法则是从构建正交补空间的角度，更加严密地解释了正交匹 配追踪算法的原理。 让我们先回顾匹配追踪算法。 d ： 毋) 是h i l b e r t 空间内一组给定的向量集合，定义v 为d 中向量张成的空 间，w 为v 的正交补空间，即 薨1 8 页 南京邮电学院硕士论文 v = s p a n ( & )( 3 1 5 ) w = v 1 ( i nh ) ( 3 1 6 ) 这里的d 也就是前面我们讲的字典，假设向量毋已经单位化( 8 昌= 1 ) 。匹配追 踪算法可以表示成如下信号重构形式： p v 厂= a y g , ( 3 1 7 ) ，e r 其中r 是对v 空间的正交投影算子。这样，假设匹配追踪算法进行到第k 步迭 代，则有 i ，= a ，g n + 席f = 五+ 科f ( 3 1 8 ) i = 1 假如我们取i 1 1 个向量进行逼近，则 厶= o t k g n ( 3 1 9 ) 类似上面定义的v 空间，我们定义k = s p a n g g r z l g 。) 。如果有厶= p m ， 则称厶为一个最优n 项逼近，也就是说厶是用从字典d 中选出的向量子集 g 岛，g 。) 构建出的最优逼近( 值得注意的是，这里不涉及如何选择出这个 最优子集的问题) 。这样，厶是一个最优n 项逼近，当且仅当r “f 、譬。而前 面的匹配追踪算法只能得到r ”厂上g ，所以由第二章提到的匹配追踪算法得到 的厶只能是次优的【3 8 】。也正因为是这样，每一步迭代产生的残余信号能量虽可 以保证收敛，当收敛速度会比较慢。这里重复文献 3 8 】的作者举的一个简单例子， 形象地说明这一缺点。 g 。和g ：是二维实空问内两个向量，也是二维空间内一个信号，如图3 1 ( a ) 所示。图3 1 ( b ) 示出了忙州随着k 增加的变化曲线，也就是残余信号能量的收 敛曲线。 第1 9 页 一塑塞塑皇兰堕堡主篓塞 7 泛 。 j石 磊一：。 ： 一 j j ： ? j i 、 j ， ， ， ， 一 ( b ) 图3 i 二维空间内的匹配追踪算法