情報地質 第28巻 第2号 100-101頁 2017年
Geoinformatics, vol.28, no.2, pp.100-101, 2017

高速な三次元スプライン補間およびクリギングのためのフレームワーク
水野 将志*A Framework for Fast 3D Spline Interpolation and Kriging
Masashi Mizuno** ジーエスアイ株式会社 GSI Co. Ltd., 2-8-37 Chuo, Mito-shi, Ibaraki 310-0805, Japan.
E-mail: mizuno@gsinet.co.jp

キーワード：スプライン補間，クリギング，動径基底関数
Key words : Spline interpolation, Kriging, Radial basis functions

程式に帰着される．

１．はじめに点群のスプライン補間は，与えられた点群，もしくはそれらの近傍を通る“滑らかな”関数を求める手法の総称で，地形面，地層境界面や地下水面の推定などに用いられている．
2.5 次元と呼ばれる，2 変数関数を用いた 3 次元形状の表現
は，オーバーハングや球面のような閉じた物体を表現できないなど，適用できる形状に制約がある．
クリギングは，観測データ（位置と値の組）の統計的性質を考慮して未観測の位置での値を予測する手法で，降水量や鉱石品位のほか，様々な数値データに対する応用が可能である．しかしながら，予測には次数の大きな多項式時間を要するため，大規模なデータへの適用が難しい．
本研究では，RBF 補間を用いてこれらの問題を解決するフレームワーク「Polatory」を開発した．

２．RBF 補間

2.1 定義RBF 補間は，代表的な数値データ補間手法の一つである．
個の観測データに対するRBF 補間関数は，次の式で定義される．
(1)
は RBF（動径基底関数）と呼ばれ，目的により様々な種類の関数が用いられる．
はユークリッドノルムである．第 1 項は観測データを中心とする RBF の線形結合である．第 2 項は低次の多項式で，観測データに含まれる全体的な傾向を表現する．
はこの多項式の基底で，例えば 1 次の多項式はを基底に持つ．
係数およびを，次の補間条件および付随条件を満たすように決定する．これを RBF 補間問題と呼ぶ．

(2)

RBF 補間問題は，次の個の変数を持つ線形連立方(3)

線形連立方程式 (3) の係数行列が正定値（すべての固有値が正）になるために最低次の多項式が必要である
とき，RBF は 次の条件付き正定値（CPD）であるという．
また， そのものが正定値になる場合，単に RBF は正定値であるという．第 1 表に RBF の例を示す．
名前
ガウス型
逆多重二次重調和
多重二次三重調和
第1表関数形（）

定値性
正定値正定値
1 次の CPD
1 次の CPD
2 次の CPDRBF の例（Fasshauer et al., 2007）

2.2 スプライン補間との関係
一部の RBF 補間関数は，補間において特定のエネルギー汎関数を最小化するような，最も“滑らかな”関数を与えることが知られている（Carr et al., 2001）．重調和関数と 1 次以下の多項式，三重調和関数と 2 次以下の多項式の組み合わせなどがこれにあたる．このような関数を用いて，点群のスプライン補間を行うことができる．
BS-Horizon（野々垣他, 2008）などで用いられているいわ
ゆる 2.5 次元の手法では，2 変数関数 を用い，を満たす点の集合によって曲面を表現する．これに対し，3次元の陰関数による手法では，3 変数関数を用い，を満たす点の集合によって曲面を表現する．
これにより 3 次元空間中の任意の曲面が表現可能になる．
RBF 補間をこの手法に利用するには，まず，第 1 図に示すように入力点群を法線に沿ってシフトして新たな点を生成し，距離に応じた符号付きの値を付与する．これを観測データとして RBF 補間を行い，となる等値面をメ101

ッシュとして抽出することで，補間された曲面の形状を出力する．

第1図

点群から生成した値付きの点データ

Carr et al., 2001 より抜粋，加工した．

