F行列推定のためのSVDに関するノート
用途：F行列推定（=8点アルゴリズム）で8点以上の点から最適解を解析的に計算するのに使用
概要：SVDは固有値解析と同様，ある行列を，対角行列のような疎行列に両側から正規直行行列を掛けた形式に分解する．
$$ A = U\Sigma V^\mathsf{T} $$
行列のサイズを表記すると，
$$ A_{m\times n} = U_{m\times m} \Sigma_{m\times n}V^\mathsf{T}_{n\times n}$$
これが何故F行列の推定に使えるかというと，与えられた行列$A$に対し，
$$ A\mathbf{f}$$
のノルムを最小にする，(ノルムが0でない)ベクトル$\mathbf{f}$を計算することが可能であるからである．
F行列の推定
F行列の推定では，様々なベクトル対$\mathbf{b_1^n}$と$\mathbf{b_2^n}$（＝特徴点対応）に対し，
$$\mathbf{b_1^n}^\mathsf{T}F\mathbf{b_2^n} = 0$$
となるFを計算する．
ベクトル対が8つの場合，この等式が成立するFが存在するが，特徴点対応が誤差を含んでいることから，9個以上の正しいと判断された対応からFを推定する方が良い．
そのため，全てのnについて$e^n=\mathbf{b_1^n}^\mathsf{T}F\mathbf{b_2^n}$の2乗和が小さいような$F$を導出したい．
ここで，行列の表記を変える．
\mathbf{b_1}=
\left[
\begin{matrix}
b_{11}\\
b_{12}\\
b_{13}
\end{matrix}
\right]
,
\mathbf{b_2} =
\left[
\begin{matrix}
b_{21}\\
b_{22}\\
b_{23}
\end{matrix}
\right]
,
F=
\left[
\begin{matrix}
f11 & f12 & f13 \\
f21 & f22 & f23 \\
f31 & f32 & f33
\end{matrix}
\right]
とすると，
e = b_{11}b_{21}f_{11} + b_{11}b_{22}f_{12} + b_{11}b_{23}f_{13} + b_{12}b_{21}f_{21} + b_{12}b_{22}f_{22} + b_{12}b_{23}f_{23} + b_{13}b_{21}f_{31} + b_{13}b_{22}f_{32} + b_{13}b_{23}f_{33}\\
= [b_{11}b_{21} + b_{11}b_{22} + b_{11}b_{23} + b_{12}b_{21} + b_{12}b_{22} + b_{12}b_{23} + b_{13}b_{21} + b_{13}b_{22} + b_{13}b_{23}]
\left[
\begin{matrix}
f_{11}\\
f_{12}\\
f_{13}\\
f_{21}\\
f_{22}\\
f_{23}\\
f_{31}\\
f_{32}\\
f_{33}
\end{matrix}
\right]
よって，ベクトル対がN個あった場合，
\left[
\begin{matrix}
e^1 \\
e^2 \\
\vdots \\
e^N
\end{matrix}
\right]
=
\left[
\begin{matrix}
b_{11}^1b_{21}^1 + b_{11}^1b_{22}^1 + b_{11}^1b_{23}^1 + b_{12}^1b_{21}^1 + b_{12}^1b_{22}^1 + b_{12}^1b_{23}^1 + b_{13}^1b_{21}^1 + b_{13}^1b_{22}^1 + b_{13}^1b_{23}^1\\
b_{11}^2b_{21}^2 + b_{11}^2b_{22}^2 + b_{11}^2b_{23}^2 + b_{12}^2b_{21}^2 + b_{12}^2b_{22}^2 + b_{12}^2b_{23}^2 + b_{13}^2b_{21}^2 + b_{13}^2b_{22}^2 + b_{13}^2b_{23}^2\\
\vdots\\
b_{11}^Nb_{21}^N + b_{11}^Nb_{22}^N + b_{11}^Nb_{23}^N + b_{12}^Nb_{21}^N + b_{12}^Nb_{22}^N + b_{12}^Nb_{23}^N + b_{13}^Nb_{21}^N + b_{13}^Nb_{22}^N + b_{13}^Nb_{23}^N
\end{matrix}
\right]
\left[
\begin{matrix}
f_{11}\\
f_{12}\\
f_{13}\\
f_{21}\\
f_{22}\\
f_{23}\\
f_{31}\\
f_{32}\\
f_{33}
\end{matrix}
\right]
左辺を$\boldsymbol{e}$, 右辺の$b$の行列を$A$, $f$の行列を$\boldsymbol{f}$とすると
$$
\boldsymbol{e} = A\boldsymbol{f}
$$
ここで，推定したいF行列は，$argmin_\boldsymbol{f} ||\boldsymbol{e}||（||\boldsymbol{f}||=1)$と表記できる．
これを計算するためにSVDを用いる．
SVDによって $A$は
$$A_{N\times 9} = U_{N\times N}\Sigma_{N\times 9} V^\mathsf{T}_{9\times 9}$$
と分解される．
$V$を移項して
$$ A V = U \Sigma$$
ここで$\Sigma$の特異値が降順であるとすると，$i$個目の特異値は$\sigma_i$である．
$V$の第$i$列$\boldsymbol{v_i}$と$U$の第$i$列$\boldsymbol{u_i}$より，
A\boldsymbol{v}_ i = \sigma_i \boldsymbol{u}_i
両辺のノルムをとって
||A\boldsymbol{v}_ i|| = ||\sigma_i \boldsymbol{u}_i|| = \sigma_i
9番目の特異値$\sigma_9$が最小のため，$i$=9としたとき$||A\boldsymbol{v}_ i||$が最小となる．
よって，$V$の9番目の列ベクトル$\boldsymbol{v}_9$を並び替えた$3\times 3$行列が求めたいF行列である．