階層型RBF

コンピュータ グラフィックスにおいて、階層型 RBFは、ラジアル基底関数(RBF)に基づく補間方法です。階層型 RBF 補間は、3D コンピュータ グラフィックスの形状モデルの構築(下のスタンフォード バニーの画像を参照)、 3D スキャナーからの結果の処理、地形の再構築などに応用されています。

この問題は非公式に「大規模散在データ ポイント セット補間」と呼ばれています。

この方法の手順 (たとえば 3D の場合) は次のようになります。

• 散在する点を集合として表す。${\displaystyle \mathbf {P} =\{\mathbf {c} _{i}=(\mathbf {x} _{i},\mathbf {y} _{i},\mathbf {z} _{i})\vert _{i=1}^{N}\subset \mathbb {R} ^{3}\}}$
• 散在する点にある関数の値の集合が存在するとする${\displaystyle \mathbf {H} =\{\mathbf {h} _{i}\vert _{i=1}^{N}\subset \mathbb {R} \}}$
• 図形上にある点と図形上にない点の条件を満たす関数を見つける${\displaystyle \mathbf {f} (\mathbf {x} )}$${\displaystyle \mathbf {f} (\mathbf {x} )=1}$${\displaystyle \mathbf {f} (\mathbf {x} )\neq 1}$
• JC Carrらが示したように^[1] 、この関数は次のようになります。${\displaystyle \mathbf {f} (\mathbf {x} )=\sum _{i=1}^{N}\lambda _{i}\varphi (\mathbf {x} ,\mathbf {c} _{私}）}$

${\displaystyle \varphi}$— はRBFです。 — は図に示す システムの解となる係数です。${\displaystyle \lambda}$

曲面を決定するには、興味のある点xにおける関数の値を推定する必要がある。 このような方法がないと、 RBFを計算し、システムを解き、曲面を決定するの がかなり複雑になる^{[2] 。}${\displaystyle \mathbf {f} (\mathbf {x} )}$ ${\displaystyle \mathbf {O} (\mathbf {n} ^{2})}$

• 補間中心を減らす（RBFを計算してシステムを解き、表面を決定するため）${\displaystyle \mathbf {O} (\mathbf {n} ^{2})}$${\displaystyle \mathbf {O} (\mathbf {m} \mathbf {n} )}$
• RBF をコンパクトにサポートします( RBFを計算し、システムを解き、表面を決定します)${\displaystyle \mathbf {O} (\mathbf {n} \log {\mathbf {n} })}$${\displaystyle \mathbf {O} (\mathbf {n} ^{1.2..1.5})}$${\displaystyle \mathbf {O} (\mathbf {m} \log {\mathbf {n} })}$
• FMM ( RBFを計算し、システムを解き、表面を決定する)${\displaystyle \mathbf {O} (\mathbf {n} ^{2})}$${\displaystyle \mathbf {O} (\mathbf {n} \log {\mathbf {n} })}$${\displaystyle \mathbf {O} (\mathbf {m} +\mathbf {n} \log {\mathbf {n} })}$

階層的 アルゴリズムの考え方は、複雑な問題を多数の単純な問題に分解することで計算を高速化するというものです(図を参照)。

この場合、空間の階層的分割には基本部分上の点が含まれ、小さな次元のシステムがそれぞれを解きます。この場合の表面の計算は、階層的（ツリー構造に基づく）補間の計算に使用されます。2Dの場合の方法は、Pouderoux J. et al. ^{[3]によって提案されています}。3Dの場合、 W. Qiang et al. ^{[4]によって}3Dグラフィックスのタスクで使用され、Babkov V. ^[5]によって修正された方法です。