Dissertation Phase-I: Synopsis

Topic:
OPTIMUM THRESHOLDING USING FUZZY TECHNIQUES

Guided by- Presented by-
Mr.Puneet Manocha Anupama (Roll No.1600872)
Assit. Professor IIIrd Semester, M.Tech (ICE)

OBJECTIVE: * To review different research papers based on Fuzzy Thresholding. * To apply fuzzy thresholding technique to an image * To calculate optimum threshold using Gamma membership function.
LITERATURE REVIEW:
Introduction:
Typical computer vision applications usually require an image segmentation-preprocessing algorithm as a first procedure. At the output of this stage, each object of the image, represented by a set of pixels, is isolated from the rest of the scene. The purpose of this step is that objects and background are separated into non-overlapping sets. There are various techniques of segmentation and among them threshold is much simpler than other segmentation techniques. Usually, this segmentation process is based on the image gray-level histogram. In that case, the aim is to find a critical value or threshold. Through this threshold, applied to the whole image, pixels whose gray levels exceed this critical value are assigned to one set and the rest to the other. For a well-defined image, its histogram has a deep valley between two peaks. Around these peaks the object and background gray levels are concentrated. Thus, to segment the image using some histogram thresholding technique, the optimum threshold value must be located in the valley region.
What is Thresholding?
Thresholding: Is a popular, fast and computationally inexpensive segmentation technique. Thresholding is a method to divide an image containing two regions of interest: object and background. E.g. In a text, the characters are generally darker than the paper. In pictures of mitotic cells, chromosomes or tracks are darker or lighter than the background. In all these cases, the gray level histogram of the picture displays the peaks corresponding to the two gray levels: characters and the paper, chromosomes or tracks and background. In thresholding an appropriate threshold is chosen that separates these peaks and segments the picture into two or more segments: one for the object and the other for the background. A histogram containing a single peak is called unimodal, two peaks are called bimodal, and multiple peaks are called multimodal.
A complete segmentation of an image R is a finite set of regions R1, R2, R3… RN such that
R=i=1NRi and Ri∩ Rj=∅ i≠j
Thresholding is a transformation of an input image A into a segmented output image B as follows: bij=1, for aij≥T = 0 for aij≤T, where T is the threshold bij=1, for the image pixels that belong to the object class bij=0, for the image pixels that belong to the background class

However, the selection of the threshold is very crucial in segmenting an image. If the threshold is not selected properly, proper segmentation cannot be obtained. One such segmentation performed using threshold value too high and too low is shown in fig.1. If the threshold value is more than the actual threshold, the image is over segmented and if the threshold value is less than the actual threshold, the image is less segmented.
In many practical situations the image pixel are not precise and the boundaries between the regions, the edges demarcating a segment, and the definition of the regions are imprecise or vague. Fuzzy thresholding techniques are more appropriate in dealing with such images and the resulting threshold images are more accurate. Each pixel is assigned a membership degree using a appropriate membership function and the threshold is selected by an optimum threshold selection method.

Figure 1: Image thresholding: (a) original image, (b) threshold too low, (c) threshold segmentation and (d) threshold too high
Types of Thresholding:
There are different strategies of thresholding, namely, (a) global threshold, (b) local thresholding, (c) iterative thresholding, (d) multispectral thresholding, and (e) optimal thresholding. These strategies are discussed briefly.
Global Thresholding: In global thresholding, the image is considered as whole and threshold value remains constant throughout the image. Depending on the modality of the histogram, the threshold levels may be single, double, or multiple.

