**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*

_{1}to another pixel

*p*is defined as the sequence of pixels {

_{n}*p*

_{1},

*p*

_{2}, ...,

*p*} such that

_{n}*p*

_{i}_{+1}is a 4-neighbour of

*p*for all

_{i}*i*= 1, ...,

*n*−1. The path is

**8-connected**if

*p*

_{i}_{+1}is an 8-neighbour of

*p*. A set of pixels is a

_{i}**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*| ≤ &Delta and FALSE otherwise where (

_{R}*x,y*) is a pixel from the region

*R*and μ

*is the mean value of signals*

_{R}*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

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.

Sign up here with your email

ConversionConversion EmoticonEmoticon