Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Variational Surface Reconstruction Using Natura...

Variational Surface Reconstruction Using Natural Neighbors (SIGGRAPH 2025)

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

Avatar for Spatial AI Network

Spatial AI Network

July 09, 2025
Tweet

More Decks by Spatial AI Network

Other Decks in Technology

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. 3D復元のよくあるシナリオ 1. 入力は法線付き点群 • 位置: 𝐱" ∈ ℝ! • 法線:

    𝐠" ∈ ℝ! 𝑖 ∈ 1, … , 𝑛 2. 値と勾配の制約 𝑓 𝐱" = 0 𝛁𝑓 𝐱" = 𝐠" を満たす関数 𝑓: ℝ! → ℝ を求める 3. 𝑓 のゼロ等値面を抽出 • “Scattered data interpolation” と呼ばれる問題 • これを解く道具の一つが、Hermite RBF Radial Basis Function
  4. 3D復元のよくあるシナリオ 1. 入力は法線付き点群 • 位置: 𝐱" ∈ ℝ* • 法線:

    𝐠" ∈ ℝ* 𝑖 ∈ 1, … , 𝑛 2. 値と勾配の制約 𝑓 𝐱" = 𝑠" 𝛁𝑓 𝐱" = 𝐠" を満たす関数 𝑓: ℝ" → ℝ を求める 3. 𝑓 のゼロ等値面を抽出 • “Scattered data interpolation” と呼ばれる問題 • これを解く道具の一つが、Hermite RBF Radial Basis Function
  5. Hermite RBF: 式の形 • 関数を、基底関数とその勾配の重ね合わせで表す 𝜙 𝐱 = 𝐱 !

    𝑓 𝐱 = ∑+ 𝑎+𝜙(𝐱 − 𝐱+) + ∑+ 𝐛+ ,𝛁𝜙 𝐱 − 𝐱+ + 𝐩,𝐱 + 𝑞 𝛁𝑓 𝐱 = ∑+ 𝑎+𝛁𝜙(𝐱 − 𝐱+) + ∑+ ∇-𝜙 𝐱 − 𝐱+ 𝐛+ + 𝐩 • 値と勾配の制約から、未知係数を求める 𝑓 𝐱" = 𝑠" 𝛁𝑓 𝐱" = 𝐠" ∀𝑖 ∈ 1, … , 𝑛 𝑎" ∈ ℝ 𝐛" ∈ ℝ# 𝐩 ∈ ℝ# 𝑞 ∈ ℝ 未知係数 𝜙のヘッセ行列 ℝ!×!
  6. Hermite RBF: 値の制約 𝑓 𝐱! = ∑" 𝑎"𝜙!," + ∑"

    𝐛" $𝛁𝜙!," + 𝐩$𝐱! + 𝑞 = 𝑠! ∀𝑖 ∈ 1, … , 𝑛 𝜙$,$ 𝜙$,& 𝛁𝜙$,$ ' 𝛁𝜙$,& ' 𝐱$ ' 1 = 𝑠$ 𝜙(𝐱! − 𝐱") 𝑎& 𝐛$ 𝐛& 𝐩 𝑞 𝑎$
  7. Hermite RBF: 値の制約 𝑎& 𝐛$ 𝐛& 𝐩 𝑞 𝑎$ 𝜙$,$

    𝜙$,& 𝛁𝜙$,$ ' 𝛁𝜙$,& ' 𝐱$ ' 1 = 𝑠$ 𝜙&,$ 𝜙&,& 𝛁𝜙&,$ ' 𝛁𝜙&,& ' 𝐱& ' 1 𝑠&
  8. Hermite RBF: 勾配の制約 𝛁𝑓 𝐱! = ∑" 𝑎"𝛁𝜙!," + ∑"

    ∇%𝜙!,"𝐛" + 𝐩 = 𝐠! ∀𝑖 ∈ 1, … , 𝑛 𝑎& 𝐛$ 𝐛& 𝐩 𝑞 𝑎$ = 𝐠$ 𝛁𝜙$,$ ∇(𝜙$,& 𝐈 𝛁𝜙$,& ∇(𝜙$,$ 𝟎
  9. Hermite RBF: 勾配の制約 𝑎& 𝐛$ 𝐛& 𝐩 𝑞 𝑎$ =

    𝐠$ 𝛁𝜙$,$ ∇(𝜙$,& 𝐈 𝛁𝜙$,& ∇(𝜙$,$ 𝟎 𝐠& 𝛁𝜙&,$ ∇(𝜙&,& 𝐈 𝛁𝜙&,& ∇(𝜙&,$ 𝟎
  10. Hermite RBF: 値と勾配の制約の行列表記 𝜙$,$ 𝜙$,& 𝛁𝜙$,$ ' 𝛁𝜙$,& ' 𝐱$

    ' 1 𝜙&,$ 𝜙&,& 𝛁𝜙&,$ ' 𝛁𝜙&,& ' 𝐱& ' 1 𝛁𝜙$,$ ∇(𝜙$,& 𝐈 𝛁𝜙$,& ∇(𝜙$,$ 𝟎 𝛁𝜙&,$ ∇(𝜙&,& 𝐈 𝛁𝜙&,& ∇(𝜙&,$ 𝟎 𝑁) 𝑁$ 𝑀)$ 𝑀)) 𝑀$$ 𝑀)$ '
  11. Hermite RBF: 値と勾配の制約の行列表記 𝑁) 𝑁$ 𝑀)$ 𝑀)) 𝑀$$ 𝑀)$ '

    𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝑞 𝐛 𝐚 𝐠 = 𝐬 𝟏 𝟎 𝐩 このままでは制約 が足りない 𝑀## ∈ Sym$ 𝑀%% ∈ Sym$! 𝑀#% ∈ ℝ$×$! 𝑁# ∈ ℝ$×! 𝑁% ∈ ℝ$!×! 𝑛×𝑛 実対称行列
  12. Hermite RBF: 値と勾配の制約の行列表記 𝑁) 𝑁$ 𝑀)$ 𝑀)) 𝑀$$ 𝑀)$ '

    𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝑞 𝐛 𝐚 𝐠 = 𝐬 𝟏 𝟎 𝐩 このままでは制約 が足りない è制約を追加 𝑁) ' 𝑁$ ' 𝟏 𝟎 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟎 𝟎 𝑀## ∈ Sym$ 𝑀%% ∈ Sym$! 𝑀#% ∈ ℝ$×$! 𝑁# ∈ ℝ$×! 𝑁% ∈ ℝ$!×! 𝑛×𝑛 実対称行列
  13. 滑らかさの指標 [Duchon 1977] • Hermite RBFの係数 𝐚 ∈ ℝ& 𝐛

    ∈ ℝ&' 𝐩 ∈ ℝ' 𝑞 ∈ ℝ は、制約の値 𝐬 ∈ ℝ% と勾配 𝐠 ∈ ℝ%* から一意に定まる è 得られるHRBFを 𝑓𝐬,𝐠 と表記する 𝑀!! 𝑀!" 𝑀"" 𝑀!" # • Duchon’s energy: 𝐸 𝑓𝐬,𝐠 ≔ (𝐚$ 𝐛$) 𝑀** 𝑀*+ 𝑀*+ $ 𝑀++ 𝐚 𝐛 • 𝑑=1の場合、thin-plate energy と一致 • 𝑑>1 でも、似たような意味を持つ & ℝ 𝑓𝐬,𝐠 '' ( 𝑑𝑥 • (性質) Hermite RBF は、制約を満たすあらゆる関数の中で、 Duchon’s energy を最小化するもの è “最も滑らかな補間関数” 𝐚 𝐛 𝐩 𝑞 𝐴 𝐬 𝐠 𝟎 0 = “補間行列”
  14. VIPSS の問題設定 • 入力: 法線無し点群 𝐱! ∈ ℝ' 𝑖 ∈

    1, … , 𝑛 • 近似パラメタ 𝜆 ≥ 0 0 è 近似を許さない • 未知数: HRBFの制約値および勾配 𝐬 ∈ ℝ& 𝐠 ∈ ℝ&' • 𝑓 𝐱" - = 𝑠" - を 𝑖 番目の点における復元誤差と解釈 • 復元誤差と滑らかさの和で目的関数を定義: = (𝐬' 𝐠') 𝐽)) 𝐽)$ 𝐽)$ ' 𝐽$$ 𝐬 𝐠 𝐸 𝑓𝐬,𝐠 ≔ (𝐚' 𝐛') 𝑀)) 𝑀)$ 𝑀)$ ' 𝑀$$ 𝐚 𝐛 • HRBFの係数 (𝐚, 𝐛) は (𝐬, 𝐠) に対して線形なので、 • Duchon’s energy を (𝐬, 𝐠) の関数として書ける minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 𝐬$ 𝐠$ 𝐽 𝐬 𝐠 subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 𝐚 𝐛 𝐩 𝑞 𝐴,$ 𝐬 𝐠 𝟎 0 = 𝐽!! 𝐽!" 𝐽"" 𝐽!" # 自明な解 𝑓 ≡ 0 を防ぐために必要
  15. VIPSS の計算方法 • 手順: 1. 補間行列 𝐴 ∈ Sym(%M$)(*M$) を生成

    2. 𝐴N$ の左上ブロック 𝐽 ∈ Sym%(*M$) を取得 3. 行列 𝐻 を計算 4. 𝐻 の最小固有ベクトルを計算 è 𝐠 の初期値とする 5. 各 𝐠" を球面座標で表し、L-BFGS で最適化 è スケールしない 😢 minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 𝐬$ 𝐠$ 𝐽 𝐬 𝐠 subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 minimize: 𝐠 𝐠$𝐻 𝐠 subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 𝐻 = 𝐽)) − 𝜆𝐽*) + 𝐼 + 𝜆𝐽** ,)𝐽*) 𝐬 = −𝜆 𝐼 + 𝜆𝐽** ,)𝐽*) 𝐠 最適性の条件から 𝐬 を消去 ç 𝑂 𝑛! ç 𝑂 𝑛! ç 𝑂 𝑛!
  16. 着眼点: 𝑑=1の場合 • 値と勾配の制約 𝑓 𝑥" = 𝑠" 𝑓O 𝑥"

    = 𝑔" 𝑖 ∈ 1, … , 𝑛 を満たすHRBFは、区分3次多項式になる • 各区間 [𝑥P , 𝑥PQR ] で、両端の値と勾配を 満たす3次関数と一致する! • 任意の連続する部分集合に対して定まるHRBF は、対応する区間においてグローバルなHRBF と一致する • 関数を部分集合ごとのHRBFの和として定義 すれば、 𝑂(𝑛!) の計算が不要になる! グローバルな HRBF 区間ごとの エルミート補間 グローバルな HRBF {𝑥!,$ , 𝑥! , 𝑥!-$ } から定まるHRBF {𝑥! , 𝑥!-$ , 𝑥!-( } から定まるHRBF 𝑥!"# 𝜙 𝑥 = 𝑥 .
  17. 局所HRBFのブレンド • 採用する重み関数: Natural Neighbor Coordinates [Sibson 1980] 点群全体 𝑋

    = {𝐱% , … , 𝐱$ } に対応するHermiteデータ 点 𝐱( のNNに対応する Hermiteデータ I 𝑓S,T 𝐱 ≔ K "#$ % 𝑤" 𝐱 𝑓S1,T1 𝐱 𝐱( 𝑉) 𝐱( 𝐱 𝑉)∪{𝐱} 𝐱 𝐱( 𝐱 𝐱( ∝ 𝑤( (𝐱) 𝑋 = {𝐱% , … , 𝐱$ } に対するボロノイ分割 𝑋 ∪ {𝐱} に対するボロノイ分割 共通部分の体積の割合で NNC を定義 “Natural-Neighbor Duchon’s interpolant”
  18. 𝐬, 𝐠, 𝐽 𝐬 𝐠 minimize: 𝐬, 𝐠 𝐬$𝐬 +

    𝜆 𝐬$ 𝐠$ 𝐽 𝐬 𝐠 subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 K "#$ % 𝑆" , 𝐺" , 𝐽" 𝑆" 𝐺" minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 S !,+ & 𝑆! $ 𝐺! $ 𝐽! 𝑆! 𝐺! subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 ∈ Sym&(#-$) ∈ Sym&# #-$ 𝑛! ≃ 30 𝑂 𝑛! 𝑂(∑"#$ % 𝑛" !) VIPSS NN-VIPSS 滑らかさの指標 最適化問題 計算コスト NNの大きさ
  19. 𝐬, 𝐠, 𝐽 𝐬 𝐠 K "#$ % 𝑆" ,

    𝐺" , 𝐽" 𝑆" 𝐺" minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 S !,+ & 𝑆! $ 𝐺! $ 𝐽! 𝑆! 𝐺! +𝜆𝛼 S !,+ & 𝐠! % − 1 % ∈ Sym&(#-$) ∈ Sym&# #-$ 𝑛! ≃ 30 𝑂 𝑛! 𝑂(∑"#$ % 𝑛" !) VIPSS NN-VIPSS 滑らかさの指標 計算コスト 最適化問題 minimize: 𝐬, 𝐠 𝐬$𝐬 + 𝜆 𝐬$ 𝐠$ 𝐽 𝐬 𝐠 subject to: 𝐠! = 1 ∀𝑖 ∈ 1, … , 𝑛 NNの大きさ