Image Segmentation - K-means Clustering

Introduction to K-means clustering-algorithm

The K-means clustering algorithm comprised of three steps, they distance, minimum-distance cluster assignment and cluster centroid update. These three steps are repeatedly executed until convergence meet or number of iteration end.

• The K-means algorithm splits the given dataset (image) into K number of clusters or groups
• It assigns a member(pixel) into a cluster (group) based on minimum distance between the pixel and all cluster centroids
• The algorithm is not complex and iterative procedure steps
• The high speed convergence but stayed on local minimum at most of times

Unsupervised Clustering

The K-means algorithm has no training phase. The dataset (image pixels) to be clustered is not attached with class or target variables.

Assumed K number of Clusters

The K-means algorithm should starts with K number of clusters, however actual number of cluster exist in an image is unknown.

Sensitivity to Initial Cluster Centroid

Image segmentation results of K-means algorithm depends on initial cluster centroid values. If There is changes in the initial cluster's centroid values while executing the algorithm, The members(pixels) belonging to the clusters and image segmentation results will be changed.

Objective of K-means Clustering

Minimize sum of squared distance between cluster members and cluster centroids

K-means image segmentation test image 1 - cameraman.tif

Algorithm Steps for Image segmentation using K-means Clustering

• I - Input Image, i=1 to M, j=1 to N
• I_ij - Intensity of i^throw and j^thcolumn pixel on the input image
• CS - Cluster centres k=1 to K
• C_k - k^th cluster centres
• D - a matrix distance between input image I, and cluster centroids
• D_ijk = distance between i^throw and j^thcolumn pixels and k^th cluster centroid
• ML - members label
• ML_ij - label of i^throw and j^thcolumn pixel of Input image
• T - maximum number of iteration

     set T=50, eps=1e-5; set nc=4;
     CS =random-initialize;

     while ( t < T  &&  cmx > eps )

       D = find-distance(I,CS) 
       ML = cluster-labelling(D)
       CS = update-cluster-centroid(ML)
       cmx = max( abs( pCS - CS) )
       
       t= t+1
       pCS = CS   
   
    End while  

  

• nc - number of clusters
• pCS - previous iteration cluster centroids

K-means Clustering - Matlab programming code

 
%grayscale image segmentation using k-means algorithm
function kmeansegmentation
 
clc;close all; clear all;
[im,map]=imread('imagescameraman.tif');
im=im2double(im);
[row,col]=size(im);

%number of clusters
nc =4;
%Initial random cluster centroids
cs =rand(nc,1);
pcs=cs;

%number of Iteration
T= 50; t=0; 

D=zeros(row,col,nc);

tsmld =[];
eps=1.e-5; cmx=1;

while ( t<T  && cmx>eps )   
                 
    %Distance between centroids and image's pixel 
    for c=1: nc 
      D(:,:,c)=   (im - cs(c)).^2 ;     
    end
        
    
    %assign members (image pixels) to minimum distance clusters  
    [mv,ML]=min(D,[],3);
    
     %update cluster centroid
    for c=1: nc 
      I = (ML==c);  
      cs(c) = mean( mean(im(I)) );    
    end
    
    %find maximum absolute  difference between current 
     % and previous  iteration cluster centroids     
     cmx = max( abs(cs-pcs) );
     pcs = cs;
         
     t= t+1;
    
    %sum difference between centroid and their members 
    % and store it for plotting energy minimization functions
    tsmld= [tsmld; sum(mv(:)) ];
      
                   
end

 
%assign a colour to each cluster
colors = hsv(nc);
sim= colors(ML,:);
sim=reshape(sim,row,col,3);
 
figure,subplot(1,2,1), imshow(im,map);
title('Input Image: cameraman');
subplot(1,2,2);imshow(sim,map);
title('segmented Image: cameraman');


figure;plot(tsmld,'*-b');
xlabel('Iteration');ylabel('Energy');
title('K-means energy minimization - cameraman.tif');

K-means image segmentation test image 2 : lena.tif