一种基于“弦”的边界跟踪算法

刘兆财,王东兴,田洪志,林建钢

(烟台大学机电汽车工程学院,山东 烟台 264005)

在一个基于轮廓特征的模式识别[1]系统中,需要边界像素点的有序排列,才能从中提取目标通用形状特征。边界跟踪[2-4]就是来完成这项工作的,是数字图像处理技术中用来提取形状信息的一种重要方法,是基于轮廓形状匹配的一个重要步骤。

一般在获取图像中目标轮廓、质心、不变矩等操作前都会对二值图像进行连通域划分,即对二值图像进行连通域标记[5-6],而在连通域标记算法中,目前应用较广、速度极快的是基于游程编码的连通域标号算法[7-9],本文在详细分析了此种标号算法基础上,提出了一种基于“弦”的边界跟踪算法。

传统的边界跟踪算法有虫随法[10]、光栅扫描法[11]和八邻域边界跟踪法[12]等。虫随法和光栅扫描法都要多次重复才能得到结果,由于重复次数需要人为确定,因此跟踪结果未必准确。八邻域跟踪算法性能相对较好,因此提取给定图像边界时用到的频率较高,然而八邻域跟踪算法需要扫描当前边界点的八邻域来判断下一边界点,并且边界上的每个点都要进行八邻域判断,判断总次数多,搜索冗余也较多。当然,一些学者也提出了一些改进算法,如崔凤魁等[13]提出目标邻域点的边界点搜索方法, 该算法从上一边界点的下一邻域点开始搜索, 将搜索方向减至7个,但仍有大量搜索冗余未被去除。王福生等[14]将搜索方向减至最多5次,比崔凤魁等[13]提出的目标邻域点边界点搜索算法的搜索冗余少。但这些改进的算法只是在八邻域的基础上进行的算法优化,依然需要对每个边界点进行八邻域的判断,所需判断边界点总次数仍然较多,并且边界上的每个点都要进行扫描。

当连通域采用游程编码[15]表示时,若要采用上述传统算法进行边界跟踪,则还需要将用游程编码表示的连通域转换为用光栅图像表示的连通域,进一步增加了从连通域获取其边界轮廓的处理时间。而本文算法则是直接根据游程编码方法的特性进行下一边界点的判断,所以对目标轮廓进行边界跟踪时,所需进行边界点判断的总次数相较于传统的边界跟踪算法就有了很大的降低,而且无需逐像素扫描每一个边界点,此时边界跟踪效率也得到了明显的提高。本文算法可以在快速标记连通域后再进行快速的目标轮廓提取,而无需在连通域标记后先将连通域转换为光栅图像形式,再使用其他的传统边界跟踪算法来提取目标物体的轮廓,此时目标物体的轮廓提取效率有了极大的提升。

1 RLRegion连通域

经过游程编码标记后的连通域,在这里将其称为RLRegion连通域,而此RLRegion连通域中的基本描述单元则用弦(Chord)来描述(图1),很显然,每个弦的2个端点一定在域的边界上,但中间点也可能在域的边界上,图1中部与其上多个弦或其下多个弦相邻接的弦,一行中可能有一个弦,也有可能有多个弦。

图1 由弦所描述的RLRegion连通域Fig.1 A RLRegion connected region described by chords

当连通域改为用弦描述时,根据弦上的像素列坐标的连续性,很多情况下就不需要逐像素搜索边界上的像素。

2 算法描述

2.1 获得RLRegion连通域

对二值图像进行基于游程编码的连通域标号处理时,取一目标连通域,在逐行扫描图像的过程中,将每一行中连续的白色像素组成的序列作为一个弦(Chord),并记下它的起始列坐标、终止列坐标以及它所在行坐标。其中弦的数据结构定义为

struct WDChord {

Inty; //行坐标

Intxb; //起始列坐标

Intxe; //终止列坐标

};

假设RLRegion连通域由N个弦组成。

R={Ci=(xbi,xei,yi)|i∈[0,N-1]}。

(1)

每个弦都有其对应的序号,弦序号范围由0到(N-1)。在RLRegion连通域中,弦序号从左到右,从上到下依次排列,一行中可能有一个弦序号,也可能有多个弦序号,每行中的第一个弦的序号在这里称其为首弦序号。

