機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。

勉強ログです。リンクフリーです
目次へ戻る

2次元の点列にフィットする両端点と終点の接ベクトルを固定した3次ベジェ曲線を求める

ベジェ曲線 点列

はじめに

本記事は2次元の点列にフィットする3次ベジェ曲線を求める(以下、元記事)を元に書いています。
元記事に出てくる数は使いまわします。

要件

タイトルの「両端点と終点の接ベクトルを固定した」とは「始点の位置ベクトル」と「終点の位置ベクトル」と「終点の接ベクトル」を固定したという意味です。

求めるべき変数

{\bf p}_3 における符号を反転した接ベクトルのを {\bf t} とします。
{\bf p}_2 は {\bf p}_3 を通り方向ベクトルが {\bf t}=\begin{pmatrix}t_x&t_y\end{pmatrix}^\top の直線上にあり、{\bf p}_3 から見て {\bf t} 方向に存在するとすれば
\alpha>0 を用いて、以下のように書けます。

\begin{eqnarray} {\bf p}_2={\bf p}_3+\alpha{\bf t}\tag{1} \end{eqnarray}

よって、求める変数は {\bf p}_1,\alpha です。

目的関数をx成分の目的関数とy成分の目的関数の和とする

x,y 成分の目的関数をそれぞれ {\rm E}_x,{\rm E}_y とすると、以下のようになります。

\begin{eqnarray} &&{\rm E}_x(p_{1x}, \alpha)=\sum_{n=1}^N(x(t_n)-x_n)^2\tag{2}\\ &&{\rm E}_y(p_{1y}, \alpha)=\sum_{n=1}^N(y(t_n)-y_n)^2\tag{3} \end{eqnarray}

目的関数 {\rm E} を {\rm E}_x,{\rm E}_y を足し合わせて、以下のように定義します。

\begin{eqnarray} {\rm E}(p_{1x}, p_{1y}, \alpha)&=&{\rm E}_x(p_x, \alpha)+{\rm E}_y(p_y, \alpha)\\ &=&\sum_{n=1}^N(x(t_n)-x_n)^2+\sum_{n=1}^N(y(t_n)-y_n)^2\tag{4} \end{eqnarray}

解析的に解く

{\rm E} を p_{1x},p_{1y},\alpha で微分して =0 とおきます。

