（概率论与数理统计专业论文）基于二元树复小波变换的特征提取与识别.pdf

基于二元树复小波变换的特征提取与识别 概率论与数理统计专、世 研究生：高仕龙指导教师：周杰 本文从传统的实小波( c w t ) 定义出发，研究了小波变换对信号的分解和 重构的基本原理。二元树复小波变换( d u a l t r e ec w t ) 是一种新的小波变换， 它不仅保持了传统实小波变换多分辨率特性和时频局部化的分析能力，而且 具有更好的方向选择性、平移不变性和有限的数据冗余等特点。其近似的平 移不变性恰好可以解决小波变换不能解决的囡信号平移而导致各尺度上能量 分布发生变化的问题，二元树复小波变换良好的方向选择性使其在每一尺度 上可以分解为8 个子带，反映细节特征的高频部分能分别描述+ 1 5 0 , 4 5 0 ，蝴字共 6 个方向的属性，所以它能反映出灰度图像在不同分辨率下沿更多方向的变化 情况，从而更好的描述图像的方向特征。本文将二元树复小波变换和矩阵的 奇异值分解结合在一起应用于车牌汉字特征提取，利用前者近似的平移不变 性和良好的方向选择性对预处理后的灰度字符图像进行分解和重构，得到的】 个低频子图和6 个高频子图，利用矩阵奇异值分解提取每个子图的稳定的奇 异值特征构成一个特征矢量，为了提高神经网络的计算效率和收敛率，先对 特征矢量进行降维和归一化处理，然后输入b p 神经网络进行训练和模拟，得 到了很好的识别率。 最后将实验结论同二维实小波变换所做的结果作了比较，前者性能明显 优于后者。 关键词：模式识另0 特征提取二元树复小波变换奇异值分解神经网络 ac h a r a c t e rf e a t u r ee x t r a c t i o nb a s e do n d u a l t r e ec o m p l e xw a v e l e tt r a n s f o r ma n dr e c o g n i t i o n m a j o r ：p r o b a b i l i t ya n d s t a t i s t i c s p o s t g r a d u a t e ：g a os h i l o n g t e a c h e r ：z h o uj i e t l l i sp a p e rb e g i n sw i t ht h ed e f i n i t i o no ft r a d i t i o n a lr e a lw a v e l e tt r a n s f o r n l ， a n dt h e ne x p l o r e st h ep r i n c i p i u ma b o u th o wt od e c o m p o s ea n dr e c o n s t r u c ts i g n a l w i t hi t t h ed u a l t r e ec o m p l e x 、v e l e t ( d t c w t ) i san e ww a v e l e tt r a n s f o i t i i i t n o to n l yk e e p st h em u l t i r e s o l u t i o na n dt h ea n a l y t i ca b i l i t yt ot i m e f r e q u e n c y l o c a l i z a b i l i t y , b u ta l s op r o v i d e sg o o dd i r e c t i o n a ls e l e c t i v i t y s h i f ti n v a r i a n c ea n d l i m i t e dd a t ar e d t m d a n c yw h i c ha r el a c ki nt h et r a d i t i o n a lw a v e l e tt r a n s f o t i n i ti s i u s tt h es h i f ti n v a r i a n c eo fd t c w ts o l v e dt h ep r o b l e m ，v a r i a t i o no fe n e r g yi n e a c hl e v e lo ft o e 伍c i e n tf o rt h es h i f to fs i g n a l w h i c hc a nn o tb es o l v e du s i n gr e a l w a v e l e tt r a n s f o r m ；t h eg o o dd i r e c t i o n a ls e l e c t i v i t ym a k e sd t c w tq e te i g h t s u b b a n d si ne v e r yl e v e l t h eh i g h - f r e q u e n c yw h i c hr e f l e c td e t a i lf e a t u r ec a n d e s c r i b es i xd i r e c t i o n a lc h a r a c t e r i s t i c s ( + 1 5 0 , + 4 5 0 ，+ 7 5 0 ) r e s p e c t i v e l y , s oi tc a n o b t a i nm o r ei n f o r m a t i o na b o u tg r a yg r a p hi nd i f f e r e n tl e v e l i nt h i sp a p e r , w e c o m b i n ed t c w tw i t hs i n g u l a rv a l u ed e c o m p o s i t i o n ( s v d ) t oa p p l yt oc a r l i c e n s ep l a t ec h i n e s ef e a t u r ee x t r a c t i o n ，u s i n gt h ef o r m e rt od e c o m p o s ea n d r e c o n s t r u c tt h eg r a yg r a p hw h i c hh a v eb e e np r e p r o c e s s e di na d v a n c ea n dg e to n e l o w f r e q u e n c ys u b g r a p ha n ds i xh i g h f r e q u e n c ys u b g r a p h s ，t h e ne x t r a c te v e r y s u b g r a p h ss t a b i l i z e ds i n g u l a rv a l u e sb ym e a n so fs i n g u l a rv a l u ed e c o m p o s i t i o n t o c o n s t i t u t eaf e a t u r ev e c t o r w em a k ead i m e n s i o nd e s c e n ta n du n i t a r yp r o c e s s i n gt o f e a t u r ev e c t o rf o rt h ep u r p o s eo fi m p r o v i n gt h ec o m p u t a t i o n a le f f i c i e n c ya n d c o n v e r g e n c er a t eb e f o r ep u ti ti n t ob p n e u r a ln e tt ot r a i na n ds i m u l a t e 1 1 1 ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h i sm e t h o dc a r lg e tg o o dr e c o g n i t i o n r a t ea n dt h ec o n t r a s tt or e a lw a v e l e tt r a n s f o r r nd e c l a r e si ti sm o r ee m c i e n tt h a nt h e l a t t e r k e yw o r d sp a t t e r nr e c o g n i t i o n ，f e a t u r ee x t r a c t i o n ，d u a l t r e ec o m p l e xw a v e l e t ， s i n g u l a rv a l u ed e c o m p o s i t i o n ，n e u r a ln e t w o r k 四川大学硕士学位论文 第一章引言 特征提取是模式识别中的根本问题。在实际问题中，如何找到性能良好又 能实时提取的特征，是能否圆满解决问题的关键，也是研究人员一直在追求的 目标。字符图像特征提取是模式特征提取中的重要组成部分。 随着模式识别技术的发展，出现了很多提取字符或图像特征的新的理论、 方法和手段。程永清等在文献 l ， 2 中从代数理论出发，导出矩阵的相似 度概念，由此构造一种提取图像特征的相似性判别函数，提出一套基于图像 相似性判别函数的特征提取和识别方法。这种方法尽可能地保留了识别信息， 是一种有应用价值的方法，但是，当图像矩阵维数较高时，这种方法计算量 猛增，计算复杂度太大；文献 3 中作者采用模拟k l 变换、奇异值分解、主 分量分析和f i s h e r 线性判别分析技术来提取最终特征矢量；也有文献中提出 对灰度图像进行k r i s c h 检测，区域划分得到边缘图像，然后统计各个方向边 缘强度或者计算每个区域各个方向的像素密度得到特征。此外，人工神经网 络 4 、h m m 方法 5 3 和小波变换也是被用来提取字符或者图像的特征矢量的常 用方法，尤其是小波变换在特征提取方面的应用更加广泛。 文献 6 中作者将小波变换的多分辨率特性和良好的时域局部化的分析能 力应用于车牌汉字特征的提取，该方法直接对灰度图像进行小波变换，然后从 不同的小波分解子图中提取小波矩构造出字符特征，然后以识别率好坏为最优 依据，进行特征矢量排序和选择，最后把特征矢量送入b 阱中经网络进行字符识 别，该方法将小波对图像结构精细特征把握能力强的优点与小波矩所具有的平 移、缩放和旋转不变性及抗噪性强的特性有机的结合起来，提取出的特征矢量 稳定、识别率高、抗噪能力强，且避免了些传统的汉字特征提取方法需要对 图像进行二值化操作而造成的汉字字符结构信息的丢失。实验结果表明该方法 可以得到比较好的识别效果。但是计算量大和高阶矩受噪声影响较大困扰了小 波矩特征的进一步应用。 文献 7 中针对与书写内容无关的笔迹，提出利用快速6 a b o r d 、波提取笔迹 图像各尺度上的m 组小波系数，然后分别提取这m 组数据的均值和方差作为特征 数据，这样每个样本得到一个多维的特征矢量用于分类，最后用支持向量机( s v m ) 叫川i 大学坝士学位论文 进行训练和识别。在笔迹库上的实验结果表明，文中基于小波系数均值和方差 的特征矢量的笔迹鉴别方法是有效的。 文献 8 中，作者将图像变换到极坐标，采用方向能量函数确定图像主轴 的方位，将其旋转到水平方向得到方向归一化图像。通过对图像的重整和正 交小波基的位移、伸缩变换，消除位移和尺度的影响，得到具有位移，尺度 和旋转不变性的小波变换系数，从而为目标识别提供了可靠、稳健的不变特 征。 文献 9 中，作者提出一种基于多尺度小波分解的离线手写汉字的特征提 取方法，通过表示为灰度图像的手写汉字的多尺度的小波分解，能在不同尺 度下提取字符的特征。在较大的尺度下，提取字符少量的结构特征，可用于 在巨大的汉字候选类集合中进行字符的粗归类，在较小的尺度下，提取字符 的细节特征，可用于在较小的汉字候选类集合中进行字符的细归类识别，这 样一种从粗到细的策略，即减少了匹配的时间，又能保持识别的精度。 上述方法主要应用了小波变换的多分辨率特性和良好的时域局部化的分 析能力，提取的字符图像的特征应用于模式识别均取得了不错的效果，但是 小波变换对字符图像进行多尺度分解势必会使计算量成倍的增加和带来大量 的冗余：而小波变换的局部化分析能力亦非常有限，每一尺度上一幅字符图 像只能分解成4 个子带，反映细节特征的高频部分仅能描述垂直、水平和对 角3 个方向的属性；而且m a l l a t 算法对小波变换中位置参数的d e c i m a t i o n 采样破坏了小波变换的平移不变性，使普通的离散小波变换( d w t ) 对信号的起 始位置是非常敏感的 1 0 ，即数字信号在时域( 或空域) 的微小移动会造成小 波变换系数分布的极大变化，这一缺点极大地限制了小波多尺度分析在模式 识别领域中的应用。为此，本文将应用一种新的复小波变换来改进上述问题， 复小波变换不仅保持了传统的小波变换多分辨率特性和时频局部化的分析能 力，还具有近似的平移不变性、良好的方向选择性和有限的数据冗余等特性。 其近似的平移不变性恰好可以解决小波变换不能解决的因信号平移而导致各 尺度上能量分布发生变化的问题，复小波变换在每一尺度上可以分解为8 个 子带，反映细节特征的高频部分能描述+ 1 5 0 , + 4 5 0 ，+ 7 字共6 个方向的属性，所 以它能反映出图像在不同分辨率下沿更多方向的变化情况，从而更好的描述 图像的方向特征。然而，尽管复小波变换具有良好的性质，但完全重构滤波 器的设计却是很困难的，而二元树复小波变换在保留了复小波变换的诸多优 2 叫川i 大字坝士学位论卫 良特性的同时，通过增加一棵额外的滤波树，且增加的滤波树的高通滤波器 和低通滤波器分别是原有的滤波树的高通和低通滤波器做一个采样点的平移 得到的，这样采用二元树滤波的形式就消除了除谓“混叠项”的存在，从而 保证了完全重构性。 二元树复小波变换的优良性质使得它在它在数字水印 儿 、信号处理、 动态估计分析、图像消噪 1 2 、数据压缩等方面都取得了较好的效果。而其 多分辨率分析和平移不变性、多方向分析能力则使之适用于特征提取、模式 识别和信号分类。 近年来，车牌识别技术逐渐成为研究热点之一。车牌识别系统已经被广 泛应用于过路收费系统和交通管理系统，有着巨大的经济价值和现实意义。 本文将以车牌汉字特征提取为例来说明二元树复小波变换在特征提取方面的 良好性能。 常见的车牌共有七个字符，第一位是汉字，通常代表车辆所属省份，或是 军种、警别等有特定含义的字符简称；第二位为大写的英文字符，一个圆点 间隔后的第三个字符是英文字母或是数字，其余的四位为数字。车牌识别与 一般文字识别不同之处在于它的字符数有限，汉字共约5 0 多个，大写英文字 母2 6 个，数字1 0 个。车牌识别系统的关键在于汉字特征的提取，也就是如 何选取既容易提取又能为识别系统提供尽可能高的模式鉴别能力的特征矢 量，为实时识别考虑，同时还要尽量减少特征矢量的维数。由于汉字结构的 特殊性和国内路况条件较差对车牌取样的污染，使得国内车牌识别更成为难 点问题。 本文利用二元树复小波变换良好的多方向分析能力对车牌汉字字符图像 进行分解和重构，得到的1 个低频子图和6 个高频子图，分别提取7 个子图 的奇异值构成一个特征矢量，然后本文为了实现基于奇异值特征的神经网络 字符图像识别方法，着重解决了以下几个问题：( 1 ) 为了降低神经网络的负担， 减少运算量，以达到实时运用的要求，首先解决了奇异值降维压缩问题；( 2 ) 为了实现奇异值的比例不变性，提高神经网络的计算效率和收敛率，解决了 奇异值矢量标准化问题；( 3 ) 为了将b p 网络的实际输出映射成一个具体类别， 解决了竞争选择问题：( 5 ) 为了使神经网络具有较好的数据映射能力，提出了 理想样本训练和理想样本与污染样本混合训练的训练策略。且通过实验证明， 先使用理想样本训练、再使用理想样本与污染样本混合训i 练的方案比单独使 1 四川大学硕l 学位论文 用上述两种方案训练更优越。最后将实验结论同二维实小波变换所做的结果 作了比较，性能明显优于后者。 本文共分五章节，第二章主要是介绍实小波的定义和二元树复小波变换 的平移不变性和多方向选择性及其滤波器结构；第三章主要介绍用矩阵的奇 异值分解提取字符图像能量特征的原理和操作过程；第四章介绍b p 神经网络 的结构、工作原理和用途以及结合二元树复小波变换和矩阵的奇异值分解提 取车牌汉字特征的识别效果；第五章总结、将来的工作。 四川i 大学碳十学位论文 第二章小波变换 2 1 实小波变换 2 ，1 ，1 小波变换定义 小波变换( w a v e l e tt r a n s f o r m ) 是近年来迅速发展起来的新兴学科，它 具有理论深刻与应用广泛的双重意义。小波变换的含义是：把某一被称为基 本小波( 或母小波) 的函数，( f ) 与待分析的信号工( r ) 作内积，即 w t i ( a ，r ) 2 2l 。( f ) ，( o a t 其中小波基函数 虬，( f ) ) 是由一个基小波o ) 通过作位移f 后，再在不同的尺 度日 o 下伸缩生成的一组函数，( ，) = p ( 三) 。 图1 小波变换的时间频率窗，口。 a ， 小波变换是一种信号的时间尺度分析方法，在时频两域都具有表征 信号局部特征的能力，是一种窗口面积大小固定不变但其形状可变，时间窗 和频率窗都可变的时频局部化分析方法。如果我们粗略的把小波变换比作用 照相机的镜头来观察目标函数j ( ，) 的话，那么尺度因子a 的作用在于：当口值 较大时，视野较宽而分析频率低，以便于作概貌的观察：当日值较小时，视 野较窄而分析频率高，可以作细节的观察( 如图1 ) 。这种性质称为小波变换 的多分辨分析，它是小波变换联系工程应用的重要方面。m a l l a t 在文献 1 3 ，1 4 中从函数空间的剖分入手引入了多分辨率分析，指出通过适当的选取尺度函 数矿( f ) 和小波函数y ( f ) 就可得到l 2 ( r ) 空间的一组正交基，从而实现对信号的 小波分解。 些型查兰塑主兰丝笙兰 2 1 2 小波对信号的分解和重构 设r ( r ) 空间上某一多分辨率分析为 一，j z ) 具有如下性质 ( 1 ) c 矿lcv ock c 。 ( 2 ) c l o s ，：( u 一) = r ( r ) ( 3 ) n 一= 0 ) j l ( 4 ) + - = 一o ，z ( 5 ) ，( x ) f ( 2 x ) “ 是_ 的正交补，设中有低通函数矽( r ) ，使得 构成 _ ，- ，z ) 的标准正交基：中有带通函数( f ) ，使得 构成 ，j e z ) 的正交补空间 形，z 的标准正交基。尺度函数矽( ，) 和小波函数 e ( t ) 满足两尺度方程 ( = 压z h o 。o ( 2 t 一七) k p ( f ) = 2 扛。( 2 ，一) 女 其中 i = 啊。= 1 办，k ( f ) 2 啬( 2 1 卜t ) ，k z 1 吩，i ( f ) 2 啬；c ，( 2 。卜 ) ，k z m a l l a t 的多分辨率分析 ，j z ) 的基本思想就是求信号函数x ( r ) 在 一，j z ) 空间中的投影系数，即将被分析的信号分解成不同尺度下的近似分 量和细节分量，令信号z ( f ) 的近似分量和细节分量分别为c k 0 ) 和矾”，则有如 下小波分解关系式 0 ”= h on - n c n 。 破“) _ ，2 o 其中气7 1 是z ( f ) 在分辨率为下的离散逼近；矾。是x ( f ) 在分辨率为下的离 散细节信号，即小波变换。上述分解过程如图2 。 6 四川大学硕士学位论文 x ( z 图2 小波对信号的分解结构图 用类似的思路不难得到小波合成过程，其基本关系式可以表示为 q 1 = ，：。c k + 啊，：。掣 i女 由上可知，信号x ( r ) 分解后的各个层次分量分别对应不同的频率段，形成 多分辨率的塔式结构( 如图3 ) 。 l l c 2 )n ( 2 h 止” l h ( 2 )i b ( 2 ) l h ( t ) b h ( 1 ) 图3 二尺度i _ ，j 、波分解子图分布 综合上述不难得出小波变换具有以下特性： ( 1 ) 具有多分辨率，即多尺度的特点，可以由粗及精的逐级观察信号。 ( 2 ) 也可以看成用基本频率特性为、壬，洄) ( 甲( ) 是妒( ，) 的傅立叶变换) 的带通滤波器在不同的尺度a 下对信号作滤波，信号经小波分解以后，小尺 度上的小波系数主要对应于信号中的高频成份，大尺度上的小波系数主要对 应于信号中的低频成份。 ( 3 ) 适当的选择基本小波，使( r ) 在时域e 为有限支撑，v 旧) 在频域 上也比较集中，这样便可以使小波变换在时频两域都具有表征信号局部特征 的能力。 四川i 大学f ! 爱士学位论文 基于此，有人把小波变换誉为分析信号的数学显微镜。至今，小波技术 己成功的应用于包括数学领域的许多学科。小波变换突出局部特征的能力使 它成为检测瞬态突变和图像边缘的有力手段，传统上常用的检测手段是匹配 滤波和傅立叶变换，但前者需要有关待检测信号的先验知识，后者则主要对 跃期持续的周期性信号有效，而小波变换则适于检测低能量的短时瞬变，而 且不需要先验知识。小波变换还是去噪的有力工具，这是因为在不同尺度下 作小波变换其实质就是用不同中心频率的带通滤波器对信号作滤波，因此把 主要反映噪声频率的那些尺度的小波变换去掉，再把剩余各尺度的小波变换 结合起来作逆变换，就能较好的抑制噪声。由于小波变换的多分辨率分析， 故也可以应用于特征提取。除此以外，小波变换还在诸如数据压缩、纹理分 析等方面有着广泛应用。 2 2 二元树复小波变换 2 2 1 二元树复小波变换的性质 尽管小波变换作为信号处理的工具已经得到了肯定，然而，一个主要的 问题是传统的离散小波变换( d w t ) 存在两方面的缺陷： ( 1 ) 不具有平移不变性。这意味着信号的微小平移将导致各尺度上的小 波系数的能量分布的较大变化。 ( 2 ) 有限的方向选择性。在普通的小波分解中，每一尺度空间只能被分 解成有限的3 个方向( 水平、垂直和斜方向) ，其方向选择性非常有限，在某 些图像处理中，往往希望通过处理后的图像在某些方向上的纹理或边界得到 增强或者通过处理得到图像尽量多的方向上的特征信息。 克服平移对信号能量分布影响的一个简单方法是不进行向下采样，但这 将带来大量的冗余，使信号处理计算量加大。k i n g s b u r y 在文献 1 5 ，1 6 中提 出了一种新的复小波变换( c w t ) ，不仅保持了传统的小波变换时频局部化的 分析能力，还具有以下特性： ( i ) 近似的平移不变性，信号的平移不会导致各尺度上能量分布的变化。 ( 2 ) 良好的方向选择性，能反映出图像在不同分辨率上沿多个方向的变 化情形，更好的描述图像的方向属性。 ( 3 ) 有限的数据冗余，对于二维信号而言冗余为4 ：1 ，对于m 维信号冗 余仅为2 ”：1 。 8 四川1 大学硕士学位论文 复小波变换的滤波系统与实小波变换的滤波系统在结构上完全相同，不 同之处在于复小波变换中使用的滤波器系数都是复数，而且输出结果也都是 复数。然而，尽管复小波变换具有许多良好的性质，但完全重构的设计却是 很困难的。而二元树复小波变换在保留复小波的优良特性的同时，通过二元 树滤波的形式，保证了完全重构性。所以，在实际应用中，我们常常用二元 树复小波变换代替复小波变换。二元树复小波变换不仅保留了小波变换的多 分辨率特性和良好的时域局部化的分析能力，同样具有复小波变换的平移不 变性、良好的方向选择性、有限的数据冗余等优良性质。 2 2 2 二元树复小波变换的平移不变性分析 我们先来考虑j = 1 的情况，设离散小波变换的分解低通滤波器和分解高 通滤波器分别为：凰( 。) 和啊( z ) ，而重构滤波器分别为h o ( z 。) 和q ( z 。1 ) 。 设输入信号为x ( z ) ( x ( t ) 的z 一变换) ，则经分解滤波器和向上采样后生 成的低通和高通系数分别为 c 1 ( z 2 ) = 去【r ( z ) 0 ( z ) + ( 一z ) h o ( 一z ) d j ( ：z ) ：三 y ( ：) q ( ：) + y ( 一z ) q ( 一z ) 再经过重构滤波器得到信号的低频部分f ( z ) 和高频部分础( z ) 卅o ) = c 1 ( z 2 ) h o ( z - 1 ) = 寺 ( x ( z ) h 。( z ) h 。z - ) + x ( 一z ) 风( 一z ) 风( z - 1 ) ( 1 ) 弼( z ) = d 1 ( z 2 ) q ( z 一1 ) = ( ( z ) q ( z ) q ( z 一1 ) + ( 一z ) q ( 一z ) q ( z 一1 ) ( 2 ) 且有 ( z ) = 剖( z ) + 爿( z ) 假设对信号x ( z ) 做一个平移，即做变换z - i x ( z ) ，且令 z - i ( z ) = 剖( z ) + 砖( z ) 我们很容易由( 1 ) 式得到 i ( z ) = l z - x ( z ) 峨( z ) 风。) + ( 一z ) 。1 x ( 一z ) h o ( - z ) 风( z 。) 9 四川i 大学硕士学位论文 2 寺 z - i x ( z ) 胃。( z ) h 。( z 。1 ) 一z - 1 x ( 一z ) h 。( 一z ) 抒。z - ) = 寺z 。 ( x ( z ) 日。( z ) h o ( z - i ) 一z ( 一z ) h 。( 一z ) 。( zi ) z - i 剖( z ) ， 同样由( 2 ) 式可以得出嬲( z ) z - i x h l ( z ) 。 从上述结论我们可以看出，小波变换不具有平移不变性，而导致平移前 后高频和低频不等的原因在于向下采样产生的z ( 一z ) ，即所谓的混叠项的存 在。为了获得平移不变性，一种可行的办法是增加一个额外的滤波带 1 7 ， 其分解滤波器分别为z - 1 h 。( z ) 和zh ( z ) ，然后分别对低通和高通输出取平 均。假设两个滤波带分别用下标口和b 来表示，则： 胃= = 1 ( c ( z 2 l 魄一) + d 留) 玩) ) 艺瞄z ) ( z ) + 预习。o r ) ) f 1 ) + a 协魄( z ) + 凰习o 瓤哼1 ) 】 2 i 暇( z ) 国十凰司晡( 司f ) + ( x ( z ) z - 1 国十设z ) 。鼠( 劝) - j 鼠( z - 1 ) i 弓 坝啦( z 溉盯1 ) + x ( - - z ) h o ( - z 溅( z - ) + 坦z ) o 溉) 一凰鹕f ) 越办岛( z 蜗仃1 ) 对五1 ( z ) 有同样的结论，即：五1 ( z ) = 妻工( z ) q ( z ) h i ( z 。1 ) 。 娜 k 讧， 咄0 8 k 沸 l 一 一 毫i 一 2 l 一 夸i 图4 一维信号的二元树复小波分解结构图 型j _ 一谨 习一蠼扛 o l 卜_ 一螺 万b 瑶辩 逢一 嚣 差选乒 翌型查兰堡主兰垡堡墨 可见，引起混叠的项( 一z ) 消失掉了，因此分解具有了平移不变性。如图 4 是j = 3 时维信号的二元树复小波分解结构图。 图5 和图6 分别是实小波变换和二元树复小波变换平移性的比较。 ) ( c ) ( e ) 分别是原信号和做一层小波分解并重构后的低频、高频系数； ( 6 ) ( d ) ( ，) 是原信号平移三个采样点后得到的信号及其分解重构后的低频、 高频系数。 ( a )( b ) 件 。一! ，一“、一 _ _ _ w0 _ _ _ _ mh _ - _ ( c )( d ) _ _ _ 一_ _ _ _ _ _ _ 以- _ _ m ( c ) ( d ) ( e )( f )( e ) ( f ) 图5 实小波变换 图6 二元树复小波变换 从图中可以明显看出平移后信号的小波分解重构的低频部分和高频能 量均有较大变化，而二元树复小波则能保持低频和高频能量的近似平移不变 性。下面我们分析当分解层数j 2 时的情形， 令，= 1 时 4 ( z ) ：= 硎。( z ) ，吃1 ( z ) ：= 巩( z ) ， 4 1 ( z ) ：= 卅6 ( z ) ，岛1 ( z ) ：= 磁( z ) ， 当j = 2 ，j ( j 是最大分解层数) 时 以( z ) ：= 硎。( z ) 玩( z 2 ) 睨( z 2 ) ， 4 。0 ) ：= h 品( z ) h 之( z 2 ) 日如( z 2 ”1 ) ， 到( z ) 础。( z ) 瑶，( z 2 ) 马：( z 2 。) ， 彤( z ) ：= 嘲6 ( z ) n ；a z 2 ) h 厶0 ) ， 则二元树复小波变换的低通系数和高通系数分别为 四川大学硕士学位论文 c 也2 。) = 古蔫x ( 哆z ( 嵋z ) ，2 j l1 2 ”1l d j ( z 2 ) = 古乏( 嵋z ) b ( 嵋z ) = 万1 x ( 屿z ) 启( 嵋z ) j = 1 ， = o女2 j 则信号x ( z ) 可以分解为 x ( z ) = f + 硝( ：) = c 。( z 一) ( z 。1 ) + d 馏2 。) ( z 1 ) = f + 砉( 嵋z ) b ( 呜z ) b 7 ( zi ) 如果考虑h o ( p 2 ”) 以及相应的爿j ，剧的支撑区间，则上式可化为 ( z ) 令 1， 1 2 0 一1 = 寺( “+ 础+ 寺( 嵋z ) ( ( 彤( 嵋z ) 彤( z 。) + ( 剧( 吒z ) 群( z 。) ) ) ( 3 ) 厶 = i 二l = 0 ( z ) = p 似 女e z p j ( z ) = 而一( ( a ) c ) z 假设剧( = ) 和倒( z ) 有如下关系 倒乜) + j 蟛( z ) 2 p 。【z ) 影( z ) 一恻( z ) = p ( z ) + 其中p 的支撑s u p p ( 尸7 ( z ) 至 o ，j 1 ) ，很显然由( 4 ) 式( 5 ) 式可以得出 倒( z ) = j 1 ( p 他) + p 他) ) 尉( z ) = 一j 1f ( p ，( z ) 一p 。( z ) ) 利用上式的关系可以得到 ( 4 ) ( 5 ) 婴型茎兰堡主兰垡堡苎 彰( 砖z ) 剧( z 。) + ( 彰( 蟛z ) b i ( z 1 ) = 寺( ( 幢，z ) p 。( z 。) + p 。( 以，z ) + p 7 ( z 。) ) 同样，如果考虑s u p p p 7 ( w j p 2 ) 和s u p p p 。( p ) + = s u p p p 7 ( p 2 ) 的取 值区间，则式剧( 叱k ，z ) 剧( z 。) + 剧( k ，z ) 剧( z “) 当1 h 2 一1 时为零，可见 只要进一步选择滤波器矾，硪，使之在第一层分解能去掉混叠，则( 3 ) 式中 ( z ) 内引起混叠的项消失掉了，故z ( z ) 可以重新表示为 ( z ) = 昙( 础+ 础+ j 百1z ( z ) ( 剧( z ) 髟( z1 ) + 彰( z ) 吲( z1 ) ) ) 且复滤波器( z ) 和尸( z ) + 意味着二元树复小波变换的系数可以看成是 具有形如：d 。( z ) = 删( 2 ) 恻( z ) 的输出，即两棵树的输出w p a 分g j 解释成 经由二元树复小波变换而得到的实部和虚部的系数，同样的假设也适用于低 通滤波器。但是，却并不存在理想正交的f i r 滤波器m 。和垃。使褥咧和倒 满足上述关系，因此，只能构建近似满足( 4 ) 和( 5 ) 式的f i r 滤波器。 2 2 3 二元树复小波变换的滤波器设计 k i n g s b u r y 在文献 1 5 中指出，为了得到具有平移不变性和多方向选择性 的二元树复小波变换，除了在滤波器结构中第一层口树和b 树的滤波器联。和 叫。与滤波器叫。和巩之间有一个采样点的延迟以外，还要求从第二层起一 棵树中的滤波器心须与另一棵树中的滤波器之闽保持半个采样值的差距。 即，滤波器分别设计为： 当j = 1 时 删。( z ) ：= 风( z ) ，叫。( z ) = = q ( z ) = z - i h o ( 一z “) ， 圳。( z ) ：= z - 1 o ( z ) ，砚( z ) ：= z - 1 q ( z ) = z - 2 “( - z 。) ， 当j = 2 ，时 0 ) ：= 风( z ) ， h , g z ) ：= z 1 风( - z “) ， f ，厶( p 2 “) ：= 已4 5 。“1 h o ( 9 2 。) ，0 3 1 1 13 四川大学硕士学位论文 f 圮( 8 z ) ：= p m ，。h g b ( e - 2 x i ( 。+ 2 ) ：矿z w p 州1 z - 1 m o d l i 峨( 8 训m 十争) ：p 州m 十；川1 1 h ( p z 一。) ，瓞 当万e 一j 1 ，争时，e j 八c 2 x t o ) 还可表达为 巧：( p 2 ) = f p 5 ，。上( 9 2 ) 卜= 1 ，o ) 嘲q ( 矿”) 出 o ，圭) 其中甜m o d ，沏r ，等价于函数二= ： 兰：呈；j ：三；：，符号l j 表示向 下取熬。 为了证明这样的滤波带设计能满足( 4 ) 式和( 5 ) ，我们引入下面的引理 和定理。 引理1 7 l ：若，n ，国e 卜丢，1 ，则函数 ，( 国) ：( ( 2 甜+ 去) m o d1 ) 一2 0 ) 一( 2 珊r o o d1 ) 一t 一( 2 r 1 棚r o o d1 ) 满足 ( c o ) = j 1 甜 一吉，。)j甜【一j u ) 一了1 o ，吉) ， 。 7 有了引理l ，我们可以证明下面的定理2 。 定理2 m 1 ：若_ ，= 2 ，j ，n b i ( z ) ：= h 。1 ( z ) 礞乜2 ) h 0 2 ) 满足下面的 关系式 最。( p 2 ”) = 皖化2 ) e _ 昙，o ) 【o 娄) 四川大学硕十学位论文 哦他2 ”) - 哦7 ( p 2 ”) 一三，o ) ， o ，三) 一个滤波器是实的当且仅当它的负频域响应是正频域响应的复共轭 1 7 。由于风是实的，从前面滤波器的构造我们知道倒也是实的，由定理2 知剧也是实的，因而按上述方式设计的滤波器满足( 4 ) ，( 5 ) 两式，且两棵 滤波树产生的小波系数纠和珥都是实的。 2 2 4 二元树复小波变换的多方向选择i 生分析 按上述方式设计的滤波器结构可以确保b 树中第一层的向下采样取到a 树中因隔点采样运算而舍弃的、不能保留的采样值；同时可以保证两棵树的 所有样值序列都具有统一的间隔，在线性相位滤波器中，这就要求一棵树中 的滤波器为奇数长，而另一棵树中的滤波器为偶数长，则两棵树将会呈现较 好的对称性。 所以，在第，层，二元树复小波变换对二维信号x ( 互，z ，) 分解的结果为 q ，。( 毛，z ：) = ( 2 7 山) ( 群( 五) 蟛( z ) ) ( 群( z ：) + 州( z ：) ) ( 毛，z ：) ) ， d 匕，6 ( z 1 ，z 2 ) = ( 2 山) ( 群( z 。) 渊( z 。) ) ( 彰( 乙) + 恻( z ：) ) 工( 五，z ：) ) ， d 厶6 ( 毛，z 2 ) = ( 2 。山) ( 嘭( 丑) 赶搿( z ) ) ( 群( 毛) + l ( z 2 ) ) ( 互，z 2 ) ) ， 睨，。( 而，乞) = ( 2 山) ( 剧( 弓) 土f 吲( z 1 ) ) ( 嘭( z ：) + i 倒( z ：) ) x ( 毛，z ：) ) ， 其中( 2 一j ，) 表示以2 ，向下采样，下标a 和b 分别对应里的十和一。可以看 出，二元树复小波变换在每一层一共有4 个共轭复数滤波对。在实际运算中， 对行和列进行滤波处理时，常将其各自的虚部单位计为和f ，这样，每个滤 波对的输出结果就是一个四元复数向量组( r ，s ，f ，“) 垒r + s i + f f ，+ u i , i 2 ，其中 r 代表实数单元。为了得到常见的二维复数输出结果，令= = i 和 一= i 2 = i ，得到两组复数对p 一“) + 如+ f ) 和p + “) + f ( 一s + t ) ，分别对应于口 树和b 树的输出系数。则对应的每一层分解输出两个低频子带、，和6 个高 频子带矗，如，吃，啊，吃，魄。k i n g s b u r y 在文献 1 8 中指出这6 个子带分别指向 1 5 0 + 4 5 0 , + 7 5 0 。 由此可知，在普通的小波分解中，每一尺度空间只能被分解成有限的3 四川大学硕士学位论文 个方向( 水平、垂直和斜方向) ，其方向选择性非常有限。在信号处理尤其是 图像处理中，纹理或边界的方向变化一般都是连续的，传统实小波变换有限 的方向选择性很难满足分析连续的方向的要求，而二元树复小波变换不仅保 持了传统小波变换良好的时频局部化的分析能力，还具有良好的方向分析能 力，它能反映出图像在不同分辨率上沿多个方向的变化情况，从而更好的描 述图像的方向属性。 图7 二维实小波滤波器的脉冲响应 图8 二维二元树复小波滤波器的脉冲响应 如图7 、图8 是二维二元树复小波和普通的实小波滤波器的脉冲响应的比 较，从图中可以明显的看出，二元树复小波变换的方向选择性明显优于实小 波。图9 是二维信号的二元树复小波分解结构示意图。 二元树复小波变换的优良性质使得它在它在信号处理、动态估计分析、 图像消噪、数据压缩等方面有很大的用途。而其多分辨率分析和平移不变性、 良好的方向选择性则使之适用于特征提取、模式识别和信号分类。 匹| 川i 大学硕十学位论文 图9 二维信号的二元树复小波分解结构示意图 7 砖( z l ，z 2 ) 碍( z 1 ，z 2 ) 西。( z 1 ，z 2 ) 肆( z l ，z 2 ) 蝴。( z l ，z 2 ) d l ( z l ，z 2 ) 四j 】i 大学硕士学位论文 第三章特征提取 3 1 数字图像的特征 特征提取是模式识别中的根本问题。在实际问题中，如何找到性能良好又 能实时提取的特征，是能否圆满解决问题的关键，也是研究人员一直在追求的 目标。字符图像特征提取是模式特征提取中的重要组成部分。 随着模式识别技术的发展，出现了很多提取字符或图像特征的新的理论、 方法和手段。程永清人等从代数理论出发，导出矩阵的相似度概念，由此构造 一种提取图像特征的相似性判别函数，提出一套基于图像相似性判别函数的特 征提取和识别方法：周德龙等人采用模拟k l 变换、奇异值分解、主分量分析和 f i s h e r 线性判别分析技术来提取最终特征矢量；也有文献中提出对灰度图像进 行k r i s c h 检测，区域划分得到边缘图像，然后统计各个方向边缘强度或者计算 每个区域各个方向的像素密度得到特征。此外，人工神经网络、h m m 方法和小波 变换也是被用来提取字符或者图像的特征矢量的常用方法。 字符图像特征大致可以划分成四类：直观性特征( 或几何特征) ，灰度的 统计特征，变换系数特征和代数特征。由于代数特征表征了图像的内在特性而 得到重视。利用矩阵的奇异值分解提取的特征是一种代数特征，它具有稳定性、 转置不变性、位移不变性和镜象变换不变等性质，因而在模式分类中有广泛的 应用。 在字符特征提取过程中，特征选取的好坏将直接影响识别率的高低，通常 选取的字符特征应满足以下几个条件： ( 1 ) 直观易表征性，选取的特征应符合字符特点，易于提取，便于在计算 机上实现特征提取时的计算量不亦太大。 ( 2 ) 正交互补性，选取的特征之间应尽可能的相互独立，具有互补性，特征 的维数应尽量少，以提高识别效率及满足实时性要求。 ( 3 ) 稳定容错性，选取的特征必须足以区分各字符，特征应该稳定，受字型 等因素影响越小越好。 3 2 矩阵的奇异值分解 从线性代数的角度来看，一幅数字图像可以看成是一个由非负标量项组 1 8 四川大学硕士学位论文 成的m n 的矩阵。设a r ”且元素非负，r a n k ( a ) = r ，则存在m 阶正交阵u 和”阶正交阵v 使得 田 0 2 o - 1 盯2 q2 0 是a 刚茔鄙非等俞异值。 在图像处理中，通常用f ( f r o b e n i u s ) 一范数来衡量一幅图像矩阵的能量， 又由矩阵奇异值分解的定义我们有： ，2 = t r ( a 7 爿) = 护f 矿 ；： 7 ，7 u ；： 矿7 = 护“v ，