*RANSAC とは 　RANSACは，ロバスト推定のアルゴリズムの１つです．ロバスト推定とは与えられた観測値に外れ値が含まれている可能性を考え，その影響を抑えることを目的とした方法です． 　RANSACの基本的な原理については，[link:ロバスト推定 (robust estimation)]を参照してください．本解説は，そこで説明した知識を前提にしています． 　RANSACについて詳しく知りたい場合，[1]の文献が参考になります．標準的なRANSACの方法に加え，その改良方式も含めて体系的な方法論が紹介されています． {{small:[1]R.Raguram, O.Chum, M.Pollefeys, J.Matas, and J.Frahm, "Usac: A universal framework for random sample consensus", IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI), 2013}} {{small:[link:http://people.inf.ethz.ch/pomarc/pubs/RaguramPAMI13.pdf] }} *RANSACの改良 　文献[1]では，RANSACを改良するための様々なアイデアがまとめられています．ここでは，その中の一部を紹介したいと思います． 　まず，図１を見てください．図１はRANSACのフローを表します．このフローは，これから説明する方法がどの部分の改良に当たるのかを見るときに参考になると思います． [img:gshk] {{small:図１ RANSACのフロー 出典[1]}} **試行回数の適正化 　RANSACは，ランダムサンプリングを繰り返し，それにより”あたり”（外れ値を含まないデータ群）を引き当てる方法です．この繰り返しの回数{$k$}は”あたり”を引き当てるのに十分な数を設定する必要があります．ただし，多すぎると無駄に処理時間が掛かってしまいます．ここでは，その適正値の設定方法を説明します． 　考え方としては，ある数値{$\eta_0$}以上の確率で”あたり”を引けるような{$k$}を設定したいとします．まず，母集団の全データに含まれるインライア (inlier 外れ値ではないデータ)の割合を{$\epsilon$}とすると，試行回数{$k$}までに少なくとも１回は”あたり”を引く確率{$\eta$}は次の式で表すことができます． {$$\eta = 1 - (1 - \epsilon^m)^k$$} 　ここで，{$\epsilon^m$}は１回のサンプリングで”あたり”を引ける確率です．{$\epsilon$}は母集団に含まれるインライアの比率、{$m$}はサンプリングするデータ数です．例えば，直線のパラメータを推定する問題では２点です．次に，この確率が{$\eta \geq \eta_0$}となるように考えて{$k$}について解くと，次の式が得られます． {$$k \geq \frac{{\rm log}(1 - \eta_0)}{{\rm log}(1 - \epsilon^m)}$$} 　具体的に，{$\eta_0$}は0.99などの適度に大きな数値を設定します．この数値は，ユーザーがあらかじめ設定しておくことになりますが，あまり大きな数値（例えば0.999999など）を設定すると，{$k$}が大きくなりすぎて計算時間が膨大になるため注意が必要です． 　あと，{$\epsilon$}の数値は不明ですので予測して設定することになります．具体的には，繰り返しの最中に計算するRANSACの評価値{$C_i$}（推定したモデルのパラメータと整合するデータ数）の中で，その時点で最大の値{$C_{\rm max}$}からインライアの比率を設定します．これは，「少なく見積もって{$C_{\rm max}$}くらいはインライアが含まれているだろう」と考えた予測方法です． 　なお，{$\epsilon$}は，繰り返し計算の途中で決まるため，{$k$}の適正値も途中で決まることになります． **PROSAC (Progressive Sample Consensus) 　PROSACは，単純なランダムサンプリングではなく，インライアらしさの信頼度を参考にしてサンプリングを行う方法です．図１のフローでは，1aの部分で行う処理です．PROSACについて詳しく学びたい場合，文献[2]を参考にしてください． 　まず，母集団のデータには信頼度がついている前提です．例えば，画像の特徴点のマッチングを行って得たデータでは，マッチングの程度から信頼度を付与できます．要は，この信頼度に基づいて，良さそうなデータを優先的に引けるようにランダムサンプリングを調整する方法がPROSACです． 　具体的には，信頼度に応じて母集団のデータをソートして，上位のデータの範囲からサンプリングを行います．ただ，信頼度はあくまでも参考値で，上位のデータの範囲にインライアが含まれていない可能性もあり得ます．ですので，サンプリングするデータの範囲は徐々に広げて最終的には通常のRANSACと同じようにサンプリングされるようします． 　図２は，PROSACの実験結果を示します．通常のRANSACでは，10万回以上必要だった繰り返し回数が，数回に抑えられる結果が示されています．{{small:ただ，PROSACの効果が特に高い条件で実験しているため，多くの条件でここまで劇的な効果は得られないとは思います．}} [img:kxsb] {{small:図２ PROSACの実験結果 出典[2]}} {{small:[2]O.Chum, J.Matas, "Matching with PROSAC – Progressive Sample Consensus", Computer Vision and Pattern Recognition(CVPR), 2005}} {{small:[link:http://cmp.felk.cvut.cz/~matas/papers/chum-prosac-cvpr05.pdf] }} **verification 　RANSACの計算で特にネックになるのが評価値の算出です．サンプリングしたデータ群からモデルのパラメータを推定し，それが良いか悪いか見るために，母集団の全データとの整合度をチェックし整合するデータの個数を調べます．図１のフローでは，3aの部分で行う処理です． 　評価方法の高速化としては様々な方法が提案されていますが，基本的な考え方としては一部のデータで評価を行う方法です．例えば，一部のデータであっても，大体の評価値は計算できます．例えば，その評価値を参考に，もう少し丁寧な評価値計算を行うか，或いは”はずれ”として処理を切り上げるかを考えるわけです． 　文献[1]では，具体的にThe Td,d TesT, Bail-Out Test, SPRT testと呼ばれる方法が紹介されています． **local optimization 　RANSACでは外れ値の混入確率を抑えるため，最低限度のデータ数を使ってサンプリングを行い，モデルのパラメータを推定します．この時，”あたり”を引いていたとしても，データ数が少ない都合から精度が悪く良い評価値が出ない場合があります．そうなると，せっかく”あたり”を引けていてもそれを見落としてしまいます． 　そこで考えるのが，パラメータの高精度化を行うlocal optimizationです．local optimizationについて，詳しく学びたい場合，[3]の文献を参照してください．なお，図１のフローでは，4の部分で行う処理です． 　local optimizationでは，データを増やしてパラメータを再推定します．増やすデータは，一旦推定したモデルのパラメータから，インライアと思われるデータを選択します． {{small:[3]O.Chum, J.Matas, J.Kittler, "Locally optimized RANSAC", DAGM-Symposium, 2003}} {{small:[link:http://cmp.felk.cvut.cz/~matas/papers/chum-dagm03.pdf] }}