Semi-Global Matching(SGM)は，精度と処理時間のバランスに優れたステレオマッチングの手法として広く用いられています．本稿では，SGMのコスト最小化の概念をセグメンテーションに応用した，Segmentation SGMについて述べます．私たちはSegmentation SGMを組み込みGPU向けに実装・最適化し，Jetson TX2上で40~60FPSの性能を達成しています．

シーン中の障害物の認識およびその距離情報は，自動運転システムやロボティクスなど様々な分野で重要な役割を果たします．ステレオビジョンのシステムでは，左右の画像ペアからステレオマッチングによって視差を計算し，各ピクセルの3次元上の距離を推定することができます．ステレオマッチング手法の中でもSemi-Global Matching(SGM)[1]は精度と処理時間のバランスに優れたアルゴリズムとして知られています．私たちは以前，SGMをGPU向けに実装したlibSGMを開発しています．

SGMで得られたピクセルレベルの視差情報は，後段の処理でより抽象的な，物体のレベルに変換する必要があります．Daimler社の研究グループは，ピクセルレベルと物体レベルとの間を埋めるシーンの中間表現としてStixel[2][3]を提案しています．Stixelは図1(右)のように短冊状のセグメントを単位として物体の要素を表現するもので，ピクセルレベルの視差情報よりもコンパクトであり，かつ物体の要素を表現するのに十分というメリットがあります．

本稿で述べるSegmentation SGMは，図1のように視差画像を入力としてStixelを計算するアルゴリズムです．Daimlerの手法[2][3]を基本的なコンセプトにしつつ，SGMのアルゴリズムを応用して物体のセグメンテーションを実現しました．また，私たちはこのアルゴリズムをGPU向けに実装し，リアルタイム処理も可能にしています．

Segmentation SGMの説明の前に，ステレオマッチングにおけるSemi-Global Matching(Stereo SGM)を説明します．

左右の画像ペアが与えられたとき，左画像の各画素に対応する画素を，右画像から探す問題を考えます．左右の画像は平行化(Rectification)済みであり，対応点は左右の画像で同じ行に見つけられるとします．左画像の画素と右画像の画素とが対応するとき，この水平方向の差を視差と呼びます．

Stereo SGMでは，画素と個の視差候補について，対応の妥当性を与えるコスト関数を定義し，コストが最も小さくなるを求めることによって視差を推定します．

コストのベースとなるのが，画素間の類似度を表すマッチングコストです．Stereo SGMでは，計算量とロバスト性の面からCensus特徴量が有力とされています．Census特徴量は注目画素の輝度値と周辺画素の輝度値を比較し，その大小を1/0のビット列で表現したものです．特徴量間の類似度はビット列のハミング距離によって定義されます．

コスト最小化にマッチングコストだけを使用すると，テクスチャレスな領域などを十分に識別できず，誤対応を生みやすい問題があります．より正確な結果を得るため，視差の連続性(空間的に滑らかに変化すること)を制約としてコストに取り入れます．

視差の連続性は上下左右に発生しているため，2次元の制約をかけるのが一般的ですが，SGMではこれを複数の1次元の制約を組み合わせたもので近似します．制約を1次元に限定することで，動的計画法(DP)による効率的な最適化が可能になるというメリットが生まれます．

画素，視差におけるコストをとします．はDPを行う1次元の経路(Path)の方向ベクトルを表します．は典型的には左右上下と対角方向の計8種類あります．

は画像の端からスタートし，方向に沿って漸化式的に計算します．

はマッチングコストを表します．もう一方ので囲まれた項は，視差の連続性の制約を表します．意味合いとしては，前回アクセスした画素と現在の画素の視差の値を比較して，

• 視差の値が同じペナルティなし
  • これは，物体の表面は局所的に奥行きが一定である，という先見情報に基づいています
• 視差の値が1だけ違うペナルティを加算
  • 物体には傾いた平面や曲面など，奥行きが少しずつ変化する部分もあります
  • この場合にはというペナルティ値を足すことにします
• 視差の値が2以上違うペナルティを加算
  • 物体境界では奥行きが不連続であり，視差が急激に変化することもあります
  • この不連続性を扱うため，一定以上の違いに対して一律でというペナルティ値を足します

といった具合に，視差の不連続さに応じて異なるペナルティをかけているということになります．

以上のDPを全ての方向について行ったのち，その結果を足し合わせたものをとします．

最後に，各画素についてが最小となるを選択することで視差を得ます．この手続きをWinner-Takes-Allと呼びます．

SGMは事前に定義した解集合(視差の候補)の中から最適なものを選ぶという点で，離散最適化問題と考えることができます．視差のことをより一般的に「ラベル」と呼ぶことにすると，あるラベルに対応するマッチングコストと，ラベル間の遷移に対するペナルティを適切に定義すれば，SGMは視差計算以外にも応用することができます．Segmentation SGMでは，ラベルを物体(Object)や路面(Ground)に対応させ，コストの最小化によってピクセル単位での分類を実現します．

視差画像が与えられ，適当なについて視差画像を垂直方向にスキャンした際の視差分布を考えます．図2はその例です．

に対するの変化は，物体上ではほぼ一定，路面上では直線的です．そこで，ある区間で視差値が一定のものを物体(Object)，直線的に変化するものを路面(Ground)とし，視差分布はこれらの組み合わせで構成されているものと考えます．

物体(Object)に対応するラベルを以下のように定義します．

は視差値を代表値としてもつ物体を表します．

路面(Ground)に対応するラベルをとします．

に属する視差は空間上で直線上に分布しているとします．

これらのラベルを合わせたものが全体のラベル集合です．

Segmentation SGMは与えられた視差分布をもとに，各画素をのいずれかに分類する問題を解きます．

