Recently I wanted to build a feature that extracts the dominant color from a blog post's header image, which reminded me of a post I wrote ages ago about using the median-cut algorithm to extract colors from images.

Median-Cut Algorithm vs. K-Means Clustering

The median-cut algorithm is based on the color histogram; it recursively divides the color space into small cubes, and the color value of each cube is represented by the median color inside that cube. When an image's color distribution is uneven, this algorithm tends to produce obvious color deviations, causing the extracted colors to be inaccurate—for example, if an image has a lot of red and a little green, the extracted colors will lean toward red. Also, with the median-cut algorithm, the same image will yield the same colors every time.

In contrast, K-Means clustering is better at handling uneven color distributions, and because it uses randomly initialized cluster centers, the extracted colors can be different each time.

Of course, K-Means converges more slowly, so very large images may take a while; but for typical blog images the cost is negligible. Like the median-cut algorithm, K-Means also draws the image onto a canvas, so cross-origin issues can still taint the canvas.

Result

Here’s how it looks after applying it to the site. If your browser supports web theme colors, you’ll see the status-bar color change to a random color from the header image.

Below is a live demo that uses K-Means clustering to extract five colors from an image:

K-Means Clustering Algorithm JavaScript Code

The main JavaScript code is as follows:

CodeBlock Loading...

Mini-batch K-Means Algorithm

Mini-batch K-Means is an optimized version of K-Means. Because it randomly selects only a subset of the data for each iteration, it reduces computational cost and processes large datasets faster. However, since only a random subset is used, the results are less accurate than standard K-Means.

Below is the result optimized with mini-batch K-Means:

CodeBlock Loading...

Median-Cut Algorithm vs. K-Means Clustering

In contrast, K-Means clustering is better at handling uneven color distributions, and because it uses randomly initialized cluster centers, the extracted colors can be different each time.

Result

Here’s how it looks after applying it to the site. If your browser supports web theme colors, you’ll see the status-bar color change to a random color from the header image.

Below is a live demo that uses K-Means clustering to extract five colors from an image:

K-Means Clustering Algorithm JavaScript Code

The main JavaScript code is as follows:

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
fetch('{image url}')
    .then(response => response.blob())
    .then(blob => createImageBitmap(blob))
    .then(imageBitmap => {
        canvas.width = imageBitmap.width;
        canvas.height = imageBitmap.height;
        ctx.drawImage(imageBitmap, 0, 0);
        const imageData = ctx.getImageData(0, 0, canvas.width, canvas.height);
        const data = imageData.data;
        const pixels = Array.from({ length: data.length / 4 }, (_, i) => [data[i * 4], data[i * 4 + 1], data[i * 4 + 2]]);
        const kMeans = new KMeans();
        const clusters = kMeans.cluster(pixels, 5);
        const colors = clusters.centroids;
        const colorsDiv = document.getElementById('colors');
        colors.forEach((color, items) => {
            const div = document.createElement('div');
            console.log(`Color ${items + 1}: rgb(${color[0]}, ${color[1]}, ${color[2]})`);
            div.style.backgroundColor = `rgb(${color[0]}, ${color[1]}, ${color[2]})`;
            colorsDiv.appendChild(div);
        });
    });

class KMeans {
    cluster(data, k) {
        const centroids = this._initCentroids(data, k);
        let oldClusters = [];
        let newClusters = [];
        const distancesMap = new Map();
        while (!this._clustersEqual(oldClusters, newClusters)) {
            oldClusters = newClusters;
            newClusters = Array.from({ length: k }, () => []);
            data.forEach(point => {
                let distances = distancesMap.get(point);
                if (!distances) {
                    distances = centroids.map(centroid => this._euclideanDistance(point, centroid));
                    distancesMap.set(point, distances);
                }
                const nearestCentroidIndex = distances.indexOf(Math.min(...distances));
                newClusters[nearestCentroidIndex].push(point);
            });
            centroids.forEach((centroid, i) => {
                const cluster = newClusters[i];
                if (cluster.length > 0) {
                    const [sumR, sumG, sumB] = cluster.reduce(([accR, accG, accB], [r, g, b]) => [accR + r, accG + g, accB + b], [0, 0, 0]);
                    centroids[i] = [sumR / cluster.length, sumG / cluster.length, sumB / cluster.length];
                }
            });
        }
        return { centroids, clusters: newClusters };
    }

    _initCentroids(data, k) {
        const shuffledData = this._shuffle(data);
        return shuffledData.slice(0, k);
    }

    _euclideanDistance(p1, p2) {
        const dR = p1[0] - p2[0];
        const dG = p1[1] - p2[1];
        const dB = p1[2] - p2[2];
        return Math.sqrt(dR * dR + dG * dG + dB * dB);
    }

    _shuffle(array) {
        const shuffledArray = [...array];
        for (let i = shuffledArray.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            [shuffledArray[i], shuffledArray[j]] = [shuffledArray[j], shuffledArray[i]];
        }
        return shuffledArray;
    }

