FLANN (Fast Library for Approximate Nearest Neighbours)

FLANN（Muja & Lowe, 2009）は、高次元空間における近似最近傍探索のためのライブラリであり、大規模な記述子マッチングを実用的にすることを目的として構築された。厳密なブルートフォースマッチングは、次元 $d$ の $n$ 個のクエリ記述子と $m$ 個のデータベース記述子に対して $O(n \cdot m \cdot d)$ のコストがかかり、厳密な木探索も高次元ではほぼ線形スキャンに退化してしまう。FLANNの立場は実用的である。真の最近傍を、たとえば95%の確率で見つけられれば十分とし、その代わりに1〜2桁の高速化を得る、というトレードオフだ。これは特徴点マッチングにおいては十分許容できる。どうせ後段の比率テストやRANSACが誤ったマッチを捨ててくれるからである。

2つの中核インデックス構造

ランダム化kd木フォレスト。 1本のkd木を網羅的に探索する代わりに、FLANNは複数の木を構築し、それぞれの分割次元を分散が最も大きい少数の次元の中からランダムに選ぶ。すべての木は、分割境界までの距離で順序付けられた単一の共有優先度キューを通じて同時に探索され、探索は固定されたリーフチェック数の予算に達した時点で停止する。各木が空間を異なる方法で分割するため、ある木では分割の誤った側に落ちてしまう真の近傍点も、別の木では通常見つかる。これは浮動小数点記述子（SIFTの128次元、SuperPointの256次元）に対する第一選択の手法である。

優先度探索k平均木。 データはk平均法によって再帰的に分割され、各ノードで $K$ 個のクラスタ（分岐係数）が作られる。これにより、軸に沿った切断ではなく、データの自然なクラスタリングを反映した階層構造が構築される。クエリは最も近いクラスタへ降りていき、優先度キューを通じて未探索の分岐へバックトラックする。より高い精度が求められる場合、この方式が優れていることが多い。

バイナリ記述子（ORB、BRIEF）については、FLANNは代わりにマルチプローブLSHインデックスを提供する。ハミング空間には意味のある軸に沿った分割が存在しないが、ビットサンプリングハッシュ関数はそこで自然に局所性を保存する性質を持つ。

アルゴリズムの自動設定

FLANNの特徴的な機能は、アルゴリズムを自動で選んでくれることだ。データセット、目標とする探索精度（返される真の最近傍の割合）、そしてビルド時間・メモリと問い合わせ時間のどちらを重視するかを表す重みを与えると、データのサンプルに対して交差検証を行い、最適なインデックスタイプとパラメータ（木の本数、分岐係数、リーフチェック予算）を返す。これが重要なのは、最適な構造がデータ分布と要求精度に本質的に依存するためであり、唯一絶対の勝者は存在しないからである。

重要なパラメータ

自動調整であれ手動であれ、FLANNの挙動は少数のパラメータに帰着する。

木の本数（ランダム化kd森）：木が多いほど、リーフチェック予算あたりの再現率が上がるが、メモリとビルド時間のコストが増す。通常は数本程度が一般的である。
checks — クエリごとのリーフ訪問数の予算：探索時における精度/速度の最も直接的なダイヤルである。チェック数を増やすほど漸近的に厳密探索に近づく。
分岐係数と反復回数（k平均木）：粗い階層か細かい階層か、そしてビルド時にk平均法をどれだけ頑張らせるか。
目標精度（自動調整モード）：クエリのうち真の最近傍が返されるべき割合。FLANNはこれを満たす最小コストのパラメータ空間を探索する。

有用な心的モデルはこうだ。インデックスはどの候補が検査されるかを決め、checksは何個検査されるかを決める。精度の失敗は誤った距離としては現れず、単に一度も訪問されなかった正しい近傍として現れる。

マッチングパイプラインでの使用

FLANNを用いた典型的なSLAM/SfMのマッチング段階は以下の通りである。

参照画像の記述子（あるいは地図のランドマーク記述子）に対してインデックスを構築する。
各クエリ記述子について、2個の近似最近傍を取得する。
Loweの比率テストを適用する。 $d_1 / d_2 < 0.8$ の場合のみ受け入れ、曖昧なマッチを棄却する。
残ったマッチを幾何検証（essential matrixまたはPnPモデルに対するRANSAC）に渡す。

OpenCVではこれはcv::FlannBasedMatcherであり、cv::BFMatcherの代替として差し替え可能である。ただしORBに対してはLSHインデックスで設定する必要がある点に注意が必要だ。デフォルトのkd木は浮動小数点記述子を前提としているためである。近似には一つ注意点がある。比率テストは近似された第1・第2近傍を比較するため、積極的な速度設定はどのマッチが生き残るかを微妙に変えてしまう。

SLAMにおける意義

マッチングコストは地図のサイズに応じて増大し、SLAMシステムは常にマッチングを行っている。特徴点対地図の追跡、ループクロージング候補の検証、数千のキーフレームに対する再位置推定、そして画像集合をまたぐオフラインのSfMマッチング（COLMAPはFLANN流の近似探索を用いる）などである。数千個のORB特徴点を持つ2枚の画像に対してはブルートフォースで十分だが（ハミング距離＋popcountは非常に高速）、大きな地図や大きな語彙に対しては、準線形の近似探索がフロントエンドをリアルタイムに保つ鍵となる。FLANNはまた、3D点群に対する最近傍問い合わせの標準的な解答でもあり（PCLへの統合を通じて）、kd木がその低次元の得意領域で動作する場面、例えばICP内部の対応点探索などで用いられる。