にせねこメモ

はてなダイアリーがUTF-8じゃないので移ってきました。

1次B-スプライン曲線の制御点列をそのまま利用して2次B-スプライン曲線で1次B-スプライン曲線を近似する

画像処理 TrueType

問題提起

1次B-スプライン曲線(linear B-spline curve)とはすなわち折れ線のことである。
これはシンプルで、隣り合う2制御点を順番に直線で結んでいけば求める曲線(というか折れ線)が描ける。

一方で、2次B-スプライン曲線(quadratic B-spline curve)はB-スプライン基底関数という2次関数を使って制御点の影響を計算して曲線を描く。
基本的に2次B-スプライン曲線では、連続する制御点を結んだ折れ線、つまり直線の連続を描くことができない。
1次B-スプライン曲線の隣り合う2制御点の中点*1を制御点として2点間に挿入し、ノットベクトル(後述)を[0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 4]みたいにすると直線が表現できるが、制御点列としては別のものになる。


さて、ここで、1次B-スプライン曲線の制御点列をそのまま利用して、2次B-スプライン曲線で1次B-スプライン曲線を表現することはできるだろうか？

モチベーション

TrueTypeアウトラインの曲線部分は2次B-スプライン曲線の特殊な場合であるが、2次B-スプライン曲線は隣り合う2制御点を結ぶような折れ線、つまり1次B-スプライン曲線はふつう表現できない。そのため、TrueTypeアウトラインのcontourの制御点と2次B-スプライン曲線の制御点は同一ではないと考えていた。

一方で、もしそのような折れ線を2次B-スプラインで表現できるのであれば、直線部分も2次B-スプライン曲線として表現可能になり、任意のTrueTypeアウトラインは制御点を挿入することなしに2次B-スプライン曲線だと言えるのではないかと思う。

B-スプライン曲線の定義

n次のB-スプライン曲線とは、制御点列(control points) \{\boldsymbol P_i\}とノットベクトル(knot vector) \{ t_i \}で定義される曲線である。曲線の補間(制御点の影響の計算)にはn次のB-スプライン基底関数が用いられる。

