JavaScriptで画像のクラスタリングによるドット絵風加工

前回のJavaScriptでPoisson Image Editingによる滑らかな画像合成に引き続き、HTML5 Canvasを使ったJavaScriptによる画像処理の一例を紹介します。

今回は画像の画素値に対するクラスタリング(分類)を画像加工用途に応用します。クラスタリングには各画素のRGB値を特徴ベクトル(次元数3)としてk-means法と呼ばれる手法を使って行います(実装上はk-means法の初期値選択アルゴリズムを改良したk-means++法を利用)。以下のサイトでOpenCVを利用した実装例が紹介されています。

k-meansクラスタリングによる画像分割，減色 – opencv.jp

上記サイト内でも言及されているように、k-means法による画像の領域分割や減色処理はあまり良い結果が得られないことが知られています。なのでここでは画像効果のひとつとしてドット絵加工用途に応用してみます。手順は以下のようにクラスタリングの前処理として一手間加えるだけです。

画像を縦横に等分割して、各領域の平均色を求める
手順1で求めた平均色を特徴ベクトルとしたk-means法によるクラスタリングを行う
手順2で求めた各クラスタの中心値を各領域の画素値に置き換える

分割した領域の平均色で画素値を置き換えるだけだといわゆるモザイク処理された画像になりますが、そのモザイク画像の各画素値に対してクラスタリングを行うことでドット絵加工したような画像を作ることができます。

さらに4色にまで減らすと。

Demo: Pixel Clustering using k-means++
(IE10.0, Firefox23.0, Chrome28.0, Safari6.0で動作確認済)

また、このデモでは前処理の領域分割をせずに減色処理のみを試すことができます。

(16777216色を16色に減色)

案の定ベンチマーク用デモになってしまいましたのでIEとChromeで処理時間を測ってみました。

* PC: Core i5-2500K 3.30GHz, 8GB RAM, Windows7
* 標本数: 160000, k: 8

k-means++法のようなアルゴリズムに対して平均処理時間を代表値にするのは良くありませんので、ここでは処理時間の確率分布を載せておきます。サンプルはそれぞれ100回分で少ないですが、対数正規分布のような形はぼんやり見えてますね。最尤推定でPDF(確率密度関数)もプロットしてみました。サンプル数を増やせばもっと滑らかにフィッティングするかと思います。

コードはGithubにも置いてあります。もちろん自由に利用していただいて構いません。ただし、今回実装したk-means++法では色空間のクラスタリングを対象にしたため1~3次元ベクトルしか扱えません。任意の高次元ベクトルに適用するには少し修正する必要があるので注意してください。

cv/pixel_clustering/pixelcluster.js at master from wellflat/javascript-labs – GitHub

以下のように使います。初期値選択アルゴリズムはk-means++とランダム選択のどちらかを指定できるようになっています。

var ctx = document.querySelector('#Canvas').getContext('2d');
// 画像ファイル名、画像読み込み完了後のコールバック関数を指定
PixelCluster.load(srcImgName, function() {
  // k-means法による特徴ベクトルのクラスタリング(減色処理)
  // 画像分割数、色数、初期値選択アルゴリズム、処理完了後のコールバック関数を指定
  var division = 100;
  var k = 4;
  var method = PixelCluster.KMEANS_PP;  // KMEANS_PP or KMEANS_RANDOM
  PixelCluster.perform(division, k, method, function(result) {
    // 処理結果をCanvasにレンダリング
    PixelCluster.render(ctx, division, result);
  });
});

var ctx = document.querySelector('#Canvas').getContext('2d');

// 画像ファイル名、画像読み込み完了後のコールバック関数を指定

PixelCluster.load(srcImgName, function() {

// k-means法による特徴ベクトルのクラスタリング(減色処理)

// 画像分割数、色数、初期値選択アルゴリズム、処理完了後のコールバック関数を指定

var division = 100;

var k = 4;

var method = PixelCluster.KMEANS_PP; // KMEANS_PP or KMEANS_RANDOM

PixelCluster.perform(division, k, method, function(result) {

// 処理結果をCanvasにレンダリング

PixelCluster.render(ctx, division, result);

});

k-means法の画像処理分野における応用例

k-means法はアルゴリズムが単純なため、今回紹介した減色処理用途以外にも様々な応用例があります。特に物体認識分野では特徴ベクトルのクラスタリングに利用されたりしています。そのクラスタリングによって得られた各クラスタの中心値はVisual Wordsと呼ばれ、画像はそのVisual Wordsのヒストグラムで表現することができます(Bag-of-Features表現)。概要は以下のサイトなどが参考になります。

Visual Wordsを用いた類似画像検索

画像のBag-of-Features(BoF)表現は自然言語処理におけるBag-of-Words(BoW)の考え方を画像処理に応用したものになります。このブログでも2年前にBoWを使ったナイーブベイズによる文書の分類をActionScriptで実装したことがありますので参考までに。

AS3でNaive Bayesによる文書分類

今回はクラスタリングアルゴリズムであるk-means法の画像処理への応用例を紹介しました。これからもWebブラウザで実現できることをいろいろ試してみたいと思います。

JavaScriptで画像のクラスタリングによるドット絵風加工

k-means法の画像処理分野における応用例

あわせて読む:

コメントを残す