#はじめに

ベジェ曲線を描画する実装をしていて、何か機械学習を使えるアイディアないかなーと考えていると以下の記事を見つけたのがやろうと思ったきっかけです。

Pythonで最小二乗法を使って指定の点を通るベジェ曲線を近似する

やったことはこの記事とほぼ同じ＆お手軽版ですが、実装してみて勉強になったのでまとめて投稿してみました。

#開発環境

以下の開発環境で動作させました。
pythonがインストールされててSklearnが使えれば動くと思います。

PC
- OS : Windows 10 Home
- CPU : Intel Core i5 -8250U 1.6GHz
- Memory : 8GB
Software
- Python 3.6.8
- Sklearn 0.21.1

やること

下図のようにノイズが乗ったベジェ曲線の構成点（赤点）から、制御点座標を予測してベジェ曲線（青線）を描いてみます。

対象は3次のベジェ曲線で、2点目、3点目の制御点を予測します。
始終点はデータを与える時点で自明なのと、簡単な問題にするためです。

どうやって予測する？

線形回帰モデルを使って制御点の予測を行います。
まずは線形回帰モデルのアルゴリズムを簡単に解説します。

線形回帰について

機械学習や統計学で広く用いられている連続値の予測モデルです。
まず、$M$次元の実数値入力$x\in{R}$から実数値出力（ラベル）$y\in{R}$を結びつける以下の関数を考えます。

y = wx + ε = \sum_{m=1}^{M}w_{m}x_{m} + ε  \tag{1}

これに対してデータセット$D=\{X, Y\}$が与えられたとします。
$X$は$N$個の入力集合$X=\{x_{1}, ..., x_{N}\}$
$Y$は$N$個のラベル集合$Y=\{y_{1}, ..., y_{N}\}$
$ε$はバイアス項で、ランダムな値です。
このデータセット$D$に対して最も当てはまりの良い関数となるように$W$の値を調整します。
調整後の$W$を用いて、未知の入力値$x$を$(1)$に入力して結果を予測します。
そして、$W$の値を調整するには最小二乗法を使います。

最小二乗法

関数の”当てはまりの良さ”を”予測値と各ラベルの二乗誤差の合計が小さいこと”として考えます。
この問題は$N$個のデータセット$D=\{X, Y \}$に対して以下のような誤差関数で表します。

E(w) = \frac{1}{2}\sum^{N}_{n=1}\{y_{n} - wx_{n}\} ^{2}　\tag{2}

誤差関数を$w$に関して最小化する問題になります。
これは以下の図のように期待する関数（青線）と予測結果値（赤点）の差（緑線）の総和を最小化するイメージです。

最適解を$w_{LS}$と置くとこの問題は以下のように書けます。

w_{LS} = argmax_{w} E(w) \tag{3}

このようなパラメータの学習方法を最小二乗法と言います。

二乗誤差から求める誤差関数$E(w)$は$w$についての二次関数としてみることができ、$w$についての勾配が0となる値が最適解$w_{LS}$となります。
まず誤差関数の勾配$\frac{ \partial E(w)}{\partial w}$は以下の通り計算されます。

\frac{\partial E(w)}{\partial w} = - \sum^{N}_{n=1}y_{n}x_{n} + \sum^{N}_{n=1}x_{n}^2 w \tag{4}

$\frac{ \partial E(w)}{\partial w} = 0$とするとパラメータ$w_{LS}$は以下のように計算できます。

w_{LS} =  \big\{\sum^{N}_{n=1}x_{n}^2  \bigr\}^{-1}\sum^{N}_{n=1}y_{n}x_{n} \tag{5}

予測する

$(5)$で学習用データセット$D$に対して最適解$w_{LS}が計算出来たら、これを$(1)$に適応して新規の入力値xに対する予測値yを出力します。

y_{*} = w_{LS}x_{*}    \tag{6}

この線形回帰を使って制御点を予測して、その制御点からベジェ曲線を描いてみます。
実装するときはsklearnを使って上記のような数式はライブラリにお任せしてます（手抜き）。

実装

制御点の予測は以下の流れで実装しました。
0. ベジェ曲線用クラスの用意

学習用データ作成
線形回帰で学習
制御点予測

今回の学習用データはノイズが乗ったベジェ曲線を構成する点(100点)で、ラベルデータは制御点座標となります。
そのデータセットで学習を行い、新たなデータに対しても制御点座標を予測してベジェ曲線を描いていきます。

ベジェ曲線データ作成クラス

こちらの記事で書いたのですが、ベジェ曲線は制御点座標が与えられると曲線の軌跡上の座標が計算できます。
処理がバラバラだと実装がしにくいので、制御点データと計算処理メソッドを持つBezierCurveクラスを作っておきます。
内容はこちらのソースコードを参照ください。

BezierCurveクラス

学習用データ作成

まずは学習用データを作っていきます。
手順は以下の通りです。

制御点は基準となる座標4点を適当に定義する
2点目、3点目の値を少しづつ変化させてベジェ曲線100本分の制御点群を作成します。
作成した制御点群からベジェ曲線上の点群を作成
ベジェ曲線上の点群にノイズを足して学習用データとする

