特徴点の対応づけ「RANSACアルゴリズム」

以上、ここまではSIFTを例にして局所特徴量記述子について詳しく説明してきました。パノラマ画像の処理では、この局所特徴量をパノラマ画像生成に用いる各入力画像から個別に抽出し、それらの記述子の値を元に局所特徴量の存在する点の座標同士を画像間で対応づけます。そして、対応づいたそれらの特徴点ペアを用いることで、レジストレーション計算により各画像の「移動量」と「変形量」を算出することができます。

この局所特徴量の対応付けには「RANSAC(RANDdom Sample Consensus)」というアルゴリズムが用いられることが多いです。理工系や経済学部あたりで統計を学んだことがある方は「最小二乗法」という最も基本的なモデルフィッティング手法を学んだことがあると思います。たとえばある直線上にデータが乗ってくる傾向があるような統計データを集めてきたとして、その各数値がどういった傾きの直線上におよそ出ているのかを直線の傾きの値(=モデルのパラメータ)を変えていきながら二乗誤差(誤差を二乗したもの)を最小化したときに、一番データに対してモデルの直線がうまくあてはまったとみなして、その結果を直線の傾き(モデルのパラメータ)の最適値として推定するものです。しかし、最小二乗法はデータに「外れ値(outiler)」が含まれていると、その外れ値の影響がモデルフィってイングする際に大きくでてしまい、思ったようなモデルのパラメータを求めることができないという弱点があります。

最小二乗法によるモデルフィッティングの欠点(この例では直線をフィッティング)

パノラマ画像での各画像から抽出してきた局所特徴量は、他の画像に対応点が存在していない「外れ値」が多く含まれており、最小二乗法的な単純な誤差最小化によりどの点とどの点が対応するかを計算すると、外れ値が多くてうまく対応関係が作れません。そこで、パノラマ画像作成での対応点計算にはRANSACにより、外れ値に強いレジストレーションを行います。

RANSACでは以下の3つの手続きを、最適なモデルパラメータの評価値(スコア)が(3)で出てくるまで繰り返します。

(1):あらかじめ決めておいたサンプル数nだけランダムにデータをサンプリング。
(2):サンプルしたn個のデータを用いて、モデルのパラメータを算出(ここは最小二乗法的に誤差を最小化)。
(3):処理2で求めたモデルのパラメータに対して、あらかじめ範囲を決めておいた(例えば「モデルから距離3以内の」)インライア範囲内のデータのみを用いて、モデルのパラメータがどれくらい正しいかのスコアを評価。

この(1)～(3)の処理による各繰り返しにおいて、インライア(外れ値ではない、モデルフィッティングを行いたいデータ)のデータだけがモデルにうまくフィッティングできているかを判断します。こうしてインライアのデータだけにうまくフィッティングできている最適なモデルのパラメータを、ランダム繰り返し計算により求めることができます。(下記図中の直線フィッティングの例において、ランダムにサンプリングした黄色の点と、範囲を設定しておいた境界線内にあるインライアと一時的にみなしている赤色の点が、ともに1回の繰り返しにおける仮のインライアと見なすことになります)。

RANSACによる外れ値(Outlier)に強いモデルフィッティング(この例では直線をフィッティング)

RANSACは汎用性の高いモデルフィッティング手法で、Kinectなどの3次元スキャナで撮影した点群データから、たとえば平面部分を検出したり、円柱に近い物体を検出するときにもRANSAC系のアルゴリズムが用いられたりしています。