
数学において、スプラインは多項式によって区分的に定義される関数です。補間の問題では、スプライン補間は、低次多項式を使用しても同様の結果が得られ、高次多項式でのルンゲ現象を回避するため、多項式補間よりも好まれることが多いです。
コンピュータサイエンスのサブフィールドであるコンピュータ支援設計とコンピュータグラフィックスでは、スプラインという用語は、区分多項式 (パラメトリック)曲線を指すことが多いです。スプラインは、その構造の単純さ、評価の容易さと正確さ、曲線フィッティングとインタラクティブな曲線設計を通じて複雑な形状を近似する能力のため、これらのサブフィールドでよく使われる曲線です。
スプラインという用語は、造船業者や製図工が滑らかな形状を描くために使用する柔軟なスプライン装置に由来しています。
導入
「スプライン」という用語は、データの補間や平滑化を必要とするアプリケーションで使用される幅広いクラスの関数を指すために使用されます。データは 1 次元または多次元のいずれかです。補間用のスプライン関数は、補間制約の下で、適切な粗さの尺度 (たとえば、積分二乗曲率) を最小化する関数として通常決定されます。平滑化スプラインは、補間スプラインの一般化と見なすことができます。この場合、関数は、観測データの平均二乗近似誤差と粗さ尺度の加重組み合わせを最小化するように決定されます。粗さ尺度の多くの意味のある定義では、スプライン関数は本質的に有限次元であることがわかっています。これが、計算と表現でスプライン関数が有用である主な理由です。このセクションの残りの部分では、1 次元の多項式スプラインにのみ焦点を当て、「スプライン」という用語をこの限定された意味で使用します。
歴史
ジェラルド・ファリンによれば、Bスプラインは19世紀初頭にロシアのカザン大学のニコライ・ロバチェフスキーによって研究されていた。[1]
コンピュータが使用される前は、数値計算は手作業で行われていました。符号関数やステップ関数などの区分的に定義された関数も使用されていましたが、扱いやすい多項式が一般的に好まれていました。コンピュータの出現により、スプラインの重要性が増しました。最初は補間における多項式の代わりとして使用され、その後、コンピュータ グラフィックスで滑らかで柔軟な形状を作成するツールとして使用されました。
スプラインに関する最初の数学的言及は、1946 年のSchoenbergの論文であると一般に認められています。これは、滑らかな区分多項式近似に関連して「スプライン」という単語が使用された最初の例であると考えられます。ただし、このアイデアのルーツは航空機および造船業界にあります。 (Bartels 他、1987) の序文で、Robin Forrest は「ロフティング」について説明しています。これは、第二次世界大戦中に英国の航空機業界で使用された手法で、飛行機のテンプレートを作成するために、大きな設計ロフトの床に並べられた点に薄い木のストリップ (「スプライン」と呼ばれる) を通すという方法で作成されました。この手法は船体設計から借用したものです。長年、船舶設計の実践では、小規模な設計にモデルが使用されていました。次に、成功した設計をグラフ用紙にプロットし、プロットの重要なポイントを大きなグラフ用紙にフルサイズで再プロットしました。ストリップは、離散的な点 (フォレストは「アヒル」と呼び、シェーンベルクは「犬」または「ネズミ」と呼んだ) で所定の位置に保持され、これらの点の間では、歪みエネルギーが最小の形状をとる。フォレストによると、このプロセスの数学的モデル化のきっかけの 1 つは、ロフトが敵の爆弾に当たった場合に、航空機全体の重要な設計コンポーネントが失われる可能性があることだった。これにより、「円錐ロフト」が生まれ、円錐断面を使用してアヒル間の曲線の位置をモデル化した。円錐ロフトは、1960 年代初頭に、ボーイングの JC ファーガソンと (やや後になって)ブリティッシュ エアクラフト コーポレーションの MA セービンの研究に基づいて、いわゆるスプラインに置き換えられた。
「スプライン」という言葉は、もともとイースト・アングリア方言の言葉でした。
自動車のボディをモデル化するためにスプラインを使用することは、いくつかの独立した始まりがあったようです。シトロエンのde Casteljau、ルノーのPierre Bézier、ゼネラルモーターズのBirkhoff、Garabedian、およびde Boor の功績が認められています (Birkhoff および de Boor、1965 を参照)。いずれも 1960 年代のごく初期または 1950 年代後半に行われた研究です。de Casteljau の論文は少なくとも 1 つが 1959 年に出版されましたが、広くは発表されませんでした。ゼネラルモーターズでの de Boor の研究は、B スプラインに関する基礎研究の一部を含む、1960 年代初期に出版された多数の論文につながりました。
プラット・アンド・ホイットニー・エアクラフト社でも作業が行われており、そこではスプラインの最初の書籍である (Ahlberg et al., 1967) の著者のうち 2 人が雇用され、また、フェオドール・タイルハイマーによるDavid Taylor Model Basinも使用されました。ゼネラルモーターズ社での研究は、(Birkhoff, 1990) および (Young, 1997) に詳しく記載されています。Davis (1997) は、この資料の一部を要約しています。
意味
まず、 1変数の多項式に限定して議論します。この場合、スプラインは区分 多項式 関数です。この関数をSと呼び、区間[ a , b ]から値を取り、それを実数集合にマッピングします。S は区分的に定義する 必要があります。これを実現するには、区間[ a , b ] をk個の順序付けられた互いに素な部分区間でカバーします。
[ a , b ]のk個の「部分」のそれぞれについて、多項式を定義し、これをP iと呼びます。 [ a , b ]のi番目の部分区間 では、S はP iによって定義されます。
与えられたk + 1 個の点t iはノットと呼ばれます。ベクトルt = ( t 0 , …, t k )はスプラインのノットベクトルと呼ばれます。ノットが区間[ a , b ]内で等間隔に分布している場合、スプラインは均一であると言い、そうでない場合は非均一であると言います。
多項式部分P i のそれぞれの次数が最大でnである場合、スプラインは次数 ≤ n (または順序 n + 1 ) であると言われます。
t iの近傍にある場合、スプラインはt iで(少なくとも)滑らかであると言えます。つまり、 t i では、2つの多項式部分P i –1とP i は、次数 0 の導関数(関数値)から次数r iの導関数まで共通の導関数値を共有しています(言い換えると、2つの隣接する多項式部分は、最大でn – r iの滑らかさの損失で接続されています)。
i = 1, …, k – 1に対してt iでスプラインが滑らかになるようなベクトルr = ( r 1 , …, r k –1 )は、スプラインの 滑らかさベクトルと呼ばれます。
結び目ベクトルt、次数n、および tに対する 滑らかさベクトルr が与えられたとき、結び目ベクトルtと滑らかさベクトル rを持つ次数≤ nのすべてのスプラインの集合を考えることができる。2つの関数を加算する操作(点ごとの加算)と関数の実数倍をとる操作を備えたこの集合は、実数ベクトル空間になる。このスプライン空間は、一般に次のように表される。
多項式スプラインの数学的研究において、2 つの結び目、たとえばt iとt i +1が互いに接近して一致するとどうなるかという疑問に対する答えは簡単です。多項式部分P i ( t )は消え、部分P i −1 ( t )とP i +1 ( t )は、 t iとt i +1の滑らかさの損失の合計と結合します。つまり、 j i = n – r iです。これにより、結び目ベクトルのより一般的な理解がもたらされます。任意の点における連続性の損失は、その点に位置する複数の結び目の結果であると考えることができ、スプライン タイプは、次数nとその拡張された結び目ベクトル によって完全に特徴付けることができます。
ここでt iはi = 1, …, k – 1に対してj i回繰り返されます。
区間[ a , b ]上のパラメトリック曲線は、XとYの両方がその区間上で同じ拡張ノット ベクトルを持つ同じ次数のスプライン関数である 場合にスプライン曲線 になります。
例
区間[ a , b ]が[0, 3]で、区間が[0, 1]、[1, 2]、[2, 3]であるとします。多項式の各部分が次数 2 で、 [0, 1]と[1, 2]の部分は値と 1 次導関数で結合する必要があり ( t = 1 )、 [1, 2]と[2, 3]の部分は値でのみ結合します ( t = 2 )。これは、次のような スプラインS ( t )のタイプを定義します。
そのタイプのメンバーであり、また
はその型のメンバーになります。(注: 多項式部分2 t は二次ではありませんが、結果は依然として二次スプラインと呼ばれます。これは、スプラインの次数がその多項式部分の最大次数であることを示しています。) このタイプのスプラインの拡張ノットベクトルは(0, 1, 2, 2, 3)になります。
最も単純なスプラインは次数 0 です。これはステップ関数とも呼ばれます。次に単純なスプラインは次数 1 です。これは線形スプラインとも呼ばれます。平面上の閉じた線形スプライン (つまり、最初のノットと最後のノットが同じ) は単なる多角形です。
一般的なスプラインは、自然 3 次スプラインです。3 次スプラインは、次数が 3 で連続性がC 2です。つまり、値と 1 次導関数および 2 次導関数は連続しています。自然とは、スプライン多項式の 2 次導関数が補間区間の端点でゼロになることを意味します。
したがって、スプラインのグラフは、間隔の外側では直線ですが、それでも滑らかです。
自然3次スプラインを計算するアルゴリズム
3次スプラインは次の形式をとる。
座標セットが与えられた場合、 i = 0, …, n – 1のn個のスプラインのセットS i ( x ) を見つけます。
これらは以下を満たす必要があります:
1 つの 3 次スプラインS を5 組( a、b、c、d、x t )として定義します。ここで、a、 b、 c、 d は前述の形式の係数に対応し、x tはx jに等しくなります。
自然 3 次スプラインを計算するアルゴリズム:
入力: 座標セットC、| C | = n + 1出力: n 個
の 5 組
で構成されるスプライン セット。
- サイズn + 1の新しい配列aを作成し、 i = 0、…、nに対して
- それぞれサイズがnの新しい配列bとd を作成します。
- サイズnの新しい配列hを作成し、 i = 0, …, n – 1に対して
- サイズnの新しい配列αを作成し、 i = 1, …, n – 1に対して
- それぞれのサイズがn + 1の新しい配列c、l、μ、zを作成します。
- セット
- i = 1, …, n – 1の場合、次のように設定します。
- セット
- j = n – 1, n – 2, …, 0の場合、次のように設定します。
- 新しいセットを作成し
Splines、 という名前を付けます。n個のスプラインSoutput_setでそれを設定します。 - i = 0, …, n – 1の場合、次のように設定します。
- 出力
output_set
注記
ノット ベクトル内の n 個を超える多重ノットにはどのような意味があるのかと疑問に思うかもしれません。 これは、多重度が高い場所での連続性につながるためです。慣例により、このような状況は、2 つの隣接する多項式部分間の単純な不連続性を示します。つまり、拡張されたノット ベクトルでノットt i がn + 1回以上出現する場合、多重度n + 1、n + 2、n + 3などはすべて同じ意味を持つため、 ( n + 1)番目を超えるすべてのインスタンスはスプラインの特性を変更することなく削除できます。任意のタイプのスプラインを定義するノット ベクトルは、通常、この方法で除去されていると想定されます。
数値解析で使用される n 次古典的スプライン タイプには連続性があり 、これは、隣接する 2 つの多項式部分が各ノットでその値と最初のn − 1導関数で一致することを意味します。平坦スプラインを最もよくモデル化する数学的スプラインは、 3 次 ( n = 3 )、2 回連続微分可能 ( C 2 )、自然スプラインであり、これは、エンドポイントaとbで追加の条件が課されたこの古典的タイプのスプラインです。
グラフィックスでよく使用される別のタイプのスプライン (たとえば、Adobe SystemsのAdobe Illustratorなどの描画プログラム) には、立方体のピースがありますが、連続性は最大でも 10 です。 このタイプのスプラインは、 PostScriptや一部のコンピューター印刷フォントの定義でも 使用されます。
高性能グラフィックスやアニメーション向けに設計された多くのコンピュータ支援設計システム ( Autodesk Mayaなど) では、拡張ノット ベクトルが使用されます。コンピュータ支援設計システムでは、非一様有理 B スプライン(NURBS)と呼ばれるスプラインの拡張概念がよく使用されます。
関数または物理オブジェクトからサンプリングされたデータが利用可能な場合、スプライン補間はそのデータを近似するスプラインを作成する方法です。
一般的な表現C23次スプラインの補間
自然な条件を持つ点xにおけるi番目のC 2補間3次スプラインの一般的な表現は、次の式で見つけることができます。
どこ
- i番目のノットにおける 2 次導関数の値です。
- i番目のノットにおける関数の値です。
表現と名前
与えられた区間[ a , b ]とその区間上の与えられた拡張ノット ベクトルに対して、次数nのスプラインはベクトル空間を形成します。簡単に言うと、与えられたタイプの任意の 2 つのスプラインを追加すると、そのタイプのスプラインが生成され、与えられたタイプのスプラインに任意の定数を掛けると、そのタイプのスプラインが生成されます。特定のタイプのすべてのスプラインを含む空間の次元は、拡張ノット ベクトルから計算できます。
次元は次数と多重度の合計に等しい
スプラインの種類に追加の線形条件が課されている場合、結果のスプラインは部分空間内にあります。たとえば、すべての自然な 3 次スプラインの空間は、すべての 3 次C 2スプラインの空間の部分空間です。
スプラインに関する文献には、特殊なタイプのスプラインの名前が数多く記載されています。これらの名前は、次のようなものと関連付けられています。
- スプラインを表現するために選択されたもの、たとえば次のとおりです。
- スプライン全体に基底関数を使用する( Bスプラインという名前が付けられています)
- ピエール・ベジエが用いたベルンシュタイン多項式を使用して各多項式部分を表す(ベジエスプラインという名前が付けられている)
- 拡張ノット ベクトルを形成する際に行われる選択、たとえば次のようになります。
- C n –1連続性のために単一のノットを使用し、これらのノットを[ a , b ]上で均等に配置する(均一なスプラインが得られる)
- 間隔に制限のないノットを使用する(非均一なスプラインが得られる)
- スプラインに課される特別な条件。例:
- aとbで2次導関数をゼロにする(自然なスプラインを与える)
- 与えられたデータ値がスプライン上にあることを要求する(補間スプラインを与える)
多くの場合、上記の主要項目の 2 つ以上を満たすスプラインのタイプには特別な名前が付けられています。たとえば、エルミート スプラインは、エルミート多項式を使用して個々の多項式部分をそれぞれ表すスプラインです。これらは、 n = 3の場合、つまり3 次エルミート スプラインとして最もよく使用されます。この程度では、接線連続 ( C 1 )のみになるように選択することもできます。これは、すべての内部ノットが 2 重であることを意味します。このようなスプラインを特定のデータ ポイントに適合させる方法、つまり、それらを補間スプラインにする方法、および各 2 つの多項式部分が交わる妥当な接線値を推定することによって補間スプラインにする方法がいくつか発明されています (使用する方法に応じて、 カーディナル スプライン、Catmull-Rom スプライン、およびKochanek-Bartels スプラインが得られます)。
それぞれの表現について、スプラインの値が要求に応じて生成できるように、何らかの評価手段を見つける必要があります。個々の多項式部分P i ( t )をn次多項式の何らかの基底で表現する表現の場合、これは概念的に簡単です。
- 引数tの与えられた値に対して、それがどの区間に含まれるかを求める。
- その区間に選択された多項式基底を調べる
- tにおける各基底多項式の値を求めます。
- その区間c 0 , ..., c k –2上のスプラインを与える基底多項式の線形結合の係数を調べる。
- 基底多項式の値の線形結合を合計して、 tにおけるスプラインの値を取得します。
ただし、評価手順と合計手順は巧妙な方法で組み合わせられることがよくあります。たとえば、ベルンシュタイン多項式は、特殊な再帰関係を使用して線形結合で効率的に評価できる多項式の基礎です。これが、ベジェ曲線と ベジェスプラインで使用されているドゥカステルジョーのアルゴリズムの本質です。
ただし、スプラインを基底スプラインの線形結合として定義する表現には、より洗練されたものが必要です。de Boor アルゴリズムは、B スプラインを評価するための効率的な方法です。
参考文献
- ^ Farin, GE (2002). CAGD のための曲線と曲面: 実用ガイド. Morgan Kaufmann. p. 119.
- Ferguson, James C, 「多変数曲線補間」、 J. ACM、vol. 11、no. 2、pp. 221-228、1964 年 4 月。
- Ahlberg、Nielson、Walsh、「スプラインの理論とその応用」、 1967 年。
- バーコフ、「流体力学、リアクター計算、および表面表現」、スティーブ・ナッシュ(編)『科学的計算の歴史』、1990 年。
- Bartels、Beatty、Barsky、「コンピュータ グラフィックスと幾何学モデリングで使用するスプライン入門」、 1987 年。
- Birkhoff および de Boor、「Piecewise polynomial interpolation and approximation」、HL Garabedian (編)、Proc. General Motors Symposium of 1964、 pp. 164–190。Elsevier、ニューヨークおよびアムステルダム、1965 年。
- Charles K. Chui、「多変量スプライン」、SIAM、ISBN 978-0-898712261 (1987)。
- Davis, B-スプラインと幾何学的設計、SIAM News、第29巻第5号、1996年。
- エプパーソン、「スプラインの歴史」、NA ダイジェスト、第 98 巻、第 26 号、1998 年。
- Ming-Jun Lai 、Larry L. Schumaker、「Spline Functions on Triangulations」、Cambridge Univ. Press、ISBN 978-0-521-87592-9 (2007)。
- Stoer & Bulirsch、数値解析入門。スプリンガー・フェルラーグ。 p. 93-106。 ISBN 0387904204
- Schoenberg, 解析関数による等距離データの近似問題への貢献、Quart. Appl. Math.、第4巻、pp. 45–99 および 112–141、1946年。
- ヤング、ギャレット・バークホフと応用数学、AMSの通知、第44巻、第11号、pp.1446-1449、1997年。
- Chapra、Canale、「エンジニアのための数値解析手法」第 5 版。
- Larry, Schumaker、「スプライン関数: 計算方法」、SIAM、ISBN 978-1-611973-89-1、(2015)。
外部リンク
理論
- スプラインのインタラクティブな紹介、ibiblio.org
Excel関数
- XLL Excel アドイン関数 3次スプラインの実装
オンラインユーティリティ
- オンライン 3 次スプライン補間ユーティリティ
- シミュレーションによる学習 さまざまな3次スプラインのインタラクティブシミュレーション
- 対称スプライン曲線、 Theodore Grayによるアニメーション、The Wolfram Demonstrations Project、2007 年。
コンピュータコード
- ノート、PPT、Mathcad、Maple、Mathematica、Matlab、Holistic Numerical Methods Institute
- さまざまなルーチン、NTCC
- Sisl: NURBS、SINTEF 用のオープンソース C ライブラリ
- VBA スプライン補間、vbnumericalmethods.com
