k-means image segmentation - centroid initialisation and distance metric

Hi, I am using this k-means image segmentation submission found at: http://uk.mathworks.com/matlabcentral/fileexchange/8379-kmeans-image-segmentation

full code:

function [mu,mask]=kmeans(ima,k)
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %
  %   kmeans image segmentation
  %
  %   Input:
  %          ima: grey color image
  %          k: Number of classes
  %   Output:
  %          mu: vector of class means 
  %          mask: clasification image mask
  %
  %   Author: Jose Vicente Manjon Herrera
  %    Email: [e-mail]
  %     Date: 27-08-2005
  %
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    % check image
    ima=double(ima);
    copy=ima;         % make a copy
    ima=ima(:);       % vectorize ima
    mi=min(ima);      % deal with negative 
    ima=ima-mi+1;     % and zero values

    s=length(ima);

    % create image histogram

    m=max(ima)+1;
    h=zeros(1,m);
    hc=zeros(1,m);

    for i=1:s
      if(ima(i)>0) h(ima(i))=h(ima(i))+1;end;
    end
    ind=find(h);
    hl=length(ind);

    % initiate centroids

    mu=(1:k)*m/(k+1);

    % start process

    while(true)

      oldmu=mu;
      % current classification  

      for i=1:hl
          c=abs(ind(i)-mu);
          cc=find(c==min(c));
          hc(ind(i))=cc(1);
      end

      %recalculation of means  

      for i=1:k, 
          a=find(hc==i);
          mu(i)=sum(a.*h(a))/sum(h(a));
      end

      if(mu==oldmu) break;end;

    end

    % calculate mask
    s=size(copy);
    mask=zeros(s);
    for i=1:s(1),
    for j=1:s(2),
      c=abs(copy(i,j)-mu);
      a=find(c==min(c));  
      mask(i,j)=a(1);
    end
    end

    mu=mu+mi-1;   % recover real range

It works well, but I am trying to discern which method it uses for centroid initialisation here:

    % initiate centroids
      mu=(1:k)*m/(k+1);

It doesn't look like any formula I have seen in literature, am I not seeing something obvious?

Also, which type of distance metric is being applied here? It looks to me like Manhattan (city block)?

% current classification  

      for i=1:hl
          c=abs(ind(i)-mu);
          cc=find(c==min(c));
          hc(ind(i))=cc(1);
      end

Thanks for your help!

Answer 1

[Image Analyst]

For kmeans you have to initialize the cluster centroids. He's just initializing them by spacing them uniformly along the gray level axis.

I'm not 100% sure what he's doing for the "current classification" section and the mask creation section. Looks like he's finding and saving the upper left pixel or something.

He's using city block distance, which, for a 1-D situation like this is (because it's clustering the gray levels), is the same as the Euclidean distance.

By the way, if you have the Statistics and Machine Learning Toolbox, you can use the kmeans() function instead of this guy's code.

[ziggy]

Thanks a lot for your help! I do have the toolboxes, maybe I should give the original kmeans() a go again, you're right. I couldn't get it to work on my images a few years back, so I had ended up using this one.