コンピュータビジョンセミナーvol.2 ~視差計算ライブラリ libSGM のアルゴリズム解説と CUDA高速化~(2022/12/20)

7.9K Views

December 20, 22

スライド概要

フィックスターズが開発した視差計算ライブラリ libSGM は、NVIDIA製のGPUで高速に動作するよう設計されており、OpenCV にもマージされています。

今回、libSGM のバージョンアップに伴い、オンラインセミナーを開催します。 本セミナーでは、フィックスターズの Tech Blog でも紹介している視差計算アルゴリズム Semi-Global Matching を更に深堀りして解説します。

また、同アルゴリズムを GPU 実装するにあたって行った、アーキテクチャの特性を活かした CUDA高速化についても併せて説明します。

<過去資料>
・vol.1 OpenCV活用(OpenCVでCUDAを活用するためのGpuMat解説): https://www.docswell.com/s/fixstars/ZRXQ72-20220805
・vol.2 視差計算ライブラリ libSGM のアルゴリズム解説と CUDA高速化: https://www.docswell.com/s/fixstars/5ENE7J-20221220
・vol.3  視差計算を利用した障害物検出: https://www.docswell.com/s/fixstars/ZQ8447-20231027

・フィックスターズの画像処理アルゴリズム開発支援: https://www.fixstars.com/ja/services/image-processing

profile-image

フィックスターズは、コンピュータの性能を最大限に引き出すソフトウェア開発のスペシャリストです。車載、産業機器、金融、医療など、幅広い分野での開発経験があります。また、ディープラーニングや機械学習などの最先端技術にも力を入れています。 並列化や最適化技術を駆使して、マルチコアCPU、GPU、FPGA、量子アニーリングマシンなど、さまざまなハードウェアでソフトウェアを高速化するサービスを提供しています。さらに、長年の経験から培ったハードウェアの知識と最適化ノウハウを活かし、高精度で高性能なアルゴリズムの開発も行っています。       ・開催セミナー一覧:https://www.fixstars.com/ja/seminar   ・技術ブログ :https://proc-cpuinfo.fixstars.com/

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

コンピュータビジョンセミナーvol.2 視差計算ライブラリ libSGM のアルゴリズム解説と CUDA高速化 Copyright © Fixstars Group

2.

本日のAgenda ● はじめに ● フィックスターズのご紹介 ● Semi-Global Matching (SGM) のアルゴリズム解説 ● SGM の CUDA 実装・高速化 ● Q&A / 告知 Copyright © Fixstars Group 2

3.

はじめに Copyright © Fixstars Group

4.

本講演の位置づけ ● 弊社でサービス展開しているコンピュータビジョン領域での様々な技術情報を、 コンピュータビジョンセミナーとして発信しています ● Vol.1 OpenCVの活用 (発表資料) ○ OpenCVでCUDAを活用するためのGpuMat解説 ● 今回の内容 ○ 視差計算アルゴリズム Semi-Global Matching の解説 ○ Semi-Global Matching の CUDA実装・高速化 ● こんな方に向いています ○ Semi-Global Matching アルゴリズムを理解したい ○ 実用的なアルゴリズムの GPU 高速化事例を知りたい Copyright © Fixstars Group 4

5.

発表者紹介 冨田 明彦 高木 章洋 ソリューションカンパニー 執行役員 ソリューション第二事業部 2008年に入社。金融、医療業界において、ソ フトウェア高速化業務に携わる。その後、新規 事業企画、半導体業界の事業を担当し、現職。 2014年に新卒入社。自動運転向けの画像認識 アルゴリズムの開発、高速化などに携わる。 OSS活動として、libSGMの開発にも携わる。 リードエンジニア Copyright © Fixstars Group 5

6.

フィックスターズの ご紹介 Copyright © Fixstars Group

7.

