（计算机应用技术专业论文）手写体汉字识别技术的研究与实现.pdf

摘要 摘要 脱机手写体汉字识别是一个典型的大类别模式识别问题，汉字的识别与处理 对我们国家在信息时代的竞争力起着特殊重要的作用。 本文以脱机手写体汉字识别方法为研究内容，完成了以下几个方面的工作： 1 预处理方面，实现了传统的二值化、平滑、细化和归一化算法，提出了一 种改进的手写体汉字细化算法，改进了一种基于汉字整体密度均衡的非线性归一 化方法。 2 特征提取方面，实现了方向象素特征和区域投影特征的提取。 3 分类器设计方面，实现了一个基于多重隐马尔可夫模型的多分类器系统， 该系统提取基于区域投影变换形成的边界链码特征，并采用四组h m m 对一个汉 字建模；实现了一种增强隐马尔可夫模型区分力的方法一一基于h m m 的反向传 播训练算法。 关键词：手写体汉字识别归一化处理特征提取隐马尔可夫模型神经网络 垒堕竺! ! 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 n ( h c c r ) i sat y p i c a ll a r g e v o c a b u l a r yp a t t e r nr e c o g n i t i o np r o b l e m t h er e c o g n i t i o na n dp r o c e s so fc h i n e s e c h a r a c t e ri so f g r e a ti m p o r t a n c ei nt h ec o m p e t i t i o no f o u rc o u n t r yi ni t t h ed i s s e r t a t i o ni sd e n o t e dt oo 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 t h ew o r ki nt h ef o l i o w i n ga s p e c t so f t h er e s e a r c hf i e l di sp e r f o r m e d 1 i nt h es t e po fp r e p r o c e s s i n g ，t r a d i t i o n a lt h r e s h o l d i n g ，s m o o t h i n g ，t h i n n i n ga n d n o r m a l i z i n gi si m p l e m e n t e d a ni m p r o v e dt h i n n i n ga p p r o a c ho fh c c r i sp r o p o s e da n d an o n l i n e a rn o r m a l i z a t i o na p p r o a c hb a s e do nw h o l ed e n s i t ye q u i l i b r i u mo fc h i n e s e c h a r a c t e ri si m p r o v e d 2 i nt h es t e po ff e a t u r ee x t r a c t i o n ，d i r e c t i o nv e c t o rf e a t u r ea n ds u b 。r e g i o n p r o j e c t i o nf e a t u r ea r e e x t r a c t e d 3 i nt h es t e po fc l a s s i f i e rd e s i g n ，am u l t i p l ec l a s s i f i e rs y s t e mb a s e do nm u l t i p l e h i d d e nm a r k o vn l o d e li sp e r f o r m e di nt h et h e s i s ，a n df e a t u r eo ft h ec o n t o u rc h a i nc o d e s b ys u b r e g i o np r o j e c t i o nt r a n s f o r mi se x t r a c t e d f o u rg r o u p so fh m m a r ec h o s e nt o b u i l df o ro d ec h i n e s ec h a r a c t e r , ab a c k p r o p a g a t i o nt r a i n i n ga l g o r i t h mb a s e do nh m m i sp e r f o r m e dt oi m p r o v et h ed i s c r i m i n a t i o no f t h eh i d d e nm a r k o vm o d e l k e y w o r d s ：h a n d w r i a 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 n o r m a l i z a t i o n f e a t u r ee x t r a c t i o nh i d d e nm a r k o vm o d e l n u e r a ln e t w o r k y 5 8 3 4 3 1 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：盘挞冀同期金塑垒：墨： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名：煎熬墓 导师签名：錾丛生日期垒! ! 兰1 j l 墨 第一章绪论 第一章绪论 文字是人类信息交流的主要载体。随着计算机、信息技术的高速发展，使用 计算机处理并识别人们的文字信息也就成为了一个非常重要的研究领域。文字识 别技术“是指用计算机自动、高速地辨识写在纸( 或介质) 上的数字、英文符号 或汉字，是模式识别的一个重要分支，它涉及模式识别、图像处理、数字信号处 理、人工智能、模糊数学、信息论、计算机等学科，是- i 7 综合性技术。 1 1 研究汉字识别的目的和意义 当今社会是一个网络四通八达、资源高度共享、信息传播迅速的信息社会。 为满足资源共享、信息传播的需要，大量的中文信息都需要在计算机上进行处 理。目前，计算机上的中文信息处理系统，可以让人轻松愉快地对输入的中文信 息进行处理。然而汉字录入的困难制约着系统的效率，已经成为一个亟待解决的 “瓶颈”问题【4 j 。汉字识别的研究与开发，无疑将满足人们对高速自动输入汉字 的强烈要求，它在办公自动化、印刷业、信息传播等方面都有着广泛的应用前 景。 汉字识别是- - 1 3 多学科综合的研究课题，是模式识别的热点和难点。它不仅 与人工智能的研究有关，而且与数字信号处理、图像处理、信息论、计算机科 学、几何学、统计学、语言学、生物学、模糊数学、决策论等都有着千丝万缕的 联系。一方面各学科的发展给它的研究提供了工具，另一方面，它的研究与开发 也必将促进各学科的发展。因而，汉字识别有着重要的理论意义。 1 2 汉字识别的研究范围 汉字识别的研究范围可以用图1 1 所示的三维空间卧1 】来描述，它包括对各 类不同字体的各种识别方法研究：在不同文字版面质量和数量要求下的相应识别 方法研究等，具体而言，即： 按汉字的类型，汉字识别的研究内容有联机手写体汉字识别、单体印刷体汉 字识别、多体印刷体汉字识别、脱机手写印刷体汉字识别、脱机手写体汉字识别 等； 按文字和版面的质量，文字识别可包括高、中、低三级； 按文字数量和版面的复杂程度要求，汉字识别方法包括一级( 3 7 5 5 字) 、二 级( 6 7 6 3 字) 、三级( 1 0 0 0 0 字) 的识别和简单、中等、复杂三种版面的识别。 显然，离开原点愈远，研究的难度愈大。 手写体汉字识别技术的研究与实现 义7 类型 原点 脱机下q 体 脱机手写印刷体 多体印刷体 单体日j 刷体 联机手写体 文字版面质量 一量。客一一 图1 1 汉字识别的研究范围 1 3 汉字识别的应用领域 汉字识别研究介于基础研究和应用研究的边缘，它的研究对加速建立汉字信 息库、汉字信息处理系统全自动化以及实现新一代计算机的智能输入都有重要意 义，主要体现在以下几个方面： 第一，建立中文资料库，包括图书馆的资料输入。建立中文资料库时，需要 大量输入各种各样的中文书籍、杂志和报刊中文信息，使用中文o c r ( o p t i c a l c h a r a c t e rr e c o g n i t i o n ) 系统，可以实现文字的自动输入，缩短建立文字资料库的时 间，大大节约人力物力。 第二，办公自动化和情报检索。 第三，智能计算机汉字智能接口的重要组成部分。 第四，自动阅读机和盲人阅读机。将中文o c r 系统与语音合成系统结合起来， 能够形成自动阅读机或盲人阅读机。 1 4 汉字识别的发展概况 早在本世纪六十年代，人们就开始了对印刷体汉字识别的研究工作。最早对 印刷体汉字识别进行研究的是i b m 公司的c a s e y 和n a g y l 2 。1 9 6 6 年他们发表了 第一篇关于汉字识别的文章，用模板匹配法识别1 0 0 0 个印刷汉字。1 9 7 7 年，日本 东芝综合研究所研制出能识别2 0 0 0 个印刷体汉字的实验装置：1 9 8 3 年东芝研究中 心又进行了对限制性手写体与印刷体汉字识别兼容的研究工作m 。 第一章绪论 3 七十年代术，我国开始了对汉字识别的研究。1 9 8 5 年，南通电子所研究出能 识别两种字体1 8 0 0 个单字的识别方法：1 9 8 6 年，清华大学计算机系和沈阳自动化 所先后研究出能识别3 7 5 5 个印刷体汉字的实验系统；1 9 8 6 年1 1 月，清华大学的 朱夏宁等研究的能识别6 7 6 3 个印刷体汉字的汉字识别试验系统通过了技术鉴定； 1 9 9 2 年清华大学的许宁在博士学位论文中，提出了一种基于“人工神经网络”方 法的印刷体汉字识别方法1 4 j 。目前对于印刷体汉字识别的研究工作已经趋于成熟， 已有一些实用系统在市场销售。如清华文通、曙光o c r 、汉王o c r 等。 进入9 0 年代，国家教委基础研究与高科技司和国家“八六三”高科技计划智 能计算机主题专家组为了了解我国汉字识别的水平，于1 9 9 1 年、1 9 9 2 年和1 9 9 4 年先后召丌了三次汉字识别和汉语语音识别评比研讨会。1 9 9 0 年以来，在“八六 三三”资会的支持下，通过检查、评测以及在市场的激烈竞争中，我国的印刷体汉 字识别系统的主要性能指标有了新的突破，在商品市场中逐渐完善，识别系统进 入大发展的阶段。相应的测试结果请参看文献【5 j 。 在印刷体汉字识别的发展基础上，我国的手写体汉字识别技术也取得了很大 的突破。有关手写体汉字识别研究成果层出不穷，据统计，目前脱机手写体汉字 识别的正确识别率基本上在8 0 9 0 。中科院自动化所在9 6 年推出的特定人脱机 手写体汉字识别系统，正确率达9 3 6 ，代表目前手写体汉字识别的最高水平。 但是，脱机手写体汉字识别的问题还远未解决，或者说，距离问题的解决还 有很长的路要走，最终问题的解决取决于能否在理论上和实践中找到将统计识别 方法和结构分析方法有机结合起来的途径和方法悼l 。 1 5 汉字识别的问题和困难 和所有模式识别系统一样，汉字识别的主要性能指标是正确识别率、识别速 度：从实用角度看，还应考虑系统的复杂性、可靠性和价格1 2 ，6 。7 】。 对识别系统识别率和识别速度的要求，很难有一种统一的、严格的标准，主 要是根据实际应用的需要来确定。但是，作为一种输入手段，汉字识别系统的性 能应该和其它输入手段( 如人工键盘输入) 相比拟，在某些特殊的应用场合，对 识别系统的要求还应更高。 要达到上述要求是相当困难的，这是因为，从技术上讲，人们关于模式识别 的研究虽已有较长的历史，但迄今仍没有能够全面地适用于分析或描述各种模式 的严谨的理论。在研究某一种模式识别问题时，有的方法比较巧妙，或者说，某 种识别方法较符合被识别的模式集合的情况，因而得到较好的结果，但是该方法 应用于另种模式集合却可能获得很不理想的结果，因此，所研究的某一种方法 往往因其只适合于某些限定的情况，而呈现出某种局部最佳性而非全局最佳。从 4 手写体汉字识别技术的研究与实现 客观上说，汉字是一种特殊的模式集合，这种集合的模式种类( 汉字字数) 很多、 结构复杂，而且有的模式十分相似，加上印刷质量以及其它干扰因素的影响，人 们在书写时的随意性、字形不够规范等，都使正确识别十分困难。汉字识别的问 题和困难，更大程度上体现在汉字集合本身所固有的一些特点上。 首先，汉字字符集数量大。我们常用的汉字有3 0 0 0 4 0 0 0 个，国标g b 2 3 1 2 8 0 字库共有汉字6 7 6 3 个，但是受到识别方法的局限，对某一待识字进行识别时，一 般必须将该字和字典模式库中的字进行比较，找出其中最相似的字。这样，对于 大字符集的识别速度就必然较低。为提高速度，常采用树分类，即多级识别方法， 但相应地就会使识别率下降。这是正确识别率和识别速度的矛盾，同时也是汉字 识别的主要困难。 其次，汉字的字体多。印刷体有宋体、仿宋体、黑体、楷体等字体，手写体 则有楷书、行书和草书等三大类。对印刷体汉字，不同字体的同一个字的字形点 阵亦不相同；对于手写体汉字，这种差别就更大。因此，计算机进行自动识别时， 很难将不同字体的同一个字，用一个参考汉字来比较、判定，这样，为适应对各 种字体的识别就必然会使得汉字识别的字典模式库的规模变得十分庞大。 第三，汉字结构复杂、字形相似。汉字笔划最多的有3 6 划，平均每个汉字笔 划为1 i 划。由于笔划多，所以有的汉字结构十分复杂，有的字虽然笔划较少，但 字形却十分相似，如“人、入”、“土、士”、“鸟、乌”、“己、己、巳、乙”、“太、 大、犬”等。这些字只有一点之差，或者某一笔划长短略有差别，其意义就迥然 不同。这些都是汉字识别方法的研究中必须考虑的。 1 6 本文的主要工作 本文以脱机手写体汉字识别方法为研究内容，完成了手写体汉字识别研究领 域中的以下几个方面的工作： 在预处理方面，实现了传统的二值化、平滑、细化和归一化算法；提出了一 种改进的手写体汉字细化算法，有效改善了细化效果；改进了一种基于汉字整体 密度均衡的非线性归一化方法，矫正效果较好。 在特征提取方面，实现了方向象素特征和区域投影特征的提取，实验结果表 明提取到的特征兼顾了提取方法的方便性和特征的稳定性，能有效地识别手写体 汉字。 在分类器设计方面，首先实现了一个基于多重隐马尔可夫模型的多分类器系 统，该系统提取基于区域投影变换形成的边界链码特征，采用四组h m m 对一个 手写体汉字建模。手写体汉字识别实验结果证实，该方法有效提高了识别率。接 着实现了一种增强隐马尔可夫模型区分力的方法一一基于h m m 的反向传播训练 第一章绪论5 算法，陔算法应用多层前向神经刚络的结构来实现隐马尔可夫模型前向概率递推 计算，通过梯度上升的优化过程来实现互信息最大化的、增强隐马尔可夫模型区 分力的训练方法，通过反向传播的方法计算互信息的梯度变化。手写体汉字识别 实验表明，基于该算法构造的手写体汉字识别器的性能要优于基于传统的 b a u m w e l c h 参数估计方法的。 本文的文章结构组织如下： 第章是奉文的概论部分，介绍了汉字识别的研究意义、应用领域、发展概 况、问题与困难等。 第二章实现了传统的二值化、平滑、细化和归一化算法，提出一种改进的手 写体汉字细化算法，并改进了一种基于汉字整体密度均衡的非线性归一化方法。 第三章分析汉字的属性及统计特性，提取了方向象素特征和区域投影特征。 第四章实现了一个基于多重隐马尔可夫模型的多分类器系统。 第五章实现了一种基于h m m 的反向传播训练算法，优化了隐马尔可夫模型 的区分力。 第六章结束语。 6 手写体汉字识别技术的研究与实现 第二章手写体汉字识别的预处理 在待识别的手写体汉字图像中含有各种各样的噪声和畸变，去掉这些噪声和 畸变，并将图像变成标准形式，使得特征的提取和字符的识别变得容易进行，这 些处理称为汉字识别预处理。预处理是汉字识别十分重要的一步，预处理工作做 得好，使反映汉字本质特征的部分得以保留，识别就容易进行，识别率高且识别 速度快。反之，就会使识别变得困难，甚至造成误识等不良后果。 预处理阶段主要包括二值化、去噪滤波、归一化、细化等几个部分。 2 1 二值化 把汉字图像灰度数字信号处理成二值( 0 , 1 ) 的数字信号，称为汉字图像的二值 化。设原始的灰度汉字图像为f ( x ，y ) ，x = l ，2 ，x ；y = 1 ，2 ，y ，那么在选取了一 个灰度闽值r 后，令灰度值比r 值大的图像象素( 背景点) 为“0 ”，令灰度值比丁 值小的图像象素( 前景点) 为1 。即 如，_ y ) ： 1 馔：川，2 ，以y _ 1 ，2 ，y ( 2 - 1 ) g ( 石，y ) 2 1 0 ，( x ，y ) 丁x 2 i ，2 ，。一，爿；y 2 1 2 ，一，1 1 ) 便完成了汉字图像的二值化。 二值化的关键在于门限值t 的选择，文献1 1 介绍了三种二值化方法，根据实际 需要，本文选择了整体闽值二值化方法。 整体阈值二值化方法是指在二 值化过程中只使用一个阂值r 的方 法。丁值可以根据先验知识预先设 定，也可由图像直方图确定。 灰度直方图实际上是图像中不 同灰度级的灰度占有概率。如果图 像的灰度直方图具有双峰形分布0 时，我们就可以自动地确定二值门 y 5 八 x 圈2 1 双峰型灰度直方图 限7 _ 。汉字图像的直方图( 见图2 1 ) 一般有两个峰值，一个峰值对应汉字的笔划 部分，另一个峰值对应汉字的背景部分，选取两个峰之间的谷底处的灰度值作为 门限，就能较好地二值化汉字图像。 整体阈值方法优点在于算法简单，只需要一次计算阈值。对于目标和背景明 显分离、直方图呈双峰分布的文本图像，整体闲值方法可收到很好的效果。但在 第一章手写体汉字识别的预处理 7 文本图像直方图双峰特性不明显时，整体闷值方法应用受到很大限制。 2 2 平滑处理 平滑处理的同的是为了减少笔划的边缘噪声、删去孤立点、填充孤立的空洞， 以期在细化中得到更好的效果。噪声的产生是由多种原因造成的，如扫描仪本身 的问题、纸张的质量、书写的压力以及笔的类型等。 n j 盯、 ”5p胛i 饩 九， 胛8 这里采用u n g e r 提出的平滑算法9 3 ，设有3 x 3 窗口如左所 示。 其中p 为当前点，一。愧为其八个邻域点，平滑准则为： ( 1 ) 当p 为0 ( 背景点) 时，肝l ，b ，”，和月，中至少有三个元素为 l ( 前景点) ，则将p 改为1 ，n p 不变； 幽2 2 象素p 的邻域( 2 ) 当p 为l 时，如果 一、n 2 和传中至少有一个为l ，同时 、体和n ，中至少也有 一个为1 口不变，否则改为0 ； 心、”。和n ，中至少有一个为1 ，同时”，、和m 中至少也有一个为1 ，p 不 变，否则改为0 。 平滑处理使用9 个3 3 的窗口模板，“1 ”表示前景点，“0 ”表示背景点，x 表示此点不必考虑，可为“1 ”，也可为“o ”，如图2 4 所示。 、ox 01 。lx x1 1o1 x1 000 0lo 。x ( b )( c ) 图2 3 平滑窗口模板 图2 3 ( a ) 、( b ) 表示若当前点为0 且与模板匹配时，则把当前点置为“l ”， 即填充笔划边缘的凹陷噪声；图2 3 ( c ) 表示若当前点为1 且与模板匹配时，则 把当前点置为“0 ”，即删除笔划的凸起噪声，当3 个x 都为0 时，删除的是孤立 象素点。图2 3 ( a ) 和( c ) 都是对笔划的上边缘进行平滑处理，将模板旋转9 0 0 、 1 8 0 。、2 7 0 。，即可对右、下、左边缘进行平滑处理。图2 3 ( b ) 是填充笔划内部 的空洞，不必旋转。平滑处理时，对汉字点阵从上到下，从左到右扫描每个象素 点，与9 个模板匹配，一次完成。 8 手写体汉字识别技术的研究与实现 2 3 细化处理 细化又称为骨架化，是指在不改变图像象素的拓扑连接关系的条件下，连续 擦除图像边缘象素，使之最终成为一个象素宽度的图像骨架。 现有的很多细化算法都或多或少会出现一些拓扑结构改变，如y 形分叉、笔 划变短、毛刺和断线。这是由于仅靠一个有限的n 珂窗口是无法决定一些点的取 舍的，而精细地描述一个汉字却需要全局信息“。本节实现了模板匹配法f p a 和 s p t a 细化算法，提出一种快速h i l d i t c h 并行模板细化算法，该算法以经典h i i d i t c h 算法为基础，为提高细化速度将之转化为并行算法1 ，并考虑到手写体汉字书写 的一些习惯、特性，引进了一组删除模板和一组保留模板。 2 3 1 快速并行算法( f a s tp a r m l e la l g o r i t h m ) 一- - f p a 算法“ 针对二值化汉字图像中的任一象素，选取3 3 的窗口进行判断，如图2 4 。f p a 方法逐层剥去汉字笔划外围黑象素而保留属于骨架的象素点。为了保证骨架的 连续性，该算法将每次处理分为两次子处理： 、s t n o n h 玛 凡 ( i 一1 ，一1 ) ( i - l ，j ) ( f 一1 ，_ ，+ 1 ) 传p肝【 ( f ，j 1 )( f ，)( f ，j + 1 ) 忾 m “+ 1 ，j - 1 )( f + 1 ，j )( f + l ，j + 1 ) s o u t h 图2 4f p a 算法的匹配模板 第一次子处理：从东南边界和西北角进行擦除，满足式( 2 2 ) 中( 口) 、( b ) 、( c ) 、 ( d ) 的点为可删除点； 第二次子处理：从西北边界和东南角进行处理，满足式( 2 2 ) 中( 日) 、( b ) 、( c ) 、 ( d ) 的点为可删除点； 反复进行这两项子处理，直至没有可删除的点为止。 第二章手写体汉字识别的预处理9 ( a ) 2 b ( p ) 6 ( 6 ) 一( p ) = 1 ( c ) ”+ 盯，+ 竹，= o 【( d ) h i n 5 月7 = 0 式中，爿( p ) 表示，n 2 ，_ 序列中0 1 对出现的个数，而b ( p ) 是p 的八邻 域窗口中1 的个数。条件( 口) 保证骨架端点不被删除，条件( 6 ) 保证骨架中的点不 被删除，如图2 5 所示。条件( c ) 、( d ) 保证了只删除东南边界和西北角的不属于骨 架的点：条件( c ) 、( d ) 则保证只删除了西北边界和东南角的象素点。 0 0 000 0 o0o 0ll l11 1 l0 图2 5 骨架点的保护 2 3 2s p t a 细化算法( s a v ep o i n tt h i n n i n ga l g o r i t h m ) 一s p l l a 算法“4 1 与f p a 算法一样，s p t a 算法也采用了3 3 窗口判断可删除的象素点，分别从 上、下、左、右四个方向对笔划进行细化“。 细化过程中考虑以黑象素为中心的3 x 3 窗口，如图2 2 所示，窗口中的八个邻 点是决定该点可删除性的序列，记为g ， g2 啊，2 ，n 3 ，n 4 ，n 5 ，n 6 ，1 7 ，傀， 如果序列q 满足图2 6 中( a ) 、( b ) 、( c ) 、 ( d ) 中间的任一种情况，则对应的点分别是右 边界点、上边界点、左边界点和下边界点。 算法根据下面的布尔函数来判定是否为 可删除点。 图2 6s p t a 算法的判断窗口 0 ) s o = n s ( n 6 + 月7 + 坞+ ) ( 码+ 心) ( 愧+ n 4 ) ( 6 ) 只。n o ( r l i + 心+ + ”7 ) ( 月2 + n 3 ) ( n 6 + 传) ( 2 3 ) ( c ) & = 件( ，+ 1 1 + 1 5 + 1 6 x r + 1 2 ) ( n j + ) ( d ) & = n 3 ( n 4 + ，屯+ 啊+ 1 2 ) ( 1 ，+ 1 6 ) ( 1 i + 愧) 这里仅以右边界点的删除判断为例说明细化判断过程，对右边界点，就是符 合图2 6 中( 口) 模板的p 点，即传，p + 啊= 1 的p 点，若式( a ) 为0 ，则为不可删除 点。布尔表达式中相应象素为黑且未被标记的点的布尔值为1 ，否则为0 。 同理，对左、上、下边界点的表达式分别如上面的( b ) 、( c ) 、( d ) 式。 s p t a 算法一般需要经过数轮相同的检查过程，每一轮都由两次扫描组成，每 一 口 o o i = 7 ” + ， 也肝 $ 3 仇行 ) ) f d ( ( ，：l 0 手写体汉字识别技术的研究与实现 次扫描检查图像的每个象素。扫描过程可以是逐行的，也可以是逐列的。第一次 扫描检查所有的左、右边缘点，如果是可删除点则被标记；第二次扫描检查所有 的上、下边缘点，如果是可删除点则被标记。当结束一轮扫描后，没有一点被标 记，则删除所有被标记的点，算法结束，否则进入下一轮扫描。 2 , 3 3 快速h i d i t c h 并行模板细化算法 该算法以经典h i l d i t c h 细化算法为基础，经典h i l d i t c h 细化算法是一种充分利 用连接数，的基本串行算法】。首先将其转化为并行细化算法，如图2 7 所示， 其中点2 表示可删除点，点3 为确定删除点。 在此算法中，目标象素p 若同时满足以下条件即为可删除象素( 点2 ) 。其8 一邻域同图2 2 ，设k = l 2 ，8 ，则： ( 1 ) k 1 ：非端点； i ；i 8 ( 4 ) d = 1 一+ 。i = 2 ：d 2 为8 - - 邻域中0 1 对出现的个数 k = l 其中，仇= i - ，n 9 = n z 。 输入二值图像( 点1 ) i 里望竺皇! 皇! ! l 从边缘点中排除端 点f 点2 一 点3 1 通过四个循环删除点3 避华虬 是i 图2 7h i l d i t c h 并行细化算法流程图 上述判断条件检测不到“l ”、“v ”形状的笔划拐弯处的点，这会导致沿中心 骨架各方向的细化速度不一样，使得细化后笔划拐角变钝乃至变形。为此在上述 算法中引入删除模板，用于检测二值图像中该删而未删的象素点，并将其 j a , k 可 第二二章手写体汉字识别的预处理 删除候选集中，如图2 8 所示。 因此提出8 个l 模板，如下删除模板( a ) ，以及将之旋转厅2 、厅和3 n 2 后 得到的模板及其4 个镜像模板，共8 个：v 模板有8 个，如下图2 8 ( b ) 所示， 以及将之旋转7 r 4 、x 2 、3 1 ：4 及其4 个镜像模板：为避免细化后的骨架线是双象 素宽的情况，又提出了模板c 以及将之旋转汀2 、万和3 r c 2 后得到的模板；为抑 制单象素引起的噪声骨架的生长，提出了模板d 以及将之旋转z 2 、万和3 x 2 后 得到的模板，可在一定程度上克服细化产生伪笔段的缺陷。至此共计2 4 个删除模 板，如下图( a ) ( b ) ( c ) ( d ) 所示，“+ ”表示该点的象素值大于1 ，“妒表示不 为1 ，x 表示可为任意值，0 表示其象素值为0 。 xxx xx oo+ x + plx xlxx xxx +0 +x x + xx xxplx xx1xx x x ( a ) l 模板( b ) v 模板 盟田园 ( c ) 去除双象索模板( d ) 抑制生长模板 图2 8 删除模板 图2 9 保留模板 上述细化算法若单独使用会导致过分删除，使沿中心骨架各方向的细化速度 不同步，从而出现毛刺等现象。为此本节提出了4 个保留模板，如图2 9 以及将之 旋转= 2 、石和3 石2 后得到的模板。将删除点集中逐点与4 个保留模板匹配，匹 配的点从删除点集中剔除。 2 3 4 实验结果 如图2 1 0 ，f p a 算法兼顾了连续性和四周噪声免疫，处理效果较好，而且判 断可删除点的条件非常简单、容易实现。最重要的是由于f p a 是从四个方向进行 处理，速度快。但是，f p a 的缺点就是细化结果不是严格的单象素笔划，还有一些 多余象素点不能被删除，如图2 1 0 中的l 处，这样在后面跟踪提取笔划时可能出 现不必要的分叉而又需进行方向判断。除此之外，f p a 也和大多数细化处理算法 一样，难于排除撇、捺方向交叉笔划的歧变，如图2 1 0 中的2 处，由原来的一个 四叉点变形成两个三叉点。 s p t a 算法处理的结果是严格的单象素笔划，便于笔划跟踪提取，这也是s p t a 2 手写体汉字识别技术的研究与实现 算法具有的最大优点，并且比较好地代表了笔划的中轴和保持了笔划的连续性， 又具有较好的抗噪性，达到了细化的基本要求。但由于s p t a 虽然是四方向处理， 却是分四次扫描分别进行，所以速度比f p a 稍慢，而且s p t a 也难于克服4 5 。交叉 点歧变的问题，如图2 1 1 中的l 、2 处。 h i l d i t c h 并行模板细化算法综合了f p a 、s p t a 算法的优点，细化的结果比较 精确，再现了原始汉字点阵的基本特征，也大大改善了目前普遍采用的模板匹配 算法都有的交叉点歧变问题。如图2 1 2 ，图中1 、2 处的交叉点明显比f p a 和s p t a 处理得好。 图2 1 0 f p a 细化结果图2 】is p t a 细化结果图2 1 2 改进的h i l d i t c h 细化结果 2 4 归一化处理 对手写体汉字的归一化处理，可以分为线性归化和非线性归一化，线性归 一化是非线性归一化的特例，各种非线性归一化方法的共同点在于它们都是基于 密度均衡来解决手写体汉字变形，而区别在于对笔划密度的描述不同。我们研究 手写汉字的归一化方法，就是寻找相应的密度均衡函数，使得归一化后的汉字的 密度分布在某种意义下达到最佳。 设f ( x ，y ) 表示归一化之前的汉字点阵x xy ，x = 1 ，2 ，x ；y = 1 ，2 ，y 。 g ( m ，h ) 表示归一化之后的汉字点阵m x n ，m = 1 ，2 ，m ；n = l ，2 ，n 。 d ( x ，y ) 表示汉字点阵在x x y 中各点处的笔划密度函数。 ( 力，矿( y ) 分别表示密度函数在水平和垂直方向上的密度投影，即 上 日( x ) = 【d ( 石，y ) + a ( 工，y ) ， x = l ，2 ，x v = l ( 2 4 ) 上 v ( y ) = d ( x ，y ) 十口r ( x ，y ) 】， y = l ，2 ，- ，y 通常，口。( z ，y ) ，吼( 工。y ) 为己知函数或常数。 第二章手写体汉字识别的预处理 基于密度均衡的各种非线性归一化方法的通用均衡表达式如下 m ：主( ) l ， “1 ( 七) n ：杰w ) l ， 1 y ( ，) 其中，x = 1 ，2 ，x ；y = 1 ，2 ，y ；m = 1 ，2 ，m ；n = 1 ，2 ，。 2 4 1 线陛归一化方法( 简记为m 1 ) t 4 - t s ( 2 5 ) 线性归一化就是将汉字图像按比例线性放大或缩小为所要求的统一尺寸。这 种归化算法简单易行，可以保持原有手写汉字的形状和特征，失真较小，但是 无法调整手写汉字的重心位置和笔划密度。线性归一化可以表示为： 7 ”5 口x + ? y + 。i ，( 2 - 6 )1， ， o j l 门= 日2 工十0 2 y 十c 2 其中， ，y ) 为归化前的汉字点阵坐标，( m ，胛) 为归一化后的汉字点阵坐标， a l ，呸，岛，6 2 ，c 1 ，c 2 为常数。可见，线性归一化的变换函数是线性函数，线性归一化仅 能解决位置和大小变化，但是，在手写体汉字变形中，还存在着笔划倾斜、笔划 形状扭曲等其它变形，由于后者的不规则性和局部变化特性，使得线性归一化方 法不能解决这种手写汉字变形。在式( 2 5 ) 中，若令h ( x ) = 1 ，g ( y ) = 1 ，则 m ：x 警，疗：。i n ( 2 - y 7 ) 7 ”= x _ f ， 疗= 彳? j 即线性归一化是非线性归一化的特例。线性归一化处理的实验结果可以参见 图2 - 1 3 ( b ) 。 因因圆圆 ( a )( b )( c )( d ) 因圆因因 ( e )( f )( g ) 图2 1 3 几种归一化方法的实验结果 4 手写体汉字识别技术的研究与实现 图中： ( a ) 原始的汉字点阵图像： ( b ) 线性归一化后的汉字点阵图像； ( c ) 基于汉字点密度均衡的非线性归一化后的汉字点阵图像： ( d ) 基于汉字笔划穿透数目均衡的非线性归一化后的汉字点阵图像； ( e ) 基于汉字笔划间隔均衡的非线性归一化后的汉字点阵图像； ( f ) 基于汉字线密度均衡的非线性归一化后的汉字点阵图像； ( g ) 基于汉字整体密度均衡的非线性归一化后的汉字点阵图像； ( h ) 改进的基于汉字整体密度均衡的非线性归一化后的汉字点阵图像。 2 4 2 基于汉字点密度均衡的非线性归一化方法( 简记为m 2 ) 1 5 该方法的特点是利用了汉字的水平、垂直方向的投影信息，投影函数选取汉 字的水平、垂直投影，通过对投影的均衡处理，使原本分布不均匀的投影密度函 数均匀化，其实质就是将手写汉字的重心位置调整到汉字点阵的中心。其密度函 数定义为： c l ( x ，y ) = 厂( ) = 他嚣萋需銎餮( 2 - 8 ) 这种非线性归一化方法仅对笔划象素点有定义且它们的笔划密度相同，即仅 考虑了笔划象素点，未考虑背景空白点。优点是算法简单，计算速度快，缺点是 归一化后的汉字点阵中笔划粗细不均匀，如图2 1 3 ( c ) 所示，另一方面，由于密度 均衡是基于全局的，故手写体变形的不规则性及局部性不能得至q 很好的纠正。 2 4 3 基于汉字笔划穿透数目均衡的非线性归一化方法( 简记为m 3 ) f l s 该方法是对汉字点阵进行水平和垂直扫描，并统计扫描线上的笔划穿透数目。 定义汉字图像中自某一点开始，在水平方向上，从左向右扫描过程中出现0 1 对的 个数为该点在水平方向上的笔划交叉密度h ( x ) ，同样可以得到该点垂直方向的笔 划交叉密度呦，密度投影函数表达式为 胃( x ) ：圭而万面厂( w ) + ， y = l 矿( y ) = 艺f ( x - l , y ) 厂( x ，y ) + 口。 x = i ，2 ，z ( 2 9 ) y = 1 ，2 ，y 其中，f ( x ，o ) = f ( o ，y ) = 0 ，7 瓦而表示对，( 石，y ) 值取逻辑非，嘶，为常数。 这种方法仅对笔划边缘象素点定义了密度函数，与基于点密度均衡的非线性 归一化方法相似，其密度均衡也是全局性的，优点是算法简单，计算速度快，对 汉字笔划分布的总体协调能力较强，但不能很好地解决变形中存在的不规则性及 第二章手写体汉字识别的预处理 局部性问题。与基于点密度均衡的非线性归一化方法相比，该方法能较好地保持 笔划粗细均匀，如图2 1 3 ( d ) 所示。 2 4 4 基于汉字笔划间隔均衡的非线性归一化方法( 简记为m 4 ) ” 该方法同时考虑笔划象素点及背景空白点，并区别对待，给予不同的密度值。 每一象素点具有水平密度疗( ) 和垂直密度丘，( ) 两种，即 日( y ) = s h ， i ff ( x ，y ) = 1 丘，( x ，y ) = s v ，i ff ( x ，y ) = 1 1 f h ( x , y ) 2 丽1 ，i f 厂( x ，y ) = o ( 2 - 1 0 ) 1 s ( 墨y ) = 去， 矿f ( x ，y ) = 0 其中s h 、s v 为很小的常数值，h ( x ，y ) 、v ( x ，y ) 分别为在背景空白点( x ，y ) 处进行水平和垂直扫描所得的空白扫描线段的最大长度，如图2 1 4 所示。 其投影函数为 y ( 艽) = 乓( 墨_ y ) + 口h ， y m t 矿( y ) = y , f v ( x ，y ) + 口。 j = 【 x = 1 ，2 ， ( 2 1 1 ) y = 1 ，2 ，y 其中，口。，a ，为常数。 该方法同时考虑了笔划象素点及背景空 白象素点，且有不同的笔划密度描述，在背景 空白点处，笔划密度的描述具有局部特性，故 与前述两种方法相比，该方法能较好地适应手 写变形的局部性和不规则性，如图2 1 3 ( e ) 所 示，也能较好地保证笔划粗细均匀。但是，所 图2 1 4 汉字图像的线间隔 有的笔划象素点具有相同的密度表达，不太合理；而且在对空白象素点的密度描 述中，每个点具有水平和垂直两种密度表达，即将汉字点阵的二维信息转换为两 个一维信息，使得该方法对手写变形的局部性和不规则性的改善效果不是特别理 想。 2 4 5 基于汉字线密度均衡的非线性归一化方法( 简记为m 5 ) 5 1 该方法是一种结合汉字局部信息和二维特性的处理方法，其原理是使汉字点 阵中笔划复杂的部分相对于笔划简单的部分被放大，从而使笔划的形状和分布更 6 手写体汉字识别技术的研究与实现 加均匀合理。基本思路就是将汉字点阵分成形状与大小各异的网格，对区域内的 点重新采样，具体参考文献【5 】。 对汉字图像中任意一点( x ，力，该点处的密度函数d ( x ，y ) 定义如下： 假设从点( x , y ) 出发，沿水平方向向两侧遍历时相遇笔划的右边界为厶和厶， 左边界为l 3 和三。，其中和厶在点( x ，y ) 的左边，而工：和l 。在点( x ，y ) 的右边 ( 厶厶中可能出现不存在的情况) ，公式描述见式( 2 1 2 ) 。 厶= m a x x 7 i x 口托，且均为常数，称口b ( x ，y ) 为密度加强。 口删口口毋姐口 。日l r 丑。 。日l 1 r 钼卜o 、 图2 1 6 笔划间隔定义示意图 ( 2 ) 情形( c ) d a w ) 2 赢+ 口s w ( ) ， ( x 1 ，y ) 2 - 南+ d a m z + ，y x t x 。x i ( 3 ) 情形( d ) 设q 点的坐标为( ，y i ) ，0 2 点的坐标为( 工：，y ：) ，c 点的坐标为( 置、，儿，) ，其中 y l ：“：y c ，则水平方向密度定义为 一 0 0 叫刊 n - 如 旺 第二章手写体汉字识别的预处理 9 “( m ) 2 南+ ( 1 ) 啪i 。川卜丽 可帕一机) ， d “( 叠，儿) 2 f j 三主f ；t + 口s w ( x z ，y ：) ， “( 锄卜网最可怕小， ( 工l x 1 t ) ( k x 2 x 2 ) ( 2 1 7 ) 同理可以定义垂直方向的密度函数阢，( x ，y ) ，则点( x ，y ) 处的笔划密度函数定义为 舷力= r m x 西 办匆， 训( 2 - 1 8 ) 投影函数为 日( x ) = 矿( y ) = 其中a 。，吼，为常数。 d ( x ，y ) + 口h ， d ( x ，_ y ) + 口r ， x = 1 ，2 ， ( 2 1 9 ) y = 1 ，2 ，y 该方法同时考虑了背景空白象素点和笔划象素点，汉字点阵中的所有象素点 均具有笔划密度描述，且不同的象素点具有不同的笔划密度，使得密度函数的描 述更加合理；汉字周边象素点的密度加强较大，尤其是左上角，有利于保持归一 化后的汉字点阵周边信息不失真：另一方面，该方法对密度函数的描述是局部的、 二维的。不难看出该方法具有最优的矫形效果，如图2 1 3 ( h ) 所示。 2 4 7 六种归一化方法小结 从形式上看，上述六种算法的出发点各不相同，有的是针对图像的一维方向 投影，有的是基于图像中笔划的交叉数，还有的是基于二维的区域统计，但是它 们有一个共同之处，都有一组反映汉字图像的特征投影函数，即h ( x ) 和v ( y ) 。关 于这些非线性归一化方法性能的比较见表2 1 7 ： 2 0 手写体汉