*ステレオマッチング とは 　２枚の画像の各部についてマッチングを行うことで視差を推定する方法です．視差とは，２枚の画像間で対応する部位の位置の差を表します．ステレオマッチングを行い画像上の各部位の視差が推定できれば，三角測量の原理に基づいて距離を算出できます． 　middlebury大学が管理している下記のWebサイトでは，最新のステレオマッチングの結果画像や性能を比較できます． {{small:Middlebury Stereo Evaluation}} {{small:[link:http://vision.middlebury.edu/stereo/eval3/] }}   *視差の推定　基本的な原理 　図１のAの部位について視差を推定したいとします．Aに対応する部位は，片側の画像に対して引いたエピポーラ線上に存在します．まずはその線上の各部位との相関を計算し，その中で最も相関の高い部位をAに対応する部位として算出します． {{small:相関の計算方法は，例えばブロックを定義して各画素の差を計量するSAD (Sum of Absolute Difference) など一般的です．相関値の計算方法は，こちら[link:画像の相関]でいくつか紹介しています．}} [img:bwsp] {{small:図１ ステレオマッチングの基礎}} *サンプルコード (C++) ライブラリ：[link:simplesp] サンプルコード：simplesp/sample/sp/stereo ２枚の画像間の位置姿勢を推定した後，ステレオマッチングを行って視差を推定します． *アルゴリズム 　ここでは，基本的なステレオマッチングの処理の流れを説明します． １．前処理 ：画像の輝度値の正規化など ２．平行化 ：マッチングの効率化のための画像変換 ３．マッチング ：マッチングを行って視差を推定 ４．外れ値除去：左右の整合や微小領域を外れ値として除去 ５．穴埋め ：外れ値として除去した部分や，画面端の視差を推定できない箇所を埋める **１．前処理 　必須の処理ではありませんが，性能を上げるため何かしら画像に前処理を施す場合があります．例えば，OpenCVのステレオマッチングの関数では画像の正規化を行います．具体的には，各部の輝度値の平均値を算出しその値を引きます．周波数的に考えると，直流成分を除去することになります． ***正規化の効果 ２枚の画像はハードウェアのパラメータや視線の角度の違いから，同じ部位を見ていても異なる明るさで観察される場合があります．そうなると，対応する座標で高い相関値が得られないため，マッチングがうまくいかなくなります．画像の正規化を行うことで，その影響を抑えることができます． **２．平行化　レクティフィケーション (rectification) 　厳密に２台のカメラを水平に並べない限り，画像のエピポーラ線は水平になりません．斜めにエピポーラ線が伸びていると，マッチングの計算の効率が落ちます．具体的には，斜めの線に沿って位置を計算する処理や，メモリアクセスのキャッシュミスの影響により，計算時間が増加します．この問題を解決するため，画像に幾何変換を加え，事前にエピポーラ線を平行化した画像を用意します．この処理は，一般的にレクティフィケーションと呼ばれています． [img:ph9t] {{small:図２ 画像の平行化}} 　なお，正確にレクティフィケーションを行うためには，カメラの内部・外部パラメータが必要になります．事前にキャリブレーションボードなどを使って計算しておくか，画像の特徴点を利用して推定することになります． **３．マッチング 　SAD等の画像の相関値を計算する方法を使って，対応する部位の探索を行います．ブロックマッチングと呼ぶ場合も有ります．物体の距離を算出する目的を考えると，片側の画像を基準とした視差を推定するだけで十分に思えますが，後で示す外れ値除去に利用するため２枚の画像を推定する場合が多いようです． [img:ldvz] {{small:図３ 視差画像}} 　なお，ZNCC (Zero-means Normalized Cross-Correlation) などの相関値の計量方法を使って，マッチングの時点で正規化を考慮しする方法も利用されます．ただし，計算の効率化の観点で，前処理として計算しておく場合が多いと思います． **４．外れ値除去 　代表的な方法として，consistency check と呼ばれる方法があります．左右の視差の値を見て視差の値が整合するかをチェックします．この処理により，主にオクルージョンにより間違った視差が出ている部分の視差を除去することができます． [img:fdbk] {{small:図４ 視差画像（外れ値除去）}} 　また，類似する視差の値をラベリングし，その中で小さな領域を外れ値と仮定して除去する方法もあります．撮影する物体が条件に合う場合，例えば細かな形状のない物体の場合は効果的な方法です． **５．穴埋め (hole filling) 　必須の処理ではありませんが，外れ値として除去した部分や，画面端の視差を推定できない箇所を埋めます．基本的には，視差の小さい側，つまりは背景側の視差の値を引っ張ってくることで穴埋めを行います． *ステレオマッチングの改良 ステレオマッチングの性能を上げる方法をいくつか紹介します． **マッチングの最適化 マッチングは画像上の模様を手掛かりに相関値を計算します．そのため，模様の少ない部位の対応はうまく計算できない場合があります．そこで，物体の連続性を仮定した全体最適化の方法によって，模様の少ない部位についても安定的に視差を計算する手法が提案されています． [1]の文献では，マッチングの基礎的な考え方や，[link:確率伝搬法](Belief Propagation :BP)を利用した最適化の基礎が解説されています．確率伝搬法は２次元の最適化の中では高速で性能も高いため，ステレオマッチングの最適化では良く利用されます． [img:yknc] {{small:図５ BPの最適化 出典[1]}} {{small:[1]J.Sun, N.Zheng, H.Shum, "Stereo matching using belief propagation", IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI), 2003}} {{small:[link:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9063&rep=rep1&type=pdf] }} [2]の文献では，１次元最適化を８方向（或いは１６方向）について計算することで，２次元の最適化と同等の性能を高速に計算する方法が解説されています．OpenCVにも実装されていて，実践的な方法として広く利用されているようです． {{small:[2]H.Hirschmuller, "Accurate and efficient stereo processing by semi-global matching and mutual information", Computer Vision and Pattern Recognition(CVPR), 2005}} {{small:[link:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.8897&rep=rep1&type=pdf] }} **マッチングウィンドウ 単純なブロックマッチングは，画像上で注目する部位を平面に仮定しています．そのため複雑な形状の部位では仮定が破綻し，平滑化したような視差になって精度が落ちます．そこで画像の部位ごとに合わせてマッチングウィンドウを調整する方法が提案されています．[3]の文献では，画像上で注目する部位について縦横に適切な幅を設定する計算方法提案されています． [img:v9zt] {{small:図６ マッチングウィンドウの改良 出典[6]}} {{small:[3]K.Zhang, J.Lu, G.Lafruit. "Cross-based local stereo matching using orthogonal integral images", IEEE Transactions on Circuits and Systems for Video Technology, 2009}} **PatchMatch 単純なブロックマッチングは，画像上で注目する部位がカメラに対して正対(fronto-parallel)した条件を考えています．つまり法線方向は考えていません．法線（２パラメータ）を考える場合，視差と合わせて３パラメータの探索になるため，広範囲の探索になるのですが，[4]の文献では，[link:PatchMatch]の技術を利用したランダム探索を用いることで効率化し，法線も考慮した精度の高い視差を算出する方法が提案されています．最近のアルゴリズムはこの技術をベースにした方法が多く，非常に重要なアイデアと言えます． [youtube:36TkuvwlfR4] {{small:[4]M.Bleyer, C.Rhemann, C.Rother, "PatchMatch Stereo - Stereo Matching with Slanted Support Windows", The British Machine Vision Conference (BMVC), 2011}} {{small:[link:http://www.bmva.org/bmvc/2011/proceedings/paper14/paper14.pdf] }} **画像の領域分割 [link:superpixels]などの方法で画像を領域分割し，効率的な視差の計算を行う方法が提案されています．[5]の文献では，メッシュに分割し，その頂点に注目したマッチングを行います． [img:tcl9] {{small:図7 super-pixelsの利用 出典[5]}} {{small:[5]C.Zhang, Z.Li, Y.Cheng, H.Chao, Y.Rui, "MeshStereo: A Global Stereo Model with Mesh Alignment Regularization for View Interpolation", International Conference on Computer Vision (ICCV), 2015}} {{small:[link:https://pdfs.semanticscholar.org/4566/14ba6a75d47db85cf85a997b14ec31c2b28e.pdf] }} **バイナリ化 各部の特徴をバイナリ化することで，マッチングを高速に方法が提案されています[6]． {{small:[6]K.Zhang, J.Li, Y.Li, W.Hu, L.Sun, S.Yang, "Binary Stereo Matching", International Conference on Pattern Recognition (ICPR), 2012}} {{small:[link:https://arxiv.org/pdf/1402.2020.pdf] }} **Deep Learning & CNN 最近では，Deep LearningやCNNの技術を使った様々な試みが検討されています．例えば，[7]の文献では，単純なＳＡＤ等の相関値の計算ではなく，CNNを利用した相関値の計算方法により，性能を上げる方法が提案されています． [img:bgv7] {{small:図8 CNNに基づく相関値の計算 出典[7]}} {{small:[7]J.Žbontar, Y.LeCun, "Stereo Matching by Training a Convolutional Neural Network to Compare Image Patches", Computer Vision and Pattern Recognition(CVPR), 2015}} {{small:[link:https://arxiv.org/abs/1510.05970] }}