2.2 获取RLRegion连通域的行信息

连通域行信息的数据结构定义如下:

struct ConnRegInfo {

int nYFirstRow;

int nYLastRow;

int* pRowSCN;

uchar* pChordF;

};

其中:nYFirstRow为连通域第一行y坐标,nYLastRow为连通域最后一行y坐标,pRowSCN用来存储每一行上首弦的序号,pChordF则用来存储每一弦的首端标记。

2.3 初始化首端标记

申请存储空间存储连通域中每一个弦的首端标记,并将其全部初始化为0。每一个弦的首端即首像素在被搜索记录后,就将其首端标记赋值为1。当搜索完外层轮廓后,若存在内层轮廓,内层轮廓中肯定有弦的首端未进行标记的,此时通过首端标记便可进行内层轮廓的搜索。

2.4 搜索RLRegion连通域外边界及内边界

搜索外边界时取序号为0的弦为首弦,记为弦C0(xb0,xe0,y0)，xb0为A的首像素的列坐标，xe0为其尾像素的列坐标，y0为其行坐标。

为了按逆时针方向顺序排列外部边界线上的像素,或沿顺时针方向排列内部边界线上的像素,弦的搜索方向分为2个,D1:沿着每条弦的首端向下(行地址变大),D2:沿着每条弦的尾端向上(行地址变小),为简单起见,规定搜索任何一条边界线时起始搜索方向均为D1。

为了应用下述方法,记C0(xb0,xe0,y0)=A(xbA,xeA,yA)。

2.4.1 按D1法搜索 首先判断当前弦下一行的y坐标是否超出连通域最大的y坐标,若是,判断下一行上无邻接弦,否则,需要从左侧遍历下一行上是否有当前弦的邻接弦。

图2为相邻2行上2弦邻接的极限情况,记弦B为(xbB,xeB,yB),则相邻2行上弦A与B不邻接的条件为(xeBxeA+1)。

图2 相邻2行上2弦邻接的极限情况Fig.2 The limiting case of the adjacency of two chords on two adjacent rows

如图3,若当前弦A的下一行上没有与其邻接的弦,说明弦A上的像素均为边界像素,记录A的首像素的坐标(xbA,yA),要标记弦A的首端已搜索即对弦A进行首端标记,避免搜索内部边界时该弦的首像素被作为起始像素,其尾端会在下次搜索时处理,当前弦序号不变,搜索方向变为D2,按照D2法继续搜索。

图3 A的下一行上没有与其邻接的弦Fig.3 There is no adjacent chord on the next line of A

当前弦A的下一行有与A邻接的弦B,可分为以下几种情况:

(a) 弦B的首像素的列坐标大于A的首像素的列坐标加1,即xbB>xbA+1时。

如图4,这种情况下,从A的首像素开始至少有2个边界像素(如下方黑色像素块),按顺序记录黑色像素块的2个端像素的坐标:(xbA,yA)和(xbB-1,yA),当前弦改为弦B,搜索方向不变。

图4 xbB>xbA+1Fig.4 xbB>xbA+1

(b) 当xbB=xbA或xbB=xbA+1时,如图5,这种情况下,A的首像素为边界像素,记录其坐标(xbA,yA),当前弦改为弦B,搜索方向不变。

图5 xbB=xbA或xbB=xbA+1Fig.5 xbB=xbA or xbB=xbA+1

(c) 当xbB=xbA-1时,并且在A的同一行上A的左侧没有弦与B邻接,如图6,A的首像素为边界像素,记录其坐标(xbA,yA),当前弦改为弦B,搜索方向不变。

图6 xbB=xbA-1，并且A的左侧没有弦与B邻接Fig.6 xbB=xbA-1, and the left side of A has no chord adjacent to B

(d) 当xbB

图7 xbB

(e) 在A的同一行上A的左侧有弦C(xbC,xeC,yC)与B邻接，并且xeC=xbA-2，如图8,A的首像素为边界像素,记录其坐标(xbA,yA),弦B上列坐标为xbA-1的像素也是边界像素,记录其坐标(xbA-1,yB),当前弦改为弦C,搜索方向改为D2。

