这个学期选修了数据挖掘基础。要交一个大作业，正好又因为自己学习前端，想用JavaScript实现Kmeans获取图片色调。

实现功能

通过浏览器选中图片，在本地使用JavaScript和Kmeans获取图片色调。

实现思路

计算机图像是由多个像素组成的，像素又由红绿蓝三种颜色混合而成，红绿蓝通道范围均为[0,255]。正是因为如此，如果把图片的像素当作是三维空间中的一个点，那么计算机图像就是三维空间中的一堆点。可以使用Kmeans算法将这些点进行聚类，最后的结果就是图片颜色的色调。

理论基础-Kmeans

通俗地理解Kmeans，就是“物以类聚”

1. 首先输入k的值，即我们希望将数据集经过聚类得到k个分组。
2. 从数据集中随机选择k个数据点作为质心，并加入到独立的初始簇。
3. 将集合中每一个点，加入到最近的簇。
4. 这时每一个簇下都有一堆点，计算每一个簇的质心。
5. 如果新质心和原质心之间的距离小于某一个设置的阈值，即聚类已经达到期望。算法终止，否则重复3-5。

步骤

图片上传

通过FileReader将图片读取到浏览器端。

    let file = null;
    let image = new Image();
    let reader = new FileReader();
    reader.onload = function (e) {
      image.src = e.target.result;
    };
    document.querySelector("#uploadFile").onchange = function (e) {
      file = event.target.files[0];
      if (file.type.indexOf("image") == 0) {
        reader.readAsDataURL(file);
      }
    };

图片压缩

如果图片太大，或者像素点太多，计算量就会很大，造成浏览器假死。在此需要对选择的图片进行压缩处理。在js中，可以使用canvas的drawImage方法进行图片压缩。主要代码如下

    let canvas = document.querySelector("canvas");
    let image = new Image();
    let targetHeight, targetWidth;
    image.onload = function () {
      let context = canvas.getContext("2d");
      let maxWidth = 500,
        maxHeight = 500;
      targetWidth = image.width;
      targetHeight = image.height;
      let originWidth = image.width,
        originHeight = image.height;
      if (originWidth / originHeight > maxWidth / maxHeight) {
        targetWidth = maxWidth;
        targetHeight = Math.round(maxWidth * (originHeight / originWidth));
      } else {
        targetHeight = maxHeight;
        targetWidth = Math.round(maxHeight * (originWidth / originHeight));
      }
      canvas.width = targetWidth;
      canvas.height = targetHeight;
      context.drawImage(image, 0, 0, targetWidth, targetHeight);
    };

Kmeans算法

接下来使用JavaScript实现Kmeans。方便起见，定义了几个辅助类，并在其中实现了一些成员函数，方便调用。

/**
 * 像素辅助类
 *
 * @class Pixel
 */
class Pixel {
  constructor(r, g, b) {
    this._r = r;
    this._g = g;
    this._b = b;
  }
  get rgb() {
    return {
      r: this._r,
      g: this._g,
      b: this._b,
    };
  }
}

/**
 * 图像的RGB颜色空间中对应的点集合
 *
 * @class RGBSpace
 */
class RGBSpace {
  constructor(canvasContext, img) {
    // 获取图像的rgb数据
    let data = canvasContext.getImageData(0, 0, img.width, img.height).data;
    let rgbSpace = [];
    for (let row = 0; row < img.height; row++) {
      for (let col = 0; col < img.width; col++) {
        // 因为使用getImageData返回来的依次为点的r g b alpha（透明度），所以要加四
        let r = data[(img.width * row + col) * 4];
        let g = data[(img.width * row + col) * 4 + 1];
        let b = data[(img.width * row + col) * 4 + 2];
        rgbSpace.push(new Pixel(r, g, b));
      }
    }
    this._rgbSpace = rgbSpace;
    this._length = img.height * img.width;
  }
  // 获取指定位置上的Pixel
  getPixel(idx) {
    if (idx > this._length) return;
    return this._rgbSpace[idx];
  }
  // 随机获取一个图像中的Pixel
  getRandomPixel() {
    return this.getPixel(Math.floor(Math.random() * this._length));
  }
  // 获取点的个数
  get size() {
    return this._length;
  }
}

