3次エルミートスプライン

数値解析において、3次エルミートスプラインまたは3次エルミート補間器は、各部分がエルミート形式で指定された3次多項式、つまり対応する領域間隔の端点での値と1次導関数によって指定されたスプラインです。^[1]

3 次エルミート スプラインは、通常、連続関数を取得するために、指定された引数値 で指定された数値データを補間するために使用されます。データは、各 での目的の関数値と導関数で構成されている必要があります。(値のみが提供される場合、導関数はそれらから推定する必要があります。) エルミート公式は、各区間に個別に適用されます。結果として得られるスプラインは連続し、連続する 1 次導関数を持ちます。 ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$${\displaystyle x_{k}}$${\displaystyle (x_{k},x_{k+1})}$

3 次多項式スプラインは他の方法でも指定できますが、最も一般的なのはベジェ 3 次です。ただし、これら 2 つの方法では同じスプライン セットが提供され、ベジェ形式とエルミート形式の間でデータを簡単に変換できるため、これらの名前は同義語として使用されることがよくあります。

3次多項式スプラインは、コンピュータグラフィックスや幾何学的モデリングにおいて、平面または3次元空間の指定された点を通過する曲線や運動軌跡を得るために広く使用されています。これらのアプリケーションでは、平面または空間の各座標は、個別のパラメータtの3次スプライン関数によって個別に補間されます 。3次多項式スプラインは、オイラー・ベルヌーイ梁理論などの構造解析アプリケーションでも広く使用されています。3次多項式スプラインは、死亡率分析^{[2]や死亡率予測[3]}にも適用されています。

3 次スプラインは、いくつかの方法で 2 つ以上のパラメータの関数に拡張できます。双 3 次スプライン (双 3 次補間) は、デジタル画像のピクセル値や地形の 高度データなど、規則的な長方形グリッド上のデータを補間するためによく使用されます。3 つの双 3 次スプラインによって定義される双 3 次表面パッチは、コンピュータ グラフィックスに不可欠なツールです。

3 次スプラインは、特にコンピュータ グラフィックスでは、 csplineと呼ばれることがよくあります。 エルミート スプラインは、Charles Hermiteにちなんで名付けられました。

単位区間 において、での開始点とでの開始接線、で終了接線を持つ で終了点が与えられると、多項式はt ∈ [0, 1] で定義できます 。${\displaystyle [0,1]}$${\displaystyle {\boldsymbol {p}}_{0}}$${\displaystyle t=0}$${\displaystyle {\boldsymbol {p}}_{1}}$${\displaystyle t=1}$${\displaystyle {\boldsymbol {m}}_{0}}$${\displaystyle t=0}$${\displaystyle {\boldsymbol {m}}_{1}}$${\displaystyle t=1}$$${\displaystyle {\boldsymbol {p}}(t)=\left(2t^{3}-3t^{2}+1\right){\boldsymbol {p}}_{0}+\left(t^{3}-2t^{2}+t\right){\boldsymbol {m}}_{0}+\left(-2t^{3}+3t^{2}\right){\boldsymbol {p}}_{1}+\left(t^{3}-t^{2}\right){\boldsymbol {m}}_{1},}$$

任意の区間での補間は、変数のアフィン変換（次数 1）によってを にマッピングすることによって行われます。式は で、 は以下で定義される基底関数を参照します。単位区間の方程式と比較して、 接線値が でスケーリングされていることに注意してください。${\displaystyle x}$${\displaystyle (x_{k},x_{k+1})}$${\displaystyle [0,1]}$$${\displaystyle {\boldsymbol {p}}(x)=h_{00}(t){\boldsymbol {p}}_{k}+h_{10}(t)(x_{k+1}-x_{k}){\boldsymbol {m}}_{k}+h_{01}(t){\boldsymbol {p}}_{k+1}+h_{11}(t)(x_{k+1}-x_{k}){\boldsymbol {m}}_{k+1},}$$${\displaystyle t=(x-x_{k})/(x_{k+1}-x_{k})}$${\displaystyle h}$${\displaystyle x_{k+1}-x_{k}}$

上記の式は、指定された接線を持つ 2 つの点間の一意の 3 次多項式パスを提供します。