フィックスターズの強み コンピュータの性能を最大限に引き出す、ソフトウェア高速化のエキスパート集団 ハードウェアの知見 アルゴリズム実装力 各産業・研究分野の知見 目的の製品に最適なハードウェアを見抜き、 その性能をフル活用するソフトウェアを開 発します。 ハードウェアの特徴と製品要求仕様に合わ せて、アルゴリズムを改良して高速化を実 現します。 開発したい製品に使える技術を見抜き、実 際に動作する実装までトータルにサポート します。 Copyright © Fixstars Group 7

8.

開発サービス提供分野 半導体 産業機器 金融 自動車 ● NAND型フラッシュメモリ向けフ ァームウェア開発 ● 次世代AIチップの開発環境基盤 生命科学 ● Smart Factory実現への支援 ● マシンビジョンシステムの高速化 ● 自動運転の高性能化、実用化 ● ゲノム解析の高速化 ● 次世代パーソナルモビリティの 研究開発 ● 医用画像処理の高速化 Copyright © Fixstars Group ● デリバティブシステムの高速化 ● HFT(アルゴリズムトレード)の高速化 ● AI画像診断システムの研究開発 8

9.

サービス領域 様々な領域でソフトウェア開発サービスを提供しています。大量データの高速処理は、 お客様の製品競争力の源泉となっています。 AI・深層学習 組込み高速化 FPGAを活用した システム開発 自動車向け フラッシュメモリ向けフ ソフトウェア開発 ァームウェア開発 画像処理・アルゴリズム 開発 GPU向け高速化 Copyright © Fixstars Group 分散並列システム開発 量子コンピューティング 9

10.

画像処理アルゴリズム開発 高速な画像処理需要に対して、経験豊富なエンジニアが 責任を持って製品開発をご支援します。 お客様の課題 ご支援内容 高度な画像処理や深層学習等のアルゴリズム を開発できる人材が社内に限られている アルゴリズム調査・改変 課題に合ったアルゴリズム・実装手法を調査 製品実装に向けて適切な改変を実施 機能要件は満たせそうだが、ターゲット機器 上で性能要件までクリアできるか不安 深層学習ネットワーク精度の改善 様々な手法を駆使して深層学習ネットワークの精度を改善 製品化に結びつくような研究ができていない 論文調査・改善活動 論文調査から最先端の手法の探索 性能向上に向けた改善活動を継続 Copyright © Fixstars Group 10

11.

GPU向け高速化 高性能なGPUの本来の性能を十分に引き出し、 ソフトウェアの高速化を実現します。 お客様の課題 ご支援内容 GPUで計算してみたが期待した性能が出ない GPU高速化に関するコンサルティング GPU/CPUを組み合わせた全体として最適な設 CPU・GPU混在環境でのシステム設計 計がしたい アルゴリズムのGPU向け移植 原価を維持したまま機能を追加するため、も う少し処理を速くしたい GPUプログラム高速化 品質確保のため、精度を上げたく演算量は増 えるが性能は維持したい Copyright © Fixstars Group 継続的な精度向上 11

12.

Semi-Global Matching Copyright © Fixstars Group

13.

ステレオマッチング ● 基準画像の注目画素に対し、同一の空間の投影点(対応点)を 他方の画像中から探索すること ○ 今回は同じ高さの水平ライン上に対応点が存在する、平行ステレオを扱う ○ ○ ステレオマッチングの出力は、基準画像の各画素に対応する視差値を格納した、視差画像 視差から物体の奥行きを求めることができ、3次元復元等に利用される ● 注目画素と対応画素の水平方向のずれを視差(disparity)と呼ぶ 対応 左画像(基準画像) 右画像 視差画像(カラー表示) 入力図は Middlebury Stereo Datasets 2001 Tsukuba (vision.middlebury.edu/stereo/data/scenes2001/data/tsukuba) より Copyright © Fixstars Group 13

14.

