（信号与信息处理专业论文）基于fpga的提升小波变换实现.pdf

硕士论文基于f p g a 的提升小波变换实现 摘要 提升小波变换是一类不依赖傅立叶变换的小波变换新方法，可以在时域或空域中 直接实现小波的构造。目前，1 p e g 2 0 0 0 图像压缩标准已经将提升算法列入了标准之 一。通过提升方案很容易构造整数小波变换，大大简化了小波变换的硬件电路设计。 本文对提升小波算法及其在可编程逻辑器件f p g a 上的硬件结构实现进行了研 究。选取j p e g 2 0 0 0 标准中的5 3 小波，在a l t e m 公司的s t r a t i x 系列芯片上，实现提 升小波变换。 论文对小波变换的多分辨率分析、双尺度方程等做了详细地介绍。讨论了提升小 波变换的原理和构造传统小波的提升方案，并根据递推算法求解小波提升系数，给出 5 3 小波的分解和重构提升方案。同时对图像多分辨率分解进行了深入地研究和探讨。 论文基于f p g a 研究了提升小波变换实现，设计了小波变换，逆变换，全局控制 几个重要模块的硬件结构，并对模块内的主要单元做了详细的分析。设计中采用多路 选择器，提高5 3 小波提升方案核的变换速度，利用移位加代替乘法操作，节约硬件 资源：通过转置访问存储器的地址，调用行变换模块完成列变换；变换结束后得到的 四个频带系数分开存储。多层小波变换分解可以通过对小波分解模块的级联得到。本 文同时也完成了提升小波逆变换的设计。 最后建立了v h d l 硬件模型，并在q u a r t u si i 中对各个模块进行逻辑综合，并 实施功能仿真和时序仿真，取得较好的效果。 关键词：小波变换；提升格式；f p g a ；j p e g 2 0 0 0 ：图像压缩 a b s t r a c t l i f t i n gw a v e l e tt r a n s f o r mi san e w w a v e l e tt r a n s f o r mm e t h o dt h a tc a nn o tu s e f o u r i e r 缸a n s f o m 嬲m a j o ra n a l y s i st 0 0 1 i tc a l lc o n s t r u c td i r e c t l yt h ew a v e l e t i nt i m e 。d o m a i na n d 丘e q u e n c y - d o m a i n 。l i f t i n gw a v e l e th a sb e e ni n c l u d e di nt h ej p e g 2 0 0 0i m a g ec o m p r e s s m n s t 跚l d 矾t h eg e n e r a li n t e g r a lw a v e l e tt r a n s f o r mc a nb ec o n s t r u c t e db yl i f t i n ga n t e t i c ， d e s i 皿o fc i r c u i ts y s t e mo fl i f t i n gw a v e l e t t r a n s f o r mi ss i m p l i f i e dg r e a t l y i i l 也i sd i s s e r t a t i o n ，ar e s e a r c hh a sb e e nm a d eo nt h el i f t i n gw a v e l e ta l g o r i t h ma n di t s f p g ai m p l e m e n t a t i o na r c h i t e c t u r e 5 3l i f t i n gw a v e l e ts y s t e mi sr e a l i z e di na l t e r a ss t r a t i x s e r i e sc h i p f i r s t l y ，司h et h e s i s i n t r o d u c e sm u l t i r e s o l u t i o na n a l y s i s ( m r a ) ，d o u b l e s c a l i n g e q u a t i o l l s 砒1 dl i f t i n gs c h e m e i na c c o r d a n c ew i t ht h er e c u r s i o na l g o r i t h mf o rc a l c u l a t i n g l i r i i l gc o e f f i c i e n t s ，a na r c h i t e c t u r eo f5 3 w a v e l e td e c o m p o s i t i o na n dr e c o n s t r u c t i o nl s p r e s e n t e d d i s c u s st h ei m p l e m e n t a t i o no fm u l t i r e s o l u t i o nd e c o m p o s i t i o n a n dr e c o n s t r u c t i o n o f i m a g e f o c u s i n go l ll i f t i n gw a v e l e ts y s t e md e s i g nb a s e do nf p g a ，t h et h e s i s a n a l y z e st h e d e s i g no ft h ew a v e l e tt r a n s f o r m ，i n v e r s et r a n s f o r m ，t h eo v e r a l l c o n t r o lo fi m p l e m e n t a t i o n a r c l l i t e c t u 】陀w i t h i l lt h em a i nu n i t i no r d e rt os p e e du pw a v e l e tt r a n s f o r m ， m u l t i p l e x e ra n d d i s p l a c e m e n tc a l a i si n s t e a do fm u l t i p l i c a t i o no p e r a t i o n t h r o u g ht r a n s p o s et h em e m o r y a d i b e s s r o wt r a n s f o 唧a t i o nc a d _ p e r f o r mr a n kt r a n s f o r m a t i o n t h ew a v e l e tc o e f f i c i e n t si s d i v i d e di n 协f o u rp a r t st os t o r e c a c a d et h ew a v e l e tt r a n s f o r mm o d u l e ，i t c a nr e a l i z e m u l t i 1 e v e lw a v e l e tt r a n s f o r m a tl a s t , t h ea r c h i t e c t u r eo fi n v e r s el i f t i n gw a v e l e tt r a n s f o r m i sa l s op r o p o s e d f i n a l l y ，t h el o g i cs y n t h e s i sa n dt i m i n ga n a l y s i sa l ei m p l e m e n t e d i nq u a r t u si is o f t w a r e w i t hf p g as t r a t i xs e r i a lc h i po fa l t e r ac o m p a n y k e yw o r d ：w a v e l e t t r a n s f o r m ；l i f t i n gs c h e m e s ；f p g a ；j p e g 2 0 0 0 ；i m a g ec o m p r e s s i o n 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明 确的说明。 研究生签名：年月 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名：年月日 硕士论文 基于f p g a 的提升小波变换实现 1 绪论 随着信息科学的飞速发展，信号处理的理论在过去的3 0 年中也获得了迅速地发 展。新理论和新算法层出不穷，如时频分析、多抽样率信号处理、小波变换、自适应 信号处理等等。小波分析 1 - 5 是近2 0 多年来迅速发展起来并广泛应用的信号处理的新 兴学科，作为一种快速高效、高精度的近似方法，它是傅立叶( f o u r i e r ) 分析的一个突 破性发展，给许多相关学科的研究领域带来了新的思想，为工程应用提供了一种有效 的分析工具。 1 1 选题的背景 现今，信号处理已经成为当代科学技术工作的重要部分，信号处理的目的就是： 准确的分析、诊断、编码压缩和量化、快速传递或存储、精确地重构( 或恢复) 。从数 学地角度来看，图像处理可以看作是信号处理，在小波分析的许多应用中，都可以归 结为信号处理问题。平稳信号处理的理想工具仍然是傅立叶分析。由于小波变换在时 域和频域可以同时具有良好的局部化特性，有利于分析信号的局部特征，故特别适用 于分析非稳定信号，并且具有快速算法，因此，在数学和工程等领域中都获得广泛应 用f 2 一。 第一代小波函数1 3 】是由定义在三2 俾) 空间上的母小波少( r ) 作伸缩与平移所得到，不 论是从二尺度差分方程的频域关系，还是从正交小波及双正交小波的构造方法都可以 看出，第一代小波构造实际上是以傅立叶变换为工具，对某些不满足傅立叶变换的函 数，或是不允许伸缩和平移的非欧几里得( n o n e u c l i d e a n ) 空间，第一代小波就显得无能 为力。但在实际应用中也存在一些问题，例如，在对信号和图像小波变换后，产生的 是浮点数，由于受到计算机有限字长的影响，必然会带来计算误差，往往不能实现信 号和图像的精确重构；再次，在对图像处理中，对图像的尺寸是有一定要求的，并不 是所有尺寸的图像都可以进行变换。 2 0 世纪9 0 年代中期，s w e l d e n s 提出小波提升方案( 1 i f t i n gs c h e m e ) 及第二代小波的 概念，并给出了经典小波中双正交小波的提升方案( 又称提升框架【6 吲) 。同年， d a u b e c h i e s 和s w e l d e i l s 合作，利用提升方案将小波变换分解成有限的提升过程，并证 明了，凡是用m a l l a t 算法实现的小波变换都可以转用提升方案来实现【9 】。从理论上说， 提升方案大大拓展了小波分析的研究领域；从应用上来看，提升方案也使构造小波不 再是数学家的专利，工程师们也可以根据自己的实际情况来构造不同的小波。因此， s w e l d e n s 提出的的提升方案被誉为是构造第二代小波的关键技术。 小波提升方案区别于第一代小波构造方法就在于，它不依赖于傅立叶变换，而是 l 绪论 硕士论文 在时域或空域中直接实现小波的构造，因此具有以下优点【3 】： ( a ) 可以实现整数小波变换，以及整数到整数的变换【1 0 捌。 第一代小波变换都是在实数域中进行的变换，对信号分析时，小波变换系数也是 实数。在图像处理中，输入的图像数据多用整数来表示，对存储和编码而言，整数要 比浮点数来得容易。小波提升方案就可用于实现整数小波变换，以及整数到整数的变 换，从而保证了原数据的准确重构。 ( b ) 能实现任意图像尺寸的小波变换。 小波提升方案在进行小波变换的时候是在原位计算各个系数。在计算某个特定位 置的系数时，使用到的数据仅仅是若干个相邻位置的数据和该位置的原有数据，所得 结果可以直接将原有数据覆盖掉而不影响后续系数的计算。 ( c ) 能很好的克服小波变换的边界问题。 小波提升方案可以对信号边界信号的采取不同的处理方法，以满足图像信号的重 建要求。 ( d ) 不依赖于傅立叶变换实现对小波的构造。 随着对小波提升方案研究的深入，它的应用范围也变得十分广泛，其中包括了信 号处理、数据压缩、图像编码等诸多领域，小波提升方案应用于图像压缩是小波分析 成果丰硕的应用领域之一。自从sm a l l a t 将二进小波变换用于图像的边缘检测、图像 压缩与重构以及m v w i e k e r h a u s e 将小波包理论用于图像的压缩，小波理论开始真正 地应用于图像处理领域，并以其良好的时频区域性和多分辨率分析能力，开辟了图像 处理的一个崭新领域。它的特点是压缩比高，压缩速度快，压缩后能保持信号与图像 的特征不变，且在传递中可以抗干扰。 小波变换图像编码不仅能够很好地消除图像数据中的统计冗余，而且小波变换的 多分辨率分析的变换特性提供了人眼视觉特征的许多机制。小波变换后的图像数据能 够保持原图像在各种分辨率下的精细结构，为进一步进行其它形式的图像处理提供了 便利。同时，小波变换是一种很好的图像分解方法，非常适合于分析突变信号，很自 然用于静止图像边缘提取、压缩。而且高阶小波变化还可以用于实时处理视频图像信 号，在减少编码时间、提高压缩比和降低失真度方面，都有很好的效果。因此小波变 换在图像处理中具有十分优越的性能。 目前，j p e g 2 0 0 0 图像压缩标准【1 1 ，1 2 】已经将提升算法列入了标准之中，可以预测， 在不久的将来，提升算法很有可能成为新一代小波构造的主流算法。同时，如何将提 升小波变换在硬件上实现就显得十分得重要，成为当前的一个研究热点。基于这个原 因，本文对提升方案小波变换的硬件电路设计进行了研究，并在可编程逻辑器件f p g a 上实现并通过验证。 2 硕上论文基于f p g a 的提升小波变换实现 1 2 国内外研究现状 1 9 9 5 年，s w e l d e n s 提出了不依赖于f o u r i e r 变换的双正交小波构造方法一提升方 案【6 1 ( l i f t i n gs c h e m e ) ，提升方案是完全基于时( 空) 域的构造方法，它没有平移和伸缩 的概念，可将小波的概念推广到有限区域、曲面上以及非均匀采样等领域中。提升方 案有固定的小波构造公式，并且提升过程中所有自由参数都集中在提升算子上。这使 得小波的构造过程大为简单且易于理解，文献【7 】从d o n o h o 小波出发，给出了提升方 案构造d d 双正交滤波器系列的方法。2 0 0 1 年，l i 等人1 1 3 】研究了提升方案与消失矩 的关系，提出了从任意小波出发，构造具有任意阶消失矩小波的提升格式。从l a u r e n t 多项式分解理论出发，c h e n g 等人【1 4 】给出了与c d f 9 7 、c d f l1 - 9 小波有相同支撑长 度的高性能双正交小波的提升构造过程。在文献 1 5 l o p ，k o v a c e v i c 将提升方案的概念 推广到任意维。几乎是与此同时，k e i n e r t 和q t j i a n g 从不同的方法出发，研究了多 小波的提升方案【l ”7 。 提升方案具有通用性和灵活性，不仅简单易于理解，而且有高效的小波变换实现 方式。因此，提升方案迅速吸引了众多专家的密切关注。迄今为止，已有小波的提升 分解及其改进提升方案构造小波，基于提升方案的整数小波变换，自适应提升小波变 换及其应用，以及提升方案的硬件实现都得到了广泛的研究。 我国对小波的研究起步相对较晚，1 9 9 4 年形成国内的小波研究高潮，并在信号的 去噪和图像的压缩、机械故障检测等方面取得了较大的进展。目前发表的小波学术论 文在图像处理和压缩中的应用性文章较多，从内容来看，主要可分为两大部分，一部 分是利用小波分析对信号进行消噪处理，以提高分辨率，这一部分包括小波变换用于 信噪分离、弱信号的提取以及信号奇异点与奇异度的测定和多尺度边缘检测与重构； 另一部分是利用小波分析做图像或数据压缩。一个图像经小波分解后，图像轮廓主要 体现在小波系数的低频部分，而细节部分主要体现在高频部分，因此可以采用不同的 量化方法对不同层次的低频系数和高频系数进行量化处理，对量化后的小波系数进行 重构，以达到图像或数据压缩的目的。利用小波分析对信号或图像进行去噪或压缩处 理，关键的就是如何选取阈值和如何进行阈值的量化，从某种程度上说，它直接关系 到信号消噪和压缩的质量。有关量化编码方法目前主要采用嵌入式零树小波编码 e z w ( e m b e d d e dz e r o t r e ew a v e l e t s ) 、多级树集合分裂编码s p i h i ( s e tp a r t i t i o n i n h i e r a r c h i c a l ) 、集合分裂嵌入块编码s p e c k ( s e tp a r t i t i o ne m b e d d e db l o c kc o d e r ) 、最优 截断的嵌入式块编码e b c o t ( e m b e d d e db l o c kc o d i n gw i t ho p t i m i a z e dt r u n c a t i o n ) 等等 1 1 9 1 o 这些年来关于小波变换图像压缩算法的研究和应用都十分活跃。随着图文资料数 字化必然会产生大量的图像数据，对于高比率图像压缩算法的需求尤为迫切。而小波 3 l 绪论硕士论文 变换发展为一种新的有效的多分辨信号处理工具，具有良好的时频局域化特性，并且 它的分辨率特性便于与人眼的视觉特性相结合，因此合理地利用其变换系数的分布特 点，可以克服以往图像压缩算法产生的方块效应和其他不足，获得较好的压缩效果。 小波变换的特征，特别是多分辨率的特征， 嵌入式码流等特殊要求得以实现。因此， 使得图像编码中多分辨、多层质量控制、 小波变换成为新一代静止图像压缩标准 j p e g 2 0 0 0 的核心算法。作为一种优秀的图像压缩算法，小波变换图像压缩算法在图 像压缩这一领域具有重大的实用价值和广阔的发展前景，人们期待利用小波能够实现 高压缩比、高重现度图像的压缩，并探索在图像的边缘检测、分类与描述中的应用【l 2 0 l 。 随着小波在实际工程中应用的不断深入，研究人员发现，在数据速率很高的情况 下，现有的硬件系统很难承担实时处理的巨大运算量。因此，研究适合硬件实现的小 波分解算法和改进小波分解的硬件实现方法，便成为小波分析应用于工程实际的两大 关键课题。 1 3 论文主要工作 本论文的主要工作研究了基于f p g a 的提升小波算法的硬件设计，介绍了小波变 换的基础理论、小波提升方案。通过对小波提升算法的研究，用硬件描述语言v h d l 对整个设计进行编码，采用a l t e r a 公司的s t r a t i x 系列芯片，进行综合，并对布局 布线后的设计实施了功能和时序仿真，结合m a t l a b 开发工具观察和验证了仿真结果， 证明了设计的正确性和可行性。 本文一共分五章，第一章为绪论，阐明了本选题的背景和意义，介绍了小波提升 方案及其应用于图像压缩的研究现状。 第二章主要介绍了小波变换的基本理论，说明了小波变换的基本概念，如连续小 波变换的定义及其时频分析特性等，着重介绍了多分辨率分析、双尺度方程，并通过 多分辨率分析引出了构造正交小波的系统方法，最后说明了如何选取适合的小波基。 其中多分辨率分析是离散小波最重要的基础。 第三章主要讨论了提升小波变换的原理，分析构造传统小波的提升方案，以及提 升算法的多相表示，接着介绍了5 3 提升小波的分解提升方案和重构提升方案，并对 有限长序列的边界延拓方法作了说明，着重研究了对称数据延拓算法的原理和优点。 最后，详细地阐述了二维小波的提升算法，同时对最新的图像压缩标准做了简单的介 绍。 第四章的主要内容是设计了提升小波的硬件结构实现。首先对可编程逻辑器件 f p g a 及其e d a 技术做了简要的概述，介绍了硬件描述语言v h d l 的发展和开发流 程，然后重点研究了提升小波的硬件设计，分析了设计中的小波变换，逆变换，全局 控制几个重要模块的硬件设计，并对模块内的主要单元做了详细地说明，最后用v h d l 4 硕上论文基于f p g a 的提升小波变换实现 硬件描述语言编写了整个设计的可综合代码，并在a l t e r a 公司的开发软件 q u a r t u si i 中做了实现和时序仿真，取得较好的效果。 第五章给出了全文的总结，概括了本文所完成的工作，并指出了设计中存在的不 足和需要解决的问题。 2 小波变换基础 硕上论文 2 小波变换基础 小波变换是近十几年信号处理领域研究的一个热点，是继傅立叶变换和窗口傅立 叶变换之后的一个重大突破，为信号滤波、图像压缩、特征提取和数据融合及其他非 线性科学的研究领域带来革命性的影响，被认为是二十世纪公认的最辉煌的科学成就 之一。由于小波变换具有时频局部化的特点，而小波分析被誉为“数学显微镜”，这 就决定了它在高科技研究领域重要的地位。 本章主要介绍了小波变换基础理论，简单介绍了连续小波，离散小波等，详细讨 论多分辨率分析以及小波基选择原则，是论文的理论基础。 2 1 小波理论的发展 从历史上追溯，小波分析的原始思想形成于2 0 世纪初，在动力数学上的发展和工 程问题的提出及解决这两大学科的推动下发展起来的【l 捌。 当时傅立叶变换在信号处理方面已经得到了成功应用，但存在着频率与时间不能 被准确测量的问题，为突破这一障碍，科学家提出了通过将一个信号分割成并非纯正 弦波的元素，以达到同时在时间和频率两方面对信息进行浓缩，这是最初的小波思想。 1 9 0 9 年，匈牙利数学家a l f r e dh a a r 提出了“哈尔小波 ，1 9 3 6 年，英国数学家 j o h nl i t t l e w o o d 和p a l e y 开发出利用八度音阶将频率分组的方法，实现了按二进制对频 率分量分组。1 9 4 6 年，匈牙利裔的英国物理学家g a b o r 又提出加窗傅立叶变换，这样， 可以反映出信号在任意局部范围内的频率特性。经过半个多世纪，各个领域科学家的 共同努力，小波分析已经成为傅立叶分析发展史上一个新的里程碑。 小波变换是由法国地质物理工程师m o r l e t 在1 9 8 0 年提出的，用于分析震波信号， 后来称为“m o r l e t 小波”。而后，他与物理学家g r o s s m a n 合作的论文在1 9 8 4 年发表， 提出连续小波变换的几何体系，第一次提出了“小波 。1 9 8 5 年，m e y e r 发现了一种 指数衰减的任意阶可导小波，构造了一个光滑正交小波基被称为m e y e r 基，并于1 9 8 6 年与他原来的学生m a l l a t 提出了多分辨分析的思想【2 1 - 2 3 。m a l l a t 用多分辨分析来定义 小波，给出了m a l l a t 算法1 4 】，并应用于图像分析和完全重构。从此，小波迅速发展起 来，并得到空前的应用。 1 9 9 2 年，a c o h e n 和i n g r i dd a u b e c h i e s 提出了双正交小波【2 4 1 ，即对一信号的分析 小波和综合小波可以是不同的函数系。随后，g o o d m a n 等人提出多小波，用多个尺度 函数和多个小波函数表示信号，并且用h e r m i t 样条构造出第一个多小波。g o o d m a n ， h a r d i n 和m a s s o p u s t 首先构造出第一个非样条多小波，称为g h m 多小波。同时期， s w e l d e n s 提出的提升方法，实现小波构造具有线性相位，影响很大，极大地推动小波 6 硕士论文基于f p g a 的提升小波变换实现 变换的发展。 小波分析是当前应用数学和工程学科中一个迅速发展的新领域，经过近l o 年的探 索研究，重要的数学形式化体系已经建立，理论基础更加扎实。小波变换是空间( 时间) 和频率的局部变换，因而能有效地从信号中提取信息。通过伸缩和平移等运算功能可 对函数或信号进行多尺度的细化分析，解决了f o u r i e r 变换不能解决的许多困难问题。 小波变换联系了应用数学、物理学、计算机科学、信号与信息处理、图像处理、地震 勘探等多个学科。数学家认为，小波分析是一个新的数学分支，它是泛函分析、f o u r i e r 分析、调和分析、数值分析的完美结晶。信号和信息处理专家认为，小波分析是时间 尺度分析和多分辨分析的一种新技术，它在信号分析、语音合成、图像识别、计算 机视觉、数据压缩、地震勘探、大气与海洋波分析等方面的研究都取得了科学意义和 应用价值上的成果。 2 2 小波变换基本理论 小波变换是继傅立叶变换后，又一重要的信号分析工具。傅立叶变换将时间域与 频率域联系起来，分析信号特性。但它无法分析时域信号的局部频率特征信息。为了 克服这一缺陷，需要一种时间窗和频率窗都可以改变的时频局部化分析方法，即小波 分析方法。小波分析是傅立叶分析思想方法的发展和延伸，它在时域和频域内同时具 有良好的局部化特性。小波变换对不同的频率在时域上的取样步长是调节性的，即在 低频时小波变换的时间分辨率较低，而频率分辨率较高；高频时小波变换的时间分辨 率较高，而频率分辨率较低。因此，小波变换在时频分析具有突出的优势。 2 2 1 连续小波变换 设f ( t ) 是平方函数，记作厂( r ) l 2 ( r ) ，三2 俾) 表示实数轴上可测函数组成的平方可 积空间，缈o ) 为母小波或者基本小波，如果y ( r ) 满足容许性条件式( 2 1 ) 【1 。3 1 ， q = 亡学国 a o ( 2 1 ) 则 w f ( a , b ) = = 巾) 老少( 譬卜 ( 2 2 ) 称为f ( t ) 的小波变换，其中变量口尺度因子，变量b 为位移因子，即沿x 轴的平移位 置。从式( 2 1 ) 容许条件可以得出小波的两个特性： ， 振荡性：基本小波或母小波沙o ) 必须满足沙( 彩) i 萨o = o ，对应于时域上则是式 7 2 小波变换基础硕士论文 亡y ( ，) 西= o ，因此基本小波必须是振荡的且平均值为0 。 快速衰逝性：多( 缈) 在w = o 处至少有一阶零点，故y ( f ) 具有比i f | - 1 衰减的更快。可 见，小波是持续时间短，即有限的区域内不为零，但衰减很快的波形，均值为零。其 波形类似一个小波浪，故名“小波。 小波变换还可写成卷积形式， w f ( 口，6 ) = 巾) 去缈( 等卜厂承6 ) ( 2 3 ) 其中瓦( r ) ：- - - c 1 弘f 兰1 ，瓦( f ) 的傅立叶变换为 1 v “a 瓦( 国) ：云参( 口国) ( 2 4 ) m o r l e t 小波 m 眍i c a nh a t 小、捩 m 唧e r 小、寂 图2 2 1 几种常见小波【1 j 2 2 2 小波变换的时频分析特性 傅立叶变换用于信号处理，主要是分析全体信号的频谱特性，适用于平稳信号的 频谱分析，但却不具有时频分析的能力，尤其是在分析局部突变信号的能力较差。小 波的优势就在于，它的时频分析能力强，在非平稳信号处理领域得到广泛的应用。 小波函数少( ，) 为双窗函数，在 y ( 口，6 ) ) 中，口是表征频率的参数，称为尺度，b 是表征时间或空间位置的参数，称为平移因子。假定广，缈。，分别表示5 c ，的时间窗和频 率窗的中心位置，y 分别表示y 的时间窗和频率窗的半径，则小波变换 ( 厂) ( 口，6 ) 将信号厂限制在时间窗口5 1 b + a t + 一口y ，b + a t 一口吵 ( 2 5 ) 8 硕士论文 基于f p g a 的提升小波变换实现 频率窗 口- 1 国+ 一口- l 匆，口- l 国+ 口叫匆 ( 2 6 ) 之内。其中时间窗的中心在b + a t ，窗宽为2 口y ；频率窗的中心在a - 1 彩，窗宽则为 2 a 一j l f ，。频率宽度正比于其中心频率，即 可2 a - i , , 缈：垄! 兰：c ，c 为常数( 2 7 ) _ = r - 2 | - 2 乙刀吊裂 【厶，j 可见其比值与中心频率的位置无关，即小波变换具有“恒q 特性 ，随着a 的变化而 变化，如图2 2 2 所示。 缈( 口甜) j溪 f 譬? 王 ：，一r ； 罐 憋 。 f 、1 4 。r ： i、：霪 。蠢， | i - * t嚣赚 、娃 蠢 、 0 t 癸i ( _ 0 0 i 2 c o o 2 蕊 图2 2 2 y ( 鲫) 随着口的变化( 减，1 ，1 2 ) 的不同情况 由上分析可知，小波中的尺度因子a 将小波在波形相似条件下“拉伸 或“压缩 ， 平移因子b 则是将小波沿时间轴平移。a 增大，则对信号的时域观察范围变宽，而频 域观察范围则变窄，观察的中心频率逐渐降低；反之，a 减小，对信号的时域观察范 围变窄，而频域观察范围则变宽。图2 2 3 给出了小波变化的时间一频率示意图。 图2 2 3 中反映了小波变换的恒q 特性，两个矩形的面积不变，保持其时频分析 区间。小波变换提供了一个时，频平面上可调的分析窗口。小尺度时，时频窗口处于 高频范围，频率区间大，而时间区间则变短；大尺度时，时频窗口处于低频范围，频 率区间小，而时间区间则变长了。小波函数的这种伸缩和平移特性，具有极敏感的“变 焦能力，使得小波变换享有数学显微镜的美誉。 9 2 小波变换基础 硕士论文 y ( w ) q _ 1 方 町1 方 b b 七砖 图2 2 3 小波变换时间一频率窗，a l o ，则小波反变换为 巾户专f e ( 硝咖) 去y ( 譬) 卜) 考 1 0 ( 2 8 ) ( 2 9 ) 硕士论文 基于f p g a 的提升小波变换实现 由缈( f ) 三1 ( r ) 可得， 工l ( r ) 印 1 6 ( z ) i 。总存在l a u r e n t 多项式g ( z ) ，r ( z ) 满足： 口( z ) 2 6 ( z ) g ( z ) + ，( z ) l g ( z ) l - - l a t z ) i _ 1 6 ( z ) i ，显然，口( z ) 是商多项式，( z ) 是余多 义 吃( z ) = 吃。z 。 吃( z ) ：圭哳一七 o j 6 要求两者互素。根据e u c l i d e a n 算法，利用公约数的不唯一性，假定分解到最后一 级的公约数为常量k ，可以得到如下分解【3 6 ，7 8 】： 嘲= 州力瑚 a 为满足重构条件，我们总可以找到一个与其互补的滤波器旷，使得多相矩阵为： 尸。c z ，= ( 乏 三；耋： 三； = ；，；。i f g ：z 三 三昙 c 3 8 ， 由以下的恒等变换 ( g 。：z 三 = ( 三9 ：z ) ( ：三) = ( ? 三) ( 研：z ，：) c 3 9 ， 将式( 3 1 9 ) 的第一个恒等式用于式( 3 1 8 ) 1 懒，第二个恒等式用于式( 3 1 8 ) 1 拘奇 项，这样式( 3 1 8 ) 又可以表示为如下的形式： 、l ， z j 一一 6 力，j 一， r且 并 。 式项 3 提升小波变换原理及算法研究 硕十论文 即 p 。c z ，= ! ( 三q 2 j i ( z ( 吼。i z ，0 。j k 。昙 c 3 2 。， 由上文的定理i 可知，多项矩阵尸( z ) 总可以通过一个提升因子j ( z ) 从p d ( z ) 得到， 同时，定义如下： 可得到p ( z ) 的分解式 尸( z ) = p 。( z ) ( 三s ? ( 3 2 1 ) 墨( z ) 2 q ：h ( z ) ，t i ( z ) 2 q 2 心) ，其中1 f 朋，i ( z ) = 0 s 。( z ) = 七2 s ( z ) ，m = 2 n + l mr1 p ( z ) - ，曼卜 则与其对应的对偶滤波器相关的多相矩阵为： o 俨o 、i 肛刊 0 2 2 ；c z ，= ，垂。 一岛( ：一) 0 。 。1 一。z - 1 ) 言七0 c 3 2 3 ， 通过上面的分析可知，有限长的滤波器可以看作是首先进行惰性小波分解，然后 经过所级的提升和对偶提升这样一个过程，最后完成尺度变换的操作。如图3 1 7 和 图3 1 8 所示的基于因式分解的提升方案小波变换和逆变换实现结构： 图3 1 7 提升方案小波的前向变换( 分析过程) 硕士论文 基于f p g a 的提升小波变换实现 图3 1 8 提升方案小波的逆向变换( 综合过程) 将一个滤波器组分解成式( 3 2 2 ) 和式( 3 2 3 ) 这样的提升表示后，相当于将用m a l l a t 公式计算小波变换或反变换的工作分解成各个简单的运算单元的级联，极大的降低运 算的复杂性。 3 1 2 3 求解提升方案系数原理 根据上文的推导可知，s w e l d e n s 与d a u b e c h i e s 采用e u c l i d e a n 算法，分解多项式 矩阵月，得到了基于因式分解的提升方案系数，创建了基于因式分解的提升方法。 基于提升方案的小波前向变换包括分裂、预测和更新三个过程。提升步骤以多项 式矩阵表示的提升小波变换如图3 1 9 所示【2 7 1 。 朋玎)。 l 2 五c j 。 j o m ) 。 1o1 酢) z - e ( z ) 10l 1 图3 1 9 以多项式表不的提不方粟前向 p()，u()即上文中的预测算子与更新算子，可以看到，经过预测矩阵，五)保 持不变，得到了小波系数d(刀)，为五(行)和尸置(甩)的差值，而经过更新矩阵，疗) 保持不变，得到了尺度系数c 输出“疗)和吠胛)分别是提升后输出的平滑和细节分量。图3110是预测新多项式矩阵相乘后得到的提升方案前向小 3 提升小波变换原理及算法研究硕士论文 c 刀jl l - e ( z ) u ( z ) o - e ( z ) 1 d r m 。 图3 1 1 0 预测和更新多项式矩阵相乘后的提升方案 目前，提升方案研究主要是针对双正交小波，在基于因式分解的双正交小波滤波 器的最佳提升方案中，预测和更新步骤交替进行的，其原子级预测和更新步骤的多项 式分别为口( 1 + z 。1 ) 和( 1 + z - 1 ) ，其中提升系数口，是变化的。 求解提升方案系数基本步骤【2 7 1 如下 ( a ) 确定提升的级数，根据给定的双正交小波滤波器的g o ( z ) 项。判别矩阵 ( 卜端。p 咖要乘积几次可使矩阵第二行晒蝣项式的项魄小) 项数相同，所得乘积次数的两倍就是提升级数。 ( b ) 根据所确定的提升级数，列出包含尺度因子的方程组。 ( c ) 根据给定的双正交小波滤波器p ( z ) 的多项式系数，求解整个方程组。 3 2 小波提升系数 双正交镜像小波可以通过提升结构实现，通过因式分解和求解方程组得到双正交 小波的提升系数。j p e g 2 0 0 0 给出了两种双正交小波滤波器，即有损压缩c d f 9 7 小波， 其中分析滤波器为9 阶，合成滤波器为7 阶；无损滤波则采用样条5 3 小波。简称为 5 1 3 小波，其分析滤波器为5 阶，合成滤波器为3 阶。 一般情况下，图像压缩的首选滤波器是c d f 9 7 1 l 2 4 d x 波，其处理自然图像的性能 要好于样条5 3 小波，但由于c d f 9 7 小波系数均为无理数，这样就需要6 个乘法运算 和8 个加法运算，而要实现高性能的乘法和加法运算器则需要较多的硬件资源。5 3 小波的低通和高通分析滤波器分别有5 抽头和3 抽头，在图像压缩中也很受欢迎，虽 然使用5 3 小波的自然图像p s n r 明显小于c d f 9 7 小波，但是5 3 小波属于整数到整 数的小波变换，且支集较短，系数简单，计算复杂度低，并能实现无损压缩。故本设 硕士论文 基于f p g a 的提升小波变换实现 计选择5 3 小波滤波器，并在f p g a 上买现5 3 小坡，用于后期的图像压缩。 根据上章分析小波提升分解步骤，首先需要确定5 3 小波提升系数，下面根据文 献 2 8 】中介绍的递推算法来求解小波提升系数，该算法概念清晰，简单直观。 由预测矩阵( 二? 和更新矩阵( 三；) 确定了组合矩阵( 1 - 一p 尸r ； ，计算该组 合矩阵需要乘积几次使得所得矩阵的第二行第二列多项式的项数与已知滤波器的 项一样，则该双正交小波的提升级数就是乘积数的两倍。 5 3 小波提升分解滤波器组： 乃( z ) = 一i | z - 2 + l 4z - t + 三一言z 2 ( 3 2 4 ) g ( z ) 丢z - 2 ( 3 2 5 ) 则分解多项矩阵为： 尸c z ，= ( 兰 三；兰 三j = 1 - 1 3111 8484 4 1 - i 11 442 其相应的对偶重构滤波器组： 柏= 1 2 z - i 小丢1 z 厅( z ) = 1+ l + i z 三f z l ：1 三 1 z 一+ ! + 三z g ( z ) 2 4 z - 3 + 壶z - 2 三z 。1 + j 1 + 寺z 而对偶多项矩阵为： 凇) ：傺| - ， 、 l ( z ) ( z ) j 1 1z + 一1 22 1 - i 1 1 - i 3 1 一z+ 一一z一一+ 一z 22 424 ( 3 2 6 ) ( 3 2 7 ) ( 3 2 8 ) ( 3 2 9 ) 因此5 3 小波为两级提升方案，只需要进行一次预测和更新操作，c ( 刀) ，d ( 疗) 为最 后输出结果。 3 2 15 3 小波分解提升方案 设分解滤波器输入序列为：0 - x ：，a o = x 2 m ，则双正交滤波器输出的分递推式： 3 提升小波变换原理及算法研究硕士论文 研= 秽+ 口( 矽+ 或。) d = 才+ ( d + 吐。) ( 3 3 0 ) 与尺度系数相乘后的输出序列设为c ，= 屯c f ，珥- - k , 研，其中_ 是低通滤波器输出， 勺则是其输出，f l 拭( 3 3 0 ) 可推出： 一吒b “字口廿划 ( 3 3 ) 将一：z - i 争一带诫3 3 1 ) ： 办( z ) = p k o ( 一互1z ：+ z + l - p + z 一1 2 z 。2 ) ( 3 3 2 ) 将式( 3 3 2 ) - 与已知的分解滤波器式( 3 2 4 ) 比较系数可得： = 丢 ( 3 3 3 ) k 。= 1p 再将0 看做高通滤波器的输入，钟经过提前因子z 后变为0 ，所以将看作高通滤 波器的输出，同理，由式( 3 3 0 ) n ! i ， 研2 缸刃+ 口( 。+ 以) ( 3 3 4 ) 推出含系数高通滤波器： g ( z ) = k ( z 。+ 口+ 口z 之) ( 3 3 5 ) 与上文的分解高通滤波器g ( z ) 比较，可得： 口= 一一 1 p 善 。3 6 综上所述，可以得到5 3d , n 变换n # n 提升方案方框图，如图3 2 1 所示。 又由n 上d , n 递推算法基本思想，可得到5 3 小波提升方案递推算法结构图，如 硕士论文 基于f p g a 的提升小波变换实现 图3 2 15 3 小波变换的分解提升方案方框图 图3 2 2 从上往下进行是分解模式，即输入为奇偶序列，中层输出是奇序列，最下 层为输出偶序列，图中的数字为提升系数。这样得到了5 3 小波变换的提升系数。 1l i if l 1 1 2 1 2 1 、d ! l二 1 4 1 4 l - 1 2 1 4 ： | 1 ，2 1 ) d 。o 7 j 4 1 4 ， 图3 2 2 5 3 小波提升方案递推算法结构图 同理可推出9 7 小波变换的提升系数，表3 2 1 列出并对比了5 3 小波和9 7 小波 变换的提升方案。 3 提升小波变换原理及算法研究 硕士论文 表3 2 1 5 3 小波和9 7 小波变换的提升方案 小波 提升系数 研= 刃一三( 曰+ 或，) 5 3 d = 口+ 丢( 研+ 以。) d l - - 刃+ l - a ( c t + q + 1 ) ，口一1 5 8 6 ， d = q + ( 研+ 让。) ，一o 0 5 3 刃= 研+ y ( d + 吐。) ，7 o 8 8 3 9 7 【2 9 1 孑= c ；+ 万( 刃+ 以。) ，万0 4 4 4 q2 9 s 2 l ，g - = 1 1 4 5 z ：望 3 2 25 3 小波重构提升方案 小波分解的逆过程就是