使用 JavaScript 对图像进行量化并提取主要颜色

媒介

前段时间在 Halo 的 应用市场 中碰到希望主题和插件的封面图配景色为封面图主色的问题，于是乎需要根据封面图提取主色就想到使用 K-Means 算法来提取。
在图像处置处罚中，图像是由像素点构成的，每个像素点都有一个颜色值，颜色值通常由 RGB 三个分量组成。因此，我们可以将图像看作是一个由颜色值构成的点云，每个点代表一个像素点。
为了更好地理解，我们可以将图像的颜色值可视化为一个 Scatter 3D 图。在 Scatter 3D 图中，每个点的坐标由 RGB 三个分量组成，点的颜色与其坐标对应的颜色值雷同。
图像的颜色值量化

以下面的图片为例
   它的色值分布为如下的图像

从上述 RGB 3D Scatter Plot 图假如将相似的颜色值归为一类可以看出图像大概有三种主色调蓝色、绿色和粉色：

假如我们从三簇中各选一个中心，如以 A、B、C三点表现 A(50, 150, 200)、B(240, 150, 200)、C(50, 100, 50) 并将每个数据点分配到最近的中心地点的簇中这个过程称之为聚类而这个中心称之为聚类中心，这样就可以得到 K 个以聚类中心为坐标的主色值。而 K-Means 算法是一种常用的聚类算法，它的根本思想就是将数据集分成 K 个簇，每个簇的中心点称为聚类中心，将每个数据点分配到最近的聚类中心地点的簇中。
K-Means 算法的实现过程如下：

• 初始化聚类中心：随机选择 K 个点作为聚类中心。
  
• 分配数据点到最近的聚类中心地点的簇中：对于每个数据点，盘算它与每个聚类中心的间隔，将它分配到间隔最近的聚类中心地点的簇中。
  
• 更新聚类中心：对于每个簇，盘算它的所有数据点的均匀值，将这个均匀值作为新的聚类中心。
  
• 重复步骤 2 和步骤 3，直到聚类中心不再改变或达到最大迭代次数。
  

在图像处置处罚中，我们可以将每个像素点的颜色值看作是一个三维向量，使用欧几里得间隔盘算两个颜色值之间的间隔。对于每个像素点，我们将它分配到间隔最近的聚类中心地点的簇中，然后将它的颜色值更换为地点簇的聚类中心的颜色值，如 A1(10, 140, 170) 以间隔它最近的间隔中心 A 的坐标表现即 A1 = A(50, 150, 200)。这样，我们就可以将图像中的颜色值进行量化，将相似的颜色值归为一类。
最后，我们可以根据聚类中心的颜色值，盘算每个颜色值在图像中出现的次数，并按出现次数从大到小排序，取前几个颜色作为主要颜色。