ナイーブなステレオマッチングのアルゴリズム ● 左画像の注目画素に対し、右画像の水平ライン上で 最も類似度の高い(相違度の低い)画素を探索 ○ ○ 予め視差候補数Dを決めておき、0~D-1の範囲で探索するのが一般的 左画像の注目画像の位置を視差0として、左方向に探索する ○ ○ ブロック間のSAD (Sum of Absolute Difference) Census特徴間のハミング距離 ← SGMで採用されることが多い ● 相違度の例 相違度 ブロック 探索範囲 左画像 視差候補 右画像 Copyright © Fixstars Group 14

15.

Census変換 ● 注目画素をバイナリ特徴量に変換する手法 ○ 注目画素値と近傍画素値の大小を01のビット列にエンコード ○ 相違度はハミング距離で計算、CPU(GPU)上で少ない命令数で実現できる ● Census 9×7 ○ 9×7のウィンドウ内で、注目画素と近傍画素を比較する手法 ○ ビット長は62bitで、64bit変数で保持可能 ● Center-Symmetric Census 9×7 ○ 9×7のウィンドウ内で、注目画素に点対称な画素のペアを比較する手法 ○ ビット長は31bitで、32bit変数で保持可能 ○ メモリ効率・計算効率を優先するならこちらを使うと良い Copyright © Fixstars Group 15

16.

ナイーブな手法の問題点 ● テクスチャレス(平坦)な領域では、相違度による区別が困難 ● 不安定な結果を生じやすい ブロック 相違度 探索範囲 左画像 ? 視差候補 右画像 Copyright © Fixstars Group 16

17.

Semi-Global Matching(SGM) ● 視差分布に関する事前情報を利用した最適化 ○ 物体上では、隣接するピクセルの視差値は近い ○ 物体同士の境界では、隣接するピクセルの視差値が不連続に変化 ● テクスチャレスな領域でも視差が安定しやすく、物体の輪郭も保存 理想的な視差画像 ナイーブな手法 Copyright © Fixstars Group Semi-Global Matching 17

18.

最適化の原理:グラフを使った説明 ● スキャンライン上の画素と、視差候補によって作られるグラフを考える ● スキャンライン方向にグラフを横断するとき、コスト和最小となる経路は? スキャンラインの方向 p=0 d=0 p=1 … p=P-1 … d=1 コスト付きグラフ ・ノードの数:P×D個 - P:あるスキャンラインおける、ライン上の画素数 - D:視差候補数 ・ノードコスト:(p,d)におけるマッチングコスト(相違度) ・ p方向に隣接するノード間に、エッジが存在 d=D-1 スキャンラインの例 (水平とは限らない) Copyright © Fixstars Group 18

19.

ペナルティ(エッジコスト)と得られる解 ● ペナルティ0の場合 ○ マッチングコスト最小のノードを経由 (ナイーブな手法と等価) ● 視差値の変化に対してペナルティを設定 ○ 滑らかな解が得られやすい ペナルティなし ペナルティあり Copyright © Fixstars Group 19

20.

SGMにおけるペナルティの設計 ● エッジの2端点における視差k,dについて、ペナルティq(k,d)は以下の通り ○ 0 𝑞 𝑘, 𝑑 = ൞𝑃1 𝑃2 if 𝑘 − 𝑑 = 0 if 𝑘 − 𝑑 = 1 if 𝑘 − 𝑑 > 1 ○ ただし、0 < 𝑃1 < 𝑃2 ○ マッチングコストで優劣がつかない場合、視差の変化が少ない経路が好まれる ● P2の役割 ○ 物体同士の境界では奥行き(=視差値)が不連続 ○ P2がペナルティ上限となり、平滑化しすぎを防ぐ Copyright © Fixstars Group 20

21.

