4
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2018-07-01

※移行しました → 【JavaScript】K-meansを使って画像を減色する。

概要

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

ソース

【JavaScript】K-meansを使って画像を減色する。全てフルスクラッチ【canvas】

結果

うまく減色することができました。
ソースは後ほど紹介します。
数字は、k-meansのクラスタ数。
kmeans2.png

デモ

デモ : リンク
クラスタ数を数字で入力し"run"を実行。
JSタブでソースが見れます。

ソース

処理のフローとしては、

  1. canvasに画像を描画
  2. 描画されたピクセルr,g,bを一つの配列に全てpushする
  3. この配列をk-meansでクラスタリングする
  4. 画像の各ピクセルが含まれるクラスタのrgb値を描画する。
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>

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】

4
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?