Region Growing python

Question

I working on region growing algorithm implementation in python. But when I run this code on output I get black image with no errors. Use CV threshold function on input image and for seed value I use mouse click to store x,y values in tuple.

def get8n(x, y, shape):
    out = []
    if y-1 > 0 and x-1 > 0:
        out.append( (y-1, x-1) )
    if y-1 > 0 :
        out.append( (y-1, x))
    if y-1 > 0 and x+1 < shape[1]:
        out.append( (y-1, x+1))
    if x-1 > 0:
        out.append( (y, x-1))
    if x+1 < shape[1]:
        out.append( (y, x+1))
    if y+1 < shape[0] and x-1 > 0:
        out.append( ( y+1, x-1))
    if y+1 < shape[0] :
        out.append( (y+1, x))
    if y+1 < shape[0] and x+1 < shape[1]:
       out.append( (y+1, x+1))
    return out

def region_growing(img, seed):
    list = []
    outimg = np.zeros_like(img)

    list.append((seed[0], seed[1]))
    while(len(list)):
        pix = list[0]
        outimg[pix[0], pix[1]] = 255
        for coord in get8n(pix[0], pix[1], img.shape):
            if img[coord[0], coord[1]] > 0:
                outimg[coord[0], coord[1]] = 255
                list.append((coord[0], coord[1]))
        list.pop(0)
    return outimg

def on_mouse(event, x, y, flags, params): 
    if event == cv2.EVENT_LBUTTONDOWN: 
        print 'Seed: ' + str(x) + ', ' + str(y) 
        clicks.append((y,x)) 

clicks = []
image = cv2.imread('lena.jpg', 0) 
ret, img = cv2.threshold(image, 200, 255, cv2.THRESH_BINARY) 
cv2.namedWindow('Input') 
cv2.setMouseCallback('Input', on_mouse, 0, ) 
cv2.imshow('Input', img) 
cv2.waitKey() 
seed = clicks[-1] 
cv2.imshow('Region Growing', region_growing(img, seed)) 
cv2.waitKey() 
cv2.destroyAllWindows()

Answer 1

The solutions presented above are conceptually correct but from a numerical point of view they contain some strong problems making them order N^2 in the number of pixels. There is no need to search a pixel in a list if you can store the information in an array offering random access, also the connectedness function can be cythonized. Also it would be nice to be able to provide your own similarity function.

So here is my proposal for an improved, and definitely much faster version running in a Jupyter noteboook:

First cell for imports:

import numpy as np
import cv2

%pylab inline 

%load_ext Cython

