（基础数学专业论文）冗余度、提升方案以及数字水印.pdf

山东大学硕士学位论文 冗余度、提升方案以及数字水印 曹祝楼 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) 中文摘要 这篇文章主要讨论三个问题t 第一个问题是框架的冗余。我们分别在有限维 h i l b e r t 空间中和一般h i l b e r t 空闯中给出衡量框架冗余的方法；第二个问题是提 升方案，主要工作是将w i ms w e l d e n s 提出的提升方案推广，并讨论用这种推广后 的提升方案去构造m b a n d 小渡的可能性；第三个问题是数字水印，主要工作是 用基于小波变换的数字水印方法实现共享软件的注册 下面介绍一下本文的组织，本文共分三章 第一章首先给出框架的定义，并解释框架冗余的含义；接着刻画了有限维空问 中的序列成为框架的充分必要条件，给出了框架的最优界，并且指出了这种条件下 框架的冗余度与该框架的上下界之间的关系 然后我们在投有维数限制的h i l b e r t 空闻中讨论了框架的冗余度，通过框架分析算子t 的值域空同的正交余空闻刻画 了框架的冗余度，即r a n ( t ) 1 ；n ，而n 是衡量序列冗余的集合；最后我们把 这种方法用到有限维h i l b e r t 空间中得出非常有意思的结论，即框架的冗余度为t 1 + 业警吐 第二章主要工作是将w 璐s w e l d e n s 提出的提升方案推广，并讨论用这种推 广后的提升方案去构造m b a n d 小波的可能性 本章共分三节t 第一节是提升方案的编码实践。介绍提升方案，解释提升方案的优点，以及提 升方案的应用特别的我们给出图像变换的c + + 程序 第二节主要是对参考文献【4 】中的内容做一个简要介绍，引入相关概念和符 号，以便后面对提升方案的推广先后引入广义多尺度分析，有限滤波器，双正交 滤波器组，提升方案等 第三节主要是推广提升方案，关键的地方是修改【4 】中小波的定义，将小波分 成p 一1 类，从而小波空间w 分解成p 一1 个子空间，最后得到在这种设定下的 提升方案获得这个结果的过程并不复杂，只需对原文【4 中定义的符号算子g ， 山东大学硕士学位论文 分解成p 一1 个算子，再做类似运算那么为什么要做这样的推广呢? 因为：首 先 4 】中的提升方案无法直接应用在m b a n d 小波上，而推广后的提升能做到这一 点；其次对小波进行了分类推广后的提升方案可以通过矩阵更好的控制提升的 过程，处理起来更方便；虽后一点，显然原来的提升方案是推广后的提升方案的特 例，后者取p = 2 时就是前者 第三章主要工作是用基于小波变换的数字水印方法实现共享软件的注册 本章共分三节z 第一节主要介绍数字水印的基本原理和各种算法，重点介绍了基于小波变换 域的数字水印算法 第二节主要是介绍当前共享软件常用的注册方案，以及这种方法的缺陷 第三节主要是提出一种全新的共享软件的注册方案，这种方案与当前方案相 比的优点这种方案是基于数字水印的，将原来的注册密码作为水印嵌入到软件 的启动画面中 关键词t 冗余；分析算子；广义多尺度分析；提升方案；m b a n d 小波；数字 水印；软件水印 i i 山东大学硕士学位论文 r ，e d u n d a n c y l i f t i n gs c h e m ea n d d i g i t a lw a t e r m a r k i n g c a oz h u l o u ( s c h o o lo fm a t h e m a t i c sa n ds y s t e ms c i e n c e ，s h a n d o u gu n i v e r s i t y , j n i a n2 5 0 1 0 0 ) a b s t r a c t i nt h i s t h e s i s ，w e d i s c u s st h r e ep r o b l e m s t h ef i r s tp r o b l e mi sa b o u tt h e r e d u n d a n c yi nf r a m e s ，w ep r e s e n tt h em e t h o d st h o s em e a s u r et h er e d u n d a n c yi n f r a m e si nb o t hf i n i t ed i m e n s i o nh i l b e r t s p a c ea n dg e n e r a lh i l b e r ts p a c e t h e s e c o n d p r o b l e m i sa b o u th f f i n gs c h e m e o u rm a i nw o r kc o n t r i b u t e st og e n e r a l i z et h el i f t i n g s c h e m ep r e s e n t e db yw i r es w e l d e n sa n dt od i s c u s st h ep o s s i b i l i t yo fc o n s t r u c t i o no f m b a n dw a v e l e t su s i n gt h eg e n e r a l i z e dl i f t i n gs c h e m e t h et h i r dp r o b l e mi sa b o u t d i 酉t a lw a t e r m a r k o u r m a i nw o r kc o n t r i b u t e st op r e s e n t8c o m p l e t e l yn e wr e g i s t e r m e t h o do fs h a r i n gs o f t w a r ew h i c hb a s e do nd i g i t a lw a t e r m a r k t h i st h e s i s w h i c hi sd i v i d e di n t ot h r e ec h a p t e r s ，i so r g a n i z e d f o l l o w s c h a p t e r1 s t a r t sb yt h ed e f i n i t i o no ff r a m e sa n dm e a n i n go fr e d u n d a n c yi n f r a m e s 、t h e nw ed e s c r i b es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o no fs e q u e n c e sb e i n ga f r a m ei nf i n i t ed i m e n s i o ns p a c e ，a n dp r e s e n tt h eo p t i m a lf r a m eb o u n d sa n dt h e r e l a t i o n s h i pb e t w e e n t h er e d u n d a n c yr a t i oa n dt h ef r a m eb o u n d s n e x tw ed i s c u s s t h e r e d u n d a n c y 诅f r a m e s i ng e n e r a lh i l b e r ts p a c eb yo r t h o g o n a lc o m p l e m e n ts p a c e o fr a n ( t ) ，i e r ( t ) 1 = n qi st h es e tw h i c hm e a s t t r e sr e d u n d a n c yi nt h e s e q u e n c e ，w h i l et i sf r a m ea n a l y s i so p e r a t o r f i n a l l yw ea p p l yt h em e t h o di n t h et h e o r e m1 6i nf i n i t eh i l b e r ts p a c eo b t a i n i n gav e r yi n t e r e s t i n gr e s u l t s ，i , e 1 + 塑等吐 i nc h a p t e r2o u rm a i nw o r kc o n t r i b u t e st og e n e r a l i z et h el i f t i n gs c h e m ep r e - s c n t e db yw i ms w e l d e n sa n dt od i s c u s sp e s s i b i l i t yo fc o n s t r u c t i o no fm - b a n d w a v e l e t su s i n gt h eg e n e r a l i z e dl i f t i n gs c h e m e t h i sc h a p t e ri sd i v i d e di n t ot h r e e s e c t i o n s i ns e c t i o n1w ei n t r o d u c e c o n c e p t s ，a d v a n t a g e a n d a p p l i c a t i o n o fl i f t i n gs c h e m e t h e nw ep r e s e n tt h ec + + c o d e so fd w tf o ri m a g ep r o c e s s i n g i i i 山东大学硕士学位论文 i ns e c t i o n2w er e v i e wt h ec o n t e n t si nf 4 1 ，a n di n t r o d u c et h er e l a t i v ec o n c e p t a n dn o t a t i o ns u c ha sg m r a ，f i n i t ef i l t e r sa n db i o r t h o g o n a lf i l t e r s t of a c i l i t a t e g e n e r a l i z a t i o no ft h el i f t i n gs c h e m e i ns e c t i o n3w eg e n e r a l i z et h el i f t i n gs c h e m e f i r s tw em o d i f yw a v e l e t sd e f t n i t i o ni n1 4 】b ys p l i t t i n gt h ew a v e l e t si n t op 一1g r o u p s ，s ot h ew a v e l e t ss p a c ei s d e c o m p o s e di n t op 一1s u b s p a c ea n do b t a i nt h el i f t i n gs c h e m eu n d e rt h en m d i f i c a t i o n i ti sn o tc o m p l e xt oo b t a i nt h er e s u l t i nf a c to n ec a nd oi to n l yb y d e c o m p o s i n gt h en o t a t i o no p e r a t o rg ji n t op lo p e r a t o r sa n dd o i n gt h es i m i - l a ro p e r a t i o ni n 4 w h yd ow eg e n e r a l i z et h el i f t i n gs c h e m el i k et h i s ? t h e r ea r e m a n y r e a s o n s ：f i r s tt h el i f t i n gs c h e m ei n 【4 1c a nn o td i r e c t l yd e v e l o p m e n tt h el i f t i n g s c h e m ef o rm b a n dw a v e l e t sw h i l et h eg e n e r a l i z e dl i f t i n gs c h e m ec a n ；s e c o n dw e c a n c o n t r o lt h ep r o c e s so fl i f t i n gm o r ec o n v e n i e n t l yb ym a t r i x ；f i n a l l yt h el i f t i n g s c h e m ei n 【4 】i so b 、，i o u s l yt h es p e c i a lc a s eo fg e n e r a l i z e dl i f t i n gs c h e m e i nc h a p t e r3o u rm a i nw o r kc o n t r i b u t e st op r e s e n tac o m p l e t e l yn e wr c g i s t e r m e t h o do fs h a r i n gs o f t w a r ew h i c hb a s e do nd i 百t a lw a t e r m a r k t h i sc h a p t e ri s d i v i d e di n t ot h r e es e c t i o n s i ns e c t i o nlw ei n t r o d u c et h ep r i n c i p l e sa n da l g o r i t h m so fd i g i t a lw a t e r m a r k ， e s p e c i a l l yt h ed w t b a s e dd i g i t a lw a t e r m a r ka l g o r i t h m i ns e c t i o n2w ei n t r o d u c eo r d i n a r yr e g i s t e rm e t h o do fs h a r i n gs o f t w a r ea n dt h e d e f e c t so ft h i sm e t h o d i ns e c t i o n3w ep r e s e n tac o m p l e t e l yn e wr e g i s t e rm e t h o do fs h a r i n gs e f t w a r e a n dt h ea d v a n t a g eo ft h i sm e t h o d t h em e t h o di sb a s e do nw a t e r m a r k ，w h i c h e m b e d st h er e g i s t e rp a s s w o r di n t os t a r tp i c t u r eo ft h es o f t w a r e k e y w o r d s ：r e d u n d a n c y ；a n a l y s i so p e r a t o r ；g m r a ；l i f t i n gs c h e m e ；m b a n dw a v e l e t s ；d i g i t a lw a t e r m a r k i n g ；s o f t w a r ew a t e r m a r k i n g i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：雠 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：莲至塾攫导师签名：监日期：型丝! ! 第一章框架的冗余 框架是小波分析中基本的概念，各方面研究已经很成熟，在书【6 1 中做了全面 的阐述，而总结的很好的两篇文章是【7 】【8 l ，但是框架的冗余很少提及这一章讨 论了有限维h i l b e r t 空问和一般h i b e t t 空间中框架的冗余，主要结果是定理1 4 和 定理1 6 定义1 1 设日是h i l b c r t 空间， 妒。) 是h 中的序列，若存在常数0 a ，b 0 0 ， 使得 a l i 1 2s 乏二l ( ，妒。) 1 2sb l l fl 1 2 ，v ，h ( 1 1 ) 则称 ) 是打中的框架，日， 分别称为框架的上界和下界当a = b 时。称为 紧框架 注1 2 框架是基的推广- ( 1 ) 若 e 。) 是h 的标准正交基，则 是h 的框架，因为 f e 。) 1 2 = 2 ， v ，h( 1 2 ) ( 2 ) 若 妒。) 是日中的框架，则 ，= f d 。妒。， v ，h( 1 3 ) 我们知道，框架常常是包含基的，一般都比基的元素多，这样。象( 1 3 ) 式中 那样要表示空间中的任一个元素时，框架一般要比基多用些系数，这就是所谓的 冗余在有限维空间中。衡量冗余的方法是框架元素的个敷与空间的维数的比， 通常将这个比称为冗余度 例1 3 设是n 维h i l b e r t 空间， e ，l = 1 ，n ) 是日的标准正交基，e 0 h ，1 i e o i l 2 = 1 ，则 q l i = 0 ，n ) 是h 的框架，因为 n i ( ，e i ) 1 2 = l | 川2 + i ( ，e o ) n v ，日，( 1 4 ) i = 0 0s i ( ，e o ) 1 2si i 1 1 2 1 1 2 = lj i l l 2( 1 5 ) 由( 1 4 ) 和( 1 5 ) 有v ，日，i i i i i 2s l ( ，q ) 1 2 = 2 1 1 f l 2 ，于是 e d i = o ，n ) 是日中的框架，框架的冗余度是等 山东大学硕士学位论文 下面这个定理不紧刻画了有限维空间中的序列成为框架的充分条件，而且还 给出了框架最优上、下界，以及冗余度与框架上下界之间的关系 定理1 4 设是n 维 r 1 6 e 九空间，m 为固定整数，且m n ， e ，= ( n n ， ，d 。) ，el 。0 1 2 = 1 ， = 1 ，2 ，m ) ，a = ( o 玎) a + = 刁，若 a 的秩是n ， i = 1 即r 似a j = n ，则( e i ，i = l ，2 ，m ) 是h 的框架，并且有下面的式子成立t z 忏s e 。) 卜圳z 旧 v z h ( 16 ) l = l 且冗余度罢满足： a 1s 竺s 。( 1 7 ) 其中 l ，a 。分别是矩阵小a 最小、最大特征值，而且是框架的最优界 证明：v x h ，不妨设z 0 ，z = ( 2 l ，勋，z 。) 7 ，定义线性算子a ：h h 使 得 a m = ( ( z ，e 1 ) ，( z ，e 2 ) ，( ? ，e ，0 ) 显然，a ：r = a x ，记a 的共轭算子为”，同样有a z = a z ，于是 ( a a x ，z ) = ( a + 血，z ) = ( a x ，a m ) = i i a z l l 2 = l l z i 产2 0 故矩阵小 是非负定，不妨设其特征值0 a l a 2s a 。，又r ( 岔a ) = 故a l 0 ，即0 a ls 2s ! a 。，易知，存在正交特征向量噩，= 1 ，y t 使得 a ? “= h k ，k = 1 ，n 于是 z = o r k x k ，2 = 2 k = lk = l 故 l f a z f l 2 = ( a a m ，z ) = ( o a a 凡，a k x k ) = ik = l n1 7 , = ( o t k 地，a - 丑) 2 2 k o 。h | 1 k k 西 k 口 。h 、= 山东大学硕士学位论文 即 又 即 又由范数的定义 1 m 1 2si a z l 2 a 。il = i 1 2 a x 1 2 = e 。) 1 2 将( 1 9 ) 式代入( 1 8 ) 式，便得到命题中的( 1 6 ) 下面再证 z ，k 是最优的界， 设c 是框架的任一下界，即 v x 日，c i l z l i 2s e 。) 1 2 一 1 a z l l 2 = k 蚓2 = l= l 由x 的任意性，不妨取q l = l ，b 女= 0 ，1 ，于是上式成为 c a l 从而 l 是最优下界。 设b 是框架的任一上界，即 ，nn y x h ，b l l x i i 2 e t ) 1 2 = 1 1 a - , b 1 2 = k 川2 i = l= 1 由x 的任意性，不妨取q 。= 1 ，o = 0 ，佗，于是上式成为 b h 从而 。是最优上界 最后证( 1 ，7 ) 式成立， mn 考察矩阵a a 的迹；i 1 2 = m ，由根与系数的关系知 = 1 j = l 3 ( 1 8 ) 【1 9 ) 2 k 口 k 入 。蹴 | l 2 za 2 z， = 2 # a 。 8 入 一 2 口k 。腩 一 o 。随 入 i f 2 #入 山东大学硕士学位论文 m = l 十a 2 + - + a n 故n a l m 墨n a 。，即a l 罟a 。，证毕 有限维空间我们可以用框架元素个数与空问维数的比值来衡量冗余，那么无 限维呢? 显然不能用这种方法于是我们先引入分析算子的概念 定义1 5 设 ，j j 垦z ) 是i f i l b e r t 空间h 中的框架，f 2 ( j ) = c = ( q ) j j ，1 1 c 1 1 2 = i c j l 2 。) ，定义算子t ：h p ( j ) ，使得 j ， ，、 r l = ( ，奶) ) ， v ，h 、 】t j l l , i t 为框架 奶 的分析算子 下面的定理是在没有维数限制的情况下，用分析算子来衡量框架的冗余 定理1 6 设 咖，j j z ) 是h i l b e r t 空间h 中的框架，框架的下界为a ，丁为 框架的分析算子，谊n ( t ) = c c 1 2 ( j ) ，c = t l ，h ) ，r ( 丁) 1 = c l ( c ，d ) = o ，v d r n 九( t ) ) ，q = c = ( 勺) j e j ，i j 妒j = o ) ，i i , j j j ( 1 ) r a n ( t ) 是1 2 ( 了) 的闭子空问；( 2 ) r a r k r ) 1 = q ， 证明：( 1 ) 先证r a n ( 7 ) 是f 2 ( l ，) 的闭子空间 设c n r 帆( t ) ，c n c ，于是存在 h ，使得= t 厶，故l i 一c r ，l i i = 1 l t ，n 一丁，m 1 1 = l i 丁( 一，m ) i i a 1 i t ( ，n 一 。) 1 1 ( 最后- - 4 - 式子成立易由框架的定 义得到) 即1 1 c n l l a 1 i ，( 一k 故由1 1 c n 一1 1 一。知，1 1 f n 一厶 i 一0 由空问h 的完备性知，存在，日，使得，n j r ，又c n = t 厶，由算子的连续性 知，丁，= c ，则c r a n ( t ) ，从而r a n ( t ) 是1 2 ( 1 ，) 的闭子空间 ( 2 ) 再证r a n ( t ) 1 = q 设c = ( ) j e j r ( t ) j ，则( c ，d ) = o ，v d = ( 奶) ，e j r 口n ( 霸即白由= 0 又d r a n ( t ) ，故存在，h 使得t ，= d ，也即d 3 = ( ) ，故c j ( ，i ) 一0 ， 即( ，_ 仍) = 0 ，由，的任意性知。- j = 0 从而c n ，故砌n ( t ) 1 n 反过来，c f t ，则i j 仍= o ，于是w h ，( 弓锄) = 0 即 j j，j q ( ，奶) = 0 ，设d = ( 由) j j = ( ，妒j ) j e j ，则d r a n ( t ) ，勺由= 0 也即 ( c ，d ) ：0 故c 觑n ( 丁) 1 ，q 冗口n ( 1 ，从而n = r a n ( t ) 1 ，证毕 这个定理中集合q 显然可以衡量框架 奶) 的冗余，因为当框架 ) 是个 线性无关集，也就是空间的基时，n = o ) ；如果t 镪 是个线性相关集时，必 4 山东大学硕士学位论文 然包含基，那么基以外的元素越多，n 集合的元素也就越多通过上面的定理我 们知道n = r a n ( t ) 1 ，也就是说r a n ( t ) 1 同样可以衡量框架的冗余用这种方 法来考察有限维的情况，会得到下面有趣的结论 命题1 7 设是n 维h ：l b e r t 空间， 四，j j 是的框架，j 是有限集，t 是框架的分析算子，d i m r a n ( t ) 1 表示空间r o n ( t ) 1 的维数，则框架的冗余度 为：l + 塑警吐， 证明：显然，框架 协) 包含基，不失一艘陛，设框架中妒1 ，妒2 ，是基，剩 下的是妒i i = ( o m a l 2 ，a l n ) ，妒i 。= ( a 。1 ，n 。2 ，) ，这里的坐标是以 妒l ，忱，为基底的先考察r a n ( t ) 的维数，t 蛾r a n ( t ) ，i ；1 ，2 ，n ， 若c t 吼= 0 ，则丁( q 妒。) = 0 ，故e q 忱= 0 ，从而c i = 0 ，i = 1 ，2 ，n ”于 是丁妒。，t = 1 ，2 ，n ，线性无关，故 d i m r a n ( t ) n ( 1 1 0 ) 再考察r a n ( t ) 1 的维数，a l l 妒l + a 1 2 忉+ + a l 。一妒1 1 = 0 ，由定理1 6 知， c l = ( 乱l ，o u ，乱。，一l ，0 ，0 ) r a n ( t ) i ， 同理 c 2 = ( 口2 l ，0 2 2 ，口2 n ，0 ，一1 ，0 ) r a n ( t ) 1 ， = ( a m i 岫，n ，。，0 ，0 ，一1 ) r a n ( t ) 1 显然c l ，c a ，线性无关，故 d i m r a n ( t ) 1 m ( 1 1 1 ) 由算子t 的定义知d i m l 2 ( j ) = m - t - n ，又1 2 ( j ) = r a n ( t ) o r o n ( n 1 故 d i m r a n ( t ) + d i m r a n ( t ) 1 = m + 霸 ( 1 1 2 ) 综合( 1 1 0 ) ( 1 1 1 ) ( 1 1 2 ) 三式知，d i m r a n ( t ) = n ，d i m r a n ( t ) 1 = m ，故框架的冗 余度为，警= 1 + 罟= 1 + 业学，证毕 5 第二章提升方案 2 1 提升方案编码实践 提升方案是由w i ms w e l d e n s 首次在f 3 中提出的，用来构造具有紧支撑的双正 交小波提升方案的基本思想见w i ms w e l d e n s 3 5 1 ，i d a u b e c h i e s ，w s w e l d e n s 2 ， 而涉及到这方面的应用有很多，相关的文章有；g o h ，j i a n g ，t a ox i a 在1 1 】中用 提升方案来构造双正交多小波；p s c h r s d e r ，w s w e l d e n s 在中用提升方案构 造满足特殊性质的双正交球面小波；j k o v a c e v i c ，w s w e l d e n s 在i lo 中用提 升方案来构造任意维空间中格( 1 a t t i c e ) 上的双正交小波。并且可以通过对偶提升 方案增加小波的消失矩( v a n i s h i n gm o m e n t s ) ；a r c a l d e r b a n k ，i d a u b e c h i e s ，w s w e l d e n s 等在1 1 1 中用提升方案构造出整数到整数小波变换，将这种变换应用到 图像编码中可以得到无损压缩效果，而一般的小波变换只能得到有损压缩效果； r c l a y p o o l e ，g d 驰，w s w e l d e n s 等在【1 2 】中通过提升方案来研究图像编码中 非线性小波变换的问题：可逆性，稳定性等 提升方案有这么多应用。那么这种方法到底有什么优点呢? 归纳起来有如下 几点； 1 、在运算的时间方面，由提升方案分解原有的离散小波变换，会得到更快 运算速度【2 】中定理5 ( p p 2 6 4 ) 说明了这一点t “t h e o r e m 5a s y m p t o t i c a l l y , f o r l o n gf i l t e r s ，t h ec o s to ft h el i f t i n ga l g o r i t h mf o rc o m p u t i n gw a v e l e tt r a n s f o r mi so n e h a l fo ft h ec o s to ft h es t a n d a r da l g o r i t h m ” 2 、在运算的空间方面，由提升方案得到的算法是同址( i n - p l a c e ) 运算，这样 在运算的过程中能节省空间，尤其是在处理象图像、视频等含有大量数据的信号 时，这种优点就更突出 3 、提升方案很容易构造非线性小波变换典型的例子是整数到整数的变换 ( 详见【1 0 1 ) 。这种变换在无损图像编码中有非常重要的作用 当然还有许多其优点，这里就不再一一列举下面我们解释提升的具体过程 假设信号勺有个采样值，我们目的是得到是得到粗分辨率的信号8 f - l 和 细节数据出一- ，这个过程分三步； 1 、划分；将信号分成奇偶两部份， ( e v e n j “o d d j 一1 ) = 叫n ( s j ) 2 、预测z 也就是计算细节系数出一l ，方法有很多种。例如td j _ l ，= s j ，2 j + l 一3 2 1 6 山东大学硕士学位论文 或者d j 吐，= 8 j , 2 1 + l i ( s 2 1 + s j 2 1 + 2 ) 一般我们记为：由一l = o d d j l p ( e v e n j 一1 ) 3 、提升；再用第二步的细节系数和偶数部分计算出粗分辨率的信号岛一1 ， 记做s j l = e v e r , j + u ( e ) 在变换的过程中要保持均值不变，第二步中的例 子对应这一步很容易计算出，分别是： s j 吐j = s j ，2 1 + 由乩j 和s ，“1 = 岛，2 i + j ( d j _ l t j + d j “j ) 实际上我们很容易知道上面例子中的滤波器，第一个例子h a a r 小波，第二个 例子中的滤波器是： s j “j = 一i 1 勺2 i 一2 + 5 2 1 1 + i s 2 l + s 2 1 + 1 一 s j ，2 1 + 2 而这 正好是d o u b e c k i e s 双正交小波中的一种，详见【1 4 p p 2 7 7 下面我们在第二个例 子的基础上给出离散小波变换的c + + 程序，这个程序只是对图像的水平方向做 一次变换，竖直方向是类似的我们在图2 1 中给出了2 5 6 2 5 6 b m p 格式的l e n a 图像进行一次水平和竖直方向变换的结果 图2 1 ：l e n a 图像 下面函数的功能就是对图像水平方向做一次快速离散小波变换函数参数说 明：p o r i g i a 是指向原始图像的指针，p t r a n s 是存放变换后的图像的指针，n h e i g h t 是原始图像的高度，n w i d t h 是原始图像宽度的一半 v o i df d w t ( s h o r t + + p o r i g i n ，s h o r t + + p t r a n s ，i n tn h e i g h t ，i n tn w i d t h h ) i n ti d ，k ，i w i d t h = n v 们l d t h h + 2 ； 原始图像的宽度值 s h o r tl i f t ； 相邻细节系数的1 4 ，用来来提升偶数效据 s i g n e ds h o r tm e a n ；存放原始数据相邻偶数的均值 7 山东大学硕士学位论文 f o r ( i = 0 ；i n h e i g h t ；i + + ) f o r ( j = o ；j n w i d t h h ；j + + )l a z y 小波变换开始 k = j 1 ： 原始数据的偶数部分 p n a n s 【i = p o r i g i n i l k 一1 2 8 ； 原始效据的奇效部分 p t r a n s i n w i d t h h “】= p o r i g i n i l k + 1 一1 2 8 ； ) l a z y 小波变换结束 f o r ( i = o ；i 1 ) ； 在数组的后半部分存放细节数据：原始数据的奇数 p t r a n s i n w i d t h h + j 】= m e a n , ) 预测结束边，界处理开始 m e a n = ( ( p t r a n s i n w i d t h h - 1 + p t r a n s i n w i d t h h - 2 d 1 ) ； p n a n s 【i 1 i w i d t h - 1 】_ = m e a a l ； l i f t = ( ( p t r a n s i l n w i d t h h + p t r a n s i i l n w i d t h h + 1 1 ) 2 ) ； p t r a r t s i 0 1 + = l i f t ； 边界处理结束，提升开始 f o r ( j = l ；j 2 ) 在数组的前半部分存贮粗线条信息 p t r a n s i j 】+ = l i f t ； ) ) ) 8 山东大学硕士学位论文 2 2 原始的提升方案 设测度空间l 2 = l 2 ( x ，e ，p ) ，其中x 是基本集，r “中的空间域是d 代 数，“是非原子测度在本节中l 2 都是如上所设定 定义2 1l 2 中的闭子空间序列m = cl 2 1 j ，cz 称为广义多尺度分析 ( g m r a ) ，如果满足如下条件； l ，y jc 嵋+ 1 ，uy j = l 2 ，n 巧= o ) ； ，j，j 2v j z 尺度函数 妒，k 障k o ) ) 是k 的r i e s z 基 其中k ( j ) 是一个下标集这里我们假设k ( j ) ck ( j + 1 ) 而，有两种可 能。j = n ，或j = z 注2 2 这里的g m r a 去掉了经典m r a 中的k 和k + l 之间的伸缩关系，而且 还去掉了k 中r i e s z 基元素之间的平移关系 设 奶，k ) 为对应的小波函数，具体定义见【4 1 1 p p 5 1 8 类似，我们可以定义对偶的 广义多尺度分析m = 嵋i j ，) ，其中k 是l 2 中的闭子空间，其r i e s z 基是由 对偶尺度函数西，k 组成， 如，一) 为对偶小波， 如果 ( 妒，k ，西，) = 氏f ，k ，k o )( 2 1 ) 我们称驴，k ，仍，k 是双正交的 如果 ( 如尚奶) = 民k ，k k ( j )( 2 2 ) 我们称叱m 也* 是双正交的 定义2 3 实数集合 b ，k ，l l j 正k k o ) ，f k ( j + 1 ) ) 称为一个有限滤波器，如 果满足 ( 1 ) 每一个囊k ，系数h i ，的非零元素为有f g - 4 ，于是集合l ( j ，k ) = z k ( j + 1 ) l h j 1 o ) 是有限集； ( 2 ) 每一个j ，f ，系数h i ，k 1 的非零元素为有限个。于是集合k 0 ，f ) = k k ( 3 ) i h j ，k 1 o 是有限桌； ( 3 ) 对于所有的j , k , l ，集合l ( j ，k ) 和g ( j ，z ) 的大小一致有界 记m ( j ) = k ( j + 1 ) 一k 0 ) ，我们有如下双尺度关系t 仍，k = b l 协扎l ( 2 3 ) l e k u + i ) 9 山东大学硕士学位论文 蚴= g j 。忉扎l ( 24 ) j k o + 1 ) 其中h = b ，k d j k ( j ) ，f 1 1 ( j + 1 ) ) ，g = g j 。i l j z m m 0 ) ，l k ( j + 1 ) ) 都是有限滤波器类似的，i ，构成对偶双尺度关系的有限滤波器结 合( 21 ) ，( 2 2 ) 和双尺度关系，有 毋，。易m ，i = 靠。，b 西。，l = 0 ( 2 5 ) h j , k , l 珏户缸g j 。l 弧f ：0 ( 2 6 ) ff 定义2 4 如果条件( 2 5 ) ，( 2 6 ) 满足。则称 h ，h ，g ，j ) 为双正交滤波器组 下面默认a p ( ( j + 1 ) ) ，b 1 2 ( k ( j ) ) ，c f 2 ( m ( j ) ) ，分别表示a = a t l t k ( j + 1 ) ) ，b = b d t ( j ) ) ，c = c 。l m 靠( ，) ) 定义算子 g j ：t 2 ( k ( j + 1 ) ) - + 1 2 ( 0 ) ) ，b = 马n 表示，b k =eb l a ! l t g o + d 定义算子 g j ：1 2 ( 女0 + 1 ) ) + 1 2 ( m 0 ) ) ，c = g j a ，表示，=eg j ，k ，l a l f o + 1 ) 类似，我们定义算子吗，g j 显然完全重构的条件为： h ，h ；= g j g j = 1 、g ，h j = h ，g j = 0 h ：h i h + g ：g j = 、 记a = ( ，g j ) ，a = ( 毋，q ) ，则上面3 个式子等价于t a a = 1 2 x 2 ，a a = 1 1 。1 定义2 5 如果上面的式子成立，则称滤波器算子 ，岛，q ，岛) 双正交滤波器 算子 定理2 6 ( 提升方案) 假设 掣4 ，霹，g 产，0 产) 是双正交滤波器算亍设a = ( m 一1 ) 4 a “，a = m a d 4 则 吗，岛，q ，岛) 也是双正交滤波器算子，如果m