A simple region growing implementation in Python

Hi all,

Here is a simple example of (simple) Region Growing algorithm in Python.
It is part of my current project, called Tippy.

Tippy tries to implement use the power of OpenCV and Python to fasten Computer Vision prototyping.
The idea is to get as much result as possible with a minimum of code.

A word about region growing , and this implementation :

This approach to segmentation examines neighboring pixels of initial “seed points” and determines whether the pixel neighbors should be added to the region. The process is iterated on, in the same manner as general data clustering algorithms"
Basically, region growing is an iterative method used to extract similar parts of an image. One or several points are chosen as a start. The region then grows until it is finally blocked by the stop criteria. This criteria is generally an inside/outside region comparison (energy, size, . . .).
Region growing is massively used in medical imaging, and object detection. Here is an example of application in automatic Mine Hunting, which I worked with last year at TNO.

The following method uses one seed point, defined by the user. The region grows by comparing with its neighbourhood. The chosen criteria is in this case a difference between outside pixel's intensity value and the region's mean.
The pixel with minimum intensity in the region neighbouhood is chosen to be included. The growing stops as soon as the difference is larger than a threshold.

In this implementation, a 4-connectivity has been chosen. The 8-connectivity should be included soon.
Due to the method itself, only grayscale images may be processed for now. So color images should be converted first.

Here is the input image, the image with the seed point placed, and the final result!

Here is the region growing function implemented in Tippy:

{% highlight python %}
import sys
import cv
import numpy

def simple_region_growing(img, seed, threshold=1):
"""
A (very) simple implementation of region growing.
Extracts a region of the input image depending on a start position and a stop condition.
The input should be a single channel 8 bits image and the seed a pixel position (x, y).
The threshold corresponds to the difference between outside pixel intensity and mean intensity of region.
In case no new pixel is found, the growing stops.
Outputs a single channel 8 bits binary (0 or 255) image. Extracted region is highlighted in white.
"""

try:
    dims = cv.GetSize(img)
except TypeError:
    raise TypeError("(%s) img : IplImage expected!" % (sys._getframe().f_code.co_name))

# img test
if not(img.depth == cv.IPL_DEPTH_8U):
    raise TypeError("(%s) 8U image expected!" % (sys._getframe().f_code.co_name))
elif not(img.nChannels is 1):
    raise TypeError("(%s) 1C image expected!" % (sys._getframe().f_code.co_name))
# threshold tests
if (not isinstance(threshold, int)) :
    raise TypeError("(%s) Int expected!" % (sys._getframe().f_code.co_name))
elif threshold < 0:
    raise ValueError("(%s) Positive value expected!" % (sys._getframe().f_code.co_name))
# seed tests
if not((isinstance(seed, tuple)) and (len(seed) is 2) ) :
    raise TypeError("(%s) (x, y) variable expected!" % (sys._getframe().f_code.co_name))

if (seed[0] or seed[1] ) < 0 :
    raise ValueError("(%s) Seed should have positive values!" % (sys._getframe().f_code.co_name))
elif ((seed[0] > dims[0]) or (seed[1] > dims[1])):
    raise ValueError("(%s) Seed values greater than img size!" % (sys._getframe().f_code.co_name))

reg = cv.CreateImage( dims, cv.IPL_DEPTH_8U, 1)
cv.Zero(reg)

#parameters
mean_reg = float(img[seed[1], seed[0]])
size = 1
pix_area = dims[0]*dims[1]

contour = [] # will be [ [[x1, y1], val1],..., [[xn, yn], valn] ]
contour_val = []
dist = 0
# TODO: may be enhanced later with 8th connectivity
orient = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 4 connectivity
cur_pix = [seed[0], seed[1]]

#Spreading
while(dist<threshold and size<pix_area):
#adding pixels
    for j in range(4):
        #select new candidate
        temp_pix = [cur_pix[0] +orient[j][0], cur_pix[1] +orient[j][1]]

        #check if it belongs to the image
        is_in_img = dims[0]>temp_pix[0]>0 and dims[1]>temp_pix[1]>0 #returns boolean
        #candidate is taken if not already selected before
        if (is_in_img and (reg[temp_pix[1], temp_pix[0]]==0)):
            contour.append(temp_pix)
            contour_val.append(img[temp_pix[1], temp_pix[0]] )
            reg[temp_pix[1], temp_pix[0]] = 150
    #add the nearest pixel of the contour in it
    dist = abs(int(numpy.mean(contour_val)) - mean_reg)

    dist_list = [abs(i - mean_reg) for i in contour_val ]
    dist = min(dist_list)    #get min distance
    index = dist_list.index(min(dist_list)) #mean distance index
    size += 1 # updating region size
    reg[cur_pix[1], cur_pix[0]] = 255

    #updating mean MUST BE FLOAT
    mean_reg = (mean_reg*size + float(contour_val[index]))/(size+1)
    #updating seed
    cur_pix = contour[index]

    #removing pixel from neigborhood
    del contour[index]
    del contour_val[index]

return reg

{% endhighlight %}

Here is a simple test of the function, using Tippy functions. If you only want to use the function, juste remove the tippy stuff and copy the function in your source.
Please note than OpenCV is needed for the function to work ;)

{% highlight python %}
import cv

import tippy.segmentations as se
import tippy.basic_operations as bo
import tippy.display_operations as do

user_input = 0

img_name = "tippy/data/gnu.jpg"
threshold = 20
img = cv.LoadImage(img_name, cv.CV_LOAD_IMAGE_GRAYSCALE)

if user_input:
seed = bo.mouse_point(img, mode="S") # waits for user click to get seed
else:
seed = (70, 106)

out_img = se.simple_region_growing(img, seed, threshold)

do.display_single_image(out_img, "Region Growing result")
{% endhighlight %}

As you can see, the implementation is rather short in code.
An option has been included to let user interactively choose their seed.

Tippy is available here
As the project is in its very beginning, only a few functions are implemented for now.
But I have a lot more coming for you :).

As you can see in the source, tests are included with each function. Applications notes and examples will shortly be available too.
Finally, there is now proper installer for now. Simply add the tippy folder in your sources and include the files you need.

I would be very pleased to find some co-workers. It would allow the library to grow much faster :). So feel free to fork the project ;)
And (constructive) comments are of course encouraged too !

See you soon
Julien