使用python查找图像中连接的组件

Question

实际上，一个图像被分解为3个存储箱（0,1,2）。因此，任何属于特定存储箱的颜色都将替换为存储箱编号。因此，离散化的图像可以被视为此矩阵：

a=[[2,1,2,2,1,1],
[2,2,1,2,1,1],
[2,1,3,2,1,1],
[2,2,2,1,1,2],
[2,2,1,1,2,2],
[2,2,1,1,2,2]]

下一步是计算连接的组件。单个组件将用字母（A；B；C；D；E；F等）标记，我们需要保留一个表，该表维护与每个标签相关联的离散化颜色，以及该标签的像素数。当然，如果存在相同颜色的多个相邻区域，则相同的离散化颜色可以与不同的标签相关联。图像可能会变成

b=[[B,C,B,B,A,A],
[B,B,C,B,A,A],
[B,C,D,B,A,A],
[B,B,B,A,A,E],
[B,B,A,A,E,E],
[B,B,A,A,E,E]]   

连接组件表为：

Label  A  B  C D E
Color  1  2  1 3 1
Size   12 15 3 1 5

设q=4。分量A、B和E的像素大于q，分量C和D的像素小于q。因此，A、B和E中的像素被分类为相干，而C和D中的像素被分类为非相干。此图像的CCV将是

Color :        1  2  3
coherent:      17 15 0
incoherent:    3  0  1

因此，给定的颜色桶可以仅包含相干像素（如2所示），仅包含非相干像素 （如所做的3），或相干和非相干像素的混合（如所做的1）。如果我们假设只有3种可能的离散颜色，CCV也可以写成 <；（17；3）；（15；0）；（0；1）>； 三种颜色

请任何人帮助我查找连接组件的算法

我已经实现了迭代dfs和递归dfs，但这两种方法都似乎效率低下，它们需要将近30分钟来计算图像的连接组件。有人帮我找到它吗？我没时间提交我的项目了。我正在粘贴两个代码：

图像大小：384*256 使用递归dfs的代码：

import cv2
import sys
from PIL import Image
import ImageFilter
import numpy
import PIL.Image
from numpy import array
stack=[]
z=0
sys.setrecursionlimit(9000000)

def main():
    imageFile='C:\Users\Abhi\Desktop\cbir-p\New folder\gray_image.jpg'
    size = Image.open(imageFile).size
    print size
    im=Image.open(imageFile)
    inimgli=[]
    for x in range(size[0]):
        inimgli.append([])
        for y in range(size[1]):
            inten=im.getpixel((x,y))
            inimgli[x].append(inten)
    for item in inimgli:
        item.insert(0,0)
        item.append(0)
    inimgli.insert(0,[0]*len(inimgli[0]))
    inimgli.append([0]*len(inimgli[0]))
    blurimg=[]
    for i in range(1,len(inimgli)-1):
            blurimg.append([])
            for j in range(1,len(inimgli[0])-1):
                            blurimg[i-1].append((inimgli[i-1][j-1]+inimgli[i-1][j]+inimgli[i-1][j+1]+inimgli[i][j-1]+inimgli[i][j]+inimgli[i][j+1]+inimgli[i+1][j-1]+inimgli[i+1][j]+inimgli[i+1][j+1])/9)

    #print blurimg 
    displi=numpy.array(blurimg).T
    im1 = Image.fromarray(displi)
    im1.show()
    #i1.save('gray.png')
    descretize(blurimg)

def descretize(rblurimg):
    count=-1
    desc={}
    for i in range(64):
        descli=[]
        for t in range(4):
            count=count+1
            descli.append(count)
            desc[i]=descli
        del descli
    #print len(rblurimg),len(rblurimg[0])
    #print desc
    drblur=[]
    for x in range(len(rblurimg)):
        drblur.append([])
        for y in range(len(rblurimg[0])):
            for item in desc:
                if rblurimg[x][y] in desc[item]:
                    drblur[x].append(item)
    #displi1=numpy.array(drblur).T
    #im1 = Image.fromarray(displi1)
    #im1.show()
    #im1.save('xyz.tif')
    #print drblur
    connected(drblur)
def connected(rdrblur):
    table={}
    #print len(rdrblur),len(rdrblur[0])
    for item in rdrblur:
        item.insert(0,0)
        item.append(0)
    #print len(rdrblur),len(rdrblur[0])
    rdrblur.insert(0,[0]*len(rdrblur[0]))
    rdrblur.append([0]*len(rdrblur[0]))
    copy=[]
    for item in rdrblur:
        copy.append(item[:])
    global z
    count=0 
    for i in range(1,len(rdrblur)-1):
        for j in range(1,len(rdrblur[0])-1):
            if (i,j) not in stack:
                if rdrblur[i][j]==copy[i][j]:
                    z=0
                    times=dfs(i,j,str(count),rdrblur,copy)
                    table[count]=(rdrblur[i][j],times+1)
                    count=count+1
    #z=0
    #times=dfs(1,255,str(count),rdrblur,copy)
    #print times
    #print stack
    stack1=[]
    #copy.pop()
    #copy.pop(0)
    #print c
    #print table
    for item in table.values():
        stack1.append(item)

    #print stack1
    table2={}
    for v in range(64):
        table2[v]={'coherent':0,'incoherent':0}
    #for item in stack1:
    #    if item[0] not in table2.keys():
    #        table2[item[0]]={'coherent':0,'incoherent':0}
    for item in stack1:
        if item[1]>300:
            table2[item[0]]['coherent']=table2[item[0]]['coherent']+item[1]

        else:
            table2[item[0]]['incoherent']=table2[item[0]]['incoherent']+item[1]
    print table2
    #return table2


