Print

发布时间: 2017-06-16
摘要点击次数:
全文下载次数:
DOI: 10.11834/jig.160470
2017 | Volume 22 | Number 6




    图像分析和识别    




  <<上一篇 




  下一篇>> 





局部关联度最优的手写汉字骨架提取
expand article info 周正扬1,2, 詹恩奇1, 郑建彬1, 胡华成1
1. 武汉理工大学信息工程学院, 武汉 430070;
2. 光纤传感技术与信息处理教育部重点实验室(武汉理工大学), 武汉 430070

摘要

目的 研究手写汉字图像时,骨架是最为常见的切入点之一。利用传统细化算法提取手写汉字骨架,容易在笔画交叉等情况复杂的区域产生形变。针对此问题,提出一种基于局部关联度的手写汉字骨架提取算法。 方法 首先对手写汉字图像进行细化以获取原始骨架,按照端点、普通点和复杂点3种类别标注骨架点;利用8邻域窗口扫描相互连通的复杂点,检测并提取复杂区域;删除复杂区域,将原始骨架拆分为若干简单笔画段,形变部分在此过程中被一并移除;提取局部子段,根据笔画段间的方向差异程度和曲率变化程度,计算局部关联度;制定一种局部关联度最优的连接策略,对满足连接条件的笔画段进行插值补偿,从而修正形变,并得到完整的汉字骨架。 结果 对于600个实验样本,从骨架直接检测复杂区域所得结果十分接近理想情况,而轮廓法所得数量是理论值的2.5倍;基于局部关联度重组笔画段,绝大多数形变得到修正,重组后的骨架符合真实拓扑结构;以标准骨架为参考,骨架提取准确率达到了98.41%。 结论 局部关联度最优的手写汉字骨架提取算法,能够有效检测复杂区域,对形变具有良好的修正作用,提取所得骨架能够正确反映复杂笔画间的位置结构关系,是一种实用有效的骨架提取方法。

关键词

手写汉字; 细化; 骨架形变; 复杂区域; 局部关联度

Skeleton extraction algorithm based on optimum local correlation degree for handwritten Chinese characters
expand article info Zhou Zhengyang1,2, Zhan Enqi1, Zheng Jianbin1, Hu Huacheng1
1. School of Information Engineering, Wuhan University of Technology, Wuhan 430070, China;
2. Key Laboratory of Fiber Optic Sensing Technology and Information Processing(Wuhan University of Technology), Ministry of Education, Wuhan 430070, China
Supported by: National Natural Science Foundation of China(61303028)

Abstract

Objective Studies on handwritten Chinese characters, such as those on signature verification and text recognition, have been conducted for many years. The skeleton is a key point in these studies. It reduces redundant information but retains a complete topology structure. Using a thinning algorithm to extract a skeleton from a handwritten Chinese character image is a traditional approach. However, distortions exist in the extracted skeleton primarily because the complex areas are not well detected nor processed. Complex areas are the intersections and junctions of strokes. Considering that characters are saved as static images, a computer cannot recognize the existence of these areas with more than one stroke. The computer still regards these areas as an entirety, so the thinning algorithm does not perform well. To solve distortion, this study proposes a skeleton extraction algorithm based on the optimum local correlation degree for handwritten Chinese characters. Method A simple and effective method to extract complex areas is designed. This method uses a thinning algorithm to obtain the original skeleton. The points on the skeleton are classified as end, common, and complex points. Complex areas are extracted by detecting connected complex points with an eight-neighbor window. Afterward, the information on complex areas is used to modify the original skeleton. The modification algorithm is based on a strategy involving split and reconstruction. The skeleton is split into several stroke segments because all complex areas are removed. Distortions are also eliminated in the removal. The reconstruction step focuses on the reconnection of stroke segments; it analyzes the relationship among stroke segments to restore the skeleton. The directional relationship is considered. The slope between two end points of a segment may not accurately represent the correct direction because the stroke segments are not always straight. Sub-segments adjacent to a complex area can provide the required directional information. In most cases, two stroke segments that are originally connected possess similar directions. However, in several situations, obtaining the direction is insufficient when determining whether two stroke segments belong to one natural stroke. Consequently, the curvature relationship should also be considered. A concept of local correlation degree is proposed based on the relationship of direction and curvature between sub-segments. The correlation degree is designed to be sensitive to the change in direction. The correlation degrees of any two stroke segments in one complex area are calculated. When two stroke segments share the optimal local correlation degree, they are regarded as a pair of continuous segments. The connection step uses interpolation to restore the removed part between continuous segments. Discontinuous segments are provided a proper extension to prevent an incorrect connection. By connecting the stroke segments, the split skeleton is reconstructed, and distortions are modified. Result Twenty people are asked to write 600 Chinese character samples for the experiment using different pens. All images are denoised and binarized. The use of the eight-neighbor window to detect complex areas in the skeleton provides a good effect. The number of detected complex zones in the 600 samples is close to the theoretical value, whereas that obtained with the contour method is 2.5 times the theoretical value. Most distortions are modified with the local correlation degree, and the reconstructed skeleton approximates the real topology. With the standard skeleton as a criterion, the accuracy of skeleton extraction is 98.41%. Conclusion The proposed skeleton extraction algorithm for handwritten Chinese characters uses a strategy involving split and reconstruction. Reconstruction is based on the optimum local correlation degree. The proposed method has two main advantages over other methods. First, complex area detection is considerably improved. Other methods detect complex areas mainly through the analysis of turning points on the contour. Unlike these methods, the proposed method implements detection directly from the skeleton. The method is simple and avoids excessive detection. Second, the stroke extraction algorithm provides a good result on distortion modification. Removing complex areas with distortions and reconnecting stroke segments through interpolation provide an efficient solution. The extracted skeletons retain good shapes, and the position relationships among strokes are correct. To conclude, the proposed stroke extraction method demonstrates high accuracy and processing speed. It is an effective and useful method for applications dealing with handwritten Chinese characters.

