ORB (Oriented FAST and Rotated BRIEF)

ORB(Rublee et al., 2011)は、ORB-SLAMをはじめ多くのリアルタイム視覚SLAMを支えるキーポイント検出器+バイナリ記述子の組み合わせである。SIFT/SURFに代わる、高速でパテントフリーな代替として設計された。SIFTより2桁高速でありながら、トラッキング、リローカライゼーション、ループクロージングに十分なマッチング品質を持つ。名前が示すとおり、これは2つの改良が組み合わされたものである。oFAST(向き付き FAST)とrBRIEF(回転対応 BRIEF)である。

oFAST:向き情報を持つFASTキーポイント

FASTは候補点周りの16ピクセルの円をテストしてコーナーを見つけるが、スケールも向きも提供せず、そのコーナー応答は検出間で比較可能ではない。ORBはこの3点すべてを修正する。

スケール:FASTを画像ピラミッドのすべてのレベルで実行するため、カメラが近づいたり遠ざかったりしても同じ実世界の点が検出できる。
ランキング:検出された候補はHarrisコーナー尺度でスコア付けされ、上位 $N$ 個が保持される——FAST単体はエッジ上でも反応してしまう傾向がある。
向きは**強度重心(intensity centroid)**によって決まる。パッチのモーメントと向きを次のように定義する。

m_{pq} = \sum_{x, y \in \text{patch}} x^p y^q\, I(x, y), \qquad \theta = \operatorname{atan2}(m_{01},\, m_{10})

コーナーの中心からパッチの強度重心へのベクトルが再現性のある角度 $\theta$ を与える。画像を回転させると、 $\theta$ も一緒に回転する。この単一の角度が記述子を回転不変にするものである。

rBRIEF:方向補正され、無相関化されたバイナリ記述子

BRIEFは、平滑化されたパッチを $n$ 個の二値の輝度比較によって記述する。あらかじめ定義されたオフセット対 $(\mathbf{a}_i, \mathbf{b}_i)$ について、ビット $i$ は

\tau_i = \begin{cases} 1 & I(\mathbf{a}_i) < I(\mathbf{b}_i) \\ 0 & \text{otherwise} \end{cases}

となり、 $n$ ビットの文字列を与える(ORBでは $n = 256$ 、つまり32バイト)。素朴なBRIEFは回転に対して崩壊するため、ORBはテストパターンを**方向補正(steer)**する。すべての点対は、サンプリング前にキーポイントの向き $\theta$ で回転される(ルックアップテーブルとして離散化されている)。

しかし方向補正は、BRIEFが持つ統計的な良さの一部を破壊する——回転されたテストは相関が強くなり、識別力が低下する。ORBの答えはrBRIEFである。すなわち、大規模な候補テスト対のプールに対する貪欲なオフライン探索であり、平均が0.5に近く(各ビットが情報を持つ)、かつすでに選ばれたテストとの相関が低い256個のテストを選択する。この結果、バイナリ形式を保ちながら失われた識別力の大部分を回復する。

ORB記述子のマッチング

バイナリ記述子はハミング距離——異なるビットの数——で比較され、popcount(x XOR y)として計算される。これは記述子対1組あたり数個のマシン命令で済む。これによって、数千個の記述子のブルートフォースマッチングがリアルタイムで実行可能になり、地図規模の検索はLSHまたはbag-of-wordsの転置インデックスが処理する。通常のフィルタが適用される。最良と2番目に良い距離の間でのLoweの比率テスト、クロスチェック、RANSACによる幾何検証である。

実践において

OpenCVはORBをcv::ORB::create()として提供しており、重要なパラメータが直接公開されている。保持する特徴数、ピラミッドのスケール係数とレベル数、FASTしきい値である。ORB-SLAMから得られる2つの実践的な習慣は真似する価値がある。

空間的な分布:単純に応答の強い上位N個を取ると、特徴が高テクスチャ領域に偏りがちである。画像をグリッドにバケット分割する(あるいはORB-SLAMが使うクアッドツリー分布)ことで、セルごとのクォータを強制し、幾何的に望ましい、よく分散した特徴を得られる。
ピラミッドを意識したマッチング:ピラミッドレベル $k$ で抽出された記述子は、類似のレベルとマッチングされるべきである。大きく異なるスケール間で比較すると、偽の候補にハミング予算を浪費してしまう。

SLAMにおける意義

ORBは、CPUや組み込みハードウェア上で特徴ベースSLAMを実用的にしたスイートスポットを捉えている。1フレームあたり約1000個の特徴の検出・記述・マッチングを、30fpsの予算内で余裕をもって行いながら、広いベースラインでのマッチングに十分な不変性(ピラミッドによるスケール、oFAST/rBRIEFによる回転)を持つ。ORB-SLAMは、この1つの特徴の上に全体のアーキテクチャを構築した——同じORB記述子が、フレーム間トラッキング、ローカルマップマッチング、リローカライゼーション、そしてbag of visual words語彙を通じたループクロージング検出のすべてに使われる——これがこのシステムがこれほど一貫性があり頑健である理由の大きな部分を占めている。深層学習の時代においても、ORBは学習された特徴(SuperPointなど)が比較される際のデフォルトのベースラインであり続けており、計算資源が乏しい場合の現実的な選択肢でもある。

ハンズオン

古典的な局所特徴検出