连通域

图像的连通域是指图像中具有相同像素值并且位置相邻的像素组成的区域，连通域分析是指在图像中寻找出彼此互相独立的连通域并将其标记出来。提取图像中不同的连通域是图像处理中较为常用的方法，在目标检测等领域对感兴趣区域分割与识别。一般情况下，一个连通域内只包含一个像素值，因此为了防止像素值波动对提取不同连通域的影响，连通域分析常处理的是二值化后的图像。

在了解图像连通域分析方法之前，首先需要了解图像邻域的概念。图像中两个像素相邻有两种定义方式，分别是4-邻域和8-邻域。

OpenCV-python自带了连通域函数，如下：以下的标记方法只为了解原理。

• cv2.connectedComponents(image, labels=None, connectivity=None, ltype=None)

• cv2.connectedComponentsWithAlgorithm(image, connectivity, ltype, ccltype, labels=None)

• cv2.connectedComponentsWithStats(image, labels=None, stats=None, centroids=None, connectivity=None, ltype=None)

• cv2.connectedComponentsWithStatsWithAlgorithm(image, connectivity, ltype, ccltype, labels=None, stats=None, centroids=None)

参数详解：

image：待标记不同连通域的单通道图像，数据类型必须为CV_8U。
labels：标记不同连通域后的输出图像，与输入图像具有相同的尺寸。
connectivity：标记连通域时使用的邻域种类，4表示4-邻域，8表示8-邻域。
ltype：输出图像的数据类型，目前支持CV_32S和CV_16U两种数据类型。
ccltype：标记连通域时使用的算法类型标志，可以选择的参数下表中给出。

标志参数	简记	作用
CCL_WU	0	8-邻域使用SAUF算法，4-邻域用SAUF算法
CCL_DEFAULT	-1	8-邻域使用BBDT算法，4-邻域用SAUF算法
CCL_GRANA	1	8-邻域使用BBDT算法，4-邻域用SAUF算法

4-邻域连通域标记

Lookup Table：

Source	Distination
1	1
2	2
3	1

一开始被打上1标签的像素（即Source=1的像素）最终被分配到的标签1（Distination=1）；一开始被打上3标签的像素（即Source =3的像素）最终被分配的的标签也为1（Distination=1）。

算法如下：

1. 从左上角开始进行光栅扫描。

2. 如果当前遍历到的像素i(x,y)是黑像素的什么也不干。如果是白像素，考察该像素的 上方像素i(x,y-1) 和 左边像素i(x-1,y)，如果两个的取值都为0，将该像素分配一个新的标签。

   在这里我们用数字做标签，即1,2,3,4等。

3. 如果两个像素中有一个不为0（也就是说已经分配了标签），将上方和左边的像素分配的标签中数值较小的那一个（0除外）分配给当前遍历到的像素i(x,y)。在这里，将上方像素和左边像素的标签写入Lookup Table的Source，将当前遍历的像素i(x,y)分配的标签写入Distination。

4. 最后，对照Lookup Table，对像素分配的标签由Source变为Distination。

像这样的话，邻接像素就可以打上同样的标签了。因为这里是做4-4−邻域连通域标记，所以我们只用考察上方像素和左边像素。

import cv2
import numpy as np


def four_cc_label(img):
    height, width, channel = img.shape
    label = np.zeros((height, width), dtype=np.int32)
    LUT = np.zeros(height * width,dtype=np.uint8)

    COLORS = np.array([[0, 0, 255], [0, 255, 0], [255, 0, 0],
                       [255, 255, 0], [255, 0, 255], [0, 255, 255],
                       [125, 0, 255], [0, 255, 125], [255, 0, 125], 
                       [255, 255, 125], [255, 125, 255], [0, 125, 255]],dtype=np.uint8)
    out = np.zeros((height, width, channel), dtype=np.uint8)
    label[img[:,:, 0] > 0] = 1

    n = 1
    for y in range(height):
        for x in range(width):
            if label[y, x] == 0:
                continue
            c3 = label[max(y - 1, 0), x]
            c5 = label[y, max(x - 1, 0)]
            if c3 < 2 and c5 < 2:
                n += 1
                label[y, x] = n
            else:
                _vs = [c3, c5]
                vs = [a for a in _vs if a > 1]
                v = min(vs)
                label[y, x] = v

                minv = v
                for _v in vs:
                    if LUT[_v] != 0:
                        minv = min(minv, LUT[_v])
                for _v in vs:
                    LUT[_v] = minv

    count = 1

    for l in range(2, n + 1):
        flag = True
        for i in range(n + 1):
            if LUT[i] == l:
                if flag:
                    count += 1
                    flag = False
                LUT[i] = count

    for index, lut in enumerate(LUT[2:]):
        out[label == (index + 2)] = COLORS[lut - 2]
    return out


if __name__ == '__main__':
    img = cv2.imread("123.png")
    out = four_cc_label(img)

    cv2.imwrite("out1234.png", out)
    cv2.imshow("result", out)
    cv2.waitKey(0)
    cv2.destroyAllWindows()

结果输出：

8-邻域连通域标记

要进行8-8−邻域连通域标记，我们需要考察4个像素:
左上 i(x-1,y-1)，正上i(x, y-1)，正左i(x-1,y)，左下i(x+1,y-1)或者右上。

import cv2
import numpy as np


def four_cc_label(img):
    height, width, channel = img.shape
    label = np.zeros((height, width), dtype=np.int32)
    LUT = np.zeros(height * width,dtype=np.uint8)

    COLORS = np.array([[0, 0, 255], [0, 255, 0], [255, 0, 0],
                       [255, 255, 0], [255, 0, 255], [0, 255, 255]],dtype=np.uint8)
    out = np.zeros((height, width, channel), dtype=np.uint8)
    label[img[:,:, 0] > 0] = 1

    n = 1
    for y in range(height):
        for x in range(width):
            if label[y, x] == 0:
                continue
            c2 = label[max(y - 1, 0), min(x + 1, width - 1)]
            c3 = label[max(y - 1, 0), x]
            c4 = label[max(y - 1, 0), max(x - 1, 0)]
            c5 = label[y, max(x - 1, 0)]
            if c3 < 2 and c5 < 2 and c2 < 2 and c4 < 2:
                n += 1
                label[y, x] = n
            else:
                _vs = [c3, c5, c2, c4]
                vs = [a for a in _vs if a > 1]
                v = min(vs)
                label[y, x] = v

                minv = v
                for _v in vs:
                    if LUT[_v] != 0:
                        minv = min(minv, LUT[_v])
                for _v in vs:
                    LUT[_v] = minv

    count = 1
    for l in range(2, n + 1):
        flag = True
        for i in range(n + 1):
            if LUT[i] == l:
                if flag:
                    count += 1
                    flag = False
                LUT[i] = count


    for i, lut in enumerate(LUT[2:]):
        out[label == (i + 2)] = COLORS[lut - 2]
    return out


if __name__ == '__main__':
    img = cv2.imread("123.png")
    out = four_cc_label(img)

    cv2.imwrite("out456.png", out)
    cv2.imshow("result", out)
    cv2.waitKey(0)
    cv2.destroyAllWindows()

参考：
https://www.cnblogs.com/hsy1941/p/11271358.html
https://cloud.tencent.com/developer/article/1581956