Key words

handwritten Chinese character; thinning; skeleton distortion; complex area; local correlation degree

0 引言

目前,邮件分类、文档录入和笔迹鉴别等需要分析手写文字信息的工作仍主要依靠人工完成,通过计算机分析和处理这些信息正在成为一种趋势[1-2],将节省可观的人力和时间成本。手写汉字在这些场景中大量出现,因此快速有效地从中提取有用信息是该领域的研究重点之一。分析离线手写汉字的方法主要分为两种:一是提取整体统计特征[3-4],比如梯度特征、纹理特征等,通过分类器对这些特征进行分类;二是提取以笔画为主的结构特征[5-6],利用笔画的空间结构与位置关系来表现文字特点。无论采用哪一种方式,骨架都是最为常见的切入点之一,利用骨架表示原始汉字,能够在保留几何拓扑特征的前提下,减少冗余信息。若能从手写汉字图像中准确提取近乎理想的骨架,对于特征提取、内容识别等相关工作有着十分重要的意义。

细化算法是提取汉字骨架最为主要的手段,图像的细化是指在尽量保持原始图像拓扑结构和连通性的情况下,简化抽离出单像素宽骨架的过程。目前多数提取汉字骨架的细化算法都是在Zhang等人[7]细化算法模板法的基础上进行改进,已经解决了早期算法的一些不足之处,比如骨架不是严格单像素宽、存在毛刺等问题[8-9]。此类算法依靠多次迭代,逐层去除文字笔画外围符合删除条件的像素点,最终得到骨架。

细化算法的最大问题是所得骨架存在形变失真情况,形变主要集中在复杂区域,复杂区域指笔画相交、分支等情况形成的区域(也称模糊区域[10])。细化算法无法识别复杂区域存在两段或多段笔画,仍然按一个整体处理,强行将这些区域变为严格单像素宽的骨架,因此产生形变。许多学者都尝试改进传统细化算法,但对形变的修正效果不够理想,根本原因是基于迭代的细化思路不适用于处理复杂区域。此外,由于细化算法通常包含多次迭代,一旦修改不恰当,很容易对算法的时间性能造成很大损失。合理的解决方法是让细化算法避开复杂区域[11-12],或是对已经产生的形变进行修正。

基于上述问题,本文不针对细化算法进行改进,而是从汉字笔画结构出发,利用先拆分、后重组的思路,提出一种基于局部关联度的手写汉字骨架提取算法。首先使用改进后的传统细化算法[13]提取汉字骨架,并检测骨架上的复杂区域。通过删除复杂区域,骨架被拆分成若干笔画段,由于骨架形变几乎全部出现在复杂区域,因此形变部分也被一并移除。然后提取笔画段靠近复杂区域的局部子笔段,通过计算局部方向向量间的余弦相似度以及曲率变化程度来衡量笔画段间的局部关联度。最后根据是否满足局部关联度最优条件,连接原本连通的笔画段。在重新连接的过程中,被删除的部分通过符合笔画方向走势的插值进行补偿,骨架形变因此得到修正。

1 汉字局部形态和复杂区域

1.1 汉字局部形态

