1. ステレオマッチング (stereo matching) [概要]
ステレオマッチング (stereo matching)とは，コンピュータビジョンにおける「平行ステレオ」の2カメラ設定における深度推定のためのアルゴリズムである．画像のx軸方向のみの対応点探索を行うことで，推定された「左右画像間の対応点ペア」から，エピポーラ幾何を利用することで，そのペアにする三次元点の座標，および2画像平面からの深度(デプス)を求めるすることができる．
この記事では，ステレオマッチングを行うための，3次元ステレオ幾何理論の基本(2節)と，その古典的な処理アルゴリズムの一般系(3節)，およびその古典的な代表例であった Semi-Global Matching を用てのステレオマッチング(概要のみ)を紹介する(4節)．
「パッシブなステレオビジョン（Stereo Vision）」とは，隣り合って平行配置した2台のカメラで同一シーンを撮影し，画像間マッチングおよびステレオ幾何により3次元復元を行うことを指す．2画像間での3D空間上における同一点同士の対応づけを，画像全体において最適化（ステレオマッチング）したのち，その対応づけ結果である視差（Disparity）をもとに，三角測量によるカメラ間の幾何関係を用いて各点の3D座標を復元を行う．投影光の情報も活用する「アクティブステレオビジョン」とは違い，（パッシブな） ステレオビジョンでは，シーンから受動的に受け取った画像情報しか用いない．
伝統的な推定手法にのみ焦点を当てて読みやすく簡潔な記事にする目的で，この記事ではステレオマッチングの古典手法ではファーストチョイスであった「Semi-global matching （SGM） [Hirschmuller, 2008]」（2.3節） の紹介を，最終目的とする記事構成とした（ただし，SGM自体も概要紹介にとどめている）．したがって，SGM以外の代表的なステレオマッチング手法であった「Graph Cutを用いたGlobal手法」や「フィルタリングを用いたLocalパッチ手法」などについては，この記事では述べない．
1.1 記事の構成
以降は，2節において，以下の3パートに区切って，平行ステレオシステムを用いた２台のカメラによるステレオマッチングによる深度推定の概要を紹介する：
- 2.1節：2画像間の対応点ペアが求まったのちの３次元点への投影（ステレオ幾何）
- 2.2節：ステレオマッチングによる深度推定の解き方の一般形
- 2.3節：Semi-Global Matching法を用いたステレオマッチング．
2. 平行ステレオ
「平行ステレオ」は『2カメラに同じ縦横の画素数のものを用いて平行に同じ高さで少しだけ左右に離して固定配置し，エピポーラ線のy座標(高さ)を2カメラ間で一致させておく』カメラ配置で行う．ステレオカメラでは2つのカメラの撮像平面が，3次元空間上で同一平面上に(すわなち平行に)配置されていることを仮定する．
ステレオビジョンでは，3次元空間上で2カメラの光学中心間を結んだ直線を基線(baseline)と呼ぶ，各種のステレオカメラでは10cm~30cm程度の基線長で２カメラ間を配置することが多い．
ステレオマッチングの結果として各座標の視差が推定されたのちは，ステレオカメラ特有の画像座標と3次元座標の変換式を用いて(2.1節)，求まった視差とカメラの内部パラメータを元に，各対応点ペアをすぐに３次元点に投影することができる．
2.1 対応した座標ペアの3次元座標への変換
この節では，SGMなどのステレオマッチング処理の結果，２カメラ間での対応点ペアが推定された後に，それらの画像上の点がどのようにして3次元座標に変換できるかについて述べる．
まず，ステレオマッチングの結果，左カメラ画像上の点$\mathit{\bm{p_L}} = (u_L, v_L)$が，右カメラ画像上の$\mathit{\bm{p_R}} = (u_R, v_R)$と対応づいており，その２点が共通して指し示す３次元点座標が$\mathit{\bm{P}} = (X, Y, Z)$であるとする．ここで，$u_R < u_L$および$v_L = v_R$を満たす．
これらの３点と2カメラの画像平面の３次元空間上における位置関係を，2点$\mathit{\bm{p_L}}$，$\mathit{\bm{p_R}}$を通る水平断面上でみると，以下の図1のようになる(※ステレオ設定の場合，この断面はエピポーラ平面に相当する)：
この空間関係を元に考えると，マッチング結果の視差$d = p_L – p_R$，焦点距離$f$および基線長$b$を用いて(※これらの$f$と$b$はステレオカメラキャリブレーションであらかじめ取得済み)，$\mathit{\bm{P}}$の座標は以下の関係式により求まる：
\begin{equation}X = \frac{b \cdot u_L}{d}, Y = \frac{b \cdot v_L}{d}, Z = \frac{b \cdot f}{\sigma d}\tag{2.1}\end{equation}
これにより，ステレオマッチング処理で各座標の視差さえ推定し終われば，実質3次元座標まで推定できたも同然であることがわかったと思う．
2.2 一般的な Stereo デプス推定
離散的な視差ラベル$l$のパラメータ空間において，Markov Random Field (MRF)による最適化を行うことが，画像のステレオマッチングで (Global手法による)一般的な解法である．
まずステレオ全般の一般的な定式化を行う．画像中の全画素 $p \in \Omega$ において，視差のラベル $l_p \in \mathcal{L}$ (最小視差 $d_{min}$ から最大視差 $d_{max}$ までの範囲）を，「画像全体で構成したMRFの最適化」により推定したい．
そこで，「(画素ごとの)データ項 = ローカル項」と「(隣接画素間の) 平滑化項 = グローバル項」の和として，以下のようなMRFのエネルギー関数を用意し，この $E(l)$ の最小化を行うことで，各画素のラベル $l$ 全体をいっぺんに最適化する：
\[
E(l) = \sum_{p \in \Omega} \left[ E_{data}(p, l_p) +\sum_{q \in N_{p}} E_{smooth}(l_p,l_q) \right]
\tag{2.2}
\]
式(2.2)の3つの項は，それぞれ以下のエネルギーを示している：
- $E(l)$：各画素をノードとし，隣接画素間をエッジで結んだMRFで最小化したいエネルギー（以下の２つのコストの和）．
- $E_{data}(p, l_p)$：画素ごとのコスト関数の和(ローカルなコスト項)．左右画像の2パッチ間で，$p$と$p+l_p$周辺のパッチが類似しているほど，値が低くなるコスト関数を用意する．
- $E_{smooth}(l_p,l_q)$：$p$周辺の4近傍の画素 $q \in N_{p}$ との2画素間でパッチ類似度を計算した，(グローバルな) 平滑化制約項．8近傍で計算することもある．
MRFのグラフ全体を，式(2.2)の $E(l)$ を用いて，全画素値のデプス値に対するExactなグローバル最適化を行ってしまうと，かなりの計算時間がかかってしまう．
したがって，SGM(Semi-Global Matching)法は，コスト計算を行う画素を限定してコストを近似する，半全域(Semi-global)最適化で代替し，高速に視差マップを推定する (2.3節)．
ステレオカメラによる3D点推定の，一般的な処理は以下の手順で行われる：
- [Cost 計算]：
- 各y座標において，左右のパッチ領域を用いてマッチングコスト(ある視差の値を仮定した時のパッチ同士の類似度)を，右画像の視差1から視差$d_{max}$の各画素において計算する．
- 代表的なマッチングコストには「Census」がよく用いられる．
- これにより，各候補の視差において計算したマッチングコストを格納したコストボリューム(Cost Volume)と呼ばれる $W \times H \times (d_{max} +1)$ 次元の3階のテンソルが手に入る
- 3Dコストボリュームは，『Disparity Space Image （DSI）』と呼ばれることも多い．
- [Cost Aggregation（ステレオマッチング処理）]：
- 手順1で算出したコストボリュームを元に画像全体のエネルギー関数を用いて，ステレオマッチング処理を行い，全体的最適化された「各画素の視差」を推定する．
- [三次元測量（triangulation）による3D投影]：
- 左画像の各画素$\bm{p}_{L}$において，推定したその点の視差と焦点距離$f$を用いて，3次元座標点$(X,Y,Z)$に変換する．
以上が古典的な平行ステレオの処理手順である．
2.2.1 平行ステレオの利点
ここで，非並行ステレオと比較した際の，平行ステレオ設定の主な利点を述べておく：
- よって，元の撮影された2枚の画像から，すぐにステレオマッチングによる視差推定ができる．
- これは，Rectificationによる画像変換によって，平行カメラ設定の画像に変形させずとも，最初から左右画像が平行カメラ位置の画像となっているからである．
- 三角化 (Triangulation) も行いやすい(並行)2カメラ配置であるので，視差マップを求めると，それで3次元座標も簡潔に求められる．
- 平行ハイチで，2つのカメラ中心と目標点の3点間の幾何的関係が単純で済む．よって，視差 (disparity) と基線長(baseline)のあいだの比例関係式のみで，すぐ3次元座標に変換できる．
2.2.2 ステレオカメラキャリブレーション
エピポーラ幾何でチェッカーボードを用いた一台のカメラに対して行うカメラキャリブレーションとは違い，2台のカメラ間の相対的位置姿勢の対応を求めるステレオカメラキャリブレーションが，（パッシブでもアクティブでも）ステレオビジョンにおいては必要となる．
従って，手順1~3による視差推定と3D投影を行う前に，先にステレオカメラ対に対してステレオキャリブレーションを行い，必要な平行ステレオ計算用のパラメータを事前に求めておく（この記事ではステレオキャリブレーションの手順については割愛する）．
2.3 SGM (Semi-Global Matching) の処理手順と利点
この節ではSemi-Global Matching [Hirschmuller et al., 2008]のアルゴリズムを，その概要だけ紹介する(詳細な手順までは解説しない)．
SGMは，すでに述べたように『準グローバル最適化』手法である．各注目点において，45度ずつに分けた8方向「パス」の直線上に存在する点のみからコスト値をスキャンして集約して「スキャンライン上の最適化」を行う．その(中間的にスキャンパスのみで最適化をおこなった)結果のコストを，単純な式で周囲の画素のコストに伝搬させていくことで全体最適化を解くことで，全ての画素の$l$の値を順に最適化していく準最適化アルゴリズムである．
各繰り返し(各画素)では，周辺8方向スキャンパス上にある座標のコストのみ計算 + 収集を行う．そのおかげで，前述の「一般系 (2.2節)」のように，繰り返し中に全画素分のコストを計算したエネルギー式(2.1) を毎回計算する手間を避けられる点で，計算効率が高い．
各1方向パスの直線上では，平滑化項もペナルティとして加えながら動的計画法により，視差$d$の最適パスを求める．8方向の各パスは，動的計画法により，(周辺での推定結果を頼りに) 視差を一画素ずつ推定して確定させていく．このおかげで，グローバル最適化をもちいて全画素のコスト値を計算すること無しに，周辺8方向パス上のみからの必要最低限のコスト集約で計算が済むので，低計算コストで済む利点が出る．
SGMは，そのように計算効率優先であるが，その割にはグローバル最適化と同等もしくは少し劣る程度の精度で視差マップを取得できる利点がある．加えて，アルゴリズムの単純さから，実装が容易であることも手伝って，産業界でもSGMが広く用いられるようになった （※ ただし，本記事を執筆した2019年現在では，ディープニューラルネットワークを用いた『学習ベースのステレオ手法』も，ロボット向けに積極的な応用が始まりつつある．
本記事ではSemi-Globalな手法であるSGMについてのみに注目して紹介したが，古典的なステレオマッチング手法には，他にも以下のような，2手法も存在する：
- Local 手法: エッジ-awareな局所フィルタにより，ローカル窓内のみでコストを集約して，フィルタリングする推定手法 (例：[Cost Volume Filtering, CVPR2012] など)．
- Global 手法：Belief Propagationなどで，全画素のコストを全体最適化 (例；[PatchMatch BP, IJCV2013] など)．
1.は，Localのコストのみを用いた空間フィルタリングベースの手法であり，2.は， 速度重視のSGMと違い，きちんとグラフ全体を一気にGlobal 最適化する手法である (詳しくは [Pears et al., 2012] などを参照)：
3. まとめ
この記事では，2台のカメラを平行に配置するステレオカメラ画像対から，3D深度復元を行うステレオマッチングについて大まかに示した．
まずステレオマッチングの一般形を説明したのち，代表的な手法である Semi-global matchingの概要を紹介した．
参考書籍
- ディジタル画像処理 [改訂第二版], ディジタル画像処理編集委員会, 2020.
- Concise Computer Vision: An Introduction into Theory and Algorithms (Undergraduate Topics in Computer Science) , Reinhard Klette, 2014.
References
- [Kletter, 2014] R. Kletter. Concise Computer Vision: An Introduction into Theory and Algorithms. 1st edition, Springer, 2014.
- [Pears et al., 2012] N. Pears, Y. Liu, and P. Bunting. 3D imaging, analysis and applications. Springer, 2012.
- [Hirschmuller, 2008] H. Hirschmuller. Stereo processing by semiglobal matching and mutual information. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 30(2):328–341, feb 2008．
- デジタル画像処理[改訂新版], 画像情報教育振興協会, 2015.