连通域求解

图像处理中连通域指由前景相同像素，并且相同像素邻接的像素组成的域。图像处理中一般都是对二值图像（1白色，0为黑色，一般前景为0黑色）做连通域分析。连通域分析指把连通域找出来并且标记出来。

连通域标记方法：（1）两次遍历实现；（2）深度优先搜索遍历

1.第一次遍历

如果当前元素为0则赋值一个label，lebel从大于1开始，如果像素的邻接像素的标签有大于1的，则当前元素赋值为大于1的最小的label。记录等价标签。

第二次遍历

遍历找到等价标签，标记等价标签的最小值为label。

如果只求连通域的数量则只需循环一次就够了，连通域数等于label-等价标签的个数-label起始值。

如：起始标记为label = 1，等价标签存放在列表中，list=[(2,6),(3,7)],即等价标签个数有len(list),则连通域个数为label -1-len(list).

如果需要将连通区域标记的的话需要循环两次。

import numpy
a = [[1 for i in range(10)] for j in range(10)]
a = [[1, 0, 0, 1, 1, 1, 1, 1, 1, 1],
     [1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
     [1, 1, 1, 0, 0, 0, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
     [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
     [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
     [1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
     [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 1, 1, 1, 0, 1]]
a = numpy.array(a)
#cv2.imwrite('/home/lijq/IdeaProjects/AnimalRecognition_Demo/demo/person3.jpg',a)
label = 1
list = []
if a[0][0]<1:
    label +=1
    a[0][0] = label
for j in range(1,len(a[0])):
    if a[0][j]<1:
        if a[0][j-1]>1:
            a[0][j]=a[0][j-1]
        else:
            label +=1
            a[0][j] = label
for i in range(1,len(a)):
    if a[i][0]<1:
        if a[i-1][0]>1:
            a[i][0]=a[i-1][0]
        else:
            label +=1
            a[i][0] = label
for i in range(1,len(a)):
    for j in range(1,len(a[0])):
        if a[i][j]<1:
            if a[i][j-1]>1 and a[i-1][j]>1:
                a[i][j] = min(a[i][j-1],a[i-1][j])
                if a[i][j-1]!=a[i-1][j]:
                    list.append((a[i][j-1],a[i-1][j]))
            elif a[i][j-1]>1 and a[i-1][j]==1:
                a[i][j] = a[i][j-1]
            elif a[i-1][j]>1 and a[i][j-1] ==1:
                a[i][j] = a[i-1][j]
            else:
                label += 1
                a[i][j] = label
nums_lt = label-1-len(list)
print label,list,nums_lt
print a

2.深度遍历标记

通过深度优先把所有连通的找出来标记完，再继续遍历下一个连通区域。连通域数量为 label-1.（设置的label默认值为1，歧视标记为2，如果从1标记的话会和图像值里的1混淆，所以为了方便起始值可以是任意大于1的数）

a = [[1, 0, 0, 1, 1, 1, 1, 1, 1, 1],
     [1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
     [1, 1, 1, 0, 0, 0, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
     [1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
     [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
     [1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
     [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
     [1, 1, 1, 1, 1, 1, 1, 1, 0, 1]]
a = numpy.array(a)
def dfs(nums,i,j,label):
    if i >=len(nums) or j>=len(nums[0]) or i<0 or j<0:
        return
    if nums[i][j]<1:
        nums[i][j]=label
        dfs(nums,i,j+1,label)
        dfs(nums,i+1,j,label)
        dfs(nums,i-1,j,label)
        dfs(nums,i,j-1,label)
        dfs(nums,i-1,j-1,label)

label = 1
for i in range(len(a)):
    for j in range(len(a[0])):
        if a[i][j]<1:
            label +=1
            a[i][j] = label
            dfs(a,i,j+1,label)
            dfs(a,i+1,j,label)
print a