A Comparative Study of Fuzzy C-Means and Possibilistic Fuzzy C-Means Algorithm on Noisy Grayscale Images

A Comparative Study of Fuzzy C-Means and Possibilistic Fuzzy C-Means Algorithm on Noisy Grayscale Images

Sachin Singla

M.Tech IT Student Department of Computer Science & IT

BBSBEC, Fatehgarh Sahib

Baljit Singh Khehra

Associate Professor Department of Computer Science & IT

BBSBEC, Fatehgarh Sahib

Abstract Grouping is used to organize graphical data in the cluster's unsupervised learning methods. Grouping is used in the field of image processing to identify objects that have the same characteristics in an image. Clustering can be categorized into Hard and Fuzzy clustering scheme. This paper deals with the study of clustering soft (Fuzzy) algorithm outputs such as Fuzzy C-Means (FCM) and Possibilistic Fuzzy C-Means (PFCM). These algorithms are used to segment and analyze standard and colored images, but this research work involves noisy images in gray levels. PSNR, MSE and SSIM are used as an evaluation parameter to compare the FCM and PFCM results. Finally, the experimental results proved that PFCM favorable on FCM.

Keywords Image segmentation, Clustering, FCM, PFCM.

1. INTRODUCTION

   Image segmentation is an important step behind image understanding and image analysis, such as positioning objects and boundaries, machine vision and medical imaging. The purpose of segmentation is to divide the image into a set of different, visually distinct, uniform and significant areas based on certain characteristics such as intensity, color, and texture. Many different segmentation techniques have been discovered and can be seen in [1-3]. Image segmentation is divided into four techniques, namely, threshold, edge detection, grouping and extraction. However, this paper only deals with image segmentation based on method Clustering.

   c=1

   Clustering is used to process similar items, based on their respective data in the data set being grouped into groups. Assembling the data elements into clusters depends on the principle of maximizing similarity dissimilarity and reduces the similarity of things. The data items are assigned to the eligible cluster based on the minimum distance of the data item. The quality of clusters depends on low interclass and high intraclass similarity [4]. Clustering can be divided into hard and fuzzy clustering schemes, and each person has their own characteristics. Hard clusters limit each data point to exactly one cluster. Therefore, the use of hard clustering is a

   means is a widely used algorithm, in which each data item has a certain degree of membership value, which is used to determine the proximity of data items to clusters [5,6]. In Fuzzy C, each data item can belong to one or more clusters. FCM has a problem, it creates noise.

   To avoid this problem, Krishnapuram and Keller proposed a new fuzzy clustering model called c-mean probability (PCM) [7, 8]. PCM uses typical values instead of member values, but PCM has the problem of overlapping clusters. PFCM is a better clustering algorithm because it has the potential to give members or typical values more value [9]. PFCM inherits the properties of PCM and FCM and generally avoids various problems such as cluster matching and noise sensitivity. Section II discusses the FCM, Section III discusses the PFCM, Section IV presents the experimental results which include some of the evaluation parameters, comparing FCM and PFCM, and Section V concludes the paper.

