はじめに

Kmeans法で減色処理って遅いですよね。
何とかならないだろうかと思って考えてみました。
基本的な考え方は、画像を小さくしてKmeansし、量子化して画像を再構築する。であり、Kmeans法自体を速くするわけではありません。
本アルゴリズムは、「多少粗くてもいいから速い」がコンセプトなのでご注意ください。

実験結果

改良前と後で、Kmeansにかかる時間とKmeansの結果を表示するまでの時間を測定しました。
使用画像は lenna.bmp です。attempts = 2, size = 32, bitDepth = 4 です。
以下、kを変えて時間を測定してみます。

k = 5	Kmeans法にかかる時間	Kmeans後表示するまでの時間
改良前 - kmeans	300ms	54ms
改良後 - fastKmeans	2ms	71ms

k = 10	Kmeans法にかかる時間	Kmeans後表示するまでの時間
改良前 - kmeans	1200ms	52ms
改良後 - fastKmeans	6ms	72ms

k = 15	Kmeans法にかかる時間	Kmeans後表示するまでの時間
改良前 - kmeans	2100ms	52ms
改良後 - fastKmeans	10ms	72ms

kが増えても改良後はあまり遅くならないようです。
Kmeansする画像が小さい(要素の数が少ない)ので改良後の方が当然早くなります。
Kmeans後表示するまでの時間が思ったより遅くならないようです。

改良前のソース(普通のKmeansを使って減色処理)

    /**
     * Color reduction processing using K-means
     * @param {Mat} src source mat 
     * @param {Mat} dst destination mat
     * @param {number} k cluster count
     * @param {number} attempts number of attempts 
     * @param {number} maxCount the maximum number of iterations/elements
     * @param {number} epsilon the desired accuracy
     * @returns {Mat} destination mat
     */
    static kmeans(src, dst, k, attempts, maxCount = 1e4, epsilon = 1e-4) {
        // Initialize
        dst = dst || new cv.Mat(src.size(), src.type());
        const [labels, centers] = [new cv.Mat(), new cv.Mat()];
        const criteria = new cv.TermCriteria(cv.TermCriteria_EPS + cv.TermCriteria_MAX_ITER, maxCount, epsilon);
        const flags = cv.KMEANS_PP_CENTERS;

        // Create samples
        const samples = new cv.Mat(src.rows * src.cols, 3, cv.CV_32F);
        for(let y = 0; y < src.rows; y += 1) {
            for(let x = 0; x < src.cols; x += 1) {
                const idx = y * src.cols + x;
                for(let z = 0; z < 3; z += 1) {                    
                    samples.floatPtr(idx)[z] = src.data[idx * 4 + z];
                }
            }
        }

        // K-Means method
        let startDate = new Date();
        cv.kmeans(samples, k, labels, criteria, attempts, flags, centers);
        console.log('kmeans:', new Date() - startDate, 'ms');
        
        // Convert Float to UInt8
        const floatToUint8 = x => Math.min(Math.max(Math.round(x), 0), 255);
        const ui8Centers = new Uint8Array(k * 3);
        for(let c = 0; c < k; c += 1) {
            for(let z = 0; z < 3; z += 1) {
                ui8Centers[c * 3 + z] = floatToUint8(centers.floatAt(c, z));
            }
        }        
        centers.delete();
        
        // Create dst from labels and centers
        startDate = new Date();
        for(let y = 0; y < dst.rows; y += 1) {
            for(let x = 0; x < dst.cols; x += 1) {
                const p = (y * dst.cols + x) * 4;
                const c = labels.data[p];
                for(let z = 0; z < 3; z += 1) {                    
                    dst.data[p + z] = ui8Centers[c * 3 + z];
                }
                dst.data[p + 3] = src.data[p + 3];
            }
        }
        labels.delete();
        console.log('after kmeans:', new Date() - startDate, 'ms');
        return dst;
    }

