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

2023-12-13 08:27:20

问题引入

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

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

在这里插入图片描述

其绘图代码如下,其中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 P_{12} P12?的编号是3,点 P 22 P_{22} P22?的编号是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 ] a:[b, c] a:[b,c] c : [ d , e ] c:[d, e] c:[d,e]合并为 a : [ b , c , d , e ] a:[b, c, d, e] a:[b,c,d,e]。当所有编号都已经归类之后,还可以继续将其变为 [ a , b , 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')

效果如下

在这里插入图片描述

文章来源:https://blog.csdn.net/m0_37816922/article/details/134876274
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。