2. FUZZY C MEANS (FCM)

   Fuzzy C-means clustering is a part of two or more groups of data items and allows Dunn developed in 1973 [10]. This standard is widely used in pattern recognition and image, such as medical, geological and satellite images. In K-Means each data point belonging to the cluster or not, that is, belongs to the class of single cluster, but fuzzy clustering extends this concept, based on the membership function for each data point is assigned two or more groups. In K-means, each data point a value of 0 or 1, but diffuse, each data point is a percentage value between 0 and 1, which shows the amount of data pointing to a cluster. It is bound by the information sum for each data point, the value of all cluster members to be a [9,11,12]. Calculate the member function, and the value of each data element with the highest number of all cluster members are associated. The purpose of the algorithm is to minimize the following objective function:

   very difficult task in which the image has poor contrast, overlapping intensity, noise, and the like.

   (; ; ) =

   n

   r=1

   (cr)m c2

   (1)

   Another clustering scheme is fuzzy clustering based on the membership of each data item. In fuzzy clustering, fuzzy C-

   Where, X is the objective function, cr are the membership values, m fuzziness factor whose value must be greater than 1, is the rth data point, c is the cth cluster centroid and c2 is Euclidean distance.

   Let A is the dataset,

   = { , , , } and list of cluster centers

   n m c2

   represented by

   1 2 n

   = { , , , }. Algorithmic steps for Fuzzy C-

   c =

   r=1 cr

   n

   m

   (5)

   Means:

   1 2 c

   r=1 cr

   1. Provide the number of cluster i.e. i

   2. Randomly set cluster centroids.

   3. Randomly initialize membership value to = [cr] between 0 and 1.

   4. Compute fuzzy membership [cr] using:

   5. Compute membership values = [cr] if distance between image pixel and its centroid is greater than 0. Membership values calculated using (2).

   6. Compute typicality values T= [cr] if distance between image pixel and its centroid is greater than 0. Typicality values calculated using following equation:

   1

   cr = 2

   (2)

   cr = 1

   (6)

   1

   i c m1 1+( c2)(1)

   j=1( )

   j

   Here, 1 c i, 1 r n

   5. Compute center Vector using:

   Here, 1 c i, 1 r n

   7. Calculate the center Vector iusing:

   n m

   (m+t )ar

   = r=1 cr r

   (3)

   = =1 cr cr

   (7)

   n m

   (m +t )

   r=1 cr =1 cr cr

   Here, 1 c i

   1. Stop, if r+1 r < , otherwise go to step 3.

   2. Here is termination criteria between [0,1] and = [cr] is a fuzzy membership matrix.

3. POSSIBILISTIC FUZZY C-MEANS (PFCM)

   FCM has problems in handling noise and outliers. PCM has the problem of coincident clustering, and FPCM has difficulty when the data set is large because the typical value will be very small. The obvious problem with all FPCMs is that they impose constraints on the typical values (the sum of the typicalities for all data points for a particular cluster is 1). We relax the constraints on the typical values, but leave the column constraint on member values. In 1997,

   J. C. and N. R. Bezdek Pal suggested PFCM is a good clustering algorithm for performing classification tests because it has the ability to be more important to the canonical or membership value. The PFCM is a hybrid of PCM and FCM, which generally avoids the various problems of PCM, FCM and FPCM. The purpose of this algorithm is to minimize the following objective function:

   1. Stop, if error is less or equal to r+1 < , otherwise go to step 6.

      Now, its possible to determine the cluster using membership and typicality values.

