ひさしぶりのブログ。
ブラウザの処理能力の進化を測るには個人的に画像処理が一番わかりやすいです。
今回は画像内にあるオブジェクトのコーナー(corner:頂点, エッジの交点)を検出をしてみます。コーナー検出に用いられる特徴点検出法はいくつか提案されていますが、今回はブラウザ上で実行することを考慮し計算量とメモリ使用量の観点からHarrisオペレータを採用します。
コーナー検出法についてはWikipediaを参考に。
コーナー検出法 – Wikipedia
Harrisオペレータは微分幾何学に基づくアプローチを採っています。難しいことは置いといて簡単に説明すると、「一次微分値(差分)が一方向に大きければエッジ、多方向に大きければコーナーである」という知識に基づいて計算されます。特徴”点”を求めるには通常は二次微分が必要ですが、Harrisオペレータではガウシアン平滑化で以て二次微分計算を代用しています。
Harrisオペレータによる特徴量は以下の式で求めます(特徴検出 – opencv.jpより画像引用)。
うれしいことに固有値分解をわざわざ計算せずに済むわけです。また、kの値は賢い大人達の経験的に0.04~0.15が良いとされているようです。
また、実装上ではPrewittフィルタとガウシアンフィルタを組み合わせて素朴に実装している例はよく見かけますが、OpenCVの実装(cv::cornerHarris)ではSobelフィルタとボックスフィルタ(非正規化)を組み合わせているようです。今回作ったデモではOpenCVの方の実装アルゴリズムをJavaScriptに移植しました。ちなみにこれらの計算はコンピュータでは並列化しやすく、実際にOpenCVでは可能であればGPUやSSEの力を借りて計算する実装になっています。ActionScriptに移植するならStage3Dを上手く使えないでしょうか?(無知)
以下、デモを載せます。さすがにスマートフォン端末だと厳しいかと思いますのでPCから。一応、AndroidのMobile Safariでは動作確認していますがやはり重いです。
Demo: Corner Detection using Harris Operator
(IE9.0, Firefox15.0, Chrome21.0, Safari6.0, Opera12.0で動作確認済み)
ソースコードはGitHubに置きましたのでもし興味があれば。Harris検出器本体のソースコードは外部ライブラリ等を用いていません。
cv/cornerdetect.js at master from wellflat/jslib – GitHub
使い方は以下の通り。
|
1 2 3 4 5 6 7 8 9 10 |
// パラメータをObjectで渡す // blockSize: 近傍領域の大きさ、計算量の都合で3×3または5×5のみサポート // k: Harris検出器のkパラメータ、 0.04~0.15を推奨 // qualityLevel: 内部の閾値処理で用いる、一定値以下の特徴点は削除される var params = { blockSize: 3, k: 0.04, qualityLevel: 0.01 }; // 第一引数には対象のImageDataオブジェクトを渡す // 第二引数は現在 CornerDetector.HARRIS のみサポート // 第三引数にはパラメータオブジェクトを渡す // 戻り値は特徴量が格納された配列、値が0以上の位置が特徴点(コーナー) var corners = CornerDetector.detect(img, CornerDetector.HARRIS, params); |
処理速度とクロスブラウザ対応
以前のJavaScriptで2D-FFTによるハイパス/ローパスフィルタでも書きましたが、2012/09現在だと画像処理関連のクロスブラウザ対応についてはOperaが意外とネックになったりします(飽和演算とか)。IEはver9.0なら特別な対応を行わなくても動作することが多いなぁという印象。また、処理速度についてはアルゴリズムによってFirefoxとChromeが勝ったり負けたりでなかなか面白いです。Operaが少し遅れを取るようで、IE9は桁違いに遅いです。Safariは知りません。
また、Web Workersの利用判断についてですが、ブラウザの処理能力は日進月歩なのであまり経験則に頼らない方がいいと思います。Web Workersの利用有無で柔軟に処理を切り替えられる綺麗な実装パターンとしてはどういう方法が良いんでしょうかね。
Typed Array(型付き配列)の性能は?
Typed Arrayをサポートしているブラウザでは積極的に Float32Array を利用する実装にしているのですが、速くなるブラウザもあれば遅くなるブラウザもあってよくわからないです。。ばらつきが大きくなるのは避けたい所なので素直にArrayを使った方が現在はまだ良い気がします。各ブラウザのTyped Arrayの実装を見比べたいところです。
その他の手法
最初に書いたようにコーナー検出に利用できる特徴量はこれまでいくつかの手法が提案されてきましたが、最近ではFAST特徴がよく用いられています。パテントフリーで素敵なORB(Oriented FAST and Rotated BRIEF)特徴の構成要素としてもFASTが利用されています。実は最初、HarrisではなくFAST特徴によるコーナー検出をJSで試そうとしたのですが、本家のソースコード(FAST Corner Detection — Edward Rosten)を見て絶望感に包まれました。。アレをスクリプト言語で一から移植するには日曜プログラマの僕には困難な気がします。。しかもJSの場合だとスクリプトの読み込みにものすごい時間がかかるのではないでしょうか。
日曜の作業時間内で簡単に試せる手法を探しつつ、HTML5とJavaScriptの勉強も併せて進めていきたいなと思います。