 Open Access
 Total Downloads : 16
 Authors : Pallavi Khare, Anagha Gaikwad, Pooja Kumari,
 Paper ID : IJERTCONV3IS06015
 Volume & Issue : ICONECT – 2015 (Volume 3 – Issue 06)
 Published (First Online): 24042018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Modified Weighted Fuzzy CMeans Clustering Algorithm
Pallavi Khare,
Assistant Professor,
Department of Electronics and Telecommunication, Padmashree Dr. DY. Patil Institute of Engineering and Technology,
Pimpri, Pune18, India.
Anagha Gaikwad,
Student (BE),
Department of Electronics and Telecommunication, Padmashree Dr. DY. Patil Institute of Engineering and Technology,
Pimpri, Pune18, India.
Pooja Kumari,
Student (BE),
Department of Electronics and Telecommunication, Padmashree Dr. DY. Patil Institute of Engineering and Technology,
Pimpri, Pune18, India.
.
AbstractImage segmentation has been a fascinating territory for examination and creating productive calculations, assuming a foremost part in high bore image translation and picture investigation. Image segmentation is defined as action of splitting an image into band of pixels. Aim of this process is to group pixels into regions. This is used in locating objects in satellite images, face recognition, iris recognition, agricultural imaging and medical imaging. Such division requests a powerful division calculation against noise. Clustering is process that make group of similar objects and is widely used technique for brain tumor detection. FCM is very delicate to noise because of the act of just power values for grouping. We proposed a new method Modified FCM algorithm based on the Distance metric for segmentation of images that have been corrupted by intensity inhomogeneities and noise. We define a new tradeoff weighted fuzzy factor to adaptively control the local neighbor relationship. It is followed by an Edge detection algorithm using Canny Edge filter to overcome disconnected locales with openings or districts with a solitary pixel encountered during clustering. The edge detection technique is also to extract boundaries from the segmented image.
KeywordsSegmentation, clustering, tradeoff, distance, FCM, edge, Canny.

INTRODUCTION
Imaging science has longdrawnout basically along three unique yet related lines of examination: division, enrolment and visualization. Enrolment includes discovering the change that brings distinctive images of the same item into strict spatial (and/or worldly) coinciding. Also visualization includes the presentation, control, and estimation of image information. At last, division is characterized as the procedure of parceling an image into set noncovering districts whose union is the whole image where these locales ought to in a
perfect world compare to protests and their significant parts, and foundation. Most image division calculations are focused around two fundamental properties that can be separated from pixel values brokenness and closeness or a mix of them. Division of nontrivial images is a dismal issue made even inflexible by non uniform lighting, shadows, covering items, poor differentiation in the middle of articles and foundation, thus on with some level of accomplishment to this date. Image division can be approached as three philosophical viewpoints – area, limit and edge. Image preparing strategies for quantitative examination are principally utilized as a part of computational medicinal investigation. Therefore, it gets to be conceivable to enhance the demonstrative exactness. It is the vital yet tricky capacity to precisely perceive and depict all the individual questions in an image scene.
Fundamentally we can cerebrate of a few basic ideas for segmentation. Pixel predicated strategies just use the gray estimations of the individual pixels. Area predicated strategies examine the gray values in all the more colossally enormous zones. Definitively, edgepredicated routines locate edges and after that try to tail them. The predominant demand of all these methodologies is that they are predicated just on nearby data. That being said they use this data just somewhat. Pixel predicated methods don't significantly consider the nearby neighborhood. Edgepredicated strategies search just for discontinuities, while area predicated systems break down homogeneous locales. In circumstances where we ken the geometric state of an item, modelpredicated segmentation can be connected.

LITERATURE SURVEY ON SEGMENTATION METHODS VIA
CLUSTERING
Clustering is a methodology which segments a given information set or information focuses into homogeneous
gatherings predicated on given peculiarities such that related objects will be kept in a bunch while different objects will be in diverse clusters. Each one group is spoken to by its mean (centroid) and difference (spread) connected with the dissemination of the relating feature vectors of the information focuses in the bunch. Cluster analysis has been continuously developed and is used in many scientific disciplines such as biology, psychology, statistics, pattern recognition, economics and finance.Conventional data clustering methods can be classified into two broad categories: Hierarchical and Partitional. In hierarchical clustering, the number of clusters need not be specified a priori where only local neighbors in each step are considered. For this reason, it is difficult to handle overlapping clusters through the hierarchical clustering method. In addition, hierarchical clustering is static i.e. data points allocated to a cluster in the early stages may not be moved to a different cluster. Partitional clustering methods develop a clustering structure by optimizing a criterion function defined either locally (on a subset of the patterns) or globally (defined over all of the data). Partitional clustering can be further divided into two classes: crisp clustering and fuzzy clustering. In crisp clustering, a data point belongs to only one cluster and clusters are separated by crisp boundaries among them. In fuzzy clustering methods, data points belong to all clusters through a degree determined by the membership function.

