Variational Surface Reconstruction Using Natural Neighbors (SIGGRAPH 2025)

- 法線が未知の点群を入力として、高品質な3Dサーフェスを復元する方法
- 同グループによる2019年の論文では点群サイズをnとしてO(n^3)の計算コストだったのを、今回実質的にO(n)にしたことで、大規模点群にスケール可能になった
- 点群に対してドロネー三角形分割を行い、その1-ring近傍（Natural Neighbor）を局所的な部分集合として、部分集合ごとに補間関数を構築し、それを混ぜ合わせる、というのが基本アイディア
- 法線推定のための他の最新手法と比較して、優れていることを示した

Transcript

1. 第2回Spatial AI勉強会 Variational Surface Reconstruction Using Natural Neighbors (SIGGRAPH 2025 Journal Track) 高山 健志 (CyberAgent) 2025年6月29日 Project: https://jjxia81.github.io/NN-VIPSS-Project/ Paper: https://jjxia81.github.io/NN-VIPSS-Project/static/pdfs/Fast_VIPSS.pdf Code: https://github.com/jjxia81/NN-VIPSS Jianjun Xia & Tao Ju Washington University in Saint Louis
2. ハイレベルな概要 VIPSS (SIGGRAPH 2019) 𝑂(𝑛!) の計算コスト è スケールしない 😢 NN-VIPSS (SIGGRAPH 2025) 𝑂(∑"#$ % 𝑛" !) の計算コスト è スケールする 🤩 Natural Neighbor 目的: 法線無し点群から高品質な3Dサーフェスを復元 ( 𝑛! ≃ 30 )
3. 前提知識その1: Hermite RBFによる値と勾配の補間
4. 3D復元のよくあるシナリオ 1. 入力は法線付き点群 • 位置: 𝐱" ∈ ℝ! • 法線: 𝐠" ∈ ℝ! 𝑖 ∈ 1, … , 𝑛 2. 値と勾配の制約 𝑓 𝐱" = 0 𝛁𝑓 𝐱" = 𝐠" を満たす関数 𝑓: ℝ! → ℝ を求める 3. 𝑓 のゼロ等値面を抽出 • “Scattered data interpolation” と呼ばれる問題 • これを解く道具の一つが、Hermite RBF Radial Basis Function
5. 3D復元のよくあるシナリオ 1. 入力は法線付き点群 • 位置: 𝐱" ∈ ℝ* • 法線: 𝐠" ∈ ℝ* 𝑖 ∈ 1, … , 𝑛 2. 値と勾配の制約 𝑓 𝐱" = 𝑠" 𝛁𝑓 𝐱" = 𝐠" を満たす関数 𝑓: ℝ" → ℝ を求める 3. 𝑓 のゼロ等値面を抽出 • “Scattered data interpolation” と呼ばれる問題 • これを解く道具の一つが、Hermite RBF Radial Basis Function
6. Hermite RBF: 式の形 • 関数を、基底関数とその勾配の重ね合わせで表す 𝜙 𝐱 = 𝐱 ! 𝑓 𝐱 = ∑+ 𝑎+𝜙(𝐱 − 𝐱+) + ∑+ 𝐛+ ,𝛁𝜙 𝐱 − 𝐱+ + 𝐩,𝐱 + 𝑞 𝛁𝑓 𝐱 = ∑+ 𝑎+𝛁𝜙(𝐱 − 𝐱+) + ∑+ ∇-𝜙 𝐱 − 𝐱+ 𝐛+ + 𝐩 • 値と勾配の制約から、未知係数を求める 𝑓 𝐱" = 𝑠" 𝛁𝑓 𝐱" = 𝐠" ∀𝑖 ∈ 1, … , 𝑛 𝑎" ∈ ℝ 𝐛" ∈ ℝ# 𝐩 ∈ ℝ# 𝑞 ∈ ℝ 未知係数 𝜙のヘッセ行列 ℝ!×!
7. Hermite RBF: 値の制約 𝑓 𝐱! = ∑" 𝑎"𝜙!," + ∑" 𝐛" $𝛁𝜙!," + 𝐩$𝐱! + 𝑞 = 𝑠! ∀𝑖 ∈ 1, … , 𝑛 𝜙$,$ 𝜙$,& 𝛁𝜙$,$ ' 𝛁𝜙$,& ' 𝐱$ ' 1 = 𝑠$ 𝜙(𝐱! − 𝐱") 𝑎& 𝐛$ 𝐛& 𝐩 𝑞 𝑎$
8. Hermite RBF: 値の制約 𝑎& 𝐛$ 𝐛& 𝐩 𝑞 𝑎$ 𝜙$,$ 𝜙$,& 𝛁𝜙$,$ ' 𝛁𝜙$,& ' 𝐱$ ' 1 = 𝑠$ 𝜙&,$ 𝜙&,& 𝛁𝜙&,$ ' 𝛁𝜙&,& ' 𝐱& ' 1 𝑠&
9. Hermite RBF: 勾配の制約 𝛁𝑓 𝐱! = ∑" 𝑎"𝛁𝜙!," + ∑" ∇%𝜙!,"𝐛" + 𝐩 = 𝐠! ∀𝑖 ∈ 1, … , 𝑛 𝑎& 𝐛$ 𝐛& 𝐩 𝑞 𝑎$ = 𝐠$ 𝛁𝜙$,$ ∇(𝜙$,& 𝐈 𝛁𝜙$,& ∇(𝜙$,$ 𝟎
10. Hermite RBF: 勾配の制約 𝑎& 𝐛$ 𝐛& 𝐩 𝑞 𝑎$ = 𝐠$ 𝛁𝜙$,$ ∇(𝜙$,& 𝐈 𝛁𝜙$,& ∇(𝜙$,$ 𝟎 𝐠& 𝛁𝜙&,$ ∇(𝜙&,& 𝐈 𝛁𝜙&,& ∇(𝜙&,$ 𝟎
11. Hermite RBF: 値と勾配の制約の行列表記 𝜙$,$ 𝜙$,& 𝛁𝜙$,$ ' 𝛁𝜙$,& ' 𝐱$ ' 1 𝜙&,$ 𝜙&,& 𝛁𝜙&,$ ' 𝛁𝜙&,& ' 𝐱& ' 1 𝛁𝜙$,$ ∇(𝜙$,& 𝐈 𝛁𝜙$,& ∇(𝜙$,$ 𝟎 𝛁𝜙&,$ ∇(𝜙&,& 𝐈 𝛁𝜙&,& ∇(𝜙&,$ 𝟎 𝑁) 𝑁$ 𝑀)$ 𝑀)) 𝑀$$ 𝑀)$ '
12. Hermite RBF: 値と勾配の制約の行列表記 𝑁) 𝑁$ 𝑀)$ 𝑀)) 𝑀$$ 𝑀)$ ' 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝑞 𝐛 𝐚 𝐠 = 𝐬 𝟏 𝟎 𝐩 このままでは制約 が足りない 𝑀## ∈ Sym$ 𝑀%% ∈ Sym$! 𝑀#% ∈ ℝ$×$! 𝑁# ∈ ℝ$×! 𝑁% ∈ ℝ$!×! 𝑛×𝑛 実対称行列
13. Hermite RBF: 値と勾配の制約の行列表記 𝑁) 𝑁$ 𝑀)$ 𝑀)) 𝑀$$ 𝑀)$ ' 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝑞 𝐛 𝐚 𝐠 = 𝐬 𝟏 𝟎 𝐩 このままでは制約 が足りない è制約を追加 𝑁) ' 𝑁$ ' 𝟏 𝟎 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟎 𝟎 𝑀## ∈ Sym$ 𝑀%% ∈ Sym$! 𝑀#% ∈ ℝ$×$! 𝑁# ∈ ℝ$×! 𝑁% ∈ ℝ$!×! 𝑛×𝑛 実対称行列
14. Hermite RBF の動作例 空間次元数𝑑=1 𝑑=2 ※値の制約は全てゼロ 全ての点で同じ勾配制約 点ごとに異なる勾配制約
15. 滑らかさの指標 [Duchon 1977] • Hermite RBFの係数 𝐚 ∈ ℝ& 𝐛 ∈ ℝ&' 𝐩 ∈ ℝ' 𝑞 ∈ ℝ は、制約の値 𝐬 ∈ ℝ% と勾配 𝐠 ∈ ℝ%* から一意に定まる è 得られるHRBFを 𝑓𝐬,𝐠 と表記する 𝑀!! 𝑀!" 𝑀"" 𝑀!" # • Duchon’s energy: 𝐸 𝑓𝐬,𝐠 ≔ (𝐚$ 𝐛$) 𝑀** 𝑀*+ 𝑀*+ $ 𝑀++ 𝐚 𝐛 • 𝑑=1の場合、thin-plate energy と一致 • 𝑑>1 でも、似たような意味を持つ & ℝ 𝑓𝐬,𝐠 '' ( 𝑑𝑥 • (性質) Hermite RBF は、制約を満たすあらゆる関数の中で、 Duchon’s energy を最小化するもの è “最も滑らかな補間関数” 𝐚 𝐛 𝐩 𝑞 𝐴 𝐬 𝐠 𝟎 0 = “補間行列”
16. 前提知識その2: VIPSS
17. VIPSS の問題設定 • 入力: 法線無し点群 𝐱! ∈ ℝ' 𝑖 ∈ 1, … , 𝑛 • 近似パラメタ 𝜆 ≥ 0 0 è 近似を許さない • 未知数: HRBFの制約値および勾配 𝐬 ∈ ℝ& 𝐠 ∈ ℝ&' • 𝑓 𝐱" - = 𝑠" - を 𝑖 番目の点における復元誤差と解釈 • 復元誤差と滑らかさの和で目的関数を定義: = (𝐬' 𝐠') 𝐽)) 𝐽)$ 𝐽)$ ' 𝐽$$ 𝐬 𝐠 𝐸 𝑓𝐬,𝐠 ≔ (𝐚' 𝐛') 𝑀)) 𝑀)$ 𝑀)$ ' 𝑀$$ 𝐚 𝐛 • HRBFの係数 (𝐚, 𝐛) は (𝐬, 𝐠) に対して線形なので、 • Duchon’s energy を (𝐬, 𝐠) の関数として書ける minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 𝐬$ 𝐠$ 𝐽 𝐬 𝐠 subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 𝐚 𝐛 𝐩 𝑞 𝐴,$ 𝐬 𝐠 𝟎 0 = 𝐽!! 𝐽!" 𝐽"" 𝐽!" # 自明な解 𝑓 ≡ 0 を防ぐために必要
18. VIPSS の計算方法 • 手順: 1. 補間行列 𝐴 ∈ Sym(%M$)(*M$) を生成 2. 𝐴N$ の左上ブロック 𝐽 ∈ Sym%(*M$) を取得 3. 行列 𝐻 を計算 4. 𝐻 の最小固有ベクトルを計算 è 𝐠 の初期値とする 5. 各 𝐠" を球面座標で表し、L-BFGS で最適化 è スケールしない 😢 minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 𝐬$ 𝐠$ 𝐽 𝐬 𝐠 subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 minimize: 𝐠 𝐠$𝐻 𝐠 subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 𝐻 = 𝐽)) − 𝜆𝐽*) + 𝐼 + 𝜆𝐽** ,)𝐽*) 𝐬 = −𝜆 𝐼 + 𝜆𝐽** ,)𝐽*) 𝐠 最適性の条件から 𝐬 を消去 ç 𝑂 𝑛! ç 𝑂 𝑛! ç 𝑂 𝑛!
19. 提案法: NN-VIPSS Natural Neighbor
20. 着眼点: 𝑑=1の場合 • 値と勾配の制約 𝑓 𝑥" = 𝑠" 𝑓O 𝑥" = 𝑔" 𝑖 ∈ 1, … , 𝑛 を満たすHRBFは、区分3次多項式になる • 各区間 [𝑥P , 𝑥PQR ] で、両端の値と勾配を 満たす3次関数と一致する！ • 任意の連続する部分集合に対して定まるHRBF は、対応する区間においてグローバルなHRBF と一致する • 関数を部分集合ごとのHRBFの和として定義 すれば、 𝑂(𝑛!) の計算が不要になる！ グローバルな HRBF 区間ごとの エルミート補間 グローバルな HRBF {𝑥!,$ , 𝑥! , 𝑥!-$ } から定まるHRBF {𝑥! , 𝑥!-$ , 𝑥!-( } から定まるHRBF 𝑥!"# 𝜙 𝑥 = 𝑥 .
21. 𝑑 >1 の場合 • 点群に対してドロネー三角形分割を行い、 • 各点について、その1-ring近傍を部分集合として、局所HRBFを計算 • グローバルなHRBFと局所的に良く一致する！ 点群と法線 (Hermiteデータ) グローバルなHRBF 部分集合その1 部分集合その2 è Natural Neighbor
22. 局所HRBFのブレンド • 採用する重み関数: Natural Neighbor Coordinates [Sibson 1980] 点群全体 𝑋 = {𝐱% , … , 𝐱$ } に対応するHermiteデータ 点 𝐱( のNNに対応する Hermiteデータ I 𝑓S,T 𝐱 ≔ K "#$ % 𝑤" 𝐱 𝑓S1,T1 𝐱 𝐱( 𝑉) 𝐱( 𝐱 𝑉)∪{𝐱} 𝐱 𝐱( 𝐱 𝐱( ∝ 𝑤( (𝐱) 𝑋 = {𝐱% , … , 𝐱$ } に対するボロノイ分割 𝑋 ∪ {𝐱} に対するボロノイ分割 共通部分の体積の割合で NNC を定義 “Natural-Neighbor Duchon’s interpolant”
23. グローバルHRBFとNNDはほぼ一致する 𝑑=2 𝑑=3
24. 𝐬, 𝐠, 𝐽 𝐬 𝐠 minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 𝐬$ 𝐠$ 𝐽 𝐬 𝐠 subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 K "#$ % 𝑆" , 𝐺" , 𝐽" 𝑆" 𝐺" minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 S !,+ & 𝑆! $ 𝐺! $ 𝐽! 𝑆! 𝐺! subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 ∈ Sym&(#-$) ∈ Sym&# #-$ 𝑛! ≃ 30 𝑂 𝑛! 𝑂(∑"#$ % 𝑛" !) VIPSS NN-VIPSS 滑らかさの指標 最適化問題 計算コスト NNの大きさ
25. 𝐬, 𝐠, 𝐽 𝐬 𝐠 K "#$ % 𝑆" , 𝐺" , 𝐽" 𝑆" 𝐺" minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 S !,+ & 𝑆! $ 𝐺! $ 𝐽! 𝑆! 𝐺! +𝜆𝛼 S !,+ & 𝐠! % − 1 % ∈ Sym&(#-$) ∈ Sym&# #-$ 𝑛! ≃ 30 𝑂 𝑛! 𝑂(∑"#$ % 𝑛" !) VIPSS NN-VIPSS 滑らかさの指標 計算コスト 最適化問題 minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 𝐬$ 𝐠$ 𝐽 𝐬 𝐠 subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 NNの大きさ
26. 初期法線の設定方法 各点で独立に、その点の勾配 だけを未知数としてVIPSSを解く (𝑑×𝑑 行列の最小固有ベクトル) 前後の向きを Minimum Spanning Tree を使って伝播＆修正 グローバルな最適化 (L-BFGS)
27. 結果
28. 近似パラメタ 𝜆 の効果 (𝑛=20k)
29. 小規模な点群での比較実験 Tilt Brush
30. 大規模な点群での比較実験
31. 速度の検証 ※提案法は完全にCPU実装 (OpenMPによる並列化)
32. Limitations 点群が1D状のカーブに沿ってしか存在 しない場合、1-ring近傍のサイズが 点群サイズに比例する è 速度低下 近似パラメタ λ が大きいと、収束が遅くなる