连通域分割Two-Pass算法及其Python实现

连通域Two-Pass算法

在没有任何先验知识的情况下，想完成连通域的搜索，几乎最直接的想法，就是遍历图像所有像素点，如果两个像素点相连接，便将二者视为一体，直到遍历所有的像素。但这种遍历在遇到类似下面的图像时就会出现问题。

$$\begin{array}{cc}& 1\\ 2& 3\end{array}$$

上面的矩阵中，数字代表有效像素，如果扫描顺序是从左向右，从上到下，那么在扫描第二行时，$2$并不和$1$联通，$3$尽管和$1,2$均联通，但只能赋予1个编号，从而上面的情况最终标记如下

$$\begin{array}{cc}& 1\\ 2& 1\end{array}$$

所以，原本属于一个连通域的3个像素点，被分为$1,3$和$2$两个区域，所以需要再去遍历一次，把相邻的不同编号统一，这就是Two-Pass算法的基本思想。

数据准备

在具体实现算法之前，先准备一张二值图像，并封装一个绘图函数。

import matplotlib.pyplot as plt
from scipy.ndimage import binary_erosion
import numpy as np
path = r"coin.png"
img = plt.imread(path).astype(float)
img = np.mean(img, axis=2)
th = 0.513    # climb(img, 0.1, 0, 0.01)
b = img>0.4

def drawImg(im1, im2, c1='jet', c2='jet'):
    fig = plt.figure()
    ax = fig.add_subplot(121)
    plt.imshow(im1, cmap=c1)
    plt.axis('off')
    ax = fig.add_subplot(122)
    plt.imshow(im2, cmap=c2)
    plt.axis('off')
    plt.show()

b = img>0.4
bb = binary_erosion(b, np.ones([5,5]))

第一次

第一次扫描的目的是建立当前像素与左边和上边的像素之间的联通关系，同时需要一个字典保存这种映射，为后续的连通域合并做准备。

def firstPass(inImg):
    L = 0       # 标记号
    outImg = inImg.astype(float)
    h, w = inImg.shape
    dct = {}
    for i,j in product(range(h), range(w)):
        if inImg[i,j] == 0:
            continue
        neighbors = []   # 记录符合要求的邻域前景
        if i-1> 0 and inImg[i-1, j]>0:
            neighbors.append(outImg[i-1, j])
        if j-1 > 0 and inImg[i, j-1] > 0:
            neighbors.append(outImg[i, j-1])
        if len(neighbors) == 0:
            L += 1
            outImg[i,j] = L
            dct[L] = [[i],[j]]
        else:
            tmpL = min(neighbors)
            outImg[i,j] = tmpL
            dct[tmpL][0].append(i)
            dct[tmpL][1].append(j)
    return outImg, dct

实验效果如下

c1, d = firtPass(bb)
drawImg(bb, c1)

第二次

第二次扫描的目的是，将属于同一连通域，但编号不同的区域，赋予相同的序号。为此 ，需要再次遍历图像，并通过第一次遍历得到的映射字典，来完成连通域的合并。

def secondPass(outImg, dct):
    outImg = outImg * 1
    print('version')
    for i,j in zip(*np.where(outImg!=0)):
        Ls = [outImg[i,j]]
        if i-1>0 and outImg[i-1,j] != 0:
            Ls.append(outImg[i-1,j])
        if j-1 > 0 and outImg[i, j-1] != 0:
            Ls.append(outImg[i, j-1])
        Ls = np.unique(Ls)
        if len(Ls)<2:
            continue
        minL = np.min(Ls)
        for L in Ls:
            if L == minL:
                continue
            y,x = dct[L]
            outImg[y,x] = minL
            dct[minL][0].extend(dct[L][0])
            dct[minL][1].extend(dct[L][1])
            del dct[L]
    u = np.unique(outImg)
    u = np.sort(u)  # 排序
    N = len(u) - 1  # 此为图标数
    for i in range(1, N+1):
        outImg[outImg==u[i]] = i
    N = len(np.unique(outImg))
    return N, outImg

效果如下

n, c2 = secondPass(c1, d)
drawImg(c1, c2)