最近想要做一個獲取博文頭圖的顏色的功能，想到了好久好久之前寫過一篇通過 中位切分算法 來實現圖片的顏色提取。
中位切分算法與 K-Means 聚類算法#
中位切分算法是一種基於顏色直方圖的算法，通過遞歸將顏色空間劃分成小立方體，最後每個小立方體的顏色值用該立方體內顏色的中位數代表。這種算法在圖像顏色分佈不均勻的情況下容易出現明顯的顏色偏差，導致提取出來的顏色不準確，例如圖片有大量紅色，少量綠色，提取出來的顏色會偏向於紅色。同時使用中位切分算法的話一張圖片每次提取出來的顏色都是一樣的。
而 K-Means 聚類算法 比較擅長處理圖像顏色分佈不均勻的情況，而且採用 隨機初始化聚類中心 提取出來的顏色可以實現每次都不一樣。
當然由於 K-Means 聚類算法的收斂速度較慢，圖片過大可能會導致耗時比較長。不過對於博客圖片的大小來說可以忽略不計。和中位切分算法一樣，K-Means 聚類算法也會將圖片繪製在 canvas 裡，所以也會出現跨域導致畫布被污染的問題。
效果#
這是應用於網站後的效果，當你的瀏覽器支持顯示網頁的主題色的話，可以看到狀態欄的顏色會變為頭圖的隨機顏色。
下面是使用 K-Means 聚類算法獲取圖片五種顏色的實時渲染：
K-Means 聚類算法 JavaScript 代碼#
主要 JavaScript 代碼如下：
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
fetch('{圖片地址}')
.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(`顏色${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 算法#
mini-batch K-Means 算法是 K-Means 算法的優化版，由於 mini-batch K-Means 算法僅隨機選擇一部分數據進行計算，可以減少計算成本，更快地處理大規模數據集。但是也是由於只隨機選擇一部分數據進行計算，所以 mini-batch K-Means 算法會不如 K-Means 算法的結果準確。
下面是使用 mini-batch K-Means 算法優化的結果：
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
fetch('{圖片地址}')
.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(`顏色${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;
}
}
此文由 Mix Space 同步更新至 xLog
原始鏈接為 https://www.vinking.top/posts/codes/median-cut-k-means-algorithms-javascript-implementation