一种基于对象的连通区域标记方法

蒋伟达

（河海大学地球科学与工程学院，江苏 南京 211100）

1 引 言

二值图像的连通域标记处理操作是从白色像素（通常用“0”来表示）和黑色像素（通常用“1”来表示）组成的一幅点阵图像中将互相邻接（本文研究的是4邻域、8邻域，m邻域暂不讨论）的目标“1”值像素标识为同一目标。该处理过程是图像处理和分析中一个非常重要的基础操作，有广泛的应用领域［1］。

传统的标记方法如二次扫描法主要通过2次扫描确定各个不同的连通区域。第1次扫描逐行逐列扫描像素，通过判断像素之间的邻域关系对属于同一连通区域的像素赋予相同的连通标志。这样可能造成同一连通区域中不同子区域被赋予不同的值，因此要执行第2次扫描消除重复标记，以合并子区域。这种方法的效率不高，尤其是在重复性标记发生率高时，效率更低［2］。

众所周知，走迷宫时若一直沿着左侧边缘前进，则一定可以到达终点；若不从出口出去，继续沿着左侧边缘前进，必将回到起点。这就可以顺时针遍历整个迷宫道路的左沿边界。受破解迷宫方法启发，本文提出了一种基于对象的连通区域标记方法。

2 算法描述

不同于传统方法，本文算法基于对象，一次扫描即可将所有连通子区标记为同一连通区域，无需进行二次扫描。算法主要实施步骤如下。

（1）首先，从左到右、从上至下进行逐行逐列扫描，找到一个未标记的连通区域内的一点（该点在连通区域中实际位置对本算法实现无影响）设为第1点。探索该像素左侧和上侧像素点是否有标记，若有则以此为本连通子区的标记值，若无则自动分配标记值。

（2）标记该像素，根据标记符数值按一定顺序探索同一连通区域的下一个像素，并重设标记符。每当标记符tag值为2时（即向下前进时）直接向左依次标记连通区域内未标记的像素。

（3）循环步骤（2）直至返回步骤（1）中首先标记的第1点，则一个连通区域（或连通子区）的标记结束。

（4）继续步骤（1），标记下一个连通区域，直至标记完整幅图像。

在步骤（2）中，本文引入了一个标记符tag（值在0到3之间，0表示上，1表示右，2表示下，3表示左），这个标记符是用来记录探索像素时前进方向的，初始值为1（即向右探索）。

探索顺序与标记符tag的值有关，如下。

①tag＝1时，按上、右、下、左的顺序探索四邻域内像素。

②tag＝2时，按右、下、左、上的顺序探索四邻域内像素。

③tag＝3时，按下、左、上、右的顺序探索四邻域内像素。

④tag＝0时，按左、上、右、下的顺序探索四邻域内像素。

同时，根据探索前进方向重新为tag赋值，即向上前进tag＝0，向右前进tag＝1，向下前进tag＝2，向左前进tag＝3。

3 算法演示及分析

本文以传统方法标记问题最为严重的“U形”、“E形”为例演示并分析此算法推算过程。一般认为，这种形状的对象最易在传统第1次扫描过程中被判为多个不同的连通区域。

为了演示本算法标记过程，以8×8为例，我们先将每个像素的坐标按从左到右，从上到下，从0到63编号。

“U形”、“E形”对象如图1所示。① 按0～63的顺序依次遍历，直至探索到连通区的第1点9号像素，标记之，此时tag初始值为1。② 按上、右、下、左的探索顺序探索到17号像素为连通区内像素，标记之，向下前进，为tag赋值2。③ 按右、下、左、上顺序探索，探索到25号为连通区内像素，标记之，向下前进，tag赋值为2。④继续……标记51号，此时tag值为1。⑤ 探索顺序为上、右、下、左，继续到43号为连通区内像素，标记之，向上前进，为tag赋值为0……

图1 一种复杂度较高的对象

实际具体遍历顺序如图2所示。

据陈柏生［2］所述，传统二次扫描法在最好的情况下时间复杂度为O（n），而在重复标记较严重的情况下时间复杂度甚至达到O（n3）。本算法在针对较复杂的“U形”、“E形”对象时也只是对连通区域进行了2次遍历，即使在更为复杂的情况下，本算法也只会对每一个像素进行2次4邻域探索，其时间复杂度为O（2n）。

图2 像素遍历顺序示意图

4 结 语

本文主要提供了一种基于对象的连通区域标记算法。因篇幅所限，本文只提供了四连通区域的标记方法。八连通区域的标记需修改步骤（2）中探索顺序，且此种算法在标记过程中可以利用链表等数据结构储存对象边界所经过的像素坐标，有助于进一步进行栅格图像向矢量对象的转换工作。

［1］ 李欢，杨捷.求解二值图像连通域的改进算法［J］.计算机与现代化，2005，（4）：11－13.

［2］ 陈柏生.一种二值图像连通区域标记的新方法［J］.计算机工程与应用，2006，42（25）：46－47.

［3］ 葛春平.一种二值图像连通区域标记的简单快速算法［J］.价值工程，2012（28）：242－243.

［4］ 高红波，王卫星.一种二值图像连通区域标记的新算法［J］.计算机应用，2007（11）：168－169，177.