👾

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

2022/08/17に公開

JavaScript

はじめに

k-means法を用いて画像を減色しドット絵風に変換するWebアプリを作りました。

(よろしければstarを頂けると幸いです)

変換例

Lenna

k=4
75x75

Mandrill

k=8
50x50

海中のイラスト

k=12
54x30

寿司のイラスト

k=16
34x21

方針

k-means法を利用します。処理の流れは以下の通りです。

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

実装

画像の読み込み

変換前の画像がoriginalCanvasで、変換後の画像がconvertedCanvasになります。getImageData()で得た配列は扱いづらいので、pixelsに入れ直しています。

export const convert = (originalCanvas: HTMLCanvasElement, convertedCanvas: HTMLCanvasElement, k: number) => {
    const originalContext = originalCanvas.getContext("2d")
    const imageData = originalContext.getImageData(0, 0, originalCanvas.width, originalCanvas.height)

    const pixels = []

    for (const y of Array(originalCanvas.height).keys()) {
        for (const x of Array(originalCanvas.width).keys()) {
            const base = (y * originalCanvas.width + x) * 4
            pixels.push([imageData.data[base + 0], imageData.data[base + 1], imageData.data[base + 2]])
        }
    }
    // 省略
}

クラスタ分けに用いる代表色の決定

ランダムにK個の画素を選び、その画素の色をクラスタ分けに用いる代表色の初期値とします。

const choose_at_random = (array, count: number) => {
    count = count || 1
    array = array.slice()

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

export const convert = (originalCanvas: HTMLCanvasElement, convertedCanvas: HTMLCanvasElement, k: number) => {
    // 省略
    let chosenPixels = choose_at_random(pixels, k)
    // 省略
}

色の距離の計算

$(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}$ となります。大小関係が分かれば良いので平方根はとっていません。

const abs = (color1: number[], color2: number[]): number => {
    return (color1[0] - color2[0]) ** 2 + (color1[1] - color2[1]) ** 2 + (color1[2] - color2[2]) ** 2
}

各画素のクラスタ分け

これ以降の処理はクラスタ分けが収束するまで繰り返します。~~ここでは収束判定をサボって10回固定にしています。~~

各画素について、代表色のうち色の距離が最も近いものを選びクラスタ分けをします。

export const convert = (originalCanvas: HTMLCanvasElement, convertedCanvas: HTMLCanvasElement, k: number) => {
    // 省略
    let groupIndexes = []
    
    // これ以降の処理を収束するまで繰り返す
    for (const _ of Array(10).keys()) {
        groupIndexes = []
        for (const pixel of pixels) {
            const distances = []
            for (const chosenPixel of chosenPixels) {
                distances.push(abs(pixel, chosenPixel))
            }
            groupIndexes.push(distances.indexOf(Math.min(...distances)))

        }
	// 省略
    }
    // 省略
}

代表色の更新

各クラスタについて平均色を計算し、それを新たな代表色とします。

export const convert = (originalCanvas: HTMLCanvasElement, convertedCanvas: HTMLCanvasElement, k: number) => {
    // 省略
    
    // これ以降の処理を収束するまで繰り返す
    for (const _ of Array(10).keys()) {
        // 省略
        const groupIndexCount = [...Array(k).keys()].map((i) => { return groupIndexes.filter(x => x == i).length })

        const means = [...Array(k).keys()].map((i) => { return [0, 0, 0] })

        for (const i of Array(pixels.length).keys()) {
            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の値を変換後のCanvasに出力します。

export const convert = (originalCanvas: HTMLCanvasElement, convertedCanvas: HTMLCanvasElement, k: number) => {
    // 省略
    
    // これ以降の処理を収束するまで繰り返す
    for (const _ of Array(10).keys()) {
        // 省略
    }
    for (const y of Array(originalCanvas.height).keys()) {
        for (const x of Array(originalCanvas.width).keys()) {
            const base = (y * originalCanvas.width + x) * 4
            imageData.data[base + 0] = chosenPixels[groupIndexes[(y * originalCanvas.width + x)]][0]
            imageData.data[base + 1] = chosenPixels[groupIndexes[(y * originalCanvas.width + x)]][1]
            imageData.data[base + 2] = chosenPixels[groupIndexes[(y * originalCanvas.width + x)]][2]
            imageData.data[base + 3] = 255
        }
    }
    const convertedContext = convertedCanvas.getContext("2d")
    convertedContext.putImageData(imageData, 0, 0)
}