はじめに
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();