基于方向约束的文字骨架毛刺去除算法

范 静，颜廷秦，崔 鸣，薛知言

（苏州市职业大学 电子信息工程学院，江苏 苏州 215104）

图像骨架提取在图像特征提取、模式识别等领域具有广泛的应用[1]。文字骨架提取是文字识别过程的重要环节。提取文字骨架往往要求有三个基本特性：连续性、单像素性、中心性，并且能够完整地表现出文字的基本结构、笔画等特征。在骨架提取的过程中，由于提取方法的不同以及噪声的干扰，都会产生不同程度的毛刺[2]。毛刺的出现会影响后续的文字识别结果，影响识别率。

1 文字骨架毛刺去除方法及特点

文字骨架毛刺去除方法大致可以分为以下4种：①优化骨架提取方法，从而达到去除毛刺的目的[3-4]，但并不普遍适用。②基于模板的毛刺去除方法[5]。③基于区域重构的毛刺去除方法[6]，利用骨架显著性指标进行阈值化处理，计算量很大。④通过毛刺长度阈值判别毛刺[7-8]，而不考虑主干与分支的连续性，有可能会误删有效分支（主干），并且在节点的判断上仅仅考虑了两种节点的情况，未考虑节点冗余情况，并不具有普适性。

常用的ZS细化算法[9]、LW细化算法[10]、K3M细化算法[11-12]的文字骨架提取效果如图1所示。

图1 不同细化算法的文字骨架提取效果

由图1可知，不同细化算法的文字骨架提取效果均具有毛刺；毛刺与主干相比长度较短；毛刺与主干呈一定方向的夹角。

针对阈值法删除毛刺会出现节点冗余以及误删骨架本身的情况，本研究在阈值法的基础上，具有以下创新点：①增加了节点冗余去除模板，使骨架节点更清晰，适用于所有文字骨架，链码跟踪更准确。②在链码跟踪时不是一味地从节点向端点跟踪编码，而是预分类主干和毛刺，并对其分类编码，便于计算主干与毛刺的方向夹角。③重新标定了方向链码，解决了链码首尾的不连续性，据此计算方向夹角。④在长度阈值的基础上，增加了根据夹角阈值选择性删除毛刺，提高了毛刺删除的准确率。

2 毛刺与端点、节点的关系

去除毛刺的关键是找到毛刺线段，并将其转化为背景色。主干毛刺示意图如图2所示。图2中的线段bc和df应为毛刺，毛刺共同点是起始于与主干的交叉点（b、d），终于端点（c、f）。在连续的单像素骨架中找到交叉点和端点是去除毛刺的第一步。

图2 主干毛刺示意图

2.1 端点与节点的定义

这里规定背景像素值为0，骨架像素值为1。理想的骨架像素应该在8邻域中只有2个骨架像素与之相连接。

定义1一个像素的8邻域中有且只有一个像素为1的点，则定义此点为端点。

定义2一个像素的8邻域中有3个或3个以上像素为1的点，则定义此点为节点（交叉点）。

定义3N（P）为P（x，y）点8邻域中像素为1的点的个数。

将原始图像image1转存为image2，扫描像素点，当像素点的8邻域满足端点或节点的定义时，在image2中分别对其进行标记并记录坐标值为

2.2 节点冗余去除模板

根据节点的定义，将满足条件的骨架像素标记为4，则可能会出现节点冗余的情况，形成肿块，如图3所示。肿块现象会影响后续的链码跟踪，所以这里引入节点冗余删除模板，如图4所示。将冗余的节点还原标记为默认骨架1。

图3 节点冗余

在图4模板中，0代表背景像素点，1代表骨架像素点，X代表任意值，不影响删除模板的判断。在image1中根据节点坐标遍历节点，当节点的8邻域像素点满足节点冗余删除模板条件，则在image2中将其8邻域内已标记的冗余节点还原为默认骨架，如表1所示。若image1中某P点满足冗余条件，则将image2中对应的Pi替换成1。

表1 删除image2中的冗余节点

图4 节点冗余删除模板

3 基于方向约束的链码跟踪方法

3.1 链码跟踪

链码跟踪是利用起始点和跟踪点的方向码来描述曲线的延伸方向。常用的链码跟踪有8连通链码和4连通链码，本文使用的8连通链码如图5所示。单像素连续骨架图如图6所示。

图6 单像素连续骨架图

3.1.1 利用8连通链码跟踪骨架

根据定义P0（3,3）、P1（8,8）是节点，P2（6,10）、P3（10,10）是端点。从节点P1开始行程跟踪，并标记跟踪过的像素，直到跟踪到下一个节点或者端点，共跟踪到三条分支。骨架链码跟踪如图7所示。

图7 骨架链码跟踪

骨架在方向编码时分为两类：

1）节点跟踪到节点，预分类为主干。主干在编码时方向为终点到起点；

2）节点跟踪到端点，预分类为分支。分支在编码时方向为起点到终点。

如：P1→P0主干，根据8连通链码，得到链码为77777。

P1→P2分支，根据8连通链码，得到链码为11。

P1→P3分支，根据8连通链码，得到链码为77。

3.1.2 计算分支长度

分支长度可以利用已得到的8连通链码来计算。Ne为偶数链码的个数,No为奇数链码的个数,Nc为链码方向发生变化的个数，则链码长度L为