图8 A的左侧有弦C与B邻接并且xeC=xbA-2Fig.8 The left side of A has chord C adjacent to B, and xeC=xbA-2

(f)在A的同一行上A的左侧有弦C(xbC,xeC,yC)与B邻接，并且xeC

图9 A的左侧有弦C与B邻接并且xeC

(a)—(f)情况下均要标记弦A的首端已搜索即对弦A进行首端标记,避免搜索内部边界时这些弦的首像素被作为起始像素。

2.4.2 按D2法搜索 首先判断当前弦上一行的y坐标是否小于连通域最小的y坐标,若是,判断上一行上无邻接弦,否则,需要从右侧遍历上一行上是否有邻接弦。

如图10,若当前弦A的上一行上没有与A邻接的弦,说明弦A上的像素均为边界像素,记录A的尾像素的坐标(xeA,yA),要标记弦A的尾端已搜索,避免搜索内部边界时该弦的尾像素被作为起始像素,其首端会在下次搜索时处理,当前弦不变,搜索方向变为D1,按照D1法继续搜索。

图10 A的上一行上没有与其邻接的弦Fig.10 There is no adjacent chord on top of A

当前弦A的上一行有与A邻接的弦,可分为以下几种情况:

(a) 弦B的尾像素的列坐标小于A的尾像素的列坐标减1,即xeB

如图11,这种情况下,从A的尾像素开始至少有2个边界像素,按顺序记录其2个端像素的坐标(xeA,yA)和(xeB+1,yA),当前弦改为弦B,搜索方向不变。

图11 xeB

(b) 当xeB=xeA或xeB=xeA-1时，如图12，A的尾像素为边界像素，记录其坐标(xeA,yA)，当前弦改为弦B，搜索方向不变。

图12 xeB=xeA或xeB=xeA-1Fig.12 xeB=xeA or xeB=xeA-1

(c) 当xeB=xeA+1时，并且在A的同一行上A的右侧没有弦与B邻接，如图13，A的尾像素为边界像素，记录其坐标(xeA,yA)，当前弦改为弦B，搜索方向不变。

图13 xeB=xeA+1并且A的右侧没有弦与B邻接Fig.13 xeB=xeA+1, and the right side of A has no chord adjacent to B

(d)xeB>xeA+1，并且在A的同一行上A的右侧没有弦与B邻接，如图14，A的尾像素为边界像素，记录其坐标(xeA,yA)，B上至少有2个边界像素，按顺序记录其2个端像素的坐标：(xeA+1,yB)和(xeB,yB)。当前弦改为弦B，搜索方向不变。注意：邻接弦的尾像素下次搜索时会被重复记录。

图14 xeB>xeA+1并且A的右侧没有弦与B邻接Fig.14 xeB>xeA+1, and the right side of A has no chord adjacent to B

(e) 在A的同一行上A的右侧有弦C(xbC,xeC,yC)与B邻接，并且xbC=xeA+2，如图15，A的尾像素为边界像素，记录其坐标(xeA,yA)，弦B上列坐标为xeA+1的像素也是边界像素，记录其坐标(xeA+1,yB)，当前弦改为弦C，搜索方向改为D1。

图15 A的右侧有弦C与B邻接并且xbC=xeA+2Fig.15 The right side of A has chord C adjacent to B, and xbC=xeA+2

(f) 在A的同一行上A的右侧有弦C(xbC,xeC,yC)与B邻接，并且xbC>xeA+2，如图16，A的尾像素为边界像素，记录其坐标(xeA,yA)，弦B上列坐标在xeA+1与xbC-1之间的像素也是边界像素，按顺序记录2个端像素的坐标：(xeA+1,yB)和(xbC-1,yB)，当前弦改为弦C，搜索方向变为D1。

图16 A的右侧有弦C与B邻接并且xbC>xeA+2Fig.16 The right side of A has chord C adjacent to B, and xbC>xeA+2

2.4.3 搜索外边界线 根据当前搜索方向按照D1法或D2法搜索边界上的每一个弦，直到当前弦再次变回初始弦C0为止，若当前搜索方向不是D1，则还需要记录下弦C0的尾像素的坐标。

