1. 引言
二值图像即阈值化后的图像，通常像素值为0或者255，一般用于前景目标检测、字符识别等。我们在进行图像分析时，需要判断图像中有几个物体，这时就需要对不同物体进行标识。下面介绍几个基本概念。
1.1 邻域
与像素（x,y）对应的点的集合{(x+p,y+q); (p,q)为一对有意义的整数}，称之为像素(x,y)的邻域。离散图像处理中常取4邻域和8邻域，并分别记作：
1.2 连通
像素f(x,y) = f(x+i,y+j)，其中i,j在图像R内存在。f(x,y)与f(x+i,y+j）周围中的邻接点存在4点邻域和8点邻域，4邻接一共4个点，即上下左右，如下左图所示。8邻接的点一共有8个，包括了对角线位置的点，如下右图所示
1.3 标记
图像分割后的一帧图像可能存在多个连通成分，每个非连通成分都对应一个目标图像区，对各目标图像区分配对应标号的工作称之为标记。
加标记与所采取的为4邻域还是8邻域有关，因此常用的标记方法分为4连通标记法和8连通标记法。
2. 实现
2.1 生成网格图
这里生成一个简单的8X8的黑白网格图为例，进行说明。代码如下：
grid = [
[ 0, 1, 0, 0, 0, 0, 0, 0],
[ 0, 1, 1, 0, 0, 1, 0, 0],
[ 0, 1, 0, 0, 0, 1, 0, 0],
[ 0, 0, 0, 0, 1, 0, 0, 1],
[ 0, 0, 0, 0, 1, 0, 0, 0],
[ 0, 0, 0, 0, 1, 0, 0, 0],
[ 0, 0, 0, 0, 1, 0, 0, 0],
[ 0, 1, 1, 0, 0, 0, 0, 0]
]
grid = np.array(grid)
histogram(grid, interval=[0, 1])
结果如下：
2.2 判断邻域是否合法
为了便于处理，我们定义一个函数来判断当前元素的邻域是否合法，代码如下：
def _valid_neighborhood(grid, labels, s, t, M, N):
# Check if current member of neighborhood is valid
if (s or t) < 0:
return None
if (s >= M) or (t >= N):
return None
if labels[s][t]:
return None
if grid[s][t] <= 0:
labels[s][t] = -1
return None
return (s, t)
上述代码中，grid代表我们输入的原始网格，labels代表当前元素是否访问过；上述函数的功能为如果元素(s,t)没有访问过，则返回其位置；否则返回None。
2.3 四连通标记法
四连通标记法仅判断当前元素的垂直方向和水平方向四个邻域，换句话说对于元素（x,y),仅考虑（x+1,y）(x-1,y),(x,y+1)或（x,y-1)。
代码实现如下：
def connect4(grid):
'''
Define number of subsets given the 4-connected neighborhood
'''
subsets = 0
M, N = len(grid), len(grid[0])
# 4-connected neighborhood offset
connected_4 = [(1, 0), (0, 1), (-1, 0), (0, -1)]
# Matrix of labels
labels = [[0 for _ in range(M)] for _ in range(N)]
for m in range(M):
for n in range(N):
if labels[m][n]:
# Ignore visited positions
continue
if not grid[m][n]:
# Ignore invalid positions (p == 0)
# and mark its labels as -1
labels[m][n] = -1
continue
subsets += 1
connected = [(m, n)]
# Init scan from the current position
for (s, t) in connected:
neighborhood = set([None, *connected])
# Search for valid neighbors
neighborhood |= {*[_valid_neighborhood(
grid, labels, s + u, t + v, M, N
) for (u, v) in connected_4]}
neighborhood.remove(None)
# Include valid neighbors to the current scan
connected += list([v for v in neighborhood if v not in connected])
# Add subset label to the position [s, t]
labels[s][t] = subsets
return labels, subsets
grid_labeled, subsets = connect4(grid)
visualize_grid(grid, grid_labeled, subsets)
结果如下：
2.4 八连通标记法
八连通标记法不仅判断当前元素的垂直方向和水平方向还包括两条对角线共计八个邻域，一般如下所示：
代码实现如下：
def connect8(grid):
'''
Define number of subsets given the 8-connected neighborhood
'''
subsets = 0
M, N = len(grid), len(grid[0])
# 8-connected neighborhood offset
connected_8 = [
(1 , -1), (1 , 0), ( 1, 1),
(0 , -1), ( 0, 1),
(-1, -1), (-1, 0), (-1, 1)
]
# Matrix of labels
labels = [[0 for _ in range(M)] for _ in range(N)]
for m in range(M):
for n in range(N):
if labels[m][n]:
# Ignore visited positions
continue
if not grid[m][n]:
# Ignore invalid positions (p == 0)
# and mark its labels as -1
labels[m][n] = -1
continue
subsets += 1
connected = [(m, n)]
# Init scan from the current position
for (s, t) in connected:
neighborhood = set([None, *connected])
# Search for valid neighbors
neighborhood |= {*[_valid_neighborhood(
grid, labels, s + u, t + v, M, N
) for (u, v) in connected_8]}
neighborhood.remove(None)
# Include valid neighbors to the current scan
connected += list([v for v in neighborhood if v not in connected])
# Add subset label to the position [s, t]
labels[s][t] = subsets
return labels, subsets
grid_labeled, subsets = connect8(grid)
visualize_grid(grid, grid_labeled, subsets)
结果如下：
3. 完整代码
完整代码可公众号内回复 连通域 即可获取
4. 参考
关注公众号《AI算法之道》，获取更多AI算法资讯.
