コンピュータービジョンセミナー5 / 3次元復元アルゴリズム Multi-View Stereo の CUDA高速化

2024年8月7日に開催した「コンピュータビジョンセミナーvol.5～3次元復元アルゴリズム Multi-View Stereo の CUDA高速化～」の当日資料です。

Transcript

1. Copyright © Fixstars Group コンピュータービジョンセミナーvol.5 3次元復元アルゴリズム Multi-View Stereo の CUDA高速化
2. Copyright © Fixstars Group 本日のAgenda ⚫ はじめに ⚫ Multi-View Stereo の概要 ⚫ PatchMatch MVS のアルゴリズム ⚫ PatchMatch MVS の CUDA 高速化 ⚫ Q&A / 告知 1
3. Copyright © Fixstars Group はじめに 2
4. Copyright © Fixstars Group ⚫ 弊社でサービス展開しているコンピュータビジョン領域での様々な技術情報を、 コンピュータビジョンセミナーとして発信しています ⚫ Vol.1 OpenCVでCUDAを活用するためのGpuMat解説 ⚫ Vol.2 視差計算ライブラリ libSGM のアルゴリズム解説 ⚫ Vol.3 視差計算を利用した障害物検出 ⚫ Vol.4 Visual SLAM / SfM で行われる局所特徴量計算の CUDA高速化 ⚫ Vol.5 3次元復元アルゴリズム Multi-View Stereo の CUDA 高速化 ⚫ こんな方に向いています ◦ 3次元復元アルゴリズムのトレンドを知りたい ◦ 実用的なアルゴリズムの GPU 高速化事例を知りたい 本講演の位置づけ 3
5. Copyright © Fixstars Group 発表者紹介 冨田 明彦 ソリューションカンパニー 営業企画 2008年に入社。金融、医療業界において、ソ フトウェア高速化業務に携わる。その後、新規 事業企画、半導体業界の事業を担当し、現職。 4 高木 章洋 ソリューション第二事業部 エグゼクティブエンジニア 2014年に新卒入社。自動運転向けの画像認識 アルゴリズムの開発、高速化などに携わる。 OSS活動として、libSGMの開発にも携わる。
6. Copyright © Fixstars Group フィックスターズの ご紹介 5
7. Copyright © Fixstars Group フィックスターズの強み コンピュータの性能を最大限に引き出す、ソフトウェア高速化のエキスパート集団 ハードウェアの知見 アルゴリズム実装力 各産業・研究分野の知見 6 目的の製品に最適なハードウェアを見抜き、 その性能をフル活用するソフトウェアを開 発します。 ハードウェアの特徴と製品要求仕様に合わ せて、アルゴリズムを改良して高速化を実 現します。 開発したい製品に使える技術を見抜き、実 際に動作する実装までトータルにサポート します。
8. Copyright © Fixstars Group サービス概要 お客様専任のエンジニアが直接ヒアリングを行い、高速化を実現するために乗り越えるべき 課題や問題を明確にしていきます。 高速化のワークフロー コンサルティング 先行技術調査 性能評価・ボトルネックの特定 高速化 アルゴリズムの改良・開発 ハードウェアへの最適化 レポート作成 サポート レポートやコードへのQ&A 実製品への組込み支援 7 高速化したコード オリジナルソースコードのご提供 お客様
9. Copyright © Fixstars Group サービス提供分野 8 半導体 自動車 産業機器 生命科学 金融 • NAND型フラッシュメモリ向け ファームウェア開発 • 次世代AIチップの開発環境基盤 • 自動運転の高性能化、実用化 • 次世代パーソナルモビリティの 研究開発 • Smart Factory実現への支援 • マシンビジョンシステムの高速化 • ゲノム解析の高速化 • 医用画像処理の高速化 • AI画像診断システムの研究開発 • デリバティブシステムの高速化 • HFT(アルゴリズムトレード)の高速化
10. Copyright © Fixstars Group サービス領域 様々な領域でソフトウェア高速化サービスを提供しています。大量データの高速処理は、 お客様の製品競争力の源泉となっています。 9 組込み高速化 画像処理・ アルゴリズム開発 分散並列システム開発 GPU向け高速化 FPGAを活用した システム開発 量子コンピューティング AI・深層学習 自動車向け ソフトウェア開発 フラッシュメモリ向け ファームウェア開発
11. Copyright © Fixstars Group 画像処理アルゴリズム開発 高速な画像処理需要に対して、経験豊富なエンジニアが 責任を持って製品開発をご支援します。 お客様の課題 高度な画像処理や深層学習等のアルゴリズム を開発できる人材が社内に限られている 機能要件は満たせそうだが、ターゲット機器 上で性能要件までクリアできるか不安 製品化に結びつくような研究ができていない ご支援内容 深層学習ネットワーク精度の改善 様々な手法を駆使して深層学習ネットワークの精度を改善 論文調査・改善活動 論文調査から最先端の手法の探索 性能向上に向けた改善活動を継続 アルゴリズム調査・改変 課題に合ったアルゴリズム・実装手法を調査 製品実装に向けて適切な改変を実施 10
12. Copyright © Fixstars Group GPU向け高速化 高性能なGPUの本来の性能を十分に引き出し、 ソフトウェアの高速化を実現します。 お客様の課題 GPUで計算してみたが期待した性能が出ない GPU/CPUを組み合わせた全体として最適な設 計がしたい ご支援内容 GPU高速化に関するコンサルティング CPU・GPU混在環境でのシステム設計 アルゴリズムのGPU向け移植 GPUプログラム高速化 継続的な精度向上 原価を維持したまま機能を追加するため、も う少し処理を速くしたい 品質確保のため、精度を上げたく演算量は増 えるが性能は維持したい 11
13. Copyright © Fixstars Group 1. Multi-View Stereoの概要 12
14. Copyright © Fixstars Group Multi-View Stereoとは ⚫ 複数枚の画像から被写体の3次元モデルを復元する技術 ◦ 特にカメラ姿勢の推定までをSfM、それ以降をMVSとして扱うことが多い 13 SfM/MVSのパイプライン (図は[1]より引用) Structure from Motion(SfM) • 入力画像群から、元のカメラ姿勢を推定 Multi View Stereo(MVS) • 入力画像群と、対応するカメラ姿勢をもとに、 被写体の3次元構造を復元 • 必要に応じて被写体の質感も再現
15. Copyright © Fixstars Group 狭義のMulti-View Stereo ⚫ MVSのパイプライン前段では密な点群生成を行う処理があり、 これを指してMVSと呼ぶこともある 14 入力画像群 Feature Extraction Feature Matching Relateve Poses Reconstruction Bundle Adjustment カメラ姿勢+疎な点群 密な点群生成 メッシュ化 レンダリング 精緻な3Dモデル SfM MVS 狭義のMVS SfM/MVSのパイプライン詳細
16. Copyright © Fixstars Group SfM/MVSのライブラリとPatchMatch ⚫ SfMやMVS向けに様々なライブラリが公開されている ⚫ MVSライブラリの多くが、密な点群生成においてPatchMatchを採用 ⚫ 本セミナーでは、PatchMatch MVSについて解説 15 ライブラリ URL SfM MVS (dense | mesh) openMVG https://github.com/openMVG/openMVG 〇 openMVS https://github.com/cdcseacave/openMVS 〇 (PM,SGM) 〇 COLMAP https://github.com/colmap/colmap 〇 〇 (PM) 〇 OpenSfM https://github.com/mapillary/OpenSfM 〇 〇 (PM) 〇 geogram https://github.com/BrunoLevy/geogram 〇 SfM/MVSのライブラリとサポート機能 PM：PatchMatch SGM：Semi-Global Matching
17. Copyright © Fixstars Group 【参考】深層学習系のアプローチ ⚫ 深層学習ベースのMVSも近年研究されている ⚫ 特徴抽出の能力に優れており、精度面では古典手法を上回るとされる ◦ 一方で大量のGPUメモリを必要とし、高解像度データの扱いが困難 16 MVSアルゴリズムと性能分布 (図はAPD[6]より引用) 深層学習系 PatchMatchなどの古典系 ETH3D：高解像度データセット
18. Copyright © Fixstars Group 【参考】3D Gaussian Splatting ⚫ SfMの結果から、精緻かつ高速なレンダリングを行う技術 ◦ https://repo-sam.inria.fr/fungraph/3d-gaussian-splatting/ ◦ MVSと似ているが、点群やメッシュを経由せずにレンダリングする点が異なる ⚫ 近年、3D Gaussian Splattingを3D復元に応用する手法も登場 ◦ SuGaR[10]：https://anttwo.github.io/sugar/ 17 SuGaRのデモ(図は[10]より引用) A,B,Cの各シーンを3D復元し、B,CをAに合成 (ロボットのポーズも編集) A B C
19. Copyright © Fixstars Group 2. PatchMatch MVSの アルゴリズム 18
20. Copyright © Fixstars Group デプスマップ推定型MVS ⚫ 入力データ中の各視点のデプスマップを推定 ⚫ デプスをグローバルな座標系に復元後、統合することで密な点群を生成 19 入力画像 デプスマップ 点群復元結果
21. Copyright © Fixstars Group デプスマップ推定の原理 1. 参照視点の注目画素における点を、その画素のデプス値を用いて逆投影 2. 1.の点を近傍視点に投影し、画像上でマッチングコストを計算 3. コスト最小化により最適なデプス値を推定 20 参照視点のデプスマップ 逆投影 投影 注目画素 マッチングコスト計算 視点間の座標変換 • 参照視点：デプスマップ推定の対象である視点 • 近傍視点：参照視点と一定の視野を共有する視点 • マッチングコスト：画素間の見た目の相違度
22. Copyright © Fixstars Group PatchMatch MVS ⚫ PatchMatch：ランダム性を利用した、画像マッチング(対応点探索)手法 ⚫ MVSでは次のような処理から構成される 21 Z11 Z12 Z13 Z14 Z15 Z21 Z22 Z23 Z24 Z25 Z31 Z32 Z33 Z34 Z35 Z41 Z42 Z43 Z44 Z45 Z51 Z52 Z53 Z54 Z55 C11 C12 C13 C14 C15 C21 C22 C23 C24 C25 C31 C32 C33 C34 C35 C41 C42 C43 C44 C45 C51 C52 C53 C54 C55 Zij ← rand(Zmin ,Zmax ) Cij ← cost(i,j,Zij ) Z11 Z12 Z13 Z14 Z15 Z21 Z22 Z23 Z24 Z25 Z31 Z32 Z33 Z34 Z35 Z41 Z42 Z43 Z44 Z45 Z51 Z52 Z53 Z54 Z55 C’33 ← cost(3,3,Z22 ) if C’33 < C33 then Z33 ← Z22 C33 ← C’33 endif ステップ1：ランダム初期化 • デプスマップを乱数で初期化 • 各デプスに対応する初期コストを計算 ステップ2：モデル伝搬 • 注目画素に対し、ある近傍画素を参照 • 近傍画素のデプス値を用いて、注目画素に おけるコストを計算 • 注目画素のコストと比較して小さい場合、 注目画素のデプスを近傍の値に置き換え ステップ3：ランダム改善 • 注目画素のデプスに対し、乱数を用いて 小さい変更を与える • 変更後のデプスに対するコストを評価し、 コストが減少したらデプス値を置き換える Z11 Z12 Z13 Z14 Z15 Z21 Z22 Z23 Z24 Z25 Z31 Z32 Z33 Z34 Z35 Z41 Z42 Z43 Z44 Z45 Z51 Z52 Z53 Z54 Z55 Z’33 ← Z33 + rand(-ΔZ,+ΔZ) C’33 ← cost(3,3,Z’33 ) if C’33 < C33 then Z33 ← Z’33 C33 ← C’33 endif デプスマップ コストマップ ステップ2,3を指定回数繰り返し ※以降はステップ2,3をまとめてモデル更新と呼ぶことがあります
23. Copyright © Fixstars Group PatchMatch MVS ⚫ PatchMatch MVSによるデプスマップ推定の例 22 デプスマップ コストマップ ランダム初期化 モデル更新1回目 モデル更新2回目 モデル更新3回目
24. Copyright © Fixstars Group PatchMatch MVSの要素技術の紹介 ⚫ マッチングコストとHomography変換 ⚫ コスト集約と視点選択 ⚫ モデル伝搬と並列化 ⚫ Textureless領域への対応 ⚫ MVSの評価 23
25. Copyright © Fixstars Group マッチングコストと Homography変換 24
26. Copyright © Fixstars Group マッチングコストの基本 ⚫ 視点間の座標変換により、2視点の対応点を算出 ⚫ 対応点におけるパッチ(小領域)間の類似度をもとにコストを計算 ◦ PatchMatch MVSでは、入力画像をグレースケールに変換した上で、パッチ間の ゼロ平均正規化相互相関(ZNCC)を計算し、マッチングコストに利用することが多い 25 マッチングコスト計算 対応点におけるパッチ 逆投影 投影 視点間の座標変換
27. Copyright © Fixstars Group 画素間の対応 ⚫ 撮像元のカメラ配置によって、対応するパッチの見た目は大きく変化 ⚫ 類似度計算にあたり、パッチ内の画素を正しく対応させる必要がある 26
28. Copyright © Fixstars Group Homography変換 ⚫ パッチ内の各点は、局所平面 𝑿, 𝒏 上にあるとしてモデル化 ⚫ 平面から導かれるHomography変換※により、画素位置を対応付ける ◦ 𝑯 = 𝑲′ 𝑹 − 𝒕𝒏𝑇 𝒏𝑇𝑿 𝑲−1 ◦ 𝒑′′ = 𝑯𝒑 = 𝑥′′, 𝑦′′, 𝑤′′ 𝑇 ◦ 𝒑′ = 𝑥′, 𝑦′, 1 𝑇 = 1 𝑤′′ 𝒑′′ 27 𝒏：法線ベクトル 𝑿 = 𝑋, 𝑌, 𝑍 ：3D点 𝑪 𝑯 𝒑 = 𝑥, 𝑦, 1 T ※これをplane-induced Homographyと呼ぶ 導出はHomography (computer vision)[11]などを参照のこと 𝒑′ = 𝑥′, 𝑦′, 1 T 𝑪′ 参照視点画像 近傍視点画像 局所平面 変数 意味 𝑪, 𝑪′ 参照視点および近傍視点のカメラ 𝑲, 𝑲′ 𝑪, 𝑪′のカメラ行列(内部パラメータ) 𝑿, 𝒏 注目画素に対応する𝑪座標系の3D点と法線ベクトル 𝒑, 𝒑′ 平面 𝑿, 𝒏 上の3D点を𝑪, 𝑪′に投影した点 𝑹, 𝒕 𝑪座標系の3D点を𝑪′座標系に移す剛体変換(回転+並進) 𝑿′ = 𝑹𝑿 + 𝒕
29. Copyright © Fixstars Group 法線の推定 ⚫ 前述のHomography変換を計算するためには、各点の法線ベクトルが必要 ⚫ →法線ベクトルも未知数(モデルの変数)として、デプスと同時に推定 ◦ デプスと同様に、ランダム初期化・モデル伝搬・ランダム改善を適用 ◦ 以降はデプス𝑍と法線ベクトル𝒏の組𝜽 = 𝑍: 𝒏 を平面モデルと呼ぶ 28 デプスマップ 法線マップ
30. Copyright © Fixstars Group マッチングコスト計算の流れを整理 ⚫ 注目画素における平面モデル𝜽 = 𝑍: 𝒏 を評価したい ⚫ 𝑿 = 𝑋, 𝑌, 𝑍 と𝒏からHomography行列𝑯を計算 ⚫ 参照視点のパッチ内の各点𝒑𝑖 について、近傍視点中の対応点𝒑′𝑖 を計算 ⚫ 対応点における輝度値をサンプリング ◦ 𝒔 = 𝐼 𝒑1 , 𝐼 𝒑2 , … , 𝐼 𝒑𝑘 ◦ 𝒔′ = 𝐼′ 𝒑′1 , 𝐼′ 𝒑′2 , … , 𝐼′ 𝒑′𝑘 ⚫ 輝度ベクトル間のZNCCからマッチングコストを計算 ◦ 𝑚 𝜽 = 1 − ZNCC 𝒔, 𝒔′ ◦ ↑相関係数+1のときコスト0となるように 29
31. Copyright © Fixstars Group Bilateral重みづけによるZNCC ⚫ パッチ内には注目画素が属する対象物の他、それとは関係のない背景などが 含まれることがあり、これらは類似度計算においてノイズとなる ⚫ そこで、ZNCCを計算する際に画素位置毎にBilateral重みを設定することで、 対象物の寄与度を向上させる ◦ ZNCC = σ𝑖 𝑤𝑖 𝑠𝑖− ҧ 𝑠 𝑠′𝑖−ഥ 𝑠′ σ 𝑖 𝑤𝑖 𝑠𝑖− ҧ 𝑠 2 σ 𝑖 𝑤𝑖 𝑠′𝑖−ഥ 𝑠′ 2 ◦ 𝑤𝑖 = exp − ∆𝑔2 2𝜎𝑔 2 − ∆𝑓2 2𝜎𝑓 2 30 ∆𝑔：パッチ中心からの距離 ∆𝑔 = 𝑑𝑥2 + 𝑑𝑦2 ∆𝒇 ：パッチ中心における輝度𝒔𝒄 と𝒔𝒊 との差 ∆𝑓 = 𝑠𝑖 − 𝑠𝑐
32. Copyright © Fixstars Group Bilateral重みづけによるZNCC ⚫ Bilateral重みづけによるZNCCの実装例 31 const float fc = I1(xc, yc); float s12 = 0, s11 = 0, s22 = 0, s1 = 0, s2 = 0, sw = 0; for (int dy = -PATCH_RADIUS; dy <= PATCH_RADIUS; dy += SAMPLE_STEP) { for (int dx = -PATCH_RADIUS; dx <= PATCH_RADIUS; dx += SAMPLE_STEP) { const int x1 = cx + dx; const int y1 = cy + dy; const auto [x2, y2] = homographyTransform(x1, y1, H); const float f1 = I1(x1, y1); const float f2 = I2(x2, y2); const float w = calcBilateralWeight(dx, dy, f1 - fc); s12 += w * f1 * f2; s11 += w * f1 * f1; s22 += w * f2 * f2; s1 += w * f1; s2 += w * f2; sw += w; } } ...以下略...
33. Copyright © Fixstars Group コスト集約と視点選択 32
34. Copyright © Fixstars Group 近傍視点とマッチングコストの集約 ⚫ これまで近傍視点を1つに限定して説明してきたが、実際には一つの 参照視点につき複数の近傍視点を割り当てる ◦ マッチングの信頼性を向上させるため ◦ 近傍視点の割り当て方法としては、前段のSfMで得られた疎な点群(特徴点)を利用し、 一定数の特徴点を共有する他の視点を最大N個まで採用する、などがある ⚫ 複数の近傍視点に対して計算したマッチングコストは総和や平均をとるなど して、集約(aggregation)する ◦ 𝑚agg 𝜽 = 1 𝑁 σ𝑖∈𝑁 𝑚𝑖 𝜽 ◦ 𝑁は近傍視点のインデックス集合 33 一定の視野を共有する視点の集合
35. Copyright © Fixstars Group 視点選択(View Selection) ⚫ ある注目画素では、対応するパッチが別の物体で隠れたり(オクルージョン)、 画像範囲外となることで、近傍視点中に存在しないことがある ⚫ このような場合のマッチングコストは、集約の際にノイズとなる ⚫ これを避けるため、画素ごとに有効な近傍視点を選択することを、 視点選択(View Selection)と呼ぶ 34 オクルージョンの発生
36. Copyright © Fixstars Group 視点選択手法の例 ⚫ K-best selection (Gipuma[2]) ◦ 各視点に対するマッチングコストを小さい順にソートし、上位K件のコストで平均をとる ◦ 𝑚′1 , 𝑚′2 , … , 𝑚′ 𝑁 = sort 𝑚1 , 𝑚2 , … , 𝑚𝑁 ◦ 𝑚agg 𝜽 = 1 𝐾 σ𝑖=1 𝐾 𝑚′𝑖 𝜽 ⚫ Multi-Hypothesis Joint View Selection (ACMH[3]) ◦ 注目画素近傍から、8個の平面モデル𝜽1 , 𝜽2 , … , 𝜽8 を取得 ◦ 8 × 𝑁のコスト行列を作成し、各列に属するコストの値から、各視点の重み𝑤𝑖 を決定 ◦ 𝑚agg 𝜽 = 1 σ 𝑤𝑖 σ𝑖=1 𝑁 𝑤𝑖 𝑚𝑖 𝜽 35 𝑀 = 𝑚1,1 ⋯ 𝑚1,𝑁 ⋮ ⋱ ⋮ 𝑚8,1 ⋯ 𝑚8,𝑁 𝑤1 𝑤𝑁 視点の次元 平面候補(Hypothesis)の次元 Multi-Hypothesis Joint View Selectionの考え方 • 良い視点では、いくつかのモデルに対して低いコストをとる • 悪い視点では、どんなモデルに対しても高いコストをとる コスト行列
37. Copyright © Fixstars Group モデル伝搬と並列化 36
38. Copyright © Fixstars Group Propagation Scheme ⚫ 次の方針をPropagation Schemeと呼ぶ ◦ 近傍画素としてどの位置を参照するか ◦ 全画素をどのような順序で更新していくか ⚫ Gipuma以前の手法では、下図のようなシーケンシャルな伝搬が主流だった ◦ 現在の注目画素における伝搬は、直前の更新の結果に依存 ◦ 部分的に並列化できる手法はあっても、GPUの性能を十分には発揮できていなかった 37 シーケンシャル伝搬 (図は[8]より引用)
39. Copyright © Fixstars Group Red-Black伝搬 (Checkerboard伝搬) ⚫ 画像全体を赤画素・黒画素に分割し、1回の伝搬では片方の色のみを更新 ◦ 黒画素を更新する場合、近傍画素として赤画素から参照 ◦ 次の伝搬では赤画素・黒画素の役割を交代 ⚫ 画素間で処理の依存性がなく、GPUによる並列化と相性が良い 38 Red-Black伝搬 (図は[2]より引用)
40. Copyright © Fixstars Group Gipuma[2] の近傍参照パターン ⚫ 参照画素数が多い場合(下図b)、1回の伝搬で注目画素が改善される確率が 高くなるが、マッチングコストの計算回数は増加 ⚫ コストの計算回数を抑えつつ、効率的に良いモデルを見つけたい 39 Red-Black伝搬 (図は[2]より引用)
41. Copyright © Fixstars Group Adaptive Checkerboard Sampling (ACMH[3]) ⚫ 伝搬に用いる近傍画素を動的に探索 (下図c) ◦ 注目画素周辺に8つの小領域を定義 (薄赤色領域、黒画素は含まない) ◦ コストマップ内を探索し、小領域内で最もコストの小さい画素を選択 (黄色画素) ⚫ よい平面モデルを効率的に伝搬 40 (a) シーケンシャル (b) Symmetric Checkerboard (c) Adaptive Checkerboard 伝搬方法の比較 (図は[3]より引用)
42. Copyright © Fixstars Group ACMHにおけるモデル更新方法のまとめ ⚫ モデル伝搬 ◦ Adaptive Checkerboard Samplingにより、8つの候補モデル𝜽1 , 𝜽2 , … , 𝜽8 を取得 ◦ 各モデルと各視点の組に対しマッチングコストを計算し、コスト行列を作成 ◦ コスト行列から各視点の重みを計算し、マッチングコストを集約 ▪ 𝑚agg 𝜽𝑗 = 1 σ 𝑤𝑖 σ𝑖=1 𝑁 𝑤𝑖 𝑚𝑖 𝜽𝑗 ◦ 注目画素のモデル𝜽0 を含む全候補モデルの内、最小コストのものを伝搬 ▪ 𝜽best = argmin 𝑗∈ 0,1,2,…,8 𝑚agg 𝜽𝑗 ⚫ ランダム改善 ◦ 候補モデルをランダムに5つ生成 ◦ 5つの候補についてマッチングコストを計算し、コストが減少したら更新 41
43. Copyright © Fixstars Group Textureless領域への対応 42
44. Copyright © Fixstars Group Textureless領域の問題 ⚫ 輝度をベースとしたマッチングコスト(photometric consistency)では、 テクスチャレスな領域を識別できず、うまく3次元復元できない ⚫ テクスチャレスへ領域に対して様々なアプローチが提案されている 43 Textureless領域が多い画像 デプスマップ推定結果
45. Copyright © Fixstars Group Geometric Consistency ⚫ 事前に輝度ベースのPatchMatchで、各視点の中間的なデプスマップを作成 ⚫ 2視点のデプスマップを利用し、視点間の再投影誤差を計算 1. 𝒑2 = proj2←1 𝒑1 , 𝑍1 ← 𝜽 2. 𝒑′1 = proj1←2 𝒑2 , 𝑍2 ← 𝐷2 𝒑2 3. 𝑚geo 𝜽 = 𝒑1 − 𝒑′1 ⚫ 輝度ベースのマッチングコストと組み合わせる ◦ 𝑚 𝜽 = 𝑚potho 𝜽 + 𝑤geo 𝑚geo 𝜽 44 ① ② ③ 参照視点 近傍視点 Geometric Consistencyの重み
46. Copyright © Fixstars Group Multi-Scale PatchMatch ⚫ 画像を低解像度にダウンサンプルすることで、相対的にパッチ(視野)を拡大、 パッチ内に有効なテクスチャを含まれやすくする ⚫ 低解像度で推定したデプスマップは、アップサンプルして高解像度側の デプスマップ推定における初期値として利用 45 Multi-Scale PatchMatchの概略 (図は[3]より引用)
47. Copyright © Fixstars Group ACMM[3] ⚫ ACMHをベースとして、Geometric ConsistencyとMulti-Scaleを導入 46 ACMMの概略図 (図は[3]より引用) ※ ACMM：ACMH with multi-scale geometric consistency guidance (ACMM)
48. Copyright © Fixstars Group ACMM[3] ⚫ ACMMではTextureless領域の復元性能が良い 47 PatchMatchアルゴリズムの比較 (図は[3]より引用)
49. Copyright © Fixstars Group Planar Priorの導入 ⚫ Textureless領域が広範囲になると、ACMMでも対応しきれない ⚫ このような領域は壁や床など、平面と仮定できるケースが多く、 これを利用した改善手法がいくつか提案されている ⚫ 基本的なアプローチとしては以下の通り ◦ 各画素を、 Reliable(周辺にTextureがある)か、Unreliable(Textureless)かのどちらかに、 コストの値などを用いて分類 ◦ Unreliableな画素における平面モデルを、周囲のReliableな画素から補間 ◦ 補間した平面モデルをガイドとして、 輝度ベースのマッチングコストと組み合わせる 48
50. Copyright © Fixstars Group ACMP[4] ⚫ 従来型のPatchMatchを実行後、コストの値をもとにReliableな点を抽出 ⚫ Reliableな点群に対しドロネー三角形分割を適用 ◦ 三角形の頂点はReliable、三角形の内部はUnreliableという関係になっている ⚫ 頂点におけるデプスの値から三角形内部のデプス+法線を推定し、これを PatchMatchのガイドとして利用 49 デプス補間の概要 (図は[4]より引用)
51. Copyright © Fixstars Group Adaptive Patch Deformation (APD-MVS[6]) ⚫ 深層学習におけるDeformable Convolutionの考え方を輸入 ◦ Deformable Convolution：Convolution時の参照ユニットを動的に学習するCNN ⚫ Unreliableな画素に対し、周囲8点のReliableな画素を探索 ⚫ 同一の平面パラメータを8か所のReliableな位置におけるパッチで評価し、 これを従来のマッチングコストに組み込む 50 Adaptive Patch Deformationの概要 (図は[6]より引用)
52. Copyright © Fixstars Group Adaptive Patch Deformation (APD-MVS[6]) ⚫ Textureless領域で優れた復元性能を発揮 51 PatchMatchアルゴリズムの比較 (図は[6]より引用) ※ACMMP[5]：ACMPとMulti-Scaleを組み合わせた手法
53. Copyright © Fixstars Group MVSの評価 52
54. Copyright © Fixstars Group ETH3D benchmark[9] ⚫ MVS向けのデータセットおよび評価ツールを提供 53 facade office meadow pipes terrace relief
55. Copyright © Fixstars Group ETH3D benchmark[9] ⚫ Laser Scannerで計測した点群をGT(ground truth)として提供 ⚫ 評価指標は accuracy,completeness,F 1 score の3種類 ◦ accuracy ▪ 復元点を3種類の領域のいずれかに分類 • 緑：accurate、赤：inaccurate、青：unobserved (Laser視野外のため不問) ▪ accuracy = accurate点数 / (accurate点数 + inaccurate点数) ◦ completeness ▪ あるGT点q i をクエリとし、最近傍の復元点p i を検索 ▪ completeness = dist(p i ,q i ) ≦ threshold※を満たすq i の割合 ◦ F 1 score ▪ accuracy (precision) pとcompleteness (recall) r の調和平均 ▪ F 1 = (p×r)/(p+r) 54 accuracy評価用の領域 (図は[9]より引用) ※MVS手法の論文ではthresholdとして2[cm]や10[cm]が用いられる
56. Copyright © Fixstars Group F1 scoreを上げる方針 ⚫ accuracyの向上 ◦ Reliableな画素については、十分に伝搬を繰り返せばいずれ最適解に収束 ◦ Unreliableな画素はできるだけ復元しないようにする ⚫ completenessの向上 ◦ Textureless領域の復元性能を上げる ◦ デプスマップの解像度を大きくする ▪ GT点の数が多いため、復元する点群の密度を増やすだけで、ある程度completenessが向上する ▪ ETH3Dの入力画像サイズは24メガピクセル(6221×4146)程度で、原解像度のままデプスマップを 推定するのが理想的だが、処理時間やメモリの制約から、ある程度縮小するのが一般的 • PatchMatch系の論文では、6.5メガピクセル(3200×2130)程度に縮小 • 深層学習系ではGPUメモリを大量消費するため、さらに解像度を落とさざるを得ない 55
57. Copyright © Fixstars Group ETH3Dのスコア比較 ⚫ 現状は総合的にPatchMatchベースのAPDが優位 ⚫ 深層学習系は解像度の問題から、PatchMatchよりは劣る状況 56 画像解像度(ETHの原画像基準)とメモリ使用量 各MVSアルゴリズムのETH benchmark結果 (表はAPD[6]より引用)
58. Copyright © Fixstars Group 3. PatchMatch MVSの CUDA高速化 57
59. Copyright © Fixstars Group PatchMatch MVSのCUDA実装 ⚫ Gipumaをはじめとして、様々なCUDA実装のPatchMatch MVSが存在 ⚫ これらを参考にしつつも、基本的には1から実装を行った ◦ モデル更新はACMHをベースに実装 58 手法 発表年 実装言語 URL Gipuma 2015 C++/CUDA https://github.com/kysucix/gipuma ACMH/ACMM 2019 C++/CUDA https://github.com/GhiXu/ACMM ACMP 2020 C++/CUDA https://github.com/GhiXu/ACMP ACMMP 2022 C++/CUDA https://github.com/GhiXu/ACMMP HPM-MVS 2023 C++/CUDA https://github.com/CLinvx/HPM-MVS APD-MVS 2023 C++/CUDA https://github.com/whoiszzj/APD-MVS 既存のPatchMatch MVS実装
60. Copyright © Fixstars Group CUDAの簡単なおさらい ⚫ スレッドおよびメモリの階層 59 Fixstars CUDA高速化セミナーvol.1 ～画像処理アルゴリズムの高速化～ より引用 https://www.docswell.com/s/fixstars/K24MYM-20220527 スレッドの階層構造 • スレッド間に階層構造がある • 近いスレッド同士はより密に通信・同期を行うことができる メモリの階層構造 • おおむねスレッドの階層構造と対応
61. Copyright © Fixstars Group CUDA化の方針 ⚫ ランダム初期化～モデル更新をCUDA実装 ⚫ 以降はモデル更新に着目 60 デバイス上でランダム初期化～モデル更新 計算用データを デバイスメモリに転送 • 参照視点画像 • 近傍視点画像 • 視点間の座標変換情報 計算用結果を ホストメモリに転送 • デプスマップ • 法線マップ
62. Copyright © Fixstars Group スレッド割り当ての方針 ⚫ Red-Black伝搬を採用、1つの赤(黒)画素に1スレッドを割り当て ⚫ Thred Blockのサイズを16×16に設定 → 画像中の32×16の領域を担当 ◦ x方向には1画素おきにスレッドを割り当てるため、処理領域の幅は倍になる 61 16 16 Thread Block 32 16 x方向には1画素おきに スレッドを割り当て 入力画像
63. Copyright © Fixstars Group モデル更新のCUDA実装例 ⚫ カーネル関数及び、カーネル関数呼び出し 62 __global__ void propagateAndRefineACMHKernel(float* Z, Vec3f* N, float* C, int w, int h, int nviews, int color, float minZ, float maxZ, bool geom) { // checkerboardパターン(市松模様)となるようx,yを計算 const int x = 2 * (blockIdx.x * blockDim.x + threadIdx.x) + ((y % 2) ^ color); const int y = blockIdx.y * blockDim.y + threadIdx.y; if (x >= w || y >= h) return; MatchingCost MC(nviews, geom); // マッチングコスト計算クラス float viewWeights[MAX_VIEWS]; // コスト集約時の視点重み // モデル伝搬 propagateACMH(MC, Z, N, C, w, h, x, y, minZ, maxZ, viewWeights); // ランダム改善 Xorshift random(getRandomSeed(x, y, w)); // 乱数生成器 refineACMH(MC, Z, N, C, w, h, x, y, minZ, maxZ, viewWeights, random); } void propagateAndRefineACMH(GpuMat& depths, GpuMat& normals, GpuMat& costs, int nviews, int color, float minZ, float maxZ, bool geom) { const int w = depths.cols; const int h = depths.rows; const int npixelsX = w / 2; // x方向はw/2個の画素を更新 const int npixelsY = h; constexpr int BLOCK_SIZE = 16; const dim3 block(BLOCK_SIZE, BLOCK_SIZE); const dim3 grid(divUp(npixelsX, block.x), divUp(npixelsY, block.y)); auto Z = depths.ptr<float>(); auto N = normals.ptr<Vec3f>(); auto C = costs.ptr<float>(); propagateAndRefineACMHKernel<<<grid, block>>>(Z, N, C, w, h, nviews, color, minZ, maxZ, geom); CUDA_CHECK(cudaGetLastError()); } カーネル関数呼び出し モデル伝搬(ACMH)のカーネル関数
64. Copyright © Fixstars Group 1スレッドのタスク (ACMH再掲) ⚫ モデル伝搬 ◦ Adaptive Checkerboard Samplingにより、8つの候補モデル𝜽1 , 𝜽2 , … , 𝜽8 を取得 ◦ 各モデルと各視点の組に対しマッチングコストを計算し、コスト行列を作成 ◦ コスト行列から各視点の重みを計算し、マッチングコストを集約 ▪ 𝑚agg 𝜽𝑗 = 1 σ 𝑤𝑖 σ𝑖=1 𝑁 𝑤𝑖 𝑚𝑖 𝜽𝑗 ◦ 注目画素のモデル𝜽0 を含む全候補モデルの内、最小コストのものを伝搬 ▪ 𝜽best = argmin 𝑗∈ 0,1,2,…,8 𝑚agg 𝜽𝑗 ⚫ ランダム改善 ◦ 候補モデルをランダムに5つ生成 ◦ 5つの候補について伝搬と同様にコストを計算し、コストが減少したら更新 63
65. Copyright © Fixstars Group 処理のボトルネック ⚫ マッチングコスト計算(ZNCC)が最大のボトルネック ◦ モデル伝搬～ランダム改善で、多数の候補モデル𝜽を評価 ⚫ さらに要因を分類すると… ◦ メモリアクセス ▪ 輝度値のサンプリング時に、グローバルメモリへのアクセスが発生 ▪ 特に近傍視点側は参照位置のランダムアクセス性が高く、キャッシュヒット率も低 ▪ ↑に加えて参照位置が浮動小数点数となるため、バイリニア補間が必要 ◦ 演算 ▪ パッチ内の各画素に対するHomography変換には除算が含まれ、演算コスト大 ◦ Warp Divergence ▪ 画像の内外判定などの条件分岐によって有効な演算を行わないスレッドが発生 ▪ ワープ内での異なる方向への分岐は性能劣化につながる 64
66. Copyright © Fixstars Group 処理のボトルネック ⚫ ZNCC計算部のナイーブな実装例 65 for (int dy = -PATCH_RADIUS; dy <= PATCH_RADIUS; dy += SAMPLE_STEP) { for (int dx = -PATCH_RADIUS; dx <= PATCH_RADIUS; dx += SAMPLE_STEP) { const int x1 = cx + dx; const int y1 = cy + dy; if (x1 < 0 || x1 >= w1 || y1 < 0 || y1 >= h1) continue; const auto [x2, y2] = homographyTransform(x1, y1, H); if (x2 < 0 || x2 >= w2 || y2 < 0 || y2 >= h2) continue; const float f1 = I1[y1 * w1 + x1]; const float f2 = sampleBilinear(I2, w2, h2, x2, y2); const float w = calcBilateralWeight(dx, dy, f1 - fc); s12 += w * f1 * f2; s11 += w * f1 * f1; s22 += w * f2 * f2; s1 += w * f1; s2 += w * f2; sw += w; } } Homography変換 • 除算が発生 メモリアクセス • グローバルメモリへのアクセスが発生 • 近傍視点側はバイリニア補間が必要 Warp Divergence • ワープ内のスレッドが異なる 方向に分岐する可能性
67. Copyright © Fixstars Group Shared Memoryの使用 ⚫ Shared Memory ◦ Thread Block内で共有可能な、64KB～100KB程度の高速なメモリ ⚫ 参照画像については、同じ画素に繰り返しアクセスするため、データをあら かじめShared Memoryに保持 ⚫ 近傍画像については、アクセス位置が事前に分からないため、利用を断念 66 16 16 Thread Block 32+Δ 16+Δ 参照画像 パッチサイズの分、拡張した領域をコピー
68. Copyright © Fixstars Group Texture Fetchingの使用 ⚫ Texture Fetchingとは ◦ GPUのテクスチャユニットを使用した、画像データへのアクセス方法 (詳細は次頁) ⚫ CUDAからはTexture Objectを介して利用 67 // 画像サイズやデバイスメモリの情報を設定 cudaResourceDesc resDesc; memset(&resDesc, 0, sizeof(cudaResourceDesc)); resDesc.resType = cudaResourceTypePitch2D; resDesc.res.pitch2D.devPtr = image.data; resDesc.res.pitch2D.height = image.rows; resDesc.res.pitch2D.width = image.cols; resDesc.res.pitch2D.pitchInBytes = image.step; resDesc.res.pitch2D.desc = cudaCreateChannelDesc<uchar>(); // Texture Fetchingの設定 cudaTextureDesc texDesc; memset(&texDesc, 0, sizeof(cudaTextureDesc)); texDesc.addressMode[0] = addressMode; texDesc.addressMode[1] = addressMode; texDesc.addressMode[2] = addressMode; texDesc.filterMode = filterMode; texDesc.readMode = readMode; texDesc.normalizedCoords = 0; // Texture Objectの作成 cudaTextureObject_t textureObject; cudaCreateTextureObject(&textureObject, &resDesc, &texDesc, NULL); __device__ inline float sampleTex(cudaTextureObject_t obj, float x, float y) { return tex2D<float>(obj, x + 0.5f, y + 0.5f); } Texture Objectの作成 (ホスト側処理) Texture Fetching (デバイス側処理) • tex2D<T>を用いてデータを取得、座標はfloatで指定 • 整数座標における1ピクセルはfloat座標で0~1の範囲をとる • 整数座標上の(x,y) は、float座標上で(x+0.5,y+0.5) と対応
69. Copyright © Fixstars Group Texture Fetchingの使用 ⚫ Texture Fetchingのメリット ◦ Textureキャッシュが働き、局所的な2Dアクセスの効率が向上 ▪ ただし最近のGPUではL1キャッシュとTextureキャッシュは統合されており(unified L1/Texture cache)、同等の効果を自動的にL1キャッシュでまかなえることも多い ◦ Filter Mode機能 ▪ データ取得時の補間方法を指定可能 ▪ cudaFilterModeLinearを設定することで、バイリニア補間を利用可能 ◦ Address Mode機能 ▪ 画像範囲外アクセス時のアドレッシング方法を指定可能 (Wrap,Clamp,Mirror,Border) ▪ 画像の内外判定が不要に ⚫ これらメリットから、近傍画像へのアクセスにはTexture Fetchingを使用 68
70. Copyright © Fixstars Group Homography変換の近似 ⚫ Homography変換式 ◦ 𝑥′ = ℎ11𝑥+ℎ12𝑦+ℎ13 ℎ31𝑥+ℎ32𝑦+ℎ33 , 𝑦′ = ℎ21𝑥+ℎ22𝑦+ℎ23 ℎ31𝑥+ℎ32𝑦+ℎ33 ⚫ ここでは𝑥′の計算に着目、𝑦を固定し変換式を𝑥の関数とみなす ◦ 𝑥′ = 𝑓 𝑥 = 𝑢 𝑥 𝑤 𝑥 ⚫ これをパッチ中心𝑐𝑥 の周りで1次近似 ◦ 𝑓 𝑥 ≃ 𝑓 𝑐𝑥 + 𝑓′ 𝑐𝑥 𝑥 − 𝑐𝑥 = 𝑏𝑥 + 𝑎𝑥 𝑑𝑥 ◦ 𝑏𝑥 = 𝑓 𝑐𝑥 , 𝑎𝑥 = 𝑓′ 𝑐𝑥 = 𝑢′ 𝑐𝑥 𝑤 𝑐𝑥 −𝑢 𝑐𝑥 𝑤′ 𝑐𝑥 𝑤 𝑐𝑥 2 , 𝑑𝑥 = 𝑥 − 𝑐𝑥 ⚫ 𝑥に関するループ内の除算を回避 69
71. Copyright © Fixstars Group ZNCC計算の実装例 ⚫ 高速化前後の比較 70 for (int dy = -PATCH_RADIUS; dy <= PATCH_RADIUS; dy += SAMPLE_STEP) { const float ax, bx = ...; const float ay, by = ...; for (int dx = -PATCH_RADIUS; dx <= PATCH_RADIUS; dx += SAMPLE_STEP) { const int x1 = cx + dx; const int y1 = cy + dy; const float x2 = ax * dx + bx; const float y2 = ay * dy + by; const float f1 = fetchFromShared(x1, y1, ...); const float f2 = fetchFromTexture(x2, y2, ...); const float w = calcBilateralWeight(dx, dy, f1 - fc); s12 += w * f1 * f2; s11 += w * f1 * f1; s22 += w * f2 * f2; s1 += w * f1; s2 += w * f2; sw += w; } } for (int dy = -PATCH_RADIUS; dy <= PATCH_RADIUS; dy += SAMPLE_STEP) { for (int dx = -PATCH_RADIUS; dx <= PATCH_RADIUS; dx += SAMPLE_STEP) { const int x1 = cx + dx; const int y1 = cy + dy; if (x1 < 0 || x1 >= w1 || y1 < 0 || y1 >= h1) continue; const auto [x2, y2] = homographyTransform(x1, y1, H); if (x2 < 0 || x2 >= w2 || y2 < 0 || y2 >= h2) continue; const float f1 = I1[y1 * w1 + x1]; const float f2 = sampleBilinear(I2, w2, h2, x2, y2); const float w = calcBilateralWeight(dx, dy, f1 - fc); s12 += w * f1 * f2; s11 += w * f1 * f1; s22 += w * f2 * f2; s1 += w * f1; s2 += w * f2; sw += w; } } 高速化前 高速化後 Sharedメモリの使用 • 参照画像の読み込みを 高速化 Texture Fetching • バイリニア補間 • 内外判定の除外 Homography変換の近似 • ループ内の除算を回避
72. Copyright © Fixstars Group 処理時間計測 ⚫ 計測環境 ⚫ 計測結果 71 計測項目 ナイーブ実装 高速化後 処理時間 312.3[msec] 110.0[msec] Compute Throughput 68.2[%] 66.3[%] Memory Throughput 45.5[%] 84.1[%] Avg. Divergent Branches 40216.5 7244.2 GPU GeForce RTX 3080 入力画像 ETH3Dデータセットのofficeシーン (参照画像はDSC_0219.JPG) 画像サイズ 1600×1066にリサイズ 視点数 21視点(参照1 + 近傍20) 計測区間 ランダムな初期状態※1から、モデル更新(赤画素+黒画素)×3反復の時間を計測 ※1 デプスがランダムの時、画像内外判定による分岐が発生しやすい ナイーブ実装から 3倍程度高速化 ※2 ※2 NVIDIA Nsight Computeで取得した各種指標から抜粋 (計6回のカーネル実行の平均)
73. Copyright © Fixstars Group Compute Throughputが十分に上がらない要因 ⚫ レジスタ大量使用によるOccupancy(GPU利用率)低下 ◦ GPUのStreaming Multiprocessor(Thread Blockが割り当てられる演算ユニット)には レジスタ数の上限がある ◦ 1スレッドが多くのレジスタを使用すると、相対的に同時実行可能なスレッド数が減少 ⚫ レジスタ数の制限 ◦ CUDAのコンパイルオプションで、 1スレッドが使用するレジスタ数を制限できる ◦ Occupancyは改善できるが、レジスタに乗らない変数はLocal Memoryに退避され メモリアクセスが増加するため、トレードオフの関係にある ◦ レジスタ数の制限も試してみたが、現時点では 効果が見られていない 72
74. Copyright © Fixstars Group 今後の予定 ⚫ アルゴリズム開発 ◦ 今回はACMMと同等の機能まで実装 ◦ 今後はPlane Priorの導入など、Textureless領域に対応したい ⚫ ソースコードの公開 ◦ ACMM系より高速で使いやすいライブラリを目指しています 73
75. Copyright © Fixstars Group 参考文献 [1] Furukawa, Yasutaka, and Carlos Hernández. "Multi-view stereo: A tutorial." Foundations and Trends® in Computer Graphics and Vision 9.1-2 (2015): 1-148. [2] Galliani, Silvano, Katrin Lasinger, and Konrad Schindler. "Massively parallel multiview stereopsis by surface normal diffusion." Proceedings of the IEEE international conference on computer vision. 2015. [3] Xu, Qingshan, and Wenbing Tao. "Multi-scale geometric consistency guided multi-view stereo." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2019. [4] Xu, Qingshan, and Wenbing Tao. "Planar prior assisted patchmatch multi-view stereo." Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 07. 2020. [5] Xu, Qingshan, et al. "Multi-scale geometric consistency guided and planar prior assisted multi-view stereo." IEEE Transactions on Pattern Analysis and Machine Intelligence 45.4 (2022): 4945-4963. [6] Wang, Yuesong, et al. "Adaptive patch deformation for textureless-resilient multi-view stereo." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023. [7] Ren, Chunlin, et al. "Hierarchical prior mining for non-local multi-view stereo." Proceedings of the IEEE/CVF International Conference on Computer Vision. 2023. [8] Zheng, Enliang, et al. "Patchmatch based joint view selection and depthmap estimation." Proceedings of the IEEE conference on computer vision and pattern recognition. 2014. [9] Schops, Thomas, et al. "A multi-view stereo benchmark with high-resolution images and multi-camera videos." Proceedings of the IEEE conference on computer vision and pattern recognition. 2017. [10] Guédon, Antoine, and Vincent Lepetit. "Sugar: Surface-aligned gaussian splatting for efficient 3d mesh reconstruction and high-quality mesh rendering." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024. [11] https://en.wikipedia.org/wiki/Homography_(computer_vision) 74
76. Copyright © Fixstars Group Thank you! お問い合わせ窓口 : hr-seminar@fixstars.com 7 5