一种基于像素标记的二值图像区域围线追踪方法

陈兆学， 张 奎

（上海理工大学 医疗器械与食品学院，上海 200093）

在图像处理、计算机视觉以及模式识别等研究领域中，通常需要对目标区域的边界信息进行分析，如边界曲率、边界长度、链码及凹凸度等参数，围线追踪就是用来获得目标区域的这些特征信息的有效方法[1-3]。在激光平面雕刻中，图像目标区域的围线追踪同样十分必要。为了解决传统的直线式扫描带来的一系列缺点，如雕刻边缘易出现锯齿现象、频繁关断造成激光头寿命受影响等，以图像区域围线追踪为基础的螺旋扫描技术显得十分有必要。如果激光头始终沿着图像边缘行进，那么，连续的光刻槽形成的包络将消除图像边缘处的锯齿[4]。这些沿着图像边缘行进所形成的轨迹即认为是图像当前区域的围线，组合起来可认为近似构成螺旋形结构。

在现有的围线追踪算法中，很多算法在追踪某些形状的区域围线时往往会出现错误[1,5]。文献[4]虽然给出了一种用于生成螺旋扫描线的围线追踪方法，但该方法只能处理结构较为简单的图像，也没有考虑追踪过程中易出现的特殊问题，抗噪性能较差，不能直接用于工业生产中。文献[6]提出了一种基于边过程的图像区域围线追踪算法，虽然计算复杂度是线性的，但时间复杂度相对较高。在一些基于像素的围线追踪算法中，一般采用边界像素来表示围线，例如，Square Tracing，Moore-Neighbor Tracing，Radial Sweep和Theo Pavlidis算法。但由于某些特定区域存在单像素宽度的情形，导致这些围线追踪算法在这些区域的特定区段追踪时容易产生遗漏或提前终止的情况[6]。本文在文献[4]的算法基础上提出了一种改进的基于像素点多次标记[7]的二值图像区域围线追踪方法。通过定义特定追踪方向，使得追踪过程始终按照逆时针或顺时针方向沿着连通区域边缘行进[8]。在追踪过程中对像素点进行多次标记，通过在按照追踪方向确定的像素点基础上判断像素标记值来确定下一次追踪像素点的选取。由于对像素点进行多次标记，有效区分了一次追踪像素点和二次追踪像素点，解决了追踪过程中出现的追踪间断现象[9]，使得追踪结果呈现一条完整围线。实验结果表明，本文方法可以快速有效地完成二值图像连通区域的围线追踪和提取。

1 二值图像区域围线追踪算法

1.1 二值图像“尾巴点”的定义

定义 如图1所示，不参与形成封闭轮廓的且与构成轮廓像素发生黏连关系的一类像素，将其定义为“尾巴点”。若采用现有的围线追踪方法[4]追踪到该类点时，由于无跳出尾巴点的有效措施，导致提前终止追踪。本文所设计的像素点追踪算法将设法有效跳出“尾巴点”，最终追踪出完整的围线。

图 1 “尾巴点”示意Fig.1 Diagram of tail points

1.2 基于像素标记的二值图像区域围线追踪

基于像素点的二值图像区域围线追踪实际上是从目标区域某一边缘像素点出发，按照逆时针或顺时针方向不断搜寻后续边缘点，从而形成一条完整围线的过程。文献[4]中提出的围线追踪方法是基于某点P周围8个方向的优先顺序（如图2所示）来判断后续追踪点的选择。该方法能够很好地将简单区域的边缘轮廓按照逆时针的方向追踪出来，但是，对于较为复杂的图像忽略了一些容易出现的特殊情况（如“尾巴点”的存在），直接造成追踪陷入无限循环或追踪提前终止，抗边缘噪声能力较低。针对该算法的不足之处，本文给出了改进后的完整算法。

图 2 后续点方向选择优先级示意Fig.2 Diagram of the prioritization of subsequent points direction

算法步骤：

步骤1 对二值图像进行扫描，扫描到的第一个目标点设为当前点[10]，记录坐标值并将标记值设为，定义方向因子d=0，像素值转换因子s=0，算法结束标志t=0。

步 骤 2 令 方 向 因 子 d=mod （d+5，8），mod（a，b）表示求a除以b的余数，判断该方向上的点是否为目标点且未被标记，若是，则记录坐标值且标记值设为，该点设为当前点，重复步骤2，否则，令s=1，进行下一步。

步骤3 令方向因子d=mod （d+5，8 ），判断该方向上的点是否为目标点且未被标记，若是，则记录坐标值且标记值设为，该点设为当前点，转步骤2，否则，s=s+1，若s=8，令t=0，且将当前点标记值转换为，并进行下一步，否则，重复步骤3。

步骤4 若t=8，则转步骤5，否则，令方向因子 d=mod （d+1，8 ），t=t+1，判断该方向上像素点的标记值，若为，转步骤5；若为，则将标记值转换成，并将该点设为当前点，重复步骤4；若无标记值且为目标点，则该点设为当前点，记录坐标值且标记值设为，转步骤2，若不为目标点，则重复步骤4。

步骤5 结束算法。

值得说明的是，像素值转换因子s的值是像素点对应的像素值是否由转换为的标志，算法结束标志t为完整围线追踪标志。在“尾巴点”区域，像素点像素值会转换为，以此为标志，追踪过程会逐步回溯，直到找到新的未标记的目标点，从而跳出“尾巴点”。

2 实验验证与分析

如图3所示，约定颜色较深区域为目标区域，每个小方格代表一个单位像素，采用本文提出的基于像素多次标记的二值图像区域围线追踪算法对图3中的目标区域进行模拟实验，最终的追踪围线为如图4所示的颜色较深的区域。表1按照追踪到目标像素点的先后顺序给出了图像坐标系下构成围线的像素点坐标值以及最终标记值。图5展示了追踪过程。

图 3 模拟实验图像Fig.3 Simulated experimental image

图 4 追踪结果示意Fig.4 Diagram of tracking results

图 5 追踪过程示意Fig.5 Diagram of tracing process

表 1 围线追踪过程像素坐标与标记数据表Tab.1 Pixels coordinates and labeled data in contour tracing process

由图4可以看出，构成围线的像素被成功地追踪出来，呈现一条完整围线。被追踪到的目标像素点分别被标记为，和。其中，代表追踪起始点和结束点，代表追踪一次的点，代表追踪二次的点。由图4和表1可知，“尾巴点”均被标记为，也成功地被找出，且未因“尾巴点”的存在而中断追踪。

利用本文算法对图3进行完整的追踪过程总搜索判断像素点262次，追踪到有效构成围线像素点42个，利用文献[4]进行围线追踪，当追踪到表1中所示的21号点时，便无法继续追踪，充分说明本文算法对文献[4]所述算法进行了有效的改进。

3 结 论

提出了一种基于像素标记的二值图像区域围线追踪方法。该算法在已有围线追踪算法的基础上，通过定义特定追踪方向，使得追踪过程始终按照逆时针或顺时针方向沿着连通区域边缘进行。在追踪过程中对像素点进行多次标记，通过在按照追踪方向确定的像素点基础上判断像素标记值来确定下一次待追踪像素点的选取。提出“尾巴点”的概念，并对“尾巴点”区段的一次追踪和二次追踪进行了有效区分，解决了追踪过程中出现的追踪间断现象，使得追踪结果呈现一条完整围线。大量实验表明，方法可行且可靠，能够很好地实现二值图像目标区域的围线追踪。