コンピュータビジョンセミナー2 / computer_vision_seminar_libSGM

2022年12月20日に開催した「コンピュータビジョンセミナーvol.2～視差計算ライブラリ libSGM のアルゴリズム解説と CUDA高速化～」の当日資料です。

Transcript

1. Copyright © Fixstars Group コンピュータビジョンセミナーvol.2 視差計算ライブラリ libSGM のアルゴリズム解説と CUDA高速化
2. Copyright © Fixstars Group 本日のAgenda • はじめに • フィックスターズのご紹介 • Semi-Global Matching (SGM) のアルゴリズム解説 • SGM の CUDA 実装・高速化 • Q&A / 告知 2
3. Copyright © Fixstars Group はじめに
4. Copyright © Fixstars Group • 弊社でサービス展開しているコンピュータビジョン領域での様々な技術情報を、 コンピュータビジョンセミナーとして発信しています • Vol.1 OpenCVの活用 (発表資料) ◦ OpenCVでCUDAを活用するためのGpuMat解説 • 今回の内容 ◦ 視差計算アルゴリズム Semi-Global Matching の解説 ◦ Semi-Global Matching の CUDA実装・高速化 • こんな方に向いています ◦ Semi-Global Matching アルゴリズムを理解したい ◦ 実用的なアルゴリズムの GPU 高速化事例を知りたい 本講演の位置づけ 4
5. Copyright © Fixstars Group 発表者紹介 冨田 明彦 ソリューションカンパニー 執行役員 2008年に入社。金融、医療業界において、ソ フトウェア高速化業務に携わる。その後、新規 事業企画、半導体業界の事業を担当し、現職。 5 高木 章洋 ソリューション第二事業部 リードエンジニア 2014年に新卒入社。自動運転向けの画像認識 アルゴリズムの開発、高速化などに携わる。 OSS活動として、libSGMの開発にも携わる。
6. Copyright © Fixstars Group フィックスターズの ご紹介
7. Copyright © Fixstars Group フィックスターズの強み コンピュータの性能を最大限に引き出す、ソフトウェア高速化のエキスパート集団 ハードウェアの知見 アルゴリズム実装力 各産業・研究分野の知見 7 目的の製品に最適なハードウェアを見抜き、 その性能をフル活用するソフトウェアを開 発します。 ハードウェアの特徴と製品要求仕様に合わ せて、アルゴリズムを改良して高速化を実 現します。 開発したい製品に使える技術を見抜き、実 際に動作する実装までトータルにサポート します。
8. Copyright © Fixstars Group 開発サービス提供分野 8 半導体 自動車 産業機器 生命科学 金融 •NAND型フラッシュメモリ向けフ ァームウェア開発 •次世代AIチップの開発環境基盤 •自動運転の高性能化、実用化 •次世代パーソナルモビリティの 研究開発 •Smart Factory実現への支援 •マシンビジョンシステムの高速化 •ゲノム解析の高速化 •医用画像処理の高速化 •AI画像診断システムの研究開発 •デリバティブシステムの高速化 •HFT(アルゴリズムトレード)の高速化
9. Copyright © Fixstars Group サービス領域 様々な領域でソフトウェア開発サービスを提供しています。大量データの高速処理は、 お客様の製品競争力の源泉となっています。 9 組込み高速化 画像処理・アルゴリズム 開発 分散並列システム開発 GPU向け高速化 FPGAを活用した システム開発 量子コンピューティング AI・深層学習 自動車向け ソフトウェア開発 フラッシュメモリ向けフ ァームウェア開発
10. Copyright © Fixstars Group 画像処理アルゴリズム開発 高速な画像処理需要に対して、経験豊富なエンジニアが 責任を持って製品開発をご支援します。 お客様の課題 高度な画像処理や深層学習等のアルゴリズム を開発できる人材が社内に限られている 機能要件は満たせそうだが、ターゲット機器 上で性能要件までクリアできるか不安 製品化に結びつくような研究ができていない ご支援内容 深層学習ネットワーク精度の改善 様々な手法を駆使して深層学習ネットワークの精度を改善 論文調査・改善活動 論文調査から最先端の手法の探索 性能向上に向けた改善活動を継続 アルゴリズム調査・改変 課題に合ったアルゴリズム・実装手法を調査 製品実装に向けて適切な改変を実施 10
11. Copyright © Fixstars Group GPU向け高速化 高性能なGPUの本来の性能を十分に引き出し、 ソフトウェアの高速化を実現します。 お客様の課題 GPUで計算してみたが期待した性能が出ない GPU/CPUを組み合わせた全体として最適な設 計がしたい ご支援内容 GPU高速化に関するコンサルティング CPU・GPU混在環境でのシステム設計 アルゴリズムのGPU向け移植 GPUプログラム高速化 継続的な精度向上 原価を維持したまま機能を追加するため、も う少し処理を速くしたい 品質確保のため、精度を上げたく演算量は増 えるが性能は維持したい 11
12. Copyright © Fixstars Group Semi-Global Matching
13. Copyright © Fixstars Group ステレオマッチング • 基準画像の注目画素に対し、同一の空間の投影点(対応点)を 他方の画像中から探索すること ◦ 今回は同じ高さの水平ライン上に対応点が存在する、平行ステレオを扱う • 注目画素と対応画素の水平方向のずれを視差(disparity)と呼ぶ ◦ ステレオマッチングの出力は、基準画像の各画素に対応する視差値を格納した、視差画像 ◦ 視差から物体の奥行きを求めることができ、3次元復元等に利用される 13 左画像(基準画像) 右画像 視差画像(カラー表示) 入力図は Middlebury Stereo Datasets 2001 Tsukuba (vision.middlebury.edu/stereo/data/scenes2001/data/tsukuba) より 対応
14. Copyright © Fixstars Group ナイーブなステレオマッチングのアルゴリズム • 左画像の注目画素に対し、右画像の水平ライン上で 最も類似度の高い(相違度の低い)画素を探索 ◦ 予め視差候補数Dを決めておき、0～D-1の範囲で探索するのが一般的 ◦ 左画像の注目画像の位置を視差0として、左方向に探索する • 相違度の例 ◦ ブロック間のSAD (Sum of Absolute Difference) ◦ Census特徴間のハミング距離 ← SGMで採用されることが多い 14 左画像 右画像 視差候補 相違度 ブロック 探索範囲
15. Copyright © Fixstars Group Census変換 • 注目画素をバイナリ特徴量に変換する手法 ◦ 注目画素値と近傍画素値の大小を01のビット列にエンコード ◦ 相違度はハミング距離で計算、CPU(GPU)上で少ない命令数で実現できる • Census 9×7 ◦ 9×7のウィンドウ内で、注目画素と近傍画素を比較する手法 ◦ ビット長は62bitで、64bit変数で保持可能 • Center-Symmetric Census 9×7 ◦ 9×7のウィンドウ内で、注目画素に点対称な画素のペアを比較する手法 ◦ ビット長は31bitで、32bit変数で保持可能 ◦ メモリ効率・計算効率を優先するならこちらを使うと良い 15
16. Copyright © Fixstars Group ナイーブな手法の問題点 • テクスチャレス(平坦)な領域では、相違度による区別が困難 • 不安定な結果を生じやすい 探索範囲 ブロック ？ 左画像 右画像 視差候補 相違度 16
17. Copyright © Fixstars Group Semi-Global Matching(SGM) • 視差分布に関する事前情報を利用した最適化 ◦ 物体上では、隣接するピクセルの視差値は近い ◦ 物体同士の境界では、隣接するピクセルの視差値が不連続に変化 • テクスチャレスな領域でも視差が安定しやすく、物体の輪郭も保存 理想的な視差画像 ナイーブな手法 Semi-Global Matching 17
18. Copyright © Fixstars Group 最適化の原理：グラフを使った説明 • スキャンライン上の画素と、視差候補によって作られるグラフを考える • スキャンライン方向にグラフを横断するとき、コスト和最小となる経路は？ コスト付きグラフ ・ノードの数：P×D個 - P：あるスキャンラインおける、ライン上の画素数 - D：視差候補数 ・ノードコスト：(p,d)におけるマッチングコスト(相違度) ・ p方向に隣接するノード間に、エッジが存在 p=P-1 p=0 p=1 … d=0 d=1 d=D-1 … スキャンラインの例 (水平とは限らない) スキャンラインの方向 18
19. Copyright © Fixstars Group ペナルティ(エッジコスト)と得られる解 • ペナルティ0の場合 ◦ マッチングコスト最小のノードを経由 (ナイーブな手法と等価) • 視差値の変化に対してペナルティを設定 ◦ 滑らかな解が得られやすい ペナルティなし ペナルティあり 19
20. Copyright © Fixstars Group SGMにおけるペナルティの設計 • エッジの2端点における視差k,dについて、ペナルティq(k,d)は以下の通り ◦ 𝑞 𝑘, 𝑑 = ൞ 0 if 𝑘 − 𝑑 = 0 𝑃1 if 𝑘 − 𝑑 = 1 𝑃2 if 𝑘 − 𝑑 > 1 ◦ ただし、0 < 𝑃1 < 𝑃2 ◦ マッチングコストで優劣がつかない場合、視差の変化が少ない経路が好まれる • P 2 の役割 ◦ 物体同士の境界では奥行き(=視差値)が不連続 ◦ P2 がペナルティ上限となり、平滑化しすぎを防ぐ 20
21. Copyright © Fixstars Group DPテーブルの計算 • コスト和最小となる経路は動的計画法(DP)により効率的に求められる • SGMでは、各ノードの最小コスト※を記録したDPテーブルが重要 ◦ ※そのノードに達する経路の内、コスト和が最小となる経路の、コスト和の値 ◦ 経路そのものは復元しない • スキャンライン上の画素p、視差候補dにおけるDPテーブルの値は ◦ 𝐿𝒓 𝒑, 𝑑 = 𝐶 𝒑, 𝑑 + min 𝑘 𝐿𝒓 𝒑 − 𝒓, 𝑘 + 𝑞 𝑘, 𝑑 ◦ p - rの各ノードから注目ノードへの遷移を調べたとき、 最小コストになるものを選んでいるだけ！ スキャンライン方向 マッチングコスト 前回計算したコスト ペナルティ関数 p - r p k d 21
22. Copyright © Fixstars Group 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; } } オーバーフロー対策 22
23. Copyright © Fixstars Group Cost Aggregation • 特定方向にDPをした時、その方向に平滑化された結果が得られる (下図) • 様々な方向についてDPテーブルを計算し、それらを足し合わせることで、 全方向に等しく平滑化した結果を得る (Cost Aggregation) ◦ 𝑆 𝒑, 𝑑 = σ𝒓 𝐿𝒓 𝒑, 𝑑 ◦ 典型的には縦横斜め×順方向逆方向の、計8方向 ◦ 1つ1つのDPは特定方向にしか依存がないという点が、”Semi-Global”たるゆえん 水平方向だけ 垂直方向だけ 23
24. Copyright © Fixstars Group Winner-Takes-All • Cost Aggregation結果から、最小コストをとるdを出力視差とする ◦ 𝑑 𝒑 = argmin 𝑘 𝑆 𝒑, 𝑘 左画像 ブロック マッチングコストの分布 SGM後のコスト分布 24
25. Copyright © Fixstars Group 後処理 • サブピクセル推定 ◦ コスト最小値周りでパラボラフィッティング • Uniquenessチェック ◦ コスト最小値が2番目の最小値より十分小さいかチェック • LRチェック ◦ 少し処理を追加すると、右画像基準の視差画像を得られる ◦ 左右の視差値が一致しているかチェック • メディアンフィルタ ◦ ノイズ除去や無効値の補完 libSGMは全ての 機能をサポート 25
26. Copyright © Fixstars Group SGMのCUDA実装
27. Copyright © Fixstars Group CUDAの簡単なおさらい • スレッドおよびメモリの階層 Fixstars CUDA高速化セミナーvol.1 ～画像処理アルゴリズムの高速化～ より抜粋 スレッドの階層構造 • スレッド間に階層構造がある • 近いスレッド同士はより密に通信・同期を行うことができる メモリの階層構造 • おおむねスレッドの階層構造と対応 27
28. Copyright © Fixstars Group SGMの処理フローと並列性 • SGMの並列性は高く、CUDA実装自体はしやすい W×H×D volume Census変換 Matching Cost計算 ・・・ → → → → → → Cost Aggregation W×H×D volume Matching Cost 入力画像 Census画像 DP tables Smoothed Cost Winner-Takes All 視差画像 画素単位で並列化可能 要素単位で並列化可能 ライン単位で並列化可能 DP単位で並列化可能 要素単位で並列化可能 28
29. Copyright © Fixstars Group Census変換 • タスクの粒度 ◦ 出力画像(=入力画像と同サイズ)を120×16のタイルに分割 ◦ そのタイルに対し、 128×1のスレッドブロックが処理を担当 • 入力データをシェアードメモリに置く ◦ タイルの1行分(120×1)の計算には、128×7の入力データが必要 (近傍画素の分の拡張) ◦ 最初の1行分の128×7をグローバルメモリからシェアードメモリに読み込む ◦ 2行目以降は新規に必要な128×1だけシェアードメモリに読み込む 128スレッド 出力画像タイル(120×16)と 1タイルに必要な入力データ(128×22) 9×7ウィンドウ 29
30. Copyright © Fixstars Group Cost Aggregation • SGM全体の中で処理量が大 ◦ W×H×Dの計算量、8方向 • 演算に対してメモリアクセス量が多いのがボトルネック ◦ 1方向 W×H×D [Byte] のMatching CostのGlobal Read ◦ 1方向 W×H×D [Byte] の結果のGlobal Write W×H×D volume ・・・ → → → → → → W×H×D volume Matching Cost DP tables Smoothed Cost 演算は足し算とmin程度で、あまり大したことがない 30
31. Copyright © Fixstars Group 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 31
32. Copyright © Fixstars Group 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の演算性能・メモリ性能によってはアプローチの見直しの余地あり 32
33. Copyright © Fixstars Group DPのCUDA実装 (水平方向、D=128の例) • タスクの粒度 ◦ 16スレッドで128個の視差候補を処理 ▪ 1スレッド(lane)は連続する8個の視差を担当 ◦ 128個の視差を処理したら次の画素(x+1)へ • 1画素(x)当たりの処理 ◦ (1) マッチングコストの計算 ◦ (2) ペナルティ項の計算 ◦ (3) DPテーブルに結果をストア lane00 lane01 lane02 lane03 lane04 lane05 lane06 lane07 lane08 lane09 lane10 lane11 lane12 lane13 lane14 lane15 128視差 8視差 x方向 (1) (2) (3) 33
34. Copyright © Fixstars Group (1) マッチングコストの計算 • 左側のCensus特徴をグローバルメモリから読む • 右側のCensus特徴はレジスタに置いて再利用 ◦ xを一つ進めたら全要素を右に1つずらす ▪ 1レーンが持つ8要素の内、末尾要素はWarp Shuffleで隣のレーンに渡す ◦ 新規の1画素をグローバルから読み込む • ハミング距離の計算 ◦ 左右のCensus特徴のxor + popcount lane00 lane01 lane02 lane03 lane04 lane05 lane06 lane07 lane08 lane09 lane10 lane11 lane12 lane13 lane14 lane15 グローバルから1画素読む レジスタに配置した右Census特徴の更新方法 Warp Shuffle 34
35. Copyright © Fixstars Group (2) ペナルティ項の計算 • 1画素分のDPテーブルをレジスタに置いて再利用 ◦ (3)の結果はxを一つ進めたら(2)で使われる • DPテーブルの最小値計算 ◦ レーン内でminをとったのち、 Warp Shuffleで全体のminをとる レジスタに配置したDPテーブル lane00 lane01 lane02 lane03 lane04 lane05 lane06 lane07 lane08 lane09 lane10 lane11 lane12 lane13 lane14 lane15 (1) (2) (3) min intra lane min inter lane 35
36. Copyright © Fixstars Group (3) DPテーブルに結果をストア • グローバルメモリ上のDPテーブルに結果を書き込む • 8要素を一括で書き込む ◦ できるだけ多くまとめて読み書きするほうが効率が良い ◦ CUDA だと最大で 16 [Bytes] まで1命令で読み書きできる 36
37. Copyright © Fixstars Group DPの並行実行(Concurrent Kernel Execution) • ハイエンドGPUでは演算器が余る • 異なる方向間の依存性はないため並行させる ◦ 実装上は、異なるstreamを指定して実行するだけでよい Concurrent Kernel Executionを使用した8方向DPのタイムライン 37
38. Copyright © Fixstars Group Winner-Takes All • 処理の概要 ◦ 8方向のDPテーブル(W×H×D)から値を読んで足し合わせる ◦ 視差候補の内、最小コストをとるものを出力 • メモリアクセスがボトルネック • 8要素を一括で読み込む ◦ 処理量(画像サイズ)が十分大きい場合はGPUのメモリ性能を使い切る 38
39. Copyright © Fixstars Group 評価結果 • 計測環境 ◦ 画像サイズ：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を使用) 39
40. Copyright © Fixstars Group libSGMの紹介
41. Copyright © Fixstars Group libSGMの紹介 • 特徴 ◦ 他の実装より速い ◦ 各種オプションの提供 (サブピクセル推定,DP方向数,探索範囲設定,etc.) ◦ 豊富なサンプルの提供 (連番画像での実行,3次元復元,ベンチマーク, ZEDカメラ入力,etc.) ◦ OpenCVラッパーの提供 • 最近version 3.0.0にアップデート ◦ 大規模なリファクタリングを実施 ◦ 64bit Censusの(再)サポート 是非使ってください！ 41
42. Copyright © Fixstars Group Thank you! お問い合わせ窓口 : hr-seminar@fixstars.com