中国汉字结构复杂,笔画交错相连,构成多种形态,本节首先对中文字符中经常出现的局部笔画形态进行说明。

从局部来看,常见的汉字笔画形态主要有单笔形、交叉形、丁字形和回笔形四种,如图 1所示。由于细化算法不是理想的,所得骨架可能出现的形态更为复杂,只有单笔形笔画的细化情况较为理想,其骨架是一条单像素宽的曲线段。

图 1 汉字局部形态
Fig. 1 Local forms of Chinese character
((a) linear area; (b) crossing area; (c) T-shaped area; (d) back-writing area)

其他形态的区域经过细化得到的骨架会出现形变现象,图 2列举了常见复杂情况,每一种情况的左图为细化所得实际骨架,右图是对应的理想骨架。理想骨架中用不同颜色表示不同笔画,颜色最深的点表示笔画交叉或是重叠的区域。可以看到交叉形区域的形变最为明显,笔画会在此区域错开,如图 2(a)所示。丁字形是某段笔画正好是从另一段笔画中间开始书写形成的区域,其细化结果相对较好,但也存在略微形变,其骨架通常是图 2(b)中的情况。回笔形如图 2(c)所示,在书写过程中,笔画到达一端以后又转向与当前笔画夹角较小的另一个方向,容易造成重叠,而细化算法并不能识别,也就无法将该区域的笔画按理想情况分开。

图 2 细化所得骨架和理想形态
Fig. 2 Extracted skeletons and the corresponding ideal shapes
((a) crossing area; (b) T-shaped area; (c) back-writing area)

1.2 复杂区域检测

在其他学者对手写汉字开展的相关研究中,不能有效地识别和解析上述笔画相交或重叠区域是造成实验结果不够理想的一个重要原因。若能准确定位这些复杂区域并加以妥善处理,对手写汉字的研究会有很大帮助。目前,检测复杂区域的方法主要从原始文字的二值图像直接入手,常见的有角点检测法[14-15]和段化法[16]等。

角点检测法也称轮廓法,通过检测轮廓线上曲率突变点来定位复杂区域,该方法的不足之处是较长轮廓线上的突变点能被较好地检测出来,对于短轮廓线则误差较大,而且笔画弯折较大的位置也会被认为是复杂区域。段化法定义并提取几个特定方向的笔画,然后检测笔画相交的区域,这种方法仅限于笔画方向特征明显的汉字,处理印刷体效果较好,但不适合用于手写汉字。

一些学者为了使细化算法避开复杂区域,同样采用拆分重组的思路[17-18],在检测复杂区域时主要采用轮廓法。与本文先细化再检测骨架复杂区域的方法相比,从原始文字上直接检测复杂区域的方法主要有以下两处不足:

1) 原始文字所含的像素点数量是骨架的若干倍,检测成本较高,复杂区域的判断难度更大;

2) 误检测情况较多,笔画正常弯折部分容易被认为是复杂区域,导致检测到的复杂区域数量几倍于实际数量,增大了后续操作的复杂度。

从汉字细化结果特点出发,提出一种简单而有效的骨架复杂区域检测方法。在确定复杂区域前,首先对骨架上的像素点进行分类。手写中文字符的骨架图像是二值图像,骨架点的值为1,背景点为0。对于单个目标像素点,与其直接相邻的8个像素点称为目标像素点的8邻域。

定义1 设$P$为骨架上一点,$P_1$$P_2$,…,$P_8$构成$P$的8邻域,$N\left( P \right) = \sum\limits_{i = 1}^8 {{P_i}} $表示8邻域中骨架点的数量,则对于不同的$N\left( P \right)$$P$被分为3种类型,即

$P = \left\{ {\begin{array}{*{20}{l}} {{P_{{\rm{end}}}}}&{N\left( P \right) = 1}\\ {{P_{{\rm{common}}}}}&{N\left( P \right) = 2}\\ {{P_{{\rm{complex}}}}}&{N\left( P \right) \ge 3} \end{array}} \right.$ (1)

式中,${{P_{{\rm{end}}}}}$${{P_{{\rm{common}}}}}$${{P_{{\rm{complex}}}}}$分别表示端点、普通点和复杂点。端点位于笔画的两端,普通点在骨架上出现最多,表示正常笔画点。而复杂点则几乎全部出现在笔画的交叉处、丁字形的分叉处或是回笔形的重叠区域,复杂点的8邻域中至少存在3个其他骨架点。

定义2 给定$n$个复杂点组成的集合$\mathit{\boldsymbol{Z}}$,若对于其中每一个${P_i}(i = 1,2, \cdots ,n)$,都至少存在一个${P_j}(j = {\rm{ }}1,2, \cdots ,n,j \ne i)$位于${P_i}$的8邻域中,且与$\mathit{\boldsymbol{Z}}$直接相连的外部骨架点中不存在复杂点,则称$\mathit{\boldsymbol{Z}}$为一个复杂区域。

图 3$P_1$$P_4$构成一个复杂区域,具体确定一处复杂区域的算法如下:

图 3 复杂区域
Fig. 3 Complex area

1) 选择一个复杂点,令其为$P_1$,用集合$\mathit{\boldsymbol{Z}}$表示包含该点的复杂区域,将$P_1$加入$\mathit{\boldsymbol{Z}}$

