Genetic Algorithm for Centroid Selection on Kmeans Image Segmentation

The K-means clustering algorithm has wide applications for data and document-mining, digital image processing and different engineering fields. In addition to that, the clustering algorithm is composed of simple algorithm steps and has fast convergence, however it is suffered by initial centroid selection while clustering an image.

The initial centroid selection determines the clustering algorithm consistent results and performance. The good initial cluster-centroids lead to good clustering results, otherwise the bad initial cluster-centroids selection lead to bad results.

In order to achieve K-means clustering's consistent result and performance, we propose initial cluster centroids selection by Genetic optimization algorithm. The GA (genetics algorithm) has efficient search operations (selection, crossover and mutation) for determination of global minima on selection of cluster centroid problems

GA - population

A set of solutions or chromosomes are called population. Each chromosome has N number of genes (variables) that represents cluster centroids and they are randomly initialized between 0 (lower bound) and 1 (upper-bound value).

for example

chromosome 1
gene-1	gene-2	gene-3	gene-4
0.125	0.364	0.563	0.854

GA - objective function

The GA determines the fitness value of a chromosome by executing an objective function. It has minimizing sum of intra-cluster difference as the objective function, in order to obtain best initial cluster centroid values.

The following standard images are used for testing GA- centroid initialized K-means algorithms

Algorithm Steps for Genetics Algorithm for Centroid Selection

       Inputs : sample, sample-pixel (image,p) 
                no-of-variable, nc   (number of cluster)
                population-size,np
                lower-bound,lb
                upper-bound, ub 
                crossover-probability, cp
     
     output : initial cluster centroid, igcs       

           pop=  generate-population(np,nc,lb,ub)                  
           fs =  objective-function(pop)
        While ( min(fs) < Tolerance )

              sp=Roulette-selection(fs)
              arithmetic-crossover(pop,sp,cp)
              adaptfeasible-mutation(pop)
              fs=objective-function(pop)
        End

           index=min(fs)
           igcs=pop(index) 
        
  

Matlab programming code - Kmeans Segmentation Cluster-Centroid Selection based on Genetics Algorithm

 
function gakmeans

clc;close all; clear all;

% sds  - sampled dataset  
global sds;

[im,map]=imread('imagesboat.tiff');

im=im2double(im);
[row,col]=size(im);

%number of clusters
nc=4;

%select 10% samples randomly for GA cluster centroid selection
p=10;
L= row*col;
rns=(p/100)*L; 
rp=randperm(L);
sds=im(rp(1:rns));

%set GA operators options such as selection crossover,mutation 
options=gaoptimset('PopulationSize',20,
                   'PopulationType','doubleVector', ... 
                   'CrossoverFraction',0.7,... 
                   'Generations',100,...
                   'EliteCount',2, ...
                   'SelectionFcn', @selectionroulette,...
                   'CrossoverFcn',@crossoverarithmetic,...
                   'MutationFcn',@mutationadaptfeasible,...
                   'PlotFcns',@gaplotbestf) ;

               
%lower bound limit               
lb=zeros(nc,1);
% upper bound limit
ub=ones(nc,1);

%GA optimization initialized with objective function, number-of-clusters and options for GA operators               
[gics,gfv,exf] =ga(@objfunc,nc,[],[],[],[],lb,ub,[],options);

[idx,cs,egr]=kmeanseg(im,gics);
gsim=coloring(cs,idx);
gsim=reshape(gsim,row,col,3);

figure;imshow(gsim);
title('GA-Kmeans');



%ga objective energy minimization function
function egr=objfunc(cs)

  global sds
  nc = size(cs,2);
  [row,col]=size(sds);
  D=zeros(row,col,nc);
  
  for c=1: nc 
    D(:,:,c)=   (sds - cs(c)).^2 ;     
  end         
 [mv,~]=min(D,[],3);  
 egr=sum(mv(:));
 
function gsim=coloring(cs,idx)
nc = length(cs);
[~,ind]=sort(cs);
gidx=zeros(size(idx));

for s=1: nc
 gidx(idx==ind(s)) =s;   
end
colors = hsv(nc);
gsim= colors(gidx,:);



function [idx,cs,egr]=kmeanseg(im,cs)
%number of Iteration
T= 50; t=0; 
nc=length(cs);
[row,col]=size(im);
D=zeros(row,col,nc);

pcs=cs;
egr =[];
eps=1.e-8; cmx=1;

while ( t<T  && cmx>eps )   
                 
    for c=1: nc 
      D(:,:,c)=   (im - cs(c)).^2 ;     
    end            
    [mv,idx]=min(D,[],3);
    
    for c=1: nc 
      I = (idx==c);  
      cs(c) = mean( mean(im(I)) );    
    end    
     cmx = max( abs(cs-pcs) );
     pcs = cs;         
     t= t+1;
     egr= [egr; sum(mv(:)) ];                         
end        

GA-Kmeans Image segmentation results