在图像处理、计算机视觉以及模式识别等研究领域中,通常需要对目标区域的边界信息进行分析,如边界曲率、边界长度、链码及凹凸度等参数,围线追踪就是用来获得目标区域的这些特征信息的有效方法[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]追踪到该类点时,由于无跳出尾巴点的有效措施,导致提前终止追踪。本文所设计的像素点追踪算法将设法有效跳出“尾巴点”,最终追踪出完整的围线。
基于像素点的二值图像区域围线追踪实际上是从目标区域某一边缘像素点出发,按照逆时针或顺时针方向不断搜寻后续边缘点,从而形成一条完整围线的过程。文献[4]中提出的围线追踪方法是基于某点P周围8个方向的优先顺序(如图2所示)来判断后续追踪点的选择。该方法能够很好地将简单区域的边缘轮廓按照逆时针的方向追踪出来,但是,对于较为复杂的图像忽略了一些容易出现的特殊情况(如“尾巴点”的存在),直接造成追踪陷入无限循环或追踪提前终止,抗边缘噪声能力较低。针对该算法的不足之处,本文给出了改进后的完整算法。
算法步骤:
步骤1 对二值图像进行扫描,扫描到的第一个目标点设为当前点[10],记录坐标值并将标记值设为
步骤2 令方向因子d=mod (d+5,8),mod(a,b)表示求a除以b的余数,判断该方向上的点是否为目标点且未被标记,若是,则记录坐标值且标记值设为
步骤3 令方向因子d=mod (d+5,8),判断该方向上的点是否为目标点且未被标记,若是,则记录坐标值且标记值设为
步骤4 若t=8,则转步骤5,否则,令方向因子d=mod (d+1,8),t=t+1,判断该方向上像素点的标记值,若为
步骤5 结束算法。
值得说明的是,像素值转换因子s的值是像素点对应的像素值是否由
如图3所示,约定颜色较深区域为目标区域,每个小方格代表一个单位像素,采用本文提出的基于像素多次标记的二值图像区域围线追踪算法对图3中的目标区域进行模拟实验,最终的追踪围线为如图4所示的颜色较深的区域。表1按照追踪到目标像素点的先后顺序给出了图像坐标系下构成围线的像素点坐标值以及最终标记值。图5展示了追踪过程。
由图4可以看出,构成围线的像素被成功地追踪出来,呈现一条完整围线。被追踪到的目标像素点分别被标记为
利用本文算法对图3进行完整的追踪过程总搜索判断像素点262次,追踪到有效构成围线像素点42个,利用文献[4]进行围线追踪,当追踪到表1中所示的21号点时,便无法继续追踪,充分说明本文算法对文献[4]所述算法进行了有效的改进。
3 结 论提出了一种基于像素标记的二值图像区域围线追踪方法。该算法在已有围线追踪算法的基础上,通过定义特定追踪方向,使得追踪过程始终按照逆时针或顺时针方向沿着连通区域边缘进行。在追踪过程中对像素点进行多次标记,通过在按照追踪方向确定的像素点基础上判断像素标记值来确定下一次待追踪像素点的选取。提出“尾巴点”的概念,并对“尾巴点”区段的一次追踪和二次追踪进行了有效区分,解决了追踪过程中出现的追踪间断现象,使得追踪结果呈现一条完整围线。大量实验表明,方法可行且可靠,能够很好地实现二值图像目标区域的围线追踪。
[1] |
陈旺, 郭庆胜. 二值图像中目标物体边界跟踪的一种快速算法及其应用[J]. 测绘工程, 2014, 23(12): 63-66. DOI:10.3969/j.issn.1006-7949.2014.12.016 |
[2] |
陈优阔, 杨永国, 夏浩铭. 边界跟踪自动机与围线树结构的生成算法[J]. 计算机应用与软件, 2009, 26(5): 218-220. DOI:10.3969/j.issn.1000-386X.2009.05.072 |
[3] |
李雨田, 晋小莉. 基于图像边界跟踪的顶点矩阵算法[J]. 计算机工程, 2010, 36(1): 231-232. DOI:10.3969/j.issn.1000-3428.2010.01.080 |
[4] |
刘晓东, 胡兵. 基于区域围线追踪的激光雕刻新算法[J]. 华中理工大学学报, 1997, 25(11): 51-53. |
[5] |
石爽, 曲仕茹, 何力. 一种新的边界跟踪算法[J]. 图学学报, 2011, 32(3): 52-56. DOI:10.3969/j.issn.1003-0158.2011.03.010 |
[6] |
吴立德, 林应强. 基于边过程的围线追踪与围线的树结构[J]. 计算机学报, 1996, 19(6): 457-465. DOI:10.3321/j.issn:0254-4164.1996.06.008 |
[7] |
张奎, 陈兆学. 一种基于游程码的二值图像孔洞标记和表达方法[J]. 光学技术, 2017, 43(4): 364-368. |
[8] |
张毅, 李昌华. 基于边界跟踪的任意形状区域填充算法[J]. 计算机工程与设计, 2015, 36(3): 725-728. |
[9] |
周秀芝, 陈洋, 胡文婷. 基于交叉点的树遍历二值图像边界跟踪算法[J]. 计算机应用与软件, 2014, 31(2): 230-232. DOI:10.3969/j.issn.1000-386x.2014.02.062 |
[10] |
钱晓明, 杨丽娟, 楼佩煌. 基于改进的边界追踪算法的管道法兰焊缝识别[J]. 焊接学报, 2016, 37(12): 115-119. |