Contextual segmentation or Region growing
Non-contextual thresholding groups pixels with no account of their relative locations in the image plane. Contextual segmentation is better at separating individual objects because it takes into account how close pixels that belong to the same object are to each other. Based on signal discontinuity or similarity, there are two fundamental methods for contextual segmentation. 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 neighborhoods. 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 the neighborhood 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)}.
Figure: (A) 4-neighbourhood, (B) 8-neighbourhood
This is one of the easiest and most common ways to label connected regions after greyscale or colour thresholding. It uses the "grassfire" or "wave propagation" principle, which says that once a "fire" or "wave" starts at one pixel, it spreads to any of the pixel's 4- or 8-neighbors found 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.
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) − &muR| ≤ &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.
This type of 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.
Split-and-merge segmentation
the top-down split-and-merge algorithm considers of the whole image as one region and then iteratively splits each region into subregions or merges adjacent regions until all regions become uniform or until the desired number of regions have been established. A common splitting strategy for a square image is to divide it recursively into smaller and smaller quadrants until, for any region R, the uniformity predicate P(R) is TRUE. The strategy builds a top-down quadtree: if P(image) is FALSE, the image is divided into four quadrants; if P(quadrant) is FALSE, the quadrant is divided into subquadrants; and so on.