HBST (Hamming Binary Search Tree)

HBST（Schlegel & Grisetti, 2018）はバイナリ記述子（ORB、BRIEF、BRISK、FREAK）向けの二分探索木であり、ハミング空間における近似最近傍問い合わせを対数コストで解答し、さらに——SLAMにとって重要な点として——探索中の増分挿入をサポートする。これはループクロージング検出のための、Bag-of-Visual-Words（DBoW2）やFLANN-LSHに代わる軽量で語彙不要な手法として提案された。事前学習された語彙に対して記述子を量子化する代わりに、軌跡から届く生の記述子をそのままインデックス化する。

木の構築方法

バイナリ記述子は固定長のビット文字列 $\mathbf{d} \in \{0,1\}^D$ （例えばORBでは $D = 256$ ）であり、XORとpopcountで計算されるハミング距離で比較される。

各内部ノードは単一のビット位置 $k \in \{0, \dots, D-1\}$ を保持する。記述子はビット $k$ が0であれば左に、1であれば右にルーティングされる。
各リーフは記述子の集合を（そのペイロード——SLAMにおいては記述子の出所となった画像/キーフレームのインデックスとキーポイントとともに）保持する。
リーフが最大サイズを超えると分割される。すなわち、そのリーフが保持する記述子に対して分割ビットが選ばれ、2つの子ノードに再配分される。

分割ビットはバランスを考慮して選ばれる。リーフ内の記述子について候補となる各ビットの平均値 $\bar{d}_k$ を計算し、平均が $0.5$ に最も近いビット、すなわち集合を最も均等に分割するビットを選ぶ。 $N$ 個の記述子に対してバランスの取れた木の深さはおよそ $\log_2 N$ になり、各クエリはルートからリーフへの1本のパスに触れるだけとなる。

探索——そしてなぜ近似的なのか

クエリ記述子 $\mathbf{q}$ は各ノードで指定されたビット位置を自身のビットで読み取りながら木を降りていき（深さ $h$ に対して $h$ 回のビットテスト）、単一のリーフに到達し、そのリーフの記述子とのみハミング距離で網羅的にマッチングされる（距離が閾値 $\tau$ 以下のマッチを受け入れる）。総コストはリーフサイズ $L$ に対して $O(\log N + L)$ であり、ブルートフォースの $O(N)$ に対して有利である。

その代償は近似性である。クエリの記述子が分割に使われたビットのいずれかで真のマッチと異なっている場合、それは別のリーフへルーティングされ見逃されてしまう。この確率は木の深さと記述子の雑音とともに増大する。HBSTはこれを受け入れる理由がある。場所認識にはすべてのマッチが必要なわけではなく、正しいキーフレームに投票するのに十分な一貫したマッチがあればよく、幾何検証がその後で後始末をしてくれるからである。

増分探索・挿入

HBSTをSLAMのオンライン設定に適合させているのがこの操作である。新しい画像が来るたびに、その記述子は一度だけ木の中を降ろされ、その同じ1回の通過の中で木は(1)これまでインデックス化されたすべてとのマッチを報告し、(2)新しい記述子を挿入する（オーバーフローしたリーフは分割される）。データベースはオフラインの学習フェーズも、語彙ファイルも、定期的な再構築も一切なく、軌跡とともに成長する。マッチはそれぞれの過去の画像ごとに集計され——マッチした各記述子は、それが属するキーフレームに対して1票を投じる——高い得票数を持つキーフレームがループクロージング候補となり、その後幾何的に検証される（例えば、RANSAC内でのessential matrixやPnP）。

$N$ 個の記述子からなるデータベース、最大リーフサイズ $L$ に対するコストをまとめると次のようになる。

挿入：ルートからリーフへの1回の降下、 $O(\log N)$ 、および時折発生するリーフ分割。
問い合わせ： $O(\log N)$ 回のビットテスト＋リーフ内での $O(L)$ 回のハミング比較。
メモリ：生の記述子と各内部ノードにつき1つのビット位置——ハッシュテーブルも語彙も不要。
調整ノブ：最大リーフサイズ $L$ （木が深く高速なリーフになるか、より良い再現率か）とマッチングの閾値 $\tau$ 。

代替手法の中での位置づけ

ブルートフォースマッチングは厳密だがデータベースサイズに対して線形である。2枚のフレームには十分だが、数千のキーフレームに対しては絶望的である。
**BoW（DBoW2/DBoW3）**は事前学習済みの語彙を必要とする。量子化は記述子の詳細を失うが、転置インデックスは非常に高速でメモリ効率が良い。
FLANN-LSHもバイナリ記述子を増分的に扱えるが、典型的なループクロージングのワークロードでは複数のハッシュテーブルを持ち、メモリ・レイテンシが高くなる。
HBSTは、記述子レベルでの直接マッチング（キーポイント対応が無料で得られ、幾何検証にすぐ使える）を、非常に高速な問い合わせと学習不要で実現する代わりに、一定量の再現率を犠牲にする。

SLAMにおける意義

ループクロージング検出は、「以前にこれを見たか？」という問いを、リアルタイムの予算内で、数フレームごとに、成長し続けるデータベースに対して問い続けなければならない。HBSTは、バイナリ記述子を既に計算している特徴点ベースのシステムに対する、クリーンで自己完結した解答である。語彙の配布が不要（DBoW2のORB語彙は大きなバイナリ資産である）、単一の構造から画像レベルかつキーポイントレベルの対応が得られ、軌跡に沿った問い合わせ時間は対数的にしか増大しない。また、ハミング空間をインデックス化する際の精度と速度のトレードオフを学ぶ好例でもある。LSHやBoWと比較することで、この3つすべてへの理解が深まる。