RANSACとLMedSの実験

closeこれは 2 年 2 ヶ月 3 日 前に投稿されたものです。最新のものではありませんので、間違っているかも知れません。


外れ値を含んだデータでも使えるロバスト推定として知られる「RANSAC」および「LMedS」をやってみたくなった。そのため、この2つを使って、テキトーに用意した平面データから定数を推定してみる。

平面データの用意

以下の式、
$$z = \mathrm{A}x + \mathrm{B}y + \mathrm{C}$$
で表せる平面の定数、A、B、Cを推定するにあたり、以下の平面、
$$\begin{eqnarray}
z &=& \frac{\frac{1}{7}x + \frac{1}{13}y}{\frac{400}{7} + \frac{600}{13}} \times 255 \\
&=& 0.35265957446x + 0.18989361702y + 0
\end{eqnarray}$$
という式から作成したデータを用いた。

データ作成の際には、誤差が発生するよう、

  • zの値は小数点以下を切り捨てて整数とする
  • 1%~10%の範囲で、一様乱数で選択された点の値を0~255の(一様乱数による)ランダムな値にする

という処理を行う。これらをPythonスクリプトとして実装すると、こんな感じになる。

かなりまな板だよコレ!

なお、このデータをgnuplotで眺めると、こんな感じになる。planeちゃんとノイズが入っている。また、画像を拡大すると、階調が不連続に変化している(「トーンジャンプ」というらしい)ことも分かる。

RANSACとLMedSによる推定

平面の方程式の定数を、先ほど用意した平面データから「RANSAC(RANdom SAmple Consensus)」と「LMedS(Least Median of Squares)」によって、推定する。それぞれの解説やアルゴリズムは、下記ページを参照すれば良い。

おべんきょうwiki - ロバスト推定
http://www23.atwiki.jp/yahirohumpty/pages/5.html

OpenCVで遊ぼう!: RANSACを調べてみました
http://playwithopencv.blogspot.jp/2010/07/ransac.html

RANSAC法を利用してKinect深度データから平面除去 - 明日とロボット
http://d.hatena.ne.jp/astrobot/20110711/1310364448

画像認識のための統計学-分類,最適化,モデル化-
http://www.ime.info.hiroshima-cu.ac.jp/~hiura/lec/ime/03.pdf

最後の広島市立大学の講義資料(と思われる)によれば、LMedSは外れ値が全データに対して50%まで、RANSACでは50%以上でも動くらしい。また、大きな違いとして、「RANSACは誤差を測ってそれが許容できるか否かを調べる」、つまり「許容できる範囲」を人間が設定するのに対し、LMedSではそれが不要となる。ただ、「許容できる範囲なんて知らないからLMedSでやるやでー」として、無事平面が推定できたとしても、「平面を除去」したい場合は、結局「許容できる範囲」を設定する必要があるんじゃないんですかね。得られた最小化された「誤差の中央値」で良いのかな。どうだろう。

ひとまず、実装は以下となる。

最初は、普通のPythonを使っていたが、あまりに遅かったため、NumpyとCythonを使ってみた。速くて良い。
しかし、人に見せないものだと、手間をかけたくないとか思って、恐らくこんなことはやらないので、今回の記事を書いて良かった良かった。

CythonやらNumpyをインストールした上で、以下を実行すれば動く。

warningが出まくるのは、今後の課題としたい。

実行結果

同じ平面データで、5回実行してみた。こうなる。

数値の意味は、さっき示したソースコードから見てくれれば良いと思った。「得られた値」「真の値との差」「推定に掛かった時間(秒数)」ってだけなんですけど。

で、この結果によると、実行速度は、「RANSAC > LMedS」という感じですかね。
なお、RANSAC、LMedS共に、繰り返し数Nはテキトーに決めた N=1000 としていますが、全体の「1%~10%の外れ値(誤差)」だと、もっと少なくても良いかも知れません。実際、N=100 にして実行してみましたが、結果に大きな違い(実行時間除く)はないと思いましたまる。この辺りは、乱数の機嫌によっても変わるでしょうが…。

なお、その精度をRANSACとLMedSで比較するために、定数A、B、Cに分けてプロットしてみると、以下となった。
a
b
c
精度は、「LMedS > RANSAC」といったところでしょうか。定数Cのところは見なかったことにして。

ところで、その定数Cの誤差について、RANSAC、LMedS共にヒドイ。定数A、Bの誤差と比べて、桁が1、2桁…それ以上?違っている。zに及ぼす影響が小さいからでしょうが、真のCが0でなければ、また違う結果になったのですかね。

さいごに

久しぶりに記事を書きました。研究の参考になればと思って、RANSACとLMedSをやりました。Cythonが面白かったです。LaTeX…いや、$$\LaTeX$$ばっか書きまくっていたせいで、HTMLを忘れ、「箇条書き HTML」でググるのも面白かったです。

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>