BA on Graph Processor

Ortiz 2020 · 論文

一行要約 — バンドル調整がグラフプロセッサ(Graphcore IPU)上でガウス型ビリーフプロパゲーションを用いて極めて高速に解けることを初めて示した(CVPR 2020)論文であり、FutureMapping が提示したアルゴリズム・ハードウェア協調設計というビジョンを実証した。

問題

バンドル調整は SLAM と SfM における中心的な計算上のボトルネックである。古典的なソルバーは Levenberg-Marquardt を用いて MAP 解の点推定を計算する——これは本質的に集中的なバッチ計算であり、iSAM2 のようなツリーベースの逐次的手法でさえグラフの周期的な集中的再構成を必要とする。一方で、低消費電力の身体性を持つ Spatial AI は、データ転送を最小限に抑えた大規模並列・インプレース計算を要求する。本論文は、これまで幾何ビジョンではほとんど使われてこなかった GBP が、Graphcore の IPU——1216個の独立したコア(「タイル」)、各256KBのローカルメモリと6個のハードウェアスレッド、全対全の相互接続、GPU/CPU の DRAM でバイトあたり数百 pJ かかるのに対しオンチップアクセスはバイトあたり約1 pJ——に自然に対応することを示す。

手法とアーキテクチャ

因子グラフとしての BA。 変数はキーフレーム姿勢 XX とランドマーク LL であり、因子はガウス事前分布 ϕi(xi)\phi_i(\mathbf{x}_i)、θj(lj)\theta_j(\mathbf{l}_j)(単眼スケールを設定し2自由度の再投影メッセージを条件付けるために必要であり、測定項より100倍弱く自動生成される)、および測定モデル h(xk,lm)=π(Rklm+tk)\mathbf{h}(\mathbf{x}_k,\mathbf{l}_m) = \pi(R_k\mathbf{l}_m + \mathbf{t}_k) を持つ再投影因子 ψkm\psi_{km} である。MAP 推論は事前分布と再投影にわたる二乗マハラノビス残差の和を最小化する。(xk,0,lm,0)(\mathbf{x}_{k,0},\mathbf{l}_{m,0}) 周りで 2×92\times 9 のヤコビアン J\mathrm{J} を用いて線形化すると、各測定因子は情報形式で次のようになる:

ηkm=J⊤ΣM−1(J[xk,0lm,0]+zkm−h(xk,0,lm,0)),Λkm=J⊤ΣM−1J.\eta_{km} = \mathrm{J}^{\top}\Sigma_M^{-1}\left( \mathrm{J}\begin{bmatrix}\mathbf{x}_{k,0}\\ \mathbf{l}_{m,0}\end{bmatrix} + \mathbf{z}_{km} - \mathbf{h}(\mathbf{x}_{k,0},\mathbf{l}_{m,0}) \right), \qquad \Lambda_{km} = \mathrm{J}^{\top}\Sigma_M^{-1}\mathrm{J}.

GBP メッセージパッシング。 各変数ノードはビリーフ bit(vi)=N−1(vi;ηbit,Λbit)b_i^t(\mathbf{v}_i)=\mathcal{N}^{-1}(\mathbf{v}_i;\eta_{b_i}^t,\Lambda_{b_i}^t) を保持する。分割されたパラメータを持つペアワイズ因子 ψij\psi_{ij} は変数 vi\mathbf{v}_i に次を送る:

ηj→it+1=ηiij−Λijij(Λjjij+Λbjt−Λi→jt)−1(ηjij+ηbjt−ηi→jt),\eta_{j\to i}^{t+1} = \eta_i^{ij} - \Lambda_{ij}^{ij}\left( \Lambda_{jj}^{ij} + \Lambda_{b_j}^{t} - \Lambda_{i\to j}^{t} \right)^{-1} \left( \eta_j^{ij} + \eta_{b_j}^{t} - \eta_{i\to j}^{t} \right),

Λj→it+1=Λiiij−Λijij(Λjjij+Λbjt−Λi→jt)−1Λjiij,\Lambda_{j\to i}^{t+1} = \Lambda_{ii}^{ij} - \Lambda_{ij}^{ij}\left( \Lambda_{jj}^{ij} + \Lambda_{b_j}^{t} - \Lambda_{i\to j}^{t} \right)^{-1} \Lambda_{ji}^{ij},

そして各変数は事前分布と受信メッセージを合計してビリーフを更新する: ηbit+1=ηpi+∑jηj→it\eta_{b_i}^{t+1} = \eta_{p_i} + \sum_j \eta_{j\to i}^{t}、Λ\Lambda についても同様である。因子からのメッセージは減衰され、ηt+1←(1−d) ηt+1+d ηt\eta^{t+1} \leftarrow (1-d)\,\eta^{t+1} + d\,\eta^{t}(d=0.4d=0.4)となる。再線形化は完全にローカルである: 因子は、その変数のビリーフが線形化点から β=0.01\beta = 0.01 以上ずれたときに再線形化する(最大でも10イテレーションごと)。ロバストコスト: マハラノビス距離 MkmM_{km} が NσN_\sigma を超えたときに因子のガウス分布をリスケールすることで Huber カーネルを組み込み、外れ値と疑われる測定からのメッセージを減衰させる。

IPU マッピング。 各因子/変数ノードは1つのタイルに対応する(大きなグラフでは6個のスレッドを用いて1タイルに複数ノードを配置)。IPU のバルク同期並列モデルの下で動作し、すべての因子が再線形化してメッセージを計算し、交換し、すべての変数がビリーフを更新し、交換する——GBP の1イテレーション全体は125マイクロ秒未満で完了する。実装全体は約1000行の Poplar C++ で書かれている。IPU は半精度・単精度は扱えるが倍精度を扱えないため、事前分布は当初測定制約と同じスケールで設定され、10イテレーションにわたって徐々に100倍弱められ、数値的安定性を保つ。

実験結果

評価には TUM と KITTI のシーケンスの一部を使用し、ORB-SLAM をフロントエンド(キーフレーム、ORB 特徴、対応点)とし、6コアの i7-8700K(18スレッド、密な Schur を用いた LM、Huber カーネル、解析的導関数)上の Ceres と比較する:

SLAMにおける意義

本論文は、グラフ、ローカルストレージ、メッセージパッシングを中心に SLAM の計算を再考することで桁違いの高速化が得られるという、FutureMapping の思索的な論考を具体的な証拠へと転換した。著者らは、本当の価値は静的な BA の速度ではなく、「Spatial AI 問題を表す一般的かつ動的に変化する因子グラフの柔軟なインプレース最適化」——異種の因子、認識からの事前分布、任意の逐次更新——にあると論じている。SLAM が異種のエッジハードウェアやマルチロボットシステムへ移行する中で、GBP の純粋にローカルな計算モデルは、コア数に自然にスケールする数少ないバックエンド設計の一つである。

関連ノート