機械学習基礎理論独習

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

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

3次ベジェ曲線のG1接続 - 接続点に隣接する制御点の移動量を最小にする - 別々に最適化

ベジェ曲線

要件

2つのベジェ曲線 P,Q があり、曲線 P の終点と曲線 Q の始点が等しいとします。
曲線 P の制御点は {\bf p}_0,{\bf p}_1,{\bf p}_2,{\bf p}_3 とし、位置ベクトルは {\bf p}(t)=(1-t)^3{\bf p}_0+3(1-t)^2t{\bf p}_1+3(1-t)t^2{\bf p}_2+t^3{\bf p}_3 とし、
曲線 Q の制御点は {\bf q}_0,{\bf q}_1,{\bf q}_2,{\bf q}_3 とし、位置ベクトルは {\bf q}(t)=(1-s)^3{\bf q}_0+3(1-s)^2s{\bf q}_1+3(1-s)s^2{\bf q}_2+s^3{\bf q}_3 とします。

曲線 P の終点と曲線 Q の始点が等しいので、以下が成り立ちます。

\begin{eqnarray} {\bf p}_3={\bf q}_0\tag{1} \end{eqnarray}

制御点間の長さ \alpha_p,\alpha_q を以下のように定義します。

\begin{eqnarray} &&\alpha_p=||{\bf p}_2-{\bf p}_3||\tag{2}\\ &&\alpha_q=||{\bf q}_1-{\bf q}_0||\tag{3} \end{eqnarray}

曲線 P,Q が {\bf p}_3={\bf q}_0 でG1連続である時、 {\bf p}_2-{\bf p}_3 に平行なベクトルを {\bf u} とおくと、

\begin{eqnarray} &&{\bf p}_2={\bf p}_3+\alpha_p{\bf u}\tag{4}\\ &&{\bf q}_1={\bf q}_0-\alpha_q{\bf u}\tag{5} \end{eqnarray}

が成り立ちます。

要件は「曲線 P,Q のG1連続維持(式 (4),(5) を満たす)しつつ、曲線 P,Q が {\bf p}_2,{\bf q}_1 の移動量を最小にするような {\bf u},\ \alpha_p,\ \alpha_q を見つけること」です。

{\bf u} と \alpha_p,\alpha_q を別々に最適化する

まずは {\bf u} を最適化します。

目的関数 {\rm E} を定義します。

\begin{eqnarray} {\rm E}&=& ||\Delta{\bf p}_2||^2+||\Delta{\bf q}_1||^2\\ &=&||{\bf p}_2-\hat{\bf p}_2||^2+||{\bf q}_1-\hat{\bf q}_1||^2\\ &=&||{\bf p}_2-\left({\bf p}_3+\alpha_p{\bf u}\right)||^2+||{\bf q}_1-\left({\bf q}_0-\alpha_q{\bf u}\right)||^2\\ &=&||{\bf p}_2-{\bf p}_3-\alpha_p{\bf u}||^2+||{\bf q}_1-{\bf q}_0+\alpha_q{\bf u}||^2\tag{6} \end{eqnarray}

{\rm E} を {\bf u} で微分して ={\bf 0} とおきます。

\begin{eqnarray} &&\dfrac{\partial{\rm E}}{\partial{\bf u}}={\bf 0}\\ &&\Rightarrow\dfrac{\partial}{\partial{\bf u}}||{\bf p}_2-{\bf p}_3-\alpha_p{\bf u}||^2+\dfrac{\partial}{\partial{\bf u}}||{\bf q}_1-{\bf q}_0+\alpha_q{\bf u}||^2\\ &&\Rightarrow2({\bf p}_2-{\bf p}_3-\alpha_p{\bf u})\cdot(-\alpha_p)+2({\bf q}_1-{\bf q}_0+\alpha_q{\bf u})\cdot\alpha_q={\bf 0}\\ &&\Rightarrow-\alpha_p{\bf p}_2+\alpha_p{\bf p}_3+\alpha_p^2{\bf u}+\alpha_q{\bf q}_1-\alpha_q{\bf q}_0+\alpha_q^2{\bf u}={\bf 0}\\ &&\Rightarrow\left(\alpha_p^2+\alpha_q^2\right){\bf u}=\alpha_p\left({\bf p}_2-{\bf p}_3\right)+\alpha_q\left({\bf q}_0-{\bf q}_1\right)\\ &&\Rightarrow{\bf u}=\dfrac{\alpha_p}{\alpha_p^2+\alpha_q^2}\left({\bf p}_2-{\bf p}_3\right)+\dfrac{\alpha_q}{\alpha_p^2+\alpha_q^2}\left({\bf q}_0-{\bf q}_1\right)\tag{7} \end{eqnarray}

