使用python查找圖像中的連接組件

Question

實際上，圖像被分類爲3個bin（0,1,2）。因此，任何屬於特定bin的顏色都將被bin no替換。因此，可以將離散圖像視爲此矩陣：

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分鐘計算圖像的連接組件。任何人都可以幫我找到它？我沒有時間提交我的項目。我貼我的兩個代碼：

圖像尺寸：

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：使用遞歸的DFS 384 * 256 代碼

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且尚未參觀，recurssively訪問該節點）

Answer 2

的DFS是好的算法，但遞歸算法是浪費空間和非遞歸一個很複雜的，所以我會建議connected component labelling算法線性時間內兩次使用不相交集數據結構以非遞歸方式求解。

注意：使用圖像處理庫，因爲它們具有並行快速實現。