/**
 *
 * @class Cluster
 */
class Cluster {
  // 中心rgb和该cluster包含的点
  constructor(pixel) {
    this._centerR = pixel._r;
    this._centerG = pixel._g;
    this._centerB = pixel._b;
    this._cluster = [pixel];
  }
  // 添加到cluster中
  addToCluster(pixel) {
    this._cluster.push(pixel);
  }
  // 重新计算质心centroid
  recalculateCenter() {
    let oldCenter = new Pixel(this._centerR, this._centerG, this._centerB);
    let length = this._cluster.length;
    let reduced = this._cluster.reduce(
      (pre, cur) => {
        let { r: rPre, g: gPre, b: bPre } = pre;
        let { r: rCur, g: gCur, b: bCur } = cur.rgb;
        return {
          r: rPre + rCur,
          g: gPre + gCur,
          b: bPre + bCur,
        };
      },
      { r: 0, g: 0, b: 0 }
    );
    let r = reduced.r / length;
    let g = reduced.g / length;
    let b = reduced.b / length;
    this.cluster = [new Pixel(r, g, b)];
    this._centerR = r;
    this._centerG = g;
    this._centerB = b;
    // 返回原来的质心（后面用于比较新旧质心之间的距离是否“足够近”，从而可以结束算法
    return new Cluster(oldCenter);
  }
  // 获取某个pixel相对于这个cluster的centroid的距离，或者两个cluster的centroid之间的距离
  getDistance(pixel) {
    let { _centerR, _centerG, _centerB } = this;
    if (pixel instanceof Pixel) {
      let { r, g, b } = pixel.rgb;
      return (r - _centerR) ** 2 + (g - _centerG) ** 2 + (b - _centerB) ** 2;
    }
    if (pixel instanceof Cluster) {
      let { _centerR: r, _centerG: g, _centerB: b } = pixel;
      return (r - _centerR) ** 2 + (g - _centerG) ** 2 + (b - _centerB) ** 2;
    }
  }
}

/**
 * 用来分类
 *
 * @param {*} ClusterList
 * @param {*} space
 * @return {*}
 */
function classify(ClusterList, space) {
  space._rgbSpace.forEach((pixel) => {
    // 每个像素都和目前的cluster的centroid计算距离
    let distanceArray = ClusterList.map((Cluster) => {
      return Cluster.getDistance(pixel);
    });
    // 将该像素加入到最近的cluster
    let min = Math.min(...distanceArray);
    let minIndex = distanceArray.indexOf(min);
    ClusterList[minIndex].addToCluster(pixel);
  });
  // 重新计算每个cluster的centroid，并将原来的clusterList返回
  return ClusterList.map((Cluster) => {
    return Cluster.recalculateCenter();
  });
}

/**
 * 判断新点和旧点是否足够近
 *
 * @param {*} old
 * @param {*} now
 * @param {*} threshold
 * @return {*}
 */
function isCloseEnough(old, now, threshold) {
  let index = 0;
  for (let oldCenter of old) {
  	// 如果任意cluster的centroid与旧cluster的centroid大于某一阈值，说明还不足够近
    if (oldCenter.getDistance(now[index++]) > threshold) return false;
  }
  return true;
}

/**
 * 使用Kmeans找相应点颜色
 *
 * @param {*} context
 * @param {*} image
 * @param {*} colorPanel
 * @param {*} K
 * @param {*} threshold
 */