Calculating Distance between Clusters and Popular Distance Measures.
Centroid is the middle of a cluster.
N
C m = (tip)
i=1
N
Distances are normally used to measure the similarity or dissimilarity between two data objects. The distance between the centroids of two clusters, i.e., dis (Ki, Kj) = dis(Ci , Cj).
The Minkowski metric favors the prime scaled feature, which dominates others. The problem can be addressed by proper normalization or other weighting schemes applied in the feature space where d is the dimensionality of the data.
d (i ,j)=q(xi1xj1q+xi2xj2q+)
Where i = (xi1, xi2, , xip) and j = (xj1, xj2, , xjp) are two p dimensional data objects, and q is a positive integer.
If q = 1, d is Manhattan distance
whitening transformation to the data by using the
Mahalanobis distance measure d M(x, y) as d M (x, y) = ( (x – y)A1 (x y)T)1 /2
Where A is a covariance matrix.
Kernel based similarity measure capacities map information from data space to high, perhaps boundless, dimensional feature space. For a finite sample of data X, the kernel function yields a symmetric N*N positive definite matrix K, where the K (i, j) entry corresponds to the dot product between f (x i) and f (x j) as measured by the kernel function. In feature space, the distance measure between any two patterns is given by:
f (xi) – f (x j) 2 =<f (x i) ,f (x j)> + < f (x i) ,f (x j) > – 2<f (x i),
f (x j)> f (x i) – f (x j) 2 =k (i ,i ) k(i ,j ) 2k (i ,j )

Kmeans clustering
Kmeans (MacQueen, 1967) is one of the simplest unsupervised learning algorithms. It outlins a conceptually simple way to partition a data set into a specified number of clusters k. The algorithm aims to iteratively minimize a simple squared error objective function of the form
k
i j
i j
J =  x j c 2 ,
j=1 all i
in class j
Where cj denotes the coordinate vector of the jth cluster and
i
i
{x j} are the points assigned to the jth cluster. Minimizing J equivalently means reaching that configuration at which switching any point to a cluster other than its currently assigned one will only increase the objective function.
Start
Number of Cluster K
Centroid
Centroid
Distance Objects to Centroids
Distance Objects to Centroids
Grouping based on Minimum Distance
Grouping based on Minimum Distance
d(i ,j)=xi1xj1+xi2xj2++xip – xjp
If q = 2, d is Euclidean distance which is defined as the distance between two points as the length of the line segment connecting them. The Euclidean distance has an intuitive appeal as it is commonly used to evaluate the proximity of objects in 2 or 3D space. It works well when a data set has "compact" or "isolated" clusters. The advantage of Euclidean distance is that it is intuitively obvious. The disadvantages are
No object move group?
End
No
Yes
costly calculation due to the square root, and its Nonintegral value.
Linear correlation among features can also distort distance measures. This distortion can be alleviated by applying a
Fig. 1.Algorithm for Kmeans clustering
Shortcomings of Kmeans clustering

The learning calculation requires apriori assignment of the quantity of group focuses.

If there are two highly overlapping data then kmeans will not be able to resolve that there are two clusters.

The learning calculation is not invariant to nondirect changes i.e. with distinctive representation of information we get diverse results (information spoke to in manifestation of Cartesian coordinates and polar directions will give distinctive results).

Euclidean separation measures can unequally weight basic components.

The learning algorithm provides the local optima of the squared error function.

Randomly winnowing of the cluster focus can't lead us to the productive result.

Applicable just when mean is characterized i.e. fizzles for absolute information.

Unable to handle strepitous information and anomalies.


Fuzzy Cmeans Clustering
Fuzzy cmeans (FCM) is a scheme of clustering which allows one section of data to belong to dual or supplementary clusters. This method was developed by Dunn in 1973 and enriched by Bezdek in 1981 and it is habitually used in pattern recognition. Main objective of fuzzy cmeans algorithm is to minimize:
n c
J (U, V) = (uij)mxivj2
i=1 j=1
Where, 'xi vj' is the Euclidean distance between ith data and jth cluster centre.
Start
Randomly select c cluster centres
Randomly select c cluster centres
Initialize fuzzy membership matrix uij
Initialize fuzzy membership matrix uij
Calculate fuzzy centres vij
Calculate fuzzy centres vij
Update membership matrix
Update membership matrix
No
If u(k+1) u(k)<threshold
2) Data point is assigned membership to each cluster center as a result of which data point may belong to more than one cluster center.
Weaknesses of Fuzzy cmeans clustering