4. EXPERIMENTAL RESULTS

   In this paper, several noise gray scale images are tested to show the results obtaned from the clustering algorithm. An image is acquired from a database of still images. Noise is added to the original grayscale image using matlab's default Gaussian noise function. Matlab also has the function of parameters PSNR, MSE and SSIM to check the image quality of grayscale images [13]. Based on the above parameters, this study summarizes which clustering algorithm is more suitable for noise gray-scale image segmentation.

   In this work, the size of the noise gray-scale image is 255 * 255, and the K-Means, FCM and PFCM algorithms are tested with different initial conditions and output shown in Figure 1.

   1. FCM

      min

      {(, , , ) =

      n (m + t )

      2 +

      • Total cluster taken: 2

        (,,)

        c=1

        r=1 cr

        cr c

      • Centroid randomly initialized

        i c=1

        n r=1

        (1 cr)} (4)

        • Maximum iteration: 200

          c

          =1

          Subject to constraint = 1 , and 0, 1. Here b>0, a>0, >1, m>1 and > 0 are user defined constants. The constants a, b are used to define the relative proportions of the values of the typicality and membership values. In above objective function = [] is a membership matrix analogous to FCM and

          = [], a typicality matrix analogous to PCM algorithm. If giving

          more importance to the membership values that PFCM work closer to the FCM algorithm and if giving more importance to the values of typicity than PFCM work closer to PCM.

          Let A is the dataset, = {1, 2, , n} and list of cluster centers represented by = {1, 2, , c}. Set the various parameters b>0, a>0, >1, m>1. Algorithmic steps for PFCM:

          1. Provide the number of cluster i.e. c

          2. Randomly set clusters centroids.

          3. Run FCM Algorithm described in section II.

          4. With the help FCM algorithm results, the penalty parameter c is computed for eeach cluster using following equation and put K=1.

             • Membership matrix assigned randomly

             • Parameter values are m=2, Epsilon = 0.0001

   2. PFCM

      • Total cluster taken: 2

      • Centroid randomnly initialized

      • Maximum Iteration: 200 and Epsilon =0.0001

      • Typicality and Membership matrix initialized randomly

      • PFCM checked for various parameter values are

        • a=1, b=1, m=2, =2

        • a=2, b=1, m=2, =2

        • a=1, b=2, m=2, =2

          Original Image

          FCM Result (For m=2)

          ESDST – 2017 Conference Proceedings

          For a=1 and b=2

          For a=2 and b=1

          For a=1 and b=1

          PFCM Results( m=2,=2)

          b)

          e)

          d)

          c)

          a)

          Fig. 1. Comparative results for different noisy grayscale images named cat, zelda, house, pepper and circuit, a) The

          original Images, b) FCM results, (c-e) PFCM results for various parameter values.

          TABLE 1. MSE VALUES FOR SEGMENTED IMAGES BY FCM AND PFCM ALGORITHM

          Original Image Name	FCM (m=2)	PFCM (m=2,=2)
          		For a=1 and b=1	For a=2 and b=1	For a=1 and b=2
          Cat	0.0293	0.0223	0.0231	0.0224
          Zelda	0.0327	0.0281	0.0283	0.0285
          House	0.0461	0.0409	0.0428	0.0420
          Pepper	0.0355	0.0316	0.0316	0.0307
          Circuit	0.0260	0.0191	0.0205	0.0192

          TABLE II. PSNR VALUES FOR SEGMENTED IMAGES BY FCM AND PFCM ALGORITHM

          Original Image Name	FCM (m=2)	PFCM (m=2,=2)
          		For a=1 and b=1	For a=2 and b=1	For a=1 and b=2
          Cat	63.4675	64.6429	64.4870	64.6232
          Zelda	62.9790	63.6491	63.6197	63.5750
          House	61.4936	62.0107	61.8198	91.9016
          Pepper	62.6247	63.1403	63.1390	63.2545
          Circuit	63.9811	65.3209	65.0041	65.3025

          ESDST – 2017 Conference Proceedings

          TABLE III. SSIM VALUES FOR SEGMENTED IMAGES BY FCM AND PFCM ALGORITHM

          Original Image Name	FCM (m=2)	PFCM (m=2,=2)
          		For a=1 and b=1	For a=1 and b=1	For a=1 and b=1
          Cat	0.9977	0.9983	0.9982	0.9983
          Zelda	0.9974	0.9978	0.9977	0.9978
          House	0.9961	0.9965	0.9964	0.9965
          Pepper	0.9971	0.9975	0.9974	0.9975
          Circuit	0.9978	0.9984	0.9984	0.9985

   3. Evaluation Parameters

   1. MSE: By all pixels and summing the squared difference divided by the total number of pixels, pixel by pixel to calculate the mean square error Lets assume an Image A= {1, 2, . , } and Image B= {1, 2, . , } with m no. of pixels then,

5. CONCLUSION

In this work, the Gaussian noise function is used to add artifacts to different gray-scale images to demonstrate that PFCM provides better results in noise-gray images than FCM. After analysis of the results obtained for the PSNR, MSE, and SSIM of the noise gray scale image, it is shown that the PFCM is effective

(, ) = 1 m

b 2

(8)

and robust. The results obtained from the PFCM algorithm are

m i=1 i i

The smaller the MSE value, the better the image quality. Table 1 shows the FCM and PFCM results between the real and reconstructed images of each algorithm.