1. <script>
2.   const img = new Image();
3.   img.src = "https://guqing-blog.oss-cn-hangzhou.aliyuncs.com/image.jpg";
4.   img.setAttribute("crossOrigin", "");
6.   img.onload = function () {
7.     const canvas = document.createElement("canvas");
8.     const ctx = canvas.getContext("2d");
9.     canvas.width = img.width;
10.     canvas.height = img.height;
11.     ctx.drawImage(img, 0, 0);
13.     const imageData = ctx.getImageData(0, 0, canvas.width, canvas.height);
14.     const data = imageData.data;
16.     const k = 3; // 聚类数
17.     const centers = quantize(data, k);
18.     console.log(centers)
20.     for (const color of centers) {
21.       const div = document.createElement("div");
22.       div.style.width = "50px";
23.       div.style.height = "50px";
24.       div.style.backgroundColor = color;
25.       document.body.appendChild(div);
26.     }
27.   };
29.   function quantize(data, k) {
30.     // 将颜色值转换为三维向量
31.     const vectors = [];
32.     for (let i = 0; i < data.length; i += 4) {
33.       vectors.push([data[i], data[i + 1], data[i + 2]]);
34.     }
36.     // 随机选择 K 个聚类中心
37.     const centers = [];
38.     for (let i = 0; i < k; i++) {
39.       centers.push(vectors[Math.floor(Math.random() * vectors.length)]);
40.     }
42.     // 迭代更新聚类中心
43.     let iterations = 0;
44.     while (iterations < 100) {
45.       // 分配数据点到最近的聚类中心所在的簇中
46.       const clusters = new Array(k).fill().map(() => []);
47.       for (let i = 0; i < vectors.length; i++) {
48.         let minDist = Infinity;
49.         let minIndex = 0;
50.         for (let j = 0; j < centers.length; j++) {
51.           const dist = distance(vectors[i], centers[j]);
52.           if (dist < minDist) {
53.             minDist = dist;
54.             minIndex = j;
55.           }
56.         }
57.         clusters[minIndex].push(vectors[i]);
58.       }
60.       // 更新聚类中心
61.       let converged = true;
62.       for (let i = 0; i < centers.length; i++) {
63.         const cluster = clusters[i];
64.         if (cluster.length > 0) {
65.           const newCenter = cluster
66.             .reduce((acc, cur) => [
67.               acc[0] + cur[0],
68.               acc[1] + cur[1],
69.               acc[2] + cur[2],
70.             ])
71.             .map((val) => val / cluster.length);
72.           if (!equal(centers[i], newCenter)) {
73.             centers[i] = newCenter;
74.             converged = false;
75.           }
76.         }
77.       }
79.       if (converged) {
80.         break;
81.       }
83.       iterations++;
84.     }
86.     // 将每个像素点的颜色值替换为所在簇的聚类中心的颜色值
87.     for (let i = 0; i < data.length; i += 4) {
88.       const vector = [data[i], data[i + 1], data[i + 2]];
89.       let minDist = Infinity;
90.       let minIndex = 0;
91.       for (let j = 0; j < centers.length; j++) {
92.         const dist = distance(vector, centers[j]);
93.         if (dist < minDist) {
94.           minDist = dist;
95.           minIndex = j;
96.         }
97.       }
98.       const center = centers[minIndex];
99.       data[i] = center[0];
100.       data[i + 1] = center[1];
101.       data[i + 2] = center[2];
102.     }
104.     // 计算每个颜色值在图像中出现的次数，并按出现次数从大到小排序
105.     const counts = {};
106.     for (let i = 0; i < data.length; i += 4) {
107.       const color = `rgb(${data[i]}, ${data[i + 1]}, ${data[i + 2]})`;
108.       counts[color] = counts[color] ? counts[color] + 1 : 1;
109.     }
110.     const sortedColors = Object.keys(counts).sort(
111.       (a, b) => counts[b] - counts[a]
112.     );
114.     // 取前 k 个颜色作为主要颜色
115.     return sortedColors.slice(0, k);
116.   }
118.   function distance(a, b) {
119.     return Math.sqrt(
120.       (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 + (a[2] - b[2]) ** 2
121.     );
122.   }
124.   function equal(a, b) {
125.     return a[0] === b[0] && a[1] === b[1] && a[2] === b[2];
126.   }
127. </script>

复制代码

主动选取 K 值

在现实应用中，我们大概不知道应该选择多少个聚类中心，即 K 值。一种常用的方法是使用 Gap 统计量法，它的根本思想是比力聚类效果与随机数据集的聚类效果之间的差异，选择使差异最大的 K 值。
Gap 统计量法的实现过程如下：

• 对原始数据集进行 K-Means 聚类，得到聚类效果。
  
• 生成 B 个随机数据集，对每个随机数据集进行 K-Means 聚类，得到聚类效果。
  
• 盘算聚类效果与随机数据集聚类效果之间的差异，使用 Gap 统计量表现。
  
• 选择使 Gap 统计量最大的 K 值。
  

下面是使用 JavaScript 实现 Gap 统计量法的示例代码：

1. function gap(data, maxK) {
2.   const gaps = [];
3.   for (let k = 1; k <= maxK; k++) {
4.     const quantized = quantize(data, k);
5.     const gap = logWk(quantized) - logWk(randomData(data.length));
6.     gaps.push(gap);
7.   }
8.   const maxGap = Math.max(...gaps);
9.   return gaps.findIndex((gap) => gap === maxGap) + 1;
10. }
12. function logWk(quantized) {
13.   const counts = {};
14.   for (let i = 0; i < quantized.length; i++) {
15.     counts[quantized[i]] = counts[quantized[i]] ? counts[quantized[i]] + 1 : 1;
16.   }
17.   const n = quantized.length;
18.   const k = Object.keys(counts).length;
19.   const wk = Object.values(counts).reduce((acc, cur) => acc + cur * Math.log(cur / n), 0);
20.   return Math.log(n) + wk / n;
21. }
23. function randomData(n) {
24.   const data = new Uint8ClampedArray(n * 4);
25.   for (let i = 0; i < data.length; i++) {
26.     data[i] = Math.floor(Math.random() * 256);
27.   }
28.   return data;
29. }

复制代码

使用：

1. const k = gap(data, 10)
2. // const k = 3; // 聚类数
3. const centers = quantize(data, k);

复制代码

好吧，挺贫困的，最终直接将封面图再作为配景图添加 backdrop-filter 来实现了