连通域标记算法及其Python实现

问题引入

通俗地说，如果把图像分为前景和背景两部分，那么连通域就是连通在一起的前景，这种关系对于二值图像来说比较明显。

以下面的硬币图像，在二值化之后，可以很明显看到，图像被分为黑色和白色两个部分，若以白色为背景，则黑色被白色隔开，彼此之间并不联通。连通域标记的目的，就是为不连通的这些黑色区域，标上不同的序号。

其绘图代码如下，其中climb是此前实现的自动ostu阈值算法，参考这篇：OTSU算法及其Python实现

import matplotlib.pyplot as plt
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>th

def drawImg(im1, im2, c1='gray', c2='gray'):
    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()

drawImg(img, b)

实现

常用的连通域标记算法是Two-Pass算法，顾名思义，就是迭代两次，第一次用于记录相邻像素的连通域关系，第二次则把相连通的区域置以相同的标签。

在遍历之前，先初始化一个编号矩阵，考虑到Python提供了字典这种数据类型，所以第一次遍历，将关联相邻像素的编号。比如，点$P_{12}$的编号是3，点$P_{22}$的编号是4，而且二者均为目标，则将产生一组键值对 { 3 : 4 } \{3:4\} {3:4}。

下面就是这个字典的创建过程，由于在遍历过程中，每个像素点要和它左侧和上方的像素点进行比较，所以这个字典的值应该是一个列表。

from itertools import product
def getIndDct(img):
    # 元素个数
    m,n = img.shape
    # 编号矩阵
    indMat = np.arange(m*n).reshape([m,n])
    dct = {}
    for i,j in product(range(m), range(n)):
        if img[i,j] == 0:
            continue
        ind = indMat[i,j]
        dct[ind] = []
        if i>1 and img[i-1,j]!=0:
            dct[ind].append(indMat[i-1,j])
        if i+1<m and img[i+1, j]!=0:
            dct[ind].append(indMat[i+1,j])
        if j > 1 and img[i,j-1]!=0:
            dct[ind].append(indMat[i, j-1])
        if j+1 < n and img[i, j+1] != 0:
            dct[ind].append(indMat[i, j+1])
    return dct

在得到编号映射字典之后，需要将其归一化，就是把类似$a:[b,c]$和$c:[d,e]$合并为$a:[b,c,d,e]$。当所有编号都已经归类之后，还可以继续将其变为$[a,b,c,d,e]$实现如下

from copy import deepcopy
def mergeKey(dct, key):
    keys = [key]
    st, ed = 0, 1
    while len(keys)>0:
        for i in range(st, ed):
            k = keys[i]
            if k in dct:
                keys += dct[k]
                del dct[k]
        if ed == len(keys):
            break
        st, ed = ed, len(keys)
    return keys

def uniqueDct(dct):
    uDct = deepcopy(dct)
    for k in dct:
        if k in uDct:
            uDct[k] = list(set(mergeKey(uDct, k)))
    return [list(set([k]+v)) for k,v in uDct.items()]

最后，将其重新赋值，由于编号矩阵是按照自然数列的顺序创建的，故而只需先把图像展平，就可以通过编号矩阵的索引直接对图像的某些区域重新赋值。

def cds(img):
    dct = getIndDct(img)
    lst = uniqueDct(dct)
    arr = img.reshape(-1)*0
    for i,L in enumerate(lst, 1):
        arr[L] = i
    return arr.reshape(img.shape)

测试

接下来，将这个连通域算法应用到硬币图像上，由于上面的硬币图案有很多噪声，会影响连通域计算结果，所以先对其进行预处理

from scipy.ndimage import binary_erosion

b = img>0.4
bb = binary_erosion(b, np.ones([5,5]))
c = cds(bb)
drawImg(img, c, 'gray', 'jet')

效果如下