'Topological_structural_analysis_of_digitized_binary_images_by_border_following_论文方法分析及c++实现'

(1)框架:框架就是指图片的第一列、最后一列、第一行、最后一行像素,这四个长条组成的一个矩形框框,我们这些点是黑点,也就是0。

(2)背景:除了框架之外,和框架属于同一层级的像素点,这些点也是黑点,也就是0。

(3)外轮廓:外轮廓就是指包裹了一堆白点的最外围的白点。

(4)内轮廓:内轮廓是指在包裹了一堆白点的最内部的白点。

用一张图片表示会很清晰:

在这张图片中,S1是背景,也是框架层。S2是包裹的一堆白点,这堆白点的最外层和框架层紧密相连,B1就是S2的外轮廓,B2就是S2的内轮廓。

那么我们怎么用计算机判断一张图片上的点是外轮廓还是内轮廓呢?

那么就得进行如下的步骤:

(1)首先,我们设定外部框架的边界值NBD为1。

(2)接着忽略最外层的框架,然后从图片的第二行的最左侧开始,判断:

如果这个数字是1,并且它的左侧的像素是0,那么我们令(i,j)为这个像素,然后令(i2,j2)=(i,j-1)为它左侧的像素(如果是第一次运算,那么坐标就是(2,2),它要是1,(2,1)是0,那么(i,j)=(2,2)、(i2,j2)=(i,j-1)=(2,1))。然后我们令NBD=NBD+1,并且认为这个点是外轮廓点。

如果这个数字是大于等于1的,并且它的右侧像素是0,那么我们令(i,j)为这个像素,然后令(i2,j2)=(i,j+1)为它右侧的像素。(如果是第一次运算,那么坐标就是(2,2),它要是1,(2,3)是0,那么那么(i,j)=(2,2)、(i2,j2)=(i,j+1)=(2,3)),并且认为这个点是内轮廓点。

如果是其它的情况,那么,令直接跳到最后一步。

(3)下一步是判断这个点到底是内轮廓还是外轮廓,我们用这个表格来判断:

image

这里面B’表示的是上一个按照我们这个步骤走的点是什么轮廓。B表示我们当前的点是什么轮廓。如果这是第一次,没有上一次的点,那么直接认为是外轮廓就好了。

(4)从点(i,j)开始,它的邻近地方有8个点(3*3)的格子之内,然后我们以(i2,j2)点为起始点,然后顺时针的沿着这8个点移动,一直走走走走,唉,发现了一个不为0的像素点,并且令这个点为(i1,j1)。如果这8个点都为0的话,令中心点(i,j)为-NBD,然后直接跳到最后一步。

(5)如果(i1,j1)存在的话,那么我们令(i2,j2)=(i1,j1),(i3,j3)=(i,j)。

(6)然后我们从点(i3,j3)开始,以(i2,j2)为起始点,然后逆时针移动遍历(i,j)邻近地方的8个点。找到第一个不为0的点((i2,j2)这个点不算)。然后令它为(i4,j4)。注意这里肯定不会存在没有不为0点的情况,因为(i3,j3)=(i,j),上一次循环都循环一次了,没有早退出了。

(7)然后我们判断:如果(i3,j3)前面的点(i3,j3+1)为0的话,那么我们把(i3,j3)这个点的像素值赋予-NBD。

如果(i3,j3)点前面的点不为0,且(i3,j3)这个点的像素为1的话,那么把(i3,j3)的像素值赋予NBD。

如果是其它情况的话,这个值保持不变。

(8)判断,如果(i4,j4)=(i,j)也就是我们最开始的那个值,且(i3,j3)=(i1,j1),那么我们跳到最后一步。如果要不符合条件,我们返回到(6)继续计算直到满足条件。

(9)我们回到我们最开始选择的那个点,也就是(i,j)然后我们往右边移动一格,如果已经到达末尾了,换到下一行的左边。如果我们于(i,j)那点的像素不为1的话,我们令LNBD等于(i,j)那点的像素的绝对值。

这九步,我们就把轮廓计算完毕了。在铃木桑的论文中,它举了一个例子来说明这个算法,如下所示:

这个是它最后得到的结果,但是我有点不信,下面我按照它同样的算法,自己手算了一遍:

我的最后结果是分为4部分,4个外轮廓,没有内轮廓,而铃木的是5部分,有一个内轮廓。我认为我的里面那个-3不是内轮廓,因为内轮廓应该是八方向都封闭起来的,而这两个-3只有2个方向是封闭,两个方向直接和背景连接。所以我认为是外轮廓。

谁对谁错我不好说,你们自己分析,然后对这两个人的案例对错评论一下,告诉我哈!

这样,我们的轮廓就检测完毕了。我们用OPENCV检测也非常的简单:

(1)首先我们导入一张图片。

(2)将图片二值化变成黑白图像

(3)运用轮廓搜索算法找出轮廓

(4)显示轮廓。