DPテーブルの計算 ● コスト和最小となる経路は動的計画法(DP)により効率的に求められる ● SGMでは、各ノードの最小コスト※を記録したDPテーブルが重要 ○ ※そのノードに達する経路の内、コスト和が最小となる経路の、コスト和の値 ○ 経路そのものは復元しない ● スキャンライン上の画素p、視差候補dにおけるDPテーブルの値は ○ p 𝑘 スキャンライン方向 ○ p-r 𝐿𝒓 𝒑, 𝑑 = 𝐶 𝒑, 𝑑 + min 𝐿𝒓 𝒑 − 𝒓, 𝑘 + 𝑞 𝑘, 𝑑 マッチングコスト 前回計算したコスト ペナルティ関数 p - rの各ノードから注目ノードへの遷移を調べたとき、 最小コストになるものを選んでいるだけ! Copyright © Fixstars Group k d 21

22.
[beta]
DPテーブルの計算
● ペナルティ項を整理すると、最終的には以下の計算になる

● OpenCV風に書くとこんな感じ
static void updateCost(const cv::Mat1i& C, cv::Mat1i& L, int D, int xp, int yp, int xc, int yc, int P1, int P2)
{
int minLp = COST_INF;
for (int d = 0; d < D; d++)
minLp = std::min(minLp, L(yp, xp, d));

for (int d = 0; d < D; d++)
{
const int Lp0 = L(yp, xp, d);
const int Lp1 = d > 0
? L(yp, xp, d - 1) + P1 : COST_INF;
const int Lp2 = d < D - 1 ? L(yp, xp, d + 1) + P1 : COST_INF;
const int Lp3 = minLp + P2;
L(yc, xc, d) = C(yc, xc) + std::min(std::min(Lp0, Lp1), std::min(Lp2, Lp3)) - minLp;
}

オーバーフロー対策

}
Copyright © Fixstars
Group

22

23.

Cost Aggregation ● 特定方向にDPをした時、その方向に平滑化された結果が得られる (下図) ● 様々な方向についてDPテーブルを計算し、それらを足し合わせることで、 全方向に等しく平滑化した結果を得る (Cost Aggregation) ○ 𝑆 𝒑, 𝑑 = σ𝒓 𝐿𝒓 𝒑, 𝑑 ○ 典型的には縦横斜め×順方向逆方向の、計8方向 ○ 1つ1つのDPは特定方向にしか依存がないという点が、”Semi-Global”たるゆえん 水平方向だけ 垂直方向だけ Copyright © Fixstars Group 23

24.

Winner-Takes-All ● Cost Aggregation結果から、最小コストをとるdを出力視差とする ○ 𝑑 𝒑 = argmin 𝑆 𝒑, 𝑘 𝑘 ブロック マッチングコストの分布 SGM後のコスト分布 左画像 Copyright © Fixstars Group 24

25.

後処理 ● サブピクセル推定 ○ コスト最小値周りでパラボラフィッティング ● Uniquenessチェック ○ コスト最小値が2番目の最小値より十分小さいかチェック ● LRチェック ○ 少し処理を追加すると、右画像基準の視差画像を得られる ○ 左右の視差値が一致しているかチェック ● メディアンフィルタ ○ libSGMは全ての 機能をサポート ノイズ除去や無効値の補完 Copyright © Fixstars Group 25

26.

SGMのCUDA実装 Copyright © Fixstars Group

27.

CUDAの簡単なおさらい ● スレッドおよびメモリの階層 スレッドの階層構造 • スレッド間に階層構造がある • 近いスレッド同士はより密に通信・同期を行うことができる メモリの階層構造 • おおむねスレッドの階層構造と対応 Fixstars CUDA高速化セミナーvol.1 ~画像処理アルゴリズムの高速化~ より抜粋 Copyright © Fixstars Group 27

28.

SGMの処理フローと並列性 ● SGMの並列性は高く、CUDA実装自体はしやすい 入力画像 DP tables Census画像 Matching Cost ・・・ W×H×D volume → → → Smoothed Cost 視差画像 W×H×D volume → → → Census変換 画素単位で並列化可能 Matching Cost計算 要素単位で並列化可能 Cost Aggregation ライン単位で並列化可能 DP単位で並列化可能 Copyright © Fixstars Group Winner-Takes All 要素単位で並列化可能 28

29.

