（计算机软件与理论专业论文）汉字笔迹的笔划提取.pdf

i 摘要 在多媒体信息量飞速增长的今天，从包含有汉字信息的图片、视频等媒介 中，进行汉字笔迹的自动识别，成为目前研究的热点。笔划提取是汉字笔迹识 别的一个重要步骤。由于手写汉字具有字量大、书写风格众多、随意性较大和 结构复杂等特点，所以，目前笔划提取还存在许多技术问题，包括汉字分割、 细化和笔划提取等问题，需要进一步研究。 在对汉字书写的特点以及已有的分割方法进行分析的基础上，设计了用密 度聚类来分割汉字的方法。聚类方法以组成汉字的像素点为研究对象，聚类完 成后得到的簇就是分割出来的汉字。实验结果表明，用聚类方法可以有效地解 决汉字粘连等问题。 针对现有的细化算法不能解决细化过程带来的局部结构变形和“伪分支” 的问题，对通用细化算法进行了改进，增加了一些排除规则。实验结果表明， 在改进后算法的效果要比以前好，能够有效地解决原算法存在的结构变形和伪 分支等问题。另外，对轮廓跟踪细化算法作了分析，针对起始点难以确定和跟 踪过程复杂的问题，给出了确定跟踪起始点的方法，并解决了跟踪过程中存在 的一些问题。 实验结果表明， 轮廓跟踪细化算法能够克服局部结构的变形和“伪 分支”问题。 在笔划提取上，通过分析细化后骨架的交叉点与模糊区域的关系，设计了 合并交叉点并寻找离交叉点最近距离的轮廓点来检测模糊区域的方法。实验结 果表明，该方法能够正确地检测出模糊区域。在检测模糊区域后，分析模糊区 域附近的笔划间的关系，合并笔划段，最后提取出笔划。 关键词： 汉字笔迹识别; 密度聚类; 汉字分割; 细化算法; 笔划提取算法 ii abstract writer identification is recognizing chinese characters written on paper automatically with the help of computer, it has become a white- hot research point in pattern recognition which is largely different from printed chinese character recognition and on- line handwritten chinese character recognition. compared with printed chinese character recognition, the style of handwritten chinese characters is diverse and optional which is hard to find rules in it. on the other hand, compared with on- line handwritten chinese character recognition, writer identification doesnt have any real- time information. as stroke is primitive of chinese character, stroke extraction is a significant step in writer identification. however, stroke extraction is still one of the most challenging research topics because it involved a large number of characters, considerable writing style and complex structure. according to the speciality of writer identification, new algorithms should be proposed. first, in order to recognize handwritten chinese characters, dividing document image into individual characters is a very important step. upon that density- based spatial clustering is proposed which treats with every pixel and looks at the cluster as a separate character. also, simulation results prove it can deal with the problem of characters adhered to each other effectively. to sum up, the algorithm provides an efficient method to partition connective strokes. and then, thinning character images may bring not only the elimination of image information redundancy but also the predigestion of character recognize. thinning procedure is the preprocessing step of character recognize. therefore, an optimized thinning algorithm is proposed. experiment results show that it can improve on dealing with the local configuration distortion and spurious segments. in addition, thinning algorithm based on tracing- contour is introduced to resolve the problem of iii local configuration distortion. at last, ambiguous zones are places where strokes intersect or overlap, detecting them and analyze the strokes near them is helpful to extract strokes. by analyzing the corresponding relation between the fork points on skeleton and ambiguous zones, an algorithm to detect ambiguous zones is proposed. the experiment results prove that it can detect ambiguous zones correctly, and then, sub- strokes besides the ambiguous zones are analyzed and merged. k e y w o r d s ： writer identification; density- based spatial clustering; chinese characters dividing; thinning algorithm; strokes extraction algorithm 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人 承担。 学位论文作者签名： 日期： 2008 年 6 月 6 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 保密 ，在_年解密后适用本授权书。 本论文属于 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期：2008 年 6 月 6 日 日期：2008 年 6 月 6 日 1 1 绪论 1 . 1 课题背景 字符识别是模式识别学科的一个传统研究领域。从五十年代开始，许多研 究者就在这一领域开展了广泛的探索，推动了模式识别的发展。汉字识别，特 别是汉字笔迹识别，是字符识别中最富挑战性的理论研究课题。目前，随着多 媒体信息量的飞速增长，用计算机来处理并提取有用的信息可以极大地提高工 作效率，因此成为计算机工作者们研究的热点。在包含有汉字笔迹信息的图片、 视频等媒介中，人们需要从中提取和识别出汉字，以减少人们用眼睛识别的工 作量。然而汉字笔迹识别还存在许多困难，成为一个有待解决的问题。汉字笔 迹识别的研究与开发，将满足人们对自动输入汉字的要求，在许多方面都有着 广泛的应用背景。 汉字识别可以分为手写体汉字识别和印刷体汉字识别两大类，手写体识别 的难度要高于印刷体识别。按输入方式不同，手写体汉字识别又可分为联机和 脱机两种。在联机手写体汉字识别中，计算机能够通过与计算机相连的手写输 入设备获得输入的汉字笔划的顺序、笔划的方向以及汉字的形状，因此与脱机 手写体汉字识别相比较，它更容易识别一些，但它要求输入者必须在指定的设 备上书写，在人们的生活中大部分情况下不能满足这一要求。如果需要计算机 去识别已经成为文字的东西，就需要脱机手写体汉字识别技术。脱机手写体汉 字识别可以使用任何一种图像采集设备，如 ccd、扫描仪、数码相机等。脱机 手写体汉字识别系统通过采集设备将书写好的文字的图像输入到计算机中，然 后由计算机去识别。由于脱机手写体汉字识别系统的输入只是简单的一幅图像， 它就不能像联机输入那样比较容易地从物理上获得汉字笔划书写时的实时信 息，因此脱机手写体汉字识别更具有挑战性1。汉字笔迹识别属于脱机手写体 汉字识别的范畴，本文所要研究的汉字笔迹的笔划提取是汉字笔迹识别的一个 非常重要的前提，笔划提取工作的好坏直接影响识别的效果。为了更好地提取 2 笔划，本文主要做了汉字的分割、细化以及笔划提取的研究工作。 汉字笔迹识别的应用十分广泛，可以应用于许多领域，如支票、税票、邮 件等的自动化处理；建立中文资料库，使用汉字识别系统，可以实现文字的自 动输入；办公自动化和情报检索；人工智能，智能计算机汉字智能接口的重要 组成部分；自动阅读机2。 1 . 2 国内外概况 1 . 2 . 1 汉字笔迹的笔划提取发展概况 自从 1966 年 ibm 公司的 casey和 nagy 发表了第一篇有关印刷体汉字识别 的论文以来，汉字识别取得了很大的进展，提出了很多理论和方法。对于汉字 笔迹识别而言，其识别过程一般可以分为原始图像获取、图像预处理、分割、 细化、提取笔划、特征定义和抽取、识别和后处理等步骤。本文研究的汉字笔 迹的笔划提取包括从图像预处理到提取笔划这些工作。 1图像预处理 图像在扫描过程中会带来噪声，图像质量会因为扫描的分辨率的不同而不 同。扫描图像预处理工作的好坏会直接影响到识别的效果。在预处理过程需要 解决的问题主要用图像的二值化、平滑化和归一化等。 2分割 大部分汉字识别系统识别的对象都是单个汉字，然而经过光学仪器扫描得 到的大都是整幅文本图像，而非单个汉字图像，所以汉字分割技术就产生了。 由于汉字字符数量多，手写体汉字具有随意性，其字符大小、字间距、字内距 变化大，切分难度远远大于西文字符以及数字之间的切分。对汉字进行分割时， 如果汉字间出现粘连，重叠和交叠等情况，将给分割工作带来很大的困难。此 外，一个汉字的左右部分如果分得太开或者汉字内部的笔划出现断裂，在分割 时很容易被分割成两个或两个以上的字符，造成分割错误。上述所有情况是汉 字分割研究的重点和难点2。 目前存在的汉字分割方法有基于汉字整体认识的分割方法，像素跟踪法， 3 基于汉字笔划结构的分割方法，基于识别的分割方法5- 8，基于骨架法形态分析 的粘连字符分割方法9。 3细化 细化处理在汉字识别系统中的地位非常重要，因为它能去除汉字的多余信 息，同时又能保持原汉字的大部特征信息，有利于特征提取。汉字细化要求保 持原有笔划的连续性，细化后的骨架为单像素宽，并且应尽量接近原来笔划的 中心线，还要求保持笔划特征。 细化算法有很多，按照细化处理的过程可以分为串行、并行和混合12- 13； 按照处理像素点的方式可以分为迭代细化算法和非迭代细化算法14。han 等人 16提出了一种完全并行细化算法，算法中采用了 5*5 的窗口，它的缺点是消耗 的时间比较多。lei huang 等人12也提出了一种并行细化算法，它的效率较高。 与迭代细化算法不同，非迭代细化算法如轮廓跟踪细化算法17，它不用处理所 有的像素点，而只处理轮廓上的像素点，计算中心点并通过插值的方法来获取 骨架。文献18根据主曲线与中心轴之间的相似性，用分段主曲线来获取骨架， 是一种有效的方法。 4提取笔划 笔划提取在脱机手写体汉字识别中扮演了非常重要的角色，后面的特征提 取和识别工作的效果受笔划提取工作好坏的影响非常大。目前主要有两类提取 笔划的方法，一类是直接从原汉字中提取笔划，另一类是从细化后的骨架中提 取笔划。前者利用了笔划的宽度、曲率、方向等信息，消耗的时间非常多，如 基于模糊子笔划统计特征的手写体识别方法19。而后者由于骨架保留了笔划的 长度和方向等特征，同时又去除了多余的信息，使得它在时间上消耗较少，相 对来说较为实用。有许多方法从骨架中提取笔划，大多数是利用骨架上的特征 点，如端点、交叉点。但是由于手写体汉字的随意性和粘连性，使得此方法很 难保证它的稳健性，容易受笔划的形状影响。rui chen 等人20设计了用过滤器 的方法来提取印刷体和手写体汉字的笔划，可以去除多余的连接笔划。yu qiao 等26从骨架中建立图模型，去除细化过程带来的伪分支，然后对图中笔划进行 4 分析，计算笔划间匹配的概率，定义合并和分离算子，笔划提取过程显得十分 复杂。文献27- 28通过全局跟踪，计算笔划间的光顺性来提取笔划。文献29 在由骨架建立的图中进行双向搜索来提取笔划。文献30- 32也是从骨架中建立 图模型，为了克服细化过程带来的变形和伪分支问题，对多余的交叉点进行合 并或者最大环准则32去除。 in- jung kim 等33应用半细化的方法解决笔划交叉部 分的骨架变形问题，然后建立图模型提取笔划。文献35- 36用 b 样条来作为细 化后的骨架，使骨架形状更能代表原笔划的特征，然后从骨架中提取笔划。 通常来讲，从骨架上来提取笔划的研究较为普遍，其中分为两类：一类是 由点到线，另一类是由线到点。第一类先检测特征点，再由此将汉字笔画拆分 成笔段。大多数基于细化汉字的笔画抽取方法都是这一类，如汉字骨架的像素 跟踪、线性拟合方法等。第二类则是先提取笔段，再通过对笔画结构分析定义 特征点，如黑色像素段提取、高斯模板和 gabor 滤波器等方法。 在笔划提取中，笔划相交或相连的地方由于笔划情况复杂，细化后得到的 骨架在这些地方通常会变形，称之为模糊区域。提取模糊区域附近的笔划是很 困难的。为了检测出这些区域，很多方法都是先计算轮廓上的点的曲率，然后 再寻找曲率最大点40- 46。笔划交叉的地方通常是笔划的轮廓变形较大的地方， 因此检测出曲率最大点是为了定位笔模糊区域， 文献47提出了检测模糊区域的 算法，但是由于汉字结构复杂，效果并不好。 1 . 2 . 2 汉字笔迹的笔划提取的问题和困难 在前面的笔划提取的发展中可以看出，笔划提取的研究过程还存在许多困 难，主要是由于手写体汉字的特殊性决定的，可以归纳为如下 5 条。 1字量大。目前我国常用汉字约 3000- 4000 个，国标 gb2312- 80 两级汉字 共 6763 个汉字。汉字个数越多，分类识别就越困难。 2字体多。汉字的手写字体分楷书、行书和草书三大类，虽然不同字体的 拓扑结构基本相同，但笔画的长短、位置及姿态却有一定的差别，尤其是草书， 可能与楷书和行书根本就不相似。 3结构复杂。汉字笔画多，结构复杂，笔画最多的汉字有三十六画，每个 5 汉字平均有十一画。 4书写变化大。手写体汉字识别的最大难点在于由书写不同引起的结构变 形，这种变形因人而异，而且变形可能十分严重。 5字与字之间相互粘连。这也是手写体汉字中常见的现象，字与字之间的 粘连使得汉字分割成为汉字笔迹识别研究中的一项富有挑战性的课题。由于分 割是汉字笔迹识别中非常关键的一步，如果分割结果不正确，识别就无从谈起。 正因为脱机手写体汉字存在以上特殊性，汉字笔迹识别被看成是一项高难 度的模式识别问题，如果汉字笔迹识别系统进入实用阶段，将标志着模式识别 领域达到了一个前所未有的新高度。 1 . 3 课题主要研究工作 鉴于前面提出的课题背景和国内外概况，本课题将研究汉字笔迹识别的技 术，主要包括汉字分割，细化及笔划提取这三个方面。在汉字分割方面，对已 有的方法进行研究，提出有效分割汉字的方法，该分割方法要能处理大部分的 情况，能够有较高的正确率。在汉字细化上，对现有的细化进行对比分析，改 进现有的算法，解决细化过程带来的问题。在笔划提取上，采用统计特征或结 构特征中所用到的一些方法，借鉴和吸收前人已做的工作，对已有方法进行改 进，同时提出新的方法，提取出汉字的笔划。本课题的研究工作包括三个方面。 1 分割 研究分析现有分割方法的不足，针对现有方法不能很好解决汉字粘连的问 题，提出利用数据挖掘中密度聚类的方法，对汉字进行分割。 2 细化 综合分析国内外已有的细化方法，以及它们的特点，对现有的细化方法进 行对比实验，并进行改进。 3 笔划提取 研究分析现有的笔划提取方法，解决笔划提取过程中的关键问题，改进已 有的方法，并能提出自己的方法，提取汉字的笔划。 6 2 汉字分割方法研究 为了提高汉字分割的正确率，本章将对汉字分割方法进行研究。本章首先 对现有的汉字分割方法进行总结分析，阐述现有方法未能解决的问题，分析这 些问题出现的原因。然后，提出用密度聚类的方法来分割汉字。 2 . 1 汉字分割方法分析 汉字分割是从包含汉字的图像中，将汉字句段分割开来，得到单个汉字的 过程。汉字分割是汉字识别中很重要的一个组成部分，如果分割不正确，后面 的识别工作将无法进行。但由于手写体汉字的书写多变而随意，极大地增加了 汉字分割的难度。 手写体汉字的书写可能产生如下 6 种位置排列情况： （1）正常，汉字各自 分开独立为整体； （2）粘连，汉字的某一笔在一点或几点与相邻汉字接触； （3） 重叠，汉字间无接触，但无法用垂直分割线分割； （4）交叠，两个汉字共享某 一部分像素区域，不仅仅个别几点相连； （5）粘连且重叠，粘连与重叠情况并 存； （6）过分，汉字左右部分间距过大或汉字内部出现笔画断裂。其中，交叠 不常见，但非常难处理。重叠和粘连的情况非常常见，但可以寻找到很多相关 算法。过分是较少被提及的一种情况，因为很少出现，所以也没有什么专门针 对的算法。若书写中几种情况同时并存，就大大增加了分割的难度，是研究手 写体汉字切分的重点和难点5。 近年来，不少学者提出了一些汉字分割方法，如： （1）基于汉字整体认识 的分割方法：它将直方图投影与宽度递归法结合起来分割字符，简单且快速， 拓宽了可分汉字的类型，提高了分割率。但它们只适用于均衡字体或印刷手写 体汉字的分割，一旦笔划宽度改变，汉字相互重叠或粘连，就无法产生很好的 效果。 （2）像素跟踪法：这种方法以一个黑像素点为起始点，不断寻找相邻的 黑像素点，直至没有，称为跟踪笔划，由此产生原始连通域。非常适合无粘连 字符的切分，而且时间要比直方图投影法要快。为了解决无法分割粘连汉字的 7 问题，文献6提出了基于连通域单元和改进穿越算法的汉字切分，可以切分粘 连字符，还可以解决部分粘连位置在竖直方向上可能存在多个笔划的问题，但 对于粘连过于紧密的字符仍不能正确切分。 （3）基于汉字笔划结构的分割方法： 这种方法采用笔划提取再合并，从另一个角度来解决笔画粘连问题。文献7提 到了一种笔画连接盒的动态算法，还有一种通过黑游程跟踪法8提取笔画的方 法。基于笔画提取的分割方法在很大程度上依赖于笔画的提取优劣程度，而且 过于复杂。 （4）基于骨架法形态分析的粘连字符图像分切方法9：通过脊形点 确定切分位置，使用修剪算法对各切分点进行处理，被分离的字符骨架可以直 接通过分类器而不必再作进一步处理。 （5）基于识别的分割方法：基于识别的 统计分割方法是汉字分割的新的思路，如背景细化方法，基于神经网络识别器 的切分方法，基于隐马尔可夫模型的切分方法。这些方法虽然对于复杂情况有 一定的适应性，减少了分割错误，但由于单字识别耗时且正确率有限，还有待 完善。 回顾手写体汉字分割的发展，每种方法可以解决复杂情况中的单个问题， 有针对性地应用在不同的场合。多种方法的结合可以适应多种汉字排列的复杂 情况，提高了汉字分割的正确率。为了解决汉字之间排列复杂的问题，曲线分 割是一种行之有效的方法，背景细化算法的有效性就证明了这一点。由于相邻 汉字间关系的复杂性，无论直线或斜线常常无法正确分割，可以采用统计的方 法来帮助寻找分割线。 2 . 2 基于密度聚类的分割方法的研究与实现 相对于印刷体，自由手写体汉字之间存在连笔和字符大小不一等情况，其 切分的难度很大。当字间存在连笔时，容易被当成一个字，这是本文需要解决 的问题。汉字一般由很多笔划构成，汉字内部的笔段部分一般都有好几道笔划 重叠在一起，而字间连笔的地方一般只有一条笔划，存在像素点的疏密的不同。 作为统计学的一个分支，聚类分析已经被广泛地研究了许多年，它在许多 领域都发挥了重大的作用，如数据挖掘，统计学，机器学习等。目前存在大量 8 的聚类算法，其中基于密度的聚类算法可以发现任意形状的簇，它将簇看作是 数据空间中被低密度区域分割开的高密度对象区域。在上一小节中本文已经分 析过，为了适应汉字与汉字之间结构变化的各种复杂情况，利用曲线能够有效 地分割汉字。因此利用基于密度的聚类算法能够发现任意形状簇的优点，本文 提出了基于密度聚类的分割方法，在聚类过程中，将属于每个汉字的所有像素 点看成是类似的对象，不同汉字的像素点看成是不同的对象，从而达到将不同 的汉字分割开的目的。 2 . 2 . 1 基于高密度连接区域聚类的分割算法 为了能够有效地分割汉字，将基于高密度连接区域的聚类方法应用于汉字 的分割，提出了基于高密度连接区域聚类的分割算法（dividing algorithm using density- based spatial clustering of applications with noise，daudbscan） 。 2 . 2 . 1 . 1 算法思路 基于高密度连接区域的聚类方法（density- based spatial clustering of application with noise，dbscan）是一个基于密度的聚类算法10。该算法将具 有足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任 意形状的聚类。它定义簇为密度相连的最大集合。 将 dbscan 算法应用于汉字分割，把聚类过程完成后得到的簇与单个汉字 对应起来，簇中的对象就是组成单个汉字的像素点。 dbscan 涉及到的一些定义： 1- 邻域：给定对象半径内的区域。 2核心对象：如果一个对象的- 邻域至少包含最小数目 minpts 的对象， 则该对象为核心对象。 3给定一个对象集合，如果 p 是在 q 的- 邻域内，而 q 是一个核心对象， 我们说对象 p 从对象 q 出发是直接密度可达的。 4如果存在一个对象链 p1，p2 ，pn，p1=q，pn=p，对 pid， （1ni ） ， pi+1是从 pi关于和 minpts 直接密度可达的，则对象 p 是从对象 q 关于和 minpts 密度可达的。 9 5 如果对象集合d中存在一个对象o,使得对象p和q是从o关于和minpts 密度可达的，那么对象 p 和 q 是关于和 minpts 密度相连的。 密度可达是直接密度可达的传递闭包，这种关系是非对称的。只有核心对 象之间是相互密度可达的。然而，密度相连性是一个对称的关系。 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包 含在任何簇中的对象被认为是“噪声” 。 daudbscan 从图像的左上角开始检查， 寻找每个黑色像素点的- 邻域来 寻找聚类。由于图像经过二值化后，只包含黑白像素点。如果一个点 p 的- 邻 域包含多于 minpts 个黑色像素点，则创建一个以p 作为核心对象的新簇。 然后， 算法反复地寻找从这些核心对象直接密度可达的对象，这个过程可能会有一些 密度可达簇的合并。当找不到新的黑色像素点可以被添加到任何簇中时，算法 结束。 2 . 2 . 1 . 2 算法过程 daudbscan 算法过程用伪码描述如下： for 图像中每个黑色像素点 pi do if pi是核心对象 then if pi没有被访问过 then / /创建一个新簇 c c=createcluster(); / /将 pi放入簇 c 中 addintocluster(c，pi); / /寻找 pi的- 邻域 findneighbors(pi); else / /寻找 pi所属的簇 c，将 pi的- 邻域内的像素点放入 c 中 c=getcluster(pi); for pi的- 邻域内的像素点 p do 10 addintocluster(c，p); end for end if end if end for 如果采用空间索引，daudbscan 的时间复杂度是 o(nlogn)， n 是黑色像 素点的数目。否则，计算复杂度是 o(n2)。 该算法要求用户输入半径和最 小数目 minpts，对参数敏感，参数选择的好坏对分割效果有很大影响。 2 . 2 . 1 . 3 实验结果 图 2. 1 是实验结果，反映了 daudbscan 分割汉字的效果。图中是四个粘 连的汉字，实验结果表明，daudbscan 能有效地解决汉字粘连问题。通过对 许多实验样本进行实验，daudbscan 对粘连汉字的分割效果很好，切分准确 率较高。切分错误主要出现在汉字部件之间距离过大的左右结构的汉字上。 图 2. 1 基于高密度连接区域的聚类方法分割汉字的结果 2 . 2 . 2 基于相对密度聚类的分割算法 由于 daudbscan 依赖于两个参数： 对象的邻域半径和邻域内的最少 对象数 minpts。它通过检查数据集中每个点的邻域来寻找聚类；如果一个点 p 的邻域包含多于 minpts 个点，则创建一个以 p 为核心对象的新类。然后， daudbscan 反复寻找从这些核心对象直接密度可达的对象，当没有新点可被 添加到任意类时，聚类过程结束，那些不属于任何类的点被标志为噪声。 11 daudbscan 可以在有噪声的情况下中发现任意形状的类，但是它留给用户决 定的参数难以确定，而且它对参数值非常敏感，设置的细微不同即可能导致差 别较大的聚类结果。 同时，考察 daudbscan 可以发现，对于全局恒定的邻域半径和最少对 象数 minpts 值，高密度的聚类结果被完全包含在相连的低密度的聚类结果中。 为了解决这个问题，文献9提出了一种基于相对密度的聚类算法（relative density based clustering，rdb） 。它能很好地发现任意形状、不同密度的类， 并且有效地解决了高密度簇完全被相连的低密度簇所包含等问题。因此，可以 将 rdb 算法应用于汉字分割，本文提出了基于相对密度聚类的分割方法 （dividing algorithm using relative density- based clustering，daurdbc） 。 2 . 2 . 2 . 1 算法介绍 rdb 算法引入了一些概念： （1）对象的 k 近邻距离； （2）k 近邻邻居； （3） 近邻密度； （4）对象关于其 k 近邻邻居的相对密度（relative density，rd） ，rd 反映了对象的近邻密度与其邻居的近邻密度之间的差别，当 rd 接近 1 时，说 明对象与其邻居能很好地融为一体，在数据分布上密度十分接近； （5）核心对 象，若| rd- 1 |，则称该对象为核心对象； （6）核心集合，核心对象 p 的 k 近邻邻居中， 由所有核心对象加 p 本身构成的子集称为核心对象 p 的核心集合， 若 p 非核心对象，则其核心集合无定义； （7）密度可达，若对象 p 是核心对象 q 的 k 近邻邻居，则称对象 p 关于核心对象 q 密度可达； （8）核心对象 p 初始类， 包含所有与 p 的核心集合中的核心对象密度可达的对象； （9）对象 p 关于初始 类的相对密度，反映了对象 p 的近邻密度与初始类中成员对象的平均近邻密度 之间的差别。 rdb 算法首先在数据集 d 中找到任意一个核心对象 p， 求出 p 的核心集合， 得到初始类 c；然后由初始类 c 开始进行类的扩展，直至没有任何对象可以归 入该类；重新在 d 中寻找任意一个未归类的核心对象 q，重复上述过程，直至 没有任何对象可以归入任何类，算法结束。 由初始类 c 的扩展过程分两步进行：首先，对 p 的核心集合进行扩展，得 12 到类 c 的扩展核心集合；然后，根据关于扩展核心集合中核心对象的密度可达 这一条件，对类 c 进行扩展11。 daurdbc 从图像的左上角开始寻找黑色像素点， 应用 rdb 算法寻找核心 对象和扩展初始类。算法结束后，每个初始类经过了扩展，其中包含了许多对 象，这些对象就是组成单个汉字的像素点，这样多个汉字被分割开来。 2 . 2 . 2 . 2 实验结果 图 2 . 2 是实验结果，反映了 daurdbc 分割汉字的效果。图中是四个相互 粘连的汉字，实验结果表明，daurdbc 能够有效地解决粘连汉字的分割问题。 通过对许多文档图像应用 daurdbc 来分割汉字， 发现 daurdbc 在粘连汉字 的分割上效果较好，用户参数也更容易确定。同 daudbscan 一样，切分错误 主要出现在汉字部件之间距离过大的左右结构的汉字上。 图 2 . 2 基于相对密度的聚类方法分割汉字的结果 2 . 3 对比分析 通过对 daudbscan 和 daurdbc 进行汉字分割的实验结果进行分析， 从两个方面来对它们进行比较。 在时间上，二者对同一样本所花的时间是接近的。这是因为 daudbscan 的时间复杂度是 o(nlogn)，daurdbc 采用中间数据表对核心对象的近邻密度 的计算结果进行保存，算法的时间由 k近邻查询的时间和对中间数据表的扫描 时间两部分组成， k 近邻查询的时间复杂度为 o(nlogn), 对中间数据表的扫描时 13 间复杂度为 o(n)，因此 daurdbc 的时间复杂度也为 o(nlog n), 二者没有明 显的时间差异。 在参数的选择上，daurdbc 的参数要比 daudbscan 算法更容易确定。 daudbscan 需要两个参数：对象的邻域半径和邻域内的最少对象数 minpts，这两个参数值的设定依靠用户的经验和对数据的了解，不太容易确定。 daurdbc 也需要两个参数：对象的 k 近邻距离和关于其 k 近邻邻居相对密度 的阈值 d，对于一个类 c, 考虑对象 p，通过分析可以得出类 c的核心对象 p 的 相对密度值接近于 1 。这样就为算法参数 d 的选择限定了取值范围, 从而不像 daudbscan 算法中参数取值具有太多的盲目性和试探性。 2 . 4 小结 本章从汉字分割实际存在的难题出发，对已有的各种分割方法进行了研究， 结合数据挖掘中密度聚类的特点，提出了基于密度聚类的分割方法。 基于高密度连接区域的聚类方法和基于相对密度的聚类方法都是对组成汉 字的像素点进行聚类分析，通过不同的密度划分方法，将密度上接近的像素点 加入到同一个簇中，最后得到的簇就是分割出来的单个汉字。基于相对密度的 聚类方法是对基于高密度连接区域的聚类方法的改进，克服了高密度的聚类结 果被完全包含在相连的低密度的聚类结果中这一缺点，并且使得参数选择更简 单。 汉字分割一直是个难以解决的问题，通过对已有的方法进行比较分析，发 现它们都存在一些缺陷。本章提出基于密度聚类的方法来分割汉字，是一种新 的思路，还有待完善和改进。 14 3 细化方法研究 在上一章中介绍了汉字分割方法后，多个汉字被分割成了独立的汉字。本 章将对汉字的细化方法进行研究。 本章首先对现有的细化方法进行分析，指出它们存在的问题，分析出现这 些问题的原因。然后，对现有的细化算法中用得最多的一种细化算法进行分析， 并提出改进。最后，介绍另一种不同类型的细化算法并对它进行了改进，它能 够较好地解决前一种细化方法仍不能很好解决的问题。 3 . 1 细化方法分析 细化是将汉字细化为单个像素宽的骨架的过程。细化减少了要处理的数据 量，有助于准确提取汉字的特征。在汉字的细化过程中，要求保持字体的结构 信息不变，保证原有笔划的连续性，骨架应尽量接近笔划的中心线。 汉字的细化处理非常重要。因为在二值化点阵图像中，对识别有价值的汉 字特征信息主要集中在汉字骨架上，细化后的汉字骨架能保留原汉字大部分的 特征，有利于特征提取。细化后骨架的存储量比原汉字二值化点阵要少得多， 降低了处理工作量。细化结果的好坏将直接影响到字符特征提取的准确与否， 最终影响到整个字符识别系统的识别率，因而字符细化已成为字符识别系统中 极为重要的环节。 由于细化在字符识别中的重要地位，长期以来人们对其作了大量的研究， 提出了多种细化算法。这些细化算法在处理西文字符时均取得了较好的效果， 由于汉字的字形与西文字符的字形存在较大的差异，这些传统的细化算法在应 用于汉字细化时，往往会造成新的畸变，增加了对识别的干扰和困难，且算法 本身也较耗时。 通过对已有的细化方法进行分析，发现可以分为两类： （1）迭代细化算法： 不断删除连续像素块的边界，直到只剩下单个像素宽的骨架为止。为了保持字 符的连通性，需要有像素删除的标准。按照像素点删除顺序，又可以分为顺序 15 细化算法和并行细化算法。 （2）非迭代细化算法：通过寻找像素块的中心轴、 距离变换方法或者轮廓跟踪方法来产生骨架，而不是检查所有的像素点。相比 迭代细化算法，非迭代细化算法能够很好地保持字符的特征和连通性。 下面分两节来分别研究一种迭代细化算法和一种非迭代细化算法，然后会 对它们进行对比分析。 3 . 2 改进的通用细化算法 为了改进迭代细化算法的效果，许多研究者提出基于模板的细化算法。基 于模板的细化算法必须在细化结果和细化速度之间进行权衡、折衷：即快速的 细化算法要求模板不能太多，模板的尺寸也不能太多，而这些都将导致细化结 果在某些情况下可能出现严重的变形；另一方面，侧重细化结果的算法要求模 板数比较多，模板尺寸也较大，从而导致细化速度明显降低。然而模板再多、 模板尺寸再大也无法完全避免细化结果中出现变形的现象。这是由于任何局部 的关联都无法完全表达全局的关联，因此基于模板的细化算法不能完全避免在 细化结果中出现毛刺和胡须。 l. huang12等人提出一种改进的并行细化算法，可以快速有效地识别汉字。 算法中用到一些新的规则，用来解决不连续性的问题。增加轮廓信息来克服细 化过程中可能带来的信息丢失问题。细化后得到的骨架接近于笔划的中心线， 保留了原始笔划的拓扑信息。 文献13提出了一种算法，是对 l. huang12提出的算法的改进。改进之处 在于修改了保留规则。下面小节介绍该算法，并针对该算法存在的问题，本文 提出了改进。 3 . 2 . 1 算法改进的思路 在二值化后，汉字图像只包含黑白像素点，1 代表黑色像素点，即组成汉 字的像素点； 0 代表白色像素点，即背景像素点。黑色像素点代表组成汉字的像 素点或细化后骨架上的像素点。 16 细化算法的核心是排除规则，它决定了细化算法的性能。 算法中使用了 3*3 的窗口， 8 邻居的 256 种组合情况都考虑到了，从这些所有的组合中，挑选出排 除规则。由于有些排除规则会造成细化后的骨架变形，或者不连续，因此这些 排除规则就被去掉了。 算法中使用的排除规则见图 3 . 1所示，1 代表黑色像素点，空白的格子代 表白色像素点。 图 3 . 1 排除规则 17 按照被考察像素点的 8 邻居中的黑色像素点的个数，这些排除规则被分为 9 类。第一列是 8 邻居中黑色像素点的个数，第二列是排除规则。这些排除规则 决定了哪些情况下像素点应该被删除掉。排除规则要取得适当，过多或者不足 都会造成细化后的骨架不连续或变形。对每个像素点应用所有的排除规则，如 果匹配某一个排除规则，该像素点就会被去掉。可是，在有些情况下，像素点 不该被去掉。在水平或垂直方向有偶数个邻居的像素点如果被去掉，就有可能 造成连通性的丢失，比如两个像素宽的矩形区域就会被完全删掉。为了保持连 通性，这种情况下像素点不应该被删除掉。因此，算法中还定义了一些保留规 则。 应用图 3. 1 中的排除规则实现该算法，通过对实验样本进行测试，我们发 现在有些情况下， 细化后的骨架会存在伪分支，如图 3. 2 所示。图中是汉字 “贫” 和细化后的结果， 可以发现骨架上多出了原来不存在的两段， 这就是所谓的“伪 分支” 。 图 3 . 2 汉字“贫”和细化后的骨架 为了解决“伪分支”的问题，本文又提出一些排除规则，主要是针对 8 邻 居数为 4，5 和 6 的三种情况。在增加了排除规则后，对同一个汉字“贫”进行 细化，伪分支被去除掉了，有效地解决了该问题。如图 3. 3 所示。 图 3 . 3 增加排除规则后， “贫”和细化 后的结果与图 3 . 2 相比，伪分支被去除了 18 增加的排除规则如图 3. 4 所示。 图 3 . 4 增加的排除规则 3 . 2 . 2 算法过程 首先计算一个像素点的 8 邻居的个数，然后在排除规则表里寻找相同 8 邻 居数的排除规则。如果有匹配的排除规则，接着判断它是否有偶数个 8 邻居的 黑色像素点，如果存在，就检查是否符合保留规则。如果符合其中一个保留规 则，就被保留下来，否则就会被去掉。 改进后的通用细化算法的步骤如下： step 1计算像素点的 8 邻居中的黑色像素点个数。 step 2在排除规则表里寻找具有相同数目的 8 邻居中的黑色像素点个数， 如果匹配，则转到 step 3，否则转到 step 5。 step 3计算像素点的 8 邻居的连续黑色像素点的个数。 step 4如果有偶数像素宽的黑色像素点，检查保留规则，如果匹配，就保 19 留该像素点，否则删掉该像素点。 step 5重复 step 1 至 step 4，直到没有可删除的像素点。 算法不断地迭代删除笔划轮廓上的像素点，直到笔划只剩下单像素宽度为 止，这样迭代的平均次数为笔划的平均宽度的一半。在每次迭代中，检查笔划 上的每个像素点，如果像素点的八邻居排列情况和某个排除规则符合，则删除 该像素点；若同时也和某个保留规则符合，则保留该像素点。假设像素点的个 数为 n，排除规则和保留规则的个数为 m，笔划的平均宽度为 w，则算法的运 行时间 t(n)= 2 *wmn ，时间复杂度为 o(n*m*w)。 由于汉字的像素点个数是一定的，笔划的平均宽度也是不变的，所以算法 的效率取决于规则的个数。规则越多，算法效果越好，但是消耗的时间也越多。 为了减少搜索规则所消耗的时间，按照像素点的八邻居个数对规则分类，大大 减少了搜索匹配的时间，提高了算法效率。 3 . 2 . 3 实验结果 在评价一个细化算法的好坏时，通常是根据 3 个指标来进行的： （1）是否 保持了原始图像的连通性； （2）细化后的骨架宽度是否为 1； （3）是否能够排除 噪声点的干扰； （4）是否能够保留图像中原有的信息。 图 3 . 5是实验样本以及细化结果。第一列是实验样本，第二列是文献15 中提出的细化算法的实验结果，第三列是文献16中提出的细化算法的实验结 果，第四列是文献12中提出的细化算法的实验结果，第五列是文献13中的细 化算法的实验结果， 第六列是本文提出的对文献13提出的细化算法改进后的实 验结果。仔细观察图 3. 5中实验样本的细化结果可以发现，文献15提出的算法 对汉字细化后的骨架虽然在交叉区域能够很好地保持原来的形状，但不是单像 素宽的，比如在有些类型的笔划处，如“撇” 、 “捺” 。文献16提出的算法对汉 字细化后，虽然是单像素宽的，但骨架不是连续的，破坏了笔划的连通性，一 条连续的笔划会被分成几段，造成了笔划结构的变化。 20 图 3 . 5 几种迭代细化算法的细化结果对比。列 1 是实验样 本；列 2 是文献 1 5 中的细化算法结果；列 3 是文献 1 6 中 的细化算法结果；列 4 是文献 1 2 中的细化算法结果；列 5 是文献 1 3 中的细化算法结果；列 6 是对文献 1 3 中的细 化算法改进后的实验结果。 21 文献12提出的算