Hybrid of Fuzzy Logic and Random Walker Method for Medical Image Segmentation

Published Online January 2015 in MECS

Images are the most significant vehicle of expressing information. In this computer vision arena, the information got from images can be used for different critical tasks, for instance: robots navigation, extracting lesion tissues from body scans, detection of malign cells, and recognition of important places (for example Airport) from remote sensing data. Above tasks require a method, which help us to understand images and get information to fulfill our requirements. Image segmentation is best for above requirements, hence, is an initial step in the image analysis process. Image segmentation partitions an image into multiple segments (set of pixels) based on some homogeneity criteria (like color, intensity or texture) to locate and identify objects and boundaries in a digital image [1].

• A.    Segmentation Types

Practically, image Segmentation helps in filtering digital noisy images, medical tasks (Locate tumors and other pathologies, Quantify tissue volumes, Computer guided surgical treatments, Diagnosis, Treatment plan), Locate places in satellite images (airports, roads, forests etc.), recognition tasks (Face Recognition, Fingerprint Recognition, etc.). In the literature, there are many methods for segmentation. Each segmentation technique has different advantages and disadvantages for distinct images and the selection of a segmentation method is determined by the particular type of image and the problem’s features [2].

For segmentation, we use a plethora of segmentation technologies. Based on two attributes of images, these methods are grouped into two categories [1].

• 1.    Detecting Image Discontinuities : In this, an image is segmented when intensities in image changes abruptly, image segmentation algorithm like edge detection fall in this category [3, 4].

• 2.    Detecting Image Similarities: this class of image segmentation divides a digital image into regions which are similar according to pre-specified measures; the example of this type includes image segmentation algorithms like thresholding [4], region growing, region splitting and merging [5,6].

• B.    Random Walker Method

The random walker algorithm is a method for image segmentation. It is based on partial differential equation (a supervised segmentation method) which means user input effects segmentation. This input comprises of seeds (labeling a pixel) i.e. the areas where the user defines whether that area belongs to object which one want to segment or not. Now the random walks start from the unlabeled pixels and the probability is computed to belong to the object. If a user marks K seeds have different label, then it becomes important to calculate the probability for every pixel that a random walk starts from a pixel will first arrive at each seed. This may be determined by solving a system of linear equations. When probabilities got calculated, the pixel is allotted to the label for which it is most potential to send a random walk. The digital image is treated as a weighted graph [7], in which every pixel is like a node which is joined to neighboring nodes by edges, and the changes in image intensities are mapped to edge weights to reflect the similarity between the pixels.

The rest of the paper is organized as follows: Section II gives the overview of Fuzzy Logic including Fuzzy Set Theory and Fuzzy System. A detailed description of the proposed method is presented in Section III. In Section IV, experimental results are described. Finally, section V concludes the research work done in this paper and gives future prospects for further research in this area .

• II.    Fuzzy Logic

Fuzzy logic provides mathematical rules and functions which permitted natural language queries. Fuzzy logic gives ways to calculate intermediate values within absolute truth and absolute false with resulting values between 0.0 and 1.0.It figures the shades of gray within black/white and true/false. It is a substitute to the A- or -not-A, Boolean 1 and 0 logic definitions made by society. Figure1 depicts the basic difference between fuzzy and Boolean logic.

Fig 1. Boolean Logic VS Fuzzy Logic

Information is much ambiguous or inaccurate in the real world. Human thinking filters and translates information in order to arrive at conclusions or to dismiss it as inconclusive. Although machines cannot still deal with imprecise information in the same ways that humans do, in that case fuzzy logic plays an important role as it is basically a type of logic that recognizes more than simple true and false values. Computer programs with fuzzy logic are turning quite useful when the sheer volume of tasks defies human analysis and action. So, a methodical and efficient method for addressing problems of imprecise information is called as fuzzy logic. The data are viewed as fuzzy sets [8] [9].

In various image processing applications, for instance, object recognition and scene analysis, expert knowledge have to be used. Fuzzy set theory and fuzzy logic, offer powerful tools to symbolize and process human facts in shape of fuzzy if-then rules, which also help in image processing tasks. In image processing many problems occur because the data, tasks, and the results are uncertain. That uncertainty, though, is not constant due to the unpredictable, but to the inborn ambiguity and vagueness of image data. Alongside unpredictability-other kinds of flaw in image processing include grayness ambiguity, geometrical fuzziness, and undefined knowledge of image characteristics.

The nature of these problems is fuzzy. The questions whether a pixel ought to become darker or brighter than it already is, the decision about boundary between two image segments, and indicating whether a tree is there in a picture or not, are instances where fuzzy logics can be used.

• A.    Fuzzy Set Theory

Fuzzy logic and fuzzy thinking take place in sets. These are sets whose elements have degrees of membership [10]. The value zero signifies complete nonmembership, value one shows complete membership, and values in between 1 and 0, are meant to characterize intermediate degrees of membership (partial membership).

This can be clarified with an example in relation to people and "youthfulness". In that case the set U (the universe of discourse) is the set of people. “Young” is a fuzzy subset defined to determine the degree up to which a person ‘p’ can be defined young. In the universe of discourse, we have to allot a degree of membership in the fuzzy subset “Young” to every ‘person’. The simplest way to do this is with a membership function grounded on the person's age.

Young (p) = {1, if AGE > = 20,

30 – AGE (p) / 10 if 2030}           (1)

Fig 2. Membership Function

• B .    Fuzzy System

Fig 3. Block Diagram of Fuzzy System

The above figure depicts a block schematic of fuzzy logic, i.e. basic working of fuzzy system [11] [12]. The steps are described below:

System Inputs : These are crisp values. These are transformed into fuzzy sets in the fuzzification step.

