Bag of Visual Words

**Bag of Visual Words(BoVW)**は、テキスト検索のアイデアを画像に応用したものである(Sivic & Zisserman, 2003): 局所特徴記述子を「visual words」の離散的な語彙に量子化し、画像を単語出現のヒストグラムとして記述し、ヒストグラムを比較することで画像を比較する。これはSLAMにおけるループクロージング検出と再局在化(relocalization)の背後にある古典的なエンジンである(例えばORB-SLAMにおけるDBoW2)。

パイプライン

語彙構築(オフライン)。 訓練用コーパスから大量の局所記述子(例: ORB、SIFT)を収集し、k-meansで $K$ 個のクラスタ中心 ―― visual words ―― にクラスタリングする。バイナリ記述子の場合、クラスタ中心はユークリッド平均ではなくハミング空間の中央値で計算される。
画像表現。 新しい画像ごとに記述子を抽出し、それぞれを最も近いvisual wordに割り当てる。画像は $K$ 次元のヒストグラム $\mathbf{v}$ となり、ビン $k$ は単語 $k$ に割り当てられたキーポイントの数を数える。すべての空間的レイアウトは捨てられる ―― これが「bag(袋)」という名前の由来である。
TF-IDF重み付け。 すべての単語が等しく情報量を持つわけではない。各ビンは、単語頻度と逆文書頻度の積で重み付けされる:

$v_k = \frac{n_{k,d}}{n_d} \cdot \log\frac{N}{n_k}$

ここで $n_{k,d}$ は画像 $d$ における単語 $k$ の出現数、 $n_d$ は画像内の単語の総数、 $N$ はデータベース画像数、 $n_k$ は単語 $k$ を含むデータベース画像の数である。あらゆる場所に現れる単語(床のテクスチャ、木の葉など)は重みが下げられ、稀で特徴的な単語がスコアを支配する。

検索。 重み付けされたヒストグラムを正規化し、類似度スコアを計算する ―― DBoW2はL1ベースのスコアを用いる

$s(\mathbf{v}_1, \mathbf{v}_2) = 1 - \frac{1}{2}\left\lVert \frac{\mathbf{v}_1}{\lVert \mathbf{v}_1 \rVert} - \frac{\mathbf{v}_2}{\lVert \mathbf{v}_2 \rVert} \right\rVert_1$

―― そしてスコアの高いデータベース画像上位をループクロージング候補として返す。

階層的語彙木

フラットな語彙は各記述子を割り当てるのに $O(K)$ の距離計算を必要とし、識別性の高い検索に必要な $K \sim 10^5$ – $10^6$ 個の単語に対しては遅すぎる。DBoW2/DBoW3は、階層的k-meansによって構築される**語彙木(vocabulary tree)**に単語を配置する: 各ノードで $k$ 個の分岐、 $L$ 層のレベルを持ち、 $K = k^L$ 個の葉ノード単語を与える。記述子の割り当ては、各レベルで $k$ 個の子ノードと比較しながら木をたどる ―― $O(kL)$ 、つまり $K$ に対して対数的である。

2つのインデックス構造が検索と検証を高速化する:

転置インデックス(inverted index): 各単語について、それを含むデータベース画像のリスト(重み付き)。クエリのスコアリングは、少なくとも1つの単語を共有する画像だけに触れる。
直接インデックス(direct index): 各画像について、ある中間レベルの木のノードごとにグループ化された特徴。候補が検索されたとき、幾何検証のための対応関係は、同じノードに落ちる特徴だけをマッチングすることで見つけられる ―― ブルートフォースの記述子マッチングよりはるかに高速である。

実践上の注意

語彙サイズが重要である: 小さい語彙は似ていない特徴を同じ単語に衝突させてしまう(識別性が低い)。非常に大きい語彙は、マッチする特徴を複数の単語に分割してしまう(再現性が低い)。検索システムが大きい語彙を使うのは、まさに階層木によって割り当てが安価に保たれるからである。
ループクロージングのための正規化: 生のスコアはシーンのテクスチャの豊富さに依存するため、ORB-SLAMのようなシステムは、クエリの共視性キーフレーム(covisible keyframes)の中での最高スコアで候補のスコアを正規化し、絶対的な閾値を相対的な閾値に変換することで、異なる環境間で転用可能にしている。
どこでも同じ語彙を使う: 事前訓練された環境非依存の語彙(例えばORB-SLAMに付属するORB語彙)は、実際には驚くほどうまく機能し、デプロイごとの訓練を回避できる。

限界と検証ステップ

BoVWは幾何情報を捨てるため、テクスチャの統計が似ている2枚の画像は、同じ場所を描いていなくても高いスコアを得ることがある(知覚的エイリアシング(perceptual aliasing) ―― 通路、レンガの壁など)。したがって、実用的なループクロージングパイプラインはBoVWの出力を候補のみとして扱い、幾何検証によって確認する: 特徴をマッチングし、RANSACで基本/基礎行列やPnP姿勢を推定し、十分な内点が一貫した幾何を支持する場合にのみループを受け入れる。時間的一致性チェック(複数の連続するフレームでマッチングを要求する)は、さらに偽陽性を抑制する。ある視覚領域で訓練された語彙は、非常に異なる環境には不完全にしか転用できない。

SLAMにおける意義

オドメトリはドリフトする。ループクロージングこそがSLAMを単なる推測航法(dead reckoning)以上のものにするものであり、BoVWはマップサイズに関わらず一定時間でループを見つける古典的な方法である。これはまた、トラッキング失敗後の再局在化や、複数セッション間のマップ位置合わせも支えている。学習ベースの大域的記述子(NetVLADとその後継)が新しいシステムで検索ステージを置き換えつつある今でも、BoVWのアーキテクチャ ―― 量子化、重み付け、転置、検証 ―― は参照設計として残っており、DBoW2形式の語彙は高速でコンパクト、CPUのみで動作するため、多くの実運用システムで今も動いている。

ハンズオン

大域的特徴検出