Apriori measurement of the number of clusters

Euclidean distance measures can inequitably weight underlying factors.


Kernelized Fuzzy Cmeans clustering
The basic idea of KFCM is to first map the input data into a feature space with higher dimension via a nonlinear transform and then perform FCM in that feature space. The kernel metric Fuzzy CMeans minimizes the following objective function.
k n
J = uijm (xj) (vi)2
i=1 j=1
where, uij denotes the membership of xj in cluster i, (vi) is the center of cluster i in the feature space, and is the mapping from the input space X to the feature space F. Minimization of the function has been proposed only in the case of a Gaussian kernel.
KFCM Algorithm

Select initial class prototype {Vi} c

Update all memberships Uij

Obtain the prototype of clusters in the forms of weighted average. Repeat step 23 till termination. The termination criterion is Vnew Vold
Where . is the Euclidean norm. V is the vector of cluster centres is a small number that can be set by user (here
=0.01).
Benefits of KFCM clustering

We can acquire a directly distinguishable hyperplane in the highdimensional, or even in an endless feature space.

They can distinguish clusters with selfassertive shapes.

Kernelbased clustering calculations, have the capacity of managing noise and outliners.

There is no prerequisite for earlier information to focus the framework topological structure.

The kernel matrix can provide the means to estimate the number of clusters.
Stop
Yes
Downsides of KFCM

A precarious issue related to KFCM clustering is the selection of an "optimal" kernel for the problem at hand and on the setting of the involved parameters.

Fig. 2. Fuzzy Cmeans algorithm
Gains of Fuzzy cmeans clustering

FCM gives best result for overlapped data set and is comparatively better than kmeans algorithm.

The kernel function in use must conform to the learning objectives in order to obtain meaningful results for unlabelled data.


FCM with Tradeoff Weighted Fuzzy Factor and Distance metric (KWFLICM algorithm)


BLOCK DIAGRAM OF THE PROPOSED METHOD
We present an improved fuzzy Cmeans (FCM) algorithm for image segmentation by introducing a tradeoff weighted fuzzy factor and a distance metric. The tradeoff weighted fuzzy factor depends on the space distance of all neighboring pixels and their graylevel difference simultaneously. Trade off weighted fuzzy factor is used for adaptively controlling the local spatial relationship. By using this factor, the new algorithm can accurately estimate the damping extent of neighboring pixels. Modified FCM technique includes similar steps as FCM except for the variation in the cluster updating and membership value updating criterions. The modified criterions are shown below.
n
Input Image
Post processing using Canny Edge detection
Preprocessing
Segmented image
Output Image
Modified FCM
Feature extraction
Ci = (uij)myj ; uij = 1
j=1 n c
(uij)m (dij / dkj)2/(m1)
j=1 k=1
Where dij = yjci y=reduced dataset.
Algorithm of modified Fuzzy C means Clustering with weighted tradeoff fuzzy factor and distance metric (KWFLICM)
Step 1: Set the number of clusters c and the parameter m
c n
Jm(u, v) = (uij)md2(xj,vi)
i=1 j=1
Initialize the fuzzy Cluster centroid vector V=[v1,,vc], randomly and set = 0.01.
Step 2 : Compute uij.
uij = 1
c
(dij / dkj)2/(m1)
k=1
Step 3 : Compute vi.
n
vi = (uij)mxj
j=1 n
(uij)m
Fig. 3. Framework of the proposed system
The framework comprises of the accompanying pieces. The crude information is passed through the framework as numerical information or as waves. Material methods are connected to get the preprocessed information. Further, the information is passed through the clustering stage, which furnishes a proportional payback focuses. Characteristic extraction is then performed to get the characteristic that can out and out represent a given occasion. Next a post transforming is utilized to improve the nature of the last divided image.

Preprocessing
The preprocessing stage is performed to change over all traits of the information into a numeric structure that can be utilized by the clustering methodology. This is greatly valuable for lessening in measurement of the dataset utilizing standardization. In the event that the estimations of a few properties fluctuate in diverse ranges then to lessen the impact of such characteristics, all estimations of the attributes are standardized to lie in some regular reach, in the same way as [0, 1]. Prepreparing improves the visual appearance of images and controls datasets.

