基于二值图像的手写体快速细化算法*

曹良斌，游莉萍，刘笔余，张轩宇，周恺卿，莫礼平

(吉首大学信息科学与工程学院，湖南 吉首 416000)

从实际环境中切分出的手写体字符图像常伴随着边框粘连、随机污点、光照不均匀等现象，因此在应用识别算法处理手写体图像前，往往需要对手写体字符图像进行预处理操作[1-2].手写体细化是图像预处理的主要步骤之一，其实质是求手写体骨架的过程[3].手写体细化算法通过保留图像中与字符有关的信息来提取字符特征[4-7]，从而确保输出的二值图像画面清晰、边缘明显.笔者针对查表算法的缺点，提出一种充分利用手写体节点的快速细化算法，以期达到减少模板数量、缩短匹配过程耗时、优化细化结果的目的.

1 常见的手写体细化算法

1.1 中轴变换算法

图1 基于中轴变换算法的细化结果Fig. 1 Thinning Result Baded on Medial Axis Transformation Algorithm

目前，常用的手写体细化算法主要分为中轴变换算法、找中点算法和查表算法[8-9].中轴变换算法主要是计算手写体笔划线上的内部像素点P到边界像素点的距离d.若存在2个以上的边界点到点P的距离最小，则令点P为一个骨架点，所有的骨架点即可组合为骨架.基于中轴变换算法的手写体细化结果如图1所示.中轴变换算法的主要缺点是：算法复杂度过高；同一个笔划中可能出现多个骨架线；对原图的清晰程度要求非常高；细化结果受噪声影响较大；细化输出的骨架在节点处可能出现断线，不能保证线条的连通.

1.2 找中点算法

找中点算法主要是通过逐行(或逐列)扫描图像，找出每一行(列)的连续像素点，并将像素点的个数记为H(n).若H(n)为奇数，则取该行(列)中心的点为细化结果；若H(n)为偶数，则取中间的左点或右点(上点或下点)为该行(列)的细化结果.找中点算法的优点是原理简单和运行速度快，主要缺点是无法准确细化笔划较粗的手写体，以及无法保证细化结果的连通性.

1.3 查表算法

设手写体一黑色像素点为P，点P的8邻点为n0～n7，如图2所示.在查表算法中，根据点P的8邻点的像素取值情况判断其是否为骨架点.判断规则是：(1)删除的点不能影响图像中各分量的拓扑邻接关系，即连通性；(2)骨架点需保留原始图像的基本信息.在手写体二值图像中，任取一点P为中间点，黑色图形像素点取值为1，白色背景像素点取值为0.根据邻点情况判断节点能否删除.

n7n0n1n6Pn2n5n4n3

图2点P的8邻点

Fig.2EightAdjacentPointsofPointP

现举例说明.设点P的8邻点情况如图3所示.根据邻点的情况判断节点能否被删除：图3a中，点P不能被删除，因为它是内部点，删除后骨架无法连通；图3b中，点P不能被删除，因为删除它会导致左右点断开，骨架无法连通；图3c中，可以删除点P，因为它不是骨架点，删除后不影响输出骨架的连通性.

0001P1000a例10101P1011b例20100P1000c例3图3 P点的邻点情况Fig.3 AdjacentPointsofPointP

因为点P的邻点取值为0或1，8邻点有256种组合方式，所以查表算法相应地需要处理256个模板.查表算法的优点是清晰简洁，主要缺点是：需要256个模板，前期准备工作烦琐；执行过程中需依次匹配256个模板，耗时多，效率较低；非骨架像素点不一定能被删除.

2 改进的手写体细化算法

2.1 算法相关说明

给定一黑色像素点P，坐标为P(x,y).点P的4邻点分别为点集n2(x+1,y),n6(x-1,y),n4(x,y-1),n0(x,y+1)；8邻点分别为点集n3(x+1,y-1),n4(x,y-1),n5(x-1,y-1),n6(x-1,y),n7(x-1,y+1),n0(x,y+1),n1(x+1,y+1),n2(x+1,y).8邻点中取值为1的黑色像素点的个数为N(P).点P的8邻点和4邻点如图4所示.

n7(x-1,y+1)n0(x,y+1)n1(x+1,y+1)n6(x-1,y)P(x,y)n2(x+1,y)n5(x-1,y-1)n4(x,y-1)n3(x+1,y-1)

图4点P的8邻点和4邻点

Fig.4EightAdjacentPointsandFourAdjacentPointsofPointP

2.2 算法思想及流程

改进的手写体快速细化算法，需先建立一张合理的索引表来记录哪些情况可以标记点P，哪些情况不可以标记点P.算法思想：扫描手写体二值图像，将二值图像中的点P及其邻点情况与索引表匹配，根据匹配结果来判断点P是否被标记；二值图像中的点P都被扫描完后，统一删除所有的标记点；执行删除步骤后，对二值图像进行新一轮的扫描，循环反复，直到扫描过程中没有任何一点被标记，此时剩下的点就是骨架点；将骨架点与优化骨架宽度模板匹配，进一步减小骨架宽度.算法流程如图5所示.

图5 算法流程Fig. 5 Algorithm Procedures

2.3 算法步骤

(ⅰ)对于手写体二值图像中的每一个黑色像素点P，根据以下规则判定点P是否被标记：