    _clustersEqual(oldClusters, newClusters) {
        if (oldClusters.length !== newClusters.length) {
            return false;
        }
        for (let i = 0; i < oldClusters.length; i++) {
            if (oldClusters[i].length !== newClusters[i].length) {
                return false;
            }
            for (let j = 0; j < oldClusters[i].length; j++) {
                if (oldClusters[i][j] !== newClusters[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

CodeBlock Loading...

Mini-batch K-Means Algorithm

Below is the result optimized with mini-batch K-Means:

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
fetch('{image url}')
    .then(response => response.blob())
    .then(blob => createImageBitmap(blob))
    .then(imageBitmap => {
        canvas.width = imageBitmap.width;
        canvas.height = imageBitmap.height;
        canvas.classList.remove("animate-pulse");
        ctx.drawImage(imageBitmap, 0, 0);
        const imageData = ctx.getImageData(0, 0, canvas.width, canvas.height);
        const data = imageData.data;
        const pixels = Array.from({
            length: data.length / 4
        }, (_, i) => [data[i * 4], data[i * 4 + 1], data[i * 4 + 2]]);
        const kMeans = new KMeans();
        const clusters = kMeans.cluster(pixels, 5);
        const colors = clusters.centroids;
        const colorsDiv = document.getElementById('colors');
        colors.forEach((color, items) => {
            const div = document.createElement('div');
            console.log(`Color ${items + 1}: rgb(${color[0]}, ${color[1]}, ${color[2]})`);
            div.style.backgroundColor = `rgb(${color[0]}, ${color[1]}, ${color[2]})`;
            colorsDiv.appendChild(div);
        });
    });
class KMeans {
    cluster(data, k, batchSize = 100) {
        const centroids = this._initCentroids(data, k);
        let oldClusters = [];
        let newClusters = [];
        const distancesMap = new Map();
        while (!this._clustersEqual(oldClusters, newClusters)) {
            oldClusters = newClusters;
            newClusters = Array.from({
                length: k
            }, () => []);
            for (let i = 0; i < data.length; i += batchSize) {
                const batch = data.slice(i, i + batchSize);
                const batchDistances = new Map();
                batch.forEach(point => {
                    let distances = distancesMap.get(point);
                    if (!distances) {
                        distances = centroids.map(centroid => this._euclideanDistance(point, centroid));
                        distancesMap.set(point, distances);
                    }
                    batchDistances.set(point, distances);
                });
                batch.forEach(point => {
                    const distances = batchDistances.get(point);
                    const nearestCentroidIndex = distances.indexOf(Math.min(...distances));
                    newClusters[nearestCentroidIndex].push(point);
                });
            }
            centroids.forEach((centroid, i) => {
                const cluster = newClusters[i];
                if (cluster.length > 0) {
                    const [sumR, sumG, sumB] = cluster.reduce(([accR, accG, accB], [r, g, b]) => [accR + r, accG + g, accB + b], [0, 0, 0]);
                    centroids[i] = [sumR / cluster.length, sumG / cluster.length, sumB / cluster.length];
                }
            });
        }
        return {
            centroids,
            clusters: newClusters
        };
    }
    _initCentroids(data, k) {
        const shuffledData = this._shuffle(data);
        return shuffledData.slice(0, k);
    }
    _euclideanDistance(p1, p2) {
        const dR = p1[0] - p2[0];
        const dG = p1[1] - p2[1];
        const dB = p1[2] - p2[2];
        return Math.sqrt(dR * dR + dG * dG + dB * dB);
    }
    _rgbToHex(color) {
        let values = color.replace(/rgba?\(/, '').replace(/\)/, '').replace(/[\s+]/g, '').split(',');
        let a = parseFloat(values[3] || 1),
            r = Math.floor(a * parseInt(values[0]) + (1 - a) * 255),
            g = Math.floor(a * parseInt(values[1]) + (1 - a) * 255),
            b = Math.floor(a * parseInt(values[2]) + (1 - a) * 255);
        return "#" + ("0" + r.toString(16)).slice(-2) + ("0" + g.toString(16)).slice(-2) + ("0" + b.toString(16)).slice(-2);
    }
    _shuffle(array) {
        const shuffledArray = [...array];
        for (let i = shuffledArray.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            [shuffledArray[i], shuffledArray[j]] = [shuffledArray[j], shuffledArray[i]];
        }
        return shuffledArray;
    }
    _clustersEqual(oldClusters, newClusters) {
        if (oldClusters.length !== newClusters.length) {
            return false;
        }
        for (let i = 0; i < oldClusters.length; i++) {
            const oldCentroid = oldClusters[i].centroid;
            const newCentroid = newClusters[i].centroid;
            const dist = distance(oldCentroid, newCentroid);
            if (dist > threshold) {
                return false;
            }
        }
        return true;
    }
}

CodeBlock Loading...

Add Different Theme Colors to Your Website

Add Different Theme Colors to Your Website

Median-Cut Algorithm vs. K-Means Clustering

Result

K-Means Clustering Algorithm JavaScript Code

Mini-batch K-Means Algorithm

Median-Cut Algorithm vs. K-Means Clustering

Result

K-Means Clustering Algorithm JavaScript Code

Mini-batch K-Means Algorithm