（检测技术与自动化装置专业论文）用硬件实现小波变换及其重构的研究.pdf

用硬件实现小波变换及其重构的研究 摘要 小波变换是数学发展史上的重要成果。它对数学及工程应用都有 深远影响。最新的静态图像压缩标准j p e g 2 0 0 0 就是以离散小波变换 ( d w t ) 为核心变换算法的。 本文开始先详细分析了小波变换的理论基础，介绍了多分辨分析 ( m r a ) 、m a l l a t 算法和提升算法( l i f t i n gs c h e m e ) 。m a l l a t 算法的 计算量大，功耗与所占用的硬件面积也大。而提升小波变换算法克服 了m a l l a t 算法的缺点。按照提升算法得到的小波系数与传统滤波器 处理得到的结果是完全相同的，但是它所使用的硬件资源远远小于传 统滤波器架构，并且具有较高的硬件使用率、较少的存储单元和更规 则的架构。因此，在分析了超大规模集成电路( v l s i ) 设计要考虑的 性能指标之后，本文提出了一种提升算法的并行二维离散小波变换硬 件结构的设计思路和方法，并用了“移位加”、“流水线”、“双口r a m 等技术对小波变换模块进行了优化设计。利用此方案设计的硬件结构 具有输入输出数据流规则；独立性、灵活性强；硬件开销小；结构 简单；具有并行性，处理速度快；硬件利用率高的特点。 本文利用上述的方案设计得到了l eg a l l5 3 小波滤波器的硬件 结构，并用硬件描述语言v e r i l o gh d l 在r t l 级( 寄存器传输级) 实现 了二维离散小波变换，成功地对它进行了仿真。仿真结果与m a t l a b 得到的结果完全一样，验证了所设计的硬件结构的正确性和可实现 性。 关键词：小波变换，重构，硬件，提升算法，v l s i h s t u d yo fi m p l e m e n t i n gv v ：a v e l e tt r a n s f o r m a n dr e c o n s t r u c t i o n 、i t hh a r d 给。r e a b s t r a c t w a v e l e tt r ：m s f o r mi sav e 哆i m p o r t a n tp r o d u c t i o ni nt h ep h 姐o g e n y o fm a t h e m a t i c s i th a ss t r o n 9 1 yi m p a c t e do nb o t hm a t h e m a t i c sa i l d e n g i n e 耐n ga 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 m s f o m ( d 、w ) h a sb e e n u s e da st h ec o r et r a n s f o m l i n gt e c i m o l o g yi nj p e g 2 0 0 0 ，an e w e s ts t a t i c i m a g ec o m p r e s s i o ns t a n d a r d f i r s t l m t h i sm e s i sa n a l y z e s 也e 也e o 巧f h n d a m e n t a lo fw a v e l e t t r a n s f o 咖i nd e t a i l s ，a n da l s oi n t r o d u c e sm u r i r e s o l u t i o na n a l y s i s ( m r a ) ， m a l l a ta l g o r i t l h na n dl i r i n gs c h e m e c o n l p a r i n gw i t ht h et r a d i t i o n a l d w t ，t h el i r i n g - b a s e dd 呵i sl o w e ri m p l e m e n t a t i o nc o m p l e x i 妙a n d 1 e s sh 疵1 w a r er e s o u r c e s a r e ra n a l y z i n gt h es p e c i f i c a t i o n so fv _ e 哆l a r g e s c a l ei n t e g r a t i o nc i r c u i t ( v l s i ) d e s i g n ，w eo b t a i nt 1 1 ed e s i g ni d e aa n d m e t h o d so f2 dd w t c h i pb a s e do nl i m n gs c h e m e e s p e c i a l l yi nm e t r a n s f o r mm o d u l e ，w eu s em es h i f t a d dt e c h n i q u e ，t h ep i p e l i n et e c 蜥q u e ， a n dt h et w o w a yr 刖mt e c h n i q u et o o p t i m i z et h ea r c h i t e c t u r e t h e o p t i 血z e da r c h i t e c t u r er e s u l t si nt h em e r i t s ：r e g u l a r 岫删o u t p u td a t a m s t r e 锄，s t r o n gi n d 印e n d e n c ea n dn e x i b i l i t 弘l o wh a r e i 、a r ec o s t ，s i m p l e a r c l l i t e c t u r e ，i 枷n s i cp a r a l l e l i s m ，h i g hp e r c e n t a g eo f h a r d w a r e u t i l i z i n g u s i n gt h ea b o v em e t h o d s ，t h eh a m w a r ea r c h i t e c t u r eo fl eg a l l5 3 w a v e l e tf i l t e ri so b t a i n e di nt h i st h e s i s t h e nw ei m p l e m e n t2 dd 、 ，ti n t h er e g i s t e rt i 硼s f e rl e v e l ( r t l ) u s i n gt h eh a r d w a r ed e s c r i p t i o nl a n g u a g e v e m o g h d l w ，ea l s os u c c e s s 如l l ys i m u l a t et l l ea r c h i t e c t u r ei ni 汀l t h e r e s u l to fs i m u l a t i o ni sm es 锄ea st h a to fm a t l a bs i m u l a t i o n ，w h i c h p r o v e st h a tm ed e s i g n e da r c h i t e c t u r ei sc o r r e c ta n dp r a c t i c a b l e 1 yw o r d s ：w a v e l e tt r a n s f o r m ，r e c o n s t r u c t i o n ，h a r d w a r e ，l i f t i n g s c h e m e v l s i 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位 论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除 文中已明确注明和引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对 所写的内容负责，并完全意识到本声明的法律结果由本人承担。 学位论文作者签名：务多己 日期：z 护多年2 月万日 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅或借阅。本人授权东华大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存和汇编本学位论文。 保密口，在年解密后适用本版权书。 本学位论文属于 ， 不保密瓯 学位论文作者签名： 奄纹 指导教师签名： 日期： 舻夕月艿日日期：九呼隽年月弭 用硬件实现小波变换及其重构的研究 1 1 选题的背景及意义 第一章绪论弟一早瑁化 小波变换的系统理论是在为了克服傅立叶变换( f o u r i 神在时域的无定位性 ( 即不能提供任何局部时间段上的频率信息) 的缺点和短时傅立叶变换( s h o r tt i m e f o u r i e r t r a n s f o m s t i 叮) 的固定时窗( 窗不随频率的变化而变化) 的缺点的情况下 产生的【1 1 。线性系统理论中的傅立叶变换是以在两个方向上都无限伸展的正弦曲 线波作为正交基函数的。对于瞬态信号或高度局部化的信号( 例如边缘) ，由于 这些成分并不类似于任何一个傅立叶基函数，它们的变换系数( 频谱) 不是紧凑 的，频谱上呈现出一幅相当混乱的构成。这种情况下，傅立叶变换是通过复杂的 安排，以抵消一些正弦波的方式构造出在大部分区间都为零的函数而实现的。为 了克服上述缺陷，使用有限宽度基函数的变换方法逐步发展起来了。这些基函数 不仅在频率上而且在位置上是变化的，它们是有限宽度的波并被称为小波 ( w a v e l e t ) 。基于它们的变换就是小波变换。 小波变换的思想来源于伸缩和平移的方法【2 】。小波分析方法的提出，最早应 属1 9 1 0 年【3 】h a a r 提出的规范正交基( 这是一组非正则基) ，这是最早的小波基。 1 9 8 4 年【7 1 ，法国地质物理学家j m o r l e t 在处理地震数据时基于群论首先提出小波 变换概念。与f o u r i e r 变换、窗口f o u r i e r 变换( g a b o r 变换) 相比，小波变换是 一个时间和频率的局域变换，因而能有效的从信号中提取信息，通过伸缩和平移 等运算功能对函数或信号进行多尺度细化分析( m u l t i s c a l ea n a l y s i s ) ，解决 了f o u r i e r 变换不能解决的许多困难问题，它是调和分析发展史上里程碑式的进 展。“小波”概念提出后仅仅1 0 年便发展成为一门重要的前沿科学，小波变换已在 2 0 余个工程领域中获得不同程度的应用。最近几年，它已广泛应用于信号检测、 特征提取、故障诊断与定位、数据压缩等方面，是多学科关心的热点，是信号处理 的前沿课题。我们知道研究稳定信号的理想工具是f o u r i e r 变换，换句话说，稳定 信号可分解为正弦波的线性组合：而研究非稳定信号的理想工具是小波变换，其 中瞬变事件不能事先知道在何时发生，应与f o u r i e r 分析技术不同，小波分析技 l 用硬件实现小波变换及其重构的研究 术既适用于大多数具体的非稳定信号的分析，也适用于具有分形结构的信号。小 波分析( w a v e l e ta n a l y s i s ) 被认为是f o u r i e r 分析发展的一个新阶段，是一种应 用较广的数学分析方法【1 2 ，1 3 1 ，它是几十年来数学家和工程师完美合作的结晶，是 继f o u r i e r 分析之后纯粹数学和应用数学完美结合的又一典范。小波理论在许多 领域己经取得了成功应用，特别是信息处理、应用数学、量子物理学等领域。 s h a p r i o 利用小波变换对图像进行压缩，在图象质量良好的情况下获得了压缩比 1 2 8 ：1 ，在图象处理领域引起了轰动。美国应用数学学会己将小波变换列入九十年 代应用数学的八个前沿课题这一：美国联邦调查局已将小波压缩技术制定为指纹 压缩规范；美国国防部关键技术计划认为：小波分析将对国防关键技术中的信号 处理等产生重大影响：英国皇家数学学会也将小波分折列入九十年代重点发展的 十大方向之一；法国、德国等也都纷纷投人力量，进行这一领域的研究。 小波变换不仅继承和发展了短时傅里叶变换的局部化的思想，而且克服了短 时傅里叶变换的窗口不随频率变化的缺点，即在时变信号中，如果是高频率信号， 周期短，采用短时问窗；如果是低频率信号，周期长，可采用长时间窗，以便能 够清楚地看到信号的变化情况。所以，小波变换特别适用于探测正常信号中夹的 瞬态反常信号，并可展开其成分，被誉为信号分析的显微镜【1 4 1 。 小波变换的发展是以解决实际问题为出发点，而后上升到理论，辐射多学科， 是多学科讨论的热点，应用领域十分广泛( 如语音、图像、通信、雷达、水声、 地震、生物医学、机械振动、化工、湍流分析等) 。可以预见，在不久的将来， 小波分析必将在工程和科技各领域发挥更大的作用，正因为如此它也成为了广大 科技人员必须掌握的一种信号处理工具。小波变换把信息工业推向了一个新的时 代。目前，小波变换及重构工作大部分在计算机中进行，并且计算工作量大。随着 小波变换理论的进一步实用化，它的硬件实现方法正日益受到重视。 1 2 本文的研究内容及结构安排 新近发展起来的小波变换方法具有很多优点，其中二进小波在各个尺度上是 一组具有不同频带的带通滤波器，已经广泛地应用于雷达信号、语音信号、机械 振动信号和生物医学信号的特征分析中，并取得了很好的应用效果。 本文主要研究二维离散小波变换v l s i 结构设计。全文包含五章。第一章为 2 用硬件实现小波变换及其重构的研究 绪论，阐述了选题的背景及意义，介绍了小波变换的研究进展并结合当前小波硬 件实现算法的研究现状，指出了本文的主要工作。 第二章分析小波理论及算法，提出基于提升算法的滤波器的构造方法，阐述 了提升算法适合硬件实现的特性。 第三章给出了一套二维离散小波变换硬件结构的设计方案并在设计中采用 流水线等技术。 为了验证设计的正确性，第四章给出了电路设计及验证结果。 最后，在第五章给出了全文总结与展望。 1 3 本章小结 本章作为绪论首先介绍了小波变换的发展及研究现状，并分析了小波变换的 优点。结合当今i c 领域的蓬勃发展，介绍了小波变换硬件结构的研究现状。最 后指出本文的主要研究内容和论文组织安排。 3 用硬件实现小波变换及其重构的研究 第二章小波变换及其重构的相关理论 电子信息技术是六大高新技术中重要的一个领域，它的重要方面是图像和信 号处理。现今，信号处理已经成为当代科学技术工作的重要部分，信号处理的目 的就是：准确的分析、诊断、编码压缩和量化、快速传递或存储、精确地重构( 或 恢复) 。从数学的角度来看，信号与图像处理可以统一看作是信号处理( 图像可 以看作是二维信号) 【1 5 j 6 1 ，在小波分析的许多应用中，都可以归结为信号处理问 题。现在，对于其性质随实践是稳定不变的信号，处理的理想工具仍然是傅立叶 分析。但是在实际应用中的绝大多数信号是非稳定的，而特别适用于非稳定信号 的工具就是小波分析。 由于小波理论在信号的分析与处理上，建立了一套新的并且实用的架构，能 够将信号分解成不同的频率成分，每一个不同的成分都可以分开进行后续的处 理，变换后的信号能够有效的降低输入信号的相关性，这就使得小波变换在许多 传统的工程问题上得到了广泛的应用空间。 本章先简单介绍小波变换的理论基础，然后对多分辨分析、m a l l a t 算法和提 升算法等做了分析，并将提升算法与m a l l a t 算法做了比较。 2 1 小波变换基本理论 2 1 1 小波变换的定义 凡是满足条件p ( f ) 出= o ，y r 厂、z 的函数吵( f ) 都可以作为一个小波基函 数。所谓的小波就是函数y ( f ) 通过伸缩和平移而派生出来的一簇函数砂。曲( f ) ： 嘣f ) _ l 口l 缈( 学) 咖姐删， 式中a 为尺度参数，b 为位置参数n 7 】。信号x ( t ) 的小波定义为 暇他耻( 砘抖i 弘，y ( 警户“删y ( 一丢) 协) 用硬件实现小波变换及其重构的研究 上式表明，信号x o ) 的小波变换暇( 口，功是信号x ( f ) 通过一个传递函数为 i 口l - - 妙( 吲国) 的滤波器的输出。亦即子波变换相当于一组带通滤波器对信号进行 滤波( 每个尺度对应于一个通带) ，从而可以得到信号在不同通带内的信息。带 通滤波器的中心频率和带宽与尺度口成反比，不同带通滤波器之间具有相同的相 对带宽。具有较小f 和乘积的m o r l e t 小波：沙( f ) = e 叫1 2 + w ，显然其实部、 虚部分别为虬= e 叫2c o s ( f ) ，( f ) = p 叫2s i n ( f ) 。实部是一个偶函数，经傅立叶 变换之后仍为偶函数，所以实部是一无相移的滤波器；而虚部与实部的相位差为 万2 ，二者的幅频特性相同。信号x ( f ) 的m o r l e t 小波变换为： 暇( 口，f ) = 暇( 口，f ) + j 嘿( 口，f ) 斗一陋声辱) 2 ，2c o s ( ( 爿出 协2 ) 斗一陋声学) 2 ，2s 协( ( 等) 班) 设n 为信号x ( 聆f ) ( n _ 0 ，2 ，n 1 ) l 的采样点数，设某一带通滤波器的尺 度为口，其中心频率为 此时带通滤波器的带宽为 厶= ( 2 嬲) v = l ( 死) 很显然，当尺度口= 1 时，该带通滤波器的带宽与f f t 相同，二者的频率相 同；当口 1 时，带通滤波器的分辨率较f f r 算法高。 由小波函数的确切定义可知，小波函数一般具有以下特点n 8 1 9 1 ： ( 1 ) 小它们在时域中都具有紧支集或近似紧支集。原则上讲，任何满足可 容许性条件的r ( r ) 空间的函数都可以作为小波母函数( 包括实数函数或复数函 数、紧支集或非紧支集函数、正则或非正则函数等) 。但一般情况下，常常选取 紧支集或近似紧支集的( 具有时域的局部性) 具有正则性的( 具有频域的局部性) 实数或复数作为小波母函数，以使小波母函数在时域和频域都具有较好的局部特 5 用硬件实现小波变换及其重构的研究 性如图2 1 所示。 图2 一l 波和小波 ( 2 ) 波动性由于小波母函数满足可容许性条件伴垒坚d 彩 0 ，位移步长0 ，将小波基本函数尺度因子口和平移因 子f 分别离散化有口= 口0 ，f = 刀r 。口；，得到离散小波函数族： j c ，肚( f ) = 口i ，2 ( 口i ，f 一刀) ，七z ( 2 6 ) 取口o = 2 时有： 少似( f ) = 2 一，2 y ( 2 一- ，f 一刀) j ，七z ( 2 7 ) 对( 2 - 6 ) 进行分析可知，当j o 且绝对值大时，y 伽的波形是集中的，较小的平移因 子就可以覆盖。 则，任意函数厂( f ) 的离散小波变换定义为： 眄( j ，后) = j 厂( f ) 幸y ”o 础 ( 2 - 8 ) 其中歹，七z ，缈，| | ( f ) 是y ，t ( f ) 的复共轭。 框架理论分析线性离散信号表示的完全性、稳定性与冗余性，可以用来研究 离散小波变换。若离散小波序列杪卅乞加z 构成一个框架，若对任意厂( f ) 日存在 满足o 彳 o( 2 1 2 ) 由式( 2 1 1 ) 、( 2 1 2 ) 可以得到一个完善的离散小波变换，并且离散小波函 数族( 2 - 6 ) 构成一个框架。利用框架的相关理论得到离散小波变换。的逆变 换如下： 儿) 2 去丢( 加似) 嘣卅r 邝) 砌) ( 2 1 3 ) 其中，i 尺i d ( b 彳一1 ) i l 厂0 当彳= 曰时，即紧框架条件下有 巾) = 彳卅( ，少似) 沙m ( f ) ( 2 1 4 ) 由式( 2 1 3 ) 、( 2 1 4 ) 可知曰彳越接近于1 ，逼近误差就越小；当么= 口时 误差项r = o 。 将连续小波变换中连续变化的尺度因子和平移因子离散化，得到了离散小波 变换。如果保持平移参量在时域上的连续变化，只对尺度沿着二进序列采样，就 会得到介于c w t 和d w t 之间的二进小波变换。 2 1 4 二进小波变换及其重构 二进小波函数表示为嘲 。，( f ) = 2 圳2 ( 等) ( 2 - 1 5 ) 式中k - 是从咖佃之间的整数； 2 尺度因子； f 位移； 卜_ 连续变量。 二进小波介于连续小波和离散小波之间，它只是对尺度因子进行离散化，而 9 用硬件实现小波变换及其重构的研究 在时间域上的平移量仍保持连续变化。因此二进小波变换仍具有连续小波变换的 时移共变性，这是它较之离散化小波变换所具有的独特优点，也正因为如此，它 在奇异性检测，图形图像处理方面十分有用。 设小波函数为o ) ，其傅立叶变换为( 国) ，若存在两个常数o 1 时，采用高阶近似或递推的 方法就可以求得精确的解。 2 2 多分辨分析 19 8 8 年，m a l l a t 与m e y e r 合作提出了多分辨分析( m u l t i r e s o l 砸o n - a n a l y s i s 简称m r a ) 的框架，其主要思想是将r ( r ) 分解为一串具有不同分辨率的子空间 序列。该子空间序列的极限就是r ( 尺) ，然后将r ( r ) 中的厂描述为具有一系列 近似函数的逼近极限，其中每一个近似函数都是厂在不同分辨率子空间上的投影 【2 4 】 o 定义设 巧 忙是r ( r ) 的一串闭子空间序列，如果满足以下五条性质，则 称 巧 ，为r ( 尺) 的一个m r a 嘲。 、 ，e = ( 1 ) 单调性( 包容性) ： c ckc c 圪ic c ( 2 ) 逼近性： u 巧= r ( r ) ，n 巧= o l鼍z|ez ( 3 ) 伸缩性： ( f ) 巧( 2 f ) 巧一。 ( 4 ) 平移不变性： 矽( f ) 巧铮矽( f - 2 产1 j | ) 巧，v 七z ( 5 ) m e s z 基的存在： 存在( f ) ，使得 矽( 2 一，f 一后) ) 蛔构成巧的砒骼z 基。 令 巧 徊是r ( r ) 空间的一个多分辨分析，则存在一个唯一的函数 矽( f ) r 俾) 使得 哌= 2 叫2 矽( 2 一，卜后) ，歹，七z ( 2 - 2 3 ) 用硬件实现小波变换及其重构的研究 必定是巧内的一个标准正交基，其中( f ) 称为尺度函数。 若( f ) 生成一个多分辨分析，那么( f ) = 九，。( f ) 虼，并且因为 丸。，七：尼z ) 是眨的一个砒e s z 基，所以( f ) 用子空间的基函数 正，七( f ) = 2 矽( 2 f 一七) 展开，令展开系数为噍，得： 矽( f ) = 压而( 后) 矽( 2 f 一后) ( 2 2 4 ) 七= 1 这就是尺度函数得双尺度方程。 由单调性( 包容性) 可知巧+ 。巧，w z ，所以巧= 巧+ 。o + 。，反复应用 此式得： r ( r ) 2 是形+ - 同样，像矽( f ) 生成一样，因圪。= o ，故沙( f ) = 。o ( f ) 圪。，即存 在一个小波基函数y ( f ) 也可以用眨。子空间的基函数正。，七( f ) = 2 矽( 2 f 一后) 展 开，令展开系数为，则有与式( 2 2 4 ) 类似的双尺度方程 y ( f ) = 2 g ( 尼) 矽( 2 f 一后) ( 2 - 2 5 ) 七= “ 式( 2 2 5 ) 称为小波函数双尺度方程。 ( 2 2 4 ) 式是多分辨分析的基础，称为改善等式、m r a 等式或者扩张等式 汹1 。它表示，任意子空间的展开还是都可以从它们自身的双倍分辨率拷贝中得到， 即从相邻较高分辨率得空间中得到。 2 3 m a i i a t 算法 利用正交多变分析以及尺度方程和构造方程的系数，可以得到信号离散小波 变换及其逆变换的递推公式，即m a l l a t 算法溉蒯。它是1 9 8 8 年由m a l l a t 在数 字图像压缩中的金字塔算法的基础上，应用尺度分析思想而构造出来的信号分解 和重构算法邺1 3 铂。 用2 一，对( 2 2 4 ) 式中的f 进行尺度化，用，l 做平移，并令肌= 2 咒+ 后，得 1 2 用硬件实现小波变换及其重构的研究 ( 卜刀) = 压办( 后) 矽( 2 ( 2 。f 一万) 一七) = 压办( m 一2 咒) 矽( 2 们f 所) ( 2 - 2 6 ) 对( 2 2 5 ) 式作同样的操作，得 缈( 卜刀) = 压g ( 后) 矽( 2 ( f 一刀) 一后) = 压g ( 所一知) 矽( 一川f 所) ( 2 - 2 7 ) 给定满足要求的尺度函数式，见式( 2 2 3 ) ，便能够定义小波函数如下： = 2 。陀y ( 2 f 一后) ( 2 2 8 ) 根据m ，对于函数厂( f ) r 似) 可由小波函数和尺度函数作序列展开，分 为低频逼近和高频细节两个部分。 厂( f ) _ 。( 尼) 吮，七( f ) + 。q ( 尼) 吩 ( f ) ( 2 - 2 9 ) 斤2 4 ，一_ ，o 斤2 1 其中矗是任意开始尺度，c 名( 尼) 称为函数近似值或尺度系数；q ( 尼) 称为细节 或小波系数。在离散小波变换中，它们的值分别是： 气( 后) = m 。1 坨( f ) 氏，七( f ) f q ( 七) = m 。彪( f ) ，七( f ) ( 2 3 0 ) ( 2 3 1 ) 厂o ) ，九，七( f ) ，七( f ) 是离散变量f = o ，1 ，2 ，m 一1 的函数。通常令矗= o 并 选择m = 2 ，对f = o ，1 ，2 ，m 一1 ；j = o ，l ，2 ，一1 ；后= o ，1 ，2 ，2 ，一1 求 将( 2 2 8 ) 式代入( 2 3 1 ) 式，可得： q ( 后) = m 。彪厂( f ) 2 叫2 ( 2 心一后) ( 2 - 3 2 ) 用式( 2 2 7 ) 代替沙( 2 7 f 一七) ，可写成： 哆( 尼) = m _ l 2 ； 厂( 啦叫2 压；g ( 研一2 后) ( 2 廿1 ) f m ) ) c 2 弼) 交换和式与整数，并重新安排后可得： q ( 尼) = 斗( 聊地) p 2 ；巾) 2 训p 一聊 ) ( 2 泓) 1 3 用硬件实现小波变换及其重构的研究 再考虑( 2 - 3 0 ) 式在矗= 歹一1 时的值，结合式( 2 - 2 3 ) 可得 q 一- ( m ) = m 。佗军厂( f ) 2 一产妒2 矽( 2 咿l f 一聊) ( 2 弼) 因此式( 2 - 3 4 ) 司改写成 q ( 七) = g ( 聊一2 后) c l l ( 聊) ( 2 - 3 6 ) 同样，将式( 2 2 3 ) 代入式( 2 3 0 ) 可得： 巳( 后) = m 。彪厂( f ) 2 咱坨矽( 2 咱f 一尼) ( 2 - 3 7 ) 用式( 2 2 6 ) 代替引2 一矗f 一后) ，并作重排后可得： q ( 尼) = 萋 办( 肌一2 后) m 。1 坨莩厂( f ) 2 也- 1 ) 2 矽( 2 - ( ) f m ) ) c 2 瑚) m l l f j j 结合式( 2 3 6 ) 和式( 2 3 8 ) 可得 q ( 尼) = 办( 所一2 后) 气。( 聊) ( 2 3 9 ) 式( 2 3 9 ) 和( 2 3 6 ) 即为m a l l a t 分解算法1 q ( 后) = 办( 历一2 尼) q 一，( 聊) 9 ( 后) = 壹g ( 聊啦) 叫聊) 2 圳 式中的办( 册一2 尼) 和g ( m 一2 后) 分别相当于低通滤波器和高通滤波器，其计 算式为：办( 朋一2 尼) = ( 纵。，七，办，朋) ，g ( 朋一2 尼) = ( 吩+ j ，办。m ) 。 这一算法揭示了离散小波变换相邻尺度系数间的重要关系，通过递归计算实 现了对离散信号的小波变换。依此算法，我们将信号分成了不同频率通道成分， 且将每一频率通道成分又按相位进行了分解：频率越高，则相位划分越细，反之 则越疏蚓。 m a l l a t 重建算法为矧： q l ( 忌) = ；办( 研一2 尼) q ( 尼) + ；g ( 研一2 后) q ( 七) ( 2 _ 4 1 ) 此处是对后求和，上式可记作c ：，一l ( 后) = j l q ( 后) + g q ( 尼) ，j i l + ，g 分别是 ，g 的 对偶算子。 1 4 用硬件实现小波变换及其重构的研究 图2 2 信号分解过程示意嘲 上图说明了m a l l a t 分解算法的过程q _ 1 ( 尼) 是j 一l 级的输入，可以是第歹一2 级的平滑输出，也可以是原始信号的采样序列厂( 霓) 。经变换后，其低通输出 c j ( 尼) 是( 后) 在第j f 级分辨率下的平滑逼近，高通输出q ( 后) 是厂( 后) 在第j 级 分辨率下的细节信号，也是离散序列厂( 尼) 在第j 级分辨率下的小波变换系数。 ，g 对应滤波器组的冲激响应，办是低通的，相当于连续小波变换中的尺度函数 ( f ) ；g 是高通的，相当于连续小波变换中的小波函数缈( f ) 。 2 4 提升算法 提升( l i f t i n gs c h 锄e ) 的概念首先是由w i ms w e l d e i l s 提出来的，相对于m a l l a t 算法而言，提升算法是一种更快更有效的小波变换方法，它不依赖傅立叶变换， 可以在空间域直接计算小波系数啪一7 矧。 提升算法主要有两方面的应用。首先，它可以用来实现已经存在的小波。 d a u b e c l l i 锱和s w e l d e n s 已经证明，任何离散小波变换或者具有有限长滤波器的 双通道子带滤波都可以分解成为一系列的提升步骤，所有能够用m a l l a t 算法实 现的小波变换，都可以用提升算法来实现啪3 。因此，从这个层面来讲，提升算法 只是一种新的实现小波变换的的方法，信号在小波变换后的性质只取决于所使用 的小波，而与提升算法( “a i n gs c h 锄e ) 本身无关。其次，提升算法能够构造 新的小波。虽然，某个具体的设计可能会使提升算法等同于某个第一代小波变换， 但从本质而言，提升算法这一层次的运用属于第二代小波变换的范畴。 小波函数少肚( f ) 通常定义为一个属于r ( r ) 空间的母小波的二进伸缩和平 移 1 5 用硬件实现小波变换及其重构的研究 哌= 2 坨j 2 i ( 2 吖f 一尼) ，j ，后z ( 2 4 2 ) 这样的小波称为第一代小波。然而，在更一般的情况下，小波并不必须是彼 此的伸缩与平移，但仍然具有第一代小波的特点，这样的小波称为第二代小波 呻4 1 伽。利用提升方案可以构造它们。 第一代小波具有如下性质： 1 ) 是r 似) 空间的砒e s z 基，还是l e b e s g u e 、l i p s d l i t z 、s o b o l e v 和b 懿o v 空 间的无条件基； 2 ) 小波及其对偶在空间和频域是局域化的，有些小波还是紧支的； 3 ) 小波分析可纳入多分辨分析的框架，这导致了快速小波变换算法。 在研究中常存在如下问题： 4 ) 第一代小波提供了定义在尺开上函数的基，但在像数据分割、在一般定义 域上的微分和积分方程的求解，需要定义在任意的、可能不光滑的域上的 小波； 5 ) 第一代小波典型地只提供具有不变侧度的空间的基，而微分方程的对角 化、在曲线或表面上的分析等需要可适应加权测度的基； 6 ) 第一代小波隐含对数据进行规则采样，而实际问题经常要处理不规则采样 的数据。 具有性质1 ) ，2 ) ，3 ) 而又满足4 ) ，5 ) ，6 ) 性质的第一代小波的推广称为第 二代小波。这里的关键问题是平移与伸缩并不是属性1 ) ，2 ) ，3 ) 所必须的，放弃 平移和伸缩，隐含着傅里叶变换不能再用作构造工具。 s w e l d e n s 在文献 4 3 】中给小波下了一个广义的定义：“小波就是能够快速去 除数据相关性的构造块 。在这个定义中包含了小波的三个特征。首先，小波是 构造块，从数学上讲就是它们形成一组基，或者说是一个框架，这就意味着任何 一个通用的数据集合或者函数都能够以一种稳定的方式写成小波的线性组合。其 次，小波具有去相关能力。这就是说用小波系数表示数据要比原始数据更紧凑。 从信息论的角度来讲，即小波系数的熵比原始数据的熵要小；从近似理论的角度 讲，就是用少量的小波系数就可以得到函数的精确近似。第三个特征是必须能够 快速找到表示数据的小波系数，即在较短的时间内完成数据的原始表示和小波表 1 6 用硬件实现小波变换及其重构的研究 示之间的切换。小波的快速去相关能力是数据压缩、快速数据传输、去除噪声、 信号恢复以及快速数值运算等应用的关键。 下面介绍利用提升方案构造第二代小波的方法。 提升算法给出了双正交小波简单而有效的构造方法，使用了基本的多项式插 补来获取信号的高频分量( 7 系数) 。之后通过构建尺度函数来获取信号的低频 分量( 名系数) 。提升算法的基本思想在于通过一个懒小波( 1 a z yw a v c l e t ) ，逐步 构建出一个具有更加良好性质的新的小波，这就是提升的基本含义。一个规范的 提升算法有3 个步骤：分裂( s p l i t ) ，预测( p 川i c t ) 和更新( u p d a t e ) 。 丸1 丘l 图2 3 提升算法的实现步骤 提升算法的实现步骤如图2 3 所示。设有数据列磊，由于数据之间有某种相 关性，可以将它用更为紧凑的格式来表示，也就是说，寻找原数据列的一个子集， 使得它能够表示原始信号所包含的信息。下面，我们按照提升算法的3 个步骤， 分三部分来进行讨论。 1 分裂 将数据列九分裂成为两个小的子集丸。和丘。我们假定相邻的数据间有最 大的相关性( 在实际中也往往是这种情况) ，按照数据的奇偶序号对数据列进行间 隔采样，也即： 卫l = 九，2 七 后z 丘l = 凡，2 七+ l 后z 在这种情况下，就是我们前面提到的基本小波。用基本小波对信号进行分解 与重构如图2 - 4 所示： 1 7 用硬件实现小波变换及其重构的研究 ，1 l i 刀- i 图2 - 4 用基本小波对信号进行分解与重构 2 预测 设一个与数据无关的预测函数p ，使得： 丘。= p ( 允。) 那么，我们就可以用允。来表示原始的数据，称凡l 为小波系数。此时，我们 已经可以用较小的数据序列丸。和小波系数h ，来代替原始的数据。如果有一个 好的预测，那么两个子集 疋。，丘。 将产生比原来的序列九更为紧凑的表示。下 面，我们可以对这个算法进行周期重复。我们将疋。抽取成两个序列厶和如， 然后用心和p ( 如) 之间的差值来代替，这样经过万步，就可以用小波表示 允珂，凡竹，丘。) 来取代原来的数据序列。假使小波系数是由基于某种相关性的 预测模型得到的，那么， 丸玎，丘一，丘1 ) 将给出一个比原序列的更为紧凑的表 示。 预测函数户的构造需要考虑原始信号本身的特点，反映数据的相关关系。在 具体应用时，不可能由偶数项的值完全准确的预测奇数项的值，但要保证预测值 尽可能的接近。这样，得到的小波系数就会比较小，数据的相关性越强，大多数 小波系数的值就越小。 预测函数通过插值细分方法构造。常用的插值细分方法有：分段性插值和三 次样条插值。 3 更新 更新的思想是通过寻找允。，从而使得对于某一个度量标准q o ，例如平均 值，允。和凡具有相同的值： 1 8 用硬件实现小波变换及其重构的研究 q ( 丸) = q ( 凡) 考虑使用已计算出的小波h 来更新丸，从而使五。保持上述性质。换句话 说，我们构造一个操作u 并如下更新冠。： 允，= 丸。+ u ( 丘1 ) 重复这个算法，从而得到了以下的小波变换公式： 声，= 一1 幻一万 f 乃，乃) = 勋胁( 乃+ 。) 乃一= 尸( 乃) l-乃+ = u ( 乃) 对于提升算法，如果我们得到了前向变换，就可以立即得到逆向变换，需要 做的只是改变加减的符号。这是提升算法的一个很优良的特性。逆向小波变换如 下所示： 乃兰飘 由此，我们得到了提升算法的有效的实现步骤。即任何有限长的双正交滤波 器都可以从基本小波开始，通过有限数目的预测和更新步骤得到。实现提升算法 的关键是寻找合理的预测函数和更新函数“射。 重构过程是上述过程的逆过程，也包括三个步骤，恢复更新，恢复预测及合 并。 从上面的叙述可以看到，提升格式有如下四个显著的特点h 翮：可以实现更快 速的小波变换算法，一般通过提升方法可以达到比m a l l a t 算法快2 倍的离散小 波分解。 l 、提升小波可以实现完全的复位( n p l 撤) 运算。 2 、利用提升方法，正向小波变换和反向变换结构是非常一致的，仅有正负号的 区别。 1 9 用硬件实现小波变换及其重构的研究 3 、可以方便的实现整数小波变换。 对于第一代小波而言，提升格式是一种比常用的m a l l a t 算法更为有效的快 速算法。d a u b e d l i 懿证明，任何用m a l l a t 算法实现的单小波变换都可以改用提升 格式来实现。 2 5 本章小结 本章首先简单介绍了小波变换重多分辨分析等的基本概念，在此之后重点阐 述了小波变换当中的提升小波变换，包括提升小波的定义，提升小波的变换流程， 分析出了提升方案相对于m a l l a t 算法的优势。 用硬件实现小波变换及其重构的研究 第三章小波变换及重构的硬件架构 不同于传统的d c t 变换，小波变换具有对信号进行多分辨率分析和反映信号 局部特征的特点。通过对图像片( t i l e ) 进行离散小波变换，得到小波系数图像， 而分解的级数视具体情况而定。小波系数图像由几种子带( s u b b 觚d ) 系数图像组 成。这些子带系数图像描述的是图像片水平和垂直方向的空间频率特性。不同子 带的小波系数反映图像片不同空间分辨率的特性。对图像信号进行多级小波分 解，可得到不同空间分辨率的图像逼近，使得压缩码流具有空间分辨率可分级的 特性。这一特点为图像做部分压缩解码提供了依据。 m a l l a t 算法的计算量大，占用硬件面积和功耗大。而提升小波变换算法克服 了m a l l a t 算法的缺点，并且5 3 提升小波已经应用到数字图像压缩标准j p e g 2 0 0 0 中。目前，很多学者对小波变换的硬件结构进行了有效研究一1 。 本章主要对离散小波变换( d w t ) 及其重构的硬件实现问题进行研究，详细分 析了提升式离散小波变换及重构的过程并在此基础上对整个算法进行了硬件架 构设计研究。本课题针对j p e g 2 0 0 0 标准推荐的既可用于有损压缩又可用于无损 压缩的l eg a l l5 3 小波基进行研究。对图像进行压缩编码，需采用二维小波变换。 二维小波变换包括小波行变换和小波列变换，先进行哪种变换并不影响最终结 果。先进行小波行( 列) 变换，再进行小波列( 行) 变换，需要大量的存储空间， 计算延迟大，影响硬件实现的速度。本文采用行列并行处理的方法，相应的增加 一些控制逻辑，提高了变换速度。具体实现时，对图像边缘都要进行周期对称延 伸，这样可以防止滤波器对图像边缘操作时产生失真。 3 1 v l s i 简介 3 1 1 概述 自从1 9 5 8 年集成电路诞生以来，经历了小规模( s s i ) 、中规模( m s u 、大规模 ( l s i ) 的发展过程。目前己进入超大规模( v l s i ) 和甚大规模集成电路( u l s i ) 阶段，是一个“s y s t e mo nc h i p 的时代。目前集成电路已进入深亚微米工艺时 代，集成电路技术迅速向着更高集成度、超小型化、高性能、高可靠性的方向发 2 l 用硬件实现小波变换及其重构的研究 展。一个芯片上将可集成高达几亿到几十亿个晶体管。过去的4 0 多年里集成电 路的发展一直遵循着摩尔定律：集成电路的集成度每一年半增加一倍嗍。 美国半导体工业协会( s i a ) 制定了美国半导体技术发展蓝图( n t r s ) ，如下 表3 1 是发展蓝图的部分指标。 表3 一l 发展规划指标 1 9 9 71 9 9 92 0 0 12 0 0 32 0 0 62 0 0 92 0 1 0 最小线宽 o 2 5 0 1 8 o 1 5 0 1 3 o 1 0 0 0 7 o 0 5 ( 胁) d r a m2 5 6 m l g未定4 g1 6 g6 4 g 2 5 6 g 容量 每片晶体管数 1 1 m 2 l m4 0 m7 6 m2 0 0 m5 2 0 m1 4 0 0 m 芯片尺寸 2 8 0 1 0 04 0 0 1 4 04 4 5 1 6 05 6 0 2 0 07 9 0 2 8 0l1 2 0 3 9 01 5 8 0 5 5 0 ( 平方毫米) 频率( 兆赫) 7 5 01 2 0 01 4 0 01 6 0 02 0 0 02 5 0 03 0 0 0 金属化层层数 6 6 7 777 8 8 9 9 最低供电电压 1 -