次に \alpha_p を最適化します。

目的関数 {\rm E}_p を定義します。

\begin{eqnarray} {\rm E}_p&=& ||\Delta{\bf p}_2||^2\\ &=&||{\bf p}_2-\hat{\bf p}_2||^2\\ &=&||{\bf p}_2-\left({\bf p}_3+\alpha_p{\bf u}\right)||^2\\ &=&||{\bf p}_2-{\bf p}_3-\alpha_p{\bf u}||^2\tag{8} \end{eqnarray}

{\rm E}_p を \alpha_p で微分して =0 とおきます。

\begin{eqnarray} &&\dfrac{\partial{\rm E}_p}{\partial\alpha_p}=0\\ &&\Rightarrow\dfrac{\partial}{\partial\alpha_p}||{\bf p}_2-{\bf p}_3-\alpha_p{\bf u}||^2=0\\ &&\Rightarrow2({\bf p}_2-{\bf p}_3-\alpha_p{\bf u})^\top(-{\bf u})=0\\ &&\Rightarrow-{\bf p}_2^\top{\bf u}+{\bf p}_3^\top{\bf u}+\alpha_p||{\bf u}||^2=0\\ &&\Rightarrow\alpha_p||{\bf u}||^2={\bf p}_2^\top{\bf u}-{\bf p}_3^\top{\bf u}\\ &&\Rightarrow\alpha_p=\dfrac{{\bf p}_2^\top{\bf u}-{\bf p}_3^\top{\bf u}}{||{\bf u}||^2}\tag{9} \end{eqnarray}

最後に \alpha_q を最適化します。

目的関数 {\rm E}_q を定義します。

\begin{eqnarray} {\rm E}_q&=& ||\Delta{\bf q}_1||^2\\ &=&||{\bf q}_1-\hat{\bf q}_1||^2\\ &=&||{\bf q}_1-\left({\bf q}_0-\alpha_q{\bf u}\right)||^2\\ &=&||{\bf q}_1-{\bf q}_0+\alpha_q{\bf u}||^2\tag{10} \end{eqnarray}

{\rm E}_q を \alpha_q で微分して =0 とおきます。

\begin{eqnarray} &&\dfrac{\partial{\rm E}_q}{\partial\alpha_q}=0\\ &&\Rightarrow\dfrac{\partial}{\partial\alpha_q}||{\bf q}_1-{\bf q}_0+\alpha_q{\bf u}||^2=0\\ &&\Rightarrow2({\bf q}_1-{\bf q}_0+\alpha_q{\bf u})^\top{\bf u}=0\\ &&\Rightarrow{\bf q}_1^\top{\bf u}-{\bf q}_0^\top{\bf u}-\alpha_q||{\bf u}||^2=0\\ &&\Rightarrow\alpha_q||{\bf u}||^2={\bf q}_0^\top{\bf u}-{\bf q}_1^\top{\bf u}\\ &&\Rightarrow\alpha_q=\dfrac{{\bf q}_0^\top{\bf u}-{\bf q}_1^\top{\bf u}}{||{\bf u}||^2}\tag{11} \end{eqnarray}

{\bf u} と \alpha_p,\alpha_q を別々に最適化する場合、要件を満たしていませんが、制御点があまり動かないのでとりあえずG1連続にしたいときにおすすめのアルゴリズムです。

{\bf u} と \alpha_p,\alpha_q を同時に最適化する

以下は書き直す可能性が大いにあります。読まないでください。
ニュートン法で最適化します。

パラメータをまとめて {\boldsymbol\theta} とおきます。