Clustering
The clustering is a vital venture, as it is a key antecedent to the peculiarity (feature) extraction. The information for peculiarity extraction is the preprocessed information, where the marks are peeled off. Clustering is a type of unsupervised discovering that serves to discover the intrinsic structure in the information.
j=1
Step 4 : Update uij. Step 5 : Update vi.
Step 6 : Repeat Steps 4 and 5 until the following termination criterion is satisfied:Vnew – Vold<.

Feature extraction
It is the procedure by which certain features of interest inside an image are discovered and spoke to for further handling. It denote the move from pictorial to nonpictorial (alphanumerical, generally quantitative) information representation which can be consequently utilized as a data to various example distinguishment and arrangement procedures,
which will then mark, group, or perceive the semantic substance of the image or its questions.

Postprocessing
Image post transforming improves the nature of the completed image, by filtration and different medicines. Here calculation, for example, locale developing, pixel network or a guideline based calculation is connected to get the last portioned areas. In the proposed system we have chosen Canny edge detection technique for postprocessing.

The Canny edge detector

The Canny edge detector is a standout amongst the most mainstream, compelling, effective and powerful edge detection operators, generally acknowledged as the best all round edge detection method advanced to date. It utilizes a set of generally extensive, situated filters at various image resolutions and consolidates the individual results into a typical edge map. The technique tries to achieve three primary objectives:

To lessen the amount of false edge points.

Achieve noble localization of edges.

Deliver only a solo mark on each edge.
Canny Edge Detection algorithm

The input image is smoothed using a Gaussian low pass filter with a defined estimation of : expansive estimations of will suppress much of the noise at the expense of weakening potentially relevant edges.

The local gradient (intensity and direction) is registered for each one point in the smoothed image.

The edge points at the output of step 2 result in wide ridges. The algorithm thins those ridges, leaving only the pixels at the top of each ridge, in a process known as nonmaximal suppression.

The edge pixels are then thresholded utilizing two limits Tlow and Thigh: edge pixels with qualities more prominent than Thigh are viewed as solid edge pixels; edge pixels with qualities in the middle of Tlow and Thigh are said to be weak pixels. This methodology is known as hysteresis thresholding.

The algorithm performs edge linking, accumulating weak pixels that are 8joined with the solid pixel.



APPLICATIONS

Quantitative or semiquantitative analytic image investigation.

Surgical arranging.

Computer aided surgery.

Prescription Inspection and understanding of images acquired from Xbeams, MRI or CAT examines, investigation of cell images, of chromosome karyotypes.

Agriculture: Satellite/airborne perspectives of area, for instance to decide the amount of area is being utilized for distinctive purposes, or to explore the suitability of diverse locales for diverse products, review of foods grown from the ground recognizing great and new create from old.

Industry: Automatic assessment of things on a generation line, examination of paper specimens.

Law requirement: Fingerprint examination, honing or desmudging of velocity cam images.


CONCLUSION
Traditional FCM algorithm based pixel attributes lead to accuracy degradation. In this paper we have spoken about the execution of the three calculations FCM, K means and the Modified Fuzzy C Means weighted algorithm (KWFLICM). The aim of this paper is to propose a new Edge detection based clustering algorithm for automatic segmentation of medical images with intensity inhomogeneity. A comparative study proposes the feasibility of the proposed algorithm over FCM and K means clustering calculation. Compared with existing clustering methods, the proposed system is able to incorporate the local information more exactly. In addition, the tradeoff weighted fuzzy factor and the distance measure are completely free of the empirically adjusted parameters determination, thereby allowing the automated applications.

ACKNOWLEDGMENT
The authors are enormously obligated to the Staff of the Department of Electronics and Telecommunication Engineering, Pad. Dr. DYPIET for their technical support and all the references used in this paper.

REFERENCES

S. Krinidis and V. Chatzis, A robust fuzzy local information Cmeans clustering algorithm, IEEE Trans. Image Process., vol. 19, no. 5, pp. 13281337, May 2010.

Mr.Tara.Saikumar and Dr. M. Sundarana Reddy, Optimized Kernel Fuzzy CMeans Clustering for BioImages Using Level Set Method , International Journal of Electronics Communication and Computer Engineering, Volume 4, Issue (6), ISSN 2249071X, National Conference on Recent Trends in Computer Science and Technology (NCRTCST)2013.

