（计算机软件与理论专业论文）基于提升算法离散小波变换的硬件设计与实现.pdf

基于提升算法离散小波变换的硬件设计与实现 摘要 近年来，离散小波变换( 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 ) 开始受到 了越来越多的重视，目前已成功地应用在各种领域，包括数值分析、信号分析、 影像编码、统计学和生物医学等等。由于离散小波变换具有极佳的能量集中的 特性和与生俱来的多分辨率的特性，非常适合应用于影像和视频压缩编码。 为了将离散小波变换应用于实时信号( 如影像、声音等) 的处理，有必要 对其进行硬件实现。近年来，人们也提出了一些一维及二维离散小波变换的硬 件架构，但是由于这些架构大多数是基于传统离散小波理论，仍然需要耗费非 常大的计算量。1 9 9 6 年，i d a u b e c h i e s 和w s w e l d e n s 提出了一种新的离散小波 变换的架构一一基于提升算法的离散小波变换。这种类似于预测编码的小波变 换架构所变换出来的小波系数与传统滤波器处理得到的结果是完全相同的，但 是其所使用的硬件资源仅是传统滤波器架构的一半，并且具有较高的硬件使用 率、较少的存储单元和更规则的硬件架构。基于提升算法的离散小波变换所具 备的这些优异特性使其成为了j p e g 2 0 0 0 的核心算法。 本论文针对一维一阶、二维一阶、二维三阶等离散小波变换的硬件架构， 提出符合j p e g 2 0 0 0 标准的离散小波变换的硬件设计。该设计实现了5 3 滤波 器及9 7 滤波器离散小波的正变换和反变换，并且具有较高的硬件使用率和较 少的缓存器数目。整个硬件使用v e r i l o gh d l 语言进行描述，采用m o d e l s i m 进 行功能验证，然后通过s y n p l i c i t y 进行综合得到相应的门级电路。 关键词：离散小波变换，提升算法，v l s i ，并行式 h a r d w a r e a p p r o a c ht o l i f t i n gb a s e dd i s c r e t ew a v e l e tt r a n s f o r m a b s t r a c t 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 ) i su s e f u li n m a n yd i f f e r e n tf i e l d s ， i n c l u d i n gs i g n a la n a l y s i s ，s i g n a lc o m p r e s s i o n ，p a t t e r nr e c o g n i t i o n ，a n dn u m e r i c a l a n a l y s i s ，e s p e c i a l l y i n i m a g e v i d e oc o m p r e s s i o n t h ed w td e c o m p o s e ss i g n a l s i n t od i f f e r e n tf r e q u e n c yb a n d s ，a n dp e r f o r m sam u l t i r e s o l u t i o na n a l y s i s b e c a u s et h et r a d i t i o n a ld w ti s c o m p o s e do ff i l t e r s ，t h ec o m p l e x i t yo fv l s i i m p l e m e n t a t i o n i s v e r y h i g h i n l9 9 6 ，l i f t i n g b a s e dd w ti s p r o p o s e d t h e a d v a n t a g e so ft h el i f t i n g b a s e dd w ta r el o w e ri m p l e m e n t a t i o nc o m p l e x i t ya n dl e s s h a r d w a r er e s o u r c e s t h el i f t i n g - b a s e dd w ti sa l s ou s e di nt h en e w e s ti m a g e s t a n d a r d s u c ha sj p e g 2 0 0 0 i nt h i st h e s i s ，an e w2 - dd w ta r c h i t e c t u r e sb a s e do nl i f t i n gs c h e m ei s p r o p o s e d i n t h ef i r s t p a r t ，w ep r e s e n tb a s i ca r c h i t e c t u r e f o r2 - d i m e n s i o n a l l i f t i n g - b a s e d d w t b e c a u s eo fd o w n s a m p l i n go ft h ed w t t h eh a r d w a r e u t i l i z a t i o ni sv e r yl o w i no r d e rt os o l v et h ep r o b l e m ，w ep r o p o s eap i p e l i n e da n d p a r a l l e la r c h i t e c t u r et h a tc o m b i n e st h eh o r i z o n t a ia n dv e r t i c a ld w tt o g e t h e r i nt h e s e c o n dp a r t ，w es o l v es e v e r a lk e yp r o b l e m si nt h eh a r d w a r ea r c h i t e c t u r eo fw a v e l e t t h ep r o p o s e da r c h i t e c t u r e c o m p u t e s2 - dd w tc o e f f i c i e n t sc o n c u r r e n t l y , a n d a c h i e v e sh i g h e rh a r d w a r eu t i l i z a t i o n t h ep r o p o s e dv l s ia r c h i t e c t u r e sa r ed e s c r i b e di nv e r i l o gh d l ，s i m u l a t e db y m o d e l s i m ，a n ds y n t h e s i z e db ys y n p l i f y k e yw o r d s ：d w t ，l i f t i n gs c h e m e ，v l s i ，p a r a l l e l 插图清单 图2 1 离散小波变换正变换架构图6 图2 2 输入数据与高低频系数的关系6 图2 3 一维一阶离散小波变换的正、反变换架构图7 图2 4 一维三阶离散小波变换的架构8 图2 5 二维一阶离散小波变换8 图2 6 二维三阶离散小波变换9 图2 7 影像分解后的示意图9 图2 8 提升式离散小波正变换原理图1 0 图2 9 提升式离散小波反变换原理图1 l 图2 1 0 提升式5 3 滤波器离散小波变换原理图1 2 图2 1 1 提升式9 7 滤波器离散小波变换原理图1 3 图3 1 提升式5 3 滤波器小波变换原理图1 8 图3 2 提升式5 3 滤波器离散小波变换v l s i 架构( 一) 1 9 图3 3 简单的流水线示意图1 9 图3 4 流水线的时空图2 0 图3 5 组合逻辑转换成流水线设计2 0 图3 6 提升式5 3 滤波器离散小波变换v l s i 架构( 二) 2 1 图3 7 提升式5 3 滤波器离散小波变换时序图2 1 图3 8 一维小波变换整体框架2 2 图3 95 3 滤波器离散小波变换数据流图( 一) 2 2 图3 1 05 3 滤波器离散小波变换数据流图( 二) 2 3 图3 1 1 一维小波变换控制模块状态转移图2 4 图3 1 2 小波变换频带分布2 5 图3 1 3 基于提升算法直接实现二维一阶离散小波变换架构2 6 图3 1 4 使用一个变换模块来完成二维一阶小波变换的示意图2 6 图3 1 5 二维离散小波变换示意图2 7 图3 1 6 并行二维离散小波变换架构2 7 图3 1 7 行方向小波变换模块v l s i 架构2 9 图3 1 8 行方向小波变换控制模块状态转移图3 0 图3 1 9 离散小波正变换的处理过程3 1 图3 2 0 离散小波反变换的处理过程3 l 图3 2 1 离散小波反变换频带处理3 1 图3 2 2 二维多阶离散小波处理架构原理图3 2 图3 2 3 列方向小波第一级有限状态机状态转移图3 3 图3 2 4 行方向小波第一级有限状态机状态转移圈3 4 图4 1 假设输入的信号一3 6 图4 2 对输入信号进行周期延拓3 6 圈4 _ 3 对输入信号进行对称周期延拓3 6 图4 4 滤波和抽样以后的输出3 7 图4 5 全样本和半样本周期延拓示意图3 7 图4 69 7 滤波器一维提升小波算法原理图3 9 图4 79 7 滤波器一维提升算法前端扩展示意图一3 9 图4 89 7 滤波器一维提升算法后端扩展示意图3 9 图4 99 7 小波有限精度分析( 一) 4 1 图4 1 09 7 小波有限精度分析( 二) 4 2 图4 1 l 采用c s d 编码实现乘法运算示意图4 4 图4 1 2 移位优化后c s d 编码实现乘法运算示意图4 5 图4 1 3 全精度c s d 编码实现乘法运算示意图4 5 图4 1 4 截断处理后c s d 编码实现乘法运算示意图4 6 图4 1 5 提升参数仪的c s d 编码实现乘法运算示意图4 6 图4 1 6 提升参数1 3 的c s d 编码实现乘法运算示意图4 6 图4 1 7 提升参数y 的c s d 编码实现乘法运算示意图4 7 图4 1 8 提升参数6 的c s d 编码实现乘法运算示意图4 7 图4 1 9 提升参数k 的c s d 编码实现乘法运算示意图4 7 图4 2 0 提升参数l k 的c s d 编码实现乘法运算示意图一4 7 图4 2 l 提升式9 7 滤波器离散小波正变换原理图4 8 图4 2 2 提升式9 7 滤波器离散小波变换硬件架构图4 8 图4 2 3 离散小波正变换小波系数排序图4 9 图4 2 4 提升式9 7 滤波器实现离散小波正变换硬件架构图4 9 图4 2 59 7 滤波器小波变换数据时序图5 0 图4 2 6 离散小波反变换中小波系数排序图5 l 图4 2 7 提升式9 7 滤波器实现离散小波反变换硬件架构图5 1 图4 2 8 消除离散小波正变换中边界效应的小波系数排序图5 2 图4 2 9 嵌入式延拓消除边界效应的离散小波正变换硬件架构图5 2 图4 3 0 消除离散小波反变换中边界效应的小波系数排序图5 2 图4 3 1 实现消除边界效应的离散小波反交换硬件架构图5 3 图5 1 电路设计流程5 4 图5 2 电路的模拟以及验证环境5 5 图5 3 图像数据5 5 图5 45 3 滤波器列方向小波变换预期结果一5 6 图5 55 3 滤波器列方向变换仿真结果5 6 图5 65 3 滤波器行方向小波变换预期结果一5 6 图5 75 3 滤波器行方向变换仿真结果( 一) 。5 7 图5 85 3 滤波器行方向变换仿真结果( 二) 5 7 图5 99 7 滤波器列方向小波变换仿真结果一5 7 图5 1 09 7 滤波器行方向小波变换仿真结果5 7 图5 1 15 3 滤波器的提升式离散小波变换v l s i 架构( 三) 5 8 图5 1 25 3 滤波器列方向小波变换运算单元门级电路6 0 图5 1 35 3 滤波器行方向小波变换运算单元门级电路6 2 图5 1 49 7 滤波器列方向小波变换运算单元门级电路6 2 图5 1 59 7 滤波器行方向小波变换运算单元门级电路6 3 图5 1 65 3 滤波器小波变换门级电路6 3 图5 1 79 7 滤波器小波变换门级电路6 4 表格清单 表2 1 硬件资源比较表1 2 表3 1 集成电路发展规划的指标1 5 表3 2 不同设计层次的描述方法1 7 表4 19 7 滤波器离散小波变换提升系数及其c s d 编码4 4 表5 1 并行式离散小波变换综合结果6 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得盒胆王些盘堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字：形磊即d 签字日期：州年髟月历珀 学位论文版权使用授权书 本学位论文作者完全了解金世王些盍堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权盒胆互些盘 ! l 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：彭彩卅0 签字日期：础年髟月僖日 学位论文作者毕业后去向； 工作单位： 通讯地址： 签字日期一b 年q 月f 7 日 电话： 邮编： 致谢 两年半的研究生生活终于要告个段落了，首先要感谢的是指导老师高明 伦教授以及师母潘剑宏老师这两年多来的悉心指导和教诲，使得我能够顺利完 成学业。更重要的是在老师的关怀和指导下，让学生学习到研究的精神和求知 治学的严谨态度。高老师广博的学识以及见解都让学生受益良多，而老师的求 学生涯、成长经历以及奋斗过程，更是学生的一面镜子，值得终身学习。 然后要感谢胡永华、王锐、张溯、杨羽、尹勇生等各位师兄学长在我困惑 的时候，给予了相当多的宝贵意见与指导。 还要感谢这两年来在实验室中朝夕相处并同求学的各位同窗好友们，包 括胡德俊、王科、张俊、郭彦、圣应山、郭舒生、孙华波、鲁斌、陈巨，我们 相互交流、学习、鼓励和帮助，使得整个求学过程顺利许多，并且我们在空闲 的时候一起运动、一起出游。你们热情、活泼的个性，使得学习之余的日常生 活多姿多彩。 在此也感谢的是我亲爱的父、母亲，你们无微不至的关怀与照顾，让我可 以无后顾之忧完成学业。 最后，感谢我的女朋友臧婷，你的陪伴、鼓励、关怀和帮助是我求学生涯 的最大动力。同时感谢其他曾经帮助过我的入，谢谢你们，在此将论文完成的 喜悦与你们分享。 作者：杨明 2 0 0 6 年4 月 第一章绪论 1 1 应用背景 小波分析是近年来应用数学和工程学科中一个迅速发展的新领域，它联系 数学、物理学、计算机科学、信号与信号处理等众多学科，已经建立起较为完 善的体系。 与傅立叶变换( f o u r i e r t r a n s f o r m ) 相比，小波变换是时间频率的局部化分 析，它通过伸缩和平移运算对信号逐步进行多尺度细化，最终达到高频处时间 细分和低频处时间细分，因此可以聚焦到信号的任何细节，成为了傅立叶变换 以来在方法和工具上的一大突破，被人们称为“数学显微镜”。经过几十年的发 展，小波分析在理论和方法上不断取得突破性进展，已经深入到非线性逼近、 分形与混沌学、计算机图形学、数字通信、地震勘探、雷达成像、图像处理、 计算机视觉与编码、生物医学、时变估计和检测以及语音合成等诸多领域。目 前，小波分析已经成为一个多学科综合、交叉发展的新学科。 随着小波理论趋向成熟，并在许多学科、领域中的广泛应用，其硬件实现 算法研究也获得了长足的进步。与此同时，半导体集成工艺的迅速发展，使得 几百万个晶体管可以集成到单个芯片上，集成电路进入了片上系统( s y s t e mo n c h i p ，简称s o c ) 时代，超大规模集成电路( v e r yl a r g es c a l ei n t e g r a t i o n ，简 称v l s i ) 的迅速发展为设计实时处理芯片提供了前提条件。由于小波变换所需 要的计算量巨大，在很多实际系统中，尤其是在实时性要求较高的应用场合， 如数码相机、可视电话、便携式摄像机和掌上电脑等，考虑到速度和面积的要 求，设计专用的小波变换编解码芯片已经成为一种迫切的要求。而v l s i 的高 速发展使得将小波变换算法实现为单个a s i c 芯片已经成为可能，它将在多个 领域获得广泛的应用。如何设计结构简单、实时性好，同时具有较小的砸积和 较低功耗的小波硬件已经成为新的富有挑战性的课题。 1 2 提升算法的提出及其意义 小波分析克服了加窗傅立叶变换的不足，其方法的提出可以追溯到1 9 1 0 年 h a a r 提出的h a a r 基，这可以看作为最简单的小波基。从1 9 3 6 年到1 9 8 1 年间， 众多学者对小波理论进行了研究，为小波分析的提出奠定了坚实的基础。 1 9 8 1 年，m o r l e t 仔细研究了o a b o r 变换方法，对傅立叶变换以及加窗傅立 叶交换的异同、特点和构造函数等进行了创造性的研究，首次提出了小波分析 ( w a v e l e t a n a l y s i s ) 的概念，并建立了以他的名字命名的m o r l e t 小波。1 9 8 6 年，法国大数学家m e y e r 第一次构造出具有衰减性的小波，该小波的二进伸缩、 平移可以构成l 2 ( r ) 空间的规范正交基，并提出了多分辨率分析的思想，为小 波理论作出了重要的贡献，从而掀起了研究小波变换的热潮。1 9 8 8 年， i d a u b e c h i e s 给出了具有紧支集和任意有限正则度的小波函数的一般构造方法， 并给出了具有紧支集的光滑正交小波基一一d a u b e c h i e s 基。1 9 8 9 年，m a l l a t 创 造性地把计算机视觉领域中的多尺度分析方法引入到小波基的构造中，统一了 s t r o m b e r g 、m e y e r 、l e r m a r i c 、b a t t l e 等人提出的各种小波构造方法 ”，并为小 波的应用铺平了道路。m a l l a t 受到了金字塔算法的启发，以多分辨率分析为基 础提出了著名的快速小波算法一一m a l l a t 算法，这是小波理论发展的突破性的 成果，m a l l a t 算法的提出宣告了小波分析从理论分析走向了宽广的应用研究之 路。 1 9 9 6 年，i d a u b e c h i e s 和w s w e l d e n s 提出了一种新的小波构造方案提 升算法【2 ，这是一种完全在空间域进行变换的小波构造方案，为了与传统的基 于傅立叶变换的小波构造方法相区别，基于提升算法构造的小波变换被称为“第 二代小波变换”。由于提升算法完全在空间域进行变换，完成对频率域信号的分 析，不需要借助于傅立叶变换，从而大大提高了计算速度，并且具有结构简单 等优点，因此得到了越来越广泛的应用。 i d a u b e c h i e s 和w s w e l d e n s 总结以往的小波理论的相关研究时发现：一、 传统的小波变换是在频率域上进行，其基本工具是傅立叶变换；二、经过传统 小波变换后得到的结果是浮点数，无论计算机的精度多高，都无法避免计算结 果损失。另外，对变换后得到的数据进行压缩时，往往需要先进行量化，这就 进一步引入了误差。相对于传统的小波变换，提升算法具有许多良好的、适合 硬件实现的特点： 1 不依赖于傅立叶变换，在空间域就能完成小波变换，实现对频率域信号的 分析。此优点使得不需要很强的傅立叶分柝背景便可以理解小波的特性和 小波变换。同时，由于摒弃了传统的傅立叶变换，转而将高低通滤波器转 化成一系列的预测和更新步骤，而预测和更新步骤的实现往往是很简单， 并且具有很大的重复性，从而简化了小波分解和重构的实现结构，降低了 运算复杂度。 2 可以进行同址运算，大大减少了程序所需要的存储器开销。这个良好的特 点使得提升算法非常适合于硬件实现，可以有效地提高硬件系统性能，降 低成本。 3 ，先分离、后运算的实现结构确保了不会产生冗余计算。传统的小波变换在 实现时，首先进行滤波操作，然后进行抽样。这样，滤波运算之后的结果 数据只有一半得到了保留，即有半的运算是无用的。提升算法由于采用 的是先分离、后运算的方法，有效地解决了这个问题。这使得在硬件实现 时，不仅提高了算法的实现速度和结果的产生速度，同时有效地降低了整 个系统的功耗。 4 ，提升算法的内部操作可以并行进行，有效地提高了小波变换运算速度。这 个特点也使得提升算法非常适合于小波变换的硬件实现，流水线结构可以 有效地将内部并行操作转化成为流水操作，从而成倍地提高运算速度。对 于硬传实现而言，这就意味着非常可观的性能改善。 5 基于提升算法构造的小波反变换可以很方便地由其正变换得到。从预测和 更新的算法可以看出，二者的实现是非常类似的，除了计算的数据和参数 不同，结构都是一样的。因而基于提升算法的小波反变换只是将正变换预 测和更新的次序颠倒一下，以及反转系数前的正负号即可。这个优点使得 我们在得到小波正变换的硬件架构的同时，可以很方便得到其反变换的硬 件实现架构。 6 通过提升算法，可以很方便地构造出整数到整数的小波变换。这不仅可以 减少由于浮点数运算带来的计算量巨大和精度失真的问题，而且结构简单， 有效地简化了算法的实现复杂度。 1 3 小波硬件实现算法的研究现状及j p e g 2 0 0 0 简介 随着小波理论的不断发展以及离散小波变换成功并广泛应用在各个不同领 域，近年来有许多一维及二维的离散小波变换的硬件架构被提出【3 _ 1 。从已经 发表出来的论文当中来看，比较著名的2 - d 离散小波变换架构有k p a r h i 和 t n i s h i t a n i 提出的合并平行字元( w o r d p a r a l l e l ) 及串霉亍数字( d i g i t a l s e r i a l ) 架构【3 】，a s l w e i s 及o k n o w l e s 所提出的四抽头( f o u r t a p ) d a u b e e h i e s 滤波器 架构 ，以及c c h a k r a b a r t i 和m v i s h w a n a t h 所提出的s i m d 线性阵列架构( s i m d a r r a ya r c h i t e c t u r e ) 1 4 1 。虽然出现了这么多的离散小波变换处理架构，但正如前 面所说，由于传统小波理论的局限，这些离散小渡变换架构都不可避免地存在 着耗费的计算量依然很大的问题。而i d a u b i c h i e s 和w s w e l d e n s 提出的离散小 波变换的提升算法很好地解决了这个问题。 基于提升算法的小波变换实现方式是一个新的研究方向国内外也有许多 专家和学者对于提升算法的硬件实现提出了一些想法和方案，但是没有比较成 熟的芯片推出。前面已经讨论过，基于提升算法的小波变换架构具有许多良好 的适合硬件实现特点，因此，基于提升算法的小波交换v l s i 实现的研究，具 有广阔的应用前景。 目前，基于提升算法离散小波的一个应用就是j p e g 2 0 0 0 静态影像标准口“。 j p e g 2 0 0 0 与传统j p e g 最大的不同在于它放弃了j p e g 所采用的以离散余弦变 换( d i s c r e t ec o s i n et r a n s f o r m ，简称d c t ) 为核心的区块编码方式，转而采用 以离散小波交换为核心内容的多锯析编码方式。离散小波交换是j p e g 2 0 0 0 的 核心，标准中的其他编码部分主要是基于离散小波的特点提出的。余弦变换是 经典的谱分析工具，它主要考察的是整个时间域过程的频率域特征或整个频率 域过程的时间域特征，因此对于平稳过程，它有很好的效果，但对于非平稳过 程，它却有诸多不足。在j p e g 标准中，离散余弦变换将图像压缩成8 x 8 的小 块，然后依次存放到文件中，这种算法靠丢弃频率信息实现压缩，因而图像的 压缩率越高，频率信息被丢弃就越多。在极端情况下，j p e g 图像只保留了反映 图像外貌的基本信息，精细的图像细节都丢失了。小波变换是更为优异的谱分 析工具，它既能考察局部时间域过程的频率域特征，又能考察局部频率域过程 的时间域特征，即使对于非平稳过程，处理起来也得心应手。它能将图像变换 成为一系列小波系数，这些系数可以被高效压缩和存储，此外，小波变换是针 对整幅图像来进行的，因此消除了d c t 压缩普遍具有的方块效应。 在j p e g 2 0 0 0 标准中，采用了两种小波变换：l e g a l l5 3 滤波器小波变换和 d a u b e c h i e s9 7 滤波器小波变换。前者可以用于有损或无损图像压缩，后者只能 用于有损压缩。本文的主要研究工作就是针对这两种滤波器而展开的。 1 4 章节概要 在本论文中，主要研究提升式离散小波变换v l s i 实现中的硬件架构设计与 实现，各章节的主要内容如下： 第一章：主要介绍离散小波变换的相关研究背景及动机，还有本论文的章 节概要。 第二章：首先介绍小波变换的原理以及实现离散小波变换的方法，其中包 括传统基于滤波器方式的离散小波变换和基于提升算法的离散小波变换，并比 较其优缺点。在此之后，介绍一维的离散小波变换的基本架构和一维三阶的基 本架构，然后将一维的小波变换架构延伸到二维架构，最后介绍二维三阶的基 本架构。 第三章：首先介绍集成电路发展概况和设计方法，然后介绍提升式5 3 滤波 器一维离散小波变换v l s i 实现的硬件架构。我们根据提升式小波变换的特点 实现了一种高效并行的二维离散小波变换硬件架构。 第四章：首先分析基于提升算法离散小波变换硬件实现中涉及到的一些关 键技术，这些技术的运用尤其对9 7 滤波器离散小波变换硬件实现有着重要的 影响。然后采用第三章提出的硬件槊构实现9 7 滤波器离散小波变换。 第五章：描述了电路的设计流程以及模拟验证结果。本文所提出的电路使 用v e r i l o gh d l 硬件描述语言进行r t l 级描述，并使用m o d e l s i m 进行仿真， 最后使用s y n p l i c i t y 进行综合得到电路的具体信息。 第六章：提出结论与展望。 1 5 课题来源 课题来源于安徽省产业厅电子发展基金资助( 2 0 0 4 0 1 3 ) 。 4 第二章离散小波变换 小波变换理论的建立始于上世纪8 0 年代的中期，法国学者m o r l e t 、 g r o s s m a n n 和m e y e r 等人首次使用小波这个名词为他们创建的理论命名。小波 理论的主要精髓在于通过一个原型函数所生成的基底函数( b a s ef u n c t i o n ) 来 对信号进行多重解析度( m u l t i r e s 0 1 u t i o n ) 描述与分析。此原型函数称为母小波 ( m o t h e r w a v e l e t ) ，而由其所生成的基底函数就称为小波( w a v e l e t ) 。9 0 年代 初，m a l l a t 和i d a u b e c h i e s 等人首先将小波变换的理论从工程应用的角度做了 新的诠释，他们的研究为小波变换的设计与实际操作建立了完备的基础，也使 得小波变换由理论阶段进入了工程应用领域。 由于小波理论在信号的分析与处理上，建立了一套新的并且实用的架构， 能够将信号分解成不同的频率成分，每一个不同的成分都可以分开进行后续的 处理，变换后的信号能够有效地降低输入信号的相关性，这就使得小波变换在 许多传统的工程问题上得到了广泛的应用空间。 本章首先简单介绍小波变换中多重解析度分析的基本概念以及小波变换的 一些基础架构，在此之后介绍基于提升算法的离散小波变换的原理与架构，并 对传统滤波器架构和提升式小波交换架构的优缺点进行了比较，最后将一维离 散小波变换延伸到二维的小波变换。 2 1 传统的离散小波变换 目前，越来越多的研究人员开始进行小波变换技术相关的应用研究，例如： 数值分析、信号处理、影像压缩、生物医学、模式识别与计算机视觉等等。当 离散小波变换应用于影像处理时具有下列的几个特点： 1 相对应的滤波器模组( f i l t e rb a n k s ) 可根据需要设计成最佳的时频分布 ( t i m e d e q u e n e yl o c a l i z a t i o n ) 。 2 提供一个极具弹性的多重解析度影像表示。 3 可与人类视觉特性相结合以达到更有效率、失真更小的压缩效果。 离散小波变换可以看成是种多重解析度的分解，小波变换将输入信号分 解成两个频带，这两个频带分别是输入信号的低频( l o w - p a s s ) 成分和高频 ( h i g h p a s s ) 成分。对于影像来说，高频成分是属于影像中比较细微的部分， 例如影像的边缘部分；而低频成分则是属于影像中比较平滑，没有太大变化的 部分。若是对低频的成分继续做分解的话，可以再将其分解为高频和低频的成 分，这就是所谓的多重解析度分解。 如果一维离散小波变换采用滤波器模组的方式来实现的，则滤波器模组包 括了低通滤波器h ( l o w p a s sf i l t e r ) 和高通滤波器g ( h i g h p a s sf i l t e r ) 。输入 信号分别通过低通滤波器和高通滤波器后，再经过二分之一的减采样 ( d o w n s a m p l i n g ) ，可以分别得到低频小波系数和高频小波系数。在低频小波 系数中仍含有较多的信号能量，因此可以将低频小波系数持续分解。假设滤波 器长度( f i l t e rt a p ) 为4 ，则低通滤波器h ( z ) 和高通滤波器g ( z ) 的运算可以表 示如下： h ( z ) = h o + h l z 叫+ h 2 z _ + h 3 z q ，11 、 g ( z ) = g o + g l z - 1 + 9 2 z - 2 + 9 3 z 。 在( 2 1 ) 式中，h 。和g 。各自表示低通滤波器和高通滤波器，而z “则表示 目前输入信号的前n 个输入信号。图2 1 为采用传统滤波器离散小波正交换架 构图，其中上2 表示二分之一取样。 图2 1 离散小波变换正变抉架构圈 假设输入资料为x ( n ) ，则可以将变换后的高、低频系数用式( 2 2 ) 和式( 2 3 ) 来表示，而图2 2 用来表示输入资料与高低频系数的关系，实线与虚线问每隔 一个输入数据就取样一次，表示二分之一取样的动作。 运算后产生的高频系数( w j ) ： w ；( o ) = x ( a ) g o + x ( 2 ) g l + x ( 1 ) 9 2 + x ( o ) 9 3 w j ( 1 ) = x ( 5 ) g o + x ( 4 ) g i + x ( 3 ) 9 2 + x ( 2 ) 9 3 ，、 w ；( 2 ) = x ( 7 ) g o + x ( 6 ) g l + x ( 5 ) 9 2 + x ( 4 ) 9 3 w ；( 3 ) = x ( 9 ) g 口+ x ( 8 ) g j + x ( 7 ) 9 2 + x ( 6 ) 9 3 运算后产生的低频系数( w ? ) ： w ：( o ) = x ( 3 ) h o + x ( 2 ) h l + x 0 ) h 2 + x ( 0 ) h 3 w ：( 1 ) = x ( 5 ) h o + x ( 4 ) h l + x ( 3 ) h 2 + x ( 2 ) h 3 ，。、 w ：( 2 ) = x ( 7 ) h o + x ( 6 ) h l + x ( 5 ) h 2 + x ( 4 ) h 3 t ( 3 ) = x ( 9 ) h o + x ( s ) h 1 + x ( 7 ) h 2 + x ( 6 ) h 3 w 刍( 1 ) w i ( 1 ) 瞻( 3 ) w 1 0 ) 图2 2 输入数据与高低频系数的关系 6 因为离散小波变换具有对称的性质，所以反变换时只要按照正变换相反的 步骤，就能顺利变换回原来的输入影像。反变换主要包括两个不同的滤波器： 高通滤波器g 和低通滤波器h ，以及一个增采样( u p s a m p l i n g ) 的动作。如果 选择适当的滤波器，并且不考虑变换时因浮点数运算所导致的误差，小波正变 换与反变换是一个无失真的交换过程。图2 3 是一阶一维离散小波变换的正、 反变换架构图。其中山2 表示二分之一减采样，个2 表示二倍增采样。 h p f l p f 离散小波正变换离散小波反变换 图2 3 维一阶离散小波变换的正、反变换架构图 为了得到多解析度的分解，我们可以简单地将一阶一维离散小波变换延伸 成多阶一维离散小波变换。每一阶离散小波变换的系数运算可以表示成： f o r c j = 1 t oj ) f o r ( i = 0 t o n 2 一l 、 k 一1 训( i ) = 咖( 2 i m ) h 。 f o r0 = 1t oj ) m 0 必 w ；( i ) = w c l ( 2 i m ) g 。；) m = 0 其中，j 表示目前的多解析的阶数，k 代表滤波器的长度，w d ( i ) 表示在第j 阶中第i 个低频小波系数，w j ( d 表示在第j 阶中第i 个高频小波系数，n 表示 原始输入数据( w r ) 的大小。图2 4 是一个一维三阶小波变换的架构图，每 一阶段变换之后，大部分的信号能量都集中在低频系数上，故下一阶段针对低 频系数继续进行变换。如果原始输入数据中包含n 个采样值，那么每经过一阶 小波变换后，采样值的数据量就会减少一半，这是因为二分之一采样动作的存 在，所以产生的低频小波系数与高频小波系数的个数都只有原始输入数据量的 一半( 即n 2 ) 。换句话说，经过图2 4 所示的三阶小波变换后，最后得到的低 频小波系数w ：( i ) 与高频小波系数w ：( i ) 的数量都只是输入w ：( i ) 的八分之一。另 外，在反变换部分，每一阶离散小波反变换的系数运算可以表示成： f o r ( i = j t o1 ) f o r ( i = 0 t o n 2 j 1 1 k 2 - 1k ，2 - 1 嘲( 2 i - 0 = w d ( i r e ) h 2 n + t + 哪( i - m ) g ：。 m = 0m = 0 k ，2 - 1 一k 2 - 1 叫( 2 i ) = w g ( i - m ) h z m + 州( i m ) 9 2 。； m = 0m = 0 l e v o lll e v e l 2l e v e l3 ms a m 图2 4 一维三阶离散小波变换的架构 如果将一维的小波变换延伸至二维的架构，一般有两种实现方法：不分离 的模式与分离的模式。在不分离模式中，必须使用二维的滤波器直接实现小波 变换；而在分离的模式中，则是使用一维的滤波器，先沿着水平的列方向进行 变换，然后再沿着垂直的行方向进行变换。 目前用来处理二维信号的二维小波变换，大多是使用如图2 5 所示的分离式 方法来实现的。图2 6 所示二维三阶小波变换则是最常用来处理二维影像的一 种小波变换方式，它经过三个二维一阶的小波变换模组来持续分解低频的小波 系数( 如w 1 ，与y t ，) ，并将一张影像分割成l o 个不同的高低频带，图2 7 是一 张影像经由此架构分解后的频带示意图。 行方向小波变换 图2 5 二维阶离散小波变换 w m 西知 w l h w l l 图2 6 二维三阶离散小波变换 一一一一一一i i w l h ： i i 一一一一一一i i w h h ： i i - - - _ - j 图2 7 影像分懈后的示意图 由于传统滤波器实现方式所需要的计算量相当庞大，假设滤波器长度为4 ， 实现小波变换需要8 个乘法器和6 个加法器，因此不利于v l s i 实现，接下来 介绍基于提升算法的离散小波变换。 2 2 提升式离散小波变换 关于离散小波变换的架构，已经有许多相关的论文被提出，但由于传统小 波变换理论的限制，这些架构所耗费的计算量仍然非常大。因此，在1 9 9 6 年， i d a u b e c h i e s 和w s w e l d e n s 提出了一种新的架构，这种架构被称为第二代离散 小波变换提升式离散小波变换( l i f t i n g b a s e dd i s c r e t ew a v e l e tt r a n s f o r m ， 简称l d w t ) 。这种类似于预测编码的小波架构所变换出来的小波系数与传统 的滤波器方式变换出来的系数相同，但是其所使用的硬件资源只是传统滤波器 架构的一半，并且运算量也大幅度地减少。国际标准组织( i s o ) 制定j p e g 2 0 0 0 的目的，主要就是针对现有j p e g 标准所末覆盖到的范围，比如低位元率的环 境( 即高压缩率的环境) 、影像在w w w 上的传输、医疗用的影像、影像资料 库与影像的即时传输等等。l d w t 技术已经明确地被纳入到j p e g 2 0 0 0 影像标 准当中。因此最近几年，在硬件电路中实现基于提升算法的离散小波变换成为 了一个研究热点。 l d w t 是新一代的离散小波变换，该算法主要由三个部分组成【1 7 ：分割模 块( s p l i t t i n g ) 、提升模块( 1 i f t i n g ) 和缩放模块( s e a l i n g ) ，图2 8 是一个提升 式离散小波正变换的原理图。 d i n 】 s i n 】 - - r - 一_ - - - - - _ - - - - - - - j - - - - - - - - 一 s p l i t i n gz f f t i n gs c a l i n g 图2 _ 8 提升式离散小波正变换原理图 各个模块的主要功能如下： 1 分割模块： 将输入的信号