Click here to Skip to main content
11,494,407 members (61,977 online)
Click here to Skip to main content

Computer Vision Applications with C# - Fuzzy C-means Clustering

, 9 Mar 2011 GPL3 62.3K 6.7K 69
Rate this:
Please Sign up or sign in to vote.
This code performs a fuzzy C-means clustering and segmentation of color images, and can be used for feature extraction.

printscreen.png

Introduction

Image segmentation, the partitioning of an image into homogeneous regions based on a set of characteristics, is a key element in image analysis and computer vision. Clustering is one of the methods available for this purpose. Clustering is a process which can be used for classifying pixels based on similarity according to the pixel's color or gray-level intensity.

The K-means algorithm has been used for a fast and crisp "hard" segmentation. The Fuzzy Set theory has improved this process by allowing the concept of partial membership, in which an image pixel can belong to multiple clusters. This "soft" clustering allows for a more precise computation of the cluster membership, and has been used successfully for image clustering and for the unsupervised segmentation of medical, geological, and satellite images.

Algorithm

The fuzzy C-means (FCM) algorithm follows the same principles as the K-means algorithm in that it compares the RGB value of every pixel with the value of the cluster center. The main difference is that instead of making a hard decision about which cluster the pixel should belong to, it assigns a value between 0 and 1 describing "how much this pixel belongs to that cluster" for each cluster. Fuzzy rule states that the sum of the membership value of a pixel to all clusters must be 1. The higher the membership value, the more likely that pixel is to belong to that cluster. The FCM clustering is obtained by minimizing an objective function shown in equation (1):

1.png (1)

Where:

  • J is the objective function
  • n is the number of pixels in the image E
  • c is the number of clusters
  • µ is the fuzzy membership value from table
  • m is a fuzziness factor (a value > 1)
  • pi is the ith pixel in E
  • vk is the centroid of the kth cluster
  • |pi – vk| is the Euclidean distance between pi and vk defined by equation (2):

2.png (2)

The calculation of the centroid of the kth cluster is achieved using equation (3):

3.png (3)

The fuzzy membership table is calculated using the original equation (4):

4.png (4)

This algorithm has been extended for clustering of color images in the RGB color space. Hence, the computation given in equation (2) to compute the Euclidean distance between the values pi and vk is modified to incorporate RGB colors, and is shown in equation (5):

1.png (5)

Picture1.png

Pseudo-Code

As mentioned earlier, this is an iterative process. The pseudo-code is as follows:

  • Step 1: Set the number of clusters, the fuzzy parameter (a constant > 1), and the stopping condition
  • Step 2: Initialize the fuzzy partition matrix
  • Step 3: Set the loop counter k = 0
  • Step 4: Calculate the cluster centroids, calculate the objective value J
  • Step 5: For each pixel, for each cluster, compute the membership values in the matrix
  • Step 6: If the value of J between consecutive iterations is less than the stopping condition, then stop; otherwise, set k=k+1 and go to step 4
  • Step 7: Defuzzification and segmentation

Using the Code

The GUI is pretty straightforward, but the calculations can be very intensive. For that reason, the processing is done in a worker thread, which complicates the interaction with the GUI.

First, use the "File" menu to load an image. Beware, large images will tale a long time!

