（计算机软件与理论专业论文）基于主曲线的低质汉字骨架提取研究.pdf

四川师范大学硕上学位论文 基于主曲线的低质汉字骨架提取研究 计算机软件与理论专业 研究生：杨勉指导教师：廖志武 摘要：骨架是穿过数据分布中心的像素点集合，是一种重要的形状特征。 该特征在保持形状的拓扑和几何性质的同时还能有效的降低计算复杂度。虽 然，骨架提取领域已经取得了诸多的研究成果，但是，现有的骨架提取算法仍 然存在一些挑战。例如大部分算法所提取的骨架与人类视觉差距较大；特别是 当形状存在模糊、扭曲以及稀疏、间断等复杂情况时骨架提取效果较差；现有 的骨架提取算法难以向高维扩展。 主曲线( p r i n c i p a lc u r v e s ) 是满足“自相合 并且穿过数据分布“中间 的光滑曲线，即该曲线可以理解为能够反映数据集合拓扑结构的“骨架 。基 于此，本论文提出了一种基于主曲线的骨架提取算法，用于提取低质手写体汉 字骨架。该算法采用类似于自动聚类算法的思路，增量的寻找每个v o r o n o i 区域中的第一主成份线段，通过代价函数连接所得的k 段主成分线段从而构造 初始哈密尔顿路径。当然这里所得的是局部意义上的一条次优哈密尔顿路径， 因此，我们提出了一种简单方法用于优化初始哈密尔顿路径，得到更具有全局 最优性的汉字骨架。另外，由于这里是用一条哈密尔顿路径去逼近汉字骨架， 因此我们还提出了一种基于全局的平均稀疏度来设定阈值的简单后处理策略， 从而删除冗余边集，得到符合人类视觉的汉字骨架。 经过了大量m a t l a b 实验证明，该方法对带模糊、扭曲、断裂、稀疏的低 质手写体汉字均取得了很好效果。另外通过对图像背景中添加噪音，也能够得 四川师范大学硕士学位论文 到连续的、完整的汉字骨架。我们还尝试进行了将2 3 个自由手写体汉字作为 一个整体进行骨架提取，也取得了较为理想的效果。无疑，本文提出的方法不 仅对于低质汉字骨架提取是可行的，而且是鲁棒性非常好的一种新方法，也为 汉字骨架提取研究提供了一条新思路。 关键词：汉字骨架，主曲线，低质，哈密尔顿路径，平均稀疏度，鲁棒性 i i 四川师范大学硕士学位论文 t h es k e l e t o n i z a t i o nr e s e a r c ho fl o w - q u a l i t yc h i n e s e c h a r a c t e r sb a s e do np r i n c i p a lc u r v e s g r a d u a t es t u d e n t ：y a n gm i a n s u p e r v i s o r ：l i a oz h i w u a b s t r a c t ：s k e l e t o n ，嬲a l li m p o r t a n ts h a p ef e a t u r e ，i st h ec o l l e c t i o no ft h ep i x e l s p a s tt h r o u g ht h e c e n t r eo fd a t ac l o u d t h i sf e a t u r er e d u c e st h ec o m p u t a t i o n a l c o m p l e x i t ye f f i c i e n t l ya sw e l l 弱k e e p st h et o p o l o g ya n dt h eg e o m e t r i cp r o p e r t i e so f t h es h a p e a l t h o u g ht h e r ea r es o m e e x i s t i n gs k e l e t o n i z a t i o na l g o r i t h m sa l r e a d y ，s t i l l w eh a v es e v e r a lb i gc h a l l e n g e s f o ri n s t a n c e ，t h er e s u l t so fm o s ts k e l e t o n i z a t i o n a l g o r i t h m sh a r d l yr e s e m b l eh u m a np e r c e p t i o n so ft h eu n d e r l y i n gs h a p e s t h e e x i s t i n ga l g o r i t h m sw i l lo b t a i nt h ed i s a p p o i n t i n gr e s u l t su n d e rt h ef u z z i n e s $ ， d e f o r m a t i o n , s p a r s e n e s s ，d i s c o n t i n u i t y i na d d i t i o n , t h e s ea l g o r i t h m s a r ea l s o d i f f i c u l tt oa c h i e v et h em u l t i d i m e n s i o n a lg e n e r a l i z a t i o n t h ep r i n c i p a lc u r v e sh a v eb e e nd e f m e d 嬲s m o o t hc u r v e ss a t i s f y i n gt h e s e l f - c o n s i s t e n c y p r o p e r t ya n dp a s s i n gt h r o u g ht h e m i d d l e o fa m u l t i d i m e n s i o n a l d a t as e t t h i sp r i n c i p a lc u r v e sc a nb eu n d e r s t o o d 硒t h es k e l e t o nr e f l e c t i n gt h e t o p o l o g yo fa d a t as e t s oi nt h i sp a p e r , w ep r o p o s e da ni m p r o v e ds k e l e t o n i z a t i o n a l g o r i t h mb a s e do np r i n c i p a lc u r v e su s e dt oe x t r a c tt h es k e l e t o no ft h el o w - q u a l i t y f r e eh a n d - w r i t i n gc h i n e s ec h a r a c t e r s t h i sa l g o r i t h mf i n d st h ef i r s tp r i n c i p a ll i n e s e g m e n ti ne v e r yv o r o n o ir e g i o ni n c r e m e n t a l l y , a n dc o n s t r u c t st h ei n i t i a lh a m i l t o n p a t hw h i c hi so b v i o u s l yas u b o p t i m a lo n eb yu s i n gt h ec o s tf u n c t i o n s ow e p r o p o s e das i m p l em e t h o dt oo p t i m i z et h i si n i t i a lh a m i l t o np a t h b e c a u s eo fu s i n g o n eh a m i l t o np a t ht oa p p r o x i m a t et h ec h a r a c t e rs k e l e t o n , w et h e np r o p o s e da i i i 四川师范大学硕上学位论文 s c h e m eb a s e d0 nt h eo v e r a l la v e r a g es p a r s e n e s st os e tt h et h r e s h o l d ，t h u st od e l e t e t h er e d u n d a n te d g e sa n do b t a i nt h es k e l e t o nc l o s e l yc o n f o r mh u m a np e r c e p t i o n t h ee n o r m o u sm a t l a bl a b o r a t o r i e sr e s u l t sd e m o n s t r a t et h a tt h i sp r o p o s e da l g o r i t h m h a v eg o o dp e r f o r m a n c e st ot h ef r e eh a n d w r i t i n gc h i n e s ec h a r a c t e r s 诵t l lf l 亿z i l l e s s ， d e f o r m a t i o n , d i s c o n t i n u i t ya n ds p a r s e n e s s t h e n , b a s e do nt h i sa l g o r i t h mw e a t t e m p tt oe x t r a c tt h es k e l e t o no fa no b j e c t 、析t l lt w oo rt h r e ec h a r a c t e r sa n da l s og e t s a t i s f i e dr e s u l t s w i t h o u ta n yd o u b lo u rs c h e m ei sa c o m p l e t e l yn e wr o b u s tm e t h o d 。a sw e l la san e wr e s e a r c hd i r e c t i o nt oe x t r a c tt h el o w - q u a l i t yc h i n e s ec h a r a c t e r s k e yw o r d s ：c h i n e s ec h a r a c t e rs k e l e t o n , p r i n c i p a lc u r v e s ，l o w - q u a l i t y , h a m i l t o n p a t h , a v e r a g es p a r s e n e s s ，r o b u s t n e s s i v 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导 行研究工作所取得的成果。除文中已经注明引 导下，独立进 文不含任何其 他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的 个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而 引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印 刷版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库供 检索；2 ) 为教学、科研和学术交流目的，学校可以将公开的学位论文或解密 后的学位论文作为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录到中国学位论文 全文数据库，并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：钐匆 签字醐：叩盼鼢日 导师签名李毒萄 签字日期：沙斧箩月z 口日 四j i i 师范大学硕士学位论文 第一章绪论 对于图像识别和分类来说，穿过数据分布中心的单像素骨架是一种重要的 结构特征。该特征比形状或形状的轮廓在噪声和扭曲中具有更强的鲁棒性，另 外骨架在保持形状的拓扑和几何性质的同时还能有效的降低计算复杂度。虽 然，骨架提取领域已经取得了诸多的研究成果，但是，现有的骨架提取算法仍 然存在一些尚未解决的难题。例如大部分算法所提取的骨架与人类视觉差距较 大；当形状存在模糊、扭曲以及稀疏、间断等复杂情况时骨架提取效果较差； 现有的骨架提取算法难以向高维扩展。 主曲线( p r i n c i p a lc u r v e s ) 是满足“自相合”并且穿过数据分布“中间 的能够真实地反映数据形态的光滑一维曲线n 引，这一特性与骨架构造思路是相 符的。 本论文着重研究低质手写体汉字骨架提取算法，特别是对带扭曲、断裂、 稀疏的低质手写体汉字进行了大量实验，并取得了较为理想的效果。无疑，该 方法是一种对于低质汉字骨架提取鲁棒性非常好的一种新方法，也为汉字骨架 提取研究提供了一条新思路。 1 1 主曲线国内外研究现状 t h a s t i e 和w s t u e t z l e l 于1 9 8 4 年提出了主曲线的概念，并于1 9 8 9 年 公开发表了“p r i n c i p a lc u r v e sa n ds u r f a c e s 一文，给出了h s 主曲线的 定义，为日后主曲线的研究应用奠定了理论基础，这篇文章也成为了主曲线 理论研究的开山之作，但当时还有一些理论有待完善。 1 9 9 2 年，b a n f i e l d 和r a f t e r y 主曲线( 简写为b r 主曲线) 在算法上改进 了h s 主曲线，解决了在闭主曲线下由于曲率过大，估计偏差对实际主曲线产 生明显影响的问题。然而，b r 主曲线方法也引入了数值不稳定性，在实际中 可能产生光滑但不正确的主曲线。 1 9 9 7 年，b 肫9 1 引入了有长度约束的主曲线概念( 即k 主曲线) n 引，证明了 在理论分布下定义的k 主曲线的存在性和唯一性，认为只要数据分布存在有限 二阶矩，则k 主曲线一定存在，同时研究了k 主曲线对数据分布的学习性质， 给出了新定义的k 主曲线收敛性。 四川师范大学硕上学位论文 1 9 9 9 年d e l i c a d o 给出了d 主曲线算法，他在考察了线性主成分的其他特性 之后，给出主定向点概念及基于定向点的主曲线定义。 2 0 0 0 年j j v e r b e e k 给出了软k 段主曲线算法m 1 ，采用局部主成分方法 来形成k 条线段，并依据光滑性来连接形成主曲线，这一方法缺陷是不能向 高维推广。在其目标函数中没有考虑曲率惩罚。 尽管在主曲线的研究中还存在着一些尚未解决的数学问题，但是，其广泛 的应用前景早己引起计算机科学家的关注，并已将主曲线成功应用到诸多领 域，如线性对撞机中对电子束运行轨迹的控制、图像处理中辨识冰原轮廓、手 写体的主曲线模板化、语音识别中对声音数据的约简建模和数据可听化、生态 学中寻找种群的有序分布及过程监控。目前，作为一个全新的研究方向，主曲 线也引起了国内计算机界研究人员的关注。主曲线的“自相合”特性，“描述 数据中间性”特性在可视化图像研究、语音识别、实时数据异常值检测、交通 路径优化选择、动态聚类等方面也发挥了重大作用n8 | 。 1 2 汉字骨架提取国内外研究现状 由于骨架的一些显而易见的优点，比如，骨架比形状或形状的轮廓在噪声 和扭曲中更稳定；骨架在保持形状的拓扑和几何性质的同时还能有效降低计算 复杂度等，骨架提取算法成为模式识别，基于内容的图像检索、医学图像处理、 遥感图像处理、可视化和虚拟现实等领域的研究热点。 提取骨架又被称作细化。传统的图像细化有两种基本方法：即边缘点删除 和内点保留。基于边缘点删除的细化算法在细化过程中只对边缘点的可删除性 进行判断并作相应处理。由于受跟踪顺序及所考察邻域的影响容易产生骨架的 非对称性。而基于内点保留的细化算法又容易使所获得的骨架大于一个像素。 细化算法还可以依据是否使用迭代运算将其分成两类。非迭代算法即一次产生 骨架。如基于距离变换的方法、游程长度编码细化等。迭代算法，即重复删除 图像边缘满足一定条件的像素，最终得到单像素宽骨架。这类方法依据其检查 像素的方法又可再分成串行算法和并行算法。 在骨架提取方法的最近一篇综述中n ，将骨架提取算法分为：距离骨架 ( d i s t a n c es k e l e t o n ) ，非迭代方法( n o n i t e r a t i v ew a y ) 和迭代法( i t e r a t i v e 2 四j l l 师范大学硕= ：学位论文 w a y ) 三类。 其中距离骨架是由b l u m 首先提出的。b l u m 认为骨架可以看成对称点所构 成的集合，并且提出这些对称点可以通过求边缘点的内接圆的圆心的集合获 得。在b l u m 的方法上发展了很多新的骨架提取算法，比如先利用三角剖分将 形状分成一些由三角形所构成的简单区域，再对这些简单区域进行进一步分 析，以获得好的骨架特征。这些算法采用的三角剖分比内接圆更适用于进行形 状描述，所以能够获得较好的骨架特征，但是计算复杂度高。在此基础上发展 的通过边缘点的对称性求形状骨架的方法，运算复杂度低，但是只是用于类排 骨状( r i b b o n - l i k e ) 形状( 例如，文字，指纹，血管等) 骨架提取。 非迭代法中的对称中心或对称线是用非迭代方法获得的。一般说来，这些 方法先确定一些关键点，然后计算链接这些关键点的一条特殊路径。此类也只 适用于比较简单的形状的骨架提取。 迭代方法是通过迭代的方法来获取形状骨架的。其中形态学方法是迭代法 中最著名的方法，通过形态学算子的迭代运算获得形状骨架。在此基础上发展 起来的迭代算法，由于可以采用并行计算等技术，可以在较短的时间内获得形 状的骨架，但是由于迭代法主要依赖曲率( c u r v a t u r e ) 驱动曲线的演化 ( e v o l u t i o n ) ，这样获得的骨架与人的视觉吻合度差。另外也可以通过引入优 化技术控制迭代的目标，能够获得较好的骨架特征。 本论文给出的汉字骨架提取策略即是一种非迭代的方法，即通过主曲线算 法对整个像素点阵图像进行遍历从而确定一系列关键点，进而求出每个 v o r o n o i 区域中受长度约束的第一主成分线段，最终计算出连接第一主成分线 段的一条哈密尔顿路径。该路径即为穿过数据点阵“中心 的单像素点中轴骨 架线。通过一系列的m a t l a b 实验可以发现主曲线算法对于低质自由手写体汉 字骨架提取能够获得较为理想的效果。 1 3 本文的研究动机和目的 汉字骨架即为能够表示汉字图像区域结构且穿过图像数据集合中心的单 像素中轴轮廓线，也可以把该中轴轮廓线理解为距离目标边界上两个点等距的 那些像素的集合。 四川师范大学硕士学位论文 研究人员发现，根据汉字构造的最初思路，从汉字的笔画结构出发进行汉 字骨架特征提取，进而进行基于汉字笔画结构的分类和识别是合情合理的，也 非常符合汉字构造的初衷。但是，该类方法首先遇到的难题是汉字笔画结构及 其相互关系难以稳定提取。在实际应用中，面对可能出现的大量的无规律可循 的汉字结构，无法预先估计的噪声和干扰，效果都不太尽如人意。近年来研究 者也提出了许多骨架提取算法 1 ，2 如中轴变换方法、数学形态学方法、小 波模极大值的方法、基于主动轮廓的方法。但是这些方法不能从带有噪声背景 的图像中直接提取出骨架，必须先进行去噪等预处理步骤。另外特别是对于稀 疏汉字，带扭曲、断裂的汉字进行骨架提取，上述方法均会出现不同程度骨架 的间断，变形，另外所提取的骨架也具有较差的视觉吻合度。 本论文试图尝试一种有别于当前主流汉字骨架提取思路的新方法，即用某 种主曲线改进算法针对复杂汉字进行整体骨架提取。汉字图像具有弯曲度较大 和相交点众多等特点，而h s 主曲线算法、b r 主曲线算法、d 主曲线算法和t 主曲 线算法共同存在的问题是当数据分布在曲率很大或相交点多时，这些算法的 性能就很差，所得结果也不能准确反映数据的拓扑结构。 由于软k 段主曲线算法采用局部最优的方法来获得全局最优，对分布在弯 曲度很大或相交曲线周围的数据的中轴轮廓线的提取有较好效果，且具有较强 的鲁棒性，因此本文将带长度约束的软k 段主曲线算法用于提取汉字骨架，特 别是对于稀疏汉字，带扭曲、断裂的汉字进行骨架提取，并针对汉字骨架的特 点，提出了相应的改进策略。 1 4 本文的主要贡献 本论文采用改进的软k 段主曲线算法对低质汉字进行骨架提取。该算法采 用增量的方法找寻每个v o r o n o i 区域中的第一主成分线段，然后通过设立带锐 角惩罚的代价函数构造初始的哈密尔顿路径，并提出了一种全新的简单方法对 该初始哈密尔顿路径进行了一定程度的优化，最后提出了根据笔画的平均稀疏 度对优化后的哈密尔顿路径中冗余的边集进行去除从而进一步优化骨架结果， 得到符合人类视觉的汉字骨架。 大量的m a t l a b 实验结果表明，利用该策略来提取脱机自由手写汉字的骨 4 四川师范大学硕上学位论文 架特征，特别是一些低质汉字的骨架特征不但是可行的，而且取得了较好的实 验效果。我们尝试了扭曲汉字的骨架提取、笔画带断裂的汉字骨架提取、背景 加噪的汉字骨架提取，另外还尝试了对多次稀疏化以后的汉字图像进行骨架提 取，均取得了较好的实验效果。最后我们还尝试进行了将2 - 3 个汉字作为一个 整体进行骨架的提取，也取得了较好的效果。无疑，该方法以在提取骨架的同 时，很好的抑制背景噪声，并且所得骨架具有很好的连续性和单像素性，另外也 具有较好的视觉吻合度，是一种对于低质汉字骨架提取鲁棒性非常好的新方 法，也为汉字骨架提取研究提供了一种新思路。 1 5 论文的总体框架 本论文一共分为五章，总体框架见表1 - 1 。 表i - i ：论文总体框架 章节主要内容 第一章主曲线、汉字骨架提取国内外研究现状，论文研究动机、目的、主要贡献及 框架 第二章 常规的汉字骨架提取方法和本文所提出方法的实验结果比对 第三章主曲线的产生、发展和经典主曲线算法比较 第四章基于软k 段主曲线的汉字骨架提取研究的主要算法思想及优化策略 第五章算法的总体程序结构及m a t l a b 实验结果 第六章结语和展望 第一章简要阐述了主曲线及汉字骨架提取的国内外研究现状，常规研究方 法，本论文的研究动机、研究目的以及主要贡献。 第二章主要介绍和汉字骨架提取相关的基本知识，包括目前主流的骨架提 取方法，例如基于中轴变换的方法( 草火法、v o r o n o i 法) ，基于数学形态学 的方法，基于小波模极大值的方法。并给出了用本文提出的方法和上述常规方 法对汉字骨架提取的实验效果对比。 第三章主要介绍了主成分分析的原理，主曲线的产生，发展、研究意义和 四川师范人学硕士学位论文 几种经典的主曲线算法对比。 第四章详细介绍了优化后的受长度约束的软k 段主曲线的主要数学概念 及每个子程序的算法思想、实现步骤。该章节工作也算是本论文的主要工作之 一。在第四章里面我们还详细介绍了一种简单的优化初始哈密尔顿路径的方 法，能够得到满足需求的汉字骨架。另外我们还提出了一种利用平均稀疏度来 设定阈值的方法从而成功去掉优化后的哈密尔顿路径的冗余边集，得到符合人 类视觉的汉字骨架。 第五章着重介绍将此算法用于脱机自由手写体汉字骨架提取的程序结构。 并完成了大量m a t l a b 实验，包括不规则图形的骨架提取，自由手写体汉字的 骨架提取，带背景噪音、比划中带间断点、带扭曲汉字骨架提取。也尝试了多 次稀疏后的汉字骨架提取( 即模拟实际图像扫描时可能出现的间断点) ，最后 还尝试进行了将2 3 个汉字作为一个整体进行骨架提取。 第六章算是本文的一个总结，也对后续的进一步工作提出了要求和展望。 6 四川师范大学硕士学位论文 第二章汉字骨架提取常规方法与本文方法比对 虽然骨架提取算法在不同的应用领域，已经取得了很多的研究成果，但是， 随着计算机应用和图像获取技术的日益发展，现有的骨架提取算法面临很多挑 战。 2 1 汉字骨架提取难点 汉字属于非字母类的文字，结构复杂，笔画繁多。汉字集中相似字又较多， 有些汉字的差别仅为一点或一个笔画，由于手写汉字特别是自由手写体汉字存 在书写变形、连笔等等情况，使得手写体中相似字的骨架提取非常困难。 汉字的主要笔画为横、竖、撇、那、点等。汉字主要的结构有上下结构、 左右结构、半包围结构、全包围结构、独体字等。另外在自由手写体汉字中基 本的书写变形表现在以下几个方面： 1 ) 基本笔画的变化。横不平，竖不直，直笔变弯，“横折 的拐角变成 圆弧等。 2 ) 笔画模糊，不规范，该连的不连，不该连的却相连。 3 ) 笔画与笔画之间、部件与部件之间的位置发生位移变化。 4 ) 笔画的倾斜角、笔画的长短、部件的大小发生变化。 5 ) 对于脱机手写汉字，不同人用不同的书写笔可能造成笔画的粗细化。 骨架( s k e l e t o n ) 是一种形状特征，是由形状中的所有边缘点的对称中心构 成的。由于骨架对称性的理解不同，同一个形状用不同的骨架提取方法求取的 骨架是不完全相同的，但是我们认为一个“好”骨架是原始( o r i g i n a l ) 形状的 近似物，它应该满足以下的几个条件： 1 ) 骨架应该是对称的( s y m m e t r i c ) 或称为居中( c e n t e r e d ) ，即对象的 骨架应该相对于对象的边界居中； 2 ) 骨架应该是连续的( c o n n e c t e d ) ，无间断点的； 3 ) 骨架应该是符合人类视觉的，即与其描述对象的拓扑结构一致，与原 始形状接近； 4 ) 骨架的粗细应该是单像素宽度，以便在检索及配准时速度也更快； 5 ) 在噪声和一定的扭曲下，骨架应该是稳定的； 7 四川师范大学硕上学位论文 6 )骨架应该是可重建的( r e c o n s t r u c t i b l e ) ，即可以根据其骨架重建原 型，这也就是要求一个骨架变换方法是可逆的。 以上这些特征也是评判骨架提取算法性能的重要依据。好的骨架的这些显 而易见的优点使得骨架提取算法成为模式识别，基于内容的图像检索、医学图 像处理、遥感图像处理、可视化和虚拟现实等领域的研究热点。 然而基于常规的骨架提取方法例如中轴变化法、数学形态学方法、小波模 极大值方法对低质图像进行骨架提取一直效果欠佳，难以避免的出现骨架的间 断，个别笔画的骨架缺失、不符合人类视觉等情况。这里的低质汉字即指带扭 曲、带断裂、带背景噪音的汉字及稀疏汉字。 2 2 基于中轴变换的汉字骨架提取 2 2 1 中轴变换概述 中轴变换( m e d i a la x i st r a n s f o r m ，m a t ) 是描述物体骨架最为常见的方 法。通常我们对目标图像的细化处理提取其骨架，就是将图像上的曲线、直线 等几何元素的线条沿着中心轴线将其细化成单象素宽的线条的处理过程。 b l u m 首先提出连续二值图的骨架概念，b l u m 对中轴的定义是利用“草火 来描述的。即设想在t = 0 时刻，将目标边界各处同时点燃，火的前沿以匀速 向目标蔓延，当前沿相交时火焰熄灭，火焰熄灭点的集合就构成了中轴线。当 时骨架被定义为中轴( m e d i a la x i s ) ，后来称为对称轴( s y m m e t r i ca x i s ) 。由 此可见中轴( m e d i a la x i s ) 可以认为是精确定义的骨架。骨架可以认为是中轴 的一种近似。 c a l a b i 在1 9 6 6 年基于最大球概念给中轴下了更为数学化的定义( 见图 2 - 1 ) 。他认为中轴变换也可理解为在欧氏二值图像的内部任意给定一点，以该 点为圆心存在一个最大的圆盘，其整个盘体都在图像的内部，且至少有两点与 目标边界相切，则该点便是骨架上的点，所有最大圆盘的圆心构成了图像的骨 架( 中轴) 。 8 四川师范大学硕士学位论文 。妒二 图2 1 ：c aja b i 中轴定义 1 9 6 8 年，m o n t a n a r i 给出实平面内中轴的四个等价定义( 见图2 2 ) ： 1 ) 地表火模型：中轴点实在轮廓e 开始传播的波阵自身相交的点集。边界 点以恒定的速率沿法向传播，其交汇点就是中轴点。 2 ) 距离曲线的脊线：以形状的边界点作为特征点，以内部点到这些特征点 形成一个距离场，将它看成是一个距离曲面，这张曲面的脊线就是中轴线。 3 ) 避大吲盘的几何中心：这就足c a l a b i 对中轴在二维下的定义。 4 ) 中轴也可以看着是不属于任何其它内点和其对应得的最近边界的线段 的点集。 画佥圜因 图2 - 2 ：中轴的四种等价定义 自b 1u m 提出中轴变换的概念以后，许多研究者在这方面做出了杰出的成 就。常用的中轴变换方法有基于拓扑逻辑的细化算法( t o p o l o g i c a l t h i n l l i n g ) 、基于距离变换算法( d i s t a n c et r a n s f o r m ，简称d t ) 、草火法 ( s i m u l a t i o n so fg r a s s f ir ep r o p a g a t i o n ) 、v o r o n o i 法等等。 四川师范大学硕上学位论文 2 2 2 基于草火法和v o r o n oi 法的骨架提取 草火法( s i m u l a t i o n so fg r a s s f i r ep r o p a g a t i o n ) 的思想最早由b l u m 用来 给中轴下定义时使用的。b l u m 指出提取图像骨架的过程可以理解为光秃的地面 上有一块长着干草的草场，在草场四周同时点火，令火焰以相同的速率从四周 向内部燃烧蔓延，当火线相遇时的位置称为灭点( q u e n c h i n gp o i n t s ) ，记录下 灭点，同时让火不断继续蔓延直到大火熄灭。 首先，为了用计算机模拟边界同时着火，而且大火蔓延速率不变，则技巧 性地处理为每一次循环遍历一次边界。 草火法提取骨架算法描述见表2 - 1 。 表2 - 1 ：草火法提取骨架算法步骤 步骤描述 s t e p l 为输入对象建立等高线，并标记边界点 s t e p 2 沿着等高线遍历边界点，并标记关联点为下一轮边界点。若某点被重复标记， 则它就是灭点，并记录由此生成的新的边界点 s t e p 3如果所有等高线均被遍历，转s t e p 4 ：否则，转s t e p 2 s t e p 4删除所有不是灭点的点 s t e p 5如果已经没有点被删除，完成；否则，转s t e p l 用草火法描述中轴的形成是一个非常形象的方法，但缺乏合适的数学模型 去描述和定义草火法。后来，人们发现计算几何中一个有名的工具v o r o n o i 图( v o r o n o id i a g r a m ) 与草火法的灭点有很强的关联性，由于v o r o n o i 法不是 此次论文的研究重点，复杂的数学原理就不做累赘。草火法中的灭点即是由图 形边界得到的v o r o n o i 图的一个顶点，v o r o n o i 图的研究对象是多边形图形( 见 图2 2 ) 。 1 0 四川师范大学硕士学位论文 图2 2 ：矩形的v o r o n o i 图 任何一个点阵图像可以通过在其边界上进行抽样，取出的抽样点即为 v o r o n o i 多边形顶点，进而对该多边形计算其v o r o n o i 图。b r a n d t 等人证明了当 抽样密度趋于正无穷大，则由抽样点形成的多边形( 多面体) 得到的v o r o n o i 图 骨架就趋于原对象的骨架。 基于草火法的汉字骨架提取见图2 - 3 。对于规则汉字而言，草火法也不可 避免的会出现许多笔画断裂和笔画末端的分叉。不满足骨架必须连续且满足人 类视觉这一特点。对于低质自由手写体汉字，特别是间断和稀疏化较严重的情 况下，草火法基本上不能提出完整的骨架。 。 f 户 原图草火法骨架 图2 3 ：基于草火法的骨架 2 3 基于数学形态学的汉字骨架提取 数学形态学( m a t h e m a t i c a lm o r p h o l o g y ) 在图像处理中经常作为提取图 像中描述区域形状分量的一种常用工具，这些分量包括图像边界、骨架和凸壳 等，它以图像形态分析为基础，用具有一定形态结构的“结构元素 去度量图 四川师范大学硕士学位论文 像的形态。基本的形态学运算包括膨胀、腐蚀。另外腐蚀、膨胀运算有四种常 见组合，即开运算、闭运算、击中或击不中变换。根据处理的对象可以分为二 值和灰度形态运算。在实际应用中，图像通常被预处理为二值图象。 形态学的基础是腐蚀和膨胀运算。膨胀在二值图像中有加长或变粗的作 用，能够将图像中的一些裂缝桥接起来。腐蚀在二值图像中有收缩或细化对象 的作用，常常能够将图像的一些细节去掉( 腐蚀掉) 。收缩的方式和程度由一个 结构元素控制。 膨胀和腐蚀运算汹1 ： 设二值图像为彳，结构元素为b 。 么被b 腐蚀记为a o b ，定义为： a o b = zl ( b ) na 1 9 其中么被b 腐蚀是所有结构元素的原点位 置的集合，其中平移的b 与彳背景并不叠加。由此可见结构元素的选取至关重 要的，在结构元素不同的情况下，计算的骨架是不同的，所选择的结构元素应 能保证目标图像在算法的每一次迭代过程中其结构的连通性，并且保证整个 图像的构造不改变。 同理，a 被b 膨胀定义为： aob = z i ( 召) na 1 9 。 开运算和闭运算： 使用结构元素b 对集合彳进行开运算，表示为彳ob ，定义为 彳。b = ( a o b ) o b 使用结构元素b 对集合a 进行闭运算，表示为a b ，定义为 彳b = ( 彳ob ) 0 8 通过腐蚀和膨胀运算可以得到通过图像骨架。集合a 的骨架用s ( 彳) 来表示， 则由细化得到骨架的定义为：s 0 ) = u & 0 ) 其中， & ( 彳) = ( a o k b ) 一( a o k b ) 。b 扣” 这里b 是一个结构元素，( a o k b ) 表示对彳的连续七次腐蚀：第七次是彳 被腐蚀为空集合前进行的最后一次迭代，也就是说：k = m a x 七ia o k b 1 9 通过腐蚀、膨胀运算得到图像骨架算法描述见表2 2 。 1 2 四川师范大学硕士学位论文 表2 - 2 ：基于数学形态学提取骨架算法步骤 步骤内容 s t e p l对图像进行二值化 s t e p 2为细化选取合适的结构元素 s t e p 3细化操作到前后得到的连续两个骨架图像相同时停止；如果骨架的线条宽度 大于了某阈值，转s t e p 2 ，否则转s t e p 4 s t e p 4迭代结束 基于数学形态学方法的汉字骨架提取见图2 - 4 。对于规则汉字而言，此方 法最大问题时会出现许多笔画末端的树枝状分叉。视觉吻合度较差。对于低质 自由手写体汉字，特别是间断和稀疏化较严重的情况下，数学形态学方法基本 上不能提出较为满意的骨架。 原图数学形态学骨架 图2 4 ：基于数学形态学的骨架 2 4 基于小波模极大值的汉字骨架提取 在本节中将讨论通过找小波模极大值的方式确定汉字边界轮廓哺1 ，再找到 骨架中轴线的方法。在轮廓提取时，已经有许多经典的边界提取算子，例如 r o b e r t 算子、s o b e l 算子和l a p l a c e 算子，不过这些方法对图像中的噪音显得 无能为力，因为一般信号的主要轮廓信息，由拐点( 二阶导数为零的点) 确定， 而由于噪音本身也具有突变特性，于是噪音的突变点和汉字的轮廓混杂在一 四川师范人学硕士学位论文 起，很难区分，因此直接求拐点显然行不通。于是，我们通过求一阶导数的模 的极大值来确定汉字的轮廓点。 所谓小波模极大值就是先将小波函数和原信号卷积，然后对结果取模，最 后找到极大值。上述步骤，也就等价于：先把某一光滑函数求导( 求导后满足 积分为零的条件成为小波函数) ，然后卷积源信号，接着取模，最后发现极大 值。 基于小波模极大值的汉字骨架提取算法步骤见表2 - 3 。 表2 - 3 ：小波模极大值的骨架提取算法步骤 步骤内容 s t e p l对于给定某小波( 本文对比实验中所用为h a a r 小波) ，求出小波滤波器高通 分解系数h i d ，其中分解滤波器长度为2 s t e p 2 用h i _ d 系数分别与图像点阵x 方向、y 方向分别做卷积得到小波系数g x 、 g 。其中g 。= 【厂g h x 厂g 川) 】幸h i d s t e p 3求出每一个像素点的小波模值，也即是该点的梯度大小 g ，g x + g y g y ，用反正切求梯度方向或者称幅角a t a n ( g y g ，) 。这 里，注意的是反正切只能求出一、四象限的角度，其它象限要分别处理 s t e p 4 把坐标系分成八个区间( 如图2 5 ) ，每个区间赋一个码字，即落入每个区 间的所有幅角都分别对应相应的码字( 见表2 4 ) 。需要单独讨论当幅角为 0 ，z 2 ，刀，3 n - 2 的特殊情况 s t e p 5依次遍历图像中每一个模极大值点，按照一定的步长，根据该点所对应的幅 角方向若存在模极大值点，则标记出其中点 趟幺， 。乃 心 0 图2 - 5 ：坐标分区 1 4 四川师范大学硕上学位论文 表2 - 4 ：幅角取值码表 i g ， 0 ，g y 0目= a r c t a n g y g x 8e 【一；, t 2 ，万2 】 a ) 当秒【一x 8 ，x 8 】 口码字为0 b ) 当目【z r 8 ，3 n 8 】 口码字为1 c ) 当9 【3 a 8 ，n 2 】 曰码字为2 d ) 当秒【一3 n 8 ，一n 2 】 秒码字为6 e ) 当汐【一3 n 8 ，一n - 8 】 秒码字为7 i i g ， 0 目码字为2 g ，= 0 ，g ， 0 ，g ，= 0 曰码字为0 q p ，构造样本阵，为了避免变量间量度单位的差异性，对样本阵元进行 如下标准化变换： x ；一五i 乙= 型二，f = 1 , 2 ，n ；j = 1 , 2 ，p 其中；，：匦一z ：二唾型，得标准化阵z 。 n 。 ，z 一1 s t e p 2 ：对标准化阵z 求相关系数矩阵 尺= k 】p 印= 鲁署 其中， ，! = 骅 f 川，2 ，肌 s t e p 3 ：解样本自相关矩阵r 的特征方程lr 一甜，i = o 得p 个特征根， 按嚣孔s s 圳每个 z ，j = 1 , 2 ，m ，解方程组r b = 五，6 得单位特征向量6 0 ，。 s t e p 4 ： 将标准化后的指标变量转换为主成分= 互t 口0 ，j = 1 , 2 ，m u 。称为第一主成分，u 2 称为第二主成分，u 口称为第p 主成分。 s t e p 5 ：对m 个主成分进行综合评价。 对m 个主成分进行加权求和，即得最终评价值，权数为每个主成分的方差 贡献率。 1 8 四川师范大学硕士学位论文 3 1 3 第一主成分的非线性推广 主成分分析将目标函数定义为求解数据集合到一个矢量( 直线) 投影的均 方差最大问题。这里，关键是“数据集合到矢量 ，换句话说，主成分分析的 目标是求出一个矢量，以使其满足目标函数。因此，问题可以简化为求解该数 据集合的自相关矩阵的特征值方程。显然，主成分分析也可以理解为限制函数 族为一次多项式的条件下的最优函数问题。 第一主成分线的计算有下述几个性质：( 1 ) 使得数据在直线上投影的方差 最大，( 2 ) 使得数据到直线的距离函数最小，( 3 ) 数据分布呈椭圆时，第一主 成分线上的点是所有投影至该点的数据点的条件均值。这几点性质也证明了如 果数据分布满足高斯分布，第一主成分线等价于描述分布“中间性的直线， 自相关矩阵的特征向量量描述了数据分布的方向，而特征值表述了分布的大 小。 如果数据集合的分布不满足高斯分布，采用线性主成分分析时，一般不能 获得真实反映数据集合分布的描述。我们要想更为准确地描述任意数据集合在 任意分布下数据的方向、大小及。中间”性，主成分分析将无能为力，这是主 曲线提出的主要动机与意义。在很多实际应用场合，我们需要如果对数据集合 的总结以曲线甚至曲面( s u r f a c e ) 方式给定，在数学上，这个问题类似的也 转化为求解整个函数族中满足给定目标函数的最优函数问题。由于主成分与主 曲线( 曲面) 之间的密切联系，h a s t i e 在提出主曲线时，继承了主成分分析中的 这种基本思想。 下图是一个简单的例子n 引，图3 - 1 中显示了由3 0 0 个包含误差的数据点构成 的余弦状分布，图5 的直线是数据的第一主成分线，其对余弦数据的描述长度 显然较右图要短，因为这些数据点将是由一个线段描述，我们可以认为右图对 数据的信息保持性则比左图要好，一方面，它与数据间的距离均方差也要小， 另一方面，它能勾画出原始信息的轮廓。右图则是根据主曲线原理所获得的结 果。 1 9 四川师范大学硕士学位论文 图3 - 1 ：第一主成分线和主曲线对比 基于上述讨论可知，主曲线与主成分的目标函数( 距离函数) 是相同的，获 得在目标函数下曲线应该满足条件的推导过程似乎也是类似的，甚至这个条件 的形式都是可以理解为求解数据集合的自相关矩阵的特征值方程。但是，主成 分的形式己知为直线，而主曲线形式却未知。因此，尽管在推导满足距离函数 的曲线条件时，无需考虑曲线的形式。但是，在求解特征值方程时，必须已知 基于特定曲线形式下数据集合的自相关矩阵。这就是问题的困难所在，一方面， 曲线的形式是被求