\begin{eqnarray} {\boldsymbol\theta} = \begin{pmatrix} u_x\\ u_y\\ \alpha_p\\ \alpha_q \end{pmatrix}\tag{12} \end{eqnarray}

まずは勾配ベクトルを成分を計算します。

式 (7) より以下が成り立ちます。

\begin{eqnarray} &&\dfrac{\partial{\rm E}}{\partial u_x}=2\left(\left(\alpha_p^2+\alpha_q^2\right)u_x-\alpha_p\left(p_{2x}-p_{3x}\right)-\alpha_q\left(q_{0x}-q_{1x}\right)\right)\tag{13}\\ &&\dfrac{\partial{\rm E}}{\partial u_y}=2\left(\left(\alpha_p^2+\alpha_q^2\right)u_y-\alpha_p\left(p_{2y}-p_{3y}\right)-\alpha_q\left(q_{0y}-q_{1y}\right)\right)\tag{14} \end{eqnarray}

式 (10),(11) より以下が成り立ちます。

\begin{eqnarray} &&\dfrac{\partial{\rm E}_p}{\partial\alpha_p}=2\left(\alpha_p||{\bf u}||^2-{\bf p}_2^\top{\bf u}+{\bf p}_3^\top{\bf u}\right)\tag{15}\\ &&\dfrac{\partial{\rm E}_q}{\partial\alpha_q}=2\left(\alpha_q||{\bf u}||^2-{\bf q}_0^\top{\bf u}+{\bf q}_1^\top{\bf u}\right)\tag{16} \end{eqnarray}

以上より、勾配ベクトルは以下のようになります。

\begin{eqnarray} \dfrac{\partial{\rm E}}{\partial{\boldsymbol\theta}} &=& \begin{pmatrix} \dfrac{\partial{\rm E}}{\partial u_x}\\ \dfrac{\partial{\rm E}}{\partial u_y}\\ \dfrac{\partial{\rm E}}{\partial\alpha_p}\\ \dfrac{\partial{\rm E}}{\partial\alpha_q} \end{pmatrix} = \begin{pmatrix} \dfrac{\partial{\rm E}}{\partial u_x}\\ \dfrac{\partial{\rm E}}{\partial u_y}\\ \dfrac{\partial{\rm E}_p}{\partial\alpha_p}\\ \dfrac{\partial{\rm E}_q}{\partial\alpha_q} \end{pmatrix}\\ &=& \begin{pmatrix} 2\left(\left(\alpha_p^2+\alpha_q^2\right)u_x-\alpha_p\left(p_{2x}-p_{3x}\right)-\alpha_q\left(q_{0x}-q_{1x}\right)\right)\\ 2\left(\left(\alpha_p^2+\alpha_q^2\right)u_y-\alpha_p\left(p_{2y}-p_{3y}\right)-\alpha_q\left(q_{0y}-q_{1y}\right)\right)\\ 2\left(\alpha_p||{\bf u}||^2-{\bf p}_2^\top{\bf u}+{\bf p}_3^\top{\bf u}\right)\\ 2\left(\alpha_q||{\bf u}||^2-{\bf q}_0^\top{\bf u}+{\bf q}_1^\top{\bf u}\right) \end{pmatrix}\tag{17} \end{eqnarray}

次にヘッセ行列を計算します。

先に要素を計算します。

