采用行程跟踪的二值图像去毛刺算法

钟伦超， 何 川

(1.黄山学院 教务处，安徽 黄山 245041；2.黄山学院 信息工程学院，安徽 黄山 245041)

自1967年Blum提出骨架的概念以来，曲线骨架提取成为多领域研究的热点。例如指纹识别方法通常是在对原始图像进行一系列预处理之后，利用细化处理得到图像骨架，然后进一步运用其中的细节特征点（起点、终点、结合点和分叉点）进行指纹鉴别。二值图像细线化技术在图像分析与形状描述中是一个非常重要的变换，骨架是图像几何形态的重要拓扑描述，是进行图像目标的特征提取[1]、模式识别[2]等应用的前提，在很多研究领域及生产生活中应用广泛，主要用于字符识别[3]、指纹识别[4]、工程零件骨架结构识别提取[5]等，通过图像的细化处理将图像中的需要识别的部分进行细化，可以很清晰地得到需要的图像“骨架”，提取出所需目标物的单像素轮廓。但是，图像细线化带来的问题是处理后的图像在此“骨架”的线段分段处产生多余的点和线段，我们把这些多余的点和线称为“毛刺”[6-8]。

毛刺在图像中是多余的，并且会影响图像主要部分的使用。针对去毛刺过程可能存在去除图像结构主体部分的缺陷，宁亚辉等人提出改进的基于模板去除骨架毛刺方法[9]。该方法首先对目标点周围像素进行统计，找到对应像素符合的类型，再结合传统去毛刺方法中的毛刺长度设定，对毛刺进行去除。郭斯羽等人提出一种植物叶片图像骨架提取的去毛刺方法[10]，通过设定的两个指标对骨架上的毛刺进行判断和去除。安世全等人提出一种基于Zhang并行细化算法进行细化，在其基础上通过改进的毛刺消除算法满足保留较长分支为骨架主体信息的原则，最大程度地保持裂缝骨架主体信息[11]。实验结果表明上述文献提出的方法都可以减少图像噪声和毛刺，但是无法保证图像的有效部分的完整性。通过大量的实验程序编写及测试，提出去毛刺算法，针对毛刺的存在问题，利用细化图像中的交叉点和端点来确定毛刺的位置，通过端点对交叉点进行搜索，存储搜索路径，记录该跟踪路径的方向链码，通过设定毛刺长度门限值对毛刺部分进行去除，得到效果满意的细化图像。

1 去毛刺算法描述

基于行程跟踪的去毛刺算法，实质上就是对目标像素的邻近像素进行扫描，以目标像素为起始点对毛刺部分进行追踪，通过事先设定好的长度门限，定义毛刺的长度，判断毛刺位置，从而进行有效去除。通过对毛刺的特性进行分析，可以得出毛刺介于交叉点和端点之间，扫描毛刺的方式有两种：（1）以端点作为起始点，通过行程跟踪在其设定长度门限范围内寻找交叉点，定义毛刺长度，从而找出毛刺所在；（2）以交叉点为起始点，对其连通域内的8-邻域像素进行像素值判断，并通过路径跟踪以及毛刺长度，判断出毛刺位置。本文仅详细介绍以端点为起始点寻找其连通域内的交叉点，进行毛刺的检测和标记存储并有效去除。

算法步骤：首先判断给定的图像是否为二值图像，如果不是，对原图像进行二值化处理，此时的图像可能存在很多噪声点，对图像进行去噪及一系列形态学预处理，然后对给定进行细线化操作，得到初步的图像目标物骨架，细线化处理的图像会产生很明显的毛刺现象。通过行程跟踪对毛刺像素进行检测和标记存储，再对其进行有效去除，得到轮廓光滑且目标物结构不变的新图像。

（1）对原图进行去噪等预处理，采用MATLAB软件自带的二值化函数对给定图像进行二值化处理，得到二值图像；

（2）对得到的二值图像进行细线化处理，得到像素宽度为1的目标物轮廓图，从而提取出图像目标物特征骨架；

