title: finding connected components in an image using python
body: <p>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: </p>
  
  <pre><code>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]]
  </code></pre>
  
  <p>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</p>
  
  <pre><code>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]]   
  </code></pre>
  
  <p>and the connected components table will be:</p>
  
  <pre><code>Label  A  B  C D E
  Color  1  2  1 3 1
  Size   12 15 3 1 5
  </code></pre>
  
  <p>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</p>
  
  <pre><code>Color :        1  2  3
  coherent:      17 15 0
  incoherent:    3  0  1
  </code></pre>
  
  <p>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
  &lt;(17; 3) ; (15; 0) ; (0; 1)>
  for three colors </p>
  
  <p>Please anybody help me with the algorithm for finding connected components </p>
  
  <p>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:</p>
  
  <p>Image size:384*256
  code using recursive dfs:</p>
  
  <pre><code>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]&gt;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()
  </code></pre>
  
  <p>iterative dfs:</p>
  
  <pre><code>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()
  </code></pre>