このブログは、株式会社フィックスターズのエンジニアが、あらゆるテーマについて自由に書いているブログです。
Abstract: 自動運転システムというものが実用化されてきましたが、これはまだハードウェア実装に依存しています。しかしながら、これから数年のうちに、このようなコンピュートインテンシブな処理もソフトウェア実装で完璧にリアルタイム動作させることができるようになるでしょう。本稿では、私たちが組み込み用低消費電力GPU向けに実装・最適化したステレオ画像処理ベースのアルゴリズムについて述べます。私たちはこのシステムで、VGA画像処理で8FPSを達成しています。
Advanced Driver Assistance Systems(ADAS)と呼ばれる技術は、ここ数年、自動運転技術を実現するものとして、かなり注目を集めています。ダイムラー社が、2014年にメルセデス・ベンツEクラスとSクラスに搭載した6D-Vision Systemは、一つ大きな到達点となりました。
2013年時点で搭載されたものは、完全に自動運転というわけにはいきませんでしたが、Adaptive cruise control(日本語で言うと定速走行・車間距離制御装置)や、衝突回避システム、あるいはレーンキーピングシステム等を搭載しています。なかでも面白いのは、彼らがMAGIC BODY CONTROLと呼ぶ、Intelligentなサスペンションコントロールシステムです。
さて、もう少し最近で言えば、2015年5月に、ダイムラーグループのフレイトライナーが公開した、”Inspiration Truck” があります。これは6D-Vision Systemをベースとしたもので、アメリカ合衆国はネバダ州の高速道路を走行することを法的に許可されたものです。
このシステムを構成しているのは演算量的に非常に”重たい”画像処理となっています。6D-Vision Systemのサイトによれば、このシステムのデータフローはFigure.1のようになります。
Figure 1: 6D-Vision Systemにおける画像処理の全体的なデータフロー |
このシステムは、密なステレオカメラ処理――カメラ前方の各ピクセルごとの距離だとか――に依存するところが非常に大きいです。今まで様々な正確なアルゴリズムが考えだされてきましたが、2005年にSemi-Global Matching(SGM)と呼ばれるアルゴリズムが提案されるまで、”リアルタイム”なアプリケーション(VGA程度の大きさで30FPS以上、といったもの) を開発することはできませんでした。ダイムラーリサーチは2008年、市販のFPGAでこのアルゴリズムを使い、リアルタイムアプリケーションを開発しています。
ステレオ処理のアルゴリズムというのは、それまで、計算量とロバスト性と正確性のバランスから、ブロックマッチングに代表されるアルゴリズムを使用していました。ほかには、動的計画法や、確率伝搬法、あるいはグラフカット問題などです。ですが、ロバスト性、正確性、計算効率のいずれをとっても、SGMと並ぶものは存在していません。SGMはブロックマッチングと比較すると計算量が多くはあるのですが、その正確性・ロバスト性は、計算コストの増加に見合う分の価値があります。実際、6D-VisionはSGMによるものです。
Figure 4: 左画像での座標(x, y)を中心とした矩形領域のブロックマッチングの例。この時、右画像でもっとも良いマッチング結果となるのは(x*, y) |
従来のブロックマッチングでは、基準となるピクセルの周辺の領域(たとえば9×9の矩形とか) の画素値を比較することで、右画像と左画像の各画素を一致させようとします。この時の比較基準となる値をマッチングコストと呼称します。適切に画像を整えることにより、エピポーラ制約から、各ピクセルは同一のy座標を持つことが保証されるため、Figure 4に示す通り、x軸に沿って右の画像をスキャンするだけで済みます。ここで、点(x*, y)の周辺で、x軸におけるマッチングコストと、視差dが最小化する箇所を探索します。なぜなら、視差は深度情報に反比例するので、近くにある物体はより大きな視差を持つためです。このようにして得られた画像を、depth image(深度画像)と呼称します。
Figure 5: Stereo SGMが、座標(x, y)におけるスムージングコストを算出するために使用する8方向の図 |
しかしながら。Figure 3.を見てもらうとわかるように、まだ欠損や穴が見受けられます。それを軽減する方法の一つが、平滑化や、正規化といったものです。グラフカット問題や確率伝搬法などの従来の手法ではグローバルに平滑化しようとしますが、それではリアルタイムに良い結果を得ることはできません。一方で、”セミグローバルな”平滑化手法というのは革命的です。Figure 5.に示すように、グローバルな平滑化ではなく、各ピクセルの8方向程度に沿うことで、計算コストを最小限に抑えることができます。これはブロックマッチング同様、マッチングコストを最小化しているようですが、この場合では、道路やガードレール等の、十分な強度を得にくい、比較のしにくい表面においても行うことができ、”スムージングコスト”と呼称されます。キャリブレーションが正確に行われたステレオカメラで得られた三次元点群は、LIDAR(laser intensity direction and ranging、レーダー強度方向探知ならびに距離測定)で得られたものに匹敵します。
Figure 6: Segmentation SGMが座標(x,y)におけるスムージングコストを算出するための垂直方向の演算についての図 |
これで密な深度情報を得ることができました。次のステップとして、得られた情報を、道路とオブジェクトという二つの大きなクラスに分類します。道路が深度の大部分が水平に広がっている一方、オブジェクトは垂直に分布しています。しかし、Figure 3を見れば明らかなように、そのデプスマップは、カメラの傾きに依存して傾いています。分類を行う基本的なアイディアとして、まずメディアンフィルタを使用します。水平方向に5、または10ピクセルごとのメディアンフィルタを適用し、水平方向の画像幅の削減、ノイズの除去を行います。この水平方向のメディアンフィルタを適用している最中には、高さ方向への操作は行いません。その後、垂直方向にFigure 6のような、別のコスト最小化関数を適用します。総コスト関数は、マッチングコスト(測定深度と、オブジェクトや道路のモデル化された深度との差) だけでなく、モデル化された道路の事前情報等を持つ、スムージングコストとして提供しています。この状態で、道路かオブジェクトかの判定を行うには、すべてのピクセルにおいて、コスト関数の和を最小化します。コストの削減には、動的計画法がよく用いられてきましたが、SGMにもまた効果的に適用できることがわかりました。動的計画法は一次元の最適化問題に適しており、これはSGMが必要ないことを意味しています。しかし、SGMをステレオ、セグメンテーション(モデル分割) の双方に使用することで、ハードウェア・ソフトウェアを問わず、実装の手間を削減することができると信じています。
Figure 7: Segmentation SGMと、Figure2の画像を使用して得られた出力。 近いオブジェクトは赤く、遠いオブジェクトは緑色で表現されている。道路は透明。 |
現在、市販のFPGAによって、ハードウェアをカスタマイズするための労力は著しく下がっています。ここ数年から、あるいは今後数年かけて、ソフトウェアで書かれたコードをハードウェア化するソリューションが実用化されていくことでしょう。私たちの目的を証明するために、消費電力が10W以下のNVIDIA Tegra X1上でこのアルゴリズムを実装し、最適化を行いました。その処理速度がTable 1.になります。NVIDIAのロードマップに依れば、2020年前後で、SGMの二つのアルゴリズム(Stereo SGM, Segmentation SGM) をVGAサイズでリアルタイムに動作させることができるようになると思われます。
組み込み分野に対して(フィックスターズ含む)、新規の参入者ができることは、高い計算コストを持つアルゴリズムをソフトウェアで完全に実装し、それをADASを開発している人々に提供していくことであると考えています。
Width x Height x Max Disparity | Average processing time (ms) | |
640x480x64 | 1024x440x128 | |
Stereo SGM | 80 | 282 |
Segmentation SGM | 39 | 42 |
Table 1: Tegra X1上での、Stereo SGM、Segmentation SGMの 現在のパフォーマンス |
さて、デモムービーを用意しました。この動画の左右画像は、ダイムラー社が提供しているDaimler Urban Segmentation Dataset.を利用しています。わかりやすくするために、セグメント化されたオブジェクトには輪郭処理を、距離が接近したオブジェクトには警告マークを付与して表示しています。また、このデモではセグメンテーションの精度よりも速度を優先しています。もともとのSegmentation SGMのアルゴリズムでは、ノイズは少ないのですが、並列化が非常に困難です。そのため、まだ改善の余地があると考えています。現状では、オブジェクトのトラッキングを行わないため、移動している物体が自分と衝突するコースにいるかどうかという点を知ることはできません。
オブジェクトを追跡する前に、まず、オプティカルフローの密な推定値を取得する必要があります。伝統的には、ロバスト性と正確性を両立させるために、二つのアルゴリズムを使用します。特徴点と特徴量に基づいたグローバルでスパースな構造(CENSUS, SIFT, etc) と、局所改善の二つです。これらの代わりに、私たちはflow SGMというアルゴリズムを使用して、この問題に取り組み始めています。flow SGMはSegmentation SGMと同様に、Stereo SGMの派生として知られています。この手法によって、従来と同等の結果を得つつ、Stereo SGM, Segmentation SGMからのコードを再利用することで、システム全体の複雑さを軽減できることを願っています。現在、予備実験の結果は良いものが得られているため、今後、またブログにて調査結果を公開する予定です。
– The “SGM Team”: Samuel Audet, Yoriyuki Kitta, Yuta Noto, Ryo Sakamoto, Akihiro Takagi
[…] バージョンアップに伴い、オンラインセミナーを開催します。 本セミナーでは、フィックスターズの Tech Blog でも紹介している視差計算アルゴリズム Semi-Global Matching を更に深堀りして解説 […]