Second cell (don't merge which the first):

%%cython
# Use %%cython -a for more verbose output, note %%cython should be on the first line in the cell!
def get_8_connected(int x, int y, shape):
    cdef int xmax = shape[0]-1
    cdef int ymax = shape[1]-1
    cdef int connected_pixel_x 
    cdef int connected_pixel_y
    cdef int dx, dy
    
    connected_pixels = list()
    
    for dx in range(3):
        for dy in range(3):
            connected_pixel_x  = x + dx - 1
            connected_pixel_y = y + dy - 1
            if connected_pixel_x < 0 or connected_pixel_x > xmax or \
                connected_pixel_y < 0 or connected_pixel_y > ymax or \
                (connected_pixel_x == x and connected_pixel_y == y):
                    pass
            else: 
                connected_pixels.append((connected_pixel_x,connected_pixel_y)) 
    return  connected_pixels

Third cell with the region merging

def region_growing(img, 
                   seed_points, 
                   test = lambda seed_x, seed_y, x, y, img, outimg : img[x,y] != 0,
                   colormap=None):
    
    processed = np.full((img.shape[0],img.shape[1]), False)
    
    if colormap is None:
        outimg = np.zeros_like(img)
    else:
        outimg = np.zeros((img.shape[0],img.shape[1],colormap.shape[1]),dtype=np.uint8)
    
    for index, pix in enumerate(seed_points):
        processed[pix[0], pix[1]] = True
        if colormap is None:
            outimg[pix[0], pix[1]] = img[pix[0], pix[1]]
        else:
            outimg[pix[0], pix[1]]  = colormap[index % len(colormap)]
    
    while(len(seed_points) > 0):
        pix = seed_points[0]
            
        for coord in get_8_connected(pix[0], pix[1], img.shape):
            if not processed[coord[0],coord[1]]:
                test_result = test(pix[0], pix[1], coord[0], coord[1], img, outimg)
                if test_result:
                    outimg[coord[0], coord[1]]  = outimg[pix[0], pix[1]]
                    if not processed[coord[0],coord[1]]:
                        seed_points.append(coord)
                    processed[coord[0],coord[1]] = True
                    
        seed_points.pop(0)
    return outimg

and it can be called from another cell using the same logic as before:

def on_mouse(event, x, y, flags, params):
    if event == cv2.EVENT_LBUTTONDOWN:
        print( 'Seed: ' + str(x) + ', ' + str(y), img[y,x])
        clicks.append((int(y), int(x)))
        
clicks = []
image = cv2.imread('lena.bmp', 0)
ret, img = cv2.threshold(image, 128, 255, cv2.THRESH_BINARY)
cv2.namedWindow('Input')
cv2.setMouseCallback('Input', on_mouse, 0, )
cv2.imshow('Input', img)
cv2.waitKey()
cv2.destroyAllWindows()

seed = clicks
out = region_growing(img, seed)
cv2.imshow('Region Growing', out)
cv2.waitKey()
cv2.destroyAllWindows()

There are some small functional difference. A region in the output is either marked by the value of the original image at the seed or by a value from the optional colormap. The colormap needs to specify RGB colors given als unsigned 8 bit integers. It is also possible to pass in a tailored test function, replacing:

test = lambda seed_x, seed_y, x, y, img, outimg : img[x,y] != 0

with for example:

test = lambda seed_x, seed_y, x, y, img, outimg : abs(img[x,y] - img[seed_x, seed_y]) < 4

would yield all pixels who are connected to the original seed with intensity steps below 4.

In my context it works for monochrome and color images. That is both for 2d arrays and 3D arrays.

If Cython cannot be used the function get_8_connected can be replaced by:

def get_8_connected(x, y, shape):
    xmax = shape[0]-1
    ymax = shape[1]-1
    
    connected_pixels = list()
    
    for dx in range(3):
        for dy in range(3):
            connected_pixel_x  = x + dx - 1
            connected_pixel_y = y + dy - 1
            if connected_pixel_x < 0 or connected_pixel_x > xmax or \
                connected_pixel_y < 0 or connected_pixel_y > ymax or \
                (connected_pixel_x == x and connected_pixel_y == y):
                    pass
            else:
                connected_pixels.append((connected_pixel_x,connected_pixel_y))
    return  connected_pixels```

Answer 2

I had some trouble with your get8n() function so I rewrote it. I believe that the code below does what you were asking. There are two lines in the region_growing() function that are commented out. If you uncomment them they will show an animation of what is happening during the processing. It is a good way to visualize the code and give you a sense of where things are failing.

Also, in your code you left the possibility of adding pixels that you had already processed to your "to be processed" list. This was causing an infinite loop. I've added a check that prevents pixels that have already been processed from being added back into the list.

import cv2
import numpy as np

def get8n(x, y, shape):
    out = []
    maxx = shape[1]-1
    maxy = shape[0]-1
    
    #top left
    outx = min(max(x-1,0),maxx)
    outy = min(max(y-1,0),maxy)
    out.append((outx,outy))
    
    #top center
    outx = x
    outy = min(max(y-1,0),maxy)
    out.append((outx,outy))
    
    #top right
    outx = min(max(x+1,0),maxx)
    outy = min(max(y-1,0),maxy)
    out.append((outx,outy))
    
    #left
    outx = min(max(x-1,0),maxx)
    outy = y
    out.append((outx,outy))
    
    #right
    outx = min(max(x+1,0),maxx)
    outy = y
    out.append((outx,outy))
    
    #bottom left
    outx = min(max(x-1,0),maxx)
    outy = min(max(y+1,0),maxy)
    out.append((outx,outy))
    
    #bottom center
    outx = x
    outy = min(max(y+1,0),maxy)
    out.append((outx,outy))
    
    #bottom right
    outx = min(max(x+1,0),maxx)
    outy = min(max(y+1,0),maxy)
    out.append((outx,outy))
    
    return out

def region_growing(img, seed):
    seed_points = []
    outimg = np.zeros_like(img)
    seed_points.append((seed[0], seed[1]))
    processed = []
    while(len(seed_points) > 0):
        pix = seed_points[0]
        outimg[pix[0], pix[1]] = 255
        for coord in get8n(pix[0], pix[1], img.shape):
            if img[coord[0], coord[1]] != 0:
                outimg[coord[0], coord[1]] = 255
                if not coord in processed:
                    seed_points.append(coord)
                processed.append(coord)
        seed_points.pop(0)
        #cv2.imshow("progress",outimg)
        #cv2.waitKey(1)
    return outimg

def on_mouse(event, x, y, flags, params):
    if event == cv2.EVENT_LBUTTONDOWN:
        print 'Seed: ' + str(x) + ', ' + str(y), img[y,x]
        clicks.append((y,x))
        
clicks = []
image = cv2.imread('lena.bmp', 0)
ret, img = cv2.threshold(image, 128, 255, cv2.THRESH_BINARY)
cv2.namedWindow('Input')
cv2.setMouseCallback('Input', on_mouse, 0, )
cv2.imshow('Input', img)
cv2.waitKey()
seed = clicks[-1]
out = region_growing(img, seed)
cv2.imshow('Region Growing', out)
cv2.waitKey()
cv2.destroyAllWindows()

Here is the result when clicking on the left side of her hat:

Answer 3

Add () for python 3.x like : print("Some things")