（模式识别与智能系统专业论文）非限制手写字符分割中相关技术与算法的研究.pdf

博上论文 非限制手写字符分割中相关技术与算法的研究 摘要 在文本识别中，字符分割是单字识别的前提和基础，字符分割效果的好坏将直接 影响识别的正确率。目前的研究和应用表明，字符分割已成为将字符类型识别、字符 识别核心算法、后处理等多项o c r 核心技术进行有效整合的中心。因此，研究如何 有效地进行字符分割对于提高系统的整体性能具有极其重要的意义。本文以非限定手 写体字符为研究对象，主要对字符分割过程中的一些相关技术和算法进行细致的研究 及改进，并给出了阶段性的算法描述和实验结论 针对手写汉字字符串中字符之间极易发生粘连、交错、过分等现象，采用单一的 切分方法无法同时对上述情况给予完善处理的问题，提出了一种多步的切分方法。该 方法分三个阶段对字符串进行分割：( 1 ) 非粘连字符的切分；( 2 ) 粘连字符的切分；( 3 ) 过分割字符的合并。该方法通过将多种切分算法进行有效地结合，对每个算法用其所 长，每个阶段都是针对特定问题来解决的，从整体上提高了执行效率。 过分割汉字的合并实际上是从所有候选路径中选出一组正确的分割路径。为了尽 可能地减少分支路径的产生，提高搜索效率，在寻找最优分割路径的过程中，应用 a 启发式搜索算法动态地确定候选路径的最小分割代价，据此对每一个搜索位置进行 评估，从而有效地搜索出最优分割结果。该方法对分割路径的评价标准更直接，求解 过程更快捷、准确。 滴水算法在对粘连数字的分割中表现出较好的执行效果，但该方法主要存在以下 两个问题：( 1 ) 在确定水滴滚落起始位置时容易受局部信息的干扰，给算法的执行带 来一定的困难；( 2 ) 垂直渗漏过程使倾斜字符笔划受损严重，造成错误分割。针对上 述不足，引入蓄水池的概念，提出了基于背景区域分析的方法，限定了滴水算法切分 起始点的搜索范围，建立了字符粘连类型的判别规则，实施了面向粘连类型的分割策 略，扩展并改进了传统垂直渗漏过程，使滴水算法的实用性和准确性得到了提高。 手写草体字因其笔划连带、省减，字体模糊、不确定等因素给切分和识别带来极 大的困难。针对手写草体英文字符串的分割，以普遍流行的过分割方式为主体框架提 出了一种基于识别后处理的分割方法。该方法先对原字符图像进行不规则分割区域划 分，尽可能地使每个区域内都隐含一条分割路径，然后利用动态规划算法来求取分割 路径在代价函数的定义上，提出了灰度信息与二值信息相结合的方法，以兼顾二值 图像中相关信息的丢失和灰度图像中不相关信息的干扰。在对分割路径进行处理时， 设计了过分割验证器来决定预分割后的子图像是否需要进一步的合并，并利用识别器 摘要博士论文 和统计语言模型相结合的方法来确定合并方案，以获得符合上下文关系的更准确的分 割结果。 关键词：手写字符分割，a 算法，蓄水池原理，滴水算法，过分割， 统计语言模型。 博士论文非限制手写字符分割中相关技术与算法的研究 a b s t r a c t c h a r a c t e rs e g m e n t a t i o ni sac r i t i c a l 雠t o ri nt h et o t a lr e c o g n i t i o ns y s t e m $ i n t a n y e 力_ o ri nt h i ss t a g ew i l lp r o p a g a t et oa l ll a t e ra n a l y s i s r e s e n tr e s e a r c h e sa n da p p l i c a t i o n s s h o wt h a tc h a r a c t 盯s e g m e n t a t i o nh a sb e 跚et h eo o t oc e n w a l i z ec l l a r a c t e rc l a s s i f i c a t i o n , r e c o g n i t i o nk e r n e la n dc o n t e x tp o s 瞳p r o c e s s i n g a n ds t u d yo nh o w t os a p o r a t cc h 卸噙c 幻糟 c o r r e c t l yb e f o r et h e ya i es e u tt ot h er e c o g n i t i o ne n g i n ei sv e r ys i g n i f i c a n tt oi m p r o v et h e t o t a ls y s t e mp e r f o r m a n c e i nt h i sd i s s e r t a t i o n ，s e v e r a lk e yt e c h n i q u e sa n da l g o r i t h m so i lh a n d w r i t t e nc h a f a c t e 璐 s e g m e n t a t i o na r ed i s c u s s e d h a n d w r i t t e nc h i n e s ec h a r a c t e r sm a yb ew r i t t e nt o u c h i n go ro v e r l a p p i n ge a c ho t h e r , a n da n ys i n g l em e t h o do r un o tg i v ep e r f e c ts o l u t i o nt ot h e mc o n c u r r e n t l y f o ra b o v e s i t u a t i o n s ，am u l t i - s t a = g ea p p r o a c hi sp r o p o s e df o ro f f - l i n eh a n d w r i t t e nc h i n e s es 咖 s e g m e n t a t i o n , w h i c hc o n s i s t so f n o n - t o u c h i n gc h a r a c 把f ss e g m e n t a t i o n , t o i l c h i n gc h a r a c t e r s s e g m e n t a t i o na n do v e r - s e g m e n t e dc h a r a g t e r sm o r g i l l g b ym e a n so fc o m b i n i n gs e v e r a l m e t h o d se f f e c t i v e l y , e a c hp r o b l e mi ss o l v e di nac c l l a l ns t a g ea n dt o t a lp e r f o r m a n c ei s i m p r o v e d i nt h ep r o c e d u r eo fm e r g i n go v e r - s e g m e n t e dc h a r a c t e r s ，t h ew e l l - k n o w na h e u r i s t i c s e a r c ha l g o r i t h mi s a p p l i e dt of i n d t h eo p t i m a ls e g m e n t a t i o nr e s u l t si nt h ew e i g h t e d s e a r c h i n gg r a p h w i t hd y n a m i c a l l yd e t c r m i n i n gt h e t h em i n i m u ms e g m e n t a t i o nc o s t f u n c t i o na st h ec r i t e r i o no fc o n f i d e n c el e v e l , t h en u m b e ro ft h et r a v e r s e dp a t h sw o u l db e m i n i n a l 。 d r o pf a l la l g o r i t h mi sm o r ea c c u r a t ei ns e v e r a lc o n t o u rs p l i t t i n ga l g o r i t h m s ，b u ti ti s l a c k i n gi nl o c a t i n gt h e s t a r tp o i n ti n s l i d i n gp r o c e s sa n ds e e p i n gp r o c e s si nv e r t i c a l d i r e c t i o nt h r o u g ht h eb l a c kb l o c lf o rt h ep u r p o s eo fs o l v i n gt h ep r o b l e m sa n dg e t t i n g b e t t e rp e r f o r m a n c e ，b a c k g r o u n dr e g i o na n a l y s i si sp r o p o s e df o rs e g m e n t i n gh a n d w r i t t e n t o u c h i n gn u m e r a l s a c c o r d i n gt ot h ei n f o r m a t i o ne x t r a c t e df r o mt h eg i v e nb a c k g r o t m d r e g i o n , t h el o c a t i o no ft h es t a r tp o i n ti ss p e c i f i e d , a n dt h ec r i t e r i aa r ce s t a b l i s h e dt o d i s c r i m i n a t et h et y p eo ft h et o u c h i n gn u m e r a l s t os p l i tt h en u m e r a l s ，d i f f e r e n ts t r a t e g y o r i e n t e dt o u c h i n gt y p ei si m p l e m e n t e db ys e l e c t i n g 觚a p p r o p r i a t ea l g o r i t h mf r o mt h es e t o fd r o pf a l la l g o r i t h m , a n dt h es c e p i l l gp r o c e s si se x t e n d e da n d i m p r o v e dt og e ta c c u r a t e s e g m e n t a t i o nr e s u l t s ，w h e nt h ed r i pm o v e st h r o u g ht h e j u n c t i o nb c t w nt h et w on u m e r a l s t h e p r o b l e mo f s e g m e n t i n gt h ec u r s i v eh a n d w r i t t e nl e t t e r si sm a d ec o m p l e xb yt h ef a c t t h a tt h ew r i t i n gi s i n h e r e n t l ya m b i g u o u sa st h el e t t e r si nas t 血l ga r eg e n e r a l l yl i n k e d 1 1 i a b s t r a c t博士论文 t o g e t h e r , p o o r l yw r i t t e n , a n dm a ye v b m f lb em i s s i n g a sac o n s e q u e n c e c u r s i v el e t t e r s s e g m e n t a t i o nr e q u i r e ss o p h i s t i c a t e dt e c h n i q u e s t h e r e f o r e 觚a p p r o a c hb a s e d o i l r e c o g n i t i o n a n d p o s t p r o c e s s i n g i s p r e s e n t e d , w h i c h a d o p t s t h e p r e v a l e n t o v e r s - s e g m e n t a t i o nt e c h n i q u ea n dm a k e s f u l lu s eo fr e c o g n i t i o na n dc o n t e x t u a l i n f o r m a t i o nt oc o m p e n s a t ef o rt h ea m b i g u i t y f i r s t l y ，t h e 妊n gi i b a g ei sd i v i d e di n t os o m e s e g m e n t a t i o nr e g i o n s e a c ho fw h i c hc o n t a i n sas f l i t t i n gp a t ht oa s s u n om o r et h a no d e c h a r a c t e ri n 扯i nt h ef o l l o w i n gs t e po fg e n e r a t i n gt h es p l i t t i n g p a t hb yd y n a m i c p r o g r a m m i n g ，t h ei n f o r m a t i o no fg r a ys c a l ea n db i n a r yi m a g e sa r ec o m b i n e di no r d e rt o a v o i dt h el i m i t a t i o no f b o t hg r a y s c a l ei m a g ea n db i n a r yi n 扭g e i nt h er e c o g n i t i o ns t a g e ，t h e o v e r - s e g m e n t a t i o nv e r i f i e ri sd e s i g n e df o rd e t e r m i n i n gw h e t h e re a c hp r e s e g m e n ti sf l l r t h o r p r o c e s s e do rn o t , a n dt h ev e r i f i e ri n t e r a c t sw i t ht h ec l a s s i f i e ra n dt h es t a t i s t i c a ll a n g u a g e m o d e lt oa c h i e v em o r er e l i a b l er e s u l t s n a m e l ye a c hs e g m e n tc o n t a i n i n ge x a c t l yo n el d 舱r k e y w o r d s ：h a n d w r i t t e nc h a r a c t e r ss e g m e n t a t i o n ，a + a l g o r i t h m ，w a t e r r e s e r v o i r , d r o pf a l la l g o r i t h m , o v e r - s e g m e n t a t i o n , s t a t i s t i c a ll a n g u a g e m o d e l i v 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：墨盘2 0 0 7 年7 月2 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：二埠_ 2 0 0 7 年7 月2 日 博士论文 非限制手写字符分割中相关技术与算法的研究 i i 引言 第1 章绪论 文字是人类思想的载体，是交流的工具。进入信息时代后，面对日益增长、呈指 数膨胀的海量信息，传统以纸为媒介来存放并处理文字、数据和图像等信息的方式己 无法满足信息时代的要求，人们广泛采用计算机、网络、通讯等信息处理技术来适应 日新月异的信息化世界。 光学字符识别( o c r ) 是模式识别学科的个重要研究领域，它的研究最早开始于 2 0 世纪4 0 年代。从5 0 年代以后，许多研究者在这一领域开展了广泛的探索l l 一，推动 了模式识别的发展。随着电子信息的应用越来越广泛，人们对计算机的要求也越来越 高，希望计算机在一定程度上具有类似人类一样的智能，能听懂人类的自然语言，看 懂人们所写的各种文字，认识人们的面容，甚至理解人们此刻的心情。人类的这些需 求给模式识别及人工智能的研究与应用提供了强大的动力，也使字符识别在这段时期 一直成为模式识别领域中的重要研究方向之一。 近年来，o c r 技术在许多领域中得到广泛的运用，例如通用票据自动处理p 羽、 文档的自动录入【6 】、邮政编码自动分检 7 - 9 1 、车牌和集装箱自动识别1 1 川等。目前，大 多数字符识别是针对单字进行识别的，在这些应用系统中通常先把待识别字符从图像 中提取出来，然后把提取的字符串分割成一系列的单个字符，再送入分类器进行单字 识别。毋庸置疑，字符识别的实现除单字识别以外还必须解决好字符分割的问题。因 此，字符分割是o c r 系统中一个必不可缺的关键步骤，占有极其重要的位置，1 2 1 。 然而，在字符识别技术发展的早期，研究重点主要集中在提高分类器单字识别的 性能上，实验使用的字符串图像都是很容易被切分的，因此，字符分割并没有引起充 分的关注。但是，随着o c r 技术在商业上的应用不断扩大，需要处理的对象越来越 复杂，切分的难度也随之增大【1 3 1 ，字符分割技术已逐渐成为研究的热点。一些国外研 究者们发现，由于分割不当引起的识别错误比由于字形不规范而引起的错误还要多， 这种情况不论是在印刷体还是手写体字符的识别系统中都存在【闻。也就是说，只有当 每一个单个字符图像都能正确地从文本图像中分割出来，才有可能进行正确的字符识 别，否则必然造成难以校正的错误，可见字符分割在字符识别中的重要影响。 本文主要以非限制手写体字符为研究对象，着重讨论了字符分割中的相关技术和 算法 第1 章绪论 博士论文 1 2 字符分割概述 在众多的o c r 应用系统中，文本图像往往先被分割成只含有单个字符的子图像 集，然后送入识别模块进行字符识别。将多字符图像切分成单字符图像的过程就是字 符分割。字符分割在o c r 系统中处于重要地位，分割的准确率将直接影响整个o c r 系统的性能。 字符分割属于图像分割范畴，根据不同的字符集可分为英文字符分割、汉字字符 分割、数字字符分割、中英混合字符分割等；根据不同的字符形式可分为印刷体字符 分割、手写体字符分割等。其中手写体字符又有工整手写体和非限制手写体之分，不 同的对象一般采用不同的切分方法，然而许多不同字符也可以采用相同的切分策略。 在实际应用中，字符间的位置关系常常表现出以下五种形式： ( 1 ) 孤立：字符之间各自分开，独立为整体； ( 2 ) 粘连；两个字符在某个笔划一点处或多点处接触： ( 3 ) 交错：两个字符投影有重叠，但没有实际粘连； ( 4 ) 交叠：两个字符共享某一块像素区域； ( 5 ) 粘连且交错：粘连与交错情况同时存在； 粘连是指两个字符的轮廓在一点处或几点处接触，如果能找到粘连位置，可以利 用直线或直线段将两个字符完全分开。交错是指两个字符没有接触，属于不同的连通 区域，但它们的垂直投影有重叠，这种情况下无法用直线将两个字符完全分开。交叠 是指两个相邻字符不仅轮廓相接，而且共享某一部分像素区域，这种情况处理起来较 为复杂，但并不常见。上述几种情况的综合形成了更为复杂的情况，如相邻字符既粘 连又交错等。 很多情况下，字符的字体存在着多样性，各种因素使得字符分割的复杂性变大。 从分割的难易程度上看，手写体的难度大于印刷体，而非限制的手写体又要难于普通 的手写体。就切分方式来讲，对于字形比较工整或字间距较为固定的字符可以采用简 单的方法进行切分：对于复杂情况的字体，采用的切分方法也较为复杂。当前的研究 方法不仅要借助于字符，还要借助于短语甚至整个文档的结构分析，例如利用h m m ” 1 6 1 、神经网络【1 7 1 引、上下文语义分析【1 9 1 等工具。在系统实现中，多种因素决定了切分 算法的多样性和系统实现的复杂性。目前，字符分割的难点是解决粘连字符的分割问 题。 1 3 字符分割的策略 在o c r 系统中，字符的分割过程和识别过程是密不可分的，分割是识别的基础 和前提，识别的好坏又决定了分割效果的优劣，这两个过程相互启发、相互反馈。根 2 博士论文 非限制手写字符分割中相关技术与算法的研究 据分割过程对识别结果的不同依赖程度，可将字符的分割策略分为以下几类【2 啪】： 1 基于图像分析的分割方法( i l n 零g ca n a l y s i sb a s e ds e g m e n t a t i o nm e t h o d ) 或称为 直接剖分方法( d i s s e c t i ) 畔1 。 2 基于识别的分割方法( r e c o g n i t i o n - b a s e ds e g m e n t a t i o nm e t h o d ) 或称为自由分割 方法( s e g m e n t a t i o n - f r e em e t h o d ) 脚冽。 3 上面两种方法的混合网。 4 整体识别方法( h o l i s t i c ) 或称为全局识别方法( g l o b a lm e t h o d ) 1 3 1 1 3 i 基于图像分析的分割策略 基于图像分析的分割方法是经典的字符切分方法。这种策略充分利用了字符图像 的结构特征和统计特征，例如字符的高度、宽度、相邻字符块的间距、笔划的分布规 律等将字符图像分割成字符块，然后送入识别器。当然，也可以利用识别结果来验证 分割是否正确，但分割并不依赖于识别。这种切分方法从o c r 的早期开始至今不断 地得到发展，其中常用的几种图像特征主要有： ( 1 ) 字符间隙和字符大小特征 ， 字符间隙是分割的一个重要特征。对于印刷体或书写工整的手写体，字符之间通 常有固定的空隙，并且每个字符的宽度变化不大，从而为确定分割点提供了依据。在 某些特定的应用领域中，字体的书写也受到一定的限制，比如，银行支票上的字体被 规定在方格内，为字符切分提供了方便。另外，字符大小和水平单位距离的字符数等 特征也可以作为切分依据。 ( 2 ) 投影特征 投影法【3 2 】是许多字符切分中采用的基本方法。它主要通过统计图像中每一列( 行) 的黑像素个数得到垂直( 水平) 投影直方图。在直方图中字符区域对应于波峰，字符间 隙对应于波谷，以此为基础对字符进行切分。投影法的优点是算法简单，容易实现， 而且速度较快。一般说来，投影法的切分路径为一条直线，比较适用予字符之间能够 明显分开或者出现简单粘连的情况，而对于严重粘连或交错的字符难以区分字符边 界，往往得不到正确的切分。这时，投影特征只能作为一种补充手段。 ( 3 ) 连通域特征 连通域分析法【1 2 】是在整个字符图像中寻找相连的像素作为连通元，分析这些连通 元本身的图像属性，判断它们是属于同一个字符图像，还是属于相邻字符图像的粘连， 然后利用一些先验知识对它们进行拆分和合并。连通域分析法对于交错字符，即两个 字符外接矩形有重叠、但并没有发生实际粘连的字符切分效果较好。但使用该方法时 连通元容易过碎，使严重断裂的字符图像无法重新合并，真正粘连的字符也不能通过 连通元切分开，这需要在后续的识别模块中加入粘连字符模板或者通过其它方法进行 3 第1 章绪论 博士论文 再切分。连通域分析法对书写倾斜的字符能够准确地切分，这一点好于投影法。 1 3 2 基于识别的分割策略 基于识别的分割策略是通过识别模块来指导切分，识别结果对分割起着决定性的 作用，分割是识别的副产品，它避免了复杂的硬分割算法。基于识别的分割策略可分 为两类：递归分割法和识别寻优法。前者首先将字符图像利用某些结构特征分成一些 字符块，然后根据这些字符块的识别选取最优分割结果。后者是在细分割结果下，利 用识别结果来选择最优方案。 ( 1 ) 递归分割法 递归分割法【3 3 - - 般先在整个字符图像中大致找出所有可能的分割点，然后利用一 个大小可变的矩形浮动窗口，对窗口内的子图像依次进行识别，并将窗口内识别出的 子图像从待识别图像中删去，再对其余图像继续识别。反复执行此过程，直到每个窗 口中的子图像都能找到对应的识别类。 ( 2 ) 识别寻优法 识别寻优法【卅是先根据字符图像的一些基本特征产生一系列的假设切分点，并对 其进行识别；然后根据识别结果选择最佳的切分方案。识别器的引入方式分为串行和 并行两种。串行方式是从左到右反复对字符进行识别，直到找出最满意的识别结果。 并行方式则采用全局方法，首先产生包含所有字符块组合的分割图，然后在分割图中 选择最优路径作为最佳切分方案。 1 3 3 混合分割策略 字符分割可以采用上面两种策略中的一种，也可以是两种策略的组合。 最近发展起来的过分割方式( o v e r - s e g m e n t i n g ) ，3 0 】就是综合直接剖分和基于识 别的一种组合方法。它首先利用某个切分算法在整个字符图像中找出尽可能多的候选 分割点，进行最大可能的切分，在此过程中允许单个字符被分成多个部分。然后将得 到的一系列候选切分路径送到识别器中，根据识别结果的好坏来选取最合适的切分方 案作为最终分割结果。这种方法是在近几年识别算法完善的基础上发展起来的，由于 它可以利用一定的规则来指导和判断切分，因此在邮政、金融等具有一定先验知识的 领域中有着广阔的应用前景。 1 3 4 整体识别的分割策略 整体识别的切分策略是在识别过程中不再把字符串看成仅仅是多个字符的简单 组合，而是把整个字符串视为一个具有逻辑意义的对象来进行识别，它主要考虑的是 4 博士论文 非限制手写字符分割中相关技术与算法的研究 分割后整串字符的综合识别效果。识别时，般以特定的语法或者字典库作为驱动， 然后采用诸如隐马尔可夫模型f 3 5 】或动态规划 3 6 1 等一些方法，根据前后关联得到整体 上的最优解。由于该方法需要预先设定一些词，因此识别器的识别结果只能局限于特 定的字典库，这样限定了它只能应用在具有专门词汇以及特定用户的行业中，比如地 址识别和支票识别，这是该方法的主要缺点。 由上述可见，基于图像分析的分割策略是对图像进行的硬分割，与识别以及后处 理模块是分开的，其分割效果的评价标准是分割后的字符块是否符合单个字符的一些 属性，例如高度、宽度，与相邻字符块之间的位置关系等等：基于识别的分割策略结 合分割和识别，在二者的反复交互中完成分割，其评价标准是识别结果的可信度；整 体识别的切分策略更是引入了后处理的功能，以词表等作为驱动，从整体上指导分割 和识别的进行。 1 4 手写字符的分割方法 前面提过，不同的对象一般采用的切分方法不同，然而许多不同的字符也可以采 用相同的切分策略。下面按手写字符分割的不同处理对象来分别介绍。 1 4 1 手写英文的分割方法 英文字符的分割是影响识别率的重要因素之一。因为英文以单词为单位，每个单 词由若干字母组合而成，如果一个字母出现错误，整个单词的识别结果就会受到影响。 常用的方法有以下几种： l 。字符间隙法 最早使用的方法就是利用字符间隙( 指两个字符间的空白间距) 和字符间距( 指两 个字符中心的距离) 进行字符切分f 1 2 】。这种方法非常简单，利用基本相同的字符宽度 和相近的字符间隙，通过搜索字符间隙进行切分。该方法要求字符宽度和字符间隙基 本相同，并且对输入图像的质量依赖性很大，因此，只适合于书写比较工整的字符切 分。 2 垂直投影法 。 垂直投影法是利用垂直方向上的投影特征来进行字符切分。具体来说就是对整个 字符图像进行石轴方向上的投影，得到纵向黑像素个数的统计直方图。字符区域对应 直方图中的波峰，字符间的空隙对应直方图中的波谷。以此为基础，加上必要的修正 措施在文本行中进行切分，得到一个个单独的字符图像。投影分析法的不足之处在于： ( 1 ) 不适用于粘连或交错字符的分割；( 2 ) 对于严重倾斜和印刷质量较差的图像，由于 投影特征不够清晰，很难找到确定的切分位置；( 3 ) 对于笔划断裂的字符，容易造成 第l 章绪论 博士论文 字符过分割或分割不足；( 4 ) 切分路径多数是直线。 3 连通域法 连通域法f 1 2 j 也是一种应用比较普遍的字符切分方法。该方法首先在整个字符图像 中找到所有连通元。然后通过分析这些连通元图像本身的属性或根据上下文的依赖关 系来对连通元进行拆分和合并。对于非粘连字符，连通域法是一个非常有效的切分方 法，它能够很好地解决交错字符的切分问题，但对粘连字符却无能为力。该方法若能 同时融入单字识别及语义理解，会得到更好的切分效果。 4 基于动态规划的方法 动态规划d p ( d y n a m i cp r o g r m m i n g ) 算法啪】是一种很有效的寻找最佳路径的方 法，它通过把一个步过程转化为个单步过程，来降低算法的复杂度。应用动态 规划能够避免垂直切分造成字符损伤而给后期识别带来的影响。它往往预先定义切分 点的分割代价，通过计算、比较来进行小范围的优化，从中寻找切分路径。虽然该方 法能够在一定程度上对切分路径起到调节作用，但由于分割代价的计算具有局部性， 对切分路径的寻找只在黑白像素交界处具有选择作用，一旦进入黑( 白) 像素区就只能 进行垂直分割，因此并未从根本上解决多种粘连方式的分割问题。 5 基于距离变换的方法 文献【1 2 】介绍了一种基于距离变换的切分方法。该算法分为三个步骤进行：初始 切分、分裂和合并。初始切分是首先利用相邻部件进行字符分割，然后通过连接水平 线来组合断裂字符；分裂是在距离变换的基础上进行，它将背景像素用其到最近笔划 的距离来表示，具有最小距离值的点被看作是可能的分割点，同时采用启发式方法定 义切分路径的起始点并修改距离函数；最后根据动态规划算法与神经网络分类器相结 合的输出来得到最终分割结果。 6 基于识别的方法 基于识别的方法首先通过某个算法得到一些可能的分割位置，然后根据分割图像 的识别结果进行验证。这类方法的优点是：( 1 ) 可以动态地选择分割点，减少因分割 错误丽造成的误识或拒识；( 2 ) 切分难度大大降低，因为只要求分割出一定范围内的 字符笔划图像，而不是完整的单字符图像。缺点是：( 1 ) 切分时间长；( 2 ) 切分的正确 性依赖于识别算法：( 3 ) 容易发生过分割现象，有时尽管所有分割出来的子图像都得 到了正确匹配，但结果却是错误的。这时，需要通过后处理来提高识别和切分的准确 度，但切分时间也将随之增大。 7 上下文分析法 英文单词是最小的语义单位，组成单词的各个字符之间是前后关联的。目前，单 字识别正确率不可能无限制地提高，想要进一步提高识别率，就必须建立文本的词法、 句法和文法模型，充分利用上下文相关信息作为识别的补充手段来检测、纠正识别中 6 博士论文 非限制手写字符分割中相关技术与算法的研究 的错误。后处理就是利用文本的实际相关信息，对分类器的识别结果做进一步处理， 从而提高整个系统的识别率。目前，后处理主要采用的方法有：( 1 ) 字典法。即把经 常使用的词汇有条理地组织起来，以便与候选结果匹配：( 2 ) 统计法。即统计单词中 字与字的相关概率，然后在候选结果中加以利用；( 3 ) 词典法与统计法的结合。 1 4 2 手写数字的分割方法 目前，手写数字的分割方法很多，除了常用的垂直投影分析法、连通域分析法以 及上下轮廓特征法阳以外，还有一些较为复杂的方法： 1 基于区域的方法 基于区域的方法口8 ，3 9 1 首先将字符图像中的背景区域分为山峰区域、山谷区域和环 区域等，然后利用“峰顶”和“谷底”两种匹配算法确定可以构造出分割路径的特征 点。但由该方法得到的区域经常出现冗余分割点。当两个字符之间的公共笔划过长时， 该方法也表现得不太稳定。 2 基于轮廓的方法 基于轮廓的方法充分利用了字符图像的原始信息，例如外轮廓线上曲率最大值点 4 0 1 、每一列y 坐标的最大最小值1 4 ”、相邻笔划的垂直边缘 4 2 , 4 3 】、水平穿越笔划数 4 4 1 、 上下轮廓距离1 3 0 , 4 5 1 、轮廓角点【柏删以及分离字符的几何度量【4 7 】等因素。 ( 1 ) 重要轮廓点算法 重要轮廓点 4 0 l ( s i g n i f i e a t ec o t m t o u rp o i n t s ，s c p ) 是字符结构上的一类特征点，它包 括拐点、局部极值点以及延伸凹角处的直笔划所得到的潜在路径的入点和出点。因此， 可以从这些特征点中选出一对构造出切分路径。选择时需要考虑的因素有：局部极小 值极大值点对、拐点、点间的距离、轮廓变化的剧烈程度、极小值极大值点对之问 的水平距离、极值点到图像左边缘的距离等。 ( 2 ) m i l l - m a x 算法 m i n - m a x 算法 4 8 1 是目前使用较多的切分算法，它基于以下前提：两个字符总是 在它们上下轮廓间的距离最短处发生粘连。因此，该算法主要考虑极小值极大值点 对，将字符分为上下轮廓，通过寻找上轮廓极小值点和下轮廓极大值点来确定合适的 切分路径。当出现不止一个轮廓极值点时，可能有多条候选切分线。这时需要通过其 它一些特征来选出其中的一对来生成切分线。选择时主要考虑的因素有两点间的距 离、点到图像中心的距离以及切分线穿越笔划的次数。 重要轮廓点算法和m i n - m a x 算法都不能保证正确地找到所有分割点，例如当两 个字符之间是以一个直笔划连接时，轮廓特征点中是不存在明显分割点的。 ( 3 ) 滴水算法 滴水算法 4 9 1 是通过模仿水滴在字符的粘连处从高向低自由滴落的过程来对字符 7 第l 章绪论 博士论文 串进行切分。水滴从当前位置开始，在重力的作用下沿着字符轮廓向下滴落或水平滚 动，根据一系列规则在相邻位置中搜索下一点，水滴经过的轨迹就是切分路径。在该 算法中，如何确定水滴滚落的起始位置是一个关键问题。 3 基于背景分析的方法 背景分析方法【5 0 1 ( b a c k g r o u n da n a l y s i s ，b a ) 首先对字符的背景图像进行细化，并提 取特征点，包括分叉点、端点和角点，然后连接背景上的这些特征点，来构造从图像 顶部到底部的所有路径。最后利用混合高斯概率密度函数对候选路径进行评价，选择 最佳的一条切分路径。 前景背景分析( b a c k g r o u n da n df o r e g r o u n da n a l y s i s 。b f a ) 方法是对背景分析方法的 一种改进，它对前景和背景同时进行细化，利用前景和背景的特征点来构造切分路径。 该方法在构造切分路径的算法中，对字符多处粘连的情况也能给出相应的处理。 4 基于识别的方法 基于识别的方法【5 1 侧首先对字符串进行分割，然后将分割的子图像送入分类器， 以分类器的可信度作为评价标准，选取出最优的切分结果。这种方法可以提高字符串 切分和识别的准确率。但它依赖于分类器的稳定性，且效率不高。 在实际应用中，虽然每种切分方法都是行之有效的，但它们的适用范围都受到一 定程度的限制，无法处理手写数字串的所有情况。一般来说，对于相邻字符间隔比较 明显的情况，可以采用垂直投影法等简单的直线切分方法；对于倾斜、交错、粘连的 字符，则采用比较复杂的滴水算法和b f a 算法为好。但b f a 方法过于复杂，很难保 证实时性。滴水算法执行起来比较简单，但算法容易受到局部因素的影响。 1 4 3 手写汉字的分割方法 手写汉字的识别是模式识别领域中一个极具挑战性的难题【5 5 ) ，这不仅因为汉字书 写风格千变万化，给识别带来一定的困难，更主要的是汉字分割一直是汉字识别系统 中影响识别结果的重要因素。 当前，许多研究者对英文及数字字符的切分进行了大量的研究工作，然而对汉字 字符的切分主要是针对印刷体文本进行处理的，非限制手写汉字的切分方法目前还很 有限，常用的方法有以下几种： 1 垂直投影法 正如英文字符的分割，垂直投影法也是最早被应用于汉字分割的一种方法。该方 法速度快，实现简单。但投影分析法在汉字分割中同样存在几点不足：( 1 ) 无法进行 非线性分割；( 2 ) 在一定程度上依赖于手写汉字文本的书写质量和规范；( 3 ) 无法处理 字体大小变化较大的情况。因此，单纯的投影法不能在系统中被深一步地应用，往往 用来进行粗切分( c o a r s e g m e n t a t i o n ) ，然后对分割结果再次细切分 5 6 ( f i n e r 博士论文非限制手写字符分割中相关技术与算法的研究 s c g m o n t a t i o n ) ，从而解决粘连或交错字符的切分问题 2 笔划合并的方法 t s e n g 和c h e r t 提出了基于笔段边界框( s t r o k eb o u n d i n gb o x e s ) 合并的方法网。该方 法首先提取汉字的笔段，然后将各笔段的外接框经过细合并、倾斜笔段合并、重叠笔 段合并以及延伸笔段合并等几种基于知识的合并操作后，得到候选外接框，这些候选 外接框有的是汉字的外接框，有的是汉字部件的外接框。然后再利用动态规划方法， 根据这些候选外接框的长宽比，决定汉字字符的最佳切分边界。这种方法采用先提取 汉字的笔划边界再进行启发式合并的策略，可以有效地分割交错、粘连的汉字字符， 但缺点是计算复杂，而且对于字迹潦草的手写体汉字，由于笔划类别和边界难以准确 定义，因此分割效果不太理想。该方法比较适用于字迹工整的手写体汉字切分。另外， 如何有效地提取笔划信息还亟待解决。 3 组件合并的方法 汉字通常由笔划、字根和单字三个层次组成，字根位于笔划和单字之间的中间层 次，是构成单字不宣拆分的基本结构单位，又称之为部件、组件或元件。l u 5 8 埂出 了利用汉字结构特征和部件位置关系，对部件进行合并的方法。该方法将两个部件之 间的位置关系分为上下、左右和包围三种，根据每个部件的位置信息，可以较容易地 将上下和包围关系的部件合并，然后利用整个字符串中部件的分布信息再对汉字内左 右关系的部件进行合并。 4 基于b f a 的方法 这种方法的使用与手写数字的分割基本相同。在分割粘连汉字字符时，一般需要 记录粘连笔划上的分叉点，依据汉字字符的平均宽度确定顶部背景骨架线上的分叉 点，并将其作为候选分割点。然后，在一定角度范围内向下( 上) 跟踪背景骨架，以搜 索背景中的连接点，最后将上下两个端点的连线作为分割路径。 5 v i t e r b i 算法 t s e n g 2 8 1 以竖向排列的文本分割为例，详细介绍y v i t c r b i 算法在汉字分割中的使 用。v i t e r b i 算法是一种用于获得最佳路径的动态算法，利用它可以在字符串图像中产 生非线性的分割路径。从文献【2 8 】中给出的分割结果可以看出，对于交错字符的切分 达到了很好的效果。由于v i t e r b i 算法对于交错字符的分割效果好于粘连字符，因此， 可专门应用于非粘连字符的分割。 6 基于识别的切分方法 基于识别的切分方法在英文字符的切分中得到广泛的应用，但在一般情况下，这 种方法对汉字的单字识别器有更高的要求，一般要求单字识别器给出识别的可靠性。 求取汉字字符候选分割位置的方法归纳起来主要有两种：( 1 ) 投影法：( 2 ) 结构信息法 其中，结构信息法主要是通过对汉字图像中诸如连通域、笔划形状、长度等结构信息 第l 章绪论 博士论文 的研究，运用概率函数来确定可能的分割位置，经过一定数量样本的训练，得到指导 分割的分类器。结构信息法可以对汉字图像进行非线性分割，所以效率比较好。但由 于汉字结构信息的不稳定性，结构信息法对于不同样本集的性能差距很大，尤其是在 非限制手写汉字识别中，不仅计算的复杂度较大，而且很多汉字信息无法通过程序顺 利地提取，所以分割效果并不理想。 基于识别的方法与后期识别密切相关，虽然对于各种复杂情况都有一定的适应 性，而且可以动态选择分割点、减少分割错误，但由于单字识别耗时且正确率有限， 所以这种过于依赖识别的方法仍有待进一步地改善。 1 5 手写字符分割的研究现状 随着字符识别应用领域的不断扩展，分类器单字识别能力逐步得到了提升。然而， 粘连字符识别错误率还比较高。一般认为，粘连字符的错误切分导致了字符的严重失 真变形，无法