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

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

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

はじめに Copyright © Fixstars Group

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

• https://speakerdeck.com/fixstars/computer-vision-seminar-1/

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

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

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

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

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

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

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

Semi-Global Matching Copyright © Fixstars Group

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

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

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

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

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

最適化の原理：グラフを使った説明 ● スキャンライン上の画素と、視差候補によって作られるグラフを考える ● スキャンライン方向にグラフを横断するとき、コスト和最小となる経路は？ スキャンラインの方向 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

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

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

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

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

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

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

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

SGMのCUDA実装 Copyright © Fixstars Group

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

• https://speakerdeck.com/fixstars/cudagao-su-hua-seminavol-dot-1-hua-xiang-chu-li-arugorizumufalsegao-su-hua

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

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

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

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

• https://github.com/dhernandez0/sgm

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

• https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#arithmetic-instructions

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

(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

(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

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

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

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

評価結果 ● 計測環境 ○ 画像サイズ：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

• https://developer.nvidia.com/embedded/visionworks

libSGMの紹介 Copyright © Fixstars Group

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

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