System Outputs : These are the results of defuzzification step, i.e. convert output fuzzy sets back to crisp value.

Fuzzification : In this, crisp values are transformed into the degree of membership for linguistic values, such as, far, near, small, big; of fuzzy sets.

Knowledge base block: This block performs aggregation of propositions having linguistic variables; rules can be specified as:

If(x is a) and (y is b)…..then (z is c)

Fuzzy Interface Engine: It combines facts of fuzzification and knowledge base and conduct fuzzy reasoning process.

Defuzzification: This process converts the results back to real world values.

• III.    Proposed Method

Image segmentation is a topic of higher attention on which there has been a lot of research work is performed. Due to this, thousands of different segmentation methods are there in the literature, still a method is required, which can be efficient in all respects regarding the quality of image segmentation and equally well for different type of images [13]. Similarly, Random walker method [14] has some problems that should be addressed. The results produced by random walker method should need to be more efficient and precise. Also, in this method noise is correlated which makes this random walker method not suitable for many applications as it also segments the noise in the image.

In this paper, to address above mentioned problems we have used fuzzy logic and combine it with the random walker segmentation to make the basic method more effective. The proposed method follows following steps:

Step 1. Input original image which you want to be segmented and generate weights based on image intensities. The segmentation is devised on a weighted graph. In order to represent the image structure (given in the pixels) by random walker biases (i.e., edge weights), one must define a function that maps a change in image intensities to edge weights [15] [16] [17] [18]. In that case we have opted (due to empirical causes) the classic Gaussian weighting function specified with an equation:

v(ij) = exp(-a[(b(i) - h(j)]2)        (2)

Where,

h(i) = image intensity at pixel i

h(j) = image intensity at pixel j a = free parameter

Step 2. Obtain a set of pre-labeled (seeds) pixels. These pixels are marked either interactively or automatically. [19]

Step 3. Now random walks start from unseeded pixels and the probability of unlabeled pixels is computed [11].

• i.    Calculate the probability that a random walker starting at an unseeded pixel x first reaches a seed with label ‘ s’

• ii.    Label each pixel with the most feasible seed destination

Step 4. To approximate the boundaries we use fuzzy rules which help us to take a decision about defining boundaries between two segments, which in turn help to produce better segmentation results as compared to earlier methods.

Step 5. After the approximation process weighted graph is build over the boundaries.

Step 6. In the last step we get segmented image finally. It is done by assigning pixel to label for which it has the highest probability.

Fig 4. Flow Chart Of Proposed Technique

Fig 9. (a) Original Image (b) Segmented Image using RWM alone (c) Segmented Image using a combination of RWM and Fuzzy Logic

Fig 12. (a) Original Image (b) Segmented Image using RWM alone (c) Segmented Image using a combination of RWM and Fuzzy Logic

(a)                                    (b)

(c)

Fig 10. (a) Original Image (b) Segmented Image using RWM alone (c) Segmented Image using a combination of RWM and Fuzzy Logic

(a)

(b)

(c)

Fig 13. (a) Original Image (b) Segmented Image using RWM alone (c) Segmented Image using a combination of RWM and Fuzzy Logic

(a)                                       (b)

(c)

Fig 11. (a) Original Image (b) Segmented Image using RWM alone (c) Segmented Image using a combination of RWM and Fuzzy Logic

Fig 14. (a) Original Image (b) Segmented Image using RWM alone (c) Segmented Image using a combination of RWM and Fuzzy Logic

Table 1. Comparison of earlier and purposed method based on BCI

Image set	Proposed Method	Earlier Method
Set 1	1	0.49595
Set 2	1	0.49605
Set 3	1	0.49344
Set 4	1	0.49602
Set 5	1	0.49326
Set 6	0.95286	0.45605
Set 7	1	0.49591
Set 8	1	0.49156
Set 9	1	0.49591
Set 10	0.87857	0.49595

Table 2. Comparison of earlier and purposed method based on LCI

Image set	Purposed Method	Earlier Method
Set 1	0.42333	0.098833
Set 2	0.41667	0.098814
Set 3	0.73667	0.0999326
Set 4	0.41833	0.098819
Set 5	0.77833	0.099362
Set 6	0.41667	0.098814
Set 7	0.42667	0.098842
Set 8	1	0.099695
Set 9	0.42666	0.098842
Set 10	0.42668	0.098846

Table 3. Comparison of earlier and purposed method based on ER

Image set	Purposed Method	Earlier Method
Set 1	2.3622	10.1181
Set 2	2.4	10.12
Set 3	1.3575	10.0679
Set 4	2.3904	10.1195
Set 5	1.2848	10.0642
Set 6	2.4	10.12
Set 7	2.3438	10.1172
Set 8	0.61287	10.0306
Set 9	2.3438	10.1172
Set 10	2.3437	10.1171

Fig 15. Bar chart comparing values of BCI

Fig 16. Bar chart comparing values of LCI

Fig 17. Bar chart comparing values of ER

Above computed values (in tables and bar charts) depicts that BCI and LCI for proposed technique is increased as compared to earlier method which signifies that the texture of resulted image is better after segmentation. ER, has minified i.e. results have lesser number of misclassified pixels, leading to improved image quality.

• V.    Conclusion And Future Work

Image segmentation has greater use for isolation of images in different segments to diagnose lesions and other important information in an image. In the current paper, we have modified the random walker. A novel random walker algorithm has been presented by combining the features of fuzzy logic with it. We have verified this approach on various medical images and compared this new method with basic random walker method and results found satisfactory. In this new technique, the probability that a pixel belongs to a given seed region is calculated by using fuzzy technique. In future we will apply the fuzzy technique with K mean clustering and verify the results with this modification .