2) 从$\mathit{\boldsymbol{Z}}$中取出未执行过本步骤的一点$P_i$,遍历$P_i$的8邻域,若某8邻域点$P_j$是复杂点且不在$\mathit{\boldsymbol{Z}}$中,则将$P_j$加入$\mathit{\boldsymbol{Z}}$

3) 若$\mathit{\boldsymbol{Z}}$中全部的点都执行过步骤2),则算法结束,复杂区域$\mathit{\boldsymbol{Z}}$确定。

简单来说,上述算法从一个复杂点出发,用3×3的窗口扫描和搜索周围其他相邻的复杂点,使得这些点的集合构成它们所处的复杂区域。当形变较为严重时,一个交叉形区域可能被分成两个较小的复杂区域,在初步提取复杂区域之后,对属于同一交叉部位的邻近复杂区域还需加以合并。

2 骨架的局部关联度修正算法

本节详细讨论通过局部关联度来修正骨架形变的算法。检测出骨架上全部复杂区域后,删除复杂区域从而将骨架拆分为若干笔画段,并仍然保留这些笔画段与对应复杂区域的连接信息。骨架拆分的目的是为了移除形变,笔画段重组的过程则是为了补偿符合笔画走势的骨架点。局部关联度用来衡量笔画段之间的连通关系,通过制定合理的连接策略完成连接操作,从而得到最终的骨架图像。基于局部关联度的手写汉字骨架提取算法流程如图 4所示。

图 4 基于局部关联度的骨架提取算法流程
Fig. 4 Flow of skeleton extraction algorithm based on local correlation degree

图 5(a)(c)分别显示了手写汉字“文”的原始骨架图像、复杂区域检测情况及删除复杂区域后得到的笔画段。骨架上圆圈标注的部分是复杂区域,笔画交叉区域存在较为明显的形变,在拆分之后形变部分被去除。

图 5 骨架拆分示例
Fig. 5 Split of skeleton
((a) original skeleton; (b) complex areas; (c) stroke segments)

2.1 局部关联度

为了正确重组骨架,需要确定笔画段间的连通关系。连通关系由方向角度、曲率变化等因素决定,这些数据从离线图像中是无法直接得到的,需要根据笔画段已有信息进行估算。多数情况下,连通的笔画段间保持基本一致的方向,依靠方向向量能够很好地确定连通关系。然而存在少数情况,仅靠方向信息不足以判断连通性,需要借助曲率变化进行区分。因此,本文提出局部关联度作为笔画段连通性分析的依据,以方向关联度为主要因素,辅以曲率关联度。

假设图 6(a)中交叉区域的四段笔画段为$S_1$$S_2$$S_3$$S_4$,根据该汉字的理论构成,$S_1$应该与$S_3$相连、$S_2$应该与$S_4$相连。衡量$S_2$$S_4$间的方向关系,最简单的方法是选取笔画段两端端点,转化为方向向量,如红色线段所示,但由于笔画段中可能存在弯曲,该向量并不能贴切表示笔画段在待连接区域的真实方向。事实上,选取笔画段靠近交叉区域的局部方向更为合理,如图 6(b)所示。

图 6 笔画段方向与曲率变化
Fig. 6 Direction and curvature change of stroke segments
((a) global direction; (b) local direction; (c) curvature variation)

根据局部方向能够正确判断大多数笔画段的连通关系,然而对于图 6(c)中的情况,仅靠方向不足以判定$S_6$应该与$S_5$还是$S_7$连通。此时需要借助局部的曲率变化来进行分析,显然$S_6$$S_5$间的曲率变化更为自然平滑。

笔画段上确定局部方向与曲率的部分称为局部子段。若笔画段$S$含有$n$个点,$S$靠近复杂区域$\mathit{\boldsymbol{Z}}$的端点为$P_1$,另一端端点为$P_n$,则$S$靠近区域$\mathit{\boldsymbol{Z}}$的局部子段$\mathit{\boldsymbol{T}}$$P_1$${P_m}$确定,$\mathit{\boldsymbol{T}} = \{ {P_1},{P_2}, \cdots ,{P_m}\} $$m$的值分以下3种情况:

