Region growing

The main goal of segmentation is to partition an image into regions. Some segmentation methods such as thresholding achieve this goal by looking for the boundaries between regions based on discontinuities in grayscale or color properties. Region-based segmentation is a technique for determining the region directly. The basic formulation is:[1]

${\displaystyle (a){\text{ }}\bigcup _{i=1}^{n}{R_{i}=R.}}$

${\displaystyle (b){\text{ }}R_{i}{\text{ is a connected region}},{\text{ i}}={\text{1}},{\text{ 2}},{\text{ }}...,{\text{n}}}$

${\displaystyle (c){\text{ }}R_{i}\bigcap R_{j}=\varnothing ,i\neq j}$

${\displaystyle (d){\text{ }}P(R_{i})=\mathrm {TRUE} {\text{ for }}i=1,2,...,n.}$

${\displaystyle (e){\text{ }}P(R_{i}\bigcup R_{j})=\mathrm {FALSE} {\text{ for any adjacent region }}R_{i}{\text{ and }}R_{j}.}$

${\displaystyle P(R_{i})}$ is a logical predicate defined over the points in set ${\displaystyle R_{i}}$ and ${\displaystyle \varnothing }$ is the null set.

(a) means that the segmentation must be complete; that is, every pixel must be in a region.

(b) requires that points in a region must be connected in some predefined sense.

(c) indicates that the regions must be disjoint.

(d) deals with the properties that must be satisfied by the pixels in a segmented region. For example, ${\displaystyle P(R_{i})={\text{TRUE}}}$ if all pixels in ${\displaystyle R_{i}}$ have the same grayscale.

(e) indicates that region ${\displaystyle R_{i}}$ and ${\displaystyle R_{j}}$ are different in the sense of predicate ${\displaystyle P}$.

The first step in region growing is to select a set of seed points. Seed point selection is based on some user criterion (for example, pixels in a certain grayscale range, pixels evenly spaced on a grid, etc.). The initial region begins as the exact location of these seeds.

The regions are then grown from these seed points to adjacent points depending on a region membership criterion. The criterion could be, for example, pixel intensity, grayscale texture, or colour.

Since the regions are grown on the basis of the criterion, the image information itself is important. For example, if the criterion were a pixel intensity threshold value, knowledge of the histogram of the image would be of use, as one could use it to determine a suitable threshold value for the region membership criterion.

One can use 4-connected neighborhood to grow from the seed points. An alternative for pixels adjacent relationship is the 8-connected neighborhood. Pixels adjacent to the seed points are examined and classified into the seed points if they have the same intensity value. It is an iterated process until there are no change in two successive iterative stages. Other criteria can be chosen; the main goal is to classify the similarity of the image into regions.

• k-means clustering
• Watershed (image processing)

• Jian-Jiun Ding, The class of "Time-Frequency Analysis and Wavelet Transform", the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2007.
• Jian-Jiun Ding, The class of "Advanced Digital Signal Processing", the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2008.
• W. K. Pratt, Digital Image Processing 4th Edition, John Wiley & Sons, Inc., Los Altos, California, 2007
• M. Petrou and P. Bosdogianni, Image Processing the Fundamentals, Wiley, UK, 2004.
• R. C. Gonzalez and R.E. Woods, Digital Image Processing 2nd Edition, Prentice Hall, New Jersey, 2002.