【JavaScript】K-meansを使って画像を減色してみる。【canvas】

### [※移行しました → 【JavaScript】K-meansを使って画像を減色する。](https://tech-blog.s-yoshiki.com/entry/17/)

# 概要
K-menasで画像を減色してみた。
JavaScript + canvasを使用。
OpenCVとかライブラリは使わず全てフルスクラッチ

#### ソース
[【JavaScript】K-meansを使って画像を減色する。全てフルスクラッチ【canvas】](https://tech-blog.s-yoshiki.com/2018/07/197/)

# 結果
うまく減色することができました。
ソースは後ほど紹介します。
数字は、k-meansのクラスタ数。
![kmeans2.png](https://qiita-image-store.s3.amazonaws.com/0/82419/993a158b-6678-7bd6-6f3b-7c53ad97250f.png)

# デモ
<a href="//jsfiddle.net/s_yoshiki/ntoa92uw/show">デモ : リンク</a>
クラスタ数を数字で入力し"run"を実行。
JSタブでソースが見れます。

# ソース

処理のフローとしては、
1. canvasに画像を描画
2. 描画されたピクセルr,g,bを一つの配列に全てpushする
3. この配列をk-meansでクラスタリングする
4. 画像の各ピクセルが含まれるクラスタのrgb値を描画する。


```html:index.html
<canvas id="canvas"></canvas>
<br>
<input type="text" id="claster_n" value="3">
<button id="run">
run
</button>
<button id="reset">
reset
</button><br>
<input type="checkbox" id="high-speed" checked> 高速計算
<div id="result">

</div>

```

```javascript:index.js
(function() {
    var b64_lenna = "画像のURL"

    readImage(b64_lenna, draw)

    document.getElementById("run").addEventListener("click", function() {
        try {
            subtractiveColor()
            document.getElementById("result").innerHTML = "計算終了"
        } catch (e) {
            document.getElementById("result").innerHTML = "計算失敗<br>" + e
        }
    })

    document.getElementById("reset").addEventListener("click", function() {
        readImage(b64_lenna, draw)
        document.getElementById("result").innerHTML = ""
    })

    function subtractiveColor() {
        let canvas = document.getElementById("canvas")
        let ctx = canvas.getContext("2d")
        let reduction_flg = document.getElementById("high-speed").checked
        var src = ctx.getImageData(0, 0, canvas.width, canvas.height);
        var dst = ctx.createImageData(src);
        var class_n = parseInt(document.getElementById("claster_n").value, 10)
        class_n = class_n === 0 ? 2 : class_n
        var mat = []

        for (var i = 0; i < src.data.length; i += 4) {
            if (reduction_flg) {
                if ((i / 4) % (canvas.width * 2) >= canvas.width) {
                    continue
                }
                if (i % 8 === 4) {
                    continue
                }
            }
            mat.push([
                src.data[i],
                src.data[i + 1],
                src.data[i + 2]
            ])
        }

        var arg = {
            "map": mat, //乱数データ
            "n": class_n, // クラスタ数
            "transaction_max": 100 //試行回数上限
        }
        //
        // k-menas
        //
        var km = KMeans(arg)
        var _w = canvas.width / 2
        for (var i = 0; i < dst.data.length; i += 4) {
            var count = i / 4
            var index = -1
            var mode = 0
            if (reduction_flg) {
                if ((i / 4) % (canvas.width * 2) >= canvas.width) {
                    if (i % 8 === 4) {
                        mode = 4
                    } else {
                        mode = 3
                    }
                } else if (i % 8 === 4) {
                    mode = 2
                } else {
                    mode = 1
                }

            } else {
                mode = 0
            }
            try {
                var r = 0,
                    g = 0,
                    b = 0
                if (mode === 0) {
                    index = km.node[count]
                    r = Math.ceil(km.result[index][0])
                    g = Math.ceil(km.result[index][1])
                    b = Math.ceil(km.result[index][2])

                } else if (mode === 1) {
                    count = count / 2 - Math.ceil((i / 4) / canvas.width / 2) * (canvas.width / 2) + canvas.width / 2
                    index = km.node[count]
                    r = Math.ceil(km.result[index][0])
                    g = Math.ceil(km.result[index][1])
                    b = Math.ceil(km.result[index][2])

                } else if (mode === 2) {
                    r = dst.data[i - 4]
                    g = dst.data[i - 4 + 1]
                    b = dst.data[i - 4 + 2]

                } else if (mode === 3) {
                    count = canvas.width * 4
                    r = dst.data[i - count]
                    g = dst.data[i + 1 - count]
                    b = dst.data[i + 2 - count]

                } else if (mode === 4) {
                    count = canvas.width * 4
                    r = dst.data[i - count]
                    g = dst.data[i + 1 - count]
                    b = dst.data[i + 2 - count]
                }
                dst.data[i] = r
                dst.data[i + 1] = g
                dst.data[i + 2] = b

            } catch (e) {}

            dst.data[i + 3] = src.data[i + 3]
        }
        ctx.putImageData(dst, 0, 0);
    }

    function draw(image) {
        let canvas = document.getElementById("canvas")
        let ctx = canvas.getContext("2d")
        canvas.width = image.width
        canvas.height = image.height
        ctx.drawImage(image, 0, 0)
    }

    function readImage(image_src, callback) {
        let image = new Image()
        image.src = image_src
        image.onload = function() {
            if (callback !== undefined) {
                callback(image)
            }
        }
    }


    function KMeans(obj) {
        var ptnMap = obj.map.slice();
        var ptnMapBuffer = new Array(obj.map.length)
        var grvArr = obj.map.slice(0, obj.n)
        var transaction = obj.transaction_max
        var count = 0;

        runClusterLoop()

        return {
            "result": grvArr,
            "count": count,
            "node": getBelongingCluster(grvArr, obj.map)
        };

        //クラスタリング メインロジック
        function runClusterLoop() {
            var buffer = grvArr.slice();
            var result = calcClaster(ptnMap, grvArr);

            if (isEqualArray(buffer, grvArr)) {
                return;
            }

            if (count > transaction) {
                return
            }
            count++;
            runClusterLoop();
        }

        // 配列の比較
        function isEqualArray(arr1, arr2) {
            var a = JSON.stringify(arr1);
            var b = JSON.stringify(arr2);
            return (a === b);
        }

        // クラスタの計算
        function calcClaster(node, clusters) {
            var i = 0
            //配列初期化
            var store = new Array(clusters.length);

            for (i = 0; i < store.length; i++) {
                store[i] = [];
            }

            //ノードループ
            for (i = 0; i < node.length; i++) {
                var minVal = calcDistance(node[i], clusters[0]);
                var minCount = 0;

                //クラスタループ
                for (var j = 0; j < clusters.length; j++) {
                    if (calcDistance(node[i], clusters[j]) < minVal) {
                        minCount = j;
                        minVal = calcDistance(node[i], clusters[j]);
                    }
                }
                store[minCount].push(node[i].slice());
            }

            for (i = 0; i < clusters.length; i++) {
                clusters[i] = calcGravity(store[i]);
            }

            return clusters;
        }

        // 分類
        function getBelongingCluster(cluster, node) {
            var result = []
            for (var i = 0; i < node.length; i++) {
                var minValue = -1;
                var minIndex = 0;

                for (var j = 0; j < cluster.length; j++) {
                    var d = calcDistance(cluster[j], node[i])
                    if (j === 0 || d < minValue) {
                        minValue = d
                        minIndex = j
                    }
                }
                result.push(minIndex)
            }

            return result
        }

        // 重心
        function calcGravity(vec) {
            var sum = vec[0];
            for (var i = 1; i < vec.length; i++) {
                for (var j = 0; j < sum.length; j++) {
                    sum[j] += vec[i][j];
                }
            }
            for (var j = 0; j < sum.length; j++) {
                sum[j] /= vec.length;
            }
            return sum;
        }

        // 距離
        function calcDistance(vec1, vec2) {
            var result = 0;
            for (var i = 0; i < vec1.length; i++) {
                result += Math.pow(2, Math.abs(vec2[i] - vec1[i]));
            }
            return (Math.sqrt(result));
        }

        //配列初期化
        function initMat(n, m, min, max) {
            if (min === undefined || min === null) {
                min = 0;
                max = 512;
            }
            if (max === undefined) {
                max = 512;
            }
            var array = [];
            for (var i = 0; i < m; i++) {
                var tmp = [];
                for (var j = 0; j < n; j++) {
                    tmp.push(getRandomInt(min, max));
                }
                array.push(tmp);
            }
            return array;
        }

        function getRandomInt(min, max) {
            return Math.floor(Math.random() * (max - min + 1)) + min;
        }
    }
})()

```


# 参考
[【JavaScript】K-meansを使って画像を減色する。全てフルスクラッチ【canvas】](https://tech-blog.s-yoshiki.com/entry/17)