\begin{eqnarray} \left\{ \begin{array}{l} \dfrac{\partial {\rm E}}{\partial p_{1x}}=0\hspace{100px}(5)\\ \dfrac{\partial {\rm E}}{\partial p_{1y}}=0\hspace{100px}(6)\\ \dfrac{\partial {\rm E}}{\partial \alpha}=0\hspace{110px}(7)\\ \end{array} \right. \end{eqnarray}

式 (5) の左辺を変形します。

\begin{eqnarray} \dfrac{\partial {\rm E}}{\partial p_{1x}}&=&\dfrac{\partial {\rm E}_x}{\partial p_{1x}}+\dfrac{\partial {\rm E}_y}{\partial p_{1y}}\\ &=&\dfrac{\partial {\rm E}_x}{\partial p_{1x}}\\ &=&\dfrac{\partial}{\partial p_{1x}}\sum_{n=1}^N(x(t_n)-x_n)^2\\ &=&2\sum_{n=1}^N(x(t_n)-x_n)\dfrac{\partial}{\partial p_{1x}}(x(t_n)-x_n)\\ &=&2\sum_{n=1}^N(x(t_n)-x_n)\dfrac{\partial}{\partial p_{1x}}({\rm B}_0^3(t_n)p_{0x}+{\rm B}_1^3(t_n)p_{1x}+{\rm B}_2^3(t_n)p_{2x}+{\rm B}_3^3(t_n)p_{3x}-x_n)\\ &=&2\sum_{n=1}^N(x(t_n)-x_n)\dfrac{\partial}{\partial p_{1x}}({\rm B}_0^3(t_n)p_{0x}+{\rm B}_1^3(t_n)p_{1x}+{\rm B}_2^3(t_n)(p_{3x}+\alpha t_x)+{\rm B}_3^3(t_n)p_{3x}-x_n)\\ &=&2\sum_{n=1}^N(x(t_n)-x_n)\dfrac{\partial}{\partial p_{1x}}{\rm B}_1^3(t_n)p_{1x}\\ &=&2\sum_{n=1}^N(x(t_n)-x_n){\rm B}_1^3(t_n)\\ &=&2\sum_{n=1}^N{\rm B}_1^3(t_n)({\rm B}_0^3(t_n)p_{0x}+{\rm B}_1^3(t_n)p_{1x}+{\rm B}_2^3(t_n)(p_{3x}+\alpha t_x)+{\rm B}_3^3(t_n)p_{3x}-x_n)\\ &=&2\left({\rm A}_{1,1}p_{1x}+t_x{\rm A}_{1,2}\alpha+{\rm A}_{1,0}p_{0x}+{\rm A}_{1,2}p_{3x}+{\rm A}_{1,3}p_{3x}-\sum_{n=1}^N{\rm B}_1^3(t_n)x_n\right)\\ &=&2\left({\rm A}_{1,1}p_{1x}+t_x{\rm A}_{1,2}\alpha-X_1\right)\tag{8} \end{eqnarray}

式 (8) で {\rm A}_{i,j}=\displaystyle\sum_{n=1}^N{\rm B}_i^3(t_n){\rm B}_j^3(t_n),\ -X_i={\rm A}_{i,0}p_{0x}+{\rm A}_{i,2}p_{3x}+{\rm A}_{i,3}p_{3x}-\displaystyle\sum_{n=1}^N{\rm B}_i^3(t_n)x_n とおきました。

式 (6) の左辺も同様にして、以下のようになります。

\begin{eqnarray} \dfrac{\partial {\rm E}}{\partial p_{1y}}&=&2\left({\rm A}_{1,1}^2p_{1y}+t_y{\rm A}_{1,2}\alpha-Y_1\right)\tag{9} \end{eqnarray}

式 (9) で -Y_i={\rm A}_{i,0}p_{0y}+{\rm A}_{i,2}p_{3y}+{\rm A}_{i,3}p_{3y}-\displaystyle\sum_{n=1}^N{\rm B}_i^3(t_n)y_n とおきました。

式 (7) の左辺を計算します。

\begin{eqnarray} \dfrac{\partial {\rm E}}{\partial \alpha}=\dfrac{\partial {\rm E}_x}{\partial \alpha}+\dfrac{\partial {\rm E}_y}{\partial \alpha}\tag{10} \end{eqnarray}

式 (10) の \dfrac{\partial {\rm E}_x}{\partial \alpha} を計算します。

\begin{eqnarray} \dfrac{\partial {\rm E}_x}{\partial \alpha}&=&\dfrac{\partial}{\partial \alpha}\sum_{n=1}^N(x(t_n)-x_n)^2\\ &=&2\sum_{n=1}^N(x(t_n)-x_n)\dfrac{\partial}{\partial \alpha}(x(t_n)-x_n)\\ &=&2\sum_{n=1}^N(x(t_n)-x_n)\dfrac{\partial}{\partial \alpha}({\rm B}_0^3(t_n)p_{0x}+{\rm B}_1^3(t_n)p_{1x}+{\rm B}_2^3(t_n)(p_{3x}+\alpha t_x)+{\rm B}_3^3(t_n)p_{3x}-x_n)\\ &=&2\sum_{n=1}^N(x(t_n)-x_n)\dfrac{\partial}{\partial \alpha}{\rm B}_2^3(t_n)\alpha t_x\\ &=&2\sum_{n=1}^N(x(t_n)-x_n){\rm B}_2^3(t_n) t_x\\ &=&2t_x\sum_{n=1}^N{\rm B}_2^3(t_n)({\rm B}_0^3(t_n)p_{0x}+{\rm B}_1^3(t_n)p_{1x}+{\rm B}_2^3(t_n)(p_{3x}+\alpha t_x)+{\rm B}_3^3(t_n)p_{3x}-x_n)\\ &=&2t_x\left({\rm A}_{2,1}p_{1x}+t_x{\rm A}_{2,2}\alpha+{\rm A}_{2,0}p_{0x}+{\rm A}_{2,2}p_{3x}+{\rm A}_{2,3}p_{3x}-\sum_{n=1}^N{\rm B}_2^3(t_n)x_n\right)\\ &=&2\left(t_x{\rm A}_{2,1}p_{1x}+t_x^2{\rm A}_{2,2}\alpha+t_x\left({\rm A}_{2,0}p_{0x}+{\rm A}_{2,2}p_{3x}+{\rm A}_{2,3}p_{3x}-\sum_{n=1}^N{\rm B}_2^3(t_n)x_n\right)\right)\\ &=&2\left(t_x{\rm A}_{2,1}p_{1x}+t_x^2{\rm A}_{2,2}\alpha-t_xX_2\right)\tag{11} \end{eqnarray}

式 (10) の \dfrac{\partial {\rm E}_y}{\partial \alpha} も同様にして、以下のようになります。

\begin{eqnarray} \dfrac{\partial {\rm E}_y}{\partial \alpha}&=&2\left(t_y{\rm A}_{2,1}p_{1y}+t_y^2{\rm A}_{2,2}\alpha-t_yY_2\right)\tag{12} \end{eqnarray}

式 (11),(12) を式 (10) に代入します。

\begin{eqnarray} \dfrac{\partial {\rm E}}{\partial \alpha}&=&2\left(t_x{\rm A}_{2,1}p_{1x}+t_x^2{\rm A}_{2,2}\alpha-t_xX_2\right)+2\left(t_y{\rm A}_{2,1}p_{1y}+t_y^2{\rm A}_{2,2}\alpha-t_yY_2\right)\\ &=&2\left(t_x{\rm A}_{2,1}p_{1x}+t_y{\rm A}_{2,1}p_{1y}+\left(t_x^2{\rm A}_{2,2}+t_y^2{\rm A}_{2,2}\right)\alpha-t_xX_2-t_yY_2\right)\tag{13} \end{eqnarray}

式 (8),(9),(13) をそれぞれ式 (5),(6),(7) に代入します。

\begin{eqnarray} &&\left\{ \begin{array}{l} 2\left({\rm A}_{1,1}p_{1x}+t_x{\rm A}_{1,2}\alpha-X_1\right)=0\\ 2\left({\rm A}_{1,1}p_{1y}+t_x{\rm A}_{1,2}\alpha-Y_1\right)=0\\ 2\left(t_x{\rm A}_{2,1}p_{1x}+t_y{\rm A}_{2,1}^2p_{1y}+\left(t_x^2{\rm A}_{2,2}+t_y^2{\rm A}_{2,2}\right)\alpha-t_xX_2-t_yY_2\right)=0\\ \end{array} \right.\\ &&\Rightarrow\left\{ \begin{array}{l} {\rm A}_{1,1}p_{1x}+t_x{\rm A}_{1,2}\alpha=X_1\\ {\rm A}_{1,1}p_{1y}+t_y{\rm A}_{1,2}\alpha=Y_1\\ t_x{\rm A}_{2,1}p_{1x}+t_y{\rm A}_{2,1}p_{1y}+\left(t_x^2{\rm A}_{2,2}+t_y^2{\rm A}_{2,2}\right)\alpha=t_xX_2+t_yY_2\\ \end{array} \right.\\ &&\Rightarrow \begin{pmatrix} {\rm A}_{1,1} & 0 & t_x{\rm A}_{1,2}\\ 0 & {\rm A}_{1,1} & t_y{\rm A}_{1,2}\\ t_x{\rm A}_{2,1} & t_y{\rm A}_{2,1} & t_x^2{\rm A}_{2,2}+t_y^2{\rm A}_{2,2} \end{pmatrix} \begin{pmatrix}p_{1x}\\ p_{1y}\\ \alpha\end{pmatrix} = \begin{pmatrix}X_1\\Y_1\\t_xX_2+t_yY_2\end{pmatrix}\\ &&\Rightarrow \begin{pmatrix}p_{1x}\\ p_{1y}\\ \alpha\end{pmatrix} = \begin{pmatrix} {\rm A}_{1,1} & 0 & t_x{\rm A}_{1,2}\\ 0 & {\rm A}_{1,1} & t_y{\rm A}_{1,2}\\ t_x{\rm A}_{2,1} & t_y{\rm A}_{2,1} & t_x^2{\rm A}_{2,2}+t_y^2{\rm A}_{2,2} \end{pmatrix}^{-1} \begin{pmatrix}X_1\\Y_1\\t_xX_2+t_yY_2\end{pmatrix}\tag{14} \end{eqnarray}

式 (14) を計算すれば、p_{1x},p_{1y},\alpha が求まるので、要件を満たす3次ベジェ曲線が定まります。

式 (14) の逆行列が存在しないまたは \alpha\leq 0 の場合

式 (14) の逆行列が存在しないときは、当然解は定まりませんし、
\alpha\leq 0 は \alpha > 0 の仮定に反します。
そのような場合の解決策として、\alpha=\dfrac{||{\bf p}_3-{\bf p}_0||}{3||{\bf t}||} とし、{\bf p}_1 のみ最適化するという方法があります。

目次へ戻る