K-means clustering                       

• Selects an initial partition with K clusters.
• Generates a new partition by examining each component in the population (Macroblock).
• Assigns each Macroblock to one of the clusters depending on a metric.
• Computes new cluster centers as the centroids of the cluster.
• Repeat steps  2,3 and 4 until the centroids are fixed.