ド・ブールのアルゴリズム

Method of evaluating spline curves

数値解析という数学の分野において、ド・ブールのアルゴリズム^[1]は、Bスプライン形式のスプライン曲線を評価するための多項式時間かつ数値的に安定したアルゴリズムである。これは、ベジェ曲線に対するド・カステルジョのアルゴリズムの一般化である。このアルゴリズムは、ドイツ系アメリカ人の数学者カール・R・ド・ブールによって考案された。ド・ブールのアルゴリズムを簡略化し、より高速化できる可能性のある変種も作成されているが、安定性が比較的低いという欠点がある。^{[2] [3]}

導入

Bスプラインの概要はメイン記事で説明しています。ここでは、位置 にあるスプライン曲線を評価するための効率的で数値的に安定した手法である de Boor のアルゴリズムについて説明します。この曲線は、潜在的にベクトル値の定数（制御点と呼ばれる） を乗じたBスプライン関数の和から構築されます。次数 のBスプラインは、ノットのグリッド上で定義された次数 の区分的多項式関数に接続されています（以下では常にゼロベースのインデックスを使用します）。De Boor のアルゴリズムは、O (p ² ) + O (p) 回の演算を使用してスプライン曲線を評価します。注：Bスプラインに関するメイン記事と古典的な出版物^[1]では、異なる表記法が使用されています。Bスプラインは でインデックスが付けられます。 ${\displaystyle \mathbf {S} (x)}$ ${\displaystyle x}$ ${\displaystyle B_{i,p}(x)}$ ${\displaystyle \mathbf {c} _{i}}$ $${\displaystyle \mathbf {S} (x)=\sum _{i}\mathbf {c} _{i}B_{i,p}(x).}$$ ${\displaystyle p+1}$ ${\displaystyle p}$ ${\displaystyle {t_{0},\dots ,t_{i},\dots ,t_{m}}}$ ${\displaystyle B_{i,n}(x)}$ ${\displaystyle n=p+1}$

現地サポート

Bスプラインは局所サポートを持ち、つまり多項式はコンパクト領域内でのみ正となり、それ以外の領域では零となる。Cox-de Boorの再帰式^[4]はこれを示している。 $${\displaystyle B_{i,0}(x):={\begin{cases}1&{\text{if }}\quad t_{i}\leq x<t_{i+1}\\0&{\text{otherwise}}\end{cases}}}$$ $${\displaystyle B_{i,p}(x):={\frac {x-t_{i}}{t_{i+p}-t_{i}}}B_{i,p-1}(x)+{\frac {t_{i+p+1}-x}{t_{i+p+1}-t_{i+1}}}B_{i+1,p-1}(x).}$$

インデックス は位置 を含むノット区間を定義します。再帰式から、このノット区間では を持つBスプラインのみが非ゼロであることが分かります。したがって、和は次のように簡約されます。 ${\displaystyle k}$ ${\displaystyle x\in [t_{k},t_{k+1})}$ ${\displaystyle i=k-p,\dots ,k}$ $${\displaystyle \mathbf {S} (x)=\sum _{i=k-p}^{k}\mathbf {c} _{i}B_{i,p}(x).}$$

からが導かれます。同様に、再帰において、最も高いクエリノット位置はインデックス にあることがわかります。これは、実際に使用されるノット間隔には、その前後に少なくとも 個の追加ノットが存在する必要があることを意味します。コンピュータプログラムでは、これは通常、最初に使用されたノット位置の時刻と最後に使用されたノット位置の時刻を繰り返すことによって実現されます。例えば、と実際のノット位置 の場合、ノットベクトルを にパディングします。 ${\displaystyle i\geq 0}$ ${\displaystyle k\geq p}$ ${\displaystyle k+1+p}$ ${\displaystyle [t_{k},t_{k+1})}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p=3}$ ${\displaystyle (0,1,2)}$ ${\displaystyle (0,0,0,0,1,2,2,2,2)}$

アルゴリズム

これらの定義を用いて、de Boorのアルゴリズムを記述することができます。このアルゴリズムはBスプライン関数を直接計算するのではなく、等価な再帰式を用いて評価します。 ${\displaystyle B_{i,p}(x)}$ ${\displaystyle \mathbf {S} (x)}$

を とする新しい制御点とし、 に対して以下の再帰が適用されます。 ${\displaystyle \mathbf {d} _{i,r}}$ ${\displaystyle \mathbf {d} _{i,0}:=\mathbf {c} _{i}}$ ${\displaystyle i=k-p,\dots ,k}$ ${\displaystyle r=1,\dots ,p}$ $${\displaystyle \mathbf {d} _{i,r}=(1-\alpha _{i,r})\mathbf {d} _{i-1,r-1}+\alpha _{i,r}\mathbf {d} _{i,r-1};\quad i=k-p+r,\dots ,k}$$ $${\displaystyle \alpha _{i,r}={\frac {x-t_{i}}{t_{i+1+p-r}-t_{i}}}.}$$