1) 当$n$≥ 10且笔画段整体较为平滑时,$m$=10。本文通过测试发现,对于宽度为100像素的文字图像,长度为10的局部子段已包含足够的方向与曲率信息,因此$m$的最大值为10。

2) 当笔画段长度$n$<10且笔画段整体较为平滑时,$m$=$n$

3) 先根据前两种情况暂定$m$的值,当$P_1$${P_m}$之间存在曲率突变的拐点时,$m$的值应更新为拐点序号。

确定$m$后,点$P_1$${P_m}$构成的向量$\mathit{\boldsymbol{v}}$称为$S$的局部方向向量。

定义3 假设笔画段$S_i$$S_j$与复杂区域$\mathit{\boldsymbol{Z}}$相连,${\mathit{\boldsymbol{v}}_i}$${\mathit{\boldsymbol{v}}_j}$表示对应的局部方向向量,则$S_i$$S_j$之间的方向关联度${\alpha _{ij}}$等于${\mathit{\boldsymbol{v}}_i}$${\mathit{\boldsymbol{v}}_j}$余弦相似度的绝对值,即

${\alpha _{ij}} = \left| {\frac{{{\mathit{\boldsymbol{v}}_i} \cdot {\mathit{\boldsymbol{v}}_j}}}{{\left\| {{\mathit{\boldsymbol{v}}_i}} \right\|\left\| {{\mathit{\boldsymbol{v}}_j}} \right\|}}} \right|$ (2)

${\alpha _{ij}}$的值介于0和1之间,越接近1则表示两段笔画段的局部方向越相近,余弦相似度保证了笔画段间的方向关系被正确表示。

分析笔画段间的曲率变化关系保证笔画段以自然平滑的方式进行连接,采用式(3) 估算曲率,令$P_i$为离散曲线$C({P_{i - m}},{P_{i - m + 1}}, \cdots ,{P_i}, \cdots ,{P_{i + n - 1}},{P_{i + n}})$上一点,则$P_i$的曲率为

$cur({P_i}) = \frac{1}{t}\sum\limits_{k = 1}^t {d({P_i},({P_{i - k}},{P_{i + k}}))} $ (3)

式中,$t = {\rm{min}}(m,n),d({P_i},({P_{i - k}},{P_{i + k}}))$表示${P_i}$到直线段$({P_{i - k}},{P_{i + k}})$的距离。

定义4 假设笔画段$S_i$$S_j$与复杂区域$\mathit{\boldsymbol{Z}}$相连,$T_i$$T_j$表示对应的局部笔画,$B_ij$表示$T_i$$T_j$间的B样条插值曲线,则$S_i$$S_j$之间的曲率关联度由$T_i$$T_j$的平均曲率之差来表示,即

${\beta _{ij}} = \frac{1}{{{l_{ij}}}}\left| {\frac{1}{{{l_i}}}\sum\limits_{P \in {T_i}} {cur\left( P \right)} - {\rm{ }}\frac{1}{{{l_j}}}\sum\limits_{P \in {T_j}} {cur\left( P \right)} } \right|$ (4)

式中,${{l_i}}$${{l_j}}$${{l_{ij}}}$分别表示${{T_i}}$${{T_j}}$${{B_{ij}}}$的长度,$P$位于曲线$C\left( {{T_i},{B_{ij}},{T_j}} \right)$上。$β_ij$的值越小,表示$S_i$$S_j$之间的曲率变化程度越小、走势更自然平滑。

定义5 给定笔画段$S_i$$S_j$的方向关联度${\alpha _{ij}}$和曲率关联度${\beta _{ij}}$,则$S_i$$S_j$间的局部关联度为

$co({S_i},{S_j}) = {\alpha _{ij}}{\rm{exp}}\left( { - \frac{{\beta _{ij}^2}}{{{\sigma ^2}}}} \right)$ (5)

式中,常数因子$\sigma $使得${\beta _{ij}}$在合理范围内变化时,${\rm{exp}}\left( { - \frac{{\beta _{ij}^2}}{{{\sigma ^2}}}} \right)$的变化幅度很小。

$co({S_i},{S_j})$的值介于0和1之间,越接近1则表示$S_i$$S_j$的局部关联程度越高,原本连通的可能性更大。$co({S_i},{S_j})$${\alpha _{ij}}$的变化更为敏感,符合局部关联度以方向关联度为主、曲率关联度为辅的要求。