BS-Horizon で用いられている一様 B-スプライン補間は，補間の際に解像度，つまり基底関数の間隔を指定する必要があり，この間隔よりも小さな特徴についての情報は捉えることができない．一方 RBF 補間では，観測データの位置に一致するように基底関数が配置されるため，補間後に任意の解像度で点群の特徴を復元できる．
2.3 クリギングとの関係
一変量クリギングによる値の予測は，RBF 補間問題に帰着できることが知られている（Billings et al., 2002）．RBFがバリオグラムに対応する．ただし，バリオグラムは条件付き負定値であるため，RBF を CPD に取るには負号が必要である（）．また，ナゲット効果を含むバリオグラム（）を用いる場合は，(3) の行列要素を次のように修正する必要がある．
(4)
RBF 補間関数 (1) の多項式の次数が 0 次の場合は通常クリギングに，1 次以上の場合は普遍クリギングに対応する．
2.4 計算量
RBF 補間の計算量を第 2 表に示す．RBF 補間の実用化には， 3.1 節に示すような高速法の使用が不可欠である．
ただし，高速法による RBF 補間の計算量は，実際にはデータの分布にも大きく依存する．
直接法
高速法
RBF 補間空間計算量
時間計算量
RBF 補間関数の評価（1 点あたり）
空間計算量
時間計算量
第 2 表 RBF 補間の計算量：観測データの数
高速法と等値面追跡アルゴリズムを用いると，点群の補間＋メッシュ生成（解像度）はの時間で行うことができる．また，クリギングによって点の位置での値を予測する場合，従来の計算法はの空間およびの時間を要するが，RBF 補間の高速法を用いると，これらをそれぞれおよびに削減できる．

３．実装

3.1 高速法の概要
Polatory は点群の補間やクリギングを行うフレームワー
クで，C++で記述されている．Polatory には RBF 補間の高速法が実装されていて，任意の式で定義される RBF を利用できる（ただし振動のない，を除き滑らかな関数に限られる）．高速法は，RBF 補間関数を定数時間で評価するための FMM（高速多重極法，Gumerov et al., 2005），線形連立方程式の反復法の一種であるクリロフ部分空間法，およびその前処理に用いる領域分割法から構成される．
3.2 精度の見積りとコントロール
高速法では近接する複数の基底関数をまとめ，より軽量な関数表現に圧縮することで評価の高速化を図る．その際，展開に用いる関数の数に応じて打ち切り誤差が発生するほか，その後の計算の種々の過程で誤差が蓄積する．ここでは，RBF 補間関数の評価に伴う誤差の上限を評価精度と呼ぶ．
また，反復法の収束条件として与える目標精度を補間精度と呼ぶ．評価精度は補間精度よりも数オーダー小さくなるよう調整されることが望ましい．Polatory の現在の実装では，補間精度の指定および補間後の評価精度の見積りは可能であるが，評価精度の定量的なコントロールはできない．
実装の検証のため，テストデータを用いたクリギングの予測計算を R の geoR パッケージおよび gstat パッケージ
で行い，それぞれ補間精度以内で Polatory の結果と値が一致することを確認した．

４．議論

点 群 の 補 間 に つ い て は ， 現 在 Poisson surface
reconstruction（Kazhdan et al., 2006）と呼ばれる手法が広く用いられている．この手法はスプライン補間の一種ではないが，非常に高速であるため，目的に応じて選択肢に含めることが望ましい．

５．まとめ

RBF 補間の高速法の実装により，スプライン補間およびクリギングを従来よりも広範なデータに対し適用することが可能になった．Polatory は実装の詳細な検証および活発な議論・貢献を可能にするため，オープンソースソフトウェ
アとして公開される予定である．
今後の課題として，ノイズを含むデータ，不等式データ，走向傾斜データへの対応（Hillier et al., 2014）や，Pythonなど他言語へのバインディングの提供などが挙げられる．

文

献Billings S.D., Beatson R.K., and Newsam G.N. (2002),
Interpolation of Geophysical Data Using Continuous
Global Surfaces. Geophysics, 67(6), 1810–1822.
Carr J.C., Beatson R.K., Cherrie J.B., Mitchell T.J.,
Fright W.R., McCallum B.C., and Evans T.R. (2001),
Reconstruction and Representation of 3D Objects with
Radial Basis Functions. In proceedings of SIGGRAPH'01, 43–54.
Fasshauer G.E. (2007), Meshfree Approximation Methods
with MATLAB., World Scientific.
Gumerov N.A., and Duraiswami R. (2005), Fast Multipole
Methods for the Helmholtz Equation in Three
Dimensions. Elsevier.
Hillier M.J., Schetselaar E.M., de Kemp E. A., and PerronG. (2014), Three-Dimensional Modelling of Geological
Surfaces Using Generalized Interpolation with Radial
Basis Functions. Math. Geosci., 46(8), 931–953.
Kazhdan M., Bolitho M., and Hoppe H. (2006), Poisson
Surface Reconstruction. In proceedings of Symposium
on Geometry Processing 2006, 61–70.
野々垣 進・升本 眞二・塩野 清治 (2008), 3 次 B-スプラインを用いた地層境界面の推定. 情報地質, 19(2), 61–77.