A single threshold determines the value by iterating each pixel independent of its neighborhood. In this, the histogram contains two peaks: object and background.
For a double threshold, when an image consist of two objects of different gray levels, two different threshold values are used to threshold the image. The histogram that is trimodal contains three peaks: two for the object and one for the background.
Locally adaptive thresholding: In local thresholding, the image is divided into several windows or regions and thus threshold is not constant throughout the image. Rather, the threshold values vary throughout the image and there is one threshold for each window. The threshold value depends on the local statistics of the region such as variance, mean, etc., of the image. It may be termed as regional thresholding. It works well when the intensities are not uniform and multiple objects are present with different gray levels. Such types of images are the real images, for e.g. medical images where the images are not properly illuminated. One possible way is replacing each pixel by mean and standard deviation of its local neighborhood of size b x b. Threshold may be calculated as
Ti,j=mi,j+k.σ(i,j)
Where m, σ, and k are the local mean, variance, and bias setting, respectively.
Another possible way is to divide the image into several windows and then calculate the threshold is for each window. Then the image is thresholded using all the threshold values of the windows.
Iterative Thresholding: Iterative Thresholding is one of the iterative schemes. Initially a threshold value, T, is selected for an image using the average of the background and foreground regions. With this threshold value, the image is thresholded into two regions, R1 and R2. Again the mean is calculated for the two regions and a new threshold, Tn+1=mTn(obj)+mTn(back)/2 is selected, where mTn(obj) and mTn(back) are the means of the object and background regions at the nth iteration. The same step is repeated till there is no appreciable change in the threshold, Tn-Tn-1.

Optimal Thresholding: In an image, histogram peaks are not always clear. An image may consist of slight variations of gray levels and so prominent peaks may not be present. Peaks may overlap, and choosing a threshold in the valley between two overlapping peaks will not classify the pixels into different regions. There are various methods for threshold selection that deal with the probability densities of the image histogram using normal distributions. The gray level distribution is modeled as a mixture of two Gaussian or normal distributions for the object and background. The threshold is selected corresponding to the minimum probability value between the maxima of two normal distributions, which results in minimum error segmentation. But there is a difficulty in estimating the normal distribution parameters together with an uncertainty in considering the distribution normal. These difficulties can be eliminated by using the technique called optimum thresholding, where an optimum threshold is selected. In optimum thresholding, a criterion function is designed that yields some measure of separation between regions. The criterion function is calculated for each gray level, and the gray value that maximizes the measure is chosen as the threshold. There are many different methods, such as maximizing the gray level variance, minimizing the classification of the error probability based on the condition that the histogram are Gaussian, entropy, similarity, and moment, measure of fuzziness.
Multispectral thresholding: Many images such as color images contain three spectral (color) bands, for e.g. red, green, and blue. Multispectral remote sensing images or meteorological satellite images may have even more spectral bands that require multispectral thresholding. Segmentation in this case is based on n-dimensional vectors of gray levels in n spectral bands for each pixel or small pixel neighborhood. This segmentation is widely used in remote sensing. Image segmentation in this case may be achieved by using a multilevel thresholding. The simplest way to threshold an image is to obtain a threshold independently in each spectral band and combine them into a single segmented image.
Fuzzy Based Thresholding: * It considers the uncertainty in the image due to the imprecise pixel gray levels and vagueness in image regions and boundaries. * This uncertainty is incorporated in the form of membership function, which is the degree of belongingness of the pixels in an image. * Then using some fuzzy measures such as entropy, fuzzy divergence, fuzzy similarity etc., and an optimum threshold is selected. Fuzzy Based Thresholding Methods: 1. Entropic based thresholding: It result in algorithms that use the entropy of the foreground (object) and background regions, the cross-entropy between the original and binarized image, etc. 2. Clustering based thresholding: It considers the thresholding as a two-class clustering problem. There are some algorithms such as fuzzy c-means (FCM) etc. 3. Fuzzy geometry based thresholding: optimizes geometrical measures such as compactness, index of area coverage, etc 4. Fuzzy divergence, similarity, and index of fuzziness based thresholding: minimizes or maximizes measures of fuzziness and image information such as index of fuzziness or crispness, fuzzy entropy, fuzzy divergence etc. Because of its simplicity and high speed, this approach is the most used fuzzy technique.
Otsu's method
In computer vision and image processing, Otsu's method is used to automatically perform clustering-based image thresholding, or, the reduction of a gray level image to a binary image. The algorithm assumes that the image to be thresholded contains two classes of pixels or bi-modal histogram (e.g. foreground and background) then calculates the optimum threshold separating those two classes so that their combined spread (intra-class variance) is minimal. The extension of the original method to multi-level thresholding is referred to as the Multi Otsu method.[6] Otsu's method is named after Nobuyuki Otsu. In Otsu's method we exhaustively search for the threshold that minimizes the intra-class variance (the variance within the class), defined as a weighted sum of variances of the two classes:

