Region growing:
a recursive approach

This is the counterpart of the edge linking mechanism which is based on local comparison of pixel properties without reference to a more global viewpoint. Regions (or pixels) should be merged if they are homogeneous, i.e. have similar grey level intensity, colour, texture, depth etc. In a segmented image,

where S is the number of regions in the image, and is a Boolean homogeneity evaluation of region i, based normally on a statistical measure such as the standard deviation of the grey levels about the mean pixel intensity. In the segmented image, regions must be be both homogeneous and maximal, by which we mean that the homogeneity criteria would cease to be true if adjacent regions were merged.

First we consider a recursive algorithm (iterative equivalents scan the image top to bottom, left to right) based on a 4-connected model of image connectivity.

where denotes the current pixel, and , , and denote the upper, left, lower (down) and right pixels respectively in a 4-connected image matrix. (In an 8-connected matrix the central pixel would also be connected to the diagonal pixels.) The object is to compare the current pixel to each of the adjacent pixels to see if it can be added to an existing region. The algorithm is expressed with reference to a grey scale image.

An initial pixel must be found. This may satisfy some predetermined criteria, e.g. start with the most red or brightest pixel, or may start from some predetermined location, e.g. the centre of the image. When the recursive function terminates, there will, in general, be a group of pixels conjoined to form a labelled region with property I. The process must be repeated for another start pixel with similar or different property value. For example, if the goal was colour segmentation it might be appropriate to form the red regions, then when no more red pixels can be found to form the green regions and so on.

Algorithm for recursive region growing (4-connected version)


Start from point (x,y) with property I.

Recursive_label(x, y); Begin f(x, y) := label; x := x - 1; { recurse left } If f(x, y) = I and pixel not labelled then recursive_label(x, y); x := x + 2; { recurse right } If f(x, y) = I and pixel not labelled then recursive_label(x, y); x := x - 1; y := y - 1; { recurse up } If f(x, y) = I and pixel not labelled then recursive_label(x, y); y := y + 2; { recurse down } If f(x, y) = I and pixel not labelled then recursive_label(x, y); End;


[ Regional segmentation | Splitting and merging ]

Comments to: Sarah Price at ICBL.