相関ステレオマッチングの高速化アルゴリズム

今、研究で２枚の画像の視差を求めるために相関ステレオマッチングを使っています。
せっかくなので相関ステレオマッチングの高速化について書きます。

まず、相関ステレオマッチングはグラフカットステレオマッチングの方法に比べるとずいぶん高速なアルゴリズムです。
しかし、普通に１画素ずつブロックを比較していくような方法をとると、リアルタイム処理が必要ないとしても、画像の解像度がある程度大きくなってくると処理の遅さを感じます。

効率の良いプログラム実験や、快適なソフトウェアを作るためには高速化はどうしても必要なのです。

では、どのようにすれば高速化は実現できるのでしょうか。

答えは冗長な計算を省くことです。

同じ計算を何度もしないで、昔の計算結果を再利用できれば、それだけでずいぶん高速化することができます。
具体的には、一番最初にすべての画素の相関値を計算して保存して相関値マップのようなものを作っておけば良いのです。

例えば、ある探索距離で次のように各画素の相関値が求まったとします。

それをに左側からx軸の和をとりながら記録してゆくと次のようになります。

このマップから何を求められるかおわかりでしょうか。
上からn番目、左からm番目の画素をp[n][m]、その画素に記録された値をv[n][m]と表すとすると、次の式は何を求めているでしょうか。

s = (v[1][4] - v[1][1]) + (v[2][4] - v[2][1]) + (v[3][4] - v[3][1])

そうです、p[2][3]の3x3近傍の相関値の総和を求めているのです。
和の差分をとることでその間の相関値の和をとることができるので、この方法を使えば冗長した計算を省くことができるようになるのです。

さて、まだよくわからない人のためにもう一つやってみます。
p[3][4]の5x5近傍の相関値の総和を求めてみましょう。

ということで、p[3][4]の5x5近傍の総和は66となります。
本当にそうなっているのか確かめてみましょう。最初の相関値の表から5x5近傍を抜き出して、和を求めてみます。

となり、正しい答えが求められていることがわかります。
これを探索範囲のすべての距離に対して行い、その中でもっとも相関の高い探索距離をマッチングした距離として記録します。
このアルゴリズムを使えば、ブロックサイズにほとんど影響を受けない高速な相関ステレオマッチングプログラムを作成することができます。

今、示した例ではｘ軸のみの和の冗長性をなくしていますが、y軸にも適用することができるので、x軸の和のマップからさらにy軸の和をy軸方向にとっていくようなマップを作ればもっと高速化することができます。

さらに、探索範囲の距離を一つ一つ順番に調べるのではなく、階層化して調べていけば、余計な計算をしなくても済むのでもっと高速化することが可能です。

相関マッチングの操作できるパラメータは少なく、ブロックサイズと探索範囲くらいです。この両方において無駄な計算を省くことが高速化の鍵となります。

私の場合は、この他にマッチングの精度を向上させるために、ハイパスフィルタを通したエッジ画像を利用して探索画素周辺の特長をつかめる適正なブロックサイズを計算するようにプログラムを改善してあります。
さらに、求められた深度画像のヒストグラムの両端に局所的に高い深度が入っていた場合は、それをオクルージョンとみなして、近傍画素から補間するようにしてあります。

なんだか、相関マッチングプログラムにいろんな改造をしていると、RPGゲームでキャラクタに新しい武器を装備させてパワーアップさせているような感覚と同じような感覚になって楽しくなります。

次は精度の高いオクルージョンの計算を実装させてみたいですね。
うまくいったら、ここに載せますのでどうぞご期待下さい。


追記 -----------------------------
ステレオマッチング実装において参考にしたサイト
http://vision.middlebury.edu/stereo/

関連記事

顕著性マップ(Saliency Map)でウンダムの目立ち度を計る

ヒストグラムから山を抽出して画像領域分割

位相限定相関法を用いたステレオマッチング

C++ 線形(Bilinear)補間で画像を拡大するサンプル

C++ 最近傍探索法による画像拡大縮小サンプル

Java 画像データ用クラス

POCステレオマッチング　普通の顔と光を投影した顔の深度計算結果の比較

可変ダイナミックレンジによる独自画像圧縮形式

Maya Image-based Modeling用プラグインを開発中