2.4.4 搜索一条内部边界线 当此连通域外边界线找到后，接着遍历各弦的首端标记，找到第一个首端未标记的弦作为首弦，初始搜索方向为D1，此时，按照搜索外边界线的方法搜索边界上的每一个弦，找到一条内部边界线。

2.4.5 搜索所有内部边界线 最后按照上述找到一条内部边界线的方法找到所有内部边界线，此时所有弦的首端均完成标记，即此连通域的所有内外边界线均已搜索完成。

3 实验与分析

3.1 实验说明

硬件条件为Intel(R) Core(TM) i5-8250U CPU @ 1.60 GHz；软件环境为Visual Studio 2013×32 Debug模式和OpenCV3.0。

图17为原始的二值图，该图片大小为504 pixel×356 pixel。图18为文献[14]算法的边界跟踪结果。图19为采用本文算法的边界跟踪结果。效率实验采用4组每组10张大小相同的二值图像，1—4组分别对应的图片大小依次为504 pixel×356 pixel、500 pixel×500 pixel、30 pixel×19 pixel、11 pixel×11 pixel，运用2种算法分别计算每张图片的时间，取每组的平均时间，其中2种算法所执行的对象都是经过游程编码标记后的目标连通域。

图17 原二值图Fig.17 Original binary image

图18 文献[14]算法的边界跟踪结果Fig.18 Boundary tracking result of Ref.[14]

3.2 结果与分析

3.2.1 轮廓跟踪所存储的点集 在上方的边界跟踪结果图中，图18绘制的是文献[14]算法所得到的点集，图19绘制的是本文算法跟踪存储的点集。若要得到点集对应的完整轮廓，可以通过OpenCV中的drawContours()函数进行绘制，该函数能将点与点之间的连线按照一定的拓扑关系来绘制，图20为使用图19中的点集绘制得到的轮廓图。

图19 本文算法边界跟踪结果Fig.19 Boundary tracking result of the proposed algorithm

图20 drawContours()函数所绘制的轮廓Fig.20 The outline drawn by drawContours()

由边界跟踪结果图可以看出,图18的边界跟踪是将轮廓上的每个点都进行了扫描存储,而图19本文算法边界跟踪所扫描存储的点为弦的端像素点,且处于边界上的弦的边界点并未全部进行扫描存储,从点集可以看出,本文算法要比八邻域边界跟踪算法的搜索范围小。

3.2.2 跟踪效率 表1为2种不同算法运行时间的比较。

表1 2种不同算法的运行时间比较Tab.1 Execution time of two different algorithms s

由表1中的数据可以得到基于“弦”的边界跟踪算法比文献[14]算法提高的效率,效率的公式为

η=(T2-T1)/T1。

(2)

由式(2)可以得到表2,从表2中可以得到本文算法的运行时间效率要比文献[14]算法的运行时间效率平均提高了大约69.08%。

表2 效率提高Tab.2 Efficiency improvement table %

从已得的实验结果分析可知,组成RLRegion连通域中的“弦”越长,“长弦”的占比越大,并且连通域边界越规则,那么本文算法所提高的效率就越高。反之,连通域越小,“弦”越短,那么本文算法所提高的效率就不够显著。

4 结束语

本文在已有的基于游程编码的连通域标记基础上,提出了一种基于“弦”的边界跟踪算法。该算法是专门针对由“弦”组成的RLRegion连通域进行边界跟踪的特殊算法,在同等背景环境下,本文算法所耗时间要比八邻域边界跟踪算法所耗时间少了很多,效率提高较为显著。当然本文算法也有不足之处,本文算法所使用的环境必须是在RLRegion连通域的基础上才能使用,即在使用本文算法之前,要先对二值图像进行基于游程编码的连通域标记处理,使其变成由弦组成的连通域。尽管有这些不足,但连通域标记又是几乎所有二值图像分析的基础,若要针对目标连通域进行轮廓提取等操作,需先对图像进行连通域标记处理。而目前连通域标记处理的算法中,基于游程编码的连通域标记算法是应用较广、效率最高的标记算法,所以本文算法具有广阔的应用场景。