👾

k-means法を用いて画像をドット絵風に変換する

2022/08/17に公開

 はじめにk-means法を用いて画像を減色しドット絵風に変換するWebアプリを作りました。
https://github.com/3w36zj6/pixel-art-converter
https://3w36zj6.github.io/pixel-art-converter/
(よろしければstarを頂けると幸いです)

 変換例
 Lennak=4
75x75
http://www.ess.ic.kanagawa-it.ac.jp/app_images_j.html

 Mandrillk=8
50x50
http://www.ess.ic.kanagawa-it.ac.jp/app_images_j.html

 海中のイラストk=12
54x30
https://www.irasutoya.com/2016/01/blog-post_620.html

 寿司のイラストk=16
34x21
https://www.irasutoya.com/2013/04/blog-post_705.html

 方針k-means法を利用します。処理の流れは以下の通りです。
ランダムにK(定数)個の画素を選び、クラスタ分けに用いる代表色を決定する。
各画素について、最も近い代表色を選びクラスタ分けをする。
各クラスタについて平均色を計算し、新たな代表色とする。
上記の処理でクラスタの割当てが変化しない、または変化量が閾値を下回った場合に収束したと判断して処理を終了する。そうでなければ処理を繰り返す。

 実装https://github.com/3w36zj6/pixel-art-converter/blob/main/src/convert.ts

 画像の読み込みImageDataで画像データを取得し、pixelsに入れ直しています。
export function pixelizeImageData(imageData: ImageData, k: number): ImageData {
  const { width, height, data } = imageData
  const pixels: number[][] = []

  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      const base = (y * width + x) * 4
      pixels.push([data[base + 0], data[base + 1], data[base + 2]])
    }
  }
  // 省略
}

 クラスタ分けに用いる代表色の決定ランダムにK個の画素を選び、その画素の色をクラスタ分けに用いる代表色の初期値とします。
function chooseAtRandom(array: number[][], count: number): number[][] {
  count = count || 1
  array = array.slice()

  const result = []
  for (const i of Array.from({ length: count }).keys()) {
    const arrayIndex = Math.floor(Math.random() * array.length)
    result[i] = array[arrayIndex]
    array.splice(arrayIndex, 1)
  }
  return result
}

export function pixelizeImageData(imageData: ImageData, k: number): ImageData {
  // 省略
  let chosenPixels = chooseAtRandom(pixels, k)
  // 省略
}
https://cly7796.net/blog/javascript/get-one-randomly-from-the-specified-multiple-values/

 色の距離の計算(R_1,G_1,B_1)と(R_2,G_2,B_2)のユークリッド距離を計算すると\sqrt{(R_1-R_2)^2+(G_1-G_2)^2+(B_1-B_2)^2}となります。大小関係が分かれば良いので平方根はとっていません。
function abs(color1: number[], color2: number[]): number {
  return (color1[0] - color2[0]) ** 2 + (color1[1] - color2[1]) ** 2 + (color1[2] - color2[2]) ** 2
}

 各画素のクラスタ分けこれ以降の処理はクラスタ分けが収束するまで繰り返します。ここでは収束判定をサボって10回固定にしています。
各画素について、代表色のうち色の距離が最も近いものを選びクラスタ分けをします。
export function pixelizeImageData(imageData: ImageData, k: number): ImageData {
  // 省略
  let groupIndexes: number[] = []

  // これ以降の処理を収束するまで繰り返す
  for (let iter = 0; iter < 10; iter++) {
    groupIndexes = []
    for (const pixel of pixels) {
      const distances = chosenPixels.map(cp => abs(pixel, cp))
      groupIndexes.push(distances.indexOf(Math.min(...distances)))
    }
    // 省略
  }
  // 省略
}

 代表色の更新各クラスタについて平均色を計算し、それを新たな代表色とします。
export function pixelizeImageData(imageData: ImageData, k: number): ImageData {
  // 省略

  // これ以降の処理を収束するまで繰り返す
  for (let iter = 0; iter < 10; iter++) {
    // 省略
    const groupIndexCount = Array.from({ length: k }, (_, i) => groupIndexes.filter(x => x === i).length)
    const means = Array.from({ length: k }, () => [0, 0, 0])

    for (let i = 0; i < pixels.length; i++) {
      means[groupIndexes[i]][0] += pixels[i][0] / groupIndexCount[groupIndexes[i]]
      means[groupIndexes[i]][1] += pixels[i][1] / groupIndexCount[groupIndexes[i]]
      means[groupIndexes[i]][2] += pixels[i][2] / groupIndexCount[groupIndexes[i]]
    }

    chosenPixels = means
  }
  // 省略
}

 変更をCanvasに出力クラスタの割当てが収束したら、pixelsのRGBの値で新しいImageDataを作成し返却します。
export function pixelizeImageData(imageData: ImageData, k: number): ImageData {
  // 省略

  // これ以降の処理を収束するまで繰り返す
  for (let iter = 0; iter < 10; iter++) {
    // 省略
  }

  const newData = new Uint8ClampedArray(data.length)
  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      const base = (y * width + x) * 4
      const color = chosenPixels[groupIndexes[y * width + x]]
      newData[base + 0] = color[0]
      newData[base + 1] = color[1]
      newData[base + 2] = color[2]
      newData[base + 3] = 255
    }
  }
  return new ImageData(newData, width, height)
}