1. PSNR: The peak signal-to-noise ratio is described in decibels (dB) as the maximum value of the maximum signal power of the MSE, which is assumed to be the noise power. Lets assume an Image A= {1, 2, . , } and Image B= {1, 2, . , } with m no. of pixels then PSNR is given by,

   closer to the FCM algorithm and require more computation time than the FCM. Therefore, future work needs to develop new methods or improve which are beneficial to noise gray-scale images and provide better image quality.

   ACKNOWLEDGMENT

   The author would like to express his sincere gratitude to all faculty and staff of Baba Banda Singh Bahadur Engineering Institute and Fatehgarh Sahib for their invaluable advice on research.

   REFERENCES

   1. R. C. Gonzalez, R. E. Woods, Digital Image Processing, 3rd

      (, ) = 1010

      ( 2) (9)

      (,)

      ed., Prentice Hall, New Jersey (2008).

   2. K. S. Fu, A survey on image segmentation, Pattern Recognition, Vol. 13, pp. 316(1981).

      For 8-bit grayscale images, the maximum value is 255. The higher

      the value of the peak signal to noise ratio, the bette the image quality. Table 2 shows the results of the calculation of the FCM and PFCM between the real and reconstructed images for each algorithm.

2. SSIM :Structural similarity indices measure the structural similarity between real and reconstructed images. Its value is between -1 and 1. When the two images are equal, the SSIM approaches 1. The SSIM evaluation index is based on the calculation of three terms, namely, brightness, contrast, and structural terms. The overall SSIM exponent is then the product of the above three terms as follows:

2 2 2 2

(, ) = (2AB+1)(2AB+2) (10)

(A+B+K1)(A+B+2)

Where, 1 = (0.01 ). ^2 2 = (0.03 ). ^2 is the regularization constants and is dynamic range value, A, is the local means and A, is the standard deviation, is cross variance.

The higher the SSIM value, the better the image quality. In this work, the matlab function SSIM is used to check the quality of the image. Table 3 shows the FCM and PFCM results between the real and reconstructed images of each algorithm.

Table (1-3) shows that PFCM has a lower MSE value, higher PSNR and SSIM value, which proves that PFCM produces better results for noise gray scale image.

1. N.R. Pal, S.K. Pal, A review on image segmentation Techniques, Pattern Recoginition, Vol. 26, pp. 1277- 1294(1993).

2. S. Ghosh, S.K. Dubey, Comparative Analysis of K-Means and Fuzzy C-Means, International Journal of Advanced Computer Science and Applications (IJACSA), Vol. 4, No. 4(2013).

3. J. C. Bezdek, Pattern Recognition With Fuzzy Objective Function Algorithms, New York: Plenum (1981).

4. D.C. Park, Intuitive fuzzy C-means algorithm for MRI segmentation, IEEE International Conference on Information Science and Applications (ICISA), pp. 1-7(2010).

5. R. Krishnapuram, J. M. Keller, Apossibilistic approach to clustering, IEEE Trans. Fuzzy Syst.,Vol. 1, No. 2, pp. 98 110(1993).

6. R.J. Almeida, J. M. C. Sousa, Comparison of fuzzy clustering algorithms for classification, IEEE International Symposium on Evolving Fuzzy Systems, pp. 112-117(2006).

7. N.R. Pal, K. Pal, J.M. Keller, J.C. Bezdek, A Possibilistic Fuzzy c-Means Clustering Algorithm, IEEE Trans. on Fuzzy Systems, Vol. 13, No. 4, pp. 517-530(Aug. 2005).

8. J. C. Dunn, A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters, Journal of Cybernetics, 3(3), pp. 32-57(1973).

9. L.A. Zadeh, Fuzzy sets, Information and control, 8(3), 338- 353(1965).

10. Yong Yang, Image Segmentation By Fuzzy C-Means Clustering Algorithm with a novel penalty term, Computing and informatics, Vol. 26, pp. 17-31(2007).

11. Yusra, A. Y. AI-Najjar, Dr. Der Chen Soong, Comparison of image quality assessment: PSNR, HVS, SSIM, UIQI, International Journal of Scientific and Engineering Research, 3(3), 1-5(2012).