Extracting Dominant Image Colors in Flutter with the K-means Algorithm

Why have I extracted colors from images when there are already libs for that, and why have I used the K-means++ algorithm for that?

7 min readOct 6, 2023

For my small Flutter project, an example of implementing clean architecture, I needed the extracted colors from the images, that I would use as background behind the images. I believe there are libraries on the pub.dev that are doing just that, but, as I had a lot of time at that moment, at 23:00 in the evening, not going to sleep as usual 🙄, I decided to do it by myself.

Why have I used the K-means algorithm?

First, let me explain what is K-means algorithm and in detail why it was a good option for my case.

When the goal is to find the most dominant colors in a photo (or similar image quantization tasks), clustering algorithms are the best solution. K-means is the most widely used centroid-based clustering algorithm. That is the reason why I decided to choose it for a task like extracting dominant colors from the photos. Other clustering algorithms that may be suitable for tasks, like this one, are:

1. K-means++: This is an improved version of the K-means algorithm. Its main advantage is a smarter initialization of the centroids, which tends to lead to faster convergence and better final clustering results.

2. Median Cut Algorithm: Specifically designed for color quantization, this algorithm divides the color space based on where it will reduce color variance the most. It’s like making cuts in a 3D RGB space to capture the most significant color ranges.

3. DBSCAN (Density-Based Spatial Clustering of Applications with Noise): Unlike K-means, DBSCAN doesn’t require you to specify the number of clusters beforehand. It works based on the density of points. For color clustering, it might work well when dominant colors are tightly packed in the color space.

4. Hierarchical Clustering: This algorithm builds a tree of clusters. You can then “cut” the tree at a particular level to get the desired number of clusters. This might be a good choice if you want a hierarchical understanding of dominant colors.

5. Gaussian Mixture Models (GMM): Assumes that data is generated from several Gaussian distributions. Each cluster corresponds to one Gaussian distribution. The Expectation-Maximization (EM) algorithm is typically used to identify the parameters of the Gaussian distributions. It’s a soft clustering method, meaning each data point (color) gets a probability of belonging to each cluster.

6. Agglomerative Clustering: It’s a type of hierarchical clustering where each data point starts as its own cluster, and pairs of clusters are merged as one moves up the hierarchy.

7. Mini-Batch K-means: A variant of the K-means algorithm that uses mini-batches of data points to update the centroids, which can be faster than the regular K-means for large datasets.

For the specific task of finding the most dominant colors in a photo, the two most applicable algorithms are definitely:

- K-means and K-means++, which I used, because they’re straightforward, efficient, and often bring good results.

The Median Cut Algorithm can also be very effective, given its design specifically for color quantization — My next ToDo task.

How exactly does the K-means algorithm work?

Based on my case, I will explain it in the simplest way using the markers analogy.

If you have a big box of differently colored markers, and you want to group them based on their colors, the K-means algorithm would work like this.

We pick randomly a few markers from the box of differently colored markers. Let’s say we choose 5 markers. These are our starting points (or “centroids” in fancy terms).
Now, we take each marker from the box and place it next to the starting marker it looks most like in color.
So if we have a blue, a red, and a green marker as our starting points, all the blueish markers go near the blue one, all the reddish ones near the red, and so on.
Once we’ve grouped all the markers, we look at each group and find the marker that’s in the middle of each group. These middle markers are our new starting points. (In the real K-means algorithm, this would be the average color of all the markers in the group.) Now we repeat the process.
With our new starting points, we regroup the markers by the marker color they’re closest to. Then find the middle marker again. We keep doing this until our groups don’t change much.

Once our marker groups don’t change anymore, we’re done. We’ve now successfully grouped our markers by color. And that’s the K-means algorithm. In real-world applications, instead of markers, we’re often grouping data points, but the idea is the same.

How fast is the K-mean?

The speed (or computational complexity) of the K-means algorithm depends on, first, the number of data points (n) — The more data we have, the longer it’ll take. It depends on the number of clusters because more clusters mean more centroids to compare with, which can slow down the process (which I faced too). If each data point has many attributes (like in high-dimensional data), each distance computation can take longer.

Given these factors, the general time complexity of the K-means algorithm is O(n * k * i * d).

In practical terms, it is fast for small datasets — K-means can be very fast with small datasets or when k, i, and d are modest. For large datasets, or if the number of desired clusters is high, K-means can become slower. Especially if it takes many iterations to converge.

If the initial centroids (starting points) are chosen poorly, the algorithm can require more iterations to converge, or it might even get stuck in a suboptimal solution.

There are various optimizations and variations of the K-means algorithm, such as K-means++, that help in improving the initialization of centroids or the speed of convergence.

So, for my case, K-means++ was a good solution and I decided to implement it for this particular case. The K-means++ initialization is done through these steps:

The first centroid is chosen uniformly at random from the data points that are being clustered.
The next centroid is selected from the remaining data points with probability proportional to the square of the distance from the point to the nearest existing centroid.
Repeat the previous step until centroids are chosen.

So, first, we have a Uint8List representation of the image ( the bytes in the previous function). This list will be processed to extract pixel colors which can then be clustered using K-means++ to obtain the dominant colors. Dividing code into important parts, which you can see fully here, would be:

class DominantColor {
  final Uint8List bytes;
  final int k = 2; 
// The bytes are the raw bytes of the image we want to process.
// k is the number of clusters (colors) we want. It's set to 2 here.
  DominantColor(this.bytes, this.k);

Distance Function:

This function calculates the Euclidean distance between two colors. It measures “how far apart” the two colors are in the RGB color space.

double distance(Color a, Color b) {
  return sqrt(pow(a.red - b.red, 2) + pow(a.green - b.green, 2) + pow(a.blue - b.blue, 2));
}

Centroids Initialization:

This method initializes the centroids using the K-means++ method, which is a more efficient way than picking them randomly.

List<Color> initializeCentroids(List<Color> colors) {
 final random = Random();
    List<Color> centroids = [];
    centroids.add(colors[random.nextInt(colors.length)]);
...
}

Extract Dominant Colors — the heart of the algorithm:

This method organizes the colors into clusters using the K-means++ method. In the end, the centroids of these clusters are the dominant colors.

List<Color> extractDominantColors() {
//half of image is enough to pick all dominat colors
 List<Color> colors = _getPixelsColorsFromHalfImage(); 
    List<Color> centroids = initializeCentroids(colors);
    List<Color> oldCentroids = [];

    while (_isConverging(centroids, oldCentroids)) {
      oldCentroids = List.from(centroids);
      List<List<Color>> clusters =
          List.generate(dominantColorsCount, (index) => []);

      for (var color in colors) {
        int closestIndex = _findClosestCentroid(color, centroids);
        clusters[closestIndex].add(color);
      }

      for (int i = 0; i < dominantColorsCount; i++) {
        centroids[i] = _averageColor(clusters[i]);
      }
    }
    return centroids;
}

Find the closest Centroid:

 int _findClosestCentroid(Color color, List<Color> centroids) {
    int minIndex = 0;
    double minDistance = distance(color, centroids[0]);
    for (int i = 1; i < centroids.length; i++) {
      double dist = distance(color, centroids[i]);
      if (dist < minDistance) {
        minDistance = dist;
        minIndex = i;
      }
    }
    return minIndex;
  }

I optimized the algorithm by taking only half of the image and setting the sampling to get every 5th pixel. This approach could be further optimized, of course. After extensive testing with various image sizes, I found that this approach worked very well. Taking only half of the image was enough to extract all of the dominant colors. In the example below, you can see that the image, mostly, has all the most repetitive colors in the one half of the image.