n次のB-スプライン基底関数(n-th order B-spline basis function) N_i^n(t)は、次のように定義される。(コンピュータグラフィックス編集委員会(2004), p.66 (3.29)式)
\displaystyle N_i^0(t) = \left\{ \begin{array}{ll} 1 & (\text{if} \quad t_i \leq t < t_{i+1}) \\ 0 & (\text{if} \quad t_i \leq t < t_{i+1}) \end{array} \right.

\displaystyle N_i^n(t) = \frac{t-t_i}{t_{i+n}-t_{i}} N_i^{n-1}(t) + \frac{t_{i+n+1}-t}{t_{i+n+1}-t_{i+1}} N_{i+1}^{n-1}(t) \quad (n\geq 1)

これを使って、L個のセグメントからなるn次B-スプライン曲線は次のように定義される。
\displaystyle \boldsymbol{P}(t) = \sum_{i=0}^{n+L-1}\boldsymbol{P}_iN_i^n(t) \quad (t_n \leq t < t_{n+L})

1次B-スプライン曲線

さてここで、1次B-スプライン曲線の場合を見ていく。

L個のセグメントからなる1次B-スプライン曲線は次のように定義される。
\displaystyle \boldsymbol{P}(t) = \sum_{i=0}^{L}\boldsymbol{P}_iN_i^1(t) \quad (t_1 \leq t < t_{L+1})

ここで、 0 \leq k < Lなる整数 kに関して、点 \boldsymbol{P}_kと \boldsymbol{P}_{k+1}で定義される一つのセグメント ( t_{k+1} \leq t < t_{k+2})だけをみると、
\displaystyle \boldsymbol{P}(t) = \boldsymbol{P}_kN_k^1(t) + \boldsymbol{P}_{k+1}N_{k+1}^1(t)

ここで、B-スプライン基底関数は次のようになる。
\displaystyle N_k^0(t) = 0

\displaystyle N_{k+1}^0(t) = 1

\displaystyle N_{k+2}^0(t) = 0

\displaystyle \begin{eqnarray*} N_k^1(t) &=& \frac{t-t_k}{t_{k+1}-t_k} N_k^0(t) + \frac{t_{k+2}-t}{t_{k+2}-t_{k+1}} N_{k+1}^0(t) \\ &=& \frac{t-t_k}{t_{k+1}-t_k} \cdot 0 + \frac{t_{k+2}-t}{t_{k+2}-t_{k+1}} \cdot 1 \\ &=& \frac{t_{k+2}-t}{t_{k+2}-t_{k+1}} \end{eqnarray*}

\displaystyle \begin{eqnarray*} N_{k+1}^1(t) &=& \frac{t-t_{k+1}}{t_{k+2}-t_{k+1}} N_{k+1}^0(t) + \frac{t_{k+3}-t}{t_{k+3}-t_{k+2}} N_{k+2}^0(t) \\ &=& \frac{t-t_{k+1}}{t_{k+2}-t_{k+1}} \cdot 1 + \frac{t_{k+3}-t}{t_{k+3}-t_{k+2}} \cdot 0 \\ &=& \frac{t-t_{k+1}}{t_{k+2}-t_{k+1}} \end{eqnarray*}

したがって、
\displaystyle \boldsymbol{P}(t) = \frac{t_{k+2}-t}{t_{k+2}-t_{k+1}}\boldsymbol{P}_k + \frac{t-t_{k+1}}{t_{k+2}-t_{k+1}}\boldsymbol{P}_{k+1}
というわけで2点間の線形補間になっている=直線であることがわかる。

2次B-スプライン曲線

さて、次に2次B-スプライン曲線の場合について考える。

2次B-スプライン曲線の1つのセグメントは3点の制御点からなる。そのため、1次B-スプライン曲線と同じ数のセグメントを用意するためには、制御点を最後に一個追加しないといけない。

L個のセグメントからなる2次B-スプライン曲線は次のように定義される。
\displaystyle \boldsymbol{P}(t) = \sum_{i=0}^{L+1}\boldsymbol{P}_iN_i^2(t) \quad (t_2 \leq t < t_{L+2})

ここで、 0 \leq k < Lなる整数 kについて、点 \boldsymbol{P}_kと \boldsymbol{P}_{k+1}, \boldsymbol{P}_{k+2}で定義される一つのセグメント t_{k+2} \leq t < t_{k+3}だけをみると、

\displaystyle \boldsymbol{P}(t) = \boldsymbol{P}_kN_k^2(t) + \boldsymbol{P}_{k+1}N_{k+1}^2(t) + \boldsymbol{P}_{k+2}N_{k+2}^2(t)
となる。

1次B-スプライン曲線の近似

さて、ここでノットベクトルとして次のような公比を無限大に近づけた等比数列 \{ t_i \}を考える*2。
\displaystyle t_i = \lim_{r \to +\infty} ar^{i} ただし \displaystyle a>0

すると、 \displaystyle t_{k+2} \leq t < t_{k+3}において、B-スプライン基底関数は次のように計算される。

後の計算で必要となるもの

\displaystyle \frac{t_{k+2}}{t_{k+3}} = \lim_{r \to +\infty}\frac{1}{r} = 0

\displaystyle \frac{t_{k+3}}{t_{k+4}} = \lim_{r \to +\infty}\frac{1}{r} = 0

\displaystyle \frac{t_{k+2}}{t_{k+4}} = \lim_{r \to +\infty}\frac{1}{r^2} = 0

\displaystyle \frac{t_{k+2}}{t_{k+4}} \leq \frac{t}{t_{k+4}} < \frac{t_{k+3}}{t_{k+4}} \quad (\because t_{k+2} \leq t < t_{k+3})より \displaystyle \frac{t}{t_{k+4}} = 0

0次

\displaystyle N_k^0(t) = 0

\displaystyle N_{k+1}^0(t) = 0

\displaystyle N_{k+2}^0(t) = 1

\displaystyle N_{k+3}^0(t) = 0

\displaystyle N_{k+4}^0(t) = 0

1次

\displaystyle \begin{eqnarray*} N_k^1(t) &=& \frac{t-t_k}{t_{k+1}-t_k} N_k^0(t) + \frac{t_{k+2}-t}{t_{k+2}-t_{k+1}} N_{k+1}^0(t) \\ &=& \frac{t-t_k}{t_{k+1}-t_k} \cdot 0 + \frac{t_{k+2}-t}{t_{k+2}-t_{k+1}} \cdot 0 = 0 \end{eqnarray*}

\displaystyle \begin{eqnarray*} N_{k+1}^1(t) &=& \frac{t-t_{k+1}}{t_{k+2}-t_{k+1}} N_{k+1}^0(t) + \frac{t_{k+3}-t}{t_{k+3}-t_{k+2}} N_{k+2}^0(t) \\ &=& \frac{t-t_{k+1}}{t_{k+2}-t_{k+1}} \cdot 0 + \frac{t_{k+3}-t}{t_{k+3}-t_{k+2}} \cdot 1 = \frac{t_{k+3}-t}{t_{k+3}-t_{k+2}} \end{eqnarray*}

\displaystyle \begin{eqnarray*} N_{k+2}^1(t) &=& \frac{t-t_{k+2}}{t_{k+3}-t_{k+2}} N_{k+2}^0(t) + \frac{t_{k+4}-t}{t_{k+4}-t_{k+3}} N_{k+3}^0(t) \\ &=& \frac{t-t_{k+2}}{t_{k+3}-t_{k+2}} \cdot 1 + \frac{t_{k+4}-t}{t_{k+4}-t_{k+3}} \cdot 0 = \frac{t-t_{k+2}}{t_{k+3}-t_{k+2}} \end{eqnarray*}

\displaystyle \begin{eqnarray*} N_{k+3}^1(t) &=& \frac{t-t_{k+3}}{t_{k+4}-t_{k+3}} N_{k+3}^0(t) + \frac{t_{k+5}-t}{t_{k+5}-t_{k+4}} N_{k+4}^0(t) \\ &=& \frac{t-t_{k+3}}{t_{k+4}-t_{k+3}} \cdot 0 + \frac{t_{k+5}-t}{t_{k+5}-t_{k+4}} \cdot 0 = 0 \end{eqnarray*}

2次

\displaystyle \begin{eqnarray*} N_k^2(t) &=& \frac{t-t_k}{t_{k+2}-t_k} N_k^1(t) + \frac{t_{k+3}-t}{t_{k+3}-t_{k+1}} N_{k+1}^1(t) \\ &=& \frac{t-t_k}{t_{k+2}-t_k} \cdot 0 + \frac{t_{k+3}-t}{t_{k+3}-t_{k+1}} \cdot \frac{t_{k+3}-t}{t_{k+3}-t_{k+2}} \\ &=& \frac{t_{k+3}-t}{t_{k+3}-t_{k+1}} \cdot \frac{t_{k+3}-t}{t_{k+3}-t_{k+2}} \\ &=& \frac{1-\frac{t}{t_{k+3}}}{1-\frac{t_{k+1}}{t_{k+3}}} \cdot \frac{1-\frac{t}{t_{k+3}}}{1-\frac{t_{k+2}}{t_{k+3}}} \\ &=& \left(1-\frac{t}{t_{k+3}}\right)^2 \end{eqnarray*}

\displaystyle \begin{eqnarray*} N_{k+1}^2(t) &=& \frac{t-t_{k+1}}{t_{k+3}-t_{k+1}} N_{k+1}^1(t) + \frac{t_{k+4}-t}{t_{k+4}-t_{k+2}} N_{k+2}^1(t) \\ &=& \frac{t-t_{k+1}}{t_{k+3}-t_{k+1}} \cdot \frac{t_{k+3}-t}{t_{k+3}-t_{k+2}} + \frac{t_{k+4}-t}{t_{k+4}-t_{k+2}} \cdot \frac{t-t_{k+2}}{t_{k+3}-t_{k+2}} \end{eqnarray*}

\displaystyle \begin{eqnarray*} \frac{t-t_{k+1}}{t_{k+3}-t_{k+1}} \cdot \frac{t_{k+3}-t}{t_{k+3}-t_{k+2}} &=& \frac{\frac{t}{t_{k+3}}-\frac{t_{k+1}}{t_{k+3}}}{1-\frac{t_{k+1}}{t_{k+3}}} \cdot \frac{1-\frac{t}{t_{k+3}}}{1-\frac{t_{k+2}}{t_{k+3}}} \\ &=& \frac{t}{t_{k+3}} \left( 1-\frac{t}{t_{k+3}} \right) \end{eqnarray*}

\displaystyle \begin{eqnarray*} \frac{t_{k+4}-t}{t_{k+4}-t_{k+2}} \cdot \frac{t-t_{k+2}}{t_{k+3}-t_{k+2}} &=& \frac{1-\frac{t}{t_{k+4}}}{1-\frac{t_{k+2}}{t_{k+4}}} \cdot \frac{\frac{t}{t_{k+3}}-\frac{t_{k+2}}{t_{k+3}}}{1-\frac{t_{k+2}}{t_{k+3}}} \\ &=& \left( 1-\frac{t}{t_{k+4}}\right) \cdot \frac{t}{t_{k+3}} = \frac{t}{t_{k+3}} \end{eqnarray*}
よって
\displaystyle \begin{eqnarray*} N_{k+1}^2(t) &=& \frac{t}{t_{k+3}} \left( 1-\frac{t}{t_{k+3}} \right) + \frac{t}{t_{k+3}} \\ &=& \frac{t}{t_{k+3}} \left( 2-\frac{t}{t_{k+3}} \right) \end{eqnarray*}

また、
\displaystyle \begin{eqnarray*} N_{k+2}^2(t) &=& \frac{t-t_{k+2}}{t_{k+4}-t_{k+2}} N_{k+2}^1(t) + \frac{t_{k+5}-t}{t_{k+5}-t_{k+3}} N_{k+3}^1(t) \\ &=& \frac{t-t_{k+2}}{t_{k+4}-t_{k+2}} \cdot \frac{t-t_{k+2}}{t_{k+3}-t_{k+2}} + \frac{t_{k+5}-t}{t_{k+5}-t_{k+3}} \cdot 0 \\ &=& \frac{t-t_{k+2}}{t_{k+4}-t_{k+2}} \cdot \frac{t-t_{k+2}}{t_{k+3}-t_{k+2}} \\ &=& \frac{\frac{t}{t_{k+4}}-\frac{t_{k+2}}{t_{k+4}}}{1-\frac{t_{k+2}}{t_{k+4}}} \cdot \frac{\frac{t}{t_{k+3}}-\frac{t_{k+2}}{t_{k+3}}}{1-\frac{t_{k+2}}{t_{k+3}}} \\ &=& \frac{t}{t_{k+4}} \cdot \frac{t}{t_{k+3}} = 0 \cdot \frac{t}{t_{k+3}} = 0 \end{eqnarray*}


ここから、 \displaystyle N_{k+2}^2(t) = 0なので \boldsymbol P_{k+2}の関与が完全になくなっていることがわかる。

また、 \displaystyle N_{k}^2(t) + N_{k+1}^2(t) = 1となることもわかる。

y = \displaystyle N_{k}^2(t), y = \displaystyle N_{k+1}^2(t)のグラフを描くとだいたい次のような感じになる*3。
f:id:nixeneko:20210814154404j:plain

実際に描いてみた

プログラムを使って描いてみた。さすがに無限大は扱えないので適当に大きな値にしてみる。

描画に用いたPython3コードを次に示す*4。STEPが公比rに相当する。
gist.github.com

描画結果

赤が正解となる1次B-スプライン曲線、黒が2次B-スプライン曲線である。

r=10

f:id:nixeneko:20210813092559p:plain

r=100

f:id:nixeneko:20210813092614p:plain

r=1000

f:id:nixeneko:20210813092622p:plain

r=10000

f:id:nixeneko:20210813092638p:plain
r=10000でほぼ一致している。
隣り合う2制御点をr:1で内分する点を通る曲線が描かれているので、r=10000のときは2点を10000:1に内分する点を通る曲線となる。誤差が1ピクセルより小さくなるので直線に見えるというわけである。
画像サイズが(1000, 1000)なので公比r=10000程度でも直線になっているが、ドローソフトで線を拡大していく場合などはそれでも足りなくなると思う。
r=10000の場合、制御点15個に対して最初のノット値と最後のノット値を比べると1064倍になっている。複雑な図形にしたらすぐにあふれそう。

考察

1次B-スプライン曲線を(制御点を変更せずに)2次B-スプライン曲線を使って表現できる(そのようなノットベクトルの取り方が存在する)ことがわかった。

つまり、適切にノットベクトルを用意すれば、TrueTypeアウトラインのcontourをそのまま2次B-スプラインを用いて描画可能なのでは？

というわけで試してみる。
用意するのは次の制御点列。onはTrueTypeにおけるon-curve点、offはoff-curve点を示す。

idx 座標 on/off
0 (10, 10) on
1 (10, 990) on
2 (250, 500) off
3 (500, 990) off
4 (750, 500) off
5 (990, 990) on
6 (990, 10) on
7 (500, 500) off
8 (10, 10) on

これに対して、
\displaystyle \boldsymbol t = \lim_{r \to +\infty}\{r^0, r^0, r^0, r^1, r^2, 2r^2, 3r^2, 4r^2, r^3, r^4, r^4, r^4\}
みたいなノットベクトルを用意してみたらどうだろう。


r=10000として計算したのが次の画像である。この手法で計算された曲線が黒い線となっている。
f:id:nixeneko:20210814200729p:plain
制御点を青の点で示している。制御点列を結んだ直線が水色の直線である。
赤は正解となる2次B-スプライン曲線で、2連続するon-curve点の途中にその2点の中点をoff-curveな制御点として挿入してon-curve点の連続をなくし、ノットベクトルを[0, 0, 0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6]としたものであるが、黒い線の下に入ってほぼ見えなくなっている。

描画に使用したPython3コードは次のものである。


というわけで、こんな感じのわけわからんノットベクトルを用意すれば、同一の制御点列を用いつつも2次B-スプライン曲線はTrueTypeアウトラインのcontourに一致する気がする*5。
ちゃんと計算すれば(上でやったのと同じような議論で)示せると思うけど面倒なので気になったら各自計算してね…

感想

無限大を導入すれば、任意のTrueTypeアウトラインのcontourの制御点列をそのまま2次B-スプライン曲線の制御点列として、同一のアウトラインを描けるノットベクトルの取り方が存在しそう、ということがわかった。無限大を導入すれば……

コンピュータで扱う数値計算に無限大を導入するな💢

実用としては素直に直線で計算するべし。

参考書籍

*1:別に内分点であればいいけど

*2:こういう数式の書き方で正しいのかわからないけど、とにかく公比をめちゃくちゃ大きくした等比数列だと思ってください。

*3:ガタガタしてるように見えるのは描くのが下手なだけので気にしないで…。普通の放物線です。

*4:このコード、めちゃくちゃ効率が悪いしあんまり汎用性もないです。あしからず。

*5:最後が直線になる場合はノット重ねるとベジエになっちゃうのでダミーの制御点追加しないといけないけど、一様B-スプライン曲線の描画と同様に制御点ループさせればいいので問題ないか…。