（计算数学专业论文）可变形模板在字符识别中的应用研究.pdf

中山大学硕士论文 可变形模板在字符识别中的应用研究 专业：计算数学 硕士生：李凯 指导教师：杨力华 摘要 7 6 6 3 6 2 本文研究了可变形模板在字符识别中的应用问题。主要思路包括，提取了 数字字符封闭的轮廓曲线坐标，对字符的两个一维坐标曲线信号进行分解，运用 随机信号处理方法处理分解后的信号，再用小波重构坐标曲线。在利用小波基进 行图形形状变形描述时，本文采取引用曲线曲率来控制形状的变形方法，得到了 较好的手写数字字符局部变形，而且这种变形具有良好的抗噪性能；在变形模板 匹配公式中，我们利用了多分类器集成原理和改进了的h a u s d o r f f 距离。在对手 写数字字符及一般物体图形实验中，本文的方法取得了较好的效果；此外，本文 还探讨了基于h a u s d o r f f 距离的细化字符的识别问题。 关键词可变形模板小波h a u s d o r f 距离字符识别细化轮廓 主坐查兰堡主至壅 a p p l i c a t i o ns t u d y o fd e f o r m a b l e7 r e m p l a t eo n c h a r a c t e rr e c o g n i t i o n m a j o r =c o m p u t a t i o n a im a t h e m a t i c s s t u d e n t ：k a il s u p e r v i s o r ：l i h u ay a n g a b s t r a c t t h i sp 印e rs t u d i e sm e 印p l i c a t i o no fd e f 0 加a b l et e m p l a t e s i nc h a r a c t e r r e c o g n i t i o n t 1 l em a i ni d e ai s ： d e c o m p o s e 也et w oc o o r d i n a t es e r i e so ft h ec l o s e d c 叻t o u ro fac h a r a 吐e rt ob er e c o g n i z e db yw a v e l e t 协n s f o r m ，m e np r o c e s st h e w a v e l e tc o e f 玎c i e m s 耐t 1 1t 1 1 e 舢d o ms i g n a lp r o c e s s i l l gm e m o d s ，f i n a l l y ，r e c o n s 劬l c t t 1 1 ec o o r d i n a t ec u r v e sb yw a v e l e tr e c o n s 劬l c t i o na k o r i t l l m mt h i sp a p e r ，m es h a p e d e f o 加强t i o ni sc o n 扛d l l e db vm ec u r v a t l l r co ft h ec o n t o l l rc u r v e s ； c l a s s i f i e r s c o m b i n a t i o nm e t h o da n dm o d i 6 e dh a u s d o r f fd i s t a i l c ea r eu s e di n 廿l ed e f o 珊a b i e t e m p l a t em a t c h i n gf b r m _ l l l a e x p e r i m e n t so n 也er e c o g n 砸o no fd i g i tn u l f n e r a l sa n d o t h e ro b j e c t s h a p e ss h o wt h a t t l l e p r o p o s e dm e m o dp r o v i d e ss a t i s 母i n gb e t t e r p e r f 0 n a l l c eb o t hm l o c a ld e f o 咖t i o na i l da n t i n o s ea b i l i 甜f i n a l l y ，r e c o g n i t i o no f 协i 皿e dc h a r a c t e r si sa l s os t t i d i e db a s e do nh a u s d o r f fd i s t a n c ei nm i sp 叩e r k e y w o r d s ： d e f o r m a b l et c f n p l a t e ，w a v e l e t ，h a u s d o r f fd i s t a n c e ，c h a m c t e rr e c o 印i t i o n ， t h i m l i n 昏c o n t o 砒 l i 中山大学硕士论文 第一章绪论 本章内容安排如下：第1 节简介模式识别及0 c r ：第2 节简述可变形模板 现状及其存在的问题；第3 节讲述可变形模板及其研究背景；第4 节概述了本 文所作工作：最后概括本文章节安排情况。 1 1 模式识别及o c r 概述 模式识别，就是通过计算机用数学技术方法来研究模式的自动处理和判读。 我们把环境与客体统称为“模式”。随着计算机技术的发展，人类有可能研究复 杂的信息处理过程。信息处理过程的一个重要形式是生命体对环境及客体的识 别。对人类来说，特别重要的是对光学信息( 通过视觉器官来获得) 和声学信息 ( 通过听觉器官来获得) 的识别。这是模式识别的两个重要方面。市场上可见到 的代表性产品有o c r ( 0 p t i c a lc h a r a c t e rr e c o g n i t i o n ) ，语音识别系统。 0 c r 是指光学字符识别技术，是自动识别技术研究和应用中的一个重要领 域。光学字符识别技术的工作原理是通过扫描仪或数码相机等光学输入设各获取 纸张上的文字图片信息，采用光学的方式将文档资料转换成原始黑白点阵的图像 文件，利用各种模式识别算法分析文字形态特征，判断出文字的标准编码，通过 识别软件将图像中的文字转换成文本格式，并按通用格式存储在文本文件或者数 据库当中，还可以利用文字处理或者编辑软件或者的进一步加工。 通常，一个o c r 系统由以下几个部分组成，如图卜l 所示： 图卜1o c r 系统的组成 中山大学硕上论文 下面简单地对图卜1 做些说明： 预处理 预处理通常包括大小归一化、平滑、细化或轮廓化等处理过程。去噪声， 加强有用的信息，并对输入测量仪器或其它因素所造成的退化现象进行复原。预 处理的方法也因噪声的不同会稍有区别。 版面分析 版面分析主要是把文字与图像部分分开，这对于纯文字的文档是小必要的。 但是，随着研究的不断细分，这部分作为一个独立的研究分支也是很有必要的。 而且，这一研究领域的存在着很多难题，也越来越引起研究人员的兴趣。 行分割 行字切分是将整页版面的原始图象先按书写行分割开。 字符分割 字符分割是从每行中切分出单个字符图象。字符分割o c r 技术的一个难题。 它是字符识别的前提，字符分割的好坏，直接影响到字符的识别率。目前为止， 字符分割还没有完全有效的解决方案。字符分割主要面临的难题是各种各样的粘 连字符的分割。 特征提取 特征提取部分是o c r 系统的关键部分。字符的表达形式有多种，每种形式 又可以选择不同的特征，每种特征又有不同的抽取方法，这就使得判别方法和准 则以及所用的数学工具不同，形成了多样的的字符识别方法。总的来说，不同的 特征提取方法决定了识别系统采用不同的处理方法，通常可以分为结构模式识别 方法、统计模式识别方法、统计与结构相结合的识别方法以及人工神经网络方法 等。 识别对提取特征后的字符识别。 后处理 后处理是指对单字识别的结果，利用词义、语义等上下文先验信息进行识 别结果的确认或纠错。 分类 分类其实就是一个分类决策的过程。它是在特征空间中用统计方法把识别 2 中山大学硕士论文 对象归为某一类别。基本做法是在样本训练集基础上确定某个判决规则，使按这 种判决规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。 字符识别的关键是获取字符的特征。这些手段分两大类：全局分析和结构 分析。对全局分析，我们可以使用模板匹配、象素密度、矩、特征点、数学变换 等技术。这类的特征常常和统计分类方法一起使用。对结构分析，多半需要从字 符的轮廓或骨架上提取字符形状的基本特征，包括：圈、端点、节点、弧、突起、 凹陷、笔画等等。与这些结构特征配合使用的往往是句法的分类方法。 字符识别的方法之一就是模板匹配法。模板匹配法的基本思想是：要判断 幅大图像中是否存在某种已知的模板图像，则以一幅与该图像有着相同尺寸和 方向的图像为模板，通过相关函数的计算可以在图中找到目标，确定其坐标位置。 早期所使用的大多是刚性模板 4 1 ，刚性模板仅仅是简单的对图形进行旋转、平 移、尺度变化等变形。而在实际字符识别应用中，字符受众多因素的影响( 如成 像系统中的噪声、成像系统中的不同视角引起的变化、部分遮掩等) ，字符的变 形是必然的。这就要求模板本身能够适应字符变形而去改变形状。这样可变形模 板就应运而生。可变形模板由于适应性强，近年来得到了比较好的应用 8 4 0 。 变形图形是可变形模板匹配中最重要的一环，其困难在于人的视觉对模板图形变 形的认知，简而言之就是，模板图形的变形程度需要限制在一个什么范围才不会 引起原型模板主要特征的缺失；而且模板变形具有一定的抗干扰能力。 1 2 可变形模板现状及存在问题 在模式识别中，可变形模板是基于模板匹配一个非常经典的问题。早在七 十年代初，人们就开始了可变形模板的研究。正因为可变形模板在模式识别和计 算机视觉中所起的重要作用，几十年来人们进行了大量的工作，取得了不少研究 成果，针对各种应用，如：图像视频数据恢复 6 l ，6 2 、图像识别和验证 8 ，1 4 ，3 0 ，6 3 、图像分割 1 5 ，2 9 ，4 6 ，6 5 和对象跟踪 2 9 ，4 4 等，提出了不同的或改进 的可变形模板匹配算法。然而，至今仍无统一的理论，还没有哪一种可变形模板 匹配方法可以对所有的图像都能进行理想的识别、跟踪等，也不存在所有方法对 中l l j 大学硕士论文 某一类图像均可获得较好的处理结果。寻找一种通用的、可适合所有图像识别等 应用的可变形模板匹配方法一直是人们不断追求的梦想。 可变形模板都存在着如下共同的问题：在形变过程中，其形状控制较为 复杂，如图卜2 ，当模板向内收缩时，可能收缩到一点，而如图卜3 或图卜4 ， 形变后，将出现纽结，与原来的模板形状相差很大。这些问题，般由能量公式 隐含地控制，或在算法设计时加入有关参数的方法进行解决，一般都没有明确提 到如何避免这些问题。在本文第4 章，本文将引入一个改进的模板结构，初步解 决这些问题；几乎所有文献的能量匹配公式都引自文献 8 4 9 ，而这公式 8 有些缺陷，详见本文第4 章第3 节。 哂 图1 2 模板在内力作用下 可能收缩为一点 图1 3 向内收缩曲线将会 扭曲 上面三个图中的箭头表示形变方向 1 3 可变形模板及其研究背景 图1 - 4 向内收缩会发生纽 结 所谓可变形模板c 8 4 9 是使模板图形发生变形( 而不仅仅是平移、旋转、 尺度变换等简单的几何变形) 以匹配到显著的图像特征。可变形模板匹配法把统 计方法与能量方法相结合，根据设计好的模板，选取合适能量公式，然后将初始 形状实施形变，直到达到能量极小。 早期关于可变形模板的研究主要集中在刚体形状匹配，其中待匹配图像相 对于模板图像只经过平移、旋转、尺度变换和仿射变换，所有这些都可以通过相 关匹配或h o u g h 变换来获得。1 9 7 3 年w i d r o w 等人提出橡皮模板 2 2 。才使得可 变形模板概念真正进入计算机视觉领域。1 9 8 8 年k a s s 等人提出的称为跚口盹的 主动轮廓模板 4 9 ，先给定一个合适的初始化轮廓，s ”口妇通过梯度下降法收敛到 4 中山大学硕士论文 最近的局部极小值。但k a s s 的肌口拓的模板方法非常依赖于局部信息，最初实现 的s h a 妇模型对它的初始位置和图像噪声是非常敏感的，轮廓经常会收敛到能量 函数的某个局部极小值人们提出了许多方法来解决这个问题，如：1 9 9 0 年 m e n e t 6 7 等人提出b 刀出，目标轮廓用b 样条来表达，轮廓的表达更加有效，同 时也能隐式地表达角点；1 9 9 3 年g e i g e r 4 4 提出了一种非迭代的方法，它允许轮 廓搜索起始点周围很大一块区域的所有地方通过加上不同的正则化约束，还可 以获得有各种不同特征的变形模型；1 9 9 4 年n e u e n s c h w a n d e r 4 5 等人允许用户 点出理想轮廓上的两个端点，在最优化过程中边缘信息从端点向中心传播；1 9 9 6 年c o x 等人 6 5 在图像分割中同时利用边缘和内部信息他们的算法通过一个快 速的分图算法来最小化外部边缘代价和内部区域收益的比值，在图中的闭合路径 相当于图像中闭合轮廓。而1 9 9 6 年j a i n 等人在文献 8 提出了基于二维空间基 函数的可变形模板方法，用二维空间的有限基函数代替无限基函数，以达到模板 变形，并提出了不同予以往的s 聆口妇匹配公式，而是基于形状边缘的匹配公式， 该方法已经成功应用到字符识别 9 等上。 1 4 本文主要工作 本文考虑用小波基在可变形模板中对手写数字字符进行识别。本文对手写 数字字符图形首先对字符轮廓跟踪，提取字符图形坐标曲线，化二维图像为两 个一维坐标曲线信号；然后对这两个一维坐标曲线信号进行小波分解重构。x 扛 门字符的变形做了些探索和研究，一是用不同小波以及尺度的选择：二是随机函 。数的选择。 对于某个数字字符有可能成为另一个数字字符的一部分，或者有部分噪声 时，识别较困难情形，选用了改进的h a u s d o r f f 距离匹配，对识别情况加以改 进。在此基础上改进了可变形模板匹配公式。详细内容请见第4 章。 在第4 章基础上，研究探讨了基于h a u s d o r f f 距离的细化字符识别。详细 内容请见第5 章。 中山大学硕士论文 1 5 本文内容安排 本文共分为五章： 第一章绪论，对可变形模板做了简单介绍； 第二章是为后面章节做准备，介绍本文使用到的相关基础知识； 第三章研究现有的可变形模板匹配算法，并指出现有方法的不足，继后提 出本文的字符可变形模板匹配算法； 第四章基于小波的可变形模板在数字字符识别及一般图形中的应用，介绍 方法和实验结果； 第五章探讨了基于h a u s d o r f f 距离的细化字符识别。 6 中山大学硕士论文 第二章基础知识 为了笔者更好地阐述后继章节和让读者更好地了解本文，有必要在本章介 绍一下本文所使用到的相关基础知识。本章的结构如下：第1 节介绍独立分类 器集成理论机器在字符识别中的应用；第2 节介绍图像二值向量相似性度量； 第3 节介绍在图象处理课程中常使用的小波分析方法；第4 节介绍骨架的提取 算法。 2 1独立分类器集成理论及其在字符识别中的应用 目前，多分类器集成是模式识别中的一个重要趋势，研究工作者对此进行 了很多的研究，提出了很多集成方法。一般来说，人们都希望参与集成的分类器 具有“独立性”。 2 1 1 独立分类器的概念 4 人们在讨论多个分类器的关系时经常提到“独立性”的概念。首先明确定义 分类器的独立性，作为进一步论述的基础，定义如下： 定义2 1 4 设待分类模式类别数为，记为：脚。，国：。：共有m 个分类器， 其中的第j 个分类器对输入样本x 输出的后验概率估计向量为置( x ) ，f - 1 m ； 墨( j ) 是一个维向量，其第_ ，维分量是该分类器估计x 属于，类的后验概率， 即： s ( 盖) = 【p f ( qx ) ，办( ，i 柳，b ( 吐i 司】7 ( 2 一1 ) 中山大学硕士论文 令s ( x ) = s 。( 盖) ( x ) s m ( z ) ( 2 2 ) 即：分向量昂组合成一个新的向量矾的，p ( 置) i 哆) 是在样本属于第f 类 时向量墨c 的的条件概率密度，即：p ( 置( ) i q ) = p ( p ( ql x ) ，p ；( i x ) ) ；又 设p ( s ( x ) l 哆) 是在样本属于第，类时向量目的条件概率密度。如果满足： p ( s ( z ) i q ) = n p ( 置( 工) i q ) f = 1 称这m 个分类器是相互独立。 2 1 2 分类器的集成准则 ( 2 3 ) 下面推导在前面的定义下独立分类器的集成准则，讨论中假定各类别先验概 率相等。由贝叶斯公式，我们有： p ( 脚，is ( r ) ) 2 p ( 5 ( z ) iq ) p ( q ) p ( x ) ) 吖 = ( np ( s ，( x ) q ) ) p ( 哆) ，p ( s ( x ) ) i ；l 埘 2 ( ( n ( p ( qs ( z ) ) ，( 置( x ) ) p ( q ) ) ) p ( 哆) p ( s ( ) ) ) p ( q ) “双砌 ( 2 4 ) 根据贝叶斯最小错误率准则，我们应当选择使p ( q i s ( x ) ) 达到最大的类别 q 作为判别结果。设各类别先验概率相等，即：p ( q ) = 1 ， 由s ( 抑的定义得到： p ( 一s ( x ) ) = p 一( 哆i 工) ( 2 5 ) 中山大学硕士论文 定义 则： 月e 习= ( 1 ，”一1 ) + n p ( s ( x ) ) p ( s ( x ) ( 2 6 ) p ( z q i s ( 并) ) = ( n b ( q l x ) ) 聃 ( 2 7 ) i = l 又因为p ( qf s ( ) ) = 1 ，所以： mnm p ( 哆1 s ( x ) ) = ( 兀n ( qi x ) ) ( n ( 坼i x ) ) ( 2 8 ) 因此，我们可以用下式作为集成系统的类别判决函数： 村 g ，( x ) = 兀a ( q l x ) ( 2 9 ) f _ l 在贝叶斯准则下，我们应该选择使钉( x ) 达到最大的类别作为集成系统的识 别结果。利用这个结果可以为第4 章模板匹配公式做准备。 2 2 h a u s d o r f f 距离和二值向量相似性度量 2 2 1h a u s d o r f f 距离 h a u s d o r f f 距离是描述两组点集之间相似程度的种量度，它是两个点集之 间距离的一种定义形式 5 0 ，假设有两组集合彳= 慨，咋) ，占= 岛，) ，则这 两个点集合之上的h a u s d o r f f 距离定义为： 定义2 1 5 0 日( 一，占) = m a x ( 厅( 一，占) ，序( 占，彳) ) ( 2 一1 0 ) 其中： 中山大学硕士论文 j j l ( 4 ，占) = 喈1 幽怕圳 ( 2 1 1 ) ( b ，4 ) = 1 学喈怕一l i ( 2 1 2 ) ”j i 是点集卿点集锏的距离范式( 如：l ：或e u c l i d e a n 距离) 。 这里，式( 2 9 ) 称为双向h a u s d o r f f 距离，是h a u s d o r f f 距离的最基本形式。 式( 2 1 0 ) 、( 2 一1 1 ) 中的五，口) 和五( e 一) 分别称为从一集合到b 集合和从口集合 到a 集合的单向h a u s d o r f f 距离。即：j j0 ，口) 实际上首先对点集a 中的每个点 矾到距离此点口f 距离最近的b 集中的点嘻之间的距离1 l q 一6 ，i f 进行排序，取这样 的距离中的最大值作为西0 ，b ) 的值；由 一) 同理可得。 由式( 2 _ 9 ) 知，双向h a u s d o r f f 距离疗臼，口) 是单向距离由o ，b ) 和血 4 ) 两 者中的较大者，它度量了两个点集问的最大不匹配程度。 考虑到由式( 2 9 ) 和式( 2 1 0 ) 、( 2 1 1 ) 定义的基本形式的h a u s d o r f f 距离易受 噪声的影响，或物体局部发生遮掩，此时若使用基本形式的h a u s d o r f f 距离必将 使计算结果产生较大的偏差，进而影响整体匹配识别结果，故而有改进的 h a u s d o r f f 距离 5 0 的定义如下： 定义2 2 5 0 ： 日( 一，占) = m a x ( ( 4 ，b ) ，k ( 曰，爿) ) ( 2 1 3 ) 其中， k ( 口，一) 。磊：吧乎l i a 一6 吣吃( 一，b ) 。芝：1 脚j | 6 一口| | ( 2 1 4 ) 这里毳：表示从口集合到爿集合的排序后的距离值集合中的第髟个值；笔表示 从彳集合到b 集合的排序后的距离值集合中的第三个值。 本文采用改进的h a u s d o r f f 距离来进行模板匹配，其定义如下： ) 2 专互卿怕“ 化- 1 其中，玎：表示从膘合到矶何的升序排序后的距离值集合中的前i 个值数目。 改进的h a u s d o r f f 距离对噪声不太敏感，可避免由于部分噪声像素点的干 扰带来的偏差。 改进的h a u s d o r f f 距离将会在第4 章用到，来度量图形轮廓点集近似的程 1 0 中大学硕士论文 度；在第5 章将会用改距离来度量字符细化后的点集的相似度。 2 2 2 二值向量相似性度量 维的二值向量z 定义为： 定义2 3 【5 7 ： 二( 而，磊，勿) ( 2 1 6 ) 其中z i = o 或1 ，j - 1 ，2 ，m 令n 为全体维二值向量集合，则单位向量，q 的每个元素z ；= l ，f - l ， 对应的z 的补定义为z = 一z ；同时定义z 的幅值为：i z i _ 毛。 令工，y q ，s j ，( j ， 0 ，l ) 为：在盖中的f 与在】，中对应位置的，同时 出现相匹配而得出的和，即： 品= 民( j ) ( 2 1 7 ) 其嘲“) - 撼帆。 则有，s 。( z ，】，) = x l 品。( 工，】，) = x y 。 基于墨。，晶。，墨。和，存在和y 之间的相似性估计值鼠墨d ，有如下定义 度量s 佤y )d c 墨y ) 墨。墨o + & l j a c c a r d 墨1 + 墨o + & l墨1 + 墨o + 最1 墨i 一s l o 氐ll 墨。一墨。晶。 c o r r e l a t i o n 仃22 仃 其中盯= 【( s 。+ s 。x 品。+ 品。) ( 戈+ 置) ( s 。+ 晶。) “2 表2 1 中山大学硕士论文 由表2 1 知： ，何，y ) - l ，1 i ( ，) = l l ，( j ，) ：( - _ ) ：1 ，足。，( ，7 ) ：k ( _ ，) ：一卜 本小节将用在第4 章，用来匹配二值图像近似程度。 2 3 小波分析 2 5 6 7 小波分析作为一种时频分析工具，在短短的数十年问，受到了研究人员广泛 的关注和研究。虽然小波分析的研究已相当深入，已可以证明其时频分析能力相 比傅立叶分析要好得多，但在实际应用上，还远远未及傅立叶分析的一个子集 d c t ( 离散余弦变换) 。究其原因是与d c t 相配套的一系列工具已相当成熟，但与 小波分析配套的工具则少之又少。不久前，新发布的 l p e g 一4 标准，可以说是小 波分析到今为止的最大的一个应用。在图象分析领域中，小波分析可以说是佼佼 者，所以我们有必要作一个简单介绍。 小波变换是一种信号的时间一尺度分析方法，他具有多分辨率分析的特点。 而且，在时域、频域都具有表征信号局部特征的能力，是一种窗口大小固定不变 但其形状可变，时间窗和频率窗都可变的时频局部化分析方法。即在低频部分具 有较高的频率分辨率和较低时间分辨率，在高频部分具有较高的时间分辨率和较 低的频率分辨率，很适合探测正常信号中夹带的瞬态反常现象并展示其成分，所 以被誉为分析信号的显微镜。 中山大学硕士论文 2 3 1 r 俾2 ) 的可分离小波正交基用尺度函数中和小波的可分离乘积构造 尺度函数。和一维多分辨率逼近( 巧) ，相联系。令，呼五。：是用哆= l o _ 定义的可分离二维多分辨率。令2 为细节空间，它等于低分辨率逼近空间哆在 吆。中的正交补： 嘭。= 呼。眩 ( 2 1 8 ) 为了构造r ( r 2 ) 的一组小波规范正交基，下面的定理 3 建立了每个细节空 间昨的一组小波基。 定理2 1 2 ：令伊是一个尺度函数， l l ，是对应的生成r ( 胄) 的一组小波规范正 交基的小波。定义三个小波如下： y ) = 妒( 置) y ( 屯) ，妒( x ) = 矿( 西) 伊( 屯) ，y 。( 曲= y ( 五) y ( 屯) ( 2 1 9 ) 对a = ，v ，d ，记 眩勘) = 扣( 羔；鱼，气净) ( 2 _ 2 0 ) 则小波族 y ；，。，妒；，。，y ；，。) ： 是胛的组规范正交基；且 ( y ；。，y ；，。，妒7 。) ( ，。) 。：， 是r 职2 ) = 可= 可的一组规范正交基。 对，r ( 矗2 ) ，我们有分解算法： 中山大学硕士论文 屯= 吉砝i 瓦h 。 = 瓦= ( 不“。) 唬，如= 一2 hg 础如c ，+ 1 。 ，屯= 吉i i 瓦i 州 。 删n 铀= 云磊i 川m 。 肼月 ( 2 2 1 ) ，( z ，y ) = c 抵女：腩南+ d 氖，也妒。：( 2 _ 2 2 ) 矗屯1 2， 1 1 ，七2 ， 五= ，v ，d 式( 2 2 0 ) 、( 2 2 1 ) 表明，对二维张量积小波，分解过程可以先对“行”作 变换，然后对“列”作变换，这是使用张量小波的优点。 2 3 2 二进制小波 2 4 函数矿r ( r ) ，如果满足 q = 腊如 佃 则称此函数为母小波，上式称为小波函数底可容许性条件。 对v r ( r ) ，定义它的小波变换为 ( 2 2 3 ) ( 町 6 ) = _ ，( ，) ：j i 讨2 南，( f ) 妒( 半弘( z z a ) 胄 v lor o 利用p 1 a n c h e r e l 公式，小波变换也可以在频率域内写为 c 嗽垆粤p 丽“如 c z z s ， 1 4 中山大学硕士论文 多分辨率分析胍a ( m u l t i r e s o l u t i o na n a l y s i s ) 是m a l l a t 和m e y e r 于1 9 8 6 年共同引入的。这一过程是构造小波基的一种有效的方法。i d a u b e c h i e s 在1 9 8 8 年成功的构造了具有紧支集的光滑小波基。 设 k ) 是工2 ( r ) 的闭子空间族，满足： ( 1 ) ce l 亡c c ( 2 ) u = 工2 ( r ) n = ii ( 3 ) ，( f ) ，( 2 f ) + 。 ( 4 ) ，( f ) ，( f 一七) ，v 七z ( 5 ) 存在伊，使得勋( f 一七) k 构成k 的一个标准正交基。 贝0 称( k 是2 的m r a 。 设尺度函数妒r 俾) ，称 妒( f ) = 以妒( 2 卜后) ( 2 2 6 ) 为双尺度方程，它在小波基的构造中起重要作用。称( 厅 ) 为尺度函数妒的面具。 我们定义 则由双尺度方程有 m 。( 国) = 去以e m 二t 庐( 卯) = 州。( ，2 ) ( 2 ) 删】记g t - ( - 1 ) k 。1 概( 咖圭e m 并令 ( 2 2 7 ) ( 2 2 8 ) 中山大学硕士论文 矿( 国) = m l ( 2 ) 庐( 国2 ) ( 2 2 9 ) 通过反傅立叶变换，我们可以得小波函数v 。 下面我们给出m a l l a t 快速算法用以作小波分解和重构。 定理2 2 ( m a l l a t 快速算法) 对任意 j z ，有 ( 1 ) 分解算法 气t = 击军一扎，屯= 击军 c z 珈， ( 2 ) 重构算法 2 4 字符细化 击莩( 忆一t f + 跏啪 ( 2 _ 3 1 ) 本节是第5 章基于h a u s d o r f f 距离的细化字符识别的基础，故简单叙述如下： 2 4 1 细化概念 所谓细化，通俗地说就是把一个具有一定面积的区域用一条( 或一组) 曲 线( 或细线) 来代表它。从广义角度来说，细化操作属于连接成分的变形操作。 如果将研究的连接成分( 集合) 用符号“l ”来表示，背景用符号“o ”来表示， 则细化操作就是用改变连接成分的形状使符号“l ”中某些象素由“l ”变成“o ”， 迭代这一过程，直到最后由一组单个象素组成的一组曲线( 或细线) 来代表这个 区。这组曲线( 或细线) 应保留连接成分的连通性和轮廓的几何特征。这一过程 就是细化操作的过程。 一个好的细化结果应该在不改变图像原有拓扑结构的前提下，即保持骨架的 1 6 中i n 大学硕士论文 连通性又不过腐蚀，同时还应具有一定的抗噪性能。近年来人们提出了许多细化 算法 5 l 5 5 】，根据他们的迭代方式不同通常有串行和并行之分。在串行算法中 细化结果不仅仅取决于前一次迭代图像，而且与当前处理有关；而并行方式下当 前迭代仅仅由前一次迭代决定。串行算法的结果依赖于对象素处理的先后顺序， 因而象素点的腐蚀或保留不可预测；而并行算法对象素进行腐蚀时利用相同的条 件同时检测所有象素点，其结果具有各向同性，并行算法另一长处时利于硬件实 现。 先给出细化中常用到的概念和定义，如下： 设待删除象素点p 是黑点，且基于如图所示的领域位置： 地 柏勋 x 5 p x l z 6 z 7 x 8 图2 1 定义如下： ( p ) ：象素p 的8 - 领域的象素点x l 、耽、物、驰、z 5 、x 6 、勋、 瓿； 4 一领域：即是x l 、勋、x s 、z 7 ( 或称是8 邻接于p ) ； 西( p ) ：在 b ) 中黑点象素的个数。这里我们也用蕾( i = l ，2 8 ) 表示该点的值l ( 黑 点) 或0 ( 白点) ； 象素的连接：在二值图像中，具有两个相同数值的象素z i 和尚，若所有与它们具 有相同值的象素，能够在4 - 8 - 领域内构成一个从五到而的邻接的象素序列，则 我们把象素孔和期叫做4 8 连接； 连接成分：在二值图像中，如果把相互连接的象素汇集为一组的话，就产生了 若干各“o ”值象素组和“l ”值的象素组，把这些组称为连接成分； 孔：在“o ”连接成分中，如果参在与外围的一行、一列的象素不相连的成分， 则把它叫做孔( h o l e ) ； 中山大学硕士论文 单连接成分：不包含孔的“l ”连接成分； 孤立点：仅含有一个象素的单连接成分； 多连接成分：含有孔的连接成分； 边缘点：其4 领域至少有一个白点； 端点： 其8 一领域最多有一个黑点( 6 ( p ) = 1 ) ； 断点：它的删除将会导致不连通； o 0 o o o 0 0 0 0 o o o o o10 01 oo o o o 0 o 01l11o o 0 o o o o 0001l ooo0 0 0 0 o 0 ol10 0 0 0 o 0 o o o 1 l oo o oo0o o 0 o o o o o o o 0 0 0 o0 o o 0o0 ol0 00 0 0 0 o 0 0 01 l o o o 图2 2 ：象素的连接，0 代表白点，l 代表黑点 图2 3 ：连接成分图列( 多连接成分和单连接成分及孤立点) 4 一8 一可删除：如果点p 的删除不改变图的4 一8 一连接性，则点p 是4 一8 可删除。 象素点的删除不能改变图像的连通性和它的几何特征。被考虑删除的象素点 都是轮廓点。所谓象素的可删除性是说，当改变一个象素值由“1 ”变成“0 ”的 时候，整个图像连接成分的连接性不改变，则这个象素被称为是可删除的。所谓 连接性不变是指，各连接成分不分离，不结合，孔不消除也不生成。 1 8 o 0 0 o o o o o o o 1 l 0 o o o 0 o o 1 l o 0 o 1 o o 0 1 1 1 0 0 o o o o o o o 0 o o o o o 0 o 0 0 0 o o o o o o o 0 o o o o o l 1 1 l 1 l l o o l o 1 l l l l o 0 l l 1 l l l l o o l l l l o o l o o l 1 l l l l 1 o o o 0 0 o o o o o 中山大学硕士沧文 一些算法的不同点出现在保证连接性的应用上。连接性主要由下面三个来定 义，如：交叉数目、连接数目、象素点的简单性。 常用关于交叉数目的定义如下： 定义2 4 ( r u t o v i t z 定义) 【5 1 ： 8 ( p ) = i 葺+ 一i ( 2 3 2 ) i = l 其中：物鼍 f 1 ；j 靠( p ) 表示点p 的交叉数目。 如果q ) = 2 ，p 点的删除将不会影响4 连接，因为在这种情况下，在 ) 中的 黑象素是4 一连接，则p 点可删除，否则反之。 oo o oo 压( p ) = 2 联p 产2 图2 4 定义2 5 ( h i l d i t c h 定义) 5 1 ： ( p ) = 6 ( 2 3 3 ) 黼蠡= e 苎1 1 j 竺! i i 暨端：表示点p 的奴飙l o 其他一 如果( p ) ；1 ，点p 的删除将不会改变图的8 一连接，可删除；否则反之。岛0 ) 取各种情况时象素点的分布如图2 5 所示： o o ooo o o o o o o oo ooo o o o ooo o o 蜘= o 而( p ) = 0知( p ) 。o妇o 闩 而( p ) 2 1粕( p ) = 3砀0 ) - 2 图2 5 1 9 中山人学硕士论文 当点的( p ) 的8 一领域全为黑点时，两种定义交叉数目都是o ，且此时该点是孤 立点。瓢p ) = 1 表明点p 是个轮廓点。而当砾0 ) = 2 时并不能确定这样的p 点是轮 廓点，为避免在这种情况下删除p 点( 它的删除会产生各h 0 1 e ) ，另外的一个条件 ( 6 ( p ) 1 ，在跟踪处理过程中不止一次被扫过的点得保留下来。同时 可删除的点被称为是简单的，而且在一个简单的8 一连接模式中，一个非孤立的轮 廓( 点是简单的当且仅当( p ) 仅有一个黑成分。这相当于妊( p ) = 1 ，即这个模式没 有洞。 2 4 2 细化算法分类 根据操作类型和使用的象素测试的标准，细化算法可分为两大类( 基于象 素) ：串行算法和并行算法。 2 4 2 1 串行细化算法 串行细化即是一边检测满足细化条件的点一边删除细化点。轮廓点以预先给 定的顺序，通过轮廓跟踪来检查。当一个轮廓点被检查时，它的删除和保留由p 中山大学硕士论文 的领域的结构特征决定。串行细化的缺点是细化后会产生很多毛刺；而且发现， 经过该算法细化的在字符的分叉点处并不是单像素宽的。 串行算法中最基本的算法是h i d t c h 算法 4 4 。它利用了取p ) 交叉数目。图像 是从左到右，从上到下被扫描，满足以下四个条件的点被标记删除； ：点p 的领域至少有一个黑点未被标记； ：在迭代开始时，取p ) = 1 ； ：勋被标记，则令耽= o 不改变磁p ) ( 均被标记也即是可变为白点) ； ：弘被标记，则令x 5 = o 不改变蹦p ) ； 说明：条件、是防止小集合类过腐蚀，如：为了保留两个象素宽的线： 条件维持连接性。 2 4 2 2 并行细化算法 在并行细化中，检测细化点的时候不进行点的删除只进行标记，而在检测完 整幅图像后一次性去除要细化的点。检查待删除的点仅仅基于前一次迭代的结 果。由于这个原因，这些算法适合于在并行处理机上应用，满足一系列条件的点 同时被删除，然而很不幸的是，如果仅仅考虑3 3 w i n 的应用，很难保留连接性。 例如：两个象素宽的笔画将会在处理后消失，解决这个问题有三个方法： 添加条件检查那些待定点的领域； 使用不同大小的“窗”来检查两个象素宽的笔画； 把每次迭代分成多个子迭代或子循环，在每次子迭代中，进入轮廓点的子 集考虑被删除。在每次迭代末，保留下来的图行被更新，为下一次子迭代做 准备； ：4 一子迭代是在每次子循环中将删除仅一个方向( 东南西北) 的轮廓点； ( 罾：2 一子迭代是在每次子循环中将删除两个方向( 北、东和南、西) 的轮廓点； ：l 一子迭代将使用大量的上下左右信息来保留连接性。 下面介绍这些并行算法： 并行细化算法最基本的是r u t o v i t z 算法( 1 一循环) 5 l ，5 2 ： 2 l 中山大学硕士论文 当点p 满足以下所有条件时，p 可删除： ：6 ( p ) 2 ( 且b ( p ) 6 ，后加的修正) ； ：( p ) = 2 ；且拍乜8 o 上魄乜5 乜6 乜7 = 0 ：z 1 + 勋+ j f 5 = o 或砀 3 ) 2 ( d ：x f j + x 7 = o 或烁0 1 ) 2 。 说明： 可产生对轮廓不敏感的连接骨架：但会导致过腐蚀。 由于4 部件可能是8 连接的，所有满足r u t o v i t z 算法的四个条件的待删除的 点不会引起对角的线成为一个单位象素宽。一个附加的条件砾0 ) = 4 ，使得位于 两个象素宽的对角的线的点p 的删除依然保留连通性，这个已经有论文证明了 4 5 。 由于条件和的不对称性，使得骨架不位于中心。这两个条件的1 8 0 度旋转( 在 3 3 w i n 内左、上下右对应位置互换) ，就有了d e u t s c h 算法( 2 一循环) 5 l 】， 满足以下迭代条件，p 点删除， ( 1 ) 奇数次迭代满足： ：婚0 ) = o ，2 或4 ；：6 0 ) l ( 类同6 0 ) 2 ) ；：x 1 + 耽+ 扔= o ；：x l t b 7 = o ； ：若妇) = 4 ，且( i ) x lt 聊= l 且轮啊6 o 且b 乜4 峨5 + 溉= 0 ； ( i i ) 石lt 功= l 且拍乜8 o 且规饥5 撬乜7 = o 。 ( 2 ) 偶数次迭代满足：，固( 其中是的1 8 0 度旋转) 。 z h a n g s u e n 算法【5 1 ，5 2 ，5 3 ，1 6 ，当点p 满足以下所有条件时，p 可删除： ：2 = 6 ( p ) = 6 ；：届( p ) = 2 ；：x 1 水x 3 屯7 = 0 ；：工木聊牛x 5 = 0 ；：x 1 幸x 3 木x 5 = o ； ：z 3 + 如+ 勋= 0 其中：是奇数次迭代；、是偶数次迭代。 说明：在该方法中，端点由b ( p ) = l 决定，但对于两个象素宽的对角线的笔画 时，会造成过腐蚀，由于端点( 对角) 满足上述条件时，将被删除，这样两象素 宽对角笔画将变成一个或两个点；甚至导致2 2 w i n 消失。 修改z s 方法一： 中山大学硕士论文 ：在奇数次迭代中，满足品q ) = 2 且x l 7 _ 1 且柏= o 的点p 不删除 ：在偶数次迭代中，满足砾) = 2 且勋5 = l 且粕= 0 的点p 不删除。 修改z s 方法二： 3 = 6 q ) = 6 ，其他条件不变。 对比各种细化算法，z h 锄g s u e n 细化算法速度快，试验效果好等特点，对字符进 行细化，本文中试验用到的就是此方法。 基- 5 可5 几种细化算法的试验结果图如图2 6 ，图2 7 ，图2 - 8 ： 图2 6 ( 从左到右是，原图，z h a n g s u e n 细化算法、d “s c h 算法、r u t o v i t z 算法) 鬈：8 图2 7 ( 从左到右是，原图，z h a i l g s u e n 细化算法、d e l i s c h 算法、r u t o v 沱算法) h t m y q p h t m y q p 振兴中华 统一祖国 图2 培 从左到右是，原图，z h 锄g s u e n 细化算法、d e u s c h 算法、r u t o v i t z 算法 一华国一一华国一一华国一 一中祖一 一中祖一 一中祖一兴二一兴二一兴二 振统一一振统一振统一 中山大学硕士论文 第三章可变形模板 本章内容安排如下：第1 节介绍早期使用的刚性模板，分析了它的缺点； 第2 节介绍了可变形模板的分类，以及常用的可变形模板。 模板匹配这是一个非常经典的图像处理技术 3 ，是最原始最基本的特征提 取方法。它把字符图像本身就作为特征向量而不做任何的加工，与各类别标准图 像( 图像轮廓、特征图像) 进行匹配识别。在分类识别的阶段，主要通过样本与 模板之间的相似度( 或不相似度) 来判断样本是否属于匹配的模