重みつき因子分解法 - スズメレンダラー・クマ将棋の開発日記

因子分解法はF枚の２次元画像から得られるP個の点情報を並べた、 $2F \times P$ の観測行列 $W$ を
復元すべき３次元のP個の点情報を横に並べた $3 \times P$ の行列 $S$ と、
カメラ行列 $C$ と射影行列 $A$ の積 $M=AC$ の、積に分解する方法です。
つまり、 $W=MS$ 　（重心はゼロとしてます）
のように分解できれば、３次元の座標とカメラの向きが分かります。
実際には、観測ノイズや射影モデル誤差などの影響で、左辺と右辺がちょうどイコールになることは
ありませんので、なんらかの誤差基準に従って推定することになります。

観測行列 $W$ を分解する方法として特異値分解を使うことができます。
特異値分解は二乗誤差を最小にしつつ、分解することができるため、
よく用いられるようです。 $\min_{M,S}\||W-MS\||^2$ となるものを一撃で計算できます。
実際には、カメラ行列が直交行列になるように制約加えて求めます。

上の場合では、全てのフレームで全ての点が観測されて対応付けられている、という前提ですが
実際の携帯カメラとかで撮影した場合、画質が悪くてあるフレームでは対応がとれなかったり、
自己遮蔽で観測点が隠れたり、見えなくなったりするため、この問題をなんとかしないといけません。
そこで、各観測点ごとに重みをつけて最小二乗法を行う特異値分解をすればできそうだ、
観測できなかった点の重みをゼロにしたり、信頼できそうな特徴点の重みを大ききすれば、なにか良さそうだ、
ということで、文献を調べたらすぐ見つかりました。

[1] Conrad J. Poelman and Takeo Kanade, "A Paraperspective Factorization Method　for Shape and Motion Recovery", 1993

です。タイトルは、Paraperspective射影モデルの話ですが、後半に重み付因子分解法の説明があります。
因子分解法が発案された直後です。重み付最小二乗法なんで、逆行列に重み行列をかければいいと思っていましたが、そんなに簡単な話ではないようです。式的には、
$\min_{M,S}\||(W-MS)\odot K\||^2$ となる $M,S$ を求めればいいのですが( $\odot$ は行列の要素ごとの掛け算、 $K$ は重み行列)、
この最小化問題はベクトルではなくて行列のノルムに関するもので、非線形（!?）最小化問題となるらしいです。
解法として、適当に初期値をあたえた $S$ を固定して $M$ を計算し、今度は $M$ を固定して $S$ を再計算するという
反復計算で求めます。
実際に計算してみたところランダムに初期値を与えても、数回の計算でちゃんと収束しました。すごい。
論文では、重みによっては不安定だ収束が遅いとありましたが、今のところ計算が失敗したりしてません。