np.random.seed(0)
ct_noize_x = np.random.uniform(-2, 1, 10000)
ct_noize_y = np.random.uniform(-2, 1, 10000)

# 制御点を変えながらベジェ曲線を構成する点群を作成（100線分）
sampling_points = []
control_points = []
sample_curve_num = 100 # 学習用データ数
for i in range(sample_curve_num):
    # 基準の制御点を用意
    points = np.array([[0,0], [2,3], [3, 3], [4, 2]], dtype=np.float32)
    idx = i * 2
    # ちょっとずつずらして制御点データ作成
    points[1][0] += ct_noize_x[idx]
    points[1][1] += ct_noize_y[idx]
    points[2][0] += ct_noize_x[idx+1]
    points[2][1] += ct_noize_y[idx+1]
    # ベジェ曲線上の点群作成
    bezier_curve = BezierCurve(points)
    bezier_points = BezierPoints(bezier_curve)
    # 点群にノイズを足して学習用データ作成
    noized_points = AddNoize(bezier_points)

    control_points.append(points)
    sampling_points.append(noized_points)

確認のため、作成した100本分のベジェ曲線のを描画するとこんな感じです。
これにノイズを乗せて学習用データを作っています。

線形回帰で学習

何を説明変数、目的変数にするか悩んだのですが、今回は以下のようにします。

説明変数：ノイズを乗せたベジェ曲線の構成点のX、Y座標
目的変数：2点目、3点目の制御点それぞれのX、Y座標

説明変数用データと目的変数用データをまとめて線形回帰モデルを作成します。
これはsklearn.linear_model.LinearRegressionを使います。
学習処理はfit()を呼び出せば完了です。楽チン

from sklearn.linear_model import LinearRegression

# control point x1
model_LR_cx1 = LinearRegression()
model_LR_cx1.fit(n1x_train, ct1x_train)

# control point x2
model_LR_cx2 = LinearRegression()
model_LR_cx2.fit(n2x_train, ct2x_train)

# control point y1
model_LR_cy1 = LinearRegression()
model_LR_cy1.fit(n1y_train, ct1y_train)

# control point y2
model_LR_cy2 = LinearRegression()
model_LR_cy2.fit(n2y_train, ct2y_train)

決定係数を確認してみます。

print('control_point_x1 : ', model_LR_cx1.score(n1x_test, ct1x_test))
print('control_point_y1 : ', model_LR_cy1.score(n1y_test, ct1y_test))
print('control_point_x2 : ', model_LR_cx2.score(n2x_test, ct2x_test))
print('control_point_y2 : ', model_LR_cy2.score(n2y_test, ct2y_test))

>>>出力結果
control_point_x1 :  0.9999999999999976
control_point_y1 :  0.9999999999999941
control_point_x2 :  0.9999999999999885
control_point_y2 :  0.9999999999999943

なんかよさそう！

制御点予測

ついに制御点を予測してベジェ曲線を描画してみます。

適当に2点目、3点目座標を変化させて制御点座標を作って点群データを作成します。
そして、データにノイズを乗せて予測用のデータを作成します。

# 始点[0, 0]、終点[4, 2]、間の制御点位置を適当に設定してベジェ曲線を描く
test_control_point = np.array([[0,0], [0.1,5], [2, -3], [4, 2]], dtype=np.float32)

# 予測対象のベジェ曲線とノイズ付きの点群を作成
bezier_curve = BezierCurve(test_control_point)
bezier_points = BezierPoints(bezier_curve)
bezier_points_noize = BezierPoints(bezier_curve)
noized_points = AddNoize(bezier_points_noize)

入力用のデータ（赤点）を描画して確認してみます。

作成した予測用データから制御点を予測してベジェ曲線を描画します。
予測したベジェ曲線は赤線で描くので、できるだけ予測対象の曲線（青線）と重なれば良い結果です。

# 制御点予測
ctx1 = model_LR_cx1.predict(test_x)
cty1 = model_LR_cy1.predict(test_y)
ctx2 = model_LR_cx2.predict(test_x)
cty2 = model_LR_cy2.predict(test_y)

# 予測した制御点
predict_control_points = np.array([test_control_point[0], [ctx1, cty1], [ctx2, cty2], test_control_point[3]])

# 予測した制御点でベジェ曲線描画用データ作成
predict_bezier_curve = BezierCurve(predict_control_points)
predict_bezier_points = BezierPoints(predict_bezier_curve)

ベジェ曲線描画結果は以下の通りです。
赤線と青線はほぼ重なってます！！

おわりに

今回は思ったよりいい感じになってうれしい結果でした。
予測対象を制御点4つ、3次ベジェ曲線のみにしたこと、始終点を固定して2点目、3点目だけを対象にしたことなど、問題を極力単純にしたのが良かったのかなと思います。
予測対象のデータの始終点座標を変化させると予測結果は悪くなりますが、まだまだ工夫や改善の余地があるということですね。

ソースコード

ソースコードはGithubにうｐしてます。
ソースや実行結果の詳細はこちらを確認ください。
https://github.com/Ruketa/Geometry

参考文献