function main(context, image, colorPanel, K, threshold) {
  // 获取一个RGBSpace类的实例
  let space = new RGBSpace(context, image);
  // 随机选取K个像素，并作为K个cluster的centroid
  let ClusterList = Array(K)
    .fill(1)
    .map(() => new Cluster(space.getRandomPixel()));
  let i = 0;
  // 这里和DOM相关了，如果有色板，就创建相应的容器
  if (colorPanel) {
    ClusterList.forEach((el, idx) => {
      let div = document.createElement("div");
      div.className = `panel-${idx}`;
      colorPanel.appendChild(div);
    });
  }
  // 一直循环，直到各个cluster的centroid都和上一次的centroid“足够近”
  while (true) {
    console.log(i++);
    let oldClusterList = classify(ClusterList, space);
    console.log(oldClusterList);
    if (isCloseEnough(oldClusterList, ClusterList, threshold)) {
      break;
    }
    // 将结果展示到对应色板上
    if (colorPanel) {
      ClusterList.forEach((cc, index) => {
        let div = document.createElement("span");
        div.style.backgroundColor = `rgb(${cc._centerR},${cc._centerG},${cc._centerB})`;
        colorPanel.children[index].appendChild(div);
      });
    }
  }
}

全部代码

index.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Kmeans获取图片主色</title>
    <style>
      body {
        display: flex;
        flex-direction: column;
        align-items: center;
      }
      main {
        display: flex;
        flex-direction: column;
        align-items: center;
      }
      .colorPanel div {
        height: 20px;
        display: flex;
      }
      .colorPanel div span {
        height: 20px;
        width: 20px;
        display: block;
      }
      canvas {
        box-shadow: 0 0 10px rgba(0, 0, 0, 0.1);
        margin: 20px;
      }
      section {
        padding: 10px;
      }
    </style>
  </head>
  <body>
    <h2>Kmeans获取图主颜色</h2>
    <main>
      <canvas></canvas>
      <section>
        <input id="uploadFile" type="file" />
        <input class="k" type="number" placeholder="需要输出几种颜色？" />
        <button class="start">Start</button>
      </section>
      <div class="colorPanel"></div>
    </main>
  </body>
  <script src="./index.js"></script>
  <script>
    let file = null;
    let canvas = document.querySelector("canvas");
    let colorPanel = document.querySelector(".colorPanel");
    let image = new Image();
    let reader = new FileReader();
    let targetHeight, targetWidth;
    image.onload = function () {
      let context = canvas.getContext("2d");
      let maxWidth = 500,
        maxHeight = 500;
      targetWidth = image.width;
      targetHeight = image.height;
      let originWidth = image.width,
        originHeight = image.height;
      if (originWidth / originHeight > maxWidth / maxHeight) {
        targetWidth = maxWidth;
        targetHeight = Math.round(maxWidth * (originHeight / originWidth));
      } else {
        targetHeight = maxHeight;
        targetWidth = Math.round(maxHeight * (originWidth / originHeight));
      }
      canvas.width = targetWidth;
      canvas.height = targetHeight;
      context.drawImage(image, 0, 0, targetWidth, targetHeight);
    };
    reader.onload = function (e) {
      image.src = e.target.result;
    };
    document.querySelector("#uploadFile").onchange = function (e) {
      file = event.target.files[0];
      if (file.type.indexOf("image") == 0) {
        reader.readAsDataURL(file);
      }
    };
    document.querySelector("button.start").onclick = function () {
      let context = canvas.getContext("2d");
      let K = parseInt(document.querySelector("input.k").value);
      if (K <= 0) {
        alert("请输入正确参数");
        return;
      }
      document.querySelector(".colorPanel").innerHTML = "";
      main(
        context,
        { height: targetHeight, width: targetWidth },
        colorPanel,
        K,
        1
      );
    };
  </script>
</html>

index.js

详见 Kmeans 算法代码

结束语

其实还是有地方需要改进的，例如可能会出现过于相近的颜色，在这里其实可以在随机选取cluster的centroid时，就检查是否和已经存在的cluster 过于相近，然后酌情重新选择。

其实在做的时候，也在想是否可以将图片进行“规范化”，后来想了一下，如果进行规范化了，不就是改变颜色了吗？选出来的颜色可能就不是原来图片的颜色了。再然后一想，可以将规范后的每个Pixel实例与原来的Pixel实例利用Proxy进行关联，只让规范后的Pixel用作统计上的意义，然后再一想，嗯。算了，好累。