LSH (Locality-Sensitive Hashing)

Locality-Sensitive Hashing（LSH、局所性感応ハッシュ）は、単純な考え方に基づく近似最近傍探索技術である。ディスクリプタをハッシュ化することで、類似したディスクリプタが高い確率で衝突する（同じバケットに入る）一方、非類似のものは低い確率でしか衝突しないようにする。クエリはデータベース全体ではなく、そのバケット内にある少数の候補とだけ比較すればよい。

局所性感応性という性質

ハッシュ関数の族 $\mathcal{H}$ が距離 $d(\cdot,\cdot)$ に対して $(r, cr, p_1, p_2)$-感応（sensitive）であるとは、任意の2点 $\mathbf{p}, \mathbf{q}$ について次が成り立つことをいう。

• $d(\mathbf{p}, \mathbf{q}) \leq r$ ならば $\Pr[h(\mathbf{p}) = h(\mathbf{q})] \geq p_1$、
• $d(\mathbf{p}, \mathbf{q}) \geq cr$ ならば $\Pr[h(\mathbf{p}) = h(\mathbf{q})] \leq p_2$、

ただし $p_1 > p_2$ かつ $c > 1$ である。言い換えれば、近い点は衝突しやすく、遠い点は衝突しにくいということである。

ハミング距離下でのバイナリディスクリプタ（ORB、BRIEF、AKAZEのMLDB）に対しては、自然な族はビットサンプリングである。$h(\mathbf{x}) = x_i$ をランダムに選んだビット位置 $i$ とする。長さ $n$ の2つのディスクリプタが $d_H$ ビットで異なる場合、それらが衝突する確率は

となり、距離に応じて正確に減少する——局所性感応性を無償で得られる。

増幅: kビット、Lテーブル

単一のランダムビットは非常に弱いハッシュであるため、LSHは2つの方向で増幅を行う。

• 連結（AND）: $k$ 個のハッシュ関数から各テーブルのキーを構築する。$g(\mathbf{x}) = (h_1(\mathbf{x}), \dots, h_k(\mathbf{x}))$。1つのテーブルの衝突確率は $(1 - d_H/n)^k$ となる——大きな $k$ はバケットをより小さく、より選択的にし、偽陽性を減らす。
• 複数テーブル（OR）: $L$ 個の独立なテーブルを構築し、すべてを探索する。真の近傍が少なくとも1つのテーブルで衝突する確率は

$k$ と $L$ の調整は精度と速度・メモリのトレードオフである。選択的なキー（大きな $k$）は、再現率を保つために多くのテーブル（大きな $L$）を必要とする。

Multi-probe LSH

標準的なLSHは良好な再現率を達成するために多くのハッシュテーブルを必要とし、メモリを多く消費する。Multi-probe LSHは、真の近傍がクエリのバケットを外した場合、それはおそらく近くのバケット——キーがわずかな位置しか異ならないバケット——に落ちているという観察に基づく。テーブルを追加する代わりに、multi-probeクエリはキーを摂動させた探索列（キーの1ビットを反転、次に2ビット、…）を、近傍を保持している可能性の高さの順に生成し、同じテーブル内でそれらの追加バケットを検査する。これにより、クエリごとの探索回数は増えるものの、数分の一のテーブル数で同程度の再現率を達成できる。OpenCVのFLANNベースのLSHインデックスは、まさにこれらのパラメータ——テーブル数、キーサイズ $k$、multi-probeレベル——を公開している。

SLAMにおける意義

特徴点ベースのSLAMシステムは1フレームあたり数千個のバイナリディスクリプタを生成し、それらを数百万件を含む地図やキーフレームデータベースに対してマッチングしなければならない。ブルートフォースマッチングは正確だが $O(nm)$ でスケールする。kd木は高次元のバイナリデータに対して性能が大きく劣化する。LSHはバイナリディスクリプタに対する標準的な解答であり——FLANNがORB/BRIEFデータに対して選択するものである——ミリ秒単位でクエリのディスクリプタ集合を大規模な地図に対してマッチングしなければならない、高速なリローカライゼーションやループクロージング候補検索を支えている。$k$/$L$/multi-probeのトレードオフを理解することで、プラットフォームに合わせて再現率とレイテンシを調整できるようになる。

関連ノート

• FLANN
• Kd-tree
• Brute-force matching
• ORB
• HBST