def dfs(x,y,co,b,c):
    dx = [-1,-1,-1,0,0,1,1,1]
    dy = [-1,0,1,-1,1,-1,0,1]
    global z
    #print x,y,co
    c[x][y]=co
    stack.append((x,y))
    #print dx ,dy
    for i in range(8):
        nx = x+(dx[i])
        ny = y+(dy[i])
        #print nx,ny
        if b[x][y] == c[nx][ny]:
            dfs(nx,ny,co,b,c)
            z=z+1
    return z




if __name__ == '__main__':
  main()

迭代dfs：

def main():
    imageFile='C:\Users\Abhi\Desktop\cbir-p\New folder\gray_image.jpg'
    size = Image.open(imageFile).size
    print size
    im=Image.open(imageFile)
    inimgli=[]
    for x in range(size[0]):
        inimgli.append([])
        for y in range(size[1]):
            inten=im.getpixel((x,y))
            inimgli[x].append(inten)
    for item in inimgli:
        item.insert(0,0)
        item.append(0)
    inimgli.insert(0,[0]*len(inimgli[0]))
    inimgli.append([0]*len(inimgli[0]))
    blurimg=[]
    for i in range(1,len(inimgli)-1):
            blurimg.append([])
            for j in range(1,len(inimgli[0])-1):
                            blurimg[i-1].append((inimgli[i-1][j-1]+inimgli[i-1][j]+inimgli[i-1][j+1]+inimgli[i][j-1]+inimgli[i][j]+inimgli[i][j+1]+inimgli[i+1][j-1]+inimgli[i+1][j]+inimgli[i+1][j+1])/9)
    #print blurimg 
    #displi=numpy.array(blurimg).T
    #im1 = Image.fromarray(displi)
    #im1.show()
    #i1.save('gray.png')
    descretize(blurimg)
def descretize(rblurimg):
    count=-1
    desc={}
    for i in range(64):
        descli=[]
        for t in range(4):
            count=count+1
            descli.append(count)
            desc[i]=descli
        del descli
    #print len(rblurimg),len(rblurimg[0])
    #print desc
    drblur=[]
    for x in range(len(rblurimg)):
        drblur.append([])
        for y in range(len(rblurimg[0])):
            for item in desc:
                if rblurimg[x][y] in desc[item]:
                    drblur[x].append(item)
    #displi1=numpy.array(drblur).T
    #im1 = Image.fromarray(displi1)
    #im1.show()
    #im1.save('xyz.tif')
    #print drblur
    connected(drblur)
def connected(rdrblur):
    for item in rdrblur:
        item.insert(0,0)
        item.append(0)
    #print len(rdrblur),len(rdrblur[0])
    rdrblur.insert(0,[0]*len(rdrblur[0]))
    rdrblur.append([0]*len(rdrblur[0]))
    #print len(rdrblur),len(rdrblur[0])
    copy=[]
    for item in rdrblur:
        copy.append(item[:])
    count=0
    #temp=0
    #print len(alpha)
    for i in range(1,len(rdrblur)-1):
        for j in range(1,len(rdrblur[0])-1):
            if (i,j) not in visited:
                dfs(i,j,count,rdrblur,copy)
                count=count+1

    print "success"

def dfs(x,y,co,b,c):
    global z
    #print x,y,co
    stack=[]
    c[x][y]=str(co)
    visited.append((x,y))
    stack.append((x,y))
    while len(stack) != 0:
        exstack=find_neighbors(stack.pop(),co,b,c)
        stack.extend(exstack)
    #print visited
    #print stack
    #print len(visited)
    #print c
    '''while (len(stack)!=0):
        (x1,y1)=stack.pop()
        exstack=find_neighbors(x1,y1)
        stack.extend(exstack)'''

def find_neighbors((x2,y2),cin,b,c):
    #print x2,y2
    neighborli=[]
    for i in range(8):
        x=x2+(dx[i])
        y=y2+(dy[i])
        if (x,y) not in visited:
            if b[x2][y2]==b[x][y]:
                visited.append((x,y))
                c[x][y]=str(cin)
                neighborli.append((x,y))
    return neighborli



if __name__ == '__main__':
    main()

Answer 1

DFS是一种很好的算法，但递归算法空间效率低，非递归算法非常复杂，因此我建议connected component labelling算法在线性时间内采用不相交集数据结构，以非递归的方式求解。

注意：使用图像处理库的方法与使用并行快速实现的方法相同。

Answer 2

我也有类似的问题，但在3D中，我在这里问了一个问题：

Increasing efficiency of union-find

我发现union-find算法在我的案例中比任何其他算法都快得多（考虑到复杂性，这是有意义的）

Answer 3

这是我回复的另一个帖子 其中包括一个简单使用DFS的示例代码。

How do I find the connected components in a binary image?

修改DFS函数：添加一个参数current_color={0,1,2}，这样您就可以决定是否可以从此节点转到另一个节点。（如果nabouring节点与current_color具有相同的颜色并且尚未访问，则递归访问该节点）