コストの定義の前に，Segmentation SGMで行われるDPについて触れておきます．

まず入力視差画像を5~10ピクセル程度の幅で水平方向に分割し，分割した各領域に対して水平方向のメディアンフィルタを適用します．これによって水平方向の画像幅の削減，ノイズの除去を行います．ここでは高さ方向への操作は行いません．

その後，図3のように各列に対して上下方向のDPを行います．Stereo SGMと同様に，マッチングコストとラベルの遷移に対するペナルティから構成されるコストを，各画素について計算していきます．

はラベルに対するマッチングコストを，はラベルがに遷移した場合のペナルティを表します．は画像幅を削減した視差画像上での座標を表します．はDPの方向ベクトルを表し，上下方向の2種類です．

このDPは水平方向の依存を考慮しないため，各列について並列に計算することができます．上から下方向，下から上方向の2つのDPの結果を足し合わせ，最後にWinner-Takes-Allで最小コストをとるラベルを選択します．

Segmentation SGMのDPで使用するマッチングコストを定義します．

座標において視差値が観測されているとします．このとき物体のマッチングコストを以下のように定義します．

は視差値を代表値としてもつことから，からの距離をコストとします．

次に，路面のマッチングコストを以下のように定義します．

は路面モデルにおいて期待される視差値であり，垂直位置の1次関数で与えられます．

パラメータは，理論的にはカメラの高さと傾きから計算できますが，観測した視差値から推定することも可能です．路面に属する視差は空間上で直線上に分布しているため，RANSACやHough変換などを用いてを推定できます．

ちなみに，となるようなが画像の範囲内()に存在する可能性があります．これは水平線に対応しており，これより上部()に路面は存在し得ないため，を割り当てないよう考慮が必要です．

ラベルの遷移ペナルティを定義します．DPの方向として上から下，の順にスキャンする場合を考えます．前回アクセスした画素と現在の画素のラベルの遷移の仕方は大きく分類すると，以下の4種類になります．

• (物体から物体)
• (物体から路面)
• (路面から物体)
• (路面から路面)

次に各遷移についてペナルティを定義していきます．

遷移前のラベルを，遷移後のラベルをとし，の遷移ペナルティを以下のように定義します．

ラベルが変化しない場合にコスト0とします．ポイントはとの場合です．

の場合を考えます．ラベルはその物体の代表視差値を表すので，遷移前のが奥側(視差小)，遷移後のが手前側(視差大)という関係性になります(図4左)．路面に直立する物体が前後に並ぶとこのような関係性になります．

の場合，遷移前のが手前側(視差大)，遷移後のが奥側(視差小)という関係性になります(図4中)．これは遷移前の物体が浮いていることになり，実際のシーンであまり起こらないと考えられます．※支柱によって支えられている道路標識などはこちらのパターンに当てはまることがあります．

以上を考慮し，Segmentation SGMではとなるようにペナルティを設定しています．

の遷移ペナルティを以下のように定義します．

物体から路面への遷移は物体の底部で発生し，その前後で視差値は共有されています(図4右)．従って，上式のとおりの場合のみ，それ以外は(この遷移は許可しない)とします．

の遷移ペナルティを以下のように定義します．

路面から物体への遷移を表しますが，遷移の直後は物体の上部を指していることになります．ここでは，少なくとも物体が手前側，であることが想定されます(図4右)．の場合，物体は地面に沈んでいることになり，ほぼ起こり得ないと考えられます．従って，上式のとおりの場合のみ，それ以外はとします．

の遷移ペナルティを以下のように定義します．

と同様に，ラベルが変化しない場合にコスト0とします．

ここまで，上から下にスキャンする場合の遷移ペナルティを定義しました．逆方向にスキャンする場合も，同様のやり方でペナルティを定義します．

上下方向のDPの結果を足し合わせ，Winner-Takes-Allで各画素ごとに最小コストをとるラベルを選択します．後処理として，各列について同一ラベルが連続している領域を統合していき，1つのセグメントとして出力します．物体()に属するセグメントを抽出し，その視差値の大小でカラー描画した結果を図5に示します．

私たちはSegmentation SGMを組み込みGPU向けに実装・最適化しました．Segmentation SGMの計算量は大よそ画像幅画像高さ視差サイズに比例したものとなります. 高さ方向はDPの依存性のため並列化できませんが，幅方向は依存性が無いため容易に並列化可能です．視差(ラベル)方向のループもWarp Shuffleを利用して効率的に実装しています．

私たちが以前に実装したStereo SGM(libSGM)とSegmentation SGMを組み合わせたシステムにおいて，Jetson TX2上で処理時間を計測した結果を以下の表に示します．

Width x Height x Max Disparity
Stereo SGM (libSGM)	30 [ms] (33FPS)	50[ms] (20FPS)
Segmentation SGM	16 [ms] (64FPS)	23[ms] (44FPS)
Total	46 [ms] (22FPS)	73[ms] (14FPS)

Segmentation SGM単体では40～60FPSを達成しており，Stereo SGMと組み合わせて10～20FPSを達成しています．最新のJetson AGX Xavierでは未評価ですが，CUDAコア数がTX2の2倍あることから，さらなる性能向上が期待できるでしょう．

[1] H. Hirschmuller, "Accurate and Efficient Stereo Processing by Semi-Global Matching and Mutual Information, " Proc. IEEE Conf. Computer Vision and Pattern Recognition, vol. 2, pp. 807-814, June 2005.

[2] D. Pfeiffer, U. Franke, Towards a global optimal multi-layer Stixel representation of dense 3D data, in: British Machine Vision Conference, 2011.

[3] D. Pfeiffer, The Stixel world - a compact Medium-level representation for efficiently modeling dynamic three-dimensional environments, Ph.D. thesis, Humboldt-Universit¨at zu Berlin (2011).