Census変換 ● タスクの粒度 ○ 出力画像(=入力画像と同サイズ)を120×16のタイルに分割 ○ そのタイルに対し、 128×1のスレッドブロックが処理を担当 ● 入力データをシェアードメモリに置く ○ タイルの1行分(120×1)の計算には、128×7の入力データが必要 (近傍画素の分の拡張) ○ 最初の1行分の128×7をグローバルメモリからシェアードメモリに読み込む ○ 2行目以降は新規に必要な128×1だけシェアードメモリに読み込む 128スレッド 出力画像タイル(120×16)と 1タイルに必要な入力データ(128×22) 9×7ウィンドウ Copyright © Fixstars Group 29

30.

Cost Aggregation ● SGM全体の中で処理量が大 ○ W×H×Dの計算量、8方向 ● 演算に対してメモリアクセス量が多いのがボトルネック ○ 1方向 W×H×D [Byte] のMatching CostのGlobal Read ○ 1方向 W×H×D [Byte] の結果のGlobal Write DP tables Matching Cost ・・・ W×H×D volume → → → Smoothed Cost W×H×D volume → → → 演算は足し算とmin程度で、あまり大したことがない Copyright © Fixstars Group 30

31.

Matching Costの扱い ● 従来実装※はMatching Costをテーブル化 ○ 8回のDPで計算結果を再利用できる ○ W×H×D [Bytes] のGlobal Readが発生 ● Matching CostをDP内で毎回計算 ○ 毎回左右のCensus特徴を読むことになるが、右側のCensus特徴の読み込み方を工夫すると、 ○ 全体で W×H×2×8 [Bytes] 程度のGlobal Readに抑えられる (64bit Censusの場合) ■ 視差候補数Dは64や128であることが多いため、テーブルサイズと比較するとかなり小さい ■ 32bit Censusの場合はさらに半分小さくなる W×H×D 回のハミング距離計算(≒popcount命令)が発生 ○ popcountが1byte読むより速ければ、従来実装より速くなりそう ※従来実装の例 • libSGM version2以前 • Hernandezらの実装:https://github.com/dhernandez0/sgm Copyright © Fixstars Group 31

32.

popcountと1byte読むのとどちらが速いか ● 特定のGPUに対するpopcountのスループット ○ CUDA公式から32bit popcountのスループットを参照 ○ Compute Capability6.1(GeForce 1000系)では32、7.x以降では16 ■ 単位は「Number of Results per Clock Cycle per Multiprocessor」 SM数とクロック周波数をかけることで、1秒当たりのpopcount回数が分かる ○ ● GeForce GTX 1080Ti (Compute Capability 6.1)の場合 ○ popcount/s = 32 [ops/cycle/SM] × 28 [SMs] × 1.481 [GHz] = 1326 [Gops/s] ■ 64bit Censusの場合はこの半分の663 [Gops/s] 一方で、メモリの速さは Bytes/s: 484.4 [GB/s] (実測340 [GB/s] 程度) ○ Matching Costを毎回計算する方が速い ○ ● libSGM 2.0以降では毎回計算を採用 ○ GPUの演算性能・メモリ性能によってはアプローチの見直しの余地あり Copyright © Fixstars Group 32

33.

DPのCUDA実装 (水平方向、D=128の例) ● タスクの粒度 ○ ○ 16スレッドで128個の視差候補を処理 ■ 1スレッド(lane)は連続する8個の視差を担当 128個の視差を処理したら次の画素(x+1)へ (2) ● 1画素(x)当たりの処理 ○ (1) マッチングコストの計算 ○ (2) ペナルティ項の計算 ○ (3) DPテーブルに結果をストア (3) (1) 128視差 8視差 lane00 lane01 lane02 lane03 lane04 lane05 lane06 lane07 lane08 lane09 lane10 lane11 lane12 lane13 lane14 lane15 x方向 Copyright © Fixstars Group 33

34.

