Skip to content

Uniform B-Spline Interpolation passes through all data points.

License

Notifications You must be signed in to change notification settings

LUXOPHIA/TrueBSplineInterpolation

Repository files navigation

True B-Spline Interpolation

How to generate control points (green) for a uniform B-Spline curve (blue) that passes through all data points (red).
すべての データ点(赤)を通る 一様Bスプライン曲線(青)のための 制御点(緑)を生成する方法。


■ 1. B-Spline Curve is not Interpolation

The uniform B-Spline curve (BSC) is a method to generate smooth and controllable segmented polynomials by arranging uniform B-Spline basis functions (CBS: B-Spline basis) with different weights (control point positions) in equal intervals. Here, if we consider the control point sequence (CPs) as a discrete signal, it can be interpreted as a kind of signal processing using the B-spline basis as a filter.
一様Bスプライン曲線(BSC)は、重み(制御点位置)の異なる 一様Bスプライン基底関数(CBS:BS基底) を等間隔に並べることで、滑らかで制御性の高い区分多項式を生成する手法である。ここで 制御点列(CPs)を離散信号とみなせば、BS基底をフィルタとして用いる一種の信号処理であると解釈できる。

The B-Spline basis can freely change the degree of the polynomial. In zero-degree (1st-order), it is equivalent to the segmented staircase approximation using square waves, and In the 1st-degree (2nd-order), it is equivalent to the segmented linear approximation using triangular waves.
BS基底は多項式の次数を自在に変化させることができる。0次(1階)では矩形波による区分階段近似と等価となり、1次(2階)では三角波による区分線形近似と等価となる。

CBS[ N_, X_ ] = BSplineBasis[ N-1, (X+N/2)/N ]; @ Wolfram Language

N:order(階数)= 1 + degree(次数)






The frequency distribution of the B-Spline basis is defined as the power of the Sinc function. Since it has a strong low-pass characteristic, filtering by the B-Spline basis significantly attenuates the high-frequency components inherent in the control point sequence. In other words, the smoothing effect is so strong that the generating curve is very smooth, but it is an approximate curve that does not pass through any control points.
BS基底の周波数分布は、Sinc 関数の累乗として定義される。強い低域通過特性を持っているため、BS基底によるフィルタリングは、制御点列が本来持つ高周波成分を大幅に減衰させる。つまり平滑化の作用が強いため、生成される曲線は非常に滑らかであるが、制御点を通らない 近似曲線 となる。

■ 2. B-Spline Basis as Discrete Filter

Although the B-Spline basis is a continuous filter, it can be regarded as a discrete filter if we focus only on the control points' values. In other words, whether or not the curve passes through the control point depends on the frequency response of the Discrete B-Spline basis function (DBS: discrete B-Spline basis).
BS基底は連続フィルタであるが、制御点での値のみに注目すると、離散フィルタとみなすことができる。つまり曲線が制御点を通るか否かは、離散Bスプライン基底関数(DBS:離散BS基底) の周波数特性に依存している。

The frequency distribution of the discrete B-Spline basis is periodic. Still, above the 3rd-order, it has a low-pass characteristic most attenuated at the Nyquist frequency (π). Conversely, discrete B-Spline basis below the 2nd-order do not attenuate the high-frequency components, so the generated curve always passes through the control point.
離散BS基底の周波数分布は周期性を持つが、3階以上では ナイキスト周波数(π)において最も減衰する低域通過特性を持つ。逆に2階以下のBS基底は高周波成分を減衰させないので、生成される曲線は必ず制御点を通過する。

■ 3. Discrete High-Enhancement filter

In order to pass a curve through the control points, it is necessary to restore the original high-frequency components of the control point sequence. To do this, we can design a Discrete High-Enhancement filter (DHE) that cancels the low-pass characteristics of the discrete B-Spline basis. In other words, its frequency distribution is the inverse of that in the discrete B-Spline basis.
制御点に曲線を通すためには、制御点列が持つ本来の高周波成分を復元する必要がある。そのためには、離散BS基底の低域通過特性を打ち消す 離散高域強調フィルタ(DHE) を設計すればよい。つまりその周波数分布は、離散BS基底のそれの逆数となる。

A discrete high-enhancement filter below the 4th-order can be derived analytically using the Hypergeometric function.
4階以下の離散高域強調フィルタは、超幾何関数を用いて解析的に導くことができる。

At first glance, the expression seems complicated, but we can see that the absolute value follows a simple exponential function (CHE).
一見複雑な関数に思えるが、絶対値が 単純な指数関数(CHE)に沿っていることが分かる。

Furthermore, since the original function's sign is alternating positive and negative, we can eliminate the hypergeometric function and derive a very simple expression (CHE).
さらに、元々の関数の符合が正負を交互に繰り返していることから、超幾何関数を排して 非常に簡単な式(CHE)を導くことができる。

The discrete high-enhancement filter is an infinite impulse response (IIR) filter. Therefore, it is necessary to cut off the coefficient sequence with an appropriate number of taps in a practical implementation.
離散高域強調フィルタは、無限インパルス応答(IIR)フィルタである。ゆえに実際の実装では、適当なタップ数で打ち切る必要がある。

DHE 3 DHE 4

The frequency distribution of a finite impulse response (FIR) filter, i.e., an approximated discrete high-enhancement filter (AHE), is almost identical to that of an ideal discrete high-enhancement filter (DHE). Empirically, 7-taps (±3) for the 3rd-order case and 9-taps (±4) for the 4th-order case are enough to guarantee accuracy.
有限インパルス応答(FIR)フィルタ,すなわち 近似的な離散高域強調フィルタ(AHE)の周波数分布は、理想的な離散高域強調フィルタ(DHE)のそれとほぼ一致する。経験的には、3階では7タップ(±3)、4階では9タップ(±4)あれば、十分な精度が保証される。


■ 4. Reference


Delphi Starter