(1)若N(P)=0，1，8，则标记点P.

(2)若N(P)=2，5，6，且点P的邻点是连续的(如图6所示，邻点n0，n1，n5，n6，n7取值为1，其余点取值为0)，则标记点P，否则不标记.

1111P0100

图6N(P)=5,邻点n0,n1,n5,n6,n7连续为1时的匹配模板

Fig.6MatchingTemplatewithN(P)=5andAdjacentn0,n1,n5,n6,n7being1

(3)若N(P)=3，点P能够与图7中任一模板匹配，则标记点P.

0100P10011100P10000111P00000101P0100图7 N(P)=3时的匹配模板Fig.7 MatchingTemplatewhenN(P)=3

(4)若N(P)=4，点P能够与图8中任一模板匹配，则标记点P.

0111P01001100P1001图8 N(P)=4时的匹配模板Fig.8 MatchingTemplatewhenN(P)=4

(5)若N(P)=7，点P的4邻点有任意一点取值为0，且点P能够与图9中任一模板匹配，则标记点P.

1011P11111110P11111111P01111111P1101图9 N(P)=7,4邻点有任意一点取值为0时的匹配模板Fig.9 MatchingTemplatewhenN(P)=7andanyoftheFourAdjacentPointsis0

(6)若点P能够与图10中的任一模板匹配，则不标记点P，以保持线条的连通.

x0x1P1111x0xx001100P000x00000P1101100000x000P001100x

x0000P10001xx11x0P10x11x000x01P0x100图10 保证线条连通的匹配模板Fig.10 MatchingTemplateGuaranteeingLineConncetion

(ⅱ)若图像中所有点P都未被标记，则执行步骤3；否则令所有被标记的点P取值为0，返回执行步骤1.

(ⅲ)为减小骨架宽度，检查图像中的每一个点P.若点P能够与图11中任一模板及它们分别旋转90°,180°,270°所得的模板匹配，则令点P取值为0，算法结束.

01x1P0x00x1x1P1x0x图11 优化后减少像素的匹配模板Fig.11 MatchingTemplateofPixedDecreaseAfterOptimization

2.4 算法分析

该算法简化了查表算法的256个模板，并剔除了一些不必要的模板.根据算法的规则，需从查表算法的256个模板中选择44个标记模板用于判断像素点P是否被标记，并且增加了15个优化模板用于改进原查表算法骨架不唯一、骨架宽度过大的缺点.相比于传统的查表细化算法，手写体快速细化算法不再一一遍历P点周围的邻点，而是根据N(P)值进行相应的分类与匹配，使得算法具有细化速度快，细化结果准确的优点.

3 实验结果及讨论

3.1 算法细化效果验证

图12示出对给定的一个字符按照手写体快速细化算法步骤进行细化操作的效果.对比原字符和细化效果发现，细化后的图像保留了基本骨架，没出现断点、毛刺等情况，显示了良好的细化效果.

图12 手写体快速细化算法效果验证Fig. 12 Effect Verification of the Fast Thinning Algorithm of Handwriting

3.2 软件运行效果

在Visual Studio 2013软件中利用C#语言实现手写体快速细化算法.图13示出用户在软件中手写输入的小写字母、大写字母、数字经运行算法后的细化效果.对比原字符和细化效果发现，该算法能准确细化小写字母、大写字母、数字等图像，且完好保留手写体骨架.

图13 软件运行效果Fig. 13 Software Operation Effect

4 结语

通过分析手写体节点与周围像素邻点的相对位置，提出了一种手写体快速细化算法.算法继承了查表算法清晰简洁的优点，并在查表算法的基础上，整理和简化了冗杂的模板，选择更具有代表性的模板作为标记样本，减小了问题规模，降低了算法复杂度.实验结果表明：改进的手写体细化算法完好地保留了手写体骨架，字符特征被完好地提取出来；细化结果边距明显、无粘连边框，能较好地应用于文字识别、图像处理和模式识别等领域.

[1] 姜 文，刘立康.基于联合两种特征的手写体维文字符识别[J].计算机工程与应用，2017，53(5)：192-196.

[2] 牟少敏，杜海洋，苏 平，等.一种改进的快速并行细化算法[J].微电子学与计算机，2013,42(1):53-55.

[3] 赵丹丹,王华彬,陶 亮,等.改进的EPTA并行细化算法[J].计算机工程与应用，2016,52(9):196-201.

[4] 韩建峰，宋丽丽.基于算法运算的改进细化算法[J].现代电子技术，2013，36(14)：13-16.

[5] 薛玉利，彭玉华，周新虹.基于实值Gabor变换的掌纹识别[J].计算机工程与应用，2007,43(6):216-219.

[6] 康文雄，邓飞琪.利用模板和邻域信息的静脉骨架提取新算法[J].中国图象图形学报，2010，15(3):378-384.

[7] STERNBY J,MORWING J,ANDERSSON J,et al.On-Line Arabic Handwriting Recognition with Templates[J].Pattern Recognition,2009,42(12):3 278-3 286.

[8] 贺继刚，杨晓伟，吴广潮，等.基于模板保留的快速并行细化算法[J].计算机应用与软件，2007，24(12):26-28.

[9] 王家隆，郭成安.一种改进的图像模板细化算法[J].中国图象图形学报，2004，9(3):297-301.