图像联通区域标记
由于最近做实验用到二值图像连通区域（八连通）标记，刚开始的时候为了验证算法有效性，用了递归的方法（太慢了，而且图像一大就容易栈溢出），最后查看了opencv和MATLAB的实现，做个记录。（为了简单说明，以下说明已四连通为例）
扫描法连通区域标记：
例：对于二值图像、四连通
第一次遍历：
1.建立一个和图像大小一样的矩阵保存结果，原图记为im,结果矩阵记为mask,mask各元素值可初始化为0. 从上到下，从左到右扫描原图像，变量Mark记录当前赋值
2.若当前访问像素坐标（i,j）且im[i,j]不为0，访问maski-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连通区域标记算法
