finding connected components in an image using python

Question

Actually an image is descretized into 3 bins (0,1,2) .So any color that falls into particular bin is replaced with the bin no.Therefore discretized image can be viewed as this matrix:

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]]

The next step is to compute the connected components. Individual components will be labeled with letters (A;B;C;D;E;F etc) and we will need to keep a table which maintains the discretized color associated with each label, along with the number of pixels with that label. Of course, the same discretized color can be associated with different labels if multiple contiguous regions of the same color exist. The image may then become

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]]

and the connected components table will be:

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

Let q=4.The components A, B, and E have more than q pixels, and the components C and D less than q pixels. Therefore the pixels in A;B and E are classied as coherent, while the pixels in C and D are classied as incoherent. The CCV for this image will be

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

A given color bucket may thus contain only coherent pixels (as does 2), only incoherent pixels (as does 3), or a mixture of coherent and incoherent pixels (as does 1). If we assume there are only 3 possible discretized colors, the CCV can also be written as <(17; 3) ; (15; 0) ; (0; 1)> for three colors

Please anybody help me with the algorithm for finding connected components

I have implemented iterative dfs and recursive dfs ,but both seem to be inefficient ,they take nearly 30 minutes to compute connected components of an image.Anybody help me how to find it ?I'm running out of time I have to submit my project. I'm pasting both my codes:

Image size:384*256 code using recursive 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()

iterative 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()

Is this an algorithm specific question or Python language specific question ? I think what you need to use BFS (Breadth First Search) or DFS (Depth First Search) to implement a flood-fill to find out the connected componets. — Raiyan, Mar 19 '14 at 06:53
If it is algorithm specific, then putting the tag Python does not make sense. — Raiyan, Mar 19 '14 at 06:55
have a set, that will hold the coordinates of pixels that have not been visited. Do a flood fill starting at the top left. Remove pixels that you fill. When you filled one area, take another coordinate from the set. — Bartlomiej Lewandowski, Mar 19 '14 at 08:44
related: [Finding number of colored shapes from picture using Python](http://stackoverflow.com/q/5298884/4279) — jfs, Mar 19 '14 at 14:18

score 2 · Accepted Answer · edited May 23 '17 at 10:31

2

Here's another post I have answered which doing exactly the same thing which include a sample code using simply DFS.

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

Modify the DFS function: add one parameter current_color = {0,1,2}, so that you can decide if you can go to another node from this node or not. (If the nabouring node has same color with current_color and not yet visit, recurssively visit that node)

edited May 23 '17 at 10:31

Community

1
1

answered Mar 19 '14 at 07:10

shole

4,046
2
29
69

What should I do for a gray scale image – user3320033 Mar 20 '14 at 06:15
Actually, for whatever image,the most important thing is you have defined what is connected component. For example, you may consider a range of color which is 4-connected as a connected component, then what you have to do is change if you can visit from the current pixel(node) to the next pixel based on your rule. – shole Mar 20 '14 at 08:05
I have implemented the same for a gray scale image. Since the image has so many connected components, I get a RuntimeError: maximum recursion depth exceeded. So ,can you help me how to do iterative dfs or two pass algorithm . I have posted what I have implemented here: http://stackoverflow.com/questions/22615109/error-while-printing-connected-components-in-a-gray-scale-image – user3320033 Mar 25 '14 at 06:52
http://stackoverflow.com/questions/9201166/iterative-dfs-vs-recursive-dfs-and-different-elements-order This post provides a straight forward iterative DFS using stack, you may have a look, also read about the accepted answer of the post. – shole Mar 25 '14 at 07:17

Vikram Bhat · Answer 2 · 2014-03-30T09:49:39.927

0

The DFS is good algorithm but the recursive algorithm is space inefficient and non recursive one is very complex so I would advice connected component labelling algorithm which uses disjoint-set datastructure in two pass to get solution in non recursive way in linear time.

Note: Use image processing libraries for the same as they do have parallel fast implementation.

edited Mar 30 '14 at 09:49

answered Mar 19 '14 at 13:55

Vikram Bhat

6,106
3
20
19

I have implemented recursive dfs as well as iterative dfs ,but both take nearly 30-45 minutes to process an image .I have gone through connected component labeling algorithm but I couldn't understand it completely , can you explain me how to do it for a gray scale image – user3320033 Mar 30 '14 at 06:45
@user3320033 for you image size it must not take that long as DFS is O(m*n) algorithm so it would finish less than a second so please check your implementation . You can use connected component labeling algorithm for gray image by using following function to check connectivity Connected(x1,y1,x2,y2) = (Arr[x1][y1]==Arr[x2][y2]) – Vikram Bhat Mar 30 '14 at 09:52

score 0 · Answer 3 · answered May 03 '19 at 15:43

0

I had a similar issue, but in 3D, and asked a question about that here:

Increasing efficiency of union-find

I found the union-find algorithm to be much faster than anything else for my case (which makes sense given the complexity)

answered May 03 '19 at 15:43

rahulv88

101
9

finding connected components in an image using python

3 Answers3