（3）通过扫描，寻找到图像中所有的端点和交叉点，对端点和交叉点进行标记并存储，设定毛刺长度门限值L，以端点为起始点在其连通域内进行目标物行程跟踪，直到寻找到交叉点，终止运算，存储行程中的每一个像素点。如果跟踪的步数M小于设定的毛刺门限值L，则该段路径为毛刺；反之，跟踪步数大于设定的毛刺长度L，则默认该段路径为图像的有效结构；

（4）通过步骤（3）确定毛刺后，根据行程跟踪过程中存储起来的像素点，将符合毛刺定义的端点和其对应的交叉点之间的像素去除；

（5）得到清晰的图像骨架，结束运算。

算法流程如图1所示。

图1 去毛刺算法流程图Fig.1 Flow chart of deburring algorithm

2 二值图像转换及图像骨架的提取

采用MATLAB R2015a软件DIP工具箱函数im2bw使用阈值变换法把灰度图像转换成二值图像：

式中：I为原图像；J为转化后的二值图像。

随即采用bwmorph函数对原二值图像进行细线化处理，提取图像中目标物的骨架：

式中：J为二值图像；运算次数n为12；H为骨架图像。

3 毛刺的定义

3.1 端点、交叉点及毛刺模型

为了确定细线化所引起的毛刺的位置所在，需要先找到产生毛刺的根源，即交叉点和端点。不难发现，毛刺一定是始于交叉点且止于端点，存在于端点和交叉点之间。如图2所示，对端点、交叉点和毛刺作形象说明。

图2 端点、交叉点和毛刺示意图Fig.2 Diagram of endpoints,intersections and burrs

图中，可以看到A点和B点处在交叉位置，则定义A点和B点为交叉点，C、D、E3点为端点，从图中可以看出，毛刺存在于端点和交叉点之间，则a、b、c3段都有可能是毛刺，但是考虑到有些毛刺可能是图像的有效部分，不可去除，例如c段。因此，我们需要设置毛刺的长度，合理地对毛刺进行去除，保留图像的有效部分。

3.2 端点、交叉点标记及存储

3.2.1 端点

规定目标像素为黑色，像素值为1，背景色像素值为0。设N8(P0)为P0的8个邻域中数值为1的像素个数。当P0=1，N8(P0)=1，即目标像素为黑色，它的8个邻域中仅有1个点为黑色，则P0为端点，如图3所示，P0为扫描到的目标像素。当P0的3×3邻域满足(a)～(h)8种情形中的任意一种时，则P0为端点。此时我们对P0点进行标记并存储。

图3 满足端点性质的P0邻域像素分布Fig.3 The P0 Neighborhood pixel distribution satisfying the endpoint property

3.2.2 交叉点

如果当前扫描到的目标像素P0，像素值为1，我们定义，当P0=1，3＜N8(P0)时，该点为交叉点。我们可以从图5看出，如果P0点的8-邻域中仅有两个点像素值为1，则该点为线段中一点，不能视为交叉点。当P0点的8-邻域中有三个或超过三个点像素值为1，则该点为交叉点，即为毛刺产生点。如图4为文字识别细线化的图像，可以看出，该图中有6处交叉点。标记所有的交叉点，并进行存储。

图4 交叉点示意图Fig.4 Cross point diagram

3.3 毛刺定义

通过大量研究可知，毛刺必然存在于端点和交叉点之间，因此，对端点和交叉点进行标记和存储，并对每个端点和对应的交叉点进行编号，使得从某一端点进行行程跟踪后，对其连通域内寻找到的交叉点进行对应，确定毛刺的位置，但是并不是所有的端点和交叉点之间的线段都是毛刺，我们通过限制毛刺长度门限来定义毛刺，确保图像有效部分不被剔除。

4 基于行程跟踪的毛刺去除

4.1 行程跟踪

扫描全图，以扫描到的端点P0为起始点，跟踪P0的8-邻域，如果扫描到黑色点，则将该黑点存储起来，再以该黑点为起始点进行扫描，则继续扫描如图5所示，图(b)为图(a)的部分像素分布图。

图5 毛刺像素分布示意图Fig.5 Schematic of burr pixel distribution

