Brute-Force Matching
ブルートフォース(BF)マッチングは、記述子マッチングに対する厳密かつ網羅的なアプローチである: 画像1のすべての記述子を画像2のすべての記述子と比較し、最近傍(あるいは上位 個の近傍)を保持する。 個と 個のキーポイント、記述子次元 に対して、コストは である。これは、あらゆる近似手法(FLANN、kd-tree、LSH)が比較される基準であり ―― フレーム間SLAMで典型的な記述子数に対しては、しばしば正しい選択である。
距離指標
- 浮動小数点記述子(SIFT、SuperPoint): ユークリッド(L2)距離
- バイナリ記述子(ORB、BRIEF、AKAZEのM-LDB): ハミング距離 ―― 異なるビットの数であり、以下のように計算される
256ビットのORB記述子はわずか32バイトしか占有せず、XOR + popcountは単一のマシン命令であるため、完全なハミング比較はほんの数サイクルで済む。これが、バイナリ記述子がブルートフォースマッチングをボトルネックから、CPU上で日常的に網羅的に実行できる(GPU上では自明に実行できる)ものへと変えた理由である。
生のマッチをフィルタリングする
最近傍距離だけでは受理基準として不十分である。いくつかの標準的なフィルタが曖昧で偽のマッチを除去する:
- Loweの比率テスト。 クエリ記述子ごとに、最近距離 と2番目に近い距離 を見つけ、以下の場合にのみマッチを受理する
識別性のある正しいマッチは、次点よりもはるかに近いはずである。2つの候補がほぼ等距離であれば、そのマッチは曖昧であり(繰り返しテクスチャ)、破棄される。この単一のテストだけで、偽マッチの大部分が排除される。
- クロスチェック(相互最近傍)。 が の最近傍でありかつ が の最近傍である場合にのみ を受理する。単純な対称的一致性フィルタであり、バイナリ記述子に対しては比率テストの代わりによく使われる。
- 絶対距離の閾値。 バイナリ記述子については、ハミング距離が上限を超えるマッチを拒否する(異なるビットの割合が大きいということは、パッチが無関係であることを意味する)。
- 幾何検証。 記述子フィルタリングを通過したものにも、まだ外れ値が含まれている。エピポーラモデルやホモグラフィモデルに対するRANSACが最終的な関門である。
ブルートフォースが有利な場合 ―― そうでない場合
BFマッチングは厳密であり、ビルド時のパラメータやチューニングパラメータを持たず、極めて並列化しやすい(SIMD、GPU)。それぞれ数千個のキーポイントを持つ2つのフレームをマッチングする場合、これは十分に単純かつ高速である。近似最近傍構造が効果を発揮するのは、データベース側が大きく、多くのクエリにわたって再利用される場合である ―― 場所認識のデータベース、大きなマップに対する再局在化、数万枚の画像を扱うオフラインSfMなどである。
実行中のSLAMシステム内では、ブルートフォースすら完全に回避されることが多い: 運動予測が利用可能であれば、特徴は**投影ガイド付き探索(projection-guided search)**によってマッチングされる ―― マップ点を現在のフレームに投影し、予測された位置周辺の小さなウィンドウ内でのみ記述子を比較する。これにより、候補集合が「すべての特徴」から「近傍のわずかな特徴」へと縮小され、どのグローバルマッチングよりも高速かつ曖昧性が低くなる。
SLAMにおける意義
データアソシエーション(data association)はフロントエンドの中核的な仕事であり、比率テストやクロスチェックを伴うブルートフォースマッチングは、初期化、広基線キーフレームマッチング、ループクロージング検証のための推定対応関係を得るための標準的な方法である。そのコスト構造を理解すること ―― そしてバイナリ記述子とハミング距離が網羅的探索をいかに安価にするか ―― は、ORB-SLAMのようなシステムにおける主要な設計選択を説明し、近似探索(FLANN、LSH、語彙木ルックアップ)の追加された複雑さがいつ正当化されるのかを明確にする。