ジョイント互換性分岐限定法（JCBB）は、SLAM（同時位置推定と地図構築）およびコンピュータビジョンにおいて、観測された特徴を既知の地図またはモデルと照合するために使用されるデータ関連付けアルゴリズムである。これは、2001年にJosé NeiraとJuan D. Tardósが論文「Data Association in Stochastic Mapping Using Joint Compatibility」で発表した。このアルゴリズムは、センサ測定値がどのランドマークまたは地図特徴に対応するかを決定する問題に対処するものであり、移動ロボット工学における正確な状態推定のための重要なステップである。
個々の特徴マッチを独立に評価する単純な最近傍法とは異なり、JCBBは、セット内のすべての特徴間の統計的相関を考慮して、マッチのセットのジョイント互換性を評価する。このジョイントテストは、特に反復的または曖昧な特徴が存在する環境において、誤マッチに対してより堅牢である。このアルゴリズムは、分岐限定法戦略を用いて可能なマッチセットの空間を探索し、より良い解につながらない分岐を体系的に刈り込み、見つかったセットがジョイント互換性を持つ最大のものであることを保証する。
アルゴリズム概要
JCBBは、予測特徴のセット（現在の地図から）と観測特徴のセット（センサデータから）に対して動作する。各観測は最大で1つの予測特徴に割り当てることができ、各予測特徴は最大で1つの観測にマッチできる。目標は、ジョイントイノベーションベクトル（観測値と予測値の差）が、完全な共分散行列を考慮した上でカイ二乗閾値内にあるような、最大基数のマッチセットを見つけることである。
分岐限定法探索は、観測の特徴への部分的な割り当てを表す各ノードを持つツリーを構築する。各ステップで、アルゴリズムは次の未割り当ての観測を考慮し、その観測と各残りの特徴との互換性を、個別および既に割り当てられたマッチとのジョイントの両方でテストすることにより、ノードを展開する。ジョイント互換性テストが失敗した場合、その分岐は刈り込まれる。探索はすべてのノードが探索されるまで続き、最良（最大）のセットが返される。効率を向上させるために、アルゴリズムは観測のヒューリスティックな順序付けを使用し、通常は個々の互換性に基づいて、良い解を早期に見つけ、より積極的に刈り込む。
ジョイント互換性テスト
JCBBの核心はジョイント互換性テストである。マッチのセットが与えられると、テストはジョイントイノベーションベクトルとその共分散行列を計算する。このベクトルのマハラノビス距離は、イノベーションベクトルの次元に等しい自由度を持つカイ二乗閾値と比較される。距離が閾値未満の場合、セットはジョイント互換性があると見なされる。このテストは、ロボットの姿勢不確実性と地図の共分散から生じる特徴間の相関を捉えるため、個別テストよりも強力である。例えば、個別には異なる地図点と互換性がある2つの特徴が、それらの間の相対幾何学が地図と一致しない場合、ジョイントでは互換性がない可能性がある。
応用と拡張
JCBBは、特に屋内および屋外の移動ロボット工学におけるSLAMシステムで広く応用されている。これは、最適化またはフィルタリングの前にフロントエンドのデータ関連付けモジュールとしてよく使用される。このアルゴリズムは、カメラ画像で検出されたキーポイントを特徴とするビジュアルSLAMや、3D点群レジストレーションにも適応されている。拡張には、初期姿勢推定のためのRANSACとの組み合わせや、大規模地図を扱うための階層的フレームワークでの使用が含まれる。実際には、JCBBは多数の特徴に対して計算コストが高くなる可能性があるため、互換性グラフと最大クリークアルゴリズムを使用するなど、探索空間を削減する変種が提案されており、これらは解の観点ではJCBBと同等であるが、より高速である可能性がある。
他の方法との関係
JCBBは、高速であるが誤マッチを起こしやすい個別互換性最近傍法（ICNN）や、最大クリーク問題を解くグラフベースの方法など、他のデータ関連付け技術としばしば比較される。分岐限定法アプローチは、ジョイント互換性基準の下で大域的最適解を見つけることを保証するが、ヒューリスティック法は準最適なセットに落ち着く可能性がある。しかし、最適性はより高い計算複雑性のコストを伴い、JCBBはオフライン処理または中程度の数の特徴を持つ環境に適している。現代のSLAMシステムでは、JCBBは特徴マッチングのための機械学習または深層学習に基づく学習方法に置き換えられることがあるが、この分野の基礎的なアルゴリズムであり続けている。
関連項目
参考文献
- Neira, J., & Tardós, J. D. (2001). Data association in stochastic mapping using joint compatibility. IEEE Transactions on Robotics and Automation, 17(6), 890-897.