機械学習基礎理論独習

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

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

点列に2次ベジェ曲線群をフィットさせる - mousemoveイベントなどで使用することを想定

はじめに

本アルゴリズムは、かなり前にネットで見つけた方法で、出所を忘れてしまいました。
単純なアルゴリズムですが、効果はあります。

要件

点列 \{{\bf x}_n\}_{n=1}^N\ ({\bf x}_n\in{\mathbb R}^m) にフィットする2次ベジェ曲線群を求めたいとします。
点列の数 N は3以上であるとします。

Canvas上(描画可能な領域)でマウスを動かして、それに追随して線を描画するようなときに使えるアルゴリズムです。
なんか、かなり限定的な局面と思われますが、要は点が多数(数百程度)あり、
点をそのまま線分で結ぶとカクカクした線分群になるのでそれを避けようというアルゴリズムです。

2次ベジェ曲線上の点を {\bf P}(t)\in{\mathbb R}^m\ (t\in[0,1]) とし、その制御点を {\bf P}_0,{\bf P}_1,{\bf P}_2\in{\mathbb R}^m おくと以下のようになります。

\begin{eqnarray} {\bf P}(t)=(1-t)^2{\bf P}_0+2(1-t)t{\bf P}_1+t^2{\bf P}_2\tag{1} \end{eqnarray}

このベジェ曲線を複数使って点列にフィットさせます。

アルゴリズム

点列から新たな点列 \{{\bf y}_n\}_{n=1}^{N-1}\ ({\bf y}_n\in{\mathbb R}^m) を作成します。

\begin{eqnarray} {\bf y}_n=\frac{{\bf x}_n+{\bf x}_{n+1}}{2}\tag{2} \end{eqnarray}

n 番目の2次ベジェ曲線を {\bf P}_n(t) とし、その制御点を {\bf P}_{n0},{\bf P}_{n1},{\bf P}_{n2}\in{\mathbb R}^m とします。
制御点を以下のように定めます。

\begin{eqnarray} \left\{ \begin{array}{l} {\bf P}_{n0}={\bf y}_n\\ {\bf P}_{n1}={\bf x}_{n+1}\\ {\bf P}_{n2}={\bf y}_{n+1} \end{array} \right.\tag{3} \end{eqnarray}

式 (1),(3) より、求めるべき {\bf P}_n(t) は以下のようになります。

\begin{eqnarray} {\bf P}_n(t)=(1-t)^2{\bf y}_n+2(1-t)t{\bf x}_{n+1}+t^2{\bf y}_{n+1}\tag{4} \end{eqnarray}

よって、求める2次ベジェ曲線群は \{{\bf P}_n(t)\}_{n=1}^{N-2} となります。

プログラムによる描画

後で画像をここに貼り付けます。

補足

求める2次ベジェ曲線群は点群の点を(基本的に)通らないことに注意してください。

目次へ戻る