（信号与信息处理专业论文）身份照片的改进压缩编码算法研究与实现.pdf

武汉理工大学硕士学位论文 摘要 身份照片由于它的特殊性，在日常生活中得到了广泛的应用。随着相关 技术的发展和身份管理系统的升级，出现了新一代的磁卡、二维条形码和 i c 卡等信息存储式身份证件。然而，无论是二维条形码还是i c 卡，存储容 量都非常有限。在一个二维条码中，除了存储一张照片外，还要存储姓名、 性别、籍贯、民族等一些个人的信息，减小照片编码后的大小就十分重要， 这对照片的压缩提出了很高的要求。 传统的e z w 算法对整幅照片进行压缩，使最重要的人脸图象变得不够 清晰，影响人眼的有效辨认。因此，考虑到视觉的特性和对照片不同区域的 重视程度的不同，把整幅照片分为面部的r o i 矩形区域，背景和除面部r o i 以外的头肩区域三个区域。本文以1 寸黑自身份照片为压缩对象，研究了用 小波零树编码( e z w ) 、感兴趣区域( r o i ) 编码分别与游程编码和直线拟合相 结合的方法对身份照片进行压缩的具体实现，并探讨了批处理的技术，可以 将包含身份照片的扫描图片分割出来，分别保存，以供压缩编码使用。文章 介绍了小波原理和感兴趣区域编码理论，详尽分析了小波的m a l l a t 算法实 现，并利用v c + + 6 0 编程实现了小波零树编码分别与游程编码和直线拟合 编码的结合。本文的方法进一步压缩了头肩轮廓码流，去除了冗余，身份照 片的整体压缩质量有了明显的提高。从现有的测试结果看，压缩的性能比较 满意，达到了预期的效果。因此，该方法对第二代身份照片的压缩编码有一 定的借鉴作用。 本论文首先介绍了课题的背景，身份照片压缩的发展与应用及本文的主 要工作，并简要地介绍了研究的主要内容、方法和技术路线。然后，对小波 理论、小波零树编码和感兴趣区域编码作了简要的介绍，并讨论了如何在小 波零树编码的算法框架内实现感兴趣区域编码。接着，详细的阐述扫描照片 分割的实现和本文对身份照片压缩的实现，并且给出了实验的结果。这一部 分主要内容是；分割程序的实现，整个压缩方案的设计，感兴趣区域的分割， 小波变换的实现，轮廓线的游程编码和直线拟合编码及实验结果。在文章的 最后，对本文的研究工作进行总结，并对下一步的研究方向进行展望。 关键宇：身份照片压缩；嵌入式小波零树编码；感兴趣区域编码；游程编码； 直线拟合 武汉理工大学硕士学位论文 a b s t r a c t p e r s o n a li d e n t i f i c a t i o np i c t u r ei sak i n do fs p e c i a lp i c t u r e ，s oi ti s p r o v e r b i a l l y e x i s t e di na l lk i n d so ft h ef i e l d sw h i c hw el i v e si n w i t ht h ec o r r e s p o n d i n g t e c h n o l o g y d e v e l o p m e n ta n dt h eu p d a t i n go fi d e n t i t ym a n a g e m e n ts y s t e m ，n e wg e n e r a t i o no f i n f o r m a t i o n - s t o r e di d e n t i t yc a r dc a m eo u t ，s u c ha s2 - d i m e n s i o nb a rc o d ea n di cc a r d b u tt h o s ec a p a c i t i e sa r el i m i t e d i no r d e rt os t o r et h ep i c t u r e ，n a l n e ，s e x ，n a t i o na n d o t h e ri n f o r m a t i o ni na2 - d i m e n s i o nb a r , t h ec o m p r e s s i o no fi d e n t i f i c a t i o np i c t u r eh a s b e e nap i v o t a lt e c h n o l o g yo f n e w g e n e r a t i o ni d e n t i t yc a r d t h et r a d i t i o n a le z w c o d i n gc o m p r e s s e st h ew h o l ep i c t u r e ，s ot h ec o m p r e s s i o n q u a l i t ya n d v i s u a le f f e c to f p e r s o n a li d e n t i f i c a t i o np i c t u r ea r et o ob a dt or e c o g n i z e i n v i e wo fv i s u a le f f e c ta n ds i g n i f i c a n c eo fd i f f e r e n tr e g i o n s ，t h ep r o g r a md i v i d e st h e w h o l e p i c t u r ei n t ot h r e ep a r t s ：r e c t a n g l eo fr o i ，b a c k g r o u n dr e g i o na n dp r o f i l er e g i o n i nt h i sp a p e r , 1 - i n c hp e r s o n a li d e n t i f i c a t i o np i c t u r e sa r et a k e na sc o m p r e s s i n go b j e c t r e s e a r c h i n gw o r ki n c l u d e se z wc o d i n g 。t h ei m p l e m e n t a t i o nt h a tt h ep r o g r a mu s e s t h er u n l e n g t hc o d i n go rs t r a i g h t - l i n ef i a i n gc o d i n gt oc o m p r e s st h eo r i g i n a lp r o f i l e c o d ea n dt h eb a t c h p r o c e s s i n gw a y s t h a tt h ep r o g r a m s e g m e n t sp e r s o n a li d e n t i f i c a t i o n p i c t u r e sf r o m t h es c a n n e dp i c t u r ea n ds a v e st h e ma si n d i v i d u a lp i c t u r e sf o rt h ec o d i n g p r o g r a m f i r s t l y , t h et h e o r y o fw a v e l e ta n dr o ii s i n t r o d u c e d ，a n dt h e n t h e i m p l e m e n t a t i o no fm a l l a ta l g o r i t h mo fw a v e l e ti sa n a l y z e di nd e t a i l t h ep r o g r a m i m p l e m e n t st h e m e t h o dt h a te z w c o d i n gi n t e g r a t e sw i t hr u n - l e n g t hc o d i n ga n d s t r a i g h t l i n ef i t t i n gc o d i n gr e s p e c t i v e l y o nv i s u a lc + 十6 0p l a t f o r m i no r d e r t oe l i m i n a t et h e r e d u n d a n c y , t h ep r o g r a mc o m p r e s s e st h ep r o f i l ec o d e ，w h i c hi m p r o v e st h eq u a l i t y o ft h e i d e n t i f i c a t i o np i c t u r e s t h ee x p e r i m e n tv e r i f i e st h a tt h ep e r f o r m a n c ea n de f f e c to f c o m p r e s s i o n a r e s a t i s f y i n g t h e r e f o r e ，t h es e c o n d - g e n e r a t i o ni d e n t i f i c a t i o np i c t u r ec a nb eu s e dt h em e t h o df o r r e f e r e n c e f i r s t l y , i m a g ec o m p r e s s i o n st h e o r y , s i g n i f i c a n c ea n db a c k g r o u n do ft h e s i s l s e l e c t i o na n dt h em a i nr e s e a r c ha r ei n t r o d u c e d t h em a i nr e s e a r c hi n c l u d e st h e c o n t e n t ，m e t h o da n dt e c h n o l o g y t h e nw a v e l e tt h e o r y , e z wc o d i n g ，r o ic o d i n ga r e i n t r o d u c e db r i e f l y h o wt oi m p l e m e n tr o ic o d i n gi nt h ea l g o r i t h mf r a m e w o r ko f n 武汉理工大学硕士学位论文 e z w c o d i n gi sd i s c u s s e di nt h i sp a r t a tt h en e x tp a r t ，t h ep r o c e d u r et h a ts e g m e n t s p e r s o n a l i d e n t i f i c a t i o n p i c t u r e s f r o mt h e s c a n n e d i m a g e a n dt h em e t h o do f c o m p r e s s i n gp e r s o n a li d e n t i t yp i c t u r e a r e e x p l a i n e d i n d e t a i l ，a n d t h e nt h e e x p e r i m e n t a lr e s u l t s a r eg i v e n t h i sp a r t i n c l u d e s ：i m p l e m e n t a t i o no fs e g m e n t i n g p r o g r a m ，t h ew h o l ed e s i g n a t i o no fc o m p r e s s i o na l g o r i t h m ，s e g m e n t a t i o no fr o i ， i m p l e m e n t a t i o n o fw a v e l e t s t r a n s f o r m a t i o n ，s i l h o u e t t e s r u n 1 e n g t hc o d i n g a n d s t r a i g h t - l i n ef i t t i n gc o d i n ga n de x p e r i m e n t a lr e s u l t s f i n a l l y ，a l lt h er e s e a r c hw o r ki n t h i sp a p e ri ss u m m a r i z e da n dt h ep r o s p e c ta b o u tt h ef u t u r er e s e a r c h i n gd i r e c t i o ni s d i s c u s s e di ub r i e f k e yw o r d s ：c o m p r e s s i o n o fi d e n t i f i c a t i o n p i c t u r e ，e z wc o d i n g ，r o ic o d i n g ， r u n l e n g t hc o d i n g ，s t r a i g h t - l i n ef i t t i n g i i i 武汉理工大学硕士学位论文 第1 章引言 伴随着通信、计算机、i t 和信息等技术的全面发展，人类社会已进入了信 息化的时代。信息社会充斥着大量的信息，使得如何压缩、存储、传输和处理 这些信息的问题变得至关重要。对于图象信息而言，主要关心以下几个方面： 图象信息的获取，存储，传输，处理，输出和显示。图象处理技术发展到今天， 许多技术已日趋成熟。在各个领域的应用取得了巨大的成就和显著的经济效益。 如在工程领域、工业生产、军事、医学、航空航天以及科学研究中的应用已十 分普遍。通过分析资源卫星得到的照片可以获得地下矿藏资源的分布及埋藏量： 利用红外线、微波遥感技术可侦察到隐藏的军事设施。但如此大量的数据在处 理之前都离不开压缩技术。图象压缩是图象信息处理的重要手段和分支，它的 研究和发展推动了图象信息的存储和传输水平。图象压缩对于人们的日常生产、 生活和科学进步有着十分重要的意义，如果没有图象压缩技术的发展，处理如 此之多的信息将耗费大量的时间、精力、物力和财力“1 。 1 1 课题的背景 图象从本质上来讲是一种视觉的信息。信息是信息论中最基本、最重要的 概念，它是一个既抽象又复杂的概念。它不能等同于情报学中的情报的概念： 也不能等同于知识；亦不能等同于消息。最早对信息进行科学定义的哈特莱认 为，信息就是从通信符号表中选择符号的具体形式，并主张用所选择的自由度 来度量信息。控制论的创始人之一维纳认为，“信息就是信息，不是物质，也 不是能量”。而信息论创始人香农认为，信息是事物运动状态或存在方式的不 确定性的描述。他于1 9 4 8 年和1 9 4 9 年接连发表了论文通信的数学理论和 噪声下的通信。在这两篇文章中，他解决了过去许多悬而未决的问题：经 典地阐明了通信的基本问题，提出了通信系统的模型，给出了信息量的数学表 达式，解决了信道容量、信源统计特性、信源编码、信道编码等有关精确地传 送通信符号的基本技术问题，为信息论奠定了理论基础。 根据信息的理论，信息是事物发展的不确定性的变化。根据概率论，事件 的不确定程度，可以用其出现的概率来描述，事件出现的可能性越小，则概率 武汉理工大学硕士学位论文 就越小，反之，则概率就越大。消息中的信息量与消息发生的概率紧密相关， 消息出现的概率越小，则消息中包含的信息量就越大“1 。 一般说来，自然界的数据或多或少都含有冗余，数据压缩的目的就是把这些 水分挤掉，用最少的比特表示最多的信息。通过一种运算，把这些多余的东西 剔除出去，就实现了数据压缩。典型的数据压缩包含去相关( 冗余) 和熵编码 两个步骤。实际上日常生活中发电报的过程就是一个数据压缩的经典范例。为 了减少电报的字数，尽量精简文字，浓缩为一种类似文言文的精炼文字，表达 的意思保持不变：然后将精简后的文字转换成莫尔斯电报码发送出去。这两个 步骤分别相当于数据压缩的去相关和熵编码。 在1 9 4 8 年香农发表的通信的数学理论这篇文章里，针对通信的信源 编码问题，作者从概率统计的角度详细讨论了输出信元为n ( n = o ，l ，2 ，3 ) 阶平 稳有限马尔科夫链时的无损压缩问题。书中香农第一定理给出的数据压缩极 限：要做到无失真的信源编码，变换每个信源符号平均所需最少的，元码元数 就是信源的熵值( 以，进制信息量单位测度) 。若编码的平均码长小于信源的 熵值，则唯一可译码不存在，在译码或反变换时必然要带来失真或差错。可见， 信源的信息熵是无失真信源压缩的极限值。也可以认为，信源的信息熵是描述 信源每个符号平均所需最少的比特数。在此基础上，1 9 5 2 年霍夫曼提出了以 他的名字命名的编码算法，解决了一阶马尔科夫序列的无损压缩问题。1 9 6 3 年p e t e re 1 i a s 提出了比霍夫曼码更优的算术编码，但是第一个实际可用的算 法直到1 9 7 6 年才由r i s s a n e n 和p a s c o 给出。1 9 7 7 年z i v 等人基于字串复杂 度分析，设计通用信源的l e m p e l z i v 编码得到了和香农的熵编码相同的结果。 此后，熵编码成为了各种数据压缩技术的基础。从信息论的角度看来，数据压 缩的问题转化为如何将高阶马尔科夫序列转化为一阶序列的问题。1 。 图象可以表示成确定性信号、随机信号和噪声的混合“1 。设图象信号为 f ( x ，y ) ，则 f ( x ，y ) = 乃( x ，y ) + f a x ，y ) + n ( c r ，) ( 1 一1 ) 其中f a x ，_ y ) 为确定性信号；f a x ，y ) 为马尔科夫随机信号；( 盯，) 为高斯噪声。 针对上述图象的混合模型，图象压缩算法应该包含以下基本步骤：( 1 ) 信号逼近； ( 2 ) 信号去噪；( 3 ) 熵编码。信号逼近的目的在于去除乃( x ，y ) 的高度相关。这时 2 武汉理工大学硕士学位论文 图象信号被当作一个二维函数形成的曲面( 以灰度为z 方向坐标) ，f ( x ，y ) 和 n ( a ，) 被近似看成是信号的高频成分。这种情况下，去相关的本质是二维曲面 的分解与逼近，常用的方法有付立叶分析或小波分析。通过某种正交变换可以 极大的去除图象信号的相关；信号去噪是为了降低数据的熵值。噪声信号一般 具有很高的熵值，混合在有效信号中对压缩编码的整体效率有很大影响，必须 在熵编码之前剔除出去；经过上述处理以后，图象信号转化为一系列随机信号， 可进一步采用熵编码进行压缩5 “。 综上所述，图象压缩的基本原理如图卜l 示，包含以下几个部分：去相关、 量化和熵编码。首先将图象当作确定性信号处理，采用d f t 、d c t 、d w t 变换等 函数逼近的方法降低信号的相关性：然后对变换的系数进行量化处理，以去除 信号的噪声，降低系数熵值；最后，采用信息论提供的方法进一步去除数据的 冗余。 图卜1图象压缩的原理框图 1 2 身份照片压缩的发展与应用 1 2 1 身份照片压缩的需要 压缩数据 身份照片压缩主要源于身份管理系统的升级换代的需要。传统的各类身份 证件的文字或图象直接打印在证件表面。在长期的使用过程中出现了不少弊 端。首先，受证件尺寸限制，所记载的信息量少；第二，信息的保密性差，由 于信息直接印在证件表面，所有的信息对证件的阅读者是公开的。第三，易于 仿造，因此安全性较差。第四，信息更改不方便。为克服上述的各种弊端，我 国即将换发第二代身份证。它采用非接触式芯片作为“机读”存储器，为i c 卡( 单页卡式) ，芯片存储容量更大，写入的信息可划分安全等级，分区存储， 按照管理需要授权读写，也可以将变动信息( 如住址变动) 追加写入。证件背面 武汉理工大学硕士学位论文 印有持证人照片、登记项目( 姓名、性别、民族、出生、住址公民身份号码) 。 它还采用了数字防伪和印刷防伪技术，数字防伪用于机读信息的防伪，是将持 证人的照片图象和身份项目内容等数字化后采用密码技术加密再存入芯片，可 以有效起到证件防伪的作用，防止伪造证件或篡改证件机读信息内容。 p d f 4 1 7 二维条形码由美国s y m b o l 公司1 9 9 1 年正式推出。它由一组条空 单元组成码词，用来表示一个或多个数字、字母或符号，每个码词有4 个条和 4 个空组成，每个条或空的宽度可以是1 到6 个模块宽，4 个条和空的宽度加 起来总共是1 7 个模块，所以称之为p d f 4 1 7 。它的最大容量参数为：可容纳1 8 5 0 个大写字母或2 7 1 0 个数字或11 0 8 个字节，并且可以存储中文。一维条形码容 量更小，一般为1 5 个数字。一维和二维条形码如图卜2 所示。 图1 - 2 一维i s b n 码和二维p d f 4 1 7 码 p d f 4 1 7 码不仅可以将证件上姓名、单位、地址、电话等信息存入编码， 而且可以将人体的特征如指纹、视网膜扫描以及照片等信息存储在可自动识读 的p d f 4 1 7 码中。1 寸左右的黑白照片的大小一般在7 0 0 0 字节以上，如果是彩 色的则会更大。因此照片的大小将直接影响到i c 卡芯片内部的存储器容量的 设计。随着存储器容量的加大，成本也会相应的提高。因此，必须对身份照片 进行压缩，才能使存储器不会过大，也能使图片的清晰度得到保证。 1 2 2 国内外的研究动态及水平 到目前为止，比较成熟的算法是h u 等人。3 提出的基于矢量量化的f c 2 v q ( f e a t u r ec o r r e c t i o nt w o - s t a g ev e c t o rq u a n t i z a t i o n ) 算法。该算法成功实现了对 黑自身份照片的压缩。该算法的主要思想是首先矢量量化整幅照片并同时把人 脸的主要特征区域( 眼睛和嘴所在的区域) 检测出来，然后对这块区域的差图 再进行矢量量化。1 以便细化该区域，最后进行霍夫曼编码。f c 2 v q 算法能把一 4 武汉理工大学硕士学位论文 张1 2 8 1 2 8 像素的黑白照片平均压缩到大约3 5 0 字节，而质量仍可接受。在1 9 9 9 年，纽约理工大学h u a n g 等人又利用f c 2 v q 算法完成了彩色( 如r g b 和y b c b c r 颜色空间) 照片的压缩。他们的实验表明，一张1 2 8 1 2 8 像素的彩色照片平均 压缩到大约5 0 0 字节，质量可以接受。 1 9 9 2 年，l e w i s 和k n o w l e s 首次提出了零树编码思想。根据其方法所产生的 恢复图象能被人们视觉所接受，但其率失真性能低于5 p e g 标准。并且因其方法 的理论缺陷，使得由小波系数和门限相比较得出的假设条件不成立时，会造成较 大的失真。针对这种方法的缺陷，s h a p i r o 于1 9 9 3 年提出了嵌入零树小波 ( e m b e d d e dz e r o t r e ew a v e l e t ，e z w ) 算法，这种方法很好地利用了小波系数的特 性使得输出的码流具有嵌入特性，既实现了高的压缩比，又保证了重建图象的质 量。 在e z w 算法的基础上，s a i d 和p e a r l m a n 提出了s p i h t ( s e tp a r t i t i o n i n gi n h i e r a r c h i c a lt r e e s ) 算法。它仍然采用树状结构来组织小波系数，所不同的是 利用集合的划分来进行编码。虽然这种表示系数的方法更为有效，但由于编码 过程中要使用三个链表，所以这种算法需要大量内存，硬件实现起来比较困难。 为此，l i n 和b u r g r e s s 提出了l z c ( l i s t l e s sz e r o t r e ec o d i n g ) 算法，用标志 位图代替了s p i h t 算法中的链表，从而极大地降低了内存的需求。在国内，牛 建伟、王刃、李波通过有机结合零树编码、位平面编码和算术编码，提出了一 种基于零树和位平面的小波图象压缩算法z b p ( z e r o t r e ea n db i tp l a n e ) ，大 大地提高了算术编码的性能。 可以看出，目前对身份照片的压缩主要采用的是矢量量化的方法。但矢量量 化无法准确预计和控制编码的长度。而在实际应用中，证件中存储的信息除身 份照片以外还有其它一些个人信息，一般包括一至两枚指纹数据等等。这些信 息的长度因人而异。如果采用基于上述矢量量化的方法对身份照片进行压缩的 话，目标编码的长度必须取所有长度中最大的一个，这样一来，必定会浪费许 多存储空间。 为了解决这一实际应用中的不足，郭。1 等人提出了一种的混合算法。该算法 利用了嵌入式小波零树编码“”的目标编码长度精确可控的特点，使卡上存储空 间可以得到完全的利用。本文主要研究的问题就是利用嵌入式小波对图象进行 编码，并对已有的成果作进一步的改进，加入了游程编码和直线拟合的方法， 提高编码的效率，增加图象的清晰度。 武汉理工大学硕士学位论文 1 3 本文的主要工作 本论文的研究工作依托于武汉理工大学科研基金项目“面向对象的小波变换 图象压缩编码算法研究”。在已有的成果上，对相应的算法提出改进的意见和扩 展。 本文的研究对象有两个：一是含有1 寸左右大小身份照片的大幅扫描图片 ( 7 2 4 x5 3 3p i x e l ，2 4 b i t 或8 b i t ，1 1 0 m b 或3 7 7 k 字节左右) ；二是1 寸左右的 普通黑白身份照片( 6 9 x 9 4p i x e l ，8 b i t ，7 6 6 0 字节左右) 。以嵌入式小波零树 编码作为主要的压缩方法。同时，为兼顾压缩比和压缩质量，引入了r o i 、游程 编码和赢线拟合技术。在压缩质量可以接受的情况下，使压缩后的照片所占空 间至少小于5 0 0 字节( 压缩比大于1 5 ) 。 本文研究工作有两个方面的意义。第一，从图象压缩和编码的角度看，本 文对感兴趣区域编码在身份照片压缩中的效果所做的研究有助于其他科研工作 者，或从事图象压缩技术开发人员直观地看到感兴趣区域编码在具体应用中所 发挥的良好作用。第二，从具体的应用角度看，本文研究成果可以直接应用于 身份照片的二维条形码或i c 卡存储。第三，引入批处理的方法，可以使扫描图 片对大量的身份照片进行分割处理，所得到的小图片的尺寸、大小和文件格式 满足编码处理程序的要求。 本文对身份照片压缩的主要的技术路线如图卜3 所示。 图卜3 身份照片压缩的主要技术路线 为了实现上述技术路线指导下的身份照片压缩，本文的主要研究工作包括以 下几个方面： 6 武汉理工大学硕士学位论文 ( 1 ) 研究有关图象分割的基本原理、主要算法和实现的程序。查阅相关的文 章、文献和论文，了解非压缩b m p 图象文件格式的格式，以实现2 4 b i t 位图至 8 b i t 位图的转换，使图片的格式和尺寸满足压缩程序处理的需要。 ( 2 ) 了解基本的小波理论和嵌入式小波零树编码算法，并在零树编码的框架 内实现了基于位面移位的感兴趣区域编码。 ( 3 ) 对现有的感兴趣区域编码算法作了一定的研究。感兴趣区域编码源于实 际的图象、视频工程应用，主要是为了解决低比特率图象编码时的视觉质量问 题。本文通过引入感兴趣区域编码来提高身份照片的整体压缩质量( 在一定的 压缩比或目标比特率下) 。 ( 4 ) 研究有关游程编码和直线拟合的基本原理、主要算法和实现的程序。查 阅有关的论文和文章，将游程编码和直线拟合编码分别嵌入到轮廓编码之中， 通过比较了解两种方法的效果，寻找一种较好的轮廓编码方法，以提高压缩比 例，去除码流中的冗余。 ( 5 ) 用v c + + 6 0 实现了本文的压缩算法，并能得出主要压缩的性能参数。 全文的具体安排如下： 第1 章介绍了课题的背景和本文的主要工作。 第2 章简单介绍了小波变换的基本原理和小波变换的m a l l a t 算法。 第3 章首先对小波零树编码理论进行了阐述，然后再分析基于图象感兴趣区 域编码理论，最后比较两种不同的位面移位方法。 第4 章讨论了图片的分割和照片压缩的总体设计，包括扫描程序的分割及图 象感兴趣区域的确定，其中重点介绍了轮廓线的两种改进编码方法：游程方法 和直线拟合。最后给出了两种改进方法的实现和实验结果。 第5 章总结了本文所做的工作，对图象压缩技术的前景做了展望。 武汉理工大学硕士学位论文 第2 章小波变换的基本原理简介 小波分析的思想可追溯到1 9 1 0 年h a r r 提出的小“波”规范正交基。1 9 8 1 年 s t r o m b e r g 对h a r r 系进行了改进，证明了小波的存在性。1 9 8 2 年b a t t l e 在构造量 子场论中使用了类似于g a l d e r o n 再生公式的展开。1 9 8 4 年法国地球物理学家 m o r l e t 在分析地震波的局部性质时，发现传统的f o u r i e r 变换难以达到要求，因 此他首次引入了“小波”的概念，建立了以他名字命名的m o r l e t d 、波，并用于 信号分析中对信号进行分解。随后，物理学家g r o s s m a n 对m o r l e t 的这种信号按 fl，l1 一个确定函数的伸缩、平移系 h i y ( 兰兰) ：口，b r ，玎0 展开的可行性进行了 l 。 玎 j 研究，这为小波分析开了先河。 1 9 8 7 年，m a l l e t 巧妙地将计算机视觉领域内的多尺度分析的思想引入到小 波分析中小波函数的构造及信号按小波变换的分解与重建，从而成功地统一了 在此以前的其他人提出的具体的小波函数的构造，研究了小波变换的离散化形 式，并将相应的算法称之为m a l l e t 算法，该算法有效地应用于图象分解与重构。 同时，d a u b e c h i e s 构造了具有有限支集的正交小波基。这样，小波分析的系统 理论初步得到了建立。 小波的基本思想是通过一个母函数在时间上的平移和尺度上的伸缩，获得 了一种能自动适应各种频率成分的有效信号分析手段，以取代短时f o u r i e r 变 换“。在分析非平稳时变信号时，既能用持续时间很短的高频基函数去分析信 号的高频成分，又能用持续时间相对较长的低频基函数去分析信号的低频成分。 小波变换在时域、频域内具有良好的局部分析特性，在信号分析、图象处理、 数据压缩、计算机视觉等很多领域得到了广泛的应用“”“。 2 1 小波变换的定义 小波变换与f o u r i e r 变换非常相似，其基本的数学思想来源于经典的调和分 析，都是将信号与一个具有两个参数的函数族作内积运算。f o u r i e r 变换以三角 函数作为基底对信号进行展开，小波变换则以局部化函数所形成的相似函数作 为基底对信号进行展开。小波变换发展了短时f o u r i e r 变换的局部化思想，其 8 武汉理工大学硕士学位论文 窗r j 可随频率增大而缩小，随频率减小而放大“”。 连续小波变换的定义“7 1 为 ( 矽，似口，6 ) = ”c 厂( f 渺( t - 。b ) d t ( 2 - 1 ) 其中y ( ，) 称为基本小波，d 称为尺度因子，b 称为平移因子。参数日和b 均 连续变化，故称之为连续小波变换。连续小波变换也可以用内积的形式表示为 ( 睨，) ( 口，6 ) = ( 2 - 2 ) 其中虬。( ，) 为基本小波的伸缩与平移，参数口的变化对小波窗函数的形状和 频谱结构起着决定作用。当口减小时，y 。( f ) 的频谱集中于高频部分，窗口的尺 寸也小，这时候的小波函数具有较好的空间分辨率；当口增大时，y 。( f ) 的频谱 又向低频部分倾斜，窗口的尺寸增大，空问分辨率也随之降低。 小波变换所采用的小波函数必须满足“容许条件”式( 2 - 3 ) ，小波变换才存 在逆变换。小波变换的容许条件“町为 = 匕 0 是固定值，则连续小 波变换转为离散小波变换。特殊地，若口0 = 2 , b 。= 1 ，则称其为二进离散小波变 换。 2 2 多分辨率分析 多分辨率分析1 从函数空间的角度建立不同尺度空间的关系，在工2 ( r ) 空间 内函数被分解为一系列近似函数的极限。每一个近似都是原函数的逼近，并且 逼近的程度越来越高。m a ll a t 首先将多分辨率分析的方法引入小波理论，并给 出了以其名字命名的二进离散正交小波变换的快速算法。多分辨率分析和滤波 器组的设计相结合，使得小波变换具有实际的意义。多分辨分析定义为如下。 三2 ( r ) 空间的序列 ) ，j z ，构成一个二进多分辨率分析，如果 满 足以下条件。“： ( 1 ) ) 是一个嵌套序列。即3 t v o k ) ( 2 ) 所有的并在2 ( r ) 中是稠密的，1 ic l o s l 2 ( r ) ( u _ ) = l 2 ( r ) j e z ( 3 ) 所有_ 的交是零函数，即n _ = 1 0 ( 4 ) ，( f ) 一 争f ( 2 t ) 一i 或f ( 2 f ) v o ，歹z ( 5 ) ，( f ) f ( t 一2 j i ) k ，k z ( 6 ) 存在妒( ，) v o ，使得i ( f ) ；尹( ，一k ) 构成v o 中的一个标准正交基。 性质( 2 ) 确保了在无限高分辨率下对信号的逼近收敛于原始信号( 假设原始 信号具有无限高分辨率) ，即 l i m 只，厂= 厂( 对所葡l 2 ( r ) ) 具有性质( 1 ) ( 3 ) 的嵌套子空间序列有很多，但其中许多子空间并不是多 分辨率分析。要成为多分辨率分析，还必须满足性质( 4 ) 的要求，即所有的子空 间矿，( ，z ) 都是主要子空间( 或称为参考子空间) v o 在不同尺度下尺度变换的 结果，这正是“多分辨率分析”的体现。 1 0 武汉理工大学硕士学位论文 性质( 1 ) 隐含着这样的意思，即信号，( f ) 在_ 一。上的正交投影一，含有它在 上正交投影的全部信息，即 0 。= 哆厂+ ，。 女 式中， ，。是哆一。fl k p vf 多的信息。它可以用小波5 c ，肚的线性组 t 合表示，其系数等于信号关于小波y 。的连续小波变换在确定的j 和不同的k 上 的取值，即为小波级数的一组系数值。由于妒( f ) 在中，而包含于t 。中，即 t l ，且( p - i , k ( f ) ；, v r 2 妒( 2 t k ) 是t l 的一个标准正交基，故妒( ，) 可用此标准正 交基表示为 妒( ，) ；峨妒- l ( ，) = 2 以9 ( 2 卜j i ) ( 2 5 ) 女t 这就是函数妒( r ) 的两尺度关系，序列 h 。 称为两尺度序列，也是滤波器系数。 它把两个不同尺度的尺度函数妒( ，) 和q ( 2 t ) 联系起来。 对于妒( f ) 生成的多分辨率分析 ) ，由于c 比，设为关于v 的补 空间，即： n = o ) ，h 。= + 由于( x ) w oc 1 ，所以存在序列 g ，) 使得： y ( x ) = 2 g ，妒( 2 ，一，) ( 2 - 6 ) r 上式是p ( ，) 关于伊( f ) 的两尺度关系， 函 是相应的两尺度序列。 2 ，3m a i1 a t 算法简介 在m a l l a t 算法。“中，( ，) 关于妒( f ) 的两尺度关系式提供了一条由尺度函数 妒。) 构造母小波0 ) 的途径。”“” 武汉理工大学硕士学位论文 由竹) 的定义式得到 l ；f ，( f ) = z g ，妒。( o 伊( r ) = 2j 2 p ( 2 t - 1 ) 将式( 2 7 ) 代入小波似( f ) 的定义式，得 将式( 2 - 8 ) 代入上式，有 用，取代2 女+ f ，上式成为 g j , k ( r ) = 2 - j 2 z g ，伊d i ( 2 一。t - k ) ( f ) = 2 - o - 1 ) 2 g ，p ( 2 ”1 ，- 2 k - t ) f = g ，妒川m + f ( f ) 妒肿( r ) = g 。仍吐) ( 2 7 ) ( 2 8 ) ( 2 9 ) 计算f ( t ) l 2 ( r ) 与上式两端的内积，便得到如下计算小波级数系数的一个公式 c 站s = 蚕m = 百d 川 ( 2 1o ) 式中，d j _ l ，= 是信号- 厂( r ) 与q ，j - i s ( f ) 的内积，一般情况下表示为 d ，= ( 2 1 1 ) 由于妒( f ) 是子空间的标准正交基，故信号在上的正交投影厂( f ) 或 ，。( f ) 可以用d 川和竹，( f ) 表示如下： ，。( ，) s p v ，f ( t ) = 嘭，竹( f ) ( 2 12 ) ， 在数学上f ( f ) 是平方可积连续函数，它是r ( r ) 的元素：d j z ) 是平 方可和序列，它是平方可和序列矢量空间1 2 ( z ) 中的元素。式说明，7 ( ，) 与 d i s ( ，z ) 有等效对应关系，在数学上称，2 ( z ) 与上2 ( r ) 之间存在着同构关系。显 然，d 比，o ) 更适合在计算机上运算。d j ，称为在分辨率2 t f ( t ) 的离散逼近。 1 2 武汉理工大学硕士学位论文 式( 2 一l o ) 的计算过程是：先计算序列九。f ( f z ) 与季一，的卷积，然后抽取偶 数下标( 隔i 抽1 ) 的卷积结果，即得到小波0 级数的系数c 似( 未z ) 。 值得注意的是，在分辨率2 。下对信号，( f ) 的离散逼近d 。( f z ) ，可以用塔 式算法来计算。这是一种迭代计算方法，推导如下。 将两尺度关系式代入妒m ( ，) 的定义式，有 9 j , k ( ，) = 2 - j 12 妒( 2 t 一i ) = 2 - o - 1 ) 2 h ，研2 ( 2 一。r 一女) 一目 ， = 薯纺吐：w ( ，) = 岛。纡- i 心) ( 2 一1 3 ) f ， 由此可以计算，( f ) 与p 。( r ) 的内积，即 d j j ； ，k 瓦。 = 瓦。d 川， ( 2 一1 4 ) 将式( 2 1 0 ) 和( 2 1 4 ) 结合起来，便得到一种计算小波级数系数的快速算法，其 过程为：由d 。开始，利用式( 2 1 5 ) 进行迭代运算( 当然应当已知序列疋，) ，陆 续计算出d 蛐、d 2 i 等等：与此同时，利用瓯pd 。pd ：。等值，m a ( 2 一i o ) 不 断计算出c 。pc ：。等小波级数系数值( 当然豇，应该是已知的) 。 一方面，计算信号在越来越低的分辨率下的逼近d 。；另一方面，同时也计 算出相邻两次逼近d 川，与d “之间的信息差c ， 。 实际中，任何测量仪器的精度或分辨率都是有限的。为不失一般性，可假 设原始信号是在口= 1 或，= 0 的分辨率下测得的，用厂o ) 或，o ( f ) 表示，它属于 子空间。在2 2 节中曾讨论过，子空间可分解成互相正交的两个子空间， 表示为 = ko w l ，kc 且k 上 k 又可做同样分解，即 k = o ，ck 且k 上 武汉理工大学硕士学位论文 照此不断分解下去，直到某一很粗的分辨率2 7 ，于是得到 k = 巧o o ( 2 1 5 ) = l 根据该式，原始信号f o ( f ) 具有下列唯一分解 j ，。( f ) = ，。( f ) + ( f ) j = l ( 2 一1 6 ) 式中，f 。( f ) 是信号，( ，) 在子空间上的正交投影或在分辨率2 。下的逼近，它 由下式确定 ，。( r ) = d j ，仍 f 6 j ( t ) 是信号在( ，= 1 , 2 ，) 各子空间上的正交投影，它们是从一个较精确的 逼近变成较粗略的逼近( 两个逼近的分辨率相邻近) 时所丢失的信息，由下式 确定 8 j ( t ) = c m ( ，) ( 2 17 ) 这一不断降低逼近分辨率的过程可以比喻成是“一层又一层的把信号进行剥皮” 的过程。当选得足够大时，“剥”下来的信息总和d ，( f ) 足够多，将足以精确 t l 表示原始信号厂。( ，) ，而最终的逼近信号厂。( r ) 的分辨率已经非常低，这样反而 ， 可以把t p ) 当成原始信号的估计，而把厂。( f ) 看成是估计误差。这就是说 j - i 用小波级数在所有分辨率下的全部系数( ，= 1 , 2 ，j ) 来代替原始信号，其误差 f 。( ，) 可以任意小。按照这种解释，式( 2 一l o ) ( 2 1 4 ) 所示的算法就是将，o ( r ) 的 信息( d o t 是它的离散表示) 表示成c 。c s 。等信息和一个估计误差( 实际上 它是在分辨率最低即2 。下的逼近) 以。这一过程实际上是在一次又一次地改