改良後のソース

    /**
     * Fast color reduction processing using K-means
     * @param {Mat} src source mat 
     * @param {Mat} dst destination mat
     * @param {Size} dsize size in resizing
     * @param {number} interpolation interpolation
     * @param {number} bitDepth bit depth [1, 8]
     * @param {number} k cluster count
     * @param {number} attempts number of attempts 
     * @param {number} maxCount the maximum number of iterations/elements
     * @param {number} epsilon the desired accuracy
     * @returns {Mat} destination mat
     */
    static fastKmeans(src, dst, dsize, interpolation, bitDepth, k, attempts, maxCount = 1e4, epsilon = 1e-4) {
        // Resize
        const resized = new cv.Mat();
        cv.resize(src, resized, dsize, 0, 0, interpolation);

        // Initialize
        dst = dst || new cv.Mat(src.size(), src.type());
        const [labels, centers] = [new cv.Mat(), new cv.Mat()];
        const criteria = new cv.TermCriteria(cv.TermCriteria_EPS + cv.TermCriteria_MAX_ITER, maxCount, epsilon);
        const flags = cv.KMEANS_PP_CENTERS;

        // Create samples
        const samples = new cv.Mat(resized.rows * resized.cols, 3, cv.CV_32F);
        for(let y = 0; y < resized.rows; y += 1) {
            for(let x = 0; x < resized.cols; x += 1) {
                const idx = y * resized.cols + x;
                for(let z = 0; z < 3; z += 1) {                    
                    samples.floatPtr(idx)[z] = resized.data[idx * 4 + z];
                }
            }
        }

        // K-Means method
        let startDate = new Date();
        cv.kmeans(samples, k, labels, criteria, attempts, flags, centers);
        console.log('kmeans:', new Date() - startDate, 'ms');

        // Convert Float to UInt8
        const floatToUint8 = x => Math.min(Math.max(Math.round(x), 0), 255);
        const ui8Centers = new Uint8Array(k * 3);
        for(let c = 0; c < k; c += 1) {
            for(let z = 0; z < 3; z += 1) {
                ui8Centers[c * 3 + z] = floatToUint8(centers.floatAt(c, z));
            }
        }        

        // Create color map
        const mem = 2 ** bitDepth;
        const quant = (mem - 1) / (256 - 1);
        const digit = Math.ceil(Math.log10(mem - 1));
        const colorMap = {};
        for(let y = 0; y < resized.rows; y += 1) {
            for(let x = 0; x < resized.cols; x += 1) {
                const p = (y * resized.cols + x) * 4;
                const key = createColorKey(resized.data, p);
                if(typeof colorMap[key] === 'undefined') {
                    colorMap[key] = labels.data[p];
                }
            }
        }        
        resized.delete();
        labels.delete();
        centers.delete();

        // Create dst from ui8Centers
        startDate = new Date();
        for(let y = 0; y < dst.rows; y += 1) {
            for(let x = 0; x < dst.cols; x += 1) {
                const p = (y * dst.cols + x) * 4;
                const key = createColorKey(src.data, p);
                // Find nearest color
                if(typeof colorMap[key] === 'undefined') {
                    let [minDist2, minC] = [Number.MAX_VALUE, -1];
                    for(let c = 0; c < k; c += 1) {
                        // Compute distance squared in color space
                        let dist2 = 0;
                        for(let z = 0; z < 3; z += 1) {
                            dist2 += (src.data[p + z] - ui8Centers[c * 3 + z]) ** 2;
                        }
                        if(dist2 < minDist2) {
                            minDist2 = dist2;
                            minC = c;
                        }
                    }
                    colorMap[key] = minC;
                }          
                // Set color
                const c = colorMap[key];
                for(let z = 0; z < 3; z += 1) {
                    dst.data[p + z] = ui8Centers[c * 3 + z];
                }
                dst.data[p + 3] = src.data[p + 3];
            }
        }
        console.log('after kmeans:', new Date() - startDate, 'ms');
        return dst;

        /**
         * Create color key
         * @param {Uint8Array} data data 
         * @param {number} p pixel index 
         * @returns {string} color key
         */
        function createColorKey(data, p) {
            let key = '';
            for(let z = 0; z < 3; z += 1) {
                const c = Math.round(data[p + z] * quant); // Quantization
                key += c.toString().padStart(digit, '0');
            }
            return key;     
        }
    }

サンプルプログラム

fastKmeansとkmeansの呼び出し例を載せておきます。

// sample program
const [dsize, interpolation, bitDepth, k, attempts] = [new cv.Size(32, 32), cv.INTER_LINEAR, 4, 5, 2];
const src = cv.imread('src-canvas');
const dst = OpenCVWrapper.fastKmeans(src, dst, dsize, interpolation, bitDepth, k, attempts);

// use kmeans
//dst = OpenCVWrapper.kmeans(src, dst, k, attempts); 
        
// Show dst
cv.imshow('dst-canvas', dst);

// Remove src and dst
src.delete();
dst.delete();