2.2 笔画段连接

一个复杂区域周围有若干笔画段相连,连接过程的主要工作是判断这些笔画段间的连通关系,从而进行连接与修正。

假设$S_1$${S_n}$$n$段笔画段与一处复杂区域相连,对于给定的$S_i$,其对应的最优匹配为

$\begin{array}{l} {S_j} = \mathop {{\rm{arg}}\;{\rm{max}}}\limits_{{S_k}} \left\{ {co\left( {{S_i},{S_k}} \right)|} \right.\\ \quad \quad \left. {1 \le k \le n,k \ne i} \right\} \end{array}$ (6)

如果${S_i}$${S_j}$之间相互构成最优匹配关系,表示它们是连通的,那么应当连接${S_i}$${S_j}$,并采用${S_i}$${S_j}$间的插值曲线$B_ij$作为补偿骨架段插入其间即可完成连接。如果笔画段${S_i}$能够找到最优匹配关系,则称${S_i}$在所处复杂区域是连续的,否则${S_i}$是不连续的。对于不连续的笔画段,不进行其他连接处理,防止错误连接。由于无法和其他笔画段进行连接,在拆分过程中被删除的部分需要通过额外的操作来补偿,补偿前需要确保其所处复杂区域中其他构成最优匹配的笔画段已得到连接。假设不连续笔画段$S_p$与复杂区域$\mathit{\boldsymbol{Z}}$相连,补偿方法如下:

1) 提取$S_p$靠近$\mathit{\boldsymbol{Z}}$的局部笔段$T_p$和局部方向向量${\mathit{\boldsymbol{v}}_p}$

2) 将$S_p$${\mathit{\boldsymbol{v}}_p}$的方向往$\mathit{\boldsymbol{Z}}$延伸,直至与骨架相交,交点为$Q$

3) 对$T_p$$Q$构成的序列进行插值。

总结而言,本文的笔画段连接策略是连接互为最优匹配的连续笔画段,对不连续的笔画段进行适当延长补偿。图 7用以说明连接策略的合理性,图 7(a)为一处交叉区域的原始骨架,删除红色复杂区域后,$S_1$$S_3$被正确连接,若$S_2$$S_4$也得到正确连接,效果如图 7(b)所示。现假设$S_2$$S_4$未能构成最优匹配对,被视作不连续笔画段。根据延长补偿策略,将$S_2$$S_4$分别按其局部方向进行插值延长,如图 7(c)所示。虽然效果不如正确连接结果,但与原始骨架相比已有较为明显的改善。延长补偿策略保证了即使出现漏连接情况,笔画段也能得到一定程度的修正。

图 7 漏连接情况的修正
Fig. 7 Modification of missing connection
((a) original skeleton; (b) correct connection;(c) missing connection)

根据最优匹配关系连接笔画段并不能保证在骨架拆分时断开的全部笔画得到正确复原,且当复杂区域周围笔画段数量较多时(不少于5段),出现漏连接的情况会增加。但是,鉴于以下三点理由,本文认为该连接策略用于修复骨架仍然是有效合理的:

1) 对于手写汉字骨架的大多数复杂区域,笔画段的数量不超过4(实验样本中笔画段数量在2 4之间的复杂区域占94.1 %);

2) 漏连接情况对骨架修正造成的影响远小于误连接;

3) 延长补偿策略对漏连接的笔画段同样有较好的修正作用。

3 实验结果与分析

实验数据采集自20位书写者,样本图像由不同粗细和类型的笔,在不同种类的纸张上书写完成,总共含有600个中文字符,包括了绝大多数手写汉字可能出现的局部笔画形态。所有样本都经过二值化、去噪等预处理操作,在对原始图像进行归一化时,为了不影响汉字的整体结构比例,只对文字图像的宽度进行了统一。

3.1 复杂区域检测

根据本文算法,在使用传统细化算法得到骨架后,首先检测复杂区域。图 8所示是本文复杂区域检测算法与轮廓法[18]的对比实验效果。文献[18]通过分析笔画边缘的曲率突变点和轮廓线方向,直接从原始文字的二值化图像上检测复杂区域,而本文则直接对骨架进行检测。

图 8 复杂区域检测效果对比
Fig. 8 Comparison of complex zones detecting results

