首页 / 问题 / 正文

使用Python在图像中寻找连通分量

1 投票
3 回答
20037 浏览
提问于 2025-04-17 22:55

其实，一张图片被分成了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）和递归深度优先搜索，但这两种方法似乎都不太高效，计算一张图片的连接区域大约需要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()
算法优化 图像处理 深度优先搜索 图像矩阵 连通分量 连接区域 像素分类 颜色区间

3 个回答

0

我之前也遇到过类似的问题，不过是在3D方面，我在这里问过这个问题：

提高并查集的效率

我发现并查集算法在我的情况下比其他任何方法都要快得多（这也很合理，因为它的复杂度比较低）

回答于 2025-04-17 由 Python大师
分享 举报
0

深度优先搜索（DFS）是一种不错的算法，但它的递归版本在空间使用上不太高效，而非递归的版本又比较复杂。因此，我建议使用连通组件标记算法。这种算法使用了一种叫做不相交集合的数据结构，通过两次处理来以非递归的方式在线性时间内找到解决方案。

注意：可以使用图像处理库来实现，因为它们有并行的快速实现。

回答于 2025-04-17 由 Python大师
分享 举报
2

这是我之前回答的另一个帖子，内容和这个问题完全一样，里面有一个简单使用深度优先搜索（DFS）的示例代码。

如何在二进制图像中找到连通区域？

修改一下DFS函数：添加一个参数 current_color = {0,1,2}，这样你就可以决定从这个节点是否可以去到另一个节点了。（如果相邻的节点和 current_color 颜色相同，并且还没有被访问过，就递归地访问那个节点）

回答于 2025-04-17 由 Python大师
分享 举报

撰写回答