K-means algorithm

classesImg,clustersCenters,compactness =	kMeansImg (inImg,nbClusters)
classesImg,clustersCenters,compactness =	kMeansImg (inImg,nbClusters,nbAttempts,nbMaxIterPerAttempt,centersShiftTol,outClassImg)
classesImg,clustersCenters,compactness =	kMeansImg (inImg,inOptSingleGreyMaskImg,nbClusters)
classesImg,clustersCenters,compactness =	kMeansImg (inImg,inOptSingleGreyMaskImg,nbClusters,nbAttempts,nbMaxIterPerAttempt,centersShiftTol,outClassImg)

Detailed Description

classifies pixels of an image using k-means algorithm

Note

Please, note that if the output image class is provided by the user, the class image field in the KMeansResults structure returned by the function points to this image. No copy is performed.

Classic K-means algorithm (LLoyd's algorithm) consists in clustering a set of n points of d dimensions in k clusters. Applied here to image processing, for an image of size (x, y, z, c, t) (with x, y and z the sizes respectively along x, y and z-axis, c the number of color channels and t the number of elements in temporal sequence), it will cluster the x*y*z pixels (for a 2d image, with z=1) or voxels (for a 3d image, with z>1) of c*t dimensions in k clusters, with k specified by the user.

The different steps are as follows:

For each attempt (number of attempts is specified by the user through the attribute):

• Compute the initial clusters centers using the K-means ++ algorithm, except if this is the first attempt and if the user has initialized the attribute ; in that last case, the content of the attribute is taken as initial centers,
• As long as at least one cluster center displacement between 2 successive iterations is greater than AND the number of iterations is lower than
  • assignment step: assign each pixel/voxel of the image to its closest cluster,
  • if there are empty clusters after assignment step, for each empty cluster, do:
    • find the most populated cluster,
    • find the most eccentric point in this most populated cluster, and replace the empty cluster by a cluster containing this point only,
  • update step: compute the barycenters of the different new clusters; they become the new clusters centers,
• Keep the set minimizing the compactness (compactness is the sum of squares of distances between pixels/voxels and their closest cluster center).

Input and output attributes of the algorithm are:

• : the input image we want to classify the content,
• : number of different initializations of the clusters centers, that equals to 1 by default (if greater than one and if attribute is intitialized by the user, then the first attempt is initialized with clusters centers specified by the user, and for the next attempts clusters centers are automatically initialized using k-means ++ algorithm). If greater than 1, the solution minimizing the compactness is kept,
• : Number of maximum iterations for each attempt (if not initialized or set to 0 by the user, there is no limit on the number of maximum iterations; in other words, the loop of "assignment step"/"update step" sequences won't stop as long as centers displacements are greater than the threshold specified by the user),
• : maximal allowed clusters centers displacement between 2 iterations, under which we consider our current attempt converged (automatically set to 0.0001 if not initialized by user),
• : collection of initial clusters centers for the first attempt. If this attribute is not initialized, clusters centers for the first attempt will be automatically initialized by the algorithm using the K-means ++ method. This attribute is also updated by the algorithm, with the properties of the resulting clusters,
• : Number of clusters expected by the user; this parameter is ignored if is initialized; at least one of these 2 parameters has to be initialized,
• : compactness of the retained solution,
• : optional, will be used by the algorithm for its internal computation. It will be used only if the number of attempts is greater than 1. If the number of attempts is greater than 1 and if this image is not provided by the user, it will be automatically be allocated by the algorithm itself,
• : Image of identifiers of clusters for each pixel/voxel (identifiers in range [0..nbClusters-1]),
• : optional; image where pixels/voxels values are replaced with their associated cluster center.

Below is an example of the application of k-means algorithm on a RGB UInt8 image, with the following parameters: ( =4, =1, =100, =0.01):

• on the left, the original image,
• on the right, the posterized image computed using the class image and the clusters centers resultating from the k-means application:

The algorithm allows to classify only a subset of pixels/voxels by using a mask image as additional input. In this case, only the pixels/voxels with a mask value of True are classified and taken into account for the clusters calculation.

Here is an example of masked k-means based classification, using the same parameters as for the previous figure. Black pixels correspond to a value of False in the mask image:

References

[1] Stuart P. Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 28(2):129–136, 1982.

Example of Python code :

Example imports

import PyIPSDK
import PyIPSDK.IPSDKIPLClassification as classif

Code Example

    # opening of input image
    inImg = PyIPSDK.loadTiffImageFile(inputImgPath)
    
    nbClusters = 4
    
    res = classif.kMeansImg(inImg, nbClusters)
    
    outClassImg = res[0]
    outClustersCenters = res[1]
    outCompactness = res[2]
    
    # Access to the first cluster center
    firstClusterCenter = outClustersCenters.coll[0].elements

Example of C++ code :

Example informations

Header file

#include <IPSDKIPL/IPSDKIPLClassification/Processor/KMeansImg/KMeansImg.h>

Code Example

    // load input image from file
    ImagePtr pInImg = loadTiffImageFile(inputImgPath);
    const ipUInt32 nbExpectedClusters = 4;
    const ipUInt32 nbAttempts = 1;
    const ipUInt32 nbMaxIterPerAttempt = 100;
    const ipReal64 clustersCentersShiftTol = 0.1;

    // apply k-means algorithm on input image
    KMeansResults res = kMeansImg(pInImg, nbExpectedClusters);
    
    // retrieve resulting class image
    const ImagePtr pOutClassImg = res._pClassesImg;

    // retrieve resulting clusters properties
    const ClustersCentersPtr pOutClustersCenters = res._pClustersCenters;

    // Access to the first generated cluster center elements
    ClusterCenterPtr clusterCenter = pOutClustersCenters->getNodeColl<ClustersCenters::Coll>()[0];
    const std::vector<ipReal64>& vRandomClusterElements = clusterCenter->getLeafColl<ClusterCenter::Elements>();