最近、ブログのヘッダー画像の色を取得する機能を作りたいと思い、ずっと前に 中位切分アルゴリズム を使って画像の色を抽出する記事を書いたことを思い出しました。
中位切分アルゴリズムと K-Means クラスタリングアルゴリズム#
中位切分アルゴリズムは、色ヒストグラム に基づくアルゴリズムで、再帰的に色空間を小さな立方体に分割し、最終的に各小立方体の色値をその立方体内の色の中央値で表します。このアルゴリズムは、画像の色分布が不均一な場合に明らかな色の偏りが生じやすく、抽出された色が不正確になることがあります。例えば、画像に大量の赤色と少量の緑色がある場合、抽出される色は赤色に偏ります。また、中位切分アルゴリズムを使用すると、1 枚の画像から毎回同じ色が抽出されます。
一方、K-Means クラスタリングアルゴリズム は、画像の色分布が不均一な状況を処理するのが得意で、ランダムに初期クラスタ中心を選択する ことで、毎回異なる色を抽出することができます。
もちろん、K-Means クラスタリングアルゴリズムは収束速度が遅いため、画像が大きすぎると処理に時間がかかる可能性があります。しかし、ブログ画像のサイズに関しては無視できる程度です。中位切分アルゴリズムと同様に、K-Means クラスタリングアルゴリズムも画像を canvas に描画するため、クロスドメインによるキャンバスの汚染問題が発生することがあります。
効果#
これはウェブサイトに適用した後の効果です。ブラウザがウェブページのテーマ色を表示することをサポートしている場合、ステータスバーの色がヘッダー画像のランダムな色に変わります。
以下は、K-Means クラスタリングアルゴリズムを使用して画像から 5 つの色をリアルタイムでレンダリングしたものです：
K-Means クラスタリングアルゴリズム JavaScript コード#
主要な JavaScript コードは以下の通りです：
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
fetch('{画像の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(`色${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('{画像の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(`色${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 です。