Oriented Bounding Box using Covariance Matrix

まとまった時間があったので、共分散行列(Covariance Matrix)を用いた主成分分析(Principal Component Analysis)にて生成した有向バウンディングボックスのデモをGoogle Gadgetsを用いて書いてみました(有向バウンディングボックスについては、過去のエントリにて簡単に解説をしています)。Mac OS XSafariChromeおよびFirefoxで動作確認しています。Canvasをサポートしたブラウザが必要です。

画像部分にて左右にドラッグすると、ドラッグの水平位置に対応したサンプルを生成し、バウンディングボックスを計算します。塗りつぶしているベクトルは共分散行列から算出した第1主成分ベクトル、塗りつぶしていないベクトルは第2主成分ベクトルで、各々共分散行列から算出した固有ベクトルとなります。また、ベクトルの原点は後に挙げるそれぞれの手法にて算出した重心位置としています。サンプル数は、Number of pointsで設定可能です。点群の分布に偏りを持たせたい場合は、Biased samplingを有効とします。


二次元の点群から共分散行列を生成するには、以下に示す代表的な3つの方法があります。

  • 直接点群から算出する
  • 凸包を計算し、その頂点間の線分を元に算出する
  • 凸包を計算し、その頂点間の線分の端点と凸包に含まれるある点からなる三角形を元に算出する

よく書籍で紹介されているのは、直接点群から算出する方法でしょう。これは、ガジェットのOBB calculated from pointsチェックボックスに対応させました。

この方法は、点群が均等に分布している場合にはなかなか良い結果を出してくれます。書籍で紹介される際はそのような点群を例に挙げていることが多く学習の一助とはなるのですが、実際の問題、点群が均等に分布していない問題を扱った場合に堅牢な結果を得られず、困惑すると思います。この挙動をガジェットで体感するには、点群の総数を32程度から減らし続けてみると分かりやすいです。確率的に均等に分布させた点群であったとしても、実際の分布としての偏りが増えて行くため、期待と大きく外れた結果となって行きます。

対して、線分や三角形を用いる方法は、OBB calculated from line segmentsとtrianglesに対応させました。

これらの方法の根本的なアイデアは同じで、線分もしくは三角形の重心位置を利用して共分散行列を生成しよう、というものです。二次元上の点群に対しては凸包の線分から共分散行列を生成すると良い品質の有向バウンディングボックスが得やすいことが一般的に知られています。

OBB calculated from line segments、trianglesを有効にして様々な条件で試してみると、何れかの手法で生成したものが暴れる場合もありますが、ほとんどの場合で同じような品質を保った有向バウンディングボックスを生成することが分かります。

また、OBB calculated from verticesは凸包の頂点群から共分散行列を生成するものです。これはあまり良い結果を生みません。凸包の頂点数は大抵元の頂点数よりも少なく、また、均等に分布することはないからです。

まとめ

普段はEmacs Museを用いて、LaTeXやPostScriptによる図表をガリガリ書き込んでいます。何らかのデータをまとめる場合には、PythonからPostScriptを生成し、そのPostScriptを貼り付けています。しかし、様々なサンプルを検証する段階では、このようにJavaScriptCanvasにて実装するのもなかなか有効ですね。

と言っても、個人的にインタラクティブな可視はあまり好みではありません。むしろ静的なものの方が好みです。プログラミングCのような名著の中の名著では、そのような制限の中万人を納得させる可視を繰り広げています。それは本当に考え込んで作られており、珠玉なのです。及ばずとも少しずつ近づいていきたいな、と常に考えています。今回の共分散行列を使った有向バウンディングボックスの生成に関しても、今回の結果から得た結果を使って、うまく画像に落とし込んで行けたらなと思います。

Prototype.jsでまじめに計算幾何に関係する実装を行なったのは初めてでしたが、Pythonと比べると一貫性がなく、時間がかかりました。

Canvasを用いてまともに実装を行なおうと思ったのも今回が初めてでした。CanvasはPostScriptのサブセットのような仕様だと思っていたのですが、今回の取り組みでPostScriptの足下にも及ばず、また、凶悪な仕様であることを認識しました。

少なくとも、コンテキストに現在設定されている行列が取れないのはおかしいと思います。