証明。与えられた境界条件を満たす 2 つの 3 次多項式を とします。次に次のように定義します。 ${\displaystyle P,Q}$${\displaystyle R=QP,}$

${\displaystyle R(0)=Q(0)-P(0)=0,}$

${\displaystyle R(1)=Q(1)-P(1)=0.}$

と はどちらも3次多項式なので、は最大でも3次多項式です。したがって、 はという形式である必要があります 。 導関数を計算すると、 ${\displaystyle Q}$${\displaystyle P}$${\displaystyle R}$${\displaystyle R}$$${\displaystyle R(x)=ax(x-1)(xr).}$$$${\displaystyle R'(x)=ax(x-1)+ax(xr)+a(x-1)(xr).}$$

さらに、

${\displaystyle R'(0)=Q'(0)-P'(0)=0,}$

${\displaystyle R'(1)=Q'(1)-P'(1)=0,}$

（１）と（２）を合わせると、 となり、したがって${\displaystyle a=0}$${\displaystyle R=0,}$${\displaystyle P=Q.}$

補間多項式は次のように表すことができます 。 ここで、、、はエルミート基底関数です。これらはさまざまな方法で表すことができ、それぞれの方法で異なる特性が明らかになります 。$${\displaystyle {\boldsymbol {p}}(t)=h_{00}(t){\boldsymbol {p}}_{0}+h_{10}(t)(x_{k+1}-x_{k}){\boldsymbol {m}}_{0}+h_{01}(t){\boldsymbol {p}}_{1}+h_{11}(t)(x_{k+1}-x_{k}){\boldsymbol {m}}_{1}}$$${\displaystyle h_{00}}$${\displaystyle h_{10}}$${\displaystyle h_{01}}$${\displaystyle h_{11}}$

「展開」列は、上記の定義で使用されている表現を示しています。「因数分解」列は、境界でと がゼロになることをすぐに示しています。さらに、とは 0 で重複度 2 のゼロを持ち、 とは1 で重複度 2 のゼロを持つため、それらの境界で傾きが 0 であると結論付けることができます。「Bernstein」列は、エルミート基底関数を3 次 ベルンシュタイン多項式に分解したものを示しています。${\displaystyle h_{10}}$${\displaystyle h_{11}}$${\displaystyle h_{01}}$${\displaystyle h_{11}}$${\displaystyle h_{00}}$${\displaystyle h_{10}}$$${\displaystyle B_{k}(t)={\binom {3}{k}}\cdot t^{k}\cdot (1-t)^{3-k}.}$$

この接続を使用すると、 4 つの値に関して3 次ベジェ曲線で 3 次エルミート補間を表現し、 de Casteljau アルゴリズムを使用してエルミート補間を行うことができます。これは、3 次ベジェ パッチで、中央の 2 つの制御点が、それぞれの外側の点で補間曲線の接線を決定することを示しています。 ${\textstyle {\boldsymbol {p}}_{0},{\boldsymbol {p}}_{0}+{\frac {1}{3}}{\boldsymbol {m}}_{0},{\boldsymbol {p}}_{1}-{\frac {1}{3}}{\boldsymbol {m}}_{1},{\boldsymbol {p}}_{1}}$

多項式を標準形式で次のように記述することもできます 。ここで、制御点と接線は係数です。これにより、定数係数を一度計算して再利用できるため、 t のさまざまな値で多項式を効率的に評価できます。 $${\displaystyle {\boldsymbol {p}}(t)=\left(2{\boldsymbol {p}}_{0}+{\boldsymbol {m}}_{0}-2{\boldsymbol {p}}_{1}+{\boldsymbol {m}}_{1}\right)t^{3}+\left(-3{\boldsymbol {p}}_{0}+3{\boldsymbol {p}}_{1}-2{\boldsymbol {m}}_{0}-{\boldsymbol {m}}_{1}\right)t^{2}+{\boldsymbol {m}}_{0}t+{\boldsymbol {p}}_{0}}$$

のデータ セットは、各区間に上記の手順を適用することで補間できます。ここで、接線は適切な方法で選択されます。つまり、端点を共有する区間の接線は等しくなります。補間された曲線は区分 3 次エルミート スプラインで構成され、 で大域的に連続的に微分可能です。 ${\displaystyle (x_{k},{\boldsymbol {p}}_{k})}$${\displaystyle k=1,\ldots ,n}$${\displaystyle (x_{1},x_{n})}$

接線の選択は一意ではなく、いくつかのオプションが利用可能です。

最も単純な選択は、一定の間隔の長さを必要としない 3 点差です。

${\displaystyle {\boldsymbol {m}}_{k}={\frac {1}{2}}\left({\frac {{\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k}}{x_{k+1}-x_{k}}}+{\frac {{\boldsymbol {p}}_{k}-{\boldsymbol {p}}_{k-1}}{x_{k}-x_{k-1}}}\right)}$

内部ポイントについては、データセットのエンドポイントでの片側差です。 ${\displaystyle k=2,\dots ,n-1}$

カーディナルスプライン（正準スプラインとも呼ばれる）^[4]は、次の式で得られる^[5]。

${\displaystyle {\boldsymbol {m}}_{k}=(1-c){\frac {{\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k-1}}{x_{k+1}-x_{k-1}}}}$

は接線の計算に使用されます。パラメータcは張力パラメータであり、 [0, 1] の範囲内になければなりません。ある意味では、これは接線の「長さ」として解釈できます。c =  1 を選択すると、すべての接線がゼロになり、c  = 0を選択すると、均一なパラメータ化の場合に Catmull-Rom スプラインが生成されます。

選択された接線については

${\displaystyle {\boldsymbol {m}}_{k}={\frac {{\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k-1}}{2}}}$

カーディナルスプラインの特殊なケースである Catmull-Rom スプラインが得られます。これは、均一なパラメータ間隔を前提としています。

この曲線は、エドウィン・キャットマルとラファエル・ロムにちなんで名付けられました。この手法の主な利点は、元の点の集合に沿った点が、スプライン曲線の制御点も構成することです。^[7]曲線の両端にさらに 2 つの点が必要です。均一なキャットマル・ロム実装では、ループと自己交差が発生する可能性があります。弦および求心キャットマル・ロム実装^[8]はこの問題を解決しますが、若干異なる計算を使用します。^[9]コンピュータグラフィックスでは、キャットマル・ロム スプラインは、キー フレーム間の滑らかな補間モーションを取得するために頻繁に使用されます。たとえば、離散キー フレームから生成されるほとんどのカメラ パス アニメーションは、キャットマル・ロム スプラインを使用して処理されます。キャットマル・ロム スプラインが人気を博している理由は、主に計算が比較的簡単であること、各キー フレームの位置に正確に到達すること、生成された曲線の接線が複数のセグメントにわたって連続していることが保証されることです。

Kochanek–Bartels スプラインは、データ ポイント、が与えられた場合に接線を選択する方法をさらに一般化したものであり、張力、バイアス、連続性パラメータの 3 つのパラメータを指定できます。 ${\displaystyle {\boldsymbol {p}}_{k-1}}$${\displaystyle {\boldsymbol {p}}_{k}}$${\displaystyle {\boldsymbol {p}}_{k+1}}$

上記のいずれかのタイプの 3 次エルミート スプラインを単調なデータ セットの補間に使用する場合、補間された関数は必ずしも単調になるわけではありませんが、接線を調整することで単調性を維持できます。

点の単一の座標とを、関数f ( x ) が整数座標x  = n  − 1、n、n  + 1、n + 2で取る値として考えると 、 ${\displaystyle {\boldsymbol {p}}_{n-1},{\boldsymbol {p}}_{n},{\boldsymbol {p}}_{n+1}}$${\displaystyle {\boldsymbol {p}}_{n+2}}$

${\displaystyle p_{n}=f(n)\quad \forall n\in \mathbb {Z} .}$

さらに、端点における接線は隣接する点の中心差として定義されていると仮定します。 $${\displaystyle m_{n}={\frac {f(n+1)-f(n-1)}{2}}={\frac {p_{n+1}-p_{n-1}}{2}}\quad \forall n\in \mathbb {Z} .}$$

実数xの補間f ( x ) を評価するには、まずx を整数部分nと小数部分uに分離します。

${\displaystyle x=n+u,}$

${\displaystyle n=\lfloor x\rfloor =\operatorname {floor} (x),}$

${\displaystyle u=x-n=x-\lfloor x\rfloor ,}$

${\displaystyle 0\leq u<1,}$

ここで、 はfloor 関数を表し、 x以下の最大の整数を返します。 ${\displaystyle \lfloor x\rfloor }$

するとCatmull-Romスプラインは^[10] となり 、ここで は行列転置を表します。下の等式はホーナー法の適用を表しています。 $${\displaystyle {\begin{aligned}f(x)=f(n+u)&={\text{CINT}}_{u}(p_{n-1},p_{n},p_{n+1},p_{n+2})\\&={\begin{bmatrix}1&u&u^{2}&u^{3}\end{bmatrix}}{\begin{bmatrix}0&1&0&0\\-{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0\\1&-{\tfrac {5}{2}}&2&-{\tfrac {1}{2}}\\-{\tfrac {1}{2}}&{\tfrac {3}{2}}&-{\tfrac {3}{2}}&{\tfrac {1}{2}}\end{bmatrix}}{\begin{bmatrix}p_{n-1}\\p_{n}\\p_{n+1}\\p_{n+2}\end{bmatrix}}\\&={\frac {1}{2}}{\begin{bmatrix}-u^{3}+2u^{2}-u\\3u^{3}-5u^{2}+2\\-3u^{3}+4u^{2}+u\\u^{3}-u^{2}\end{bmatrix}}^{\mathrm {T} }{\begin{bmatrix}p_{n-1}\\p_{n}\\p_{n+1}\\p_{n+2}\end{bmatrix}}\\&={\frac {1}{2}}{\begin{bmatrix}u{\big (}(2-u)u-1{\big )}\\u^{2}(3u-5)+2\\u{\big (}(4-3u)u+1{\big )}\\u^{2}(u-1)\end{bmatrix}}^{\mathrm {T} }{\begin{bmatrix}p_{n-1}\\p_{n}\\p_{n+1}\\p_{n+2}\end{bmatrix}}\\&={\tfrac {1}{2}}{\Big (}{\big (}u^{2}(2-u)-u{\big )}p_{n-1}+{\big (}u^{2}(3u-5)+2{\big )}p_{n}+{\big (}u^{2}(4-3u)+u{\big )}p_{n+1}+u^{2}(u-1)p_{n+2}{\Big )}\\&={\tfrac {1}{2}}{\big (}(-u^{3}+2u^{2}-u)p_{n-1}+(3u^{3}-5u^{2}+2)p_{n}+(-3u^{3}+4u^{2}+u)p_{n+1}+(u^{3}-u^{2})p_{n+2}{\big )}\\&={\tfrac {1}{2}}{\big (}(-p_{n-1}+3p_{n}-3p_{n+1}+p_{n+2})u^{3}+(2p_{n-1}-5p_{n}+4p_{n+1}-p_{n+2})u^{2}+(-p_{n-1}+p_{n+1})u+2p_{n}{\big )}\\&={\tfrac {1}{2}}{\Big (}{\big (}(-p_{n-1}+3p_{n}-3p_{n+1}+p_{n+2})u+(2p_{n-1}-5p_{n}+4p_{n+1}-p_{n+2}){\big )}u+(-p_{n-1}+p_{n+1}){\Big )}u+p_{n},\end{aligned}}}$$${\displaystyle \mathrm {T} }$

この記述は三次補間に関連しており、1 つの最適化では、同じuと異なるpを使用して CINT _{u を}16 回計算する必要があります。

• 双三次補間、2次元への一般化
• 三次元への一般化である三次補間
• エルミート補間
• 多変量補間
• スプライン補間
• 離散スプライン補間

• スプライン曲線、ドナルド・H・ハウス教授、クレムソン大学
• 多次元エルミート補間と近似、パデュー大学、チャンドラジット・バジャジ教授
• Catmull-Rom スプラインの紹介、MVPs.org
• カーディナルスプラインとキャットマルロムスプラインの補間
• 補間方法: 線形、コサイン、キュービック、エルミート (C ソースを使用)
• 一般的なスプライン方程式