Contextual segmentation: Region growing in MATLAB

www.spiroprojects.com

Non-contextual thresholding groups pixels with no account of their relative locations in the image plane. Contextual segmentation can be more successful in separating individual objects because it accounts for closeness of pixels that belong to an individual object. Two basic approaches to contextual segmentation are based on signal discontinuity or similarity. Discontinuity-based techniques attempt to find complete boundaries enclosing relatively uniform regions assuming abrupt signal changes across each boundary. Similarity-based techniques attempt to directly create these uniform regions by grouping together connected pixels that satisfy certain similarity criteria. Both the approaches mirror each other, in the sense that a complete boundary splits one region into two.

Pixel connectivity

Pixel connectivity is defined in terms of pixel neighbourhoods. A normal rectangular sampling pattern producing a finite arithmetic lattice {(x,y): x = 0, 1, ..., X−1; y = 0, 1, ..., Y−1} supporting digital images allows us to define two types of neighbourhood surrounding a pixel. A 4-neighbourhood {(x−1,y), (x,y+1), (x+1,y), (x,y−1)} contains only the pixels above, below, to the left and to the right of the central pixel (x,y). An 8-neighbourhood adds to the 4-neighbourhood four diagonal neighbours: {(x−1,y−1),(x−1,y), (x−1,y+1), (x,y+1), (x+1,y+1), (x+1,y), (x+1,y−1), (x,y−1)}.

A 4-connected path from a pixel p₁ to another pixel p_n is defined as the sequence of pixels {p₁, p₂, ..., p_n} such that p_i₊₁ is a 4-neighbour of p_i for all i = 1, ..., n−1. The path is 8-connected if p_i₊₁ is an 8-neighbour of p_i. A set of pixels is a 4-connected region if there exists at least one 4-connected path between any pair of pixels from that set. The 8-connected region has at least one 8-connected path between any pair of pixels from that set.
One of the simplest and most common algorithms for labelling connected regions after greyscale or colour thresholding exploits the "grassfire" or "wave propagation" principle: after a "fire" or "wave" starts at one pixel, it propagates to any of the pixel's 4- or 8-neighbours detected by thresholding. Each already visited (i.e. "burnt away" or "wet") pixel cannot be visited again, and after the entire connected region is labelled, its pixels are assigned a region number, and the procedure continues to search for the next connected region. Magenta and yellow stars below indicate the fire, or wave front and the burnt away pixels, respectively. To label a region, the fire starts from its first chosen pixel:

The 4- and 8-connectivity produce different segmentation results:

Moreover, each definition leads to contradictions between the discrete and continuous cases. For example, an one-pixel-wide vertical or horizontal 8-connected line separates two 8-connected regions but this separation does not hold after the line is only slightly rotated with respect to the image lattice:

At the same time, the like 4-connected line breaks into disjoint pieces after such a rotation:

Modern digital geometry has developed theoretically justified approaches to escape these problems. In many practical cases, the connectivity is simply defined variously for objects (foreground pixels) and background, e.g. 4-connectivity for objects and 8-connectivity for background or vice versa:

Binary image 64×64 (zoom by a factor of 5)

86 foreground 4-connected regions

10 foreground 8-connected regions

Region similarity

The uniformity or non-uniformity of pixels to form a connected region is represented by a uniformity predicate, i.e. a logical statement, or condition being true if pixels in the regions are similar with respect to some property (colour, grey level, edge strength, etc). A common predicate restricts signal variations over a neighbourhood: the predicate P(R), where R denotes a connected region, is TRUE if |f(x,y) − f(x+ξ,y+η)| ≤ Δ and FALSE otherwise (here, (x,y) and (x+ξ,y+η) are the coordinates of neighbouring pixels in region R. This predicate does not restrict the grey level variation within a region because small changes in signal values can accumulate over the region.
Intra-region signal variations can be restricted with a similar predicate: P(R) = TRUE if |f(x,y) − &mu_R| ≤ &Delta and FALSE otherwise where (x,y) is a pixel from the region R and μ_R is the mean value of signals f(x,y) over the entire region R.

Region growing

The bottom-up region growing algorithm starts from a set of seed pixels defined by the user and sequentially adds a pixel to a region provided that the pixel has not been assigned to any other region, is a neighbour of that region, and its addition preserves uniformity of the growing region.

Greyscale image

Seed regions

Region growing results

Such a segmentation is simple but unstable. It is very sensitive to a chosen uniformity predicate, i.e. small changes of the uniformity threshold may result in large changes of the regions found. Also, very different segmentation maps are obtained under different routes of scanning an image, different modes of exhausting neighbours of each region, different seeds, and different types of pixel connectivity.

SPIRO THE TECH GURU