ボロノイ図とクラスタリング

ここ数週間にわたり僕を煩わせてきた問題も、一定の決着を見た。
これで心置きなくAP受験勉強に専念・・・したくねぇー。

とりあえず作ったもの。例によってWonderflから。

webカムもっちりボロノイ図 - wonderfl build flash online

これは何なのか。

まず、「ボロノイ図」というものがある。
ものっすごい乱暴な説明をすれば、点と点との中間に線を引いて出来るモザイク模様だ。

ただ、ボロノイ図には統計的な意味合いがないでもない。
「K-Means法」というデータのクラスタリング手法があるのだけれど、
「あるデータ点がどちらのクラスタに分類されるか」という境界はボロノイ図として表現される。
これはボロノイ図の定義とK-Means法の手順を考えれば、当たり前っちゃ当たり前なんだけども。

で、このK-Means法によるクラスタリングを平面画像の(r,g,b,x,y)について行うとどうなるかというと
「色が近くて位置が近接している領域」の判定が出来る。
(各クラスタの境界は5次元ボロノイ立体として表現され、人間の想像力を軽々と超える。)
そしてそのクラスタリングの結果を平面画像として表現したものがまさにボロノイ図となる。

これをカメラ映像に大して行おう、と試みたのが上の小品。
オマケ要素として多角形の角を丸めてしまってはいるが。

K-Means法はとても単純な手法なので、簡単に実装できた。
むしろ数週間悩まされ続けたのがボロノイ図を作図するための「Fortuneのアルゴリズム」の実装だった。
未だに、ほんとうに効率のいい方法で実装出来たのかどうか、自信がない。