其中：A=1；；C=0。由此可得，P1到P2分支的长度;P1到P3分支的长度。

3.2 方向约束

若仅通过分支长度是否小于毛刺阈值来判断毛刺，可能会造成分支的误删。比如，若毛刺阈值,则线段P1P2、P1P3都将被删除。但线段P1P3与骨架主干的延伸方向一致，是骨架的一部分而并非毛刺，此时，需要引入方向约束。

方向约束是将毛刺的延伸方向与主干的延伸方向的夹角，与预先设定的角度阈值进行比较，当分支与主干夹角大于角度阈值时，则此分支定义为毛刺。方向夹角可转化为方向链码差实现，如0方向和1方向链码差为1。注意，虽然1方向和7方向与0方向的夹角均为45°，但是链码差是不相同的，分别为1和7。在计算链码差前，需将链码重新标定为

式中：MN为新链码值；MO为原链码值。计算节点引出的各分支与主干的2到3个链码均值，将分支的链码均值与主干的链码均值相减，若此分支链码差大于链码角度阈值，则判别为毛刺。

3.3 毛刺去除的方法

毛刺去除的算法如图8所示。其步骤如下：

图8 毛刺去除算法

1）遍历骨架元素，根据端点、节点的定义分别标记并记录其坐标，利用节点冗余模板，删除冗余的节点标记和坐标。

2） 从节点开始，对各分支进行链码跟踪，并记录分支坐标。若分支跟踪到的结束点为节点，则将此线段分类为主干，并从结束点向开始节点方向进行方向编码；若分支跟踪到的结束点为端点，则将此线段分类为分支，并从开始节点向结束点方向进行方向编码，计算分支链码长度。

3） 将同一节点引出的分支链码长度与毛刺长度阈值进行比较。若分支长度小于长度阈值，则进行下一步；若各分支均大于长度阈值，则计算下一个节点。

4） 对主干和分支的链码重新标定，并计算各分支与主干的链码差，若链码差大于链码角度阈值，则认定此分支为毛刺，并将其删除。

5）若各节点遍历结束，则输出图像。

4 实验结果与分析

4.1 实验效果

为了验证方向约束对文字骨架毛刺的去除效果，实验采用的原始图像为细化之后的连续单像素文字骨架，然后使用本文算法进行毛刺去除处理。本实验中角度阈值Cth=0.95。设图像的短边长为Lma，则毛刺的长度阈值为

式中n可根据文字的实际情况调节大小。

例1.“永”字的骨架毛刺去除效果，如图9所示。图9 (a)为已通过细化的“永”字骨架；图9(b)为仅通过长度阈值来删除毛刺的效果；图9(c)为在长度阈值判别毛刺的基础上加入了方向约束删除毛刺的效果。

由图9可以看出，原始图像在“永”字的勾和捺处有两处毛刺，仅仅通过毛刺长度阈值删除毛刺，误删了文字本身骨架（捺处的文字骨架），通过方向约束可以有效地保护文字本身骨架，毛刺删除效果更佳。

图9 “永”字的骨架毛刺去除效果

例2.“波”字的骨架毛刺去除效果，如图10所示。

图10 “波”字的骨架毛刺去除效果

由图10可以看出，经过比较，仅通过长度阈值比较会删除“波”字的点、撇和捺处的骨架，见图10（a）已圈出部分，而方向约束可以保留这三处骨架，使文字骨架更完整。

例3.多文字骨架毛刺去除效果，如图11所示。

图11 多文字骨架毛刺去除效果

由图11可以看出，方向约束法可以很好地去除文字毛刺，并完整地保留了文字本身的骨架，为后续的文字识别提高了可靠性。

4.2 实验结果的比较分析

本实验将100组分辨率为150×150的文字图片进行骨架化去毛刺处理，从运行时间以及删除毛刺效果两个方面对阈值法和方向约束法进行了对比。两种算法运行时间对比如表2所示。两种算法删除毛刺效果对比如表3所示。

表2 两种算法运行时间对比 /s

表3 两种算法删除毛刺效果对比

由表2可知，阈值法由于并未对毛刺方向进行计算，所以运行时间略短于方向约束法，但是并没有显著的差异。

由表3可知，阈值法共删除了367条毛刺，方向约束法通过方向性共删除了341条毛刺。通过人工判别，方向约束法共保留了阈值法删除保留的26条骨架中，22条为文字本身骨架（阈值法错误删除），4条毛刺由于与主干夹角较小被错误保留；两种算法均错误删除了6条骨架，阈值法除此之外，还错误删除了方向约束法保留的22条文字本身骨架，共错误删除28条骨架。从删除和保留的准确率来看，方向约束法提高了删除毛刺的准确率，效果明显。

5 结论

1）针对文字骨架的提取，提出了一种基于方向约束的链码跟踪毛刺去除方法。在节点的判断上引入节点冗余模板，更好地判断了骨架节点，防止节点冗余现象。在毛刺长度阈值判断的基础上，通过毛刺延伸方向与主干延伸方向的夹角阈值来判别毛刺，特别当文字骨架延伸段长度与毛刺长度相似时，骨架容易被错误去除。实验结果表明，此方法能很好地去除毛刺并保留文字骨架，效果良好。

2）对于毛刺长度阈值，本文通过图像短轴的实际情况调节，并未考虑文字本身的骨架主干长度，有待进一步研究。