Sayana Sivanand, Adaptive Local Threshold Algorithm and Kernel Fuzzy CMeans Clustering Method for Image Segmentation, International Journal of Latest Trends in Engineering and Technology (IJLTET), Vol. 2 Issue 3, ISSN: 2278621X, May 2013.

Chiheb Eddine Ben NCir1, Nadia Essoussi1, Patrice Bertrand2, Overlapping clustering based on kernel similarity metric, Larodec, ISG University of Tunis Ceremade1, UniversitÃ© ParisDauphine2.

Xiaojun LOU, Junying LI and Haitao LIU, Improved Fuzzy Cmeans Clustering Algorithm Based on Cluster Density, Journal of Computational Information Systems 8: 2 pp. 727737, 2012.

Mahdi'eh Motamedi and Hasan Naderi, Data clustering using Kernel based algorithm, International Journal of Information Technology, Control and Automation (IJITCA) Vol.4, No.3, July 2014.

Srinivasa K G, Venugopal K R and L M Patnaik, Feature Extraction using Fuzzy C – Means Clustering for Data Mining Systems, International Journal of Computer Science and Network Security, VOL.6 No.3A, March 2006.

Maryam Rastgarpour and Jamshid Shanbehzadeh, A New Kernel Based Fuzzy Level Set Method for Automated Segmentation of Medical Images in the Presence of Intensity Inhomogeneity , Hindawi Publishing Corporation Computational and Mathematical Methods in Medicine Volume 2014, Article ID 978373.

Naouel Baili, Fuzzy Clustering with Multiple Kernels.

P.Sivasangareswari and K.Sathish Kumar, Fuzzy CMeans Clustering With Local Information and Kernel Metric for Image Segmentation , International Journal of Advanced Research in Computer Science &
Technology, Vol. 2 Issue Special 1, ISSN : 2347 – 8446 (Online), ISSN : 2347 – 9817 (Print), Janarch 2014.

Hesam Izakian, Ajith Abraham, Fuzzy Cmeans and fuzzy swarm for fuzzy clustering problem. Expert Systems with Applications 38, 1835 1838, 2011.

James C. Bezdek, Robert Ehrlich and William Full, FCM: The Fuzzy Cmeans Clustering Algorithm, Computers & Geosciences Vol. 10, No. 23, pp. 191203, 1984.

G.J.Abisha Shiji and Ms. Berakhah .F. Stanley, Fuzzy Clustering With Spatial Information For Image Segmentation Using Kernel Metric, International Journal of Engineering Research and Applications (IJERA), ISSN: 22489622 International Conference on Humming Bird, 01st March 2014.

Liu Yang, Distance Metric Learning: A Comprehensive Survey, 2006.

Saritha A K, Ameera P.M, Image segmentation based on kernel fuzzy C means clustering using edge detection method on noisy images, International Journal of Advanced Research in Computer Engineering & Technology (IJARCET) Volume 2, Issue 2, ISSN: 2278 1323, February 2013.

Deepika Singh and Anjana Gosain, Robust new Distance Kernelized Approach to Distributed Clustering, International Journal of Engineering Science & Advanced Technology, Volume3, Issue4, 165 169, ISSN: 22503676, AugSep 2013.

D. Napoleon and K. Ragul, An Efficient MultiKernel Fuzzy CMeans Algorithm to Analyze and Segment the fastidious Tumor region in Medical Images, International Journal of Modern Embedded System (IJMES) Volume No.2, Issue No.4, ISSN: 23209003(Online) August, 2014.

K. M. Bataineh, M. Naji and M. Saqer, A Comparison Study between Various Fuzzy Clustering Algorithms, Jordan Journal of Mechanical and Industrial Engineering, Volume 5, Number 4, ISSN 19956665, Aug. 2011.

J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, New York, 1981.

Medical image analysis, Atam P. Dhawan, Second edition, published by John Wiley & Sons, Inc., Hoboken, New Jersey, ISBN 9780470 622056, 2011.

Digital Image Processing, Bernd JÃ¤hne, 5th revised and extended edition, Springer, ISBN 3540677542, 2002.

Fundamentals of Digital Image ProcessingA Practical Approach with Examples in Matlab by Chris Solomon, Toby Breckon, Wiley Blackwell publishing, ISBN 978 0 470 84472 4, 2011.

Practical Image and Video Processing Using MATLAB, Oge Marques, published by John Wiley & Sons, Inc., Hoboken, New Jersey, ISBN: 9781118093481, 2011.