Background Information

Background Information

Image Thresholding
Entropic Thresholding
Mixture Modelling Thresholding
Threshold Evaluation

A more detailed discussion of these topics can be read in my thesis.

Image Thresholding

Image segmentation is the process of separating an image into meaningful, non-overlapping regions for further analysis. There are two main categories of algorithms for image segmentation. Point or line detection algorithms are those that look for discontinuities between spatially correlated pixels, or region-based segmentation algorithms, which look for regions of similarity according to predefined criteria. Thresholding belongs in this second category (Gonzalez & Woods 2002). Global thresholding is the most basic form of thresholding as it utilises information in an image's histogram and not any spatial information contained in the image. It is a form of clustering relying on the pixels in each region having relatively homogeneous intensities, hence it does have its limitations. As an example, it will fail on images containing highly textured regions.

There are many reasons for using thresholding. Accurately segmenting an image allows for the isolated regions to be analysed in greater detail. Computationally, thresholding is less intensive than some of the other methods currently available as well as being easy to implement successfully. Its use is widespread in such areas as target detection, medical imaging and document analysis to name a few. Since segmentation is often one of the first tasks to be applied to an image, considerations such as these make continued research into thresholding techniques valuable.

Many different thresholding techniques have been proposed. Some algorithms use very different concepts to threshold an image. This thesis focuses on two main categories of thresholding techniques, the entropic and the mixture modelling methods. These are the most recent and are relevant to this research.

Entropic Thresholding

The entropy-based techniques have proven to be successful and reasonably robust (Pun 1980, Kapur, Sahoo & Wong 1985, Wong & Sahoo 1989, Pal & Pal 1989, Ray 1993, Chang, Chen, Wang & Althouse 1994), however they suffer various limitations and are sensitive to noise. These techniques rely on maximising the total entropy of both the object and background regions to find the appropriate threshold. Some of these methods also make use of the pixels' spatial information.

Relative Entropy thresholding (Chang et al. 1994) uses the Kullback-Leibler Information measure to indicate the discrepancy between the probability distribution of the histogram and its approximation. When this function is minimised an appropriate threshold is chosen. Bertolo (2001) based part of his work on the observation that Relative Entropy fits two uniform distributions to the image's actual grey-level distribution and hence is not likely to be an accurate representation of the histogram. Clearly, it is doubtful that any natural images would generate a histogram with such a distribution. Bertolo successfully modified Relative Entropy thresholding by fitting Gaussian and Poisson distributions for the object and background regions with excellent results. By fitting more natural distributions, Bertolo's modifications to Relative Entropy can be seen as specific cases of mixture modelling.

Mixture Modelling Thresholding

Mixture modelling is the process of fitting component distributions with known parameters to an arbitrarily complex probability distribution in order to simplify the task of data clustering and analysis (Wallace & Boulton 1968). As an approach to data clustering the concept seems reasonably intuitive. The most common algorithm for unsupervised learning of finite mixture models is the iterative Expectation-Maximisation (EM) algorithm using Maximum Likelihood (ML) for parameter estimation. Variations of this algorithm have been proposed to perform the unsupervised learning task of finite mixture models and these have been applied to automatic image thresholding (McLachlan & Basford 1988, Sanjay-Gopol & Herbert 1998, Cho, Kim, Park & Park 2000, Lee & Lewicki 2002). Once an appropriate mixture model is chosen, an optimum threshold can be selected in terms of minimum error classification.

Threshold Evaluation

A number of comparative performance studies have been undertaken (Weszka 1978, Sahoo, Soltani, Wong & Chen 1988, Lee, Chung & Park 1990, Glasby 1993, Turi 1994) assessing various types of thresholding algorithms, including information theoretic methods. By nature, comparative studies such as these highlight the need for evaluation criteria that can objectively assess the `goodness' of threshold selection. Different measures have been proposed (Weszka & Rosenfeld 1978, Levine & Nazif 1985, Sahoo, Soltani, Wong & Chen 1988, Lee, Chung & Park 1990) but unfortunately these criteria don't provide a comparative standard. As yet there is no definitive criterion function (or functions) that can completely remove the subjective assessment of threshold evaluation. Within the mixture modelling framework, the suitability of the Kullback-Leibler Information measure as an objective criterion for threshold evaluation is yet to be investigated thoroughly.

The principle of Minimum Message Length Inductive Inference (MML) (Wallace & Boulton 1968) states that the best encoding of the given data is the one that produces the shortest two-part message. The first part of the message describes a model that represents the data, and the second part of the message is the data encoded using the model described in the first part. Minimising the length of this two-part message provides a measure of how appropriate a mixture model is for the given data, whilst taking the complexity of the component distributions into account. The applicability to image thresholding is obvious. The first part of an MML message would describe the mixture model and the second part would encode the image's histogram using the mixture model. It could well be that the classification producing the shortest two-part message according to the MML criterion also produces the most appropriate threshold(s). MML is implemented in the classification program Snob (Wallace et. al. 1968, Wallace & Dowe 1996) which uses the EM algorithm and Minimum Message Length as a convergence criterion.