（计算机应用技术专业论文）基于结构分析的离线手写汉字切分.pdf

摘要 摘要 结构复杂、书写自由度较大的离线手写汉字识别是一项具有很大研究价值和应用前 景的课题。离线手写汉字的识别率与离线手写汉字的切分正确率密切相关，错误的切分 必然导致错误的识别，因此离线手写汉字切分技术的研究对离线手写汉字识别技术的发 展有着重要的意义。 本文针对离线手写汉字识别，提出了一种基于结构分析的离线手写汉字切分算法。 算法首先根据离线手写汉字的结构信息和合并可信度实现了无粘连情况的离线手写汉 字切分；然后针对离线手写汉字中的粘连现象设计了一种基于汉字结构聚类和笔画分析 的粘连切分算法。通过对不同人书写的大量文档图像的实验表明，本文设计的离线手写 汉字切分算法能够取得较好的切分效果。 关键词离线手写汉字识别离线手写汉字切分粘连手写汉字切分结构分析尽 均值聚类 a b s t r a c t a b s t r a c t o f f - l i n eh a n d w r i t t e nc h i n e s ec h a r a c t e rr e c o g n i t i o ni sc o m p l e xi ns t r u c t u r ea n dm o r e f r e e l yf o rh a n d - w r i t i n g i ti sag r e a ti t e mw h i c hi sv a l u a b l ei nr e s e a r c ha n dp r o s p e c t i v ei n a p p l i c a t i o n i t sr e c o g n i t i o nr a t ei sc l o s e l yr e l a t e dt oi t ss e g m e n t a t i o na c c u r a c ya n dt h ef a u l to f s e g m e n t a t i o nd e f i n i t e l yl e a d st ot h ew r o n gr e c o g n i t i o n s ot h er e s e a r c ho fo f f - l i n eh a n d w r i t t e n c h i n e s ec h a r a c t e rs e g m e n t a t i o nt e c h n i q u ei s s i g n i f i c a n tt o i t sr e c o g n i t i o nt e c h n o l o g y s d e v e l o p m e n t t h i sa r t i c l ep r o p o s e sa na l g o r i t h mw h i c hi sb a s e do nt h es t r u c t u r ea n a l y s i ss e g m e n t a t i o n i nv i e wo ft h eo f f - l i n eh a n d w r i t t e nc h i n e s ec h a r a c t e rr e c o g n i t i o n f i r s t l y , t h ea l g o r i t h m r e a l i z e sn o n - a d h e s i o no f f - l i n eh a n d w r i t t e nc h i n e s ec h a r a c t e rs e g m e n t a t i o nu s i n gt h es t r u c t u r e i n f o r m a t i o na n dt h em e r g ec o n f i d e n c el e v e lo fo f f - l i n eh a n d w r i t t e nc h i n e s ec h a r a c t e r ；a n d t h e nd e s i g n sac o n n e c t e ds e g m e n t a t i o nm e t h o db a s e do ns t r u c t u r ec l u s t e ra n ds t r o k e sa n a l y s i s f o rt h ea d h e s i o no fh a n d w r i t t e nc h i n e s ec h a r a c t e r s t h r o u g hal a r g en u m b e ro fd o c u m e n t i m a g e sf r o md i f f e r e n tp e o p l e ，e x p e r i m e n t ss h o wt h a tt h ed e s i g no fo f f - l i n eh a n d w r i t t e n c h i n e s ec h a r a c t e rs e g m e n t a t i o nm e t h o di sa b l et oa c h i e v ear e l a t i v eg o o ds e g m e n t a t i o nr e s u l t k e y w o r d s o f f - l i n eh a n d w r i t t e nc h i n e s ec h a r a c t e r s r e c o g n i t i o n o f f - l i n eh a n d w r i t t e n c h i n e s ec h a r a c t e r ss e g m e n t a t i o n s e g m e n t a t i o no fc o n n e c t e dh a n d w r i t t e n c h i n e s ec h a r a c t e r ss t r u c t u r ea n a l y s i sk m e a n sc l u s t e r i n g i l 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。 鱼 、 作者签名：璺d 凼 日期：衅年上月上日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密屯厂 ( 请在以上相应方格内打“4 ) 保护知识产权声明 本人为申请河北大学学砬所提交的题目为魂j 考搁牟颇赢南娜破奶 的学位论文，是我个人在导师叼膳夜、) 指导并与导师合作下取得的研究成果， 研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费 资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定 的各项法律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。 声明人：叁 j ：l 亟 日期：a 厶辽年丘月一之日 作者签名：壶d ：l 丑 导师签名：望堂鱼： 日期：4 年月三日 日期：垫1 2 年l 月l 日 第1 章引言 1 1 研究背景和意义 第1 章引言 随着o c r 技术应用领域的不断拓展，对离线手写汉字的识别已成为目前研究的热 点。实用化的离线手写汉字识别系统能够在信函分拣、银行支票识别、统计报表处理以 及手写文稿的自动输入、试卷的自动阅读等诸多领域发挥巨大的作用。然而离线手写 汉字的识别是模式识别领域中极具挑战性的难题，它被形象的称为汉字识别领域中“最 后的堡垒”。随着近几十年的研究，离线手写汉字识别技术已取得了一些研究进展，但 离实用化要求还有一定的距离。一方面是由于手写汉字识别技术本身固有的困难；另一 方面，手写汉字字符的切分也是汉字识别技术走向实用化的一大障碍。 虽然人们早就意识到无论是在印刷体还是手写体汉字的识别中，切分导致的错误识 别都要高于字形畸变导致的错误识别。但这个问题仍然经常被掩盖，这是因为在字符识 别的研究过程中，大多使用己切分好的样本做实验，或者在被测试的字串中预先加入人 为的空格，以便对识别算法本身进行讨论、评价f 2 】。但这使人们的书写习惯受到很大的 限制，导致离线手写汉字的识别系统远离社会需求。因此，在尽量适应人们日常书写习 惯的前提下，研究离线手写体汉字的切分显得更加迫切和重要。 综上所述，研究一种具有较高正确率的离线手写汉字切分技术不仅是手写汉字识别 系统迈向实用的必经步骤，而且对汉字信息处理系统的自动化，以及丌拓计算机新一代 的智能输入功能都具有重要意义。 1 2 国内外研究现状 在我国，汉字识别研究起步较晚。上世纪7 0 年代主要从事邮政信函分拣的数字、 英文和符号识别。上世纪7 0 年代末，一些大学和研究所开始对印刷体和手写印刷体汉 字的识别进行原理性的研究。到上世纪8 0 年代中未期，我国汉字识别研究才取得较大 进展，当时联机手写体汉字识别装置已有商品出售，印刷体汉字从单一字体的识别到多 种字体的识别已逐步实现【3 1 。 1 河，l 匕人学f 硕l j 学何论文 手写汉字识别的研究在国内从， ：世纪8 0 年代中期才真j f 丌始，到9 0 年代同趋活跃。 由于自由手写汉字识别难度很大，当时对手写汉字的识别更多的是致力于较为工整的单 个汉字的识别研究。然而经过儿十年的开发与研究，手写汉字识别的单字识别率越来越 高，正在朝着实用化的方向迈进。然而实用化的汉字识别系统不只要求对单字的高识别 率，更要求对整篇文档有很好的处理效果。这就不可避免的涉及到了手写汉字的切分问 题。因为手写汉字的识别正确率与切分正确率密切相关。错误切分必将导致错误识别， 所以设计一种具有较高正确率的手写汉字切分技术对识别技术的进一步发展有着至关 重要的意义。 针对手写汉字的切分方法主要分为3 类【4 】：基于统计的切分、基于结构的切分和基 于识别的切分方法。 基于统计的切分方法根据字符总体分布特征确定分割线，典型的如直方图投影法 【5 ，6 】，通过直方图投影找到可能的切分位置，然后根据一个统计的或估计的平均字宽作 为参考，选出最终的切分位置。统计分布特征的代表性和稳定性对切分的正确性及收敛 性起很重要的作用，因此该方法更适用于字符较为规整且宽度相差不大的情况。 基于结构的切分方法主要是根据汉字本身的结构以及汉字之间的位置关系来寻找 切分位置。常用的有连通域搜索算澍7 ，8 1 和笔划跟踪1 1 算法。连通域搜索算法能够有效 地解决重叠汉字的切分，但无法使粘连的汉字分开。笔划跟踪算法虽能很好的适应于带 有重叠、粘连的汉字切分，但计算复杂、效率较低，而且对于书写不够规范的汉字分割 效果不理想。 基于识别的切分方法通过识别模块来指导切分，识别结果对切分起着决定性的作 用。常用的切分算法有递归切分算法【1 2 1 和基于隐马尔可夫模型的切分算法【13 1 。递归切 分算法通常是先在整个字符图像中找出所有可能的切分点，利用一个大小可变的矩形浮 动窗口，对窗口内的子图像依次进行识别，然后从待识别图像中删去识别出的子图像， 再对其余图像进行识别；反复执行此过程，直到每个窗口中的子图像都能找到对应的识 别类。基于隐马尔可夫模型的切分算法一般根据字符图像的一些基本特征产生一系列的 假设切分点，并对其进行识别，然后根据识别结果选择最佳的切分方案。基于识别的切 分方法虽然能够减少因分割错误而造成的误识和拒识现象，但对时间和空间的资源消耗 较大。 筇1 章引肓 由于手写汉字书写随意性很人，不仅使得汉字大小、字i 、i l j 距、字内距变化很大，而 且使得汉字间的位置关系出现相离、重叠、粘连、交叠等多种情况。因此单一的切分技 术很难满足离线手写汉字的切分需求，更多的文献设计了综合上述儿种方法的多步切分 算法 1 4 - 2 3 】，然而到目前为止，仍没有一个完整的、适用性强、相对稳定、切分效果较 好的方法能够彻底解决汉字识别中的切分问题。由此可见，离线手写汉字的切分不仅是 汉字i , 5 t 另t l 系统中的难点，也是汉字识别系统走向实用必须解决的问题。因此还需要进行 更为深入的研究。 1 3 本文工作及内容安排 本文主要针对离线手写汉字的切分展丌研究。主要工作包括： ( 1 ) 针对无格式下离线手写汉字的单行出现倾斜，弯曲且各行倾斜、弯曲的角度、 方向等不相同的现象，设计一种对连通单元质心进行按行聚类的算法，实现整 篇文档的文字行的切分。 ( 2 ) 针对大小不一、字体多样、书写自由度较大的离线手写汉字，设计一种基于结 构分析的切分算法。 ( 3 ) 针对离线手写汉字中的两字粘连现象，设计一种基于汉字结构聚类和笔画分析 的粘连切分算法。 本文的内容安排如下： 第1 部分：介绍离线手写汉字切分的研究背景、意义和国内外研究现状； 第2 部分：介绍本文设计实现的离线手写汉字的切分算法； 第3 部分：分析离线手写汉字中粘连汉字的特点，介绍一种基于结构聚类和笔画分 析的粘连汉字切分方法； 第4 部分：分别对无粘连手写汉字和粘连手写汉字的切分结果进行分析； 第5 部分：对所做的研究工作进行总结，并对今后的研究工作提出建议。 河北人学l ：学硕f j 。f 一论文 第2 章离线手写汉字的切分 2 1 离线手写汉字切分的难点 随着识别技术的迅速发展，现有的o c r ( o p t i c a lc h a r a c t e rr e c o g n i t i o n ，光学字符识 别) 系统对印刷体文档图像的处理达到了很高的识别率。但是对离线手写汉字的识别效 果还未达到实用化的要求。虽然一方面是由于汉字识别技术本身固有的困难；但手写汉 字的切分也是限制手写汉字识别技术继续发展的一大障碍。 然而要实现离线手写汉字的切分有很多困难，概括为以下几个方面： 1 字体多、结构复杂。手写汉字与印刷体汉字相比较自由度较大，有人写字笔画 紧密；有人写字笔画松散；有人写字瘦长；有人写字宽扁。所以手写汉字字体多样而不 规范；结构复杂而无定律。就是同一个人书写的同一个汉字的大小及结构也要受到该字 前、后字及书写环境、心情等诸多因素的影响。加之一个汉字的结构又可分为左、右， 上、下，包围，半包围以及这些关系的多种组合，如图2 1 所示，因此要想实现高正确 率的手写汉字的切分将要克服很多困难。 幽苘 署 圈阅 ( a ) 左右结构 ( b ) 上卜结构( c ) 包围结构 ( d ) 卜包同结构 图2 1 不同结构的手写汉字 其中以带有左右结构的手写汉字最难切分，如图2 1 的( a ) 所示。因为左右结构的字 有很多是由独体字组合而成，而各人手写习惯不一样，导致字内距与字间距的关系不确 定，有人写字字内距大于字间距，有人写字字内距小于字问距，还有人写字字内距与字 间距相差不大。如果再考虑到字形的影响，有些情况是很容易导致错分的。例如：在字 内距与字间距相差不大的情况下，如果字间距较小且字宽过窄，就很容易出现将两个独 体字切成一个汉字的情况，如图2 - 2 ( a ) 所示。相反，如果字内距过大且字宽过宽，又 可能将一个汉字的两个部分分开，而将其切成两个汉字，如图2 - 2 ( b ) 所示。在字内距大 第2 章离线丁巧汉宁的切分 于字问距的情况下，对于左右结构的汉字，如果汉字宽度，小于一定平均字宽的6 倍， 则容易出现如图2 - 2 ( c ) 所示的错误。 褥习寻圈囝 ( a ) 字间距小且宽小( b ) 字内距大且字宽大( c ) 字内距大丁字间距且字宽小 图2 - 2 字间距影响左右结构手写汉字切分实例 2 相邻汉字间的位置关系复杂。手写汉字的书写可能产生5 种位置关系【4 1 ( 1 ) 相离：汉字各自分丌，如图2 - 3 ( a ) 所示； ( 2 ) 粘连：汉字的某一笔在一点或几点与相邻汉字接触，如图2 - 3 ( b ) 所示； ( 3 ) 重叠：汉字i 日j 无接触，但无法用垂直投影分割线分割，如图2 - 3 ( c ) 所示； ( 4 ) 交叠：两个汉字共享某一部分像素区域，而不仅仅是个别几点相连，如图2 - 3 ( d ) 所示； ( 5 ) 粘连且重叠：粘连与重叠情况并存，如图2 - 3 ( e ) 所示； 由于不规范的书写习惯。手写汉字通常大小不一、宽度变化很大，而且有些人通常 当一个字的最后一笔为撇、捺或横的情况下将该笔画拉长，这样一是导致字宽过宽；二 是容易出现重叠和粘连等现象。通过对大量手写汉字样例的统计分析发现，重叠和粘连 的现象非常普遍，但交叠现象并不常见。 刑鲰锄劬碑 ( a ) 相离( b ) 粘连 ( c ) 重叠 ( d ) 交叠( e ) 粘连且重叠 图2 3 相邻汉字间的位置关系 3 手写汉字的行结构变化多样。 一方面因为在无格式要求下手写汉字的单行通常会出现倾斜，弯曲且各行倾斜、弯 曲的角度、方向不相同，如图2 4 所示，这样用传统的投影方法无法进行整篇文档图像 中手写汉字行的切分；另一方面手写习惯也加大了汉字行切分的困难。经观察统计，多 一5 一 数人在没有横格的空白纸上写字时，当最后笔足竖的情况下会将该笔拉长。这将导致 字过高，甚至出现与下一行的重叠或粘连。 竺7 ! 巴麓维 。：代孽哆 钦的悸十乏和悲k 母孚弓，毋囱己 苎警，望詈登忌弦偏僻里幻饿屋星蓬并：z 泛磊；主芝品 甏蕴穹冬缆，代雀手苇，仅着纪逑如廷缸斋和爱壶：己丢i ： j 手 手儒屯廷么j 、凌吗，代复毕鲫编偏磋茜钓( j 己雨递j 叼 屋依终厦连矸幻缆钩连稃竹萄 f 铆争棒的椎# - p 毫馨 幽。饭言掺量搠l i 】刨氟拍畸仟寿啜的牛，白钲尾于阪如此，氟一 仟j 自，廷薮静和眩厦辽斗 廷稃的，潞甥仿南置埽 争j 置目纾手 够的纠采耘赶待幻想口擘中，一唧卅虎每乏竹焉凰乏白厶葛硅路盼 滴蜩，星是、辑记住 、i 缳缎嚎云毋越簪叨17 迁瓤磊忆峰茜甓 覆。协件唧刎九，7 一切i 己表钟履声，“中7 乏匀孛磊根但是彳王 t 雷垂碍弘? 茛 # 比藏宅亨，量侈，函3 世譬嬲嚣意篙嚣 奄搿置然籀麓拳i ：篇；荔淼忑 肿+ 竺艨：茹嚣：蒜：3 渺! 蠢篡= ：篇箸= 茹：葛 俐雠k ! ：! z ：嚣三= 篡淼+ 椭 榭删脚：竺：兰：篡嚣；三：茹 触埘熏曲警曼：竺嚣荔磊毒互再协调我蒯袍 棚瓢椭杜黑竺竺= ：磊觚鳓吩 身疽身弓1 躬 午i 脏币币吼回1 袅托喁里口工。1 “”。 ( a ) a 人手写样张 ( b ) b 人手写样张 图2 - 4 无格式要求下的手写汉字 2 2 手写汉字切分方法综述 由于汉字结构复杂，所以大多数研究汉字切分的文献已不再采用单一的切分技术进 行离线手写汉字的切分。因为单一的切分技术很难在切分汉字的同时对汉字问存在重 叠、粘连、交叠的现象和汉字内部件过分的问题进行完善处理，现在文献中普遍采用多 步切分法，即先将所有可能的切分点找到，然后根据文本中内含的信息，在这些切分点 中选出真正的切分点，或补充未被发现的切分点，以形成分割线。 离线手写汉字切分过程中切分点的寻找方法主要分为两大类：一是基于解剖分离的 方法；一是基于识别的方法。基于解剖分离的方法也有文献称之为基于字符的拓扑结构 6 第2 章离线下，弓汉字的切分 2 2 1 基于解剖分离的方法 基于解剖分离的方法是根据事先定义的字符高度、宽度、结构信息、笔画走向以及 字符问的距离等特性，来寻找切分点。基于解剖分离的方法中常用的切分技术有投影切 分技术和像素跟踪技术。 1 投影切分技术 投影切分技术产生于2 0 世纪5 0 、6 0 年代，最早被应用于西文字符的分割中，也是 目f j 应用最为广泛的一种切分技术。文献 1 ，3 ，5 ，6 在寻找分割线位置时均采用了投 影的方法。投影切分技术是一种传统、经典的汉字分割技术。其原理是分别对图像点阵 区域进行行( x 轴) 、列( y 轴) 方向上的投影，分别得到横向和纵向的黑像素的统计直 方图，字符点阵区域在直方图上呈现出波峰状，字符间的空隙在直方图上呈现出波谷状。 对图像进行横向投影如图2 5 所示。 x 轴 图2 5 横向投影结果 根据一定的阈值，就可以得到可能的切分位置。设切分阈值为6 ，图像的宽度为三， f 、分别表示图像中各个像素点所在的行号和列号。则具体行切分过程如下：首先根据 工 公式f ( f ) = g ( i ，) ，得到各行的积分投影。然后依据公式f ( f ) 万& & f ( f + 1 ) 万和 = l f ( i ) 万& ，( f + 1 ) 万进行文字行上、下分割线的判断。得到的分割线的位置如图2 - 6 所示。 河北人学1 学硕十。学何论文 璺声像譬壹獬一謦恩毒一晨啤例棚碑蕊i i i 冬是炊拙妞每冬尊仫讦械忝妻簪谢弗苑磊囊 孽伤l 钧因扰可从录i 激刃尸颗浑浑曼墨烛j 烈久 、敏楠钧煳卤吹风桃慰冒柚拙锭玩匀噬磊。 图2 - 6 各行分割线的位置 由图2 - 6 可以看出，由于第三行的倾斜，导致了三四两行之i 、口j 没有切分点，不能形 成分割线。所以投影切分不适用于存在倾斜文字行的文本图像。对纵向投影是进行文字 的字切分，投影结果如图2 7 所示。 窃莩 x 轴 图2 7 纵向投影结果 字切分过程如下：首先根据公式f ( f ) ：兰g ( f ，) ，以行为单位求出各列的积分投 i = d o w n 影。其中u p 、d o w n 分别为文本行的上分割线和下分割线，f 、分别表示图像中各个像 素点的行号和列号，g ( i ，j ) 表示彻像素点的值。然后依据公式，( f ) s & & f ( f + 1 ) s 占和 ，( f ) 占& & ，( f + 1 ) 占分别求出文字的左分割线和右分割线。其中为切分阈值。字间 分割线的位置如图2 - 8 所示。 阳p 火破 叫艮酬醚冒娴涌 图2 - 8 各字分割线的位置 第2 审离线一下了汉字的t - j j 分 由图2 - 8 可以看出，由于该行文字存在重叠和粘连，“激情”“大脑”“淋雨”等字 之间均未能找到切分点，以形成分割线。由此可见投影切分技术对印刷体字符分割线位 置的寻找效果虽然很好，但是对于存在文字行倾斜，文字j 、日j 粘连、重叠等现象的离线手 写汉字很难达到较为理想的切分效果。 2 像素跟踪技术 像素跟踪技术是数字图像处理领域的基本技术之一，它可以利用二值图像的特殊 性，跟踪黑像素得到汉字笔画。像素跟踪技术对于笔画宽度和汉字间的位置都不敏感， 它非常适合无粘连字符切分点的寻找【。像素跟踪技术的典型应用是连通域搜索算法 8 , 2 4 】。另外像素跟踪技术也通常用于笔画提取，如文献 1 0 ，1 1 ，2 2 在进行笔画提取时 均采用了黑游程跟踪算法【2 6 】。该算法的基本思想是：首先从图像中寻找到一条黑游程， 作为笔划的丌始，然后对该黑游程进行逐行跟踪，在当f j 黑游程的下一行左右的一定范 围内，找到所有的黑游程，并根据已有的游程平均宽度和游程直线拟合得到的笔划方向， 确定归入该笔划的黑游程，并确定出下一行的跟踪范围，直到找不到新的游程，跟踪结 束，得到一个笔划。 连通域搜索技术是数字图像处理和分析中的常用技术，有着广泛的应用领域。尤其 在字符分割中，凭着它具有能够将具有重叠关系的连通部件分丌的优势，应用更为普遍。 连通域搜索算法能够获得图像中所有的连通部件，然后将得到的各个连通部件视为切分 假设，作为单个待识别的符号图像。其基本思想是对图像页，自左向右，自上而下扫描， 然后根据当前像素点p 的值以及与其相邻的位于0 、1 、2 、3 位置的像素点( 如图2 9 所示) 的值来判断连通区域。 ol2 3 p 图2 - 9 连通域搜索算法示意图 经过连通域搜索算法找到的切分点形成的分割线结果如图2 1 0 所示。 河北人硕十学何论文 姓名像照瘩舟勺篇像恩焉息珞颠倒彰塥太羊事喃 懋是收脑掘何是埒仫圩采酵瓦雨花谢满地筠然 墼掣因警鼍从铡激雹鞭浑淠噩噩烛j 烈划 珊钧煳吹风毹趔冒釉瓤芯脱萄爱磊。 图2 1 0 连通域搜索算法的切分结果 由图2 1 0 可见，连通域搜索算法虽然能够不受文字行倾斜及汉字间存在重叠等现 象的影响，在手写汉字间形成多个切分位置，但由于切分位置过多，很多字被分成了一 个个不连通的部件，因此还需要对切分位置进行进一步的调整、选择，才能实现对手写 汉字的正确切分。同时由图2 1 0 中的“太单”、“大脑”等词可以看出，单纯的连通域 搜索技术不能解决粘连汉字的切分问题。 2 2 2 基于识别的切分方法 基于识别的切分方法是首先利用前面两节提到的切分方法中的一种来寻找可能的 切分位置，然后依次对可能存在的切分结果进行识别，通过对识别结果的判别来选择最 终的切分点。文献 2 7 - 2 9 均采用了基于识别的切分方法。基于识别的切分方法可以动 态地选择切分点，但对时间和空间的资源消耗较大，另外由于很多汉字是由其他汉字组 合而成，所以存在多分解现象。 2 3 离线手写汉字切分的设计思想与算法 手写汉字识别模块的识别对象是单个汉字图像，因此，实现手写汉字的正确切分是 手写汉字识别的关键步骤。由于手写汉字自由度较大、字体多、结构复杂、相邻汉字间 的位置关系复杂、手写习惯不规范等原因，手写汉字的切分错误已经成为导致识别率下 降的主要原因之一。因此，在分析研究前人的切分方法的基础上，本文通过实验、统计 与分析，针对手写汉字的切分提出了一种新的方法。本文的切分方法主要分为如下五个 一1 0 第2 葶禺线i j f j 汉7 = f 1 勺切分 过程： ( 1 ) 利用连通域搜索算法，得到多个切分单元。 ( 2 ) 根据切分单元的质心坐标对切分单元进行按行聚类，以实现对整篇文档文字行 的切分。 ( 3 ) 逐行合并上、下关系和包含关系的切分单元，然后统计计算切分单元的平均字 宽、字高，字间距，最后依据切分单元的质心、宽度、及与前后切分单元的间 距等信息，计算切分单元的合并可信度并进行多次合并。 ( 4 ) 根据切分单元的宽度和密度进行单、多字的判断。 ( 5 ) 对手写汉字中的粘连现象，应用基于汉字结构聚类和笔画分析的粘连切分算 法，进行粘连手写汉字的切分。 切分过程的流程图如2 1 1 所示。 逐邋域援索得到n 个切分母死 扳幸j 聚炎 l 逐 ，仓并上，一f 、氇翕父系舱切分聱元 计箨切分举元的，节均字瓷、宇岛，! 乒朗弱i 图2 1l 手写汉字切分流程图 1 1 墨_r。fl 河北人学一f ：学硕十学何论文 2 3 1 对连通单元进行按行聚类 通过连通域搜索算法，可以得到多个切分单兀，为了后期识别排版，i 硎1 寸简化对具 有上、下、左、右等结构的切分单元的合并，本文对切分单元进行了按行聚类以实现文 字行的切分。但在聚类之前首先需要进行平均字高、字宽的统计。 设第i 个切分单元的宽度为w i = ，2 ，3 ，其中n 为切分单元个数，按公式 w t 肜2 气厂初步计算平均字宽形，然后选出满足不等式o 8 5 1 5 矽的切分单 兰w 元，设共有川个，继续使用公式2 与r 求出新的平均字宽，如此循环直到不再 发生变化为止。为防止w 出现小范围内得波动，此处限制循环次数为2 0 。 同样，设第i 个切分单元的高度为h ， i = 1 , 2 ，3 ，其中n 为切分单元个数，按 h ， 公式日2 弓f 初步计算平均字宽为h ，然后选择出满足不等式日 ， 1 2 日的切分 兰庇， 单元，设共有1 个，继续使用公式日2 i = l r 求出新的平均字宽，如此循环1 2 次其 中1 2 为实验得出的数据) 。得到平均字宽h 。 得到粗略的平均字高、字宽之后，就可以进行文字行的聚类。聚类步骤如下： ( 1 ) 首先将连通域搜索得到的切分单元，按质心的横坐标从左到右排序，得到切 分单元集合为c 。 ( 2 ) 取出c 中的第一个切分单元口。，因为该切分单元一定是某一行最左侧的切分 单元，所以设口，为第k 行的第一个单元，然后在c 中删除口。 ( 3 ) 以a 。为比较的基准，从c 中按顺序逐一取出所有的切分单元口i 进行比较，如 果符合合并为同一行的条件，则将a 。合并到第尼行，并在集合c 中删除口。 然后将口。作为新的比较基准，再从c 中向后继续寻找符合条件的切分单元， 筇2 章离线手丐汉宁的叨分 直到没有符合条件的切分单元为止。 ( 4 ) 重复执行步骤2 ) 、3 ) ，直到集合c 中没有元素为止。 聚类过程中进行合并的条件如下： ( 1 ) 玑一，+ l 口b _ r i g h ，- - a kr i g h ，l 1 5 木w ( 2 ) 吼一 + k 一鼬一口b 蜘l 1 1 木日 ( 3 ) a k _ r 曲- - a 6 一柚i o 7 宰h ( 4 ) 口。质心的纵坐标与a 。及其前的1 0 个切分单元( 如果不存在，该步不执行) 质心 纵坐标所拟合直线的距离小于o 5 倍的平均字高。 其中g k w 为切分单元口。的宽度，a k _ r i g h ，为切分单元口。的右边界，a b _ 耐，为切分单 元口6 的右边界，为平均字宽；吼。为切分单元口。的高度，吼棚为切分单元吼的下 边界，a 6 为切分单元的下边界，日为平均字高；吼妇和口6 柚分别为口女和a 6 的质 心纵坐标。 经过上述步骤的合并，会出现很多只包含一个或几个切分单元的孤立行，还需要对 这些孤立行进行处理。处理思想为：找出与本行切分单元质心横坐标相差一个平均字宽 的所有非本行的切分单元，然后选择与本行切分单元质心纵坐标差的绝对值最小的切分 单元所在行进行合并。 聚类结果如图2 1 2 所示，( a ) 是对图2 - 6 中文字进聚类的结果，( b ) 、( c ) 是对图( 2 4 ) a 人手写样张和b 人手写样张聚类结果的一部分。图中以实线和虚线区别奇数行和偶数 行。由实验结果可以看出本文设计的行聚类的方法能够适应无格式要求下手写汉字行倾 斜等现象。 四冒稳霸国豳圊圜愚圈造饔鼹嘲斛圈自圃 熬爱溅黼绷德戮舔熬糍黼煎黼戮粼黼骥舔熬 霎黑甲因粤雹圆嚣l 粤耀圆四墟基凰觋露熬图 黼约蠛缀粼蘸罄躺麟戮黼稳夔i ( a ) 行聚类结果一 1 3 霉羔韵烹黧翟篓竺墨曼劁鳓。冯争尉鹈鉴飘黢圈弱。凝陶豳。 詈翼霎黎2 魏 琏曼勰缀厦履建蘸荔漾磊荔蓑篆晶 苎鞫氅翼翻t 圆麓巴霉斟阖翅豳缵魑艇葫奁“谴满“葛善菌：； 缝蠢a 黍蠖鼯蕊麴挚凌绣。粼蔟栾酲孽，编编菘。箍勰聂。赢暴：絮 ( b ) 行聚类结果二 翅粒剿葛幽茏囊圆糊瑷幽翰宙豳隅鍪嬲鹳图鞠黼烈。臌鼢口疆磷翳匿黝鳃一番枣甜 躲毳鬻瓣普篱鬃糕晒复熬麓纭。誊受瞄糍嚣攫缮碰菱巍塞，荔蠡颡麓翮雯蠡鲤嚣酗系惹缫囊 豳遣璺瘦圆督囤丽醯园罄| 圜籍戡四韬曙色豳嘤鲥滋弼田圈园嬲田学塑溜疑观 觐。蕾籀技瘸j ；疆缀翱罐菇酗藩鬟，糍域麓蜒麟黜嗣蹭缆罐，”藩瞄饕砻 豳塑颦田蘑毅潮薅& 匿蓬蘧毽嚣縻翻萤琶疵黥醐雷绍避洒罄漕- 豳礁圄_ 因悬瞎 艇髫裁游鸯香霸瞄暗豹蒺髦涟麓勰嘲滞孽畿旒殪硝臻瑟”囊麒翻罐i 5 鲤裁瓣冶 鼍然! 然罴燃葚嚣竺塞篇三言 瓢霎詈竺：一篡篙盏i 篡篙薹 蜜因。蘑腿豳留团蹈黼豳豳囚豳函藏缝豳斟| 嗵印皑斛闭j 到硝舭删一一 ( c ) 行聚类结果三 图2 一1 2 部分手写汉字样张行聚类结果 - 1 4 第2 幸离线于巧汉字的切分 2 3 2 合并上下关系和包含关系的切分单元 对切分单兀进行按行聚类之后，本文首先对具有上、f ，包含关系的切分单兀进行 了合并。因为在同一行中，具有上、下，包含关系的切分单元应该属于同一个字，所以 合并策略相对简单。具有上、下，包含关系的切分单元的合并过程如下： ( 1 ) 从左向右检测相邻两个切分单元口j 、口，如果仉一。+ k 。一倒，一a i _ 恸，i s 1 2 木w 并且| 口f 一。一。一麒i 鱼茅，一c 形，或者口川一材 纪一憎，贝。合并。 ( 2 ) 从右向左检测相邻两个切分单元a ，、口， 如果 艮u + a i _ r i g h t a i - ir i g h t 陋木并且l a i - i _ x x - a i _ x x l 等木，或者 a h 。 a f 枷，则合并。 ( 3 ) 万值自加，重复执行步骤( 1 ) 、( 2 ) ，直到万大于5 为止( 万初值小于5 ) 。 其中a i _ w 为切分单元口，的宽度，a i 哪，为切分单元口，的右边界，a i + l _ 蚴，为切分单 元口川的右边界，形为平均字宽；a ，。和以川。分别为a i 和a 川的质心纵坐标。 经过上述合并过程之后对文字行进行从上到下的排序。然后再次统计平均字宽。这 时得到的平均字宽相对较为准确。平均字宽的统计过程如下： 设第i 个切分单元的宽度为i = j ，2 , 3 ，其中为切分单元个数，按公式 2 气r 初步计算平均字宽为矿，然后对切分单元按从大到小排序，去掉最大的0 【个 切分单兀( 此处主要考虑到粘连汉字的影响，为了，使统计的字宽不会因受其影响而过 大) ，选择出满足不等式0 8 5 xw w f 1 5xw 的切分单元，设共有m 个，继续使用公 n i w 式矿2 弓f ，求出新的平均字宽，如此循环直到形不再发生变化为止。为防止形出现 小范围内的波动，此处限制循环次数为1 2 。 河北人。l 。顾t “? ；0 f p 论文 2 3 3 合并左右关系的切分单元 在对左右关系的切分单元进行合并之自i 首先需要求出平均字问距。根据切分单元质 心的横坐标对切分单元逐行从左到右排序，逐行对相邻切分单元求取距离和，求出平均 值作为平均字i 、日j 距。然后通过计算合并可信度来实现切分单元的合并。 合并可信度的初值如表2 1 所示。设字宽为w ，本文将o 4 半w w 0 6 木w 的切分 单元看成最有可能与其f j i 或后的切分单元进行合并的切分单元，因此其初始合并可信度 厂定为o 5 ；将w 0 4 水w 的切分单元看成某个汉字的偏旁、部首或是标点符号，因此其 初始合并可信度r 定为o 3 ；将0 6 术w 1 4 0 8 木w 的切分单 元看成独立的汉字，因此其初始合并可信度r 定为0 。 表2 1 合并可信度初值计算表 a 字宽 w 0 4 牛w0 4 幸w sw 0 6 孛w0 6 w9 俨：o 8 w脸0 8 宰w b 字宽 w 0 4 宰wo 3o 80 60 5 0 4 * wsw 0 6 宰w0 80 50 4o 0 6 宰w5w 0 8 幸w0 5000 一个切分单元与其他切分单元合并可信度的计算除了与初值有关之外，还与它们的 宽度和字间距以及质心横坐标差的绝对值有关，具体的计算过程如下：首先提取处于同 一行的切分单元，然后从第二个切分单元开始，依次计算与其相邻的两个切分单元的合 并可信度。设将要合并的切分单元为彳，其相邻切分单元为z 矿为平均字宽，aw 为 切分单元彳的宽度，xw 为分单元x 的宽度，印为a 与x 的字间距，铲为平均字间 距，ax 和xx 为切分单元么和x 的质心横坐标。 合并可信度的计算过程如下： 第2 章离线于下了汉字f n 切分 ( 1 ) 如果a w 0 4 木w 当x w 0 4 木w 时，如果彳一w + x w + 印 0 8 5 木w & & s p s p 半0 6 ， 严什0 2 ；如果a b s ( a 一石一x x ) 0 5 木w ，严什0 5 。 当o 4 半w = x w 0 8 宰时，如果a w + x w + s p = w ，严什0 3 ；如 果印 0 2 木铲，f 一0 3 ；如果a b s ( a 一石一x z ) 0 5 木w ，严什o 3 ；如 果么一w + x w + 印 w & 印 = 0 8 木w 时，如果a w + x w + s p = w ，严一o 5 ；如果 彳一w + x w + 驴 1 2 术w & & a b s ( a x x x ) 0 5 宰，严一o 5 ；如果 s p 0 4 木胆，产什o 5 。 ( 2 ) 如果0 4 木w a w 0 6 术w 当x w o 4 术w 时，如果a w + x w + 印 矿， f o 1 ；如果 印 0 2 木s p ，产一o 1 ；如果a b s ( a 一石一x x ) 0 5 枣w ，严一0 1 ；如果 么一w + 石一w + 印 0 8 木w & & 印 铲木0 6 ，严什o 1 。 当o 4 事w = x w o 6 木w 时，如果a w + x w + s p = w ，尸件o 3 ； 如果印 0 2 ，i c 印， 严什0 3 ； 如果a b s ( a x x x ) 0 5 木w & & 么一w + x w + s p - 1 1 5 木w ，f 什o 3 。 当o 6 木w - x w 0 8 木w 时，如果彳一w + x w + s p - w ，严一o 5 ； 如果印 0 3 木s p ， 产什o 5 ； 如果a b s ( a 一石一x x ) 0 5 堆w & 彳一w + x w + s p _ 1 2 术w ，产什0 5 。 ( 3 ) 如果0 6 * w _ a w 0 8 木w 当o 6 木w - a w 0 8 木w 时，如果a w + x w + s p = 1 2 木矿， 一1 7 河北人学i ：学硕p j o f 节论文 严什o 5 ；如果印 0 2 木s p ，f 什o 5 ；如果a b s ( a x x x ) 0 5 木形， 严， + 0 5 。 合并过程如下： ( 1 ) 提取属于同一行的所有切分单元； ( 2 ) 依次合并合并可信度最火的相邻切分单元； ( 3 ) 重复1 ) 、2 ) 直到没有可合并的切分单元为止。 实验结果显示，本文的合并方法对没有粘连现象的离线手写文档图像能够达到较为 理想的切分效果。但由于仍然不能处理手写汉字中的粘连情况，所以对于带有粘连的离 线手写文档图像的处理效果还不够理想。如图2 1 3 所示，因此本文特别针对手写汉字 的粘连情况提出了一种基于结构聚类和笔画分析的粘连手写汉字的切分算法。该算法的 详细内容将在下一章中介绍。 圆圈圜网图困园圆圈圈圆圈圆囫圜圈圃 困团固园圃团圆圆圈豳因园团圃圈圃园图 图2 1 3 切分结果示意图 匹i园因固汹 圉皿匪烟匪阍雕竭 豳区 雕烟 嘲圊 龇困因翊麴嘲 酬捆醚姻 鳓圜 第3 章半生于，弓汉宁的切分 第3 章粘连离线手写汉字的切分 粘连手写汉字的切分是离线手写汉字切分中的难点，也是亟待解决的问题之一。因 为据统计，离线手写汉字中存在大量的粘连现象。根据粘连方向的不同可分为左、右粘 连和上、下粘连。根据粘连点数的不同可分为单点粘连和多点粘连。单点粘连是指只有 一个点发生粘连的情况，将来做切分的时候只需要一条分割曲线；多点粘连就是有多于 一个的点发生了粘连，也就是说将来做切分的时候需要一条以上分割曲线。根据手写习 惯的不同分为连笔粘连和搭接粘连。连笔粘连是由连笔笔画产生的两个汉字的粘连；搭 接粘连是由汉字笔画书写不规范或两个汉字距离太近产生的汉字笔画搭接现象。各种粘 连现象如图3 1 所示。 图3 1 手写粘连汉字示例 3 1 粘连手写汉字切分方法综述 目前国内外针对手写汉字粘连情况所设计的切分技术也有很多，其中典型的有如下 几种：一是本文第二章中提到的投影切分技术，由于在很多情况下，两个相邻手写汉字 之间存在较大的背景区域，即包含的黑色像素较少，所以该技术常被用于寻找黑色像素 点较少的候选切分区域。由于投影切分技术在本文第二章已经详细介绍过，因此不再赘 述。二是应用滴水算法的粘连切分技术【3 0 - 3 2 1 ，滴水算法主要是用于寻找蓄水池( w a t e r r e s e r v o i ) 的池底。所谓的蓄水池【3 2 】可以认为是背景区域中，当水流灌入字符串时，由于 水流遇到字符连接部分的阻拦，而在字符轮廓的“瓮底”部位蓄积形成的水洼，水流由上 河，1 1 ：人学1j 。、：乇硕十、何沦文 向下灌入所形成的水沣称之为上蓄水池。由下向上灌入形成的水洼，称为下蓄水池。滴 水算法的决定因素主要包括：滴水的起始点、水滴的移动规则以及水滴移动方向。由于 这些因素的不同，滴水算法有很多不同的变种。但是滴水算法更适用于手写数字、字母 的粘连切分，对于笔画繁多、结构复杂的手写汉字不太适合。 目前，在汉字信息处理的应用领域，国内的许多专家学者也研究出了很多非常有效 的切分方法，并且在实际的样本处理中取得了许多非常满意的效果【3 3 1 。 马少平等人3 4 。3 5 】运用背景细化的方法在高斯混合分类器上取得了8 8 6 的j 下确率。 魏湘辉等人【3 4 】针对粘连汉字提出的基于凸包像素比的粘连汉字切分方法较好的实现了 粘连汉字的切分。赵宇明【3 6 。3 7 】等人运用自适应的算法改进了目前投影和结构信息分割粘 连汉字方法的不足，有效地处理了非限定手写汉字字形变化大的问题，提出的用于粘连 手写体汉字切分的二次寻点算法和基于笔画分析和背景细化的粘连手写汉字切分，