（计算机应用技术专业论文）基于提升小波的图像压缩与检索技术.pdf

摘要 随着经济的发展、科技的进步，图像作为种信息传播方式越来越被人们所 重视。然而由于图像存储和传输占用太多的空间和带宽，因此，寻求有效的图像 压缩编码方法具有重大意义。近2 0 多年来，多种图像压缩技术和标准被提出：如 基于离散余弦变换( d c t ) 的j p e g 标准能够在不降低图像质量的基础上成倍降低 图像存储空间，后又提出的基于离散小波变换( d w t ) 的j p e g 2 0 0 0 标准比j p e g 效果更好。但d w t 算法复杂，耗时较长，一直是个待解决的问题。提升小波算法 因其计算简单，克服了传统小波卷积运算的复杂性而被提出，并已成为图像编码 的重要技术之一。 本文先对基于邻域预测、基于线性预测和基于双线性预测的提升算法，进行 了研究，并结合s p i h t ( s e tp a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s ，分层树中分配样本图像 编码) 算法，对图像进行嵌入式编码。实验结果表明，在同样的比特率和同样分解 级数的情况下，对于纹理丰富的图像，基于双线性预测提升的小波图像编码算法， 具有更好的图像主客观质量，最差的是基于邻域的预测方法，而线性预测方法则 介于两者之间。 图像存储量降低带来了图像存储和传播的便利，网络带宽提升带来了多媒体 网络的发展，但如何从浩瀚的多媒体信息中找出需要的图像信息已成为研究人员 所面临的难题，为此，图像检索技术应运而生。其中基于小波的图像检索技术是 目前研究的热点之一。 本文利用提升小波算法，对图像检索进行了研究，一方面我们对提升小波压 缩域的图像检索进行了分析，在算法中采用了两种特征提取的方法来进行检索， 一种是基于能量和、代数和的方法，一种是基于直方图的方法。另一方面，我们 对提升小波变换后的小波系数进行统计分析，分别求解提升小波系数的能量、均 值和方差，以此作为特征向量进行检索，并提出了一种基于小波系数二进制直方 图的图像检索方法，取得了较好的检索效果。 关键词：小波变换提升图像压缩图像检索 a b s t r a c t w i t he c o n o m i cd e v e l o p m e n ta n ds c i e n t i f i ct e c h n o l o g yp r o g r e s s i m a g ea saw a yt o d i s s e m i n a t ei n f o r m a t i o nm o r ea n dm o r ep e o p l ew e r ep a y i n ga t t e n t i o n a sar e s u l t ，t h e s e a r c hf o re f f e c t i v ei m a g e c o m p r e s s i o nc o d i n gm e t h o di so fg r e a ts i g n i f i c a n c e t h r o u g h y e a r so fd e v e l o p m e n t ，av a r i e t yo fi m a g ec o m p r e s s i o nt e c h n o l o g i e sa n ds t a n d a r d sh a v e b e e nr a i s e d ，s u c ha st h ej p e gs t a n d a r db a s e do nd i s c r e t ec o s i n et r a n s f o r m ( d c t ) t o r e d u c es t o r a g es p a c ew i t h o u tl o w e r i n gt h eq u a l i t yo fi m a g e s 。a n dt h e nr a i s e dj p e g 2 0 0 0 s t a n d a r db a s e do nd 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 sb e t t e rt h a nj p e gd w t a l g o r i t h m ，b u tal o n g e rt i m e - c o n s u m i n ga n dc o m p l i c a t e d ，h a sb e e nap r o b l e mt ob e s o l v e d b e c a u s eo ft h es i m p l ec a l c u l a t i o n ，t h el i f t i n gw a v e l e to v e r c a m et h ec o m p l e x i t y o fc o n v o l u t i o no ft r a d i t i o n a lw a v e l e t ，h a sb e c o m ea ni m p o r t a n ti m a g ec o d i n g t e c h n i q u e s b a s e do nn e i g h b o rp r e d i c t i o n ，l i n e a rp r e d i c t i o na n dt h ed o u b l el i n e a rp r e d i c t i o n ， t h i sp a p e rm a i n l ys t u d i e so nt h el i f t i n gw a v e l e t c o m b i n e dw i t l ls p i h ta l g o r i t h mt o e m b e d d e dc o d i n go ns t a n d a r di m a g e s u n d e rt h es a m eb i tr a t ea n dt h es a m el e v e lo ft h e d e c o m p o s i t i o n ，t h er e s u l t so fe x p e r i m e n ts h o wab e t t e ri m a g eo ft h eo b j e c t i v ea n d s u b j e c t i v e q u a l i t yw h i c hi sb a s e do nt h ed o u b l el i n e a rp r e d i c t i o nf o rt h er i c ht e x t u r eo f t h ei m a g e a n dt h ee x p e r i m e n ta l s os h o w st h a tt h ew o r s ti st h el i f t i n gw a v e l e tb a s e do n n e i g h b o r h o o dp r e d i c t i o n ，a n dt h el i f t i n gw a v e l e tb a s e do nl i n e a rp r e d i c t i o nm e t h o di s s o m e t h i n gi nb e t w e e n t h er e d u c i n go fa m o u n to fi m a g es t o r a g eb r o u g h tt h ec o n v e n i e n c e o fi m a g e s t o r a g ea n dd i s s e m i n a t i o n n e t w o r kb a n d w i d t hu p g r a d eh a sb r o u g h tt h ed e v e l o p m e n to f m u l t i m e d i an e t w o r k b u th o wt of i n do u tt h ei m a g ei n f o r m a t i o nw en e e df r o mt h ev a s t m u l t i m e d i ai n f o r m a t i o nh a sb e c o m et h ed i f f i c u l tp r o b l e mt h er e s e a r c h e r sf a c e d t h e r e f o r e ，i m a g er e t r i e v a lt e c h n o l o g yc a m ei n t ob e i n g i m a g er e t r i e v a lb a s e do n w a v e l e tt r a n s f o r mi so n eo f t h eh o ts p o t s 。 t h ep a p e rd o e st h er e s e a r c ho ni m a g er e t r i e v a lt h r o u g ht h e l i f t i n gw a v e l e t a l g o r i t h m o nt h eo n eh a n d ，w ea n a l y s e so nt h ed o m a i no fc o m p r e s s i o no fl i f t i n g w a v e l e t w eh a v e p r o p o s e dt w o k i n d so fi m a g er e t r i e v a l a l g o r i t h m s t oe x t r a c t e i g e n v a l u e t h ef i r s tw a yb a s e do nt h ee n e r g ya n da l g e b r a ，a n o t h e rw a yt a k e so nt h e 2 i m a g eb i s t o 莎a ms t a t i s t i c s o nt h eo t h e rh a n d ，w ed os t a t i s t i c a la n a l y s i so nt h ew a v e l e t c o e f f i c i e n t so ft h el i f t i n gw a v e l e t w eu s ec o m b i n a t i o no fe n e r g y , m e a na n dv a r i a n c et o e x t r a c te i g e n v a l u e a n da l s ot h ep a p e rp r o p o s e sb i n a r yh i s t o g r a mo fc o e f f i c i e n t sf o r i m a g er e t r i e v a l ，t h er e s u l to f t h ee x p e r i m e n ti sb e t t e rt h a no t h e r s k e yw o r d s ：w a v e l e tt r a n s f o r m ，l i f t i n g ，i m a g ec o m p r e s s i o n ，i m a g er e t r i e v a l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果尽我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得江西财经大学或其他教育机构的学位或证书所使用 过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其 他复制手段保存论文 ( 保密的论文在解密后遵守此规定) 签名：翟直这二喜师签名：弛日期： 1 绪论 1 绪论 1 1 前言 随着计算机网络技术、信息处理技术的发展，人们对资源及信息的需求不断 增强。众多资源中图像信息给人最直观的感受，是人们认识世界的重要方式之一。 图像包含的信息虽然非常丰富，但由于数据量大，为了便于存储与传输就需要人 们对图像进行处理。因此，寻求有效的图像压缩编码具有重大意义i l 】。 2 0 世纪8 0 年代末期小波变换被首次引入图像处理，小波变换以其优良的时频 局部化能力和去相关能力在图像处理领域得到广泛的应用。作为一种多分辨率分 析方法，小波分析具有很好的时频局部化特性，十分适合按人眼视觉特性设计图 像编码方法，也非常有利于图像信号的渐进传输。在实际应用中，基于小波变换 的图像编码，在压缩比和编码质量方面均优于传统的变换编码。但传统第一代小 波变换是在欧式空间内通过基底的平移和伸缩构造小波基的，不适合非欧式空间 的应用。19 9 6 年s w e l d e n s 提出的提升小波为传统小波变换提供了一种更快、更简 洁的实现方法。提升小波变换的提出，为小波图像编码注入了新的活力，与传统 小波变换相比，它不依赖于傅立叶变换，计算简单，时间、空间复杂度低，易于 实现，并且可以实现图像的完全无损编码，被称为第二代小波变换。 同时随着信息需求的扩大，并在数据库系统和图像处理技术发展的支持下， 图像检索技术已经成为一个新热点领域。图像检索技术经历两个发展阶段。第一 个阶段是传统的图像检索阶段。传统的检索技术是基于关键字的检索，首先先对 图像用文字描述出来，提取其中关键字，通过关键字进行检索。这种检索方法并 不能真正表达图像所传达的意义。因此在2 0 世纪9 0 年代，学者们提出了一种“基 于内容的图像检索 ( c o n t e n d e d b a s e di m a g er e t r i e v a l ，c b i r ) 技术，c b i r 是从图 像数据本身出发，从数据中发现规律，以此为依据进行图像检索。基于内容的图 像检索大大减少了人们的主观性对搜索的影响，是一种真正意义上的图像检索 4 1 。 1 2 研究现状 1 2 1提升小波在图像处理中的应用 在数字图像压缩编码中，基于小波变换的图像编码技术较其他编码技术效果 较好，并且被越来越多的运用于三维图像压缩。基于小波变换的图像编码较好， 是因为解码器对收到的码流进行图像重构时，有较好的率失真性能，并具有以下 良好的特性f 5 】：( 1 ) 信号能量大多分布在低分辨率的子带上，因为大部分图像本质 上都是低通的；( 2 ) 高频子带上的系数大都为零；( 3 ) 小值或者零值的系数( 即不重要 基于提升小波的图像压缩与检索技术 的系数) 聚集在一个给定的子带上；( 4 ) 在一个子带上的不重要系数串和相同方向的 下一高分辨率子带上的相似串有相同的相关位置。 近年来，国内外许多专家开始研究一种新的小波结构，称为第二代小波。是 一种不依赖傅立叶变换的小波，它的运算仅用了简单的卷积，极大降低了运算复 杂度，但得到的子带结构与传统线性小波类似。1 9 9 4 年s w e l d e n s 6 】提出了提升小 波，它不依赖傅立叶变换，包含三个步骤分裂，预测，更新。随后，提升小 波被应用于各个领域：图像压缩，去噪，特征提取等【7 一】。在预测阶段由于图像的 特征不同，如果采用同样的预测策略得到的变换后效果往往不是最好，在这种情 况下，0 m e r n g e r e k 等人提出一种自适应预测方法来满足不同图像的要求。这种 方法在预测时充分利用了像素周围相关性的特点，而不是仅仅从像素左右来进行 预测。它利用设定门限值来实现自适应【9 】。国内一些专家在自适应提升小波结构上 也作出了贡献和成绩【1 0 1 。国防科大科技学院的研究人员提出了一种新的自适应提 升小波变换，指出传统二维小波变换由于是通过在水平方向和垂直方向变换得来 的，当图像纹理和方向上的特征非常丰富时传统二维小波变换不能有效的展现方 向信息，这是传统小波变换在图像压缩方面的缺陷，基于这些提出一种新的自适 应d w t 变换，提出基于图像局部内容对图像进行分割，而且为了保存纹理等信息 的完整，+ 在预测方向时对半像素进行插值【1 1 1 2 3 1 。 提升小波变换不仅用于图像压缩，也被用于物体的检索识别。m a m i r i 等提出 了一种新的自适应提升结构，来找出在一组图片中被用户所选择的物体。首先在 小波变换中选择一种物体的特征，然后利用这些被选择的特征建立自适应变换。 这种自适应变换是在提升过程中的自适应预测建立起来的。其中提到非自适应变 换的高通子带中较大的系数会在自适应高通子带中消失【1 4 】。在提升结构的基础上， o e m m ap i e l l a 等人提出了一种包含三个步骤的非线性的提升结构，它能够在保留 图像的轮廓时产生很少的大细节系数【1 5 j 。 提升小波变换用分裂、预测和更新代替了传统小波变换复杂的卷积运算。最 开始出现的提升小波变换是先进行预测再进行更新，如图1 1 所示，而在1 9 9 7 年 d a v i s 提出了一种先更新后预测的方法，如图1 2 所示。这种方法比传统提升变换有 更多的优点。在传统先预测后更新的提升变换中，低频系数是通过预测器和更新 器形成的，而在新提出的先更新后预测方法中，低频系数是不受非线性预测器影 响，直接由输入信号通过更新器形成并直接进入到下一轮的小波分解中。因此可 以看出先更新后预测的提升小波变换有利于系统稳定，并提高了系统运行速度【l 酬。 【力】 八 图1 - 1 先预测后更新的提升结构 蹦聆】 八 图1 - 2 先更新后预测的提升结构 1 绪论 刀 聆 r l r r l“上虹 基于提升小波的图像压缩与检索技术 1 2 2 图像压缩算法的研究现状 对于视频和图像来说，同等通信容量下，对其进行压缩后再传输，可使传输 的数据量变小，可以减轻信道的负担。由于图像数据中存在大量冗余信息，如空 间冗余、信息熵冗余、视觉冗余等，图像压缩就是尽可能地去掉冗余信息，保留 有用信息。因此，研究具有高压缩比且压缩后视频或图像有较高清晰度的压缩编 码是研究热点。 基于小波的压缩编码实质是对小波变换后的系数进行量化压缩。图像经过小 波变换后生成的小波图像数据总量与原图像数据量是相等的，即小波变换本身并 不具有压缩功能。之所以将它用于图像压缩，是由于生成的小波图像与原图像具 有不同的特性，表现在图像能量主要集中于低频部分，而水平、垂直和对角线部 分能量则较少，只要适当的对高频进行编码压缩就能实现图像和视频的压缩。 j p e g 2 0 0 0 就是基于小波变换的图像压缩标准，能够在减少存储量的同时保证好的 图像质量， 1 9 8 9 年m a l l a t 首次将小波变换用于信号处理，并提出了多分辨率分析的概念。 1 9 9 2 年s h a p i r o 提出了嵌入式小波零树编码，零树小波算法是一个简单的，但非常 有效的图像编码算法，是小波图像编码的一个里程碑【l 。7 1 。e z w 编码是一个由粗到 细的渐进化过程，量化阈值由大到小，精度也是由粗到细i l 引。s m g h y u nj 0 0 将 e z w 算法塔式结构中的父代和子带关系进行进一步研究，得出如果父代系数是重 要的，其子带系数也是重要的概率就相对比较大，并且这种关系可以推广到空间 距离较近的系数，由此得到一种更加简单灵活的改进e z w 算法。s p a t e l 提出在每 次扫描过程中，当碰到不重要的系数时就进行标记，在以后的扫描过程中就跳过 这些不重要的系数，从而减少了扫描时间，提高了e z w 的运行速度。a o u a f i 进 一步对e z w 进行改进，提出了如果父代系数是重要的，那么其对应的所有子带系 数都被认为是不重要的【1 9 j 。 近年来，在e z w 的基础上提出了许多改进算法，分层树中分配样本图像编码 ( s p i h t , 即s e tp a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s ) 方法就是最经典的一种。s p i h t 算法是 a s a i d 和w a p e a r l m a n 在1 9 9 6 年提出的，性能优于e z w 算法。s p i h t 算法采用了 有效的空间方向树结构和比特平面编码方法，能获得高压缩编码效率的嵌入式码 流，支持解码器的多码率解码，同时有利于图像的渐进传输。在基于小波变换的 图像编码中，s p i h t 被认为是目前效率较高的算法之一【2 0 ，2 1 1 。许多专家和学者都对 s p i h t 算法进行了改进，1 9 9 8 年w e nk u ol i n 和n b u r g e s s 提出了无表零树编码算法 l z c 。该算法利用2 个标志位代替了s p i h t 算法中的三个集合，降低了内存的占有 率，缺点是在某种程度上降低了编码器的性能。f w w h e el e r 和w a p e a r l m a n 在2 0 0 0 年提出了n l s ( n ol i s ts p i h t ) 。该算法是基于s p i h t 中的零树思想和集合分割策略， 4 1 绪论 通过状态表记录已经编码的系数，去除了s p i h t 中三个集合链表。文献 2 2 】提出根 据高频子带第一分量无效值的分布来预测其他三个分量上不重要系数的位置，从 而减小无效集合判别过程中的扫描次数，提高编码速度。 1 2 3 图像检索的研究现状 随着数据库技术和计算机技术的迅猛发展，文字描述已满足不了人们的需求， 图像、视频以及其它一些可视信息被认为是表达信息的最有效方式，所以图像作 为一种信息传输媒介在网络上大量存在，但如何快速而有效的从众多图像中寻找 到所需的图像信息已成为目前研究的焦点。 图像检索经历了两个阶段，第一个阶段是基于关键字的图像检索，但这种方 法有很多的不足。首先，图像包含的信息较多，数据量也比文字信息大，所以很 难用文字来完全表达图像中所包含的信息，所以简单的对图像关键字的检索本身 就存在缺陷。其次，用来检索的关键字都是人为提取出来的，所以带有很强的主 观因素，同一副图片不同的人有不同的理解。并且如果每幅图的关键字都由人提 取的，网络中各种图像信息是海量的，那么这种工作量将无法衡量【2 引。 实际上，图像本身就包含丰富的信息，是否可以考虑直接从图像中提取信息， 而不用通过关键字作为中介，这就是图像检索的第二个阶段基于内容的图像 检索。与第一阶段的基于关键字的图像检索相比，基于内容的图像检索有以下几 个特剧2 4 1 。 ( 1 ) 直接从图像数据中提取检索信息。基于内容的图像检索没有认为用文字 进行标记，减少了检索过程的主观性，能充分挖掘图像内在的信息以及包括人眼 无法察觉的信息。 ( 2 ) 基于内容的图像检索能减少检索的数据量。限于计算机内存的有限性， 必须先对数据库中的图像进行处理i 从中提取出图像的特征信息。现在已经有很 多的特征提取法，例如采用灰度直方图以及基于小波的提取法。 ( 3 ) 基于内容的图像检索采用的是一种近似匹配法。即在检索过程中，没有 “一样”的概念，只有最匹配的概念。所以从人的主观方面去观察图像，检索结 果中允许有不相关的图像出现。 9 0 年代初许多研究者们开始将小波变换用于图像检索中【2 5 1 。基于小波的图像 检索算法是把图像进行离散小波变换，分解成低频信息和高频信息，从中提取出 特征进行检索，利用这些特征进行图像相似度匹配。c h a n g 2 6 1 等人利用各子带能量 作为特征值进行检索，并与d c t 变换、空域方法进行比较。s m i t h z 7 j 等人提出了 基于小波变换的纹理识别算法。该算法先对图像进行三级小波变换，计算高频子 带的幅度值，每个高频子带的系数通过上采样恢复到与原图像同样大小的尺寸， 基于提升小波的图像压缩与检索技术 得到9 个高频通道，所有通道中位置相同的系数构成一个9 维向量，然后对每个 向量中的系数进行二值化处理，处理后的向量分为5 1 2 个向量，因此可以构造5 1 2 级统计直方图，最后利用直方图作为特征值来进行检索。这种方法得到的检索效 率比较高，但是计算复杂度太大，不利于广泛推广。m a i l d a l 【2 8 】等人提出了一种改 进的直方图检索方法，在保证检索性能的情况下降低计算复杂度。与其他方法不 同的是m a n d a l 等人把小波分解后的子带统计直方图作为特征值用于图像检索。他 们认为不同的图像可能具有相同的统计直方图，但图像小波分解后的子带统计直 方图不可能完全相同。本文在上面研究成果的基础上提出一种基于压缩的图像检 索算法，算法简单易实现，也能有效节省网络和硬件资源。 1 3 论文安排与主要工作 论文安排如下： 第一章提出了整个论文的框架，描述了论文图像压缩与检索的研究内容、研 究背景。其中包括提升小波的提出、发展历程，图像压缩的整个流程以及图像检 索的内容和框架，最后列出本文的安排与主要工作。 第二章叙述了小波的基础理论、提升小波的基本理论以及传统小波向提升小 波的转换过程，并对三种基本的提升算法进行分析。 第三章描述了几种小波编码算法，其中包括e z w 算法和s p i h t 算法，将s p i h t 算法用于提升小波，并且通过与第二章的三种提升小波算法结合，对比其性能和 实验结果。 第四章对基于提升小波的图像检索方法进行分析，包括基于压缩的和基于变 换的图像检索算法，而基于压缩的图像检索算法还包括基于能量和和代数和的方 式以及基于直方图的方式。基于变换的图像检索算法包括采用能量、均值和方差 的组合作为特征提取的方法及基于二进制直方图的方法。 第五章对所有实验的结果和分析做出总结，发展与展望。 6 2 小波与提升小波变换 2 小波与提升小波变换 2 1 小波基础理论 小波作为2 0 世纪8 0 年代末期出现的一种时频分析工具，不论是对数学还是 工程应用都产生了深远影响。短短十几年间，它在很多领域都得到广泛应用和发 展，如：信号处理、图像处理、理论数学、模式识别、分形等。小波分析在信号 分析方面所表现出来的优良特性使其成为众多领域中强有力的研究工具。尤其值 得一提的是小波理论在图像处理领域的发展，如图像去噪、图像压缩等，其中所 取得的成就数不胜数。而f o u r i e r 分析作为早期的时频分析工具，对小波分析的发 展提供了巨大帮助。理论上讲，凡是使用f o u r i e r 分析的地方，都可能用小波分析 来代替，它被认为是近年来工具及方法上的重大突破，被誉为“数学显微镜”。 近年来，从对f o u r i e r 缺陷的分析促进了小波理论的形成，在传统的信号分析 过程中，f o u r i e r 变换不能同时得到信号的时域和频域特性，而小波采用可变的时 频窗口来对信号进行局部性分析，有效的克服了f o u r i e r 分析的不足，因此，理论 上说一切基于f o u r i e r 变换的应用都可以用小波变换来代替【2 9 1 。本节主要描述小波 变换的基本概念。 2 1 1连续小波变换 连续小波变换的概念是在1 9 8 4 年由m o r l e t 在使用一些修正的傅立叶变换窗口 来分析物理信号时提出的，定义如下【3 0 】：设l 2 ( r ) 是一个可测出的、平方可积的一 维矢量空间，r 为实数集合。小波则是由满足【y ( ，) 班= 0 的函数( f ) 通过平移、 缩放等操作而产生的二个函数族儿。( ，) ，如式( 2 1 ) 所示 暇i 口，6 ) ： p ( ，) 沙( 丝) d t = ( 2 1 ) a a 其中，a 0 、b 和t 为连续变量，x ( t ) 是平方可积函数，缈( f ) 为基本小波或 母小波的函数，j c ，( ，) 是( ，) 的复共轭函数。并且 1f y 口6 = y ( 三二) ( 2 2 ) 、a a 连续小波变换的公式具有很重要的意义【3 。其中的基本小波沙( f ) 有可能是复 信号，也有可能是实信号。当它为复信号时，通常是表示为解析信号或近似解析 f 2 信号，如m o r l e t 小波( f ) = et e 州。m o r l e t 小波是以高斯函数为包络的复指数函 数。复信号的小波变换主要用于对信号频率的估计与跟踪，实信号的小波变换则 是用于检测信号的变换处理和信号的瞬变特性。 在公式( 2 1 ) 中。变量a 反映的是函数的尺度。a 越大，炒( 三) 越宽，a 越小， 7 基于提升小波的图像压缩与检索技术 ( 二) 越窄，变量b 反映的是小波函数在t 轴上的平移位置。母小波( f ) 的能量主 口 要集中在原点附近，小波函数柚( f ) 的能量则主要集中于b 点。 小波变换后的重构公式为： f ( t ) = f 1e 黠w z f ( a , 啪础o ) a a d b ( 2 3 ) 一 ” 无论在连续小波变换的公式( 2 1 ) 还是在重构公式( 2 3 ) 中，变量a ，b 和t 均是连续的变量，故称为连续小波变换。连续小波变换具有以下特性：( 1 ) 线性 性。一个连续的小波变换等于各个分量的小波变换之和。( 2 ) 平移不变性。平移 不变性指的是将信号退迟“时得到的系数就是把原来的小波系数在时间轴上平移 “。( 3 ) 自相似性。对于不同的变量a 和变量b 的连续小波变换之间是自相似的。 ( 4 ) 冗余性。经过小波变换后得到的信息是冗余的。 2 1 。2 离散小波变换 通常在实际应用中应用到的都不是连续小波变换，因为由以上的连续小波变 换的性质我们得知，连续小波变换在变换之后得到的信息是存在冗余的，所以我 们就设想在理想情况下，可不可以得到一组离散后小波基函数是正交完备性条件 的，而此时得到的变换后的信息是没有冗余的，这样就对数据量进行了压缩。这 里所提到的离散指的是对变量a 和b 的离散，而不是指对t 的离散。 我们在连续小波变换的基础上对参数a ，b 进行离散，令a - 2 吖，b = 七2 一j ( ，k z ) ，则离散小波变换的公式为： 啊( ，尼) = 2 ? 厂( ，渺( 2 卜七渺 r ， d 、 然而，怎样选择a 和b ，才能够保证重构信号的精度呢? 显然，即a 和b 尽可 能小，因为如果网络点越稀疏，使用的小波函数少m ( f ) 和离散小波系数啊( ，- k ) 就 越少，信号重构的精确度也就会越低。上面是对尺度参数a 和平移参数b 进行离 散化的要求j 为了使小波变换具有可变化的时间和频率分辨率，适应待分析信号 的非平稳性，我们很自然地需要改变a 和b 的大小，以使小波变换具有“变焦距” 的功能。换言之，在实际中采用的是动态的采样网格。最常用的是二进制的动态 采用网格，即a = 2 ，b = l ，每个网格点对应的尺度为2 ，而平移为2 j k 。由此得到的 小波序列则称为二进小波【3 2 匕 2 1 3 多分辨率分析理论 s m a l l a t 在1 9 8 6 年将计算机视觉领域内的多分辨率分析的思想巧妙地引入到 小波分析中，从而统一了在此之前各种小波基的构造方法，并给出了一种子带滤 2 小波与提升小波变换 波器结构的离散小波变换与重构算法。这一算法在小波分析中的地位相当于经典 f o u r i e r 分析中的f f t 的地位，奠定了离散小波变换在图像处理、图像编码等领域中 的应用基础。多分辨率分析的思想来自干计算机视觉理论。从机器视觉的角度而 言，单纯从灰度信息理解一幅图像中的物体是很困难的，更重要的是图像中灰度 的局部变化。为了能够较好地理解一个物体，表达这种局部变化的尺度应该与物 体的大小适配。然而在一般的图像中，需要理解的各种结构拥有不同的大小。因 此不可能预先定一个最佳的分辨率来描述他们。为解决这一难题，在计算机视觉 中采用了不同的分辨率来处理图像中不同信息的方法，将图像在各种分辨率下的 细节提取出来。得到一个拥有不同分辨率，f ( ，z ) 的图像细节序列。其中，分辨率 时图像细节定义为：在分辨率下对图像的逼近和在分辨率，下对图像的逼近之 差。这种多分辨率的表示提供了一种图像信息简单的分层描述，在不同的分辨率 下，图像的细节刻划了不同尺度的物理结构。在粗分辨率时，这些细节表示了大 的结构信息，提供了图像的“上下文( c o n t e x t ) 描述。因此，很自然地应该完整分 析这些信息。然后逐渐增加分析精度。这种由粗到细的分析过程己经广泛应用在 立体视觉匹配和模扳匹配中，并且表明与人眼的低级视觉处理是根相似的。关于 分辨率的层次划分，考虑到计算和推导的方便以及入眼的视觉特性，一般采用倍 频程划分，即分辨率取值为2 。 我们先从理想滤波器组粗略地引入多分辨率分析的概念，然后再从函数空间 的剖分上进一步加以阐述。 当信号x ( n ) 的采样频率满足采样定理时，数字频带限制在一7 7 之间。此时 可分别用理想低通滤波器与理想高通滤波器将它分解成( 对正频率部分而亩) 频带 在0 刀2 的低频部分和频带在万2 万的高频部分，分别反映信号的概貌与细节。 处理后的两路输出必定正交( 因频带不交叠) ，而且由于两种输出的频带均减半，因 此采样率可减半而不致引起信息的丢失。 类似的过程对每次分解后的低频部分可重复进行下去，即每一级分解把该级 输入信号分解成一个低频的粗略逼近和一个高频的细节部分。而且每级输出采样 率可以再减半，这样就将原始信号x ( n ) 进行了多分辨分解。以上只是对多分辨分 析的粗略说明，结论不够全面。m a l l a t 从函数空间的剖分上作了进一步的阐述。在 二等分情况下，m a l l a t 从函数空间的分解出发，在小波变换与多分辨分析之间建立 起联系。把平方可积函数x ( t ) 看成是某一级逼近的极限情况。每级逼近都是用某 - - i l 毛通平滑函数对x ( t ) 平滑的结果，只是逐级逼近时平滑函数也作逐级伸缩。也 就是用不同分辨率来逐级逼近待分析函数i j 川。 从实际角度出发，大多数离散小波都不是p ( r ) 上的正交基，所以变换后的信 息量仍然存在冗余，而多分辨率分析理论就是构造正交基的方法之一。多分辨率 9 基于提升小波的图像压缩与检索技术 分析的定义如下【3 4 】： 一个多分辨率分析由一个嵌套的闭子空间序列组成，它们满足 以c _ c ck l ( 2 2 旷2 ，并且满足 ( 1 ) 上完整性u = 工2 ( 尺) ； 肼z ( 2 ) 下完整性n = o ) ； m e z ( 3 ) 尺度不变。i v y x ( t ) 吃营x ( 2 ”t ) v o ； ( 4 ) 位移不变性x ( ，) v ojx ( t - n ) v o ，刀z ； ( 5 ) 存在一个基缈v o ，使得 缈( f 一刀) ，z ) 是的r e i s z 基。 最初实现多分辨率分解的方法是b u r t e t a l 提出的金字塔分解算法。m a l l a t 对信 号的逼近和细节的抽取进行了深入的研究，发现在多分辨率下对信号逼近可以通 过对r ( r ) 中一个稠密空间序列的投影来实现，而且得到的信号细节刚好是按照一 组小波基的展开。从而推导出了快速的离散小波变换算法m a l l a t 算法，为构造小 波基提供了最有效的方法。2 1 4 将简要介绍m a l l a t 算法。 2 1 4m al la t 算法 m a l l a t 在著名金字塔算法( p y r a m i d a la l g o r i t h m ) 启发下，结合多分辨分析，提出 了信号的塔式多分辨分解与综合算法，即简称为m a l l a t 算法。 设o ) r 俅) ，并假定已得到f ( t ) 7 e e2 分辨率下的粗糙象a j f 巧， 杉j ，z 构成r 伍) 的多分辨分析，从而有= + ，o + ，即 彳，f = a j + i f + o j + l f ( 2 5 ) 式中a j f = c j a o ) 为第j 尺度上对信号的近似，q 厂= d j , k 乒o ) 表 k = - - k = - - - 示在信号在第i 尺度上的细节。 因此可得 c j 力，。o ) = c j + l , k 矽川，。( f ) + q + l k 缈j 扎。o ) ( 2 6 ) 七= k = - o o 七= 由尺度函数的双尺度方程可得 力扎。o ) = h ( k - 2 m 切j , k o ) 七= - - 0 0 利用尺度函数的正交性，有 ( c j + l , m 纵) = 办g - 2 m ) 同理由小波函函数的双尺度方程可得 ( 驴g j + l , m “) = g ( k - 2 m ) l o ( 2 7 ) ( 2 8 ) 2 小波与提升小波变换 由式( 2 6 ) 、( 2 7 ) 和( 2 8 ) 立即可得： c 川，。= c h ( k - 2 m ) ( 2 9 ) q + l 肘，= c g g - 2 m ) ( 2 1 0 ) c = h ( k - 2 m ) c 川，+ g - 2 m ) d j + l ，。 ( 2 1 1 ) 引入无穷矩阵日= 旧。c 。o ：。：。，g = 【g 】：；。；。，其中h = | l ，( k - 2 m ) ， g 础= g 一2 历) 则式( 2 9 ) 、( 2 1 0 ) 和( 2 1 1 ) 可分别表示为： 协l2 们7 ：o ，l ，一， (212)dg c i，+ l =， 。 一 7 、 和 c ，= h + c ，“+ g + d j + l ，j = ，一l ，l ，0 ( 2 1 3 ) 其中，g 分别是h 和g 的共轭转置矩阵。 以上的正向( 分解) 和反向( 重构) 小波变换实际上可以分别看成为一组分 解和重构滤波器细： 图2 1小波分解重构滤波器组 由图2 1 中可知，输入信号被滤波后经过亚采样得到一个低通信号l p 和一个 高通信号h p ，重构过程则是在l p 和h p 中每两个点之间插入零值进行上采样。 式( 2 12 ) 为m a l l a t 一维分解算法，式( 2 13 ) 为m a l l a t 一维重构算法，如图2 2 所示： hhh g 一g 弋 ( a ) 分解算法 基于提升小波的图像压缩与检索技术 h 1hh c o 卜c 1 + 弋卜c 3 d ld 2 d 3 ( b ) 重构算法 图2 2m a l l a t 小波分解和重构算法示意图 利用m a l l a t 分解与重构算法进行信号处理时，不必知道具体的小波函数是什 么样的，此外，在对数字信号进行处理时，通常假定相应的连续函数属于70 ，但 即使如此，该函数在y0 空间的投影的系数与由采样得到的离散序列一般不一样， 但实际上都是直接把由采样得到的信号作为最高分辨率的信号来处理，这时更多 的是把小波变换当作滤波器组来看待。 2 1 5 二维小波变换 m a l l a t 提出的多分辨率塔式分解与合成算法，使得信号在小波基函数上的内积 运算转化为与相应小波滤波器的卷积运算，因此，m a l l a t 快速算法在小波分析中的 地位等同于快速傅立叶算法( f f t ) 在傅氏分析中的重要性，而且极大地促进了小波 变换在数字信号处理中的应用。从前几节的论述，我们可以得到一维小波变换的 快速实现。对于二维数字图像信号，离散小波变换可以通过在水平和垂直方向上 分别应用h ，g 滤波器进行一维滤波来实现。二维离散小波变换每次分解产生一个低 频子带l l 和三个高频子带，即水平子带l h ，垂直子图h l 和对角子带h h 。根据 上节的多分辨率分析，我们知道低频子带反映原始图像的主体轮廓信息，水平子 带l h ，垂直子带h l 和对角子带h h 分别表示图像的水平、垂直、对角方向的边缘 细节信息。下一级小波变换是在前级产生的低频子带l l 的基础上进行，如此重复 m 次，可以将原始图像分解成m 级( 3 m + 1 ) 个子带：l l m 与l h i ，h l i ，n h i ( i = l ， m ) ，其中l l m 为最低频子带。因此，原始图像经过多级小波分解后得到的是一个 低分辨率下的“近似值”和一些不同分辨率下的边缘细节子带。3 级分解过程如图 2 3 所示【3 5 】。 1 2 2 小波与提升小波变换 图像信号 二维小 波分解7 l l l l h ! h l l h h l 二维小 波分解7 二维小 波分解7 l l 2 l h 2 h l 2 h h 2 图2 - 3 二维小波变换的三级分解 l l 3 l h 3 h l 3 h h 3 2 2 提升小波 由前一节我们知道小波具有多分辨分析的特性，这也使得它在很多领域得到 很广泛的应用，而另一方面，其小波基的一个重要特性是通过一个母函数的伸缩 平移构成一个正交基，且其大部分性质都是通过傅立叶变换工具来描述的。但是 人们也会思考，在伸缩平移不可能实现的时候该怎么办呢? 而且由于卷积带来的 高运算量是小波变换不可避免的一个缺点【3 6 1 ，这不仅加大了运算量，也给研究者 们带来了不可忽视的麻烦。1 9 9 4 年s w e l d e n s 提出了基于提升算法的小波变换，这 种算法不依赖于傅立叶变换，被称为第二代小波变换。提升小波变换的运算仅仅是 利用了简单的加法运算，可