\begin{eqnarray} &&\dfrac{\partial^2{\rm E}}{\partial u_x^2}=2\left(\alpha_p^2+\alpha_q^2\right)\tag{18}\\ &&\dfrac{\partial^2{\rm E}}{\partial u_y^2}=2\left(\alpha_p^2+\alpha_q^2\right)\tag{19}\\ &&\dfrac{\partial^2{\rm E}}{\partial u_y\partial u_x}=0\tag{20}\\ &&\dfrac{\partial^2{\rm E}}{\partial \alpha_p^2}=2||{\bf u}||^2\tag{21}\\ &&\dfrac{\partial^2{\rm E}}{\partial \alpha_q^2}=2||{\bf u}||^2\tag{22}\\ &&\dfrac{\partial^2{\rm E}}{\partial \alpha_p\partial \alpha_q}=0\tag{23}\\ &&\dfrac{\partial^2{\rm E}}{\partial \alpha_p\partial u_x}=2\left(2\alpha_p u_x-p_{2x}+p_{3x}\right)\tag{24}\\ &&\dfrac{\partial^2{\rm E}}{\partial \alpha_p\partial u_y}=2\left(2\alpha_p u_y-p_{2y}+p_{3y}\right)\tag{25}\\ &&\dfrac{\partial^2{\rm E}}{\partial \alpha_q\partial u_x}=2\left(2\alpha_q u_x-q_{0x}+q_{1x}\right)\tag{26}\\ &&\dfrac{\partial^2{\rm E}}{\partial \alpha_q\partial u_y}=2\left(2\alpha_q u_y-q_{0y}+q_{1y}\right)\tag{27}\\ \end{eqnarray}

以上より、ヘッセ行列は以下のようになります。

\begin{eqnarray} \dfrac{\partial^2{\rm E}}{\partial{\boldsymbol\theta}\partial{\boldsymbol\theta}^\top}&=& \begin{pmatrix} \dfrac{\partial^2{\rm E}}{\partial u_x^2} & \dfrac{\partial^2{\rm E}}{\partial u_x\partial u_y} & \dfrac{\partial^2{\rm E}}{\partial u_x\partial \alpha_p} & \dfrac{\partial^2{\rm E}}{\partial u_x\partial \alpha_q}\\ \dfrac{\partial^2{\rm E}}{\partial u_y\partial u_x} & \dfrac{\partial^2{\rm E}}{\partial u_y^2} & \dfrac{\partial^2{\rm E}}{\partial u_y\partial \alpha_p} & \dfrac{\partial^2{\rm E}}{\partial u_y\partial \alpha_q}\\ \dfrac{\partial^2{\rm E}}{\partial \alpha_p\partial u_x} & \dfrac{\partial^2{\rm E}}{\partial \alpha_p\partial u_y} & \dfrac{\partial^2{\rm E}}{\partial \alpha_p^2} & \dfrac{\partial^2{\rm E}}{\partial \alpha_p\partial \alpha_q}\\ \dfrac{\partial^2{\rm E}}{\partial \alpha_q\partial u_x} & \dfrac{\partial^2{\rm E}}{\partial \alpha_q\partial u_y} & \dfrac{\partial^2{\rm E}}{\partial \alpha_q\partial \alpha_p} & \dfrac{\partial^2{\rm E}}{\partial \alpha_q^2} \end{pmatrix}\\ &=& \begin{pmatrix} 2\left(\alpha_p^2+\alpha_q^2\right) & 0 & 2\left(2\alpha_p u_x-p_{2x}+p_{3x}\right) & 2\left(2\alpha_q u_x-q_{0x}+q_{1x}\right)\\ 0 & 2\left(\alpha_p^2+\alpha_q^2\right) & 2\left(2\alpha_p u_y-p_{2y}+p_{3y}\right) & 2\left(2\alpha_q u_y-q_{0y}+q_{1y}\right)\\ 2\left(2\alpha_p u_x-p_{2x}+p_{3x}\right) & 2\left(2\alpha_p u_y-p_{2y}+p_{3y}\right) & 2||{\bf u}||^2 & 0\\ 2\left(2\alpha_q u_x-q_{0x}+q_{1x}\right) & 2\left(2\alpha_q u_y-q_{0y}+q_{1y}\right) & 0 & 2||{\bf u}||^2 \end{pmatrix} \tag{28} \end{eqnarray}

ニュートン法による更新式

ニュートン法による更新式は、以下のようになります。

\begin{eqnarray} {\boldsymbol\theta}&\leftarrow&{\boldsymbol\theta}-\left(\dfrac{\partial^2{\rm E}}{\partial{\boldsymbol\theta}\partial{\boldsymbol\theta}^\top}\right)^{-1}\dfrac{\partial{\rm E}}{\partial{\boldsymbol\theta}}\tag{29} \end{eqnarray}

目的関数が2次式なので更新回数は1回でよいです。

目次へ戻る