（电路与系统专业论文）基于提升的离散小波变换vlsi结构设计与实现.pdf

摘要 摘要 小波变换由于其具有良好的时域和频域局部特性，已经广泛应用于信号处理 等领域，其中离散小波变换已经被采纳为图像压缩标准j p e g 2 0 0 0 的核心变换算 法。同时，由于离散小波变换的提升算法具有众多易于硬件实现的特性，因此设 计基于提升算法的离散小波变换v l s i 结构具有十分重要的意义。 本文首先比较详细的介绍了小波变换的基本理论，然后结合硬件设计与实现 的具体要求，本文对小波变换的提升算法进行了改进，改进的提升算法可以使传 统提升算法中分布在一条路径上串行运算的中间值，分别处于不同的路径，从而 为实现并行运算创造了条件。通过在改进的算法所对应的直接结构中添加延时寄 存器和流水线寄存器便可以使整个系统实现并行运算。对于具有多级提升的小波 变换，它所对应的直接结构具有重复性，因此可以利用分时复用技术，复用重复 的结构，以达到降低系统硬件资源消耗，提高硬件利用率的目的。此外，本文还 对二维小波变换的尺度归一化运算进行了优化，通过将一维行变换和一维列变换 的尺度归一化运算合并，进一步降低了运算量，减少了硬件消耗。在此基础上， 本文分别提出了9 1 7 和5 3 提升小波的高效v l s i 结构。 在完成提升小波v l s i 结构设计的基础上，本文使用层次式设计方法，对5 3 提升小波的硬件结构在o u a r t u si i7 0 平台上进行了仿真和实现，并将仿真结果与 用m a t l a b 7 1 软件进行的仿真结果进行了比较。结果表明，本文设计的v l s i 结构能够高效的实现小波变换，满足实际应用的需求。 关键词：离散小波变换提升算法v l s i 结构f p g a a b s t r a c ti a b s t r a c t d u et ot h ew e l lt i m e - f r e q u e n c yd e c o m p o s i t i o n ，t h ew a v e l e tt r a n s f o r mh a sb e e n e x t e n s i v e l yu s e di nm a n ya p p l i c a t i o n s t h ed i s c r e t ew a v e l e tt r a n s f o r m ( d w t ) h a s b e e n a d o p t e da s t h et r a n s f o r mc o r ei n e m e r g i n gi m a g ec o m p r e s s i o n s t a n d a r d j p e g 2 0 0 0 s i n c et h el i f t i n gs c h e m eh a ss e v e r a la d v a n t a g e sf o ri m p l e m e n t a t i o n , i ti s v a l u a b l et od e s i g nt h ev l s ia r c h i t e c t u r ef o rt h el i f t i n g - b a s e dd w t f i r s t l yt h eb a s i ct h e o r yo fw a v e l e tt r a n s f o r m ，e s p e c i a l l yt h el i f t i n gs c h e m e ，i s p r e s e n t e di nt h i st h e s i s t h e nw ep r o p o s ean e wf o r m u l ao ft h el i f t i n ga l g o r i t h m ， l e a d i n gt oan o v e lf o r mf o rt h el i f t i n gs c h e m e d u et ot h i sf o r m ，t h ei n t e r m e d i a t ed a t a w h i c ha r eu s e dt oc o m p u t et h eo u t p u td a t aa r ed i s t r i b u t e do nd i f f e r e n tp a t h s t h u s ，w e c a np r o c e s st h o s ei n t e r m e d i a t ed a t ai np a r a l l e lb ye m p l o y i n gt h ep a r a l l e la n dp i p e l i n e t e c h n i q u e s w i t l lt h e a b o v eo p e r a t i o n s ，t h ec o n v e n t i o n a ls e r i a ld a t af l o w o f l i f t i n g - b a s e dd w ti so p t i m i z e di n t op a r a l l e lo n e t h u s ，t h ec o r r e s p o n d i n gd i r e c t a r c h i t e c t u r eh a ss h o r tc r i t i c a lp a t hl a t e n c ya n di so fr e p e a t a b l e f u r t h e r , u t i l i z i n gt h i s r e p e a t a b i l i t y , t h ee f f i c i e n tf o l d e da r c h i t e c t u r e ( e f a ) i sd e r i v e df r o mt h ed i r e c t a r c h i t e c t u r eb ye m p l o y i n gt h ef o l dt e c h n i q u e w i t ht h i sp r o p o s e de 队t h er e q u i r e d h a r d w a r er e s o u r c ei sr e d u c e da n dt h eh a r d w a r eu t i l i z a t i o ni si n c r e a s e dg r e a t l y a d d i t i o n a l l y , w ea l s oo p t i m i z et h es c a l en o r m a l i z a t i o ns t e po ft h et w od i m e n s i o n a l d w t b ym e r g i n gt h es c a l en o r m a l i z a t i o ns t e p so ft h eo n ed i m e n s i o n a lr o wa n dc o l u m n t r a n s f o 锄t l m st h eh a r d w a r er e s o u r c ei sf u r t h e rr e d u c e d b a s e do nt h ea b o v e o p e r a t i o n s ，t h i st h e s i sp r o p o s e se f f i c i e n tv l s ia r c h i t e c t u r ef o r9 7a n d5 3l i f t i n g - b a s e d d w t o nt h eb a s i so ft h ea r c h i t e c t u r ef o rt h el i f t i n g b a s e ddf 玎t h et h e s i ss i m u l a t e s a n di m p l e m e n t s5 3l i f t i n g - b a s e dd w to nt h ea l t e r as t r a f i xi if p g ae p 2 s15 f 4 8 4 c 5 ， u s i n gt h eq u a r t u s i l 7 0p l a t f o r m t h es o f t w a r es i m u l a t i o nu s i n gm a t l a b 7 1i sa l s o p r e s e n t e dt ov e n f yt h eh a r d w a r es i m u l a t i o nr e s u l t s t h ec o m p r e s s i o na n ds y n t h e s i s r e s u l t si n d i c a t et h ee f f i c i e n c yo ft h ev l s ia r c h i t e c t u r ep r o p o s e di nt h i st h e s i s k e y w o r d ：d i s c r e t ew a v e l e tt r a n s f o r m ( d w t ) l i f t i n gs c h e m e v l s ia r c h i t e c t u r ef p g a 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果：也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：日期 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名：；猛址 日期 第一章绪论 第一章绪论 1 1 论文的选题背景 小波变换是最近几十年应用数学和工程学科中一个迅速发展的新领域，它在 时域和频域都具有良好的表征信号局部特征的能力，在低频部分具有较高的频率 分辨率和较低的时间分辨率，而在高频部分具有较高的时间分辨率和较低的频率 分辨率，所以非常适合探测正常信号中的部分反常信息并且展示其成分。小波变 换也因此被人们形象的称为分析信号的“数学显微镜”i i 】【2 】。 近年来小波变换已经逐步从理论分析走向实际应用。目前小波变换广泛应用 于信号处理、图像处理、视频处理、模式识别等领圳3 】【5 1 ，其中离散小波变换 ( d i s c r e t ew a v e l e tt r a n s f 0 1 t 1 1 ，d w t ) 已经成为j p e g 2 0 0 0 、m e p g 4 等新一代图像、 视频压缩标准推荐的核心变换算法( 6 】，【7 1 。然而，由于离散小波变换是一种数据密 集型运算，整个运算过程需要消耗大量的时间和存储空间，软件实现很难满足系 统实时处理的要求。而实际上，离散小波变换硬件实现是解决上述问题的有效途 径。与此同时，随着半导体技术的迅速发展，可以使成百上千万晶体管集成到一 个芯片上。超大规模集成电路( v e r yl a r g es c a l ei n t e g r a t e dc i r c u i t s ，v l s i ) 的发展， 为将小波变换算法研发为满足实时性要求的专用集成电路( a p p l i c a t i o n s p e c i f i c a t i o ni n t e g r a t e dc i r c u i t s ，a s i c ) 提供了重要的条件。因此，开展高效离散 小波变换v l s i 结构设计与实现的研究具有非常重要的意义。 经过大量调研可以发现，目前实现离散小波变换v l s i 结构的方法可以归纳 为两类：一种是基于卷积算法的结构【8 】- 【1 3 】；另一种是基于提升算法的结构【1 4 】【17 1 。 由于提升算法相对于卷积算法具有运算复杂度低、原位运算以及可以实现整数到 整数变换等易于硬件实现的特性，因此成为研究的热点。在j p e g 2 0 0 0 标准中， 由于5 3 小波变换的系数简单，被应用于j p e g 2 0 0 0 中的图像无损压缩，而9 7 小 波变换在图像压缩方面具有良好的性能，被应用于j p e g 2 0 0 0 中的图像有损压缩， 所以目前许多学者对这两种小波变换进行了大量的研究，设计了许多硬件实现的 结构【1 4 】【1 7 】。但是这些结构在系统硬件资源消耗、关键路径延时以及实现复杂度等 方面没有很好的平衡，使得所设计的结构只能针对某一特定情况，很难满足其他 应用的需求。因此，本文将主要针对y p e g 2 0 0 0 中推荐的9 7 和5 3 提升小波进行 研究，目的在于设计和实现一种硬件资源消耗低、关键路径延时短并且实现复杂 度较低的离散小波变换v l s i 结构。 基于提升的离散小波变换v l s i 结构设计与实现 1 2 国内外研究现状 小波变换在数学以及其他理论领域已经取得了巨大的成就，但由于小波变换 具有数据依赖关系复杂，运算量大等特点，使得其实际应用受到了很大的限制。 随着小波变换研究的进一步深入以及对其实际应用需求的日益增长，小波变换硬 件结构的设计越来越受到学者们的关注。 在著名的小波m a l l a t 算法提出后不久，一些学者就提出了一些基于m a l l a t 算法 的小波变换结构。k n o w l e sg 等人于1 9 9 0 年最早提出了一种小波变换的v l s i 结构。 他们利用小波函数和尺度函数对应的一对滤波器来实现所有的计算f 8 】。1 9 9 1 年， l e w i sa s s d k n o w l e sg 结合具体滤波器系数的特点，构造了一种不用乘法器的四 系数小波变换处理器【9 】。但是这种结构只对固定的四系数小波滤波器有效。此后， p a r h ik k 等人于1 9 9 3 年提出了基于格形滤波器的小波变换折叠式结构和串行结 构i l 。虽然这两种结构的硬件利用率比较高，但是反馈回路中存在大量的寄存器， 而且系统的延时很大，对所处理的数据字长还有严格的要求。f f i d m a nj 和 m a n o l a k o se s 通过分析小波变换中数据的相关性，于1 9 9 4 年提出了一种小波变 换的脉动阵列结构【1 1 1 。但是当这种结构推广到较高的变换级数时会导致效率的降 低和延时的增大。c h a k r a b a r i tc 和v i s h w a n a t hm 于1 9 9 5 年给出了单指令多数据 ( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a , s i m d ) 线性阵列和s i m d 网格结构【1 2 】。这种结 构具有一定的通用性，但是其硬件规模太大，不适合v l s i 实现。1 9 9 6 年，g r z e s z c z a k a 等人用一个脉动滤波器完成高通和低通系数计算，使得所设计的结构具有较高 的硬件利用率【l3 1 。但是该结构占用较大的面积，而且仅适用于阶数较低的小波滤 波器和分解级数。总之，以上传统的基于卷积算法的离散小波变换运算量大、存 储需求也大，所以对应的硬件规模都比较大，不利于v l s i 设计与实现。 s w e l d e n sw 于1 9 9 6 年提出了一种不依赖于傅里叶变换的新的小波构造方案 提升算法【1 8 】，【1 9 】。基于提升算法的小波变换也被称为第二代小波变换，但是实 际上，提升算法也能实现第一代小波变换。与传统的基于卷积算法的小波变换相 比，基于提升算法的小波变换具有如下适合硬件实现的特点： ( 1 ) 运算量小，其运算复杂度为卷积运算方法的一半； ( 2 ) 原位运算，从而可以极大的减小系统所需的存储资源； ( 3 ) 实现整数小波变换，可以应用在要求很高的无失真压缩等领域。 d a u b e c h i e si 和s w e l d e n sw 在文献 1 9 中证明了任何有限脉冲响应滤波器的 多项矩阵都可以分解为一系列的上三角、下三角和对角矩阵的乘积。此外，由于 在j p e g 2 0 0 0 标准中，9 7 小波变换被应用于图像的有损压缩，5 3 小波变换被应 用于图像的无损压缩，所以目前许多学者针对9 7 和5 3 提升小波进行了大量的 第一章绪论 研究，设计了许多硬件实现结构。 2 0 0 1 年，j o uj m 等人提出了一种实现提升小波的直接结构【l4 1 。这种结构设 计简单、易于硬件实现，但是该结构的缺点在于长流水线占用大量的硬件资源， 并且该结构是9 7 提升小波的直接映射，对应两级提升操作。对于5 3 提升小波， 由于其只有一级提升，因而此时硬件利用率只有5 0 。为了节省硬件资源开销、 提高硬件利用率，l i a nc ，j 等在上述直接结构的基础上，于2 0 0 1 年提出了一种 f o l d e d 结构【”】。该结构基于5 3 提升小波的一级提升操作，对于9 7 提升小波的 两级提升操作，它将第一级运算结果返回到输入端进一步进行第二次提升操作。 该结构在很大程度上降低了硬件资源的消耗，使得其所需的算术资源仅为直接结 构的一半。但是该结构的缺点在于它的最高工作频率相对于直接结构又有了一定 的降低，而且所需的存储器数目仍然比较多。鉴于以上结构存在的缺点，2 0 0 4 年 h u a n gc t 等提出了一种在不增加硬件资源开销的情况下提高系统工作频率的改 进提升算法【l6 1 。该算法的主要思想是转移从输入节点到运算节点的乘法器，以消 除时序延时的累加，从而缩短关键路径的延时提高系统工作频率。基于此算法， h u a n gc t 等提出了一种实现提升小波的f l i p p i n g 结构。w ub f 和l i nc f 于 2 0 0 5 年也提出了一种改进的提升算法。该算法的主要思想是把提升过程中的预测 和更新合并成一个步骤，以达到提高系统工作频率和降低硬件资源消耗的目的 u 。但是上述两种基于改进提升算法的结构都存在实现复杂度高和必须考虑舍入 误差的问题，实际应用有一定的难度。 二维的图像处理是小波变换应用的一个重要领域，尤其是在j p e g 2 0 0 0 标准 提出来之后，对于j p e g 2 0 0 0 中小波变换硬件实现问题的研究立刻就成为学术界 的一个热点。 从总体上看，实现二维离散小波变换的结构可以分为两类：一类是直接结构 2 0 】，【2 1 1 ，另一类是基于行的并行结构【2 2 】。【2 5 1 。直接结构的基本思想是先进行一维行 小波变换，把中间的结果存储在一个缓冲存储器中，在行变换完成后再接着进行 一维列小波变换。二维小波变换的直接结构实现简单，但是需要大量的中间数据 缓存资源，而且只有在整个一维行变换完成之后才能进行一维列变换，所以具有 较长的输出延时以及计算延时，限制了系统处理的速度。基于行的并行结构则是 在完成一定数目的一维行小波变换后，便可以进行一维列小波变换，此后一维行 变换和列变换并行进行。因此，这种结构不仅有效的用附加的处理器代替了大量 的中间缓存，节省了存储器资源，同时也提高了系统处理数据的能力。 随着半导体技术的迅速发展，目前国外一些芯片设计公司已经开发出了 j p e g 2 0 0 0 图像压缩芯片，比如美国的a d i 公司，该公司于2 0 0 3 年推出了a d v 2 0 2 芯片，其最高处理速度达1 5 0 m h z ，图像最大可达4 0 9 6 像素，而且可以根据不同 的应用要求，提供不同级别的j p e g 2 0 0 0 压缩。a d v 2 0 2 也支持更高格式的影像， 4 基于提升的离散小波变换v l s i 结构设计与实现 因此，在高清电视和数字电影技术中有广泛的应用前景【z 6 j ，【2 7 】。此外，加拿大的 d i g i t a lr a p i d s 公司，荷兰的p h i l i p s 公司等也都分别开发出了各自的图像压 缩芯片。 在国内，对于小波变换的研究还处于起步阶段，不过，已经有一些高校和研 究机构开始研发j p e g 2 0 0 0 图像压缩芯片。其中清华大学微电子学研究所的刘雷 波等提出了一种新的小波变换s c l a 算法，该算法极大的降低了j p e g 2 0 0 0 标准 中提升算法的乘法运算量。在此基础上，他们开发出了j p e g 2 0 0 0 编码芯片 t h j 2 k e 2 引。其他高校如西安交通大学、西安电子科技大学、华中科技大学、湖南 大学等也进行了相应的研究，取得了一些成果【2 9 】。【3 1 】。不过从总体上看，国内的图 像压缩芯片性能与国外先进水平相比，仍有较大差距。 综上所述，目前基于提升算法的离散小波变换v l s i 结构设计研究仍然处于 初始阶段，国内的情况更是如此，而且随着小波变换研究的进一步深入以及应用 领域的不断扩展，更加迫切的需要研究出高效的小波变换v l s i 结构。 1 3 本文研究内容及章节安排 本文对j - p e g 2 0 0 0 标准中推荐的核心变换算法_ d a u b e c h i e s 9 7 和5 3 小波 的v l s i 结构设计和实现进行了研究。目的在于设计和实现一种硬件资源消耗低、 关键路径延时短、结构简单易于扩展的离散小波变换v l s i 结构。 本文研究的主要内容包括： ( 1 ) 学习并掌握了小波变换的基本理论，在此基础上，深入研究了小波变换 的提升算法。 ( 2 ) 结合硬件设计与实现的具体需求，改进了传统的小波提升算法。在此基 础上，结合并行处理技术、流水线技术以及资源分时复用等技术，分别提出了9 7 和5 3 提升小波的v l s i 结构，并且将提出的结构和近年来一些学者提出的结构进 行了比较和分析。 ( 3 ) 以5 3 提升小波为例，采用层次式的设计方法，完成了基于f p g a 的离 散小波变换硬件设计与实现，并将仿真结果与m a t l a b 7 1 软件的仿真结果进行 了比较。 本文具体章节安排如下： 第一章为绪论，阐明了论文选题的背景和研究意义，介绍了离散小波变换 v l s i 结构的研究现状以及本文研究的主要内容和章节安排。 第二章对小波变换的基本理论，包括连续小波变换、离散小波变换、多分辨 率分析与m a l l a t 算法、提升小波变换以及二维离散小波变换做了比较详细的介绍。 第三章首先对v l s i 做了简要的介绍。接着介绍了本文的二维离散小波变换 第一章绪论 结构框架。然后结合实际需求，给出了一种改进的小波提升算法，在此基础上， 分别提出了9 7 和5 3 提升小波的v l s i 结构，包括：一维行小波变换、一维n d , 波变换以及尺度归一化的v l s i 结构。此外，本章还将提出的结构与近年来一些 学者提出的结构进行了比较和分析。 第四章以第三章中设计的5 3 提升小波v l s i 结构为例，详细介绍了其f p g a 实现过程。并且把该结构在a l t e r a 公司的f p g a 集成开发环境q u a r t u si i7 0 上的 仿真结果与在m a t l a b 7 1 软件上的仿真进行了比较。 第五章分析和总结了全文的主要工作，并指出了论文中有待改进的地方和进 一步的研究方向。 第二章小波变换理论基础 第二章小波变换理论基础 传统的信号分析一般都是建立在傅里叶变换基础之上的，但是傅里叶变换是 一种频域的分析方法，在时域无任何分辨率。也就是说，傅里叶分析可以知道信 号中有哪些频率成分，但却不知道这些频率成分是在什么时候产生的。因此，傅 里叶分析适合于处理平稳信号。然而现实生活中遇到的通常都是非平稳信号，对 于这类信号进行分析时，通常需要提取某一时间段的特征频域信息或某一频域段 所对应的时间信息。此时，傅里叶交换就显得无能为力了【3 2 1 。 为了研究信号在局部时间段内的频域特征，g a b o r 于1 9 4 6 年提出了g a b o r 变 换，后来又进一步发展成为短时傅里叶变换( s h o r tt i m ef o u r i e rt r a n s f o r m ，s ，r f t ) 。 其基本思想是：把信号划分成许多小的时间间隔，用傅里叶变换分析每个时间间 隔，从而确定该时间段内的频率信剧2 1 。其表达式为： ，m s 野l ( c o ，t ) = if ( t ) g ( t r ) e - s 。 d t o，m 其中e 一埘起着限制频率的作用，g ( f ) 起着限制时间的作用。随着时间f 的变化， 由g ( f ) 确定的“时间窗”在t 轴上移动，从而使厂( f ) 逐段进行分析。因此，g ( t ) 往 往被称为“窗口函数”。从式( 2 1 ) 可以看出，s 卵l ( c o ，t ) 大致反映了f ( t ) 在时 刻为f 、频率为缈的信号成分相对含量【3 3 】，【3 4 】。 短时傅里叶变换虽然在一定程度上解决了标准傅里叶变换不具有时域局部分 析能力的问题，但是也存在着其自身不可克服的缺陷。由短时傅里叶变换的定义 式可以看出其窗函数的大小和形状均与时间和频率无关，因而一旦窗函数确定后， 矩形窗口的形状就确定了。然而事实上，一般的高频信号持续时间较短，而低频 信号持续时间较长，因此分析高频信号宜采用小时间窗，分析低频信号宜采用大 时间窗，此时，短时傅里叶变换就无法兼顾这两方面的需求【3 5 1 。 小波变换继承和发展了短时傅里叶变换局部化的思想，它在时域和频域同时 具有良好的局部化特性。小波变换对于不同的频域在时间上的取样步长是具有调 节性的，即在高频时小波变换的时间分辨率较高、频域分辨率较低；在低频时小 波变换的时间分辨率较低、频域分辨率较高。这个特点符合了高频信号变化迅速 而低频信号变换缓慢的特点，因而是一种理想的信号处理工具。 2 1 连续小波变换 设妒( f ) r ( r ) ，其傅里叶变换为( 国) ，如果( o ( o j ) 满足如下条件： 基于提升的离散小波变换v l s i 结构设计与实现 q = e 肾认。o 式( 2 - 2 ) 则称妒( f ) 为一个基本小波或母小波( m o t h e rw a v e l e t ) ，而式( 2 2 ) 被称为小波容 许条件。也就是说，只有满足这个条件的时候，才能由构造的小波变换精确重构 原来的信号。 小波变换的过程实质上是输入信号在小波基函数集上展开的过程。小波基函 数集纪6 ( f ) 是由一个基本小波函数经过伸缩和平移构成的集合，如式( 2 - 3 ) 所示： 卜南认字m 6 如0 式( 2 - 3 ) 其中1 7 1 称为尺度因子，它的变化相当于频率大小的变化，b 称为平移因子，它的 变化相当于时间上的平移。对于任意函数f ( t ) l 2 ( r ) 其连续小波变换( c o n t i n u e w a v e l e tt r a n s f o r m ，c w t ) 定义为： w t y ( a , 6 ) = = a - - 1e ( ，砌+ ( 与争d t 式( 2 4 ) 其中，伊( 三二鱼) 为伊( 三二兰) 的共轭函数。 在所采用的基本小波满足小波容许条件式( 2 2 ) 的情况下，小波变换的逆变 换存在，那么厂( f ) 可以通过其小波变换嘎( 口，b ) 表示为： f ( t ) = 巧1e 亡去玛( a , b ) q ，o “f ) 如如 式( 2 5 ) 由小波容许条件式( 2 - 2 ) 可知，要满足小波容许条件必须满足多( o ) = 0 ，也 就是说痧( 国) 必须具有带通性质，即伊( f ) 必须是正负交替的振荡波形，使得其平均 值为0 ，这便是称之为“小波 ( w a v e l e t ) 的原因【l 】，【3 6 1 。 由小波变换的定义可以看出，连续小波变换中的眈。( f ) 和短时傅里叶变换中 的函数g ( t r ) e o 埘作用相似。但是不同的是，参数c o 的变化不影响窗口函数g ( f ) 的 频谱形状和大小，而参数a 的变化改变了纯。( f ) 的形状和大小，同时也改变了其 频谱结构。由傅里叶变换的性质容易知道纯。( f ) 的傅里叶变换为： ( o o ，6 ( 彩) = i 口i ( 口彩) p 劬 式( 2 6 ) 从式( 2 6 ) 中可以看出，如果尺度因子a 发生变化，那么用来分解信号的小波函 数纯。( f ) 频谱的中心频率和通带宽度相应的发生变化。当口较小时，( a a 。( f ) 的时域 波形较窄，在频域上中心频率较大，通带宽度较宽；当a 较大时，织。( f ) 的时域 波形较宽，在频域上中心频率较小，通带宽度较窄。因此，小波变换在时频平面 匕的基本分析单元具有如图2 1 所示的特性。此外容易得到，虽然分析频率有高 第二章小波变换理论基础 有低，但是在各个分析频段内分析的品质因素o 却保持不变。小波的这个特点， 符合实际工作的需要，即如果希望在时域上观察得越细致，就越要压缩观察的范 围，并提高分析频率。这和人类对感觉信息的加工相一致，因此，小波变换被形 象的称为数学显微镜【l 】。 2 = 1 2 ) c o o ( 口= 1 ) 2 ( 口= 2 ) 图2 1 小波变换基本分析单元特性 2 2 离散小波变换 连续小波变换具有很好的信号分析和处理特性，但同时含有大量冗余的信息， 计算量较大，这不利于小波变换在图像压缩等领域的应用。为了在保持原始信号 信息的前提下，尽可能的降低小波变换系数的冗余度，就需要对连续小波变换进 行离散化处理。因此，可以通过对尺度因子a 和平移因子b 进行取样，利用在时 间尺度平面上一些适当选取的离散点的小波变换值来描述信号，同时也不至于丢 失信息。 在连续小波变换的定义中口，b r ；a 0 ，为方便起见，在离散化过程中限制a 取正值。选取a = a j ，其中a 。是大于1 的固定伸缩步长，为整数，b = k b o a ：，b o 为常数，i 为整数，对应的离散小波函数驴，。0 ) 为： 嘣f ) ：口0 詈伊( 型警) ：口- - j 妒( 口o j t - k b o ) 0i d , o ) 纺丘o ) = 口2 伊( 二丢孑监) = 口。2 妒( 口 则，相应的离散小波变换表示为： 啊( 口：，慨) = e 厂( f 协，( f ) 出= 需要指出的是，这里的离散指的是连续的尺度因子a 和平移因子b 的离散化，而 不是指时间f ，因此这种小波变换也称为离散栅格下的小波变换【1 1 。 然而，如何选择和b o 才能保证啊( 口：，k b o ) 能够完整的表征原来的信号 厂( f ) ，也就是能不能利用吁( 口j ，砜) 的数值精确的重建厂( f ) 呢? 以及如果可以精 1 0 基于提升的离散小波变换v l s i 结构设计与实现 确重构，那么其具体的重构表示形式又是什么呢? 其实，这两个问题的答案是统 一的，都是建立在数学上所谓的“标架理论( f r a m et h e o r y ) 的基础上。当基本 小波缈( f ) 经过伸缩和平移后引出的函数族驴m ( f ) 满足以下条件时，就称缈肚( r ) 构 成一个标架： 爿| | 厂1 1 2 l 1 2 - ：1 1 2 式( 2 9 ) j k 其中0 a b 0 0 ，分别称为标架的下界和上界。当a = b 时，称为“紧标架( t i g h t f r a m e ) ”，此时重构表达式为： ( 力= 三手莩吁( 彰，慨鹚，t 其中，谚，。称为吩，。的对偶小波。 在实际应用中，信号大多是经采样得到的一系列离散值， 常是离散的数据序列，因此通常选取口。= 2 ，b o = 1 。 2 3 多分辨率分析与m a l l a t 算法 2 3 1 多分辨率分析 小波变换的对象通 从上一节我们得知：式( 2 8 ) 表示的离散小波变换仅仅是对尺度因子a 和平 移因子b 进行离散化，而对于时间t 并没有离散化，相应的计算仍然采用对时间 积分的形式，因此可以称为离散栅格下的小波变换。本节我们将从多分辨率分析 ( m u l t i r e s o l u t i o n a n a l y s i s ，m r a ) 的角度引入对尺度因子a 、平移因子b 以及时 间t 都离散化的离散小波变换。 多分辨率分析又称多尺度分析，最早是由m e y e r 和m a l l a t 引入的，后来又由 m a l l a t 创造性的将多分辨率分析理论用于小波分解与重构的算法构造上，提出了 正交小波的构造方法以及正交小波变换的快速算法，即m a l l a t 算法。多分辨率分 析的思想是：将原始信号分为不同分辨率上的一系列信号，然后选择合适的分辨 率或者同时在各级分辨率上处理此信号。多分辨率分析理论是建立在函数空间概 念的基础上的【3 7 1 。设 以) ，j z 是r ( r ) 空间中一系列闭合子空间，如果他们满足 如下条件，则称之为r ( 尺) 的一个多分辨率分析。 ( 1 ) 单调性：以c - 1 ，v j z ，即c 砭ckc z oc 圪lcv _ 2 ； ( 2 ) 逼近性：uv i = 亭( r ) ，n = 0 ； j e z 。j e z 。 ( 3 ) 伸缩性：厂( f ) 营f ( 2 t ) 巧1 ，j z ； ( 4 ) 平移不变性：f ( t ) v o u ( t - k ) v o ，对任意的k z ； 第二章小波变换理论基础 ( 5 ) r j e s z 基存在性：存在矽( f ) v o ，使得它在整数平移系 矽o 一后) ik z ) 上 构成圪的r i e s z 基。 可以证明，如果 巧) 是r ( 尺) 空间的一个多分辨率分析， ( f ) r ( 灭) 使得下式成立： 办。女( f ) = 2 7 佗妒( 2 一t - k ) j , k z 则存在唯一函数 那么办，。( f ) 必定是巧的一个标准正交基，其中，矽( f ) 称为尺度函数。 下面以一个三层分解为例，对多分辨率分析进行详细说明，一个典型的三层 多分辨率分析树如图2 2 所示。 图2 2 三层多分辨率分析树 从图2 2 中我们可以看出，多分辨率分析只是对低频部分进行进一步的分解， 而高频部分则不予考虑。因此，图中所示的三层多分辨率分解具有如下关系： s = 4 + 皿+ 职4 - d ，其中低频部分4 可以进一步分解下去。分解的最终目的是 构造一个在频率上高度逼近r ( 尺) 空间的正交小波基，而这些频率分辨率不同的 正交小波基相当于带宽各异的带通滤波器。 如果我们假设以表示图2 2 中的低频部分彳，形，表示图中的高频部分d ， 则形是巧在巧一。中的正交补，即：巧o = 巧- p j z 。因此，显然有如下关系存 在： 巧。髟o 一。o o 髟一。= 巧一。 式( 2 1 2 ) 从而多分辨率分析的子空间圪可以由有限个子空间来逼近，即： 圪= 圪。吃e 形一。o o o 彤 式( 2 1 3 ) 如果我们令乃巧表示分辨率为2 7 的函数的厂r ( r ) 逼近( 函数厂的低频部 分) ，而用嘭髟表示逼近的误差( 函数厂的高频部分) ，则由式( 2 1 3 ) 可以得 到如下关系： 兀= z + 以+ 以一1 + + d 2 + 吐 式( 2 1 4 ) 又因为f = l ，所以上式可以表示为：f = 工+ d i ，这就意味着任何函数 活l 1 2 基于提升的离散小波变换v l s i 结构设计与实现 f r 俾) 都可以由分辨率为2 ”时的低频部分和分辨率为2 j ( 1 j n ) 时的高频部 分完全重构。 由多分辨率分析概念可知，尺度函数矽( f ) 和小波函数伊( f ) 分别为尺度空间圪 和小波空间的一个标准正交基函数。又由于c - 圪，睨ck ，所以声( f ) 和矽( f ) 也属于圪，空间，从而( f ) 和缈( f ) 都可以由z 。空间的正交基丸。( f ) 线性表示： = 办 娩。( f ) = 坳) 国( 丑一n ) q o ( t ) = g o 娩( f ) = g ( ，z ) 动( 2 卜九) 式( 2 1 6 ) 其中系数h ( n ) = ，g ( n ) - - 。以上两个式子描述的是相邻两个尺度 空间基函数之间的关系，所以称为双尺度方程。其中式( 2 。1 5 ) 是多分辨率分析 的基础，表示任意子空间的展开都可以从它们自身的双倍分频拷贝中得到，即从 相邻较高分辨率的空间中得到【3 9 】。 从双尺度方程我们可以看出，多分辨率分析可以完全被尺度函数矽( f ) 所表示， 此外也可以证明任何尺度函数都可以被五血) 确定。即有如下结论存在：如果 妒( f ) r ( r ) 是一个可积的尺度函数，那么办( ) 的离散时间傅里叶变换就满足以下 关系： 陋( 彩) 1 2 + l 左( 缈+ 万) 2 = 2 磊( o ) ：压 式( 2 1 7 ) 式( 2 1 8 ) 因此，根据式( 2 1 6 ) 可知小波函数伊( f ) 也由五( 托) 确定，它们之间的关系可 以表示为： 2 3 2m a l l a t 算法 鼬) = 击触) 跏) 雪( 缈) = j i 5 + ( c o + n r ) e 一徊 多分辨率分析理论为研究信号的局部特性提供了一个直观的框架。这一点对 于非平稳信号十分重要，因为非平稳信号的频率是随着时间的不同而发生变化的， 而这种变化又可以分为慢变和快变两个部分。其中慢变部分对应于非平稳信号的 低频部分，表示的是信号的主要轮廓；而快变部分则对应于信号的高频信息，表 示的是信号的细节。基于这个思想，1 9 8 9 年m a l l a t 在研究小波变换多分辨率分析 第二章小波变换理论基础 理论和图像处理的应用时受到图像压缩中塔式算法的启发，提出了信号的塔式多 分辨率分解与重构的算法，即著名的m a l l a t 算法【2 】。 m a l l a t 算法的基本思想可以归纳为：设日，厂为能量有限信号厂r ( 尺) 在分辨 率为2 ，时的近似，那么日，厂可以迸一步分解为厂在分辨率2 一时的近似日f ( 通 过低通滤波器得到) 与位于分辨率2 ，与2 一之间的细节d n 厂( 通过高通滤波器 得到) 之和1 2 j 。 设尺度函数和小波函数分别为矽( x ) 和缈( 石) ，则信号厂在分辨率为2 川时，轮 廓信息日h 厂和细节信息d h 厂可以分别表示为： h 一厂( x ) = a i - l , k y 1 t ( 工) t = o b 一。厂( x ) = d i - 1 。纺- l ，。( x ) t = “ 其中，a j - l , k 是分辨率为2 川时的函数近似值或称之为尺度系数，d j 乩。是分辨率为 2 川时的细节或称之为小波系数。因此分辨率为2 时信号厂的近似一厂可以直接 表示为： h j = hj 七d j i 、 其中，h y f ( x ) = a j , k 矽j ，i ( 石) 。从式( 2 - 2 1 ) 、式( 2 2 2 ) 以及式( 2 2 3 ) 可以看 i = “ 出，h j f马一。厂以及q 一。厂的关系可以转化为它们相应的系数口卅与口h ，。以及 嘭- 1 。的关系。为此，我们利用双尺度方程，对式( 2 - 2 3 ) 两端用办 所o ) 做内积， 并利用式( 2 2 1 ) 和( 2 2 2 ) ，可以得到： 口椭= 玩嘲口” 七z 式( 2 2 4 ) 类似的，用函数纺- l 。( x ) 对式( 2 - 2 3 ) 两端做内积，并利用式( 2 - 2 i ) 和( 2 - 2 2 ) ， 可以得到： d j - l 。= 鼠嘲口弘 七毫z 从式( 2 2 4 ) 与( 2 2 5 ) 可以看出，序列 吸) ， 乳) 作为低通和高通滤波器系 数分别对输入序列 口卅 做滤波运算，然后每隔一点进行运算。以上两式便构成 m a l l a t 著名的塔式分解算法。利用m a l l a t 塔式分解算法，信号的分解过程如图2 3 所示。 与上述分解过程对应的多级分解后的m a l l a t 塔式重构算法为： a j 一- - z 啦a y 吐t + g 川l d j - m 上e z七z 式( 2 2 6 ) 1 4 基于提升的离散小波变换v l s i 结构设计与实现 图2 3m a l l a t 信号分解过程 2 4 提升小波变换 提升算法( l i f t i n gs c h e m e ) 是s w e d e n s 于1 9 9 6 年提出的一种不依赖于傅里 叶变换的新的小波变换构造方案，相对于m a l l a t 算法而言，提升算法是一种更快 更有效的小波变换方法，可以在空间域直接计算小波系数【1 8 】，【1 9 】，【4 0 】。因此，提升 算法适合于构造缺乏转换和扩张的小波，基于