The options available to be changed from the GUI are the number of clusters, the maximum number of iterations (so that the program doesn't just keep running forever), and the precision. The algorithm will stop before the maximum number of iterations if the precision is achieved.

options.png

Clicking the "Fuzzy C-means Clustering" button will start the computation. The program will start by creating a ClusterPoint object for every pixel in the image:

List<ClusterPoint> points = new List<ClusterPoint>();
for (int row = 0; row < originalImage.Width; ++row)
{
    for (int col = 0; col < originalImage.Height; ++col)
    {
        Color c2 = originalImage.GetPixel(row, col);
        points.Add(new ClusterPoint(row, col, c2));
    }
}

Then, create the requested number of ClusterCentroid cluster objects:

List<ClusterCentroid> centroids = new List<ClusterCentroid>();

//Create random points to use a the cluster centroids
Random random = new Random();
for (int i = 0; i < numClusters; i++)
{
    int randomNumber1 = random.Next(sourceImage.Width);
    int randomNumber2 = random.Next(sourceImage.Height);
    centroids.Add(new ClusterCentroid(randomNumber1, randomNumber2, 
                  filteredImage.GetPixel(randomNumber1, randomNumber2))); 
}

The cluster centers (or centroids) are selected randomly for the first pass, and will be adjusted by the algorithm.

Finally, create the FCM object and start the iterations:

FCM alg = new FCM(points, centroids, 2, filteredImage, (int)numericUpDown2.Value);
k++;
alg.J = alg.CalculateObjectiveFunction();
alg.CalculateClusterCentroids();
alg.Step();
double Jnew = alg.CalculateObjectiveFunction();
Console.WriteLine("Run method i={0} accuracy = {1} delta={2}", 
                  k, alg.J, Math.Abs(alg.J - Jnew));
backgroundWorker.ReportProgress((100 * k) / maxIterations, "Iteration " + k);
if (Math.Abs(alg.J - Jnew) < accuracy) break;

Progress is displayed on the status bar:

progress.png

Once the iterations are done, the algorithm will perform a defuzzification process to assign the pixel to the cluster for which it has the highest membership value. For each cluster, the program will then save a segmented image containing the pixels from the original image that are contained in that cluster.

As an example, the clustering of the following test image with 2 clusters:

printscreen.png

will result in the following clustered image:

printscreen.png

By using the cluster information and the pixels from the original image, the following regions can be extracted:

printscreen.png printscreen.png

Because this algorithm is very computationally intensive, it has a tendency to "lock" the GUI and not refresh the status and the working image. For that reason, I had to use a worker thread.

Points of Interest

This is my first post, and my first C# program, so I am sure that it leaves a lot of room for improvement. But overall, I hope that you will find this project fun and interesting!

References

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

Share

About the Author

Christophe Gauge

United States United States
Graduate student
Department of Information and Computer Sciences
University of Hawai'i at Manoa

Comments and Discussions

 
Questionhow with cluster point is image block Pin
gabachu23-Jan-15 5:46
membergabachu23-Jan-15 5:46 
QuestionEps? Pin
imparente24-Apr-13 2:09
memberimparente24-Apr-13 2:09 
Questionfuzzy c means Pin
arc_15720-Mar-13 20:28
memberarc_15720-Mar-13 20:28 
Question5 all the way Pin
khairul78612-Jan-12 5:40
memberkhairul78612-Jan-12 5:40 
GeneralMy vote of 5 Pin
khairul78612-Jan-12 5:39
memberkhairul78612-Jan-12 5:39 
GeneralMy vote of 4 Pin
gorgias9915-Mar-11 1:54
membergorgias9915-Mar-11 1:54 
QuestionCan I suggest one of my articles? Pin
Paulo Zemek9-Mar-11 9:40
memberPaulo Zemek9-Mar-11 9:40 
I think your algorithm can be improved a lot if you use a faster way to get pixels color values.
I had written two articles about ManagedBitmaps and, if you want, I can send you the last version of my work.
AnswerRe: Can I suggest one of my articles? Pin
Member 177385512-Apr-11 13:39
memberMember 177385512-Apr-11 13:39 
GeneralMy vote of 1 Pin
ghh12512-Dec-10 1:26
memberghh12512-Dec-10 1:26 
GeneralRe: My vote of 1 Pin
Nicolas Dorier9-Mar-11 22:51
memberNicolas Dorier9-Mar-11 22:51 
GeneralRe: My vote of 1 Pin
sanosay4-Apr-12 13:43
membersanosay4-Apr-12 13:43 
AnswerRe: My vote of 1 Pin
Claude He1-Oct-14 6:39
memberClaude He1-Oct-14 6:39 
GeneralMaybe a small problem Pin
likuan26-Oct-10 22:51
memberlikuan26-Oct-10 22:51 
AnswerRe: Maybe a small problem Pin
Christophe Gauge2-Feb-11 9:40
memberChristophe Gauge2-Feb-11 9:40 
GeneralMy vote of 5 Pin
Joel Ivory Johnson19-Jul-10 5:38
memberJoel Ivory Johnson19-Jul-10 5:38 
GeneralSo cool! Pin
hackcat19-Jul-10 4:23
memberhackcat19-Jul-10 4:23 
GeneralI like this a lot Pin
Yves12-Jul-10 14:57
memberYves12-Jul-10 14:57 
GeneralGreat start Pin
Alphons van der Heijden10-Jul-10 13:54
memberAlphons van der Heijden10-Jul-10 13:54 
GeneralFew tips for you..... Pin
Md. Marufuzzaman4-Jul-10 20:14
mvpMd. Marufuzzaman4-Jul-10 20:14 
GeneralRe: Few tips for you..... Pin
gaugec5-Jul-10 6:58
membergaugec5-Jul-10 6:58 
GeneralRe: Few tips for you..... Pin
Md. Marufuzzaman5-Jul-10 7:31
mvpMd. Marufuzzaman5-Jul-10 7:31 
GeneralMy vote of 1 Pin
gaurav_verma_mca4-Jul-10 19:25
membergaurav_verma_mca4-Jul-10 19:25 
GeneralRe: My vote of 1 Pin
Laserson12-Mar-11 10:45
memberLaserson12-Mar-11 10:45 
GeneralNeeds improvement... Pin
Sandeep Mewara4-Jul-10 19:18
mentorSandeep Mewara4-Jul-10 19:18 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.150520.1 | Last Updated 9 Mar 2011
Article Copyright 2010 by Christophe Gauge
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid