RANSACを調べてみました

パラメータのロバスト推定によく使用されているというRANSAC。
コンピュータビジョンの本にもところどころ出てきていますが、
どんなものなのかははっきりわかっていませんでした。

というわけで、色々と調査してみました。

Czech Technica大学の教材のPDFやおべんきょうWikiを見て調べたところ、

RANSACのアルゴリズムは、下記のようになっていました。

１．総データ個数がU個あるデータから、ランダムでn個のデータを取り出します。
２．取り出したn個のデータから、パラメータを求めます。
　（取り出すデータの個数ですが、これは求めるべきパラメータの数に比例するようです)
３．求めたパラメータを、総データ点数から取り出したn個のデータを除いたものに式を当てはめ、
観測されたデータと２．で求めたパラメータの誤差を計算します。
４．誤差が許容範囲内であれば、パラメータに対して投票を行います。
５．１～４を繰り返し、投票数が一番多かったパラメータをひとまず採用します。
（これを仮パラメータとします）

６．仮パラメータを使ってすべてのデータに再度式を適用し、誤差が許容範囲内のものを抽出します。（この時点で雑音データがほぼ取り除かれます）

７．抽出したデータを元に、再度パラメータを求めます。
８．求まったパラメータがこのデータのもっともらしいパラメータとなります。



というわけで、Excelを使って実験をしてみました。
実験の条件は下記の通りです。

実験データ個数：６００個
うち３００個は正解データ、残りの３００個は雑音データとしました。
正解データの数式は　 Y=(1-rand()/10) *X　で生成しており、
正解データはYの0.9倍から1倍の範囲にあり、平均すると0.95倍になる、、はずです。
雑音データの数式はY=rand()*X　としました。Xが0から300まであるので、最小値０、最大値３００の雑音データがランダムで発生しています。

パラメータ推定の対象となるデータをグラフにしたものが以下のものとなります。

上記のデータに、RANSACで式を当てはめてみます。
今回は原点を通る直線の式になるので、式は
　Y=AX
と簡単なものになります。
未知のパラメータが１個なので、ランダムで取り出すサンプルの個数は２個としました。


取り出した点PとQのX,Yの値を(Px,Py)、(Qx,Qy)とします。
A＝傾き＝Yの増加量/Xの増加量=(Qy-Py)/(Qx-Px) で、仮のAが求まります。
そして、仮のAをサンプル以外のデータに適用し、誤差を調べます。

今回は誤差が10%以下のものに限り投票してよいことにしました。



上記のことを600回(回数は適当に決めました)行い、得票数が一番多かったパラメータ（今回はA=0.91が得票数が一番多くなりました）を使って、誤差が範囲内にあるデータの集合を求めます。
誤差が範囲内にあるデータの集合は、雑音がほぼ取り除かれたデータとなるので、
このデータの集合を元に、再度パラメータを推定します。
今回は各データのY/Xを計算して、平均をとったところ、A=0.95となりました。
下の図のピンクがRANSACで求めたパラメータの直線です。

おぉ～

見事に雑音が無視されていますね。

あとはこれをCで書けば、今後のパラメータ推定に役立ちそうです。

ではまた。