Covisibility graph

ORB-SLAMで顕著に導入された**共視グラフ(covisibility graph)**は、キーフレーム上の重み付き無向グラフである。

• ノード: キーフレーム。
• エッジ: 共通のマップ点を観測する2つのキーフレームを結ぶ。
• エッジの重み: 共有されるマップ点観測の数。ORB-SLAMでは、重みが閾値 $\theta$(通常は共有点約15個程度)を超えるとエッジが保持される。

このグラフは、キーフレームがいつどこで作成されたかに関わらず、何が何を見ているかを符号化する。同じ視点から数分離れて撮影された2つのキーフレームは強く接続されるが、速い旋回中の連続する2つのキーフレームはほとんど接続されないこともある。これにより、共視性は時間やユークリッド距離よりも視覚マップの「近傍」概念としてはるかに優れたものとなる。

SLAMシステムは共視グラフを常時クエリする。

• ローカルバンドル調整: 新しいキーフレームが到着すると、その共視近傍とそれらが見るマップ点とともに最適化する — 関連する幾何を正確に含む明確に定義されたローカルウィンドウである。
• トラッキングとマップ点の取得: 共視キーフレームによって観測される点を現在のフレームに投影し、より多くのマッチを見つける。
• ループ閉じ込み: 認識データベースからの候補地点は共視近傍に対して検証され、検出されたループは1つの姿勢だけでなく共視グループ全体を補正する。
• キーフレームの間引き: 観測がその共視近傍によって大部分カバーされているキーフレームは冗長であり、削除してマップをコンパクトに保つことができる。

密接に関連する構造がエッセンシャルグラフである。キーフレームのスパニングツリーからなる、はるかに疎な部分グラフで、重みの高い共視エッジとループ閉じ込みエッジで補強されている。ORB-SLAMは密な共視グラフではなくエッセンシャルグラフに対してポーズグラフ最適化を実行し、完全な最適化の精度の大部分をわずかなコストで得ている。

形式的定義と維持

$\mathcal{P}_i$ をキーフレーム $K_i$ によって観測されるマップ点の集合とする。2つのキーフレーム間の共視重みは単純に

$$w_{ij} = \left| \mathcal{P}_i \cap \mathcal{P}_j \right|,$$

であり、グラフはエッジ $(i, j)$ を $w_{ij} \geq \theta$ の場合のみ保持する。これには姿勢は一切関与しない — 観測に対する純粋な帳簿処理であり — これが安価かつインクリメンタルである理由である。

• キーフレームが挿入されると、そのマッチした点を見ているキーフレーム(各マップ点の観測リストから見つかる)との共有観測を数え、エッジを追加/更新する。
• マップ点が観測を獲得または失うと(融合、間引き、新しいマッチのトラッキング)、影響を受けた重みがローカルに更新される。
• キーフレームが間引かれると、そのエッジは消え、スパニングツリーはその子を他の近傍に再接続する。

実際には、各キーフレームは重みでソートされた近傍を保持するため、「上位$N$個の最良の共視キーフレーム」(ローカルBAウィンドウの定義やループ候補の拡張に使用される)のようなクエリは $O(1)$ の参照で済む。ORB-SLAMの設計における非対称な閾値に注目してほしい。共視グラフは比較的弱いエッジを保持する($\theta \approx 15$ 共有点)。これはローカルマッピングが緩やかな近傍から利益を得るためである。一方エッセンシャルグラフは強いエッジのみを保持する($\theta = 100$)。これはポーズグラフ最適化が少数の信頼できる制約を望むためである。

なぜ時間や距離ではないのか

代替手法の失敗モードを内面化しておく価値がある。時間的ウィンドウ(直近$N$フレーム)は、カメラが場所を再訪するたびに破綻する。同じシーンを観測している古いキーフレームがローカルBAから除外され、マップがローカルに重複してドリフトする。メトリック近傍(半径$r$メートル以内のキーフレーム)は向きによって破綻する — 半径メートル以内にあるが反対側の壁を向いているキーフレームは観測を共有せず、コストだけを増やして何も貢献しない — さらに、それ自体がドリフトしている姿勢推定に依存する。共視性は、近傍を観測空間で定義することでこの両方を回避する。すなわち、同じ幾何を制約する測定を持つキーフレームだけであり、これはまさに良条件な問題のためにローカルBAが必要とする集合である。

よくある落とし穴

• 閾値のトレードオフ: $\theta$ が低すぎるとローカルBAウィンドウが肥大化する(小さな部屋のすべてのキーフレームが他のすべてに接続される)。高すぎるとグラフが断片化し、BAへの制約が不足する。小さな部屋でテクスチャの豊富なシーンがストレステストとなる。
• 古くなった重み: 点の間引き/融合が共視エッジを更新しない場合、グラフは徐々に現実から乖離し、ローカルウィンドウに無関係なキーフレームが含まれるようになる。
• 2つのグラフの混同: ローカルマッピングは(密な)共視グラフをクエリし、ループ閉じ込みのポーズグラフ最適化は(疎な)エッセンシャルグラフ上で実行される。完全な共視グラフに対してPGOを実行することは、わずかな精度向上のために劇的に遅くなる — これがまさにエッセンシャルグラフ設計の要点である。
• 共視性がマッチ可能性を意味すると仮定すること: 2つのキーフレームは多くの点を共有していても極端に視点が異なる場合がある。グラフが近傍だと言っていても、それらの間の記述子マッチングは失敗する可能性がある。

SLAMにおける意義

共視グラフは、特徴ベースSLAMがスケールするためのデータ構造である。ローカルBAのコストを制限し、マップ点探索を絞り込み、ループ閉じ込み後の高速な大域補正のための疎な骨格(エッセンシャルグラフ)を提供する。ORB-SLAMで導入されたこの構造は、ORB-SLAM2/3とその多くの派生を含む、実質的にその後のすべてのキーフレームベースシステムのマップ管理に影響を与えた。

関連ノート

• ORB-SLAM
• ORB-SLAM3
• Visual Place Recognition (VPR)
• Pose graph optimization