Segmentation techniques
Segmentation techniques broadly fall into one of two classes...Edge-based techniques such as the Canny detector [Can86] involve convolving the image with a filter to produce an edge map from which the regions may be extracted. The main problems associated with this technique arise from the creation of spurious edge points and incomplete boundaries, making region extraction difficult. Application of additional cleaning techinques (eg: median filtering, non-maximal suppression) along with the use of boundary completion algorithms can improve the results, although the specific techniques required are usually image-dependent, and so the segmentation suffers a loss of generality.
Region-based segmentation techniques such as Split/Merge [Perry89] operate by attempting to grow regions, merging areas with similar grey-level statistics. One of the advantages of this approach is that the regions formed will have complete boundaries, and so filling algorithms are unnecessary. However, the success of such techniques is found to be very dependent on the choice of the statistical measures and the threshold used in the merging phase, so, as when using edge based methods, producing a generic segmentation system is difficult.
Co-occurrence matrices
A co-occurrence matrix [HB90] is a mapping of an image to a different space (co-occurrence space). It is formed from an image I using the prescription |
[1] |
between
and
where
is a pixel,
is the
grey-level of the pixel, and
is the
displacement between pixels. The direction of the
displacement is typically taken as a unit vector in one of
four or eight directions (ie: 0 degrees, 45 degrees, 90
degrees, etc...). For use as a means of texture analysis,
the matrix is usually calculated in each of these
directions and then averaged [Park86] .
The below image would be expected to be segmented into 3 distinct regions - one for the red pixels, one for the green pixels, and one for the blue pixels - we're ignoring the black lines which are there only to make the demarcation easier for humans...
Figure 1 : Simple image for segmentation
The relationship between the grey-level histogram and the co-occurrence matrix for an image having M x M pixels and N grey-levels can be expressed by summing the elements of the co-occurrence matrix as expressed in equation below:
 |
[2] |
... where H(i) is the grey-level histogram of the image.
Co-occurence Segmentation
To illustrate how co-occurrence matrices may be used for segmentation, consider the simple image shown in Figure 1. Pixels within the blue area of the image have an almost uniform grey level of ≅ 90. Therefore by considering equation 1 we see that these pixels will contribute to elements of the co-occurrence matrix where i ≅ j ≅ 90. In a similar way, all uniform areas of brightness will affect different points on the leading diagonal, and assuming the grey levels are significantly different it may be possible to classify areas of the matrix as belonging to certain classes. In this way, the co-occurrence matrix is used as a feature space on which classification boundaries may be drawn.
Figure 2 : Co-occurrence matrix of the simple image
Now consider the contribution to the elements of the co-occurrence matrix made by pixels on region boundaries. The contribution of these pixels will be to elements of the co-occurrence matrix where i is not equal to j. These off-diagonal distributions may be separated in a similar way, and classification boundaries formed for edge and non-edge pixels.
To develop a more formal methodology for using the co-occurrence as a feature space, it is necessary to first make some assumptions about the properties of an image. Consider an image as consisting of A regions, each of uniform brightness distorted by additive Gaussian noise. It is then possible to write the conditional probability for a pixel belonging to region a to have grey-level i as
 |
[3] |
where Ca is determined by
 |
[4] |
where p(x) is the probability of x, μa is the average brightness of region a, and σa is the standard deviation of region a. Now, assuming that a pixel is in region a and its delta-neighbour is in region b, it is possible to write:
 |
[5] |
where Cab is determined by
 |
[6] |
What is in fact required is the probability that a pixel is a member of class a given that its grey level is i and the grey level of its delta-neighbour is j, or p(a | i ; j). This can be determined from the following relationship
 |
[7] |
Using Bayes' rule,
 |
[8] |
where p(a ; b) is the probability of a pixel belonging to region a and its delta-neighbour belonging to region b and p(i ; j) is the joint probability of a pixel having grey-level i and its delta-neighbour having grey-level j. From the definition of the co-occurrence matrix (equation 1), we have:
 |
[9] |
The other two probability terms required to calculate
cannot be directly calculated but can be parameterised.
This is achieved by assuming the elements of the
co-occurrence matrix are composed of a sum of Gaussian
distributions.
 |
[10] |
By finding suitable values for p(a), μa, and σa it is possible, using equation 8 to assign to each pixel a set of probabilities that it is a member of each class. These probabilities may then be used directly for classification (ie: highest probability wins) or passed on to a relaxation process. In our segmentation system, the latter option is chosen, and the relaxation algorithm is run until convergence is achieved for the vast majority of pixels. This is usually the case after 4 to 6 iterations through relaxation, and results in a clean image as input to further processing.
| ← Introduction | Flow theory → |