過去、OpenCVやFlashで簡単なステレオ画像処理を試してきましたが (ステレオ画像処理, Flashでステレオビジョン入門)、今回はJavaScriptとCanvas APIで同じものを作ってみます。
Demo: HTML5 Stereo Vision
Source Code: cv/stereo_matching at master from wellflat/jslib – GitHub
ここではKinectのように赤外線センサーはもちろん利用できないので、純粋な画像解析のみで奥行きを計算します。
2枚の画像でステレオマッチングを行い、カメラから対象までの距離を濃淡で表す視差マップ (深度マップや距離画像と呼ばれることもある、CGの視差マッピングとは別物)を生成します。使用するアルゴリズムはこれまで同様にブロックマッチングを、類似度評価にはSAD（Sum of Absolute Differences）をコストとします。
また、Web Workersを使った開発にも慣れておこうと思っていたところなので、今回も動的計画法などは併用せずにナイーブな実装にしてWeb Workersの性能も併せて確かめました。
これまでに書いてきたエントリーではステレオマッチングについての説明をほとんどしていなかったので、今回は簡単に説明しておきます。ステレオマッチングには人間や動物の両眼視のように、三角測量の原理を用いて2つの画像から対応点を求める受動ステレオ法と、2つのカメラの内1つを光を投影する光源に置き換えて対応点を求める能動ステレオ法の大きく分けて2つの手法があります。
ブロックマッチング法
今回は人間や動物と同様に左右2つの目から視差を計算する受動ステレオ法の1つ、ブロックマッチング法について簡単に説明します。このアルゴリズムの原理はとても単純で、一方の画像を小面積の領域に分割し、各領域について他方の画像上で対応する位置を探す手法です。左目と右目で視差のあるステレオペア画像において、左目画像の探索領域と似ている領域を右目画像から探しだし、その領域の位置のずれが視差として求められます。この場合、左目画像に映っている対象物は右目画像内ではその位置よりも左側に映るので、探索開始位置から左側のみを調べれば良いことになります。
各領域について画像全体を走査すると膨大な計算量になってしまうため、エピポーラ線（Epipolar Line）というものが用いられます。以下の図に示すように、一方の画像上の1点に注目したとき、その点を通る視線はもう一方の画像上では1本の直線として映ります。また、その直線上の各点を通る視線は、元の画像上では1本の直線となります。したがって、対応点の対は左右の画像上の一対の直線上に存在するため、その直線上だけ探索を行えばいいことになります。
類似度の評価には、一般的なテンプレートマッチングでも用いられるSAD（Sum of Absolute Differences）という指標を用います。これは探索領域内で左目画像と右目画像の輝度値の差の絶対値を求めて総和を取るもので、この値が小さければ小さいほど似ている領域と判断することができます。
この場合はIが左目画像、Tが右目画像、I(i,j)とT(i,j)はそれぞれ座標(i,j)の画素の輝度値になります。また、他の類似度指標としてはSSD（Sum of Squared Differences）やNCC（Normalized Cross-Correlation）などがあります。
以上がブロックマッチング法の簡単な説明になります。
ソースコードはGitHubに。Canvasを扱う外部ライブラリは使ってなくて、Canvas APIを直接利用したネイティブなJavaScriptコードになっています。
cv/stereo_matching at master from wellflat/jslib – GitHub
ブラウザ毎の処理時間
今回のデモが動作する各ブラウザで処理時間を計測してみました。10回計測した平均値(ms)です。ブロックマッチングのパラメータは探索ウィンドウサイズを7×7px、最大視差を10pxとしました。
(Windows7, Core2 Quad 2.40GHz, L2 Cache 4MB×2, 4GB RAM)
| Firefox 7.01 | 2159 ms |
| Chrome 14.0.835 | 3855 ms |
| Safari 5.0.5 | 4157 ms |
| Opera 11.51 | 3422 ms |
Firefoxがここまで速いのには驚きました。7未満のバージョンだと違った結果になるのでしょうか。Operaは少し昔のバージョンだとたぶん動かないと思いますが、現在の最新バージョンだと特に問題なく動作しました。また、Web Workersの生成およびメッセージパッシング部分のコストについては、今回のような重いCPUバウンドなデモであれば無視していいレベルかと思います。
CanvasとFlash
求めた視差データを使って三次元復元しようかと思ったのですが、CanvasはFlashと違って描画性能はまだまだ弱いので今回は諦めました。座標計算だけなら現在の処理系でも十分な性能は出せると思うのですが、描画までとなると現状はなかなかキビしいかと。逆に描画部分を含まない純粋な演算能力だけであればAVM2を凌ぐ勢いを感じたのでこれからに期待したいと思います。
一方、FlasnランタイムにおけるWeb Workersに相当する機能はFlash Player12, 13あたりで搭載されると思いますが、予定ではshared nothingなworkerのみとのことですので、Flasherのみなさんが共有リソースの泥沼にぞろぞろとハマるのは避けられそうです(参考: Adobe MAX 2011レポート：Flashランタイムの並行処理)。これはENTER_FRAMEでの負荷分散とは全く異なるものなので、Flasherの方々も将来に備えてメッセージパッシングによる並行処理の勘所をJavaScriptで事前に養っておくといいかもしれません。
まとめとして、今回はCanvasとWeb Workersを使ってJavaScriptで少しシビアな画像解析を試してみました。ActionScriptからの移植にも慣れてきたので、今後もいろいろ実験していきたいと思っています。