反復が完了すると、 が得られ、これが望ましい結果であることを意味します。 ${\displaystyle \mathbf {S} (x)=\mathbf {d} _{k,p}}$ ${\displaystyle \mathbf {d} _{k,p}}$

De Boor のアルゴリズムは、必ずゼロが乗算される項を計算しないため、Cox-de Boor 再帰式を使用したB スプラインの明示的な計算よりも効率的です。 ${\displaystyle B_{i,p}(x)}$

最適化

上記のアルゴリズムは、コンピュータへの実装に最適化されていません。一時的な制御点のためのメモリを必要とします。各一時的な制御点は、正確に1回書き込まれ、2回読み込まれます。 の反復処理を逆にする（カウントアップではなくカウントダウンする）ことで、 のメモリを再利用し、一時的な制御点のためのメモリのみを使用してアルゴリズムを実行できます。同様に、 の値は各ステップで1つしか使用されないため、メモリも再利用できます。 ${\displaystyle (p+1)+p+\dots +1=(p+1)(p+2)/2}$ ${\displaystyle \mathbf {d} _{i,r}}$ ${\displaystyle i}$ ${\displaystyle p+1}$ ${\displaystyle \mathbf {d} _{i,r}}$ ${\displaystyle \mathbf {d} _{i,r-1}}$ ${\displaystyle \alpha }$

さらに、一時的な制御点にはゼロベースのインデックスを使用する方が便利です。以前のインデックスとの関係は です。これにより、改良されたアルゴリズムが得られます。 ${\displaystyle j=0,\dots ,p}$ ${\displaystyle i=j+k-p}$

を とします。を について繰り返します。jはカウントダウンする必要があることに注意してください。反復処理が完了すると、結果は となります。 ${\displaystyle \mathbf {d} _{j}:=\mathbf {c} _{j+k-p}}$ ${\displaystyle j=0,\dots ,p}$ ${\displaystyle r=1,\dots ,p}$ $${\displaystyle \mathbf {d} _{j}:=(1-\alpha _{j})\mathbf {d} _{j-1}+\alpha _{j}\mathbf {d} _{j};\quad j=p,\dots ,r\quad }$$ $${\displaystyle \alpha _{j}:={\frac {x-t_{j+k-p}}{t_{j+1+k-r}-t_{j+k-p}}}.}$$ ${\displaystyle \mathbf {S} (x)=\mathbf {d} _{p}}$

実装例

Python プログラミング言語の次のコードは、最適化されたアルゴリズムの単純な実装です。

deBoor の定義( k : int , x : int , t , c , p : int ):         S(x)を評価します。 議論 --------- k: xを含むノット間隔のインデックス。 x: 位置。 t: ノット位置の配列。上記のようにパディングする必要があります。 c: 制御点の配列。 p: Bスプラインの次数。 「」 d  =  [ c [ j  +  k  -  p ]  （ j は 範囲（0 、 p  +  1 ））]   r が 範囲( 1 ,  p  +  1 )の場合:  j が 範囲( p ,  r  -  1 ,  - 1 )の場合: アルファ =  ( x  -  t [ j  +  k  -  p ])  /  ( t [ j  +  1  +  k  -  r ]  -  t [ j  +  k  -  p ])  d [ j ]  =  ( 1.0  - アルファ)  *  d [ j  -  1 ]  + アルファ *  d [ j ]  d [ p ]を返す

参照

• ドゥ・カステルジョーのアルゴリズム
• ベジェ曲線
• 非一様有理Bスプライン

外部リンク

• ド・ブールのアルゴリズム
• デブール・コックス計算

コンピュータコード

• PPPACK: Fortranの多くのスプラインアルゴリズムが含まれています
• GNU Scientific Library: Cライブラリ、 PPPACKから移植されたスプラインのサブライブラリを含む
• SciPy: Pythonライブラリ。FITPACKに基づくスプライン関数を備えたサブライブラリscipy.interpolateが含まれています。
• TinySpline: C++ ラッパーと C#、Java、Lua、PHP、Python、Rubyのバインディングを備えたスプライン用の C ライブラリ
• Einspline: Fortran ラッパーを使用した 1 次元、2 次元、3 次元のスプライン用の C ライブラリ

参考文献

1. C. de Boor [1971]、「Bスプライン計算用サブルーチンパッケージ」、Techn.Rep. LA-4728-MS、Los Alamos Sci.Lab、Los Alamos NM; p. 109、121。
2. Lee, ETY (1982年12月). 「簡略化されたBスプライン計算ルーチン」. Computing . 29 (4). Springer-Verlag: 365– 371. doi :10.1007/BF02246763. S2CID  2407104.
3. Lee, ETY (1986). 「いくつかのBスプラインアルゴリズムに関するコメント」. Computing . 36 (3). Springer-Verlag: 229– 238. doi :10.1007/BF02240069. S2CID  7003455.
4. C. de Boor、90ページ

引用文献

• カール・デ・ブール（2003年）『スプライン実践ガイド 改訂版』Springer-Verlag. ISBN 0-387-95366-3。

Retrieved from "https://en.wikipedia.org/w/index.php?title=De_Boor%27s_algorithm&oldid=1305046057"