Weights are the probabilities of the two classes separated by a threshold and variances of these classes.
Otsu shows that minimizing the intra-class variance is the same as maximizing inter-class variance:

Which is expressed in terms of class probabilities and class means.
The class probability is computed from the histogram as:

While the class mean is:

Where is the value at the center of the ith histogram bin. Similarly, you can compute and on the right-hand side of the histogram for bins greater than.
The class probabilities and class means can be computed iteratively. This idea yields an effective algorithm.
Algorithm [6] 1. Compute histogram and probabilities of each intensity level 2. Set up initial and 3. Step through all possible thresholds maximum intensity 1. Update and 2. Compute 4. Desired threshold corresponds to the maximum 5. You can compute two maxima (and two corresponding thresholds). is the greater max and is the greater or equal maximum 6. Desired threshold =

(b) Image thresholded using Otsu's algorithm
(a) Original image

Figure 2: an example of Image thresholding using Otsu's method
Following fuzzy approaches to image thresholding:
Fuzzy clustering considers the thresholding as a two-class clustering problem. There are some algorithms such as fuzzy c-means (FCM), possibilistic c-means (PCM), etc. that can be applied to image thresholding.
Rule-based approach uses fuzzy if–then rules to find the suitable threshold. This method is suitable if there exists explicit expert knowledge about the image (e.g. in medical applications).
Fuzzy-geometrical approach optimizes geometrical measures such as compactness, index of area coverage, etc. This approach uses, in contrast to other fuzzy techniques, spatial image information.
Information-theoretical approach minimizes or maximizes measures of fuzziness and image information such as index of fuzziness or crispness, fuzzy entropy, fuzzy divergence, etc. Because of its simplicity and high speed, this approach is the most used fuzzy technique in the literature
Application of Thresholding * In medical imaging: there is need to detect the changes due to the abnormal activity of the blood cells or sometimes need to count the blood cells for different disease detection. * To segment blood vessels and blood cells in pathological images e.g. Angiogenesis: An increase in the number. Of blood vessels may lead to cancer in prostates, mammary, etc. * In video surveillance: there is a need to track the activity of the object when cameras are recording around 20-30 frames per sec.

REFERENCES 1. Tamalika chaira, “Intuitionistic Fuzzy Segmentation of Medical Images”, IEEE Transactions on Biomedical Engg., vol. 57, No. 6, June 2010 2. Hamid R.Tizhoosh, “Image Thresholding using type-ll fuzzy sets”, Pattern Recognition Society. Published by Elsevier Ltd,Feb.2005, pp 2363-2372, 2003. 3. Abutaleb, A.S., “Automatic thresholding of gray-level pictures using two dimensional entropy”, Computer Vision Graphics and Image Processing, no-47, pp-22-32, 1989. 4. Brink, A. D., “Thresholding of digital images using two dimensional histogram and fuzzy entropy principle”, IEEE Transaction in Image Processing,9, 4, 2000 5. Chaira, T. and Ray, A. K., “Threshold selection using fuzzy set theory”, Pattern Recognition Letters, 25, 865-874,2004. 6. Nobuyuki Otsu, "A threshold selection method from gray-level histograms". IEEE Trans. Sys., Man., Cyber. 9 (1): 62–66. 1979