从对比中可以看出,本文算法检测出的复杂区域十分准确,虽然轮廓法也能检测出这些区域,但是大量笔画弯折区域也被标注出来。本文用单个汉字所包含的交叉形、丁字形和回笔形区域总数表示其理论复杂区域数量,在600个样本字符中,理论复杂区域数量为1 5的汉字分别占78个、89个、94个、102个和98个。表 1统计了采用两种不同方法检测这些汉字所得的平均复杂区域数量,由结果可知轮廓法检测所得的复杂区域数量约为理论值的2.5倍,出现了过度拆分现象。在后续进行笔画段连接时,轮廓法会耗费大量时间处理被误检测出的复杂区域。通过表 1中的对比能够得出结论,本文采用先细化后检测复杂区域的策略更为合理。

表 1 复杂区域检测数量对比
Table 1 Comparison of detected complex zones

下载CSV
方法复杂区域数量/(个/字)
理论值12345
轮廓法[18]2.575.267.449.1810.63
本文1.092.133.204.225.19

3.2 骨架修正

实验中,绝大多数骨架的形变部位都被很好地修正,汉字骨架的整体提取结果如图 9(a)所示,并与改进后的传统细化算法[13]进行对比。图 9(b)是骨架的局部修正效果对比,每组结果的左边采用文献[13]方法,右边则是经过本文修正算法处理后的骨架,不同笔画用不同深浅的颜色加以区分,可以看到修正前后的对比十分明显。

图 9 骨架形变修正效果
Fig. 9 Effect of skeleton distortion modification
((a) global effect; (b) modifications of local areas)

为了进一步评估骨架提取与修正效果,需要将所得骨架与标准骨架进行比对,得出准确率。根据细化算法原理,单笔形笔画的细化结果不存在形变,可以认为是理想的。因此,本文提取各复杂区域及其延伸部分,辅以人工操作,将笔画分离并单独细化,然后重新组合,替换原骨架中的对应区域,得到用于参考的标准骨架,如图 10所示。此骨架并不是严格意义上的标准骨架,但已十分接近理想情况,可以作为衡量骨架提取效果的参考标准。

图 10 获取标准骨架
Fig. 10 Acquisition of standard skeleton

骨架提取准确率等于重合骨架点数占标准骨架总点数的比率,若所提骨架与标准骨架完全一致,则所有骨架点均应重合。

表 2为本文骨架提取算法与文献[13]算法的准确率与处理速度。实验环境为CPU 2.80 GHz、内存8 GB的64位系统,图像宽度归一化至100像素。

表 2 准确率与处理速度对比
Table 2 Comparison of accuracy and processing speed

下载CSV
方法准确率/%处理速度/(ms/字)
文献[13]95.7235.19
本文98.4172.63

可以看出,所提方法在准确率方面有着较为明显的提升,说明骨架的形变部分得到了合理修正。虽然修正算法带来了额外的开销,但修正过程与多次迭代的细化过程运行时间相当,处于可以接受的范围内。本文对修正效果不佳的区域进行分析,发现当笔画宽度过宽时,笔画部分重合程度较为严重,导致细化与复杂区域检测效果下降。

4 结论

对于手写汉字图像的研究,骨架是分析的重点,然而细化算法带来的形变使得骨架上某些区域不能准确地反映出原始汉字结构的细节信息。本文提出了一种基于局部关联度的手写汉字骨架提取算法,与传统方法相比主要有以下创新之处:

1) 基于细化算法所得骨架检测复杂区域。首先对原始文字图像进行细化,通过骨架点分类和窗口扫描,检测出骨架上的复杂区域,然后根据复杂区域将骨架分成多段笔画段。

2) 利用局部关联度判断重组过程中笔画段间的连接关系。局部关联度由两部分组成,一是由局部方向间的余弦相似度所表示的方向关联度,二是由曲率变化程度所表示的曲率关联度。

总结而言,本文算法先通过复杂区域将骨架拆分、后基于局部关联度重组笔画段,从而修正传统细化算法带来的形变。实验结果表明,本文检测到的复杂区域数量十分接近理论值,相较轮廓法大幅减少了误检测情况,依靠局部关联度连接笔画段对骨架形变的修正效果较为明显,最终所得骨架接近理想情况。本文方法适用于笔画宽度正常、书写轨迹清晰的手写汉字,当汉字笔画达到一定宽度后,部分区域的处理效果不够理想,是所提方法的不足之处。下一步的研究计划中,考虑在本文方法的基础上加入轮廓信息,以处理笔画过宽的区域,并将所提骨架运用到汉字识别等具体场景中去。

