由于最近做实验用到二值图像连通区域（八连通）标记，刚开始的时候为了验证算法有效性，用了递归的方法（太慢了，而且图像一大就容易栈溢出），最后查看了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
八邻域连通区域标记Python实现
参考：MATLAB，opencv连通区域标记算法