(1) マッチングコストの計算 ● 左側のCensus特徴をグローバルメモリから読む ● 右側のCensus特徴はレジスタに置いて再利用 ○ ○ xを一つ進めたら全要素を右に1つずらす ■ 1レーンが持つ8要素の内、末尾要素はWarp Shuffleで隣のレーンに渡す 新規の1画素をグローバルから読み込む ● ハミング距離の計算 ○ 左右のCensus特徴のxor + popcount Warp Shuffle lane00 lane01 lane02 lane03 lane04 lane05 lane06 lane07 lane08 lane09 lane10 lane11 lane12 lane13 lane14 lane15 グローバルから1画素読む レジスタに配置した右Census特徴の更新方法 Copyright © Fixstars Group 34

35.

(2) ペナルティ項の計算 ● 1画素分のDPテーブルをレジスタに置いて再利用 ○ (3)の結果はxを一つ進めたら(2)で使われる ● DPテーブルの最小値計算 ○ レーン内でminをとったのち、 Warp Shuffleで全体のminをとる (2) (3) (1) lane00 lane01 lane02 lane03 lane04 lane05 lane06 lane07 lane08 lane09 lane10 lane11 lane12 lane13 lane14 lane15 min intra lane レジスタに配置したDPテーブル min inter lane Copyright © Fixstars Group 35

36.

(3) DPテーブルに結果をストア ● グローバルメモリ上のDPテーブルに結果を書き込む ● 8要素を一括で書き込む ○ できるだけ多くまとめて読み書きするほうが効率が良い ○ CUDA だと最大で 16 [Bytes] まで1命令で読み書きできる Copyright © Fixstars Group 36

37.

DPの並行実行(Concurrent Kernel Execution) ● ハイエンドGPUでは演算器が余る ● 異なる方向間の依存性はないため並行させる ○ 実装上は、異なるstreamを指定して実行するだけでよい Concurrent Kernel Executionを使用した8方向DPのタイムライン Copyright © Fixstars Group 37

38.

Winner-Takes All ● 処理の概要 ○ 8方向のDPテーブル(W×H×D)から値を読んで足し合わせる ○ 視差候補の内、最小コストをとるものを出力 ● メモリアクセスがボトルネック ● 8要素を一括で読み込む ○ 処理量(画像サイズ)が十分大きい場合はGPUのメモリ性能を使い切る Copyright © Fixstars Group 38

39.

評価結果 ● 計測環境 ○ 画像サイズ:1240 x 374 ○ 視差サイズ:128 ● 他のSGM実装を上回る性能を達成 SGM実装 GeForce GTX 1080 Ti 処理時間:FPS NVIDIA Tegra X2 処理時間:FPS 今回の手法 3.5[msec] : 286FPS 53.7[msec] : 19FPS Hernandez[2] 4.4[msec] : 227FPS 60.0[msec] : 17FPS VisionWorks[3] 7.0[msec] : 143FPS 74.9[msec] : 13FPS [2] Embedded real-time stereo estimation via Semi-Global Matching on the GPU, D. Hernandez-Juarez et al, ICCS 2016 code: https://github.com/dhernandez0/sgm [3] NVIDIA VisionWorks https://developer.nvidia.com/embedded/visionworks (Matching CostにはCensusを使用) Copyright © Fixstars Group 39

40.

libSGMの紹介 Copyright © Fixstars Group

41.

libSGMの紹介 ● 特徴 ○ 他の実装より速い ○ 各種オプションの提供 (サブピクセル推定,DP方向数,探索範囲設定,etc.) ○ 豊富なサンプルの提供 (連番画像での実行,3次元復元,ベンチマーク, ZEDカメラ入力,etc.) ○ OpenCVラッパーの提供 ● 最近version 3.0.0にアップデート ○ 大規模なリファクタリングを実施 ○ 64bit Censusの(再)サポート 是非使ってください! Copyright © Fixstars Group 41

42.

Thank you! お問い合わせ窓口 : [email protected] Copyright © Fixstars Group