图像联通区域标记

###由于最近做实验用到二值图像连通区域(八连通)标记,刚开始的时候为了验证算法有效性,用了递归的方法(太慢了,而且图像一大就容易栈溢出),最后查看了opencv和MATLAB的实现,做个记录。(为了简单说明,以下说明已四连通为例)

扫描法连通区域标记:

例:对于二值图像、四连通

第一次遍历:

1.建立一个和图像大小一样的矩阵保存结果,原图记为im,结果矩阵记为mask,mask各元素值可初始化为0. 从上到下,从左到右扫描原图像,变量Mark记录当前赋值 2.若当前访问像素坐标(i,j)且im[i,j]不为0,访问mask[i-1]j和mask[i,j-1](若未越界),二者若均为0,Mark++,赋值给当前坐标对应的mask. 若其中一个为0,将非0值赋值给mask[i][j]。 若均非0且相等,将mask[i][j]标记为同一类,若不等将二者最小值赋予mask[i][j],同时将二者合并为同一类(并查集)。

第二次遍历:

根据并查集的内容对区域赋值。

def countRegion(img):
    [high,width] = np.shape(img)
    mask  = np.zeros_like(img)
    mark  = 0
    union = {}
    for i in range (high):
        for j in range(width):
            if i==0 and j==0:
                if img[i][j]==255:
                    mark=mark+1
                    mask[i][j]=mark
                    union[mark]=mark
            if i==0 and j!=0:
                if img[i][j]==255:
                    left = mask[i][j-1]
                    if left!=0:
                        mask[i][j]=left
                    else:
                        mark = mark +1
                        mask[i][j]=mark
                        union[mark]=mark
            if  j==0 and i!=0:
                if img[i][j]==255:
                    up  = mask[i-1][j]
                    up_right = mask[i-1][j+1]
                    if up==0 and up_right==0:
                        mark = mark+1
                        mask[i][j]=mark
                        union[mark]=mark
                    if up==0 and up_right!=0:
                        mask[i][j]=up_right
                    if up_right==0 and up!=0:
                        mask[i][j]=up
                    if up!=0 and up_right!=0:
                        if up==up_right:
                            mask[i][j]=up
                        else:
                            mi = min(up,up_right)
                            mask[i][j]=mi
                            if up<up_right:
                                union[up_right]=up
                            else:
                                union[up]=up_right
            if i!=0 and j!=0:
                if img[i][j]==255:
                    up = mask[i-1][j]
                    up_left = mask[i-1][j-1]
                    left = mask[i][j-1]
                    up_right = 0
                    if j+1<width:
                        up_right = mask[i-1][j+1]
                    ma = max(max(max(up,up_left),up_right),left)
                    if ma==0:
                        mark = mark+1
                        mask[i][j]=mark
                        union[mark]=mark
                    else:
                        if up==up_right and up_right==up_left and up==left:
                            mask[i][j]=up
                        else:
                            mi = min(min(min(up, up_left), up_right), left)
                            if mi!=0:
                                mask[i][j]=mi
                                if up!=mi:
                                    union[up]=mi
                                if up_right!=mi:
                                    union[up_right]=mi
                                if up_left!=mi:
                                    union[up_left]=mi
                                if left!=mi:
                                    union[left]=mi
                            else:
                                n_zero = []
                                if up!=0:
                                    n_zero.append(up)
                                if up_left!=0:
                                    n_zero.append(up_left)
                                if up_right!=0:
                                    n_zero.append(up_right)
                                if left!=0:
                                    n_zero.append(left)
                                mi1 = min(n_zero)
                                mask[i][j]=mi1
                                for it in n_zero:
                                    if it!=mi1:
                                        union[it]=mi1
    for i in range(high):
        for j in range(width):
            key = mask[i][j]
            if key!=0:
                while union[key]!=key:
                    key = union[key]
                mask[i][j]=key
    return mask

参考:MATLAB,opencv连通区域标记算法