SIFT
SIFT (Scale-Invariant Feature Transform) は、David Loweによって2004年に発表された、スケールおよび回転に不変な局所特徴のランドマーク的アルゴリズムである。ORB、AKAZE、SuperPointなどが今も従う検出器+記述子というテンプレートを定義し、マッチング精度において今も金標準であり続けている(例えばCOLMAP方式のオフライン再構成において)。
キーポイント検出: スケール空間中のブロブ
SIFTはコーナーではなくブロブを検出し、それを複数のスケールにわたって行うため、同じ実世界の構造が画像中で大きく写っても小さく写っても発見される。ガウシアンスケール空間は、増加するスケールを持つガウス関数で画像を畳み込むことで構築される。
隣接するスケール間の**差分ガウシアン(Difference of Gaussians, DoG)**は、スケール正規化されたLaplacian of Gaussian(ブロブ検出器)を、わずかな計算コストで近似する。
スケール空間はオクターブ(octaves)(オクターブ間で画像を2倍ダウンサンプリング)に、オクターブあたり複数のスケールを持つように構成される。つまり、ピラミッドの各レベルに複数のブラー段階を持つ画像ピラミッドである。
キーポイントは、空間とスケール両方における**の局所極値**である。各サンプルはにわたるの立方体内の26個の近傍と比較される。候補は以下のように処理される。
- 極値周りで2次関数(の二次テイラー展開)をフィッティングすることでサブピクセル/サブスケール精度に精密化される。
- コントラストによるフィルタリング — が小さい極値は不安定であり除外される。
- エッジ応答によるフィルタリング — DoGはエッジに沿って強く応答するが、そこでは位置決めが不良である。Harrisテストと同様に、主曲率の比(すなわちのヘッシアンの固有値の比)を閾値処理することで、ブロブらしく位置決めの良い点のみを保持する。
記述子: 128次元の勾配ヒストグラム
- オリエンテーション割り当て: キーポイント近傍における勾配方向のヒストグラム(勾配の強さとガウシアン窓で重み付け)を構築し、その中の主要なピークがキーポイントの正準方向を定める。すべての記述子の測定はこれに対して相対的に行われる。これが回転不変性を提供する。
- 記述子: キーポイント周辺の領域(検出されたスケールにおいて)はのサブ領域グリッドに分割され、各サブ領域が勾配方向の8ビンヒストグラムを蓄積し、次元のベクトルを与える。このベクトルは(大きな成分をクランプして再正規化することで)照明不変性のために正規化される。
マッチング
SIFT記述子は浮動小数点ベクトルであり、L2距離で比較される。曖昧なマッチはLoweの比率テストでフィルタリングされる。最近傍を採用するのは、を第1・第2最近傍への距離として、の場合のみである。大規模データベースでは、近似最近傍構造(kd木、FLANN)がブルートフォースを置き換える。SIFTの128次元は、kd木にとって実用上の限界に近い。
コスト
SIFTは非常に精度が高いが遅い。CPU上では高解像度画像1枚あたり1秒程度かかる。そのため、リアルタイムSLAMは歴史的にFAST/ORBを代わりに採用してきた。オンラインでSIFT級のロバスト性が必要な場合は、GPU実装やバイナリの代替が用いられる。
SLAMにおける意義
- カメラが構造に接近または後退する際、スケール不変性が不可欠である。マッチングは、固定スケールのコーナーが機能しなくなる大きな深度変化を乗り越えて生き残る。
- SIFTのパイプライン(スケール空間検出、オリエンテーション割り当て、勾配ヒストグラム記述子、比率テストマッチング)は、SLAMで使われるすべての特徴系のコンセプト上の設計図である。ORBは、その最良のリアルタイム近似と理解するのが正しい。
- オフラインマッピングとStructure-from-Motion(例えばCOLMAP)は、最大限のマッチング品質を得るために今もSIFTを既定としている。視覚的な場所認識も、歴史的にはSIFT記述子からバッグオブビジュアルワード語彙を構築していた。