图为8×8的区域，0代表黑色像素点，1代表白色像素点，跟踪示意图如框图6所示。（1）从端点（2,2）开始搜索，根据交叉点定义，（4,4）点为交叉点，结束运算，该段路径可能为毛刺；（2）从端点（2,7）开始搜索，直到交叉点（4,5）结束搜索，该段路径也可能为毛刺。（3）存储两段路径的所有有效点。

图6 毛刺跟踪流程图Fig.6 Flow chart of burr tracking

4.2 毛刺去除

设定毛刺长度门限值L，标记存储细线化图像的所有端点及交叉点，其次判断P0点的8-邻域像素值为1的个数：如果N8(P0)=0，则该点为孤立点，结束运算；如果N8(P0)=1，则P0为端点，进行跟踪，此时步数M=1，M=M+1，再以P0的8-邻域内的点作为起始点，进行跟踪，直至寻找到起始点连通域内的交叉点，结束运算。若M＞L,即搜索路径长度大于毛刺长度门限值，停止运算；若M＜L，直至找到最近的交叉点。此时将存储的起始点与寻找到的交叉点一一配对；如果搜索步数小于L，则该段路径为毛刺，去除端点和对应的交叉点之间的像素；反之，该段路径为图像有效结构，不做处理。

4.3 实验过程分析

如图7(a)为一张简单的线段图，通过此图像的操作来体现文中算法的处理结果。利用细线化技术对其进行骨架图像提取，图7(b)为细线化带有毛刺的图像，此时，标记存储图(b)中所有的交叉点和端点，如图(c)(d)分别为提取的交叉点和端点，通过以端点为起始点搜寻其连通域内的交叉点，并存储搜索路径中所有的白色像素，通过路径步长M和定义的毛刺长度L进行比较，去除符合毛刺定义的路径内的所有像素即可，毛刺处理效果如图7(e)所示。

图7 行程跟踪去毛刺算法处理效果Fig.7 Processing effect of stroke tracking deburring Algorithm

5 实验结果仿真与分析

为了更好地验证基于行程跟踪的去毛刺算法在实际应用中的效果，以车牌骨架提取和文字骨架提取为例，对处理前后的图像进行对比，分析去毛刺算法的特点和优势。

图8(a)为车牌的原始彩色图像；图8(b)为车牌二值化并取反的图像；图8(c)为二值图像的细线化处理图像，可以清晰的看出，图像中出现了很多影响图像美观的毛刺，这些毛刺有的存在于线段中部，有的存在于线段尾部，这两种情况的毛刺都是产生于交叉点，结束于端点；图8(d)为本文算法处理的结果，通过与图(c)进行比较，我们可以得出，本文基于行程跟踪的去毛刺算法对处理细化图像中的毛刺有着明显的效果。

图8 车牌骨架提取去毛刺效果图Fig.8 The deburring effect diagram of license plate skeleton extraction

图9为文字骨架提取过程中毛刺去除过程。图9(a)为汉字“中国”二值化后的图像；图9(b)为车牌细线化处理图像，处理结果带来了很多毛刺；图9(c)为本文算法处理的结果，毛刺被有效去除。通过实验结果可以看出，“国”字右下角延伸出来的“横”并没有被当成毛刺去除，可见本文算法有效保证了图像的骨架完整性。

图9 文字骨架提取去毛刺效果图Fig.9 Image of text skeleton extraction deburring

图8(d)和图9(c)的实验结果是在Intel(R)Pentium(R)CPU G2030(3.00 GHz)、内存4G的微机上采用MATLAB R2016b软件编程实现的，算法运行时间分别为643和596 ms，完全满足图像处理在实际应用中的时间要求。

6 结束语

二值图像细线化算法应用广泛，其运算结果不可避免会产生影响图像质量的毛刺。本文提出基于毛刺行程跟踪的去毛刺算法，通过分析毛刺的规律、特点、性质，运用交叉点和端点定位毛刺，对细线化图像中毛刺的有效去除。该算法能够在不改变图像连通性条件下，保持图像有效部分的基本骨架，同时有效去除二值图像细线化处理带来的毛刺，改善了图像视觉质量。