参考文献

  • [1] Wang Y W, Fu Q, Ding X Q, et al. Importance sampling based discriminative learning for large scale offline handwritten Chinese character recognition[J]. Pattern Recognition, 2015, 48(4): 1225–1234. [DOI:10.1016/j.patcog.2014.09.014]
  • [2] Du J, Huo Q. A discriminative linear regression approach to adaptation of multi-prototype based classifiers and its applications for Chinese OCR[J]. Pattern Recognition, 2013, 46(8): 2313–2322. [DOI:10.1016/j.patcog.2013.01.021]
  • [3] Liu C L. Normalization-cooperated gradient feature extraction for handwritten character recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(8): 1465–1469. [DOI:10.1109/TPAMI.2007.1090]
  • [4] Vargas J F, Ferrer M A, Travieso C M, et al. Off-line signature verification based on grey level information using texture features[J]. Pattern Recognition, 2011, 44(2): 375–385. [DOI:10.1016/j.patcog.2010.07.028]
  • [5] Zeng J, Feng W, Xie L, et al. Cascade Markov random fields for stroke extraction of Chinese characters[J]. Information Sciences, 2010, 180(2): 301–311. [DOI:10.1016/j.ins.2009.09.011]
  • [6] Tan J, Lai J H, Zheng W S, et al. A novel approach for stroke extraction of off-line Chinese handwritten characters based on optimum paths[C]//Proceedings of International Conference on Frontiers in Handwriting Recognition. Bari, Italy:IEEE, 2012:786-790.[DOI:10.1109/ICFHR.2012.165]
  • [7] Lam L, Lee S W, Suen C Y. Thinning methodologies-a comprehensive survey[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(9): 869–885. [DOI:10.1109/34.161346]
  • [8] Wang J L, Guo C A. An improved image template thinning algorithm[J]. Journal of Image and Graphics, 2004, 9(3): 297–301. [王家隆, 郭成安. 一种改进的图像模板细化算法[J]. 中国图象图形学报, 2004, 9(3): 297–301. ] [DOI:10.11834/jig.20040354]
  • [9] Huang L, Wan G X, Liu C P. An improved parallel thinning algorithm[C]//Proceedings of the 7th International Conference on Document Analysis and Recognition. Edinburgh, UK:IEEE, 2003:780-783.[DOI:10.1109/ICDAR.2003.1227768]
  • [10] Su Z W, Cao Z S, Wang Y Z. Stroke extraction based on ambiguous zone detection:a preprocessing step to recover dynamic information from handwritten Chinese characters[J]. International Journal on Document Analysis and Recognition (IJDAR), 2009, 12(2): 109–121. [DOI:10.1007/s10032-009-0085-9]
  • [11] Bag S, Harit G. An improved contour-based thinning method for character images[J]. Pattern Recognition Letters, 2011, 32(14): 1836–1842. [DOI:10.1016/j.patrec.2011.07.001]
  • [12] You X G, Tang Y Y. Wavelet-based approach to character skeleton[J]. IEEE Transactions on Image Processing, 2007, 16(5): 1220–1231. [DOI:10.1109/TIP.2007.891800]
  • [13] Han J F, Song L L. An improved thinning algorithm for character image[J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(1): 62–66. [韩建峰, 宋丽丽. 改进的字符图像细化算法[J]. 计算机辅助设计与图形学学报, 2013, 25(1): 62–66. ] [DOI:10.3969/j.issn.1003-9775.2013.01.009]
  • [14] Plamondon R, Privitera C M. The segmentation of cursive handwriting:an approach based on off-line recovery of the motor-temporal information[J]. IEEE Transactions on Image Processing, 1999, 8(1): 80–91. [DOI:10.1109/83.736691]
  • [15] Yu Q, Nishiara M, Yasuhara M. A framework toward restoration of writing order from single-stroked handwriting image[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(11): 1724–1737. [DOI:10.1109/TPAMI.2006.216]
  • [16] He R, Yan H. Stroke extraction as pre-processing step to improve thinning results of Chinese characters[J]. Pattern Recognition Letters, 2000, 21(8): 817–825. [DOI:10.1016/S0167-8655(00)00039-8]
  • [17] Chiu H P, Tseng D C. A novel stroke-based feature extraction for handwritten Chinese character recognition[J]. Pattern Recognition, 1999, 32(12): 1947–1959. [DOI:10.1016/S0031-3203(99)00003-5]
  • [18] Liu X B, Jia Y D. An Algorithm of line-segment extraction and thinning for character images[J]. Journal of Image and Graphics, 2005, 10(1): 48–53. [刘峡壁, 贾云得. 一种字符图像线段提取及细化算法[J]. 中国图象图形学报, 2005, 10(1): 48–53. ] [DOI:10.11834/jig.20050110]