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

Question

实际上一个图像被离散化为 3 个 bin (0,1,2)。所以任何落入特定 bin 的颜色都被替换为 bin 号。因此离散化图像可以看作是这个矩阵:

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 的示例代码。

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

修改DFS函数:增加一个参数current_color = {0,1,2}，这样就可以决定是否可以从这个节点去到另一个节点。 (如果nabouring节点与current_color颜色相同，还没有访问，则递归访问该节点)