Recently, I wanted to create a feature to obtain the colors of blog post header images, and I remembered a long time ago I wrote an article on how to extract image colors using the median cutting algorithm.
Median Cutting Algorithm and K-Means Clustering Algorithm#
The median cutting algorithm is a method based on color histograms that recursively divides the color space into small cubes, with the color value of each small cube represented by the median color within that cube. This algorithm can exhibit significant color bias when the image's color distribution is uneven, leading to inaccurate color extraction. For example, if an image has a lot of red and a small amount of green, the extracted color will lean towards red. Additionally, when using the median cutting algorithm, the colors extracted from an image are always the same.
On the other hand, the K-Means clustering algorithm is better at handling uneven color distributions in images, and by using randomly initialized cluster centers, the extracted colors can vary each time.
Of course, due to the slower convergence speed of the K-Means clustering algorithm, processing larger images may take longer. However, this can be negligible for the size of blog images. Like the median cutting algorithm, the K-Means clustering algorithm also draws the image on a canvas, which can lead to cross-origin issues that cause the canvas to be tainted.
Effect#
This is the effect applied to the website. If your browser supports displaying the theme color of the webpage, you can see that the status bar color changes to a random color from the header image.
Below is the real-time rendering of five colors extracted from the image using the K-Means clustering algorithm:
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;
}
}
Mini-Batch K-Means Algorithm#
The mini-batch K-Means algorithm is an optimized version of the K-Means algorithm. Since the mini-batch K-Means algorithm only randomly selects a portion of the data for computation, it can reduce computational costs and process large datasets more quickly. However, because it only randomly selects a portion of the data, the results of the mini-batch K-Means algorithm may not be as accurate as those of the K-Means algorithm.
Below is the result optimized using the mini-batch K-Means algorithm:
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;
}
}
This article is synchronized and updated to xLog by Mix Space. The original link is https://www.vinking.top/posts/codes/median-cut-k-means-algorithms-javascript-implementation