takminの書きっぱなし備忘録 @はてなブログ

主にコンピュータビジョンなど技術について、たまに自分自身のことや思いついたことなど

主成分分析で直線フィッティングの導出

Tips コンピュータビジョン

先日こんなツイートをしました。

絵にするとこんな感じです。

f:id:takmin:20200917000054p:plain
直線フィッティング

それに対してありがたいことに、いくつか反応をいただきました。

主成分分析でできるという回答を複数からもらいました。

自分でも色々と試してみたところ、導出に成功しました。

というわけで、せっかくなので僕が試した方法をメモしておきます。

尚、今回このようなリプライもいただきましたが、まだこちらの内容は追えてません。

n個の点 (x_i,y_i)が与えられた時、これに最もフィットする２次元平面上の直線 ax+by+c=0を求めるものとします。 まずはn個の点 (x_i,y_i)の重心を求め、それが原点となるように各点を (x^\prime_i , y^\prime_i)へ移動します。


\begin{pmatrix}
x'_{i}\\
y'_i
\end{pmatrix}
=
\begin{pmatrix}
x_i\\
y_i
\end{pmatrix}
-
\begin{pmatrix}
\bar{x}\\
\bar{y}
\end{pmatrix}

ここで (\bar{x},\bar{y})は点群の重心です。


\begin{pmatrix}
\bar{x}\\
\bar{y}
\end{pmatrix}
=\frac{1}{n}\sum_{i}^{n}
\begin{pmatrix}
x_i\\
y_i
\end{pmatrix}

最初にこの重心移動した (x^\prime_i , y^\prime_i)の点群に対して最もフィットする直線 a'x+b'y+c' =0を求めることを考えます。

\sqrt{a'^{2}+b'^{2}} =1とすると、点 (x^\prime_i , y^\prime_i)とこの直線までの距離は、

\left| a^\prime x^\prime_i + b^\prime y^\prime_i + c^\prime \right|

で表せます。（どうしてかわからない人は自分で導出してみましょう。）

したがって、

 
\bf{A}=\begin{pmatrix}
a'\\
b'
\end{pmatrix}
,~~~
\bf{X}=\begin{pmatrix}
x'_1&y'_1\\
x'_2&y'_2\\
{\vdots}&{\vdots}\\
x'_n&y'_n
\end{pmatrix}

とした時、最もフィットする直線を求めるには、 f(\bf{A}, c') = \left( \bf{X} \bf{A} + c' \bf{1} \right) ^T \left( \bf{X} \bf{A} + c' \bf{1} \right) を最小化する \bf{A}を \bf{A}^T \bf{A} = 1 の条件の下で求めることになります。

尚、 \bf{1}は要素がすべて１の n\times 1ベクトルです。

さて、このようにある拘束条件のもとで最小化を行うような問題はラグランジュの未定乗数法を使って解くことができます。 つまり

F(\bf{A}, c', \lambda) = \left( \bf{X} \bf{A} + c' \bf{1} \right) ^T \left( \bf{X} \bf{A} + c' \bf{1} \right) - \lambda \left( \bf{A}^T \bf{A} - 1 \right)

と置き、 \frac{\partial F}{\partial \bf{A}} = \frac{\partial F}{\partial c'} = \frac{\partial F}{\partial \lambda} = 0 となる \bf{A}および c'を求めます。

まず \frac{\partial F}{\partial c'}=0は

c' = -\frac{1}{n}\bf{1}^T\bf{X}{A}

と求まります。 ここで \bf{X}は重心が原点のため、 \bf{1}^T\bf{X} = 0となるので、

c' = 0

となります。 次に \frac{\partial F}{\partial \bf{A}} = 0 は、計算すると、

\bf{X}^T\bf{X}\bf{A} = \lambda \bf{A}

となります。すなわち、 \bf{X}^T\bf{X}の固有ベクトルを求めれば \bf{A}が求まることになります。 ここで \bf{X}^T\bf{X}は共分散行列なので、共分散行列の固有値問題＝主成分分析を行っていることと同じであることがわかりました。

さて、ここで固有値が最も大きい固有ベクトル（第１主成分）が求める直線方向のベクトルとなるわけですが、 (a', b')はその直線の法線ベクトルなので、第１主成分と直行する第２主成分を \bf{A}とします。

最後にここで求まった (a', b', c')から (a, b, c)は以下のように求まります。

a = \frac{a'}{\sqrt{a'^{2} + b'^{2}}}

b = \frac{b'}{\sqrt{a'^{2} + b'^{2}}}

c = -a \bar{x} -b \bar{y}