GNC

Yang 2020 · 論文

一行要約 — Graduated Non-Convexity(GNC):凸なサロゲートコストから出発し、それを徐々に目的のロバスト(非凸)コストへと変形させる汎用ロバスト推定フレームワークで、任意の非最小解法のブラックボックスラッパーとして機能する — 初期推定値は不要。

問題

半正定値計画(SDP)や平方和(SOS)緩和は、いくつかのロボティクスおよびビジョン問題(ポーズグラフ最適化、回転平均化、位置合わせ)に対して、証明可能に最適な非最小解法を生み出してきたが、これらの解法は最小二乗の定式化に依存しているため、誤ったループクロージャや誤対応のようなアウトライアに対して脆弱である。標準的な対処法であるロバストコスト関数(Geman-McClure、Truncated Least Squares)は非凸性を再導入するため、局所反復最適化には良い初期推定値が必要となる — そして証明可能な解法はそもそも適用できなくなる。GNCは、初期推定値を必要とせずに非最小解法とロバスト推定を同時に使用可能にする。

手法とアーキテクチャ

アウトライアのない推定は最小二乗、$\min_{\mathbf{x}\in\mathcal{X}}\sum_{i=1}^{N} r^2(\mathbf{y}_i,\mathbf{x})$であり、$r$は推定値$\mathbf{x}$における測定$\mathbf{y}_i$の残差である;ロバスト化は二次項をロバストコスト$\rho$に置き換える。GNCの代わりに、制御パラメータ$\mu$によって支配されるサロゲート$\rho_\mu$を最適化する。これはスケジュールの一端では凸であり、もう一端では$\rho$に等しくなる。Geman-McClure(GM)の場合:

$$\rho_\mu(r) = \frac{\mu\bar{c}^2 r^2}{\mu\bar{c}^2 + r^2},$$

これは$\mu\to\infty$で二次(凸)になり、$\mu=1$でGMを回復する;$\bar{c}$はインライアに期待される最大誤差に設定される。Truncated Least Squares(TLS)についても類似の三分岐サロゲートが導出され、$\mu\to 0$で凸、$\mu\to\infty$で厳密になる。

主要な鍵はBlack-Rangarajan双対性である:$\sum_i \rho_\mu(r_i)$の最小化は、重み付き最小二乗問題とアウトライアプロセスの和に等価である。

$$\min_{\mathbf{x}\in\mathcal{X},\ w_i\in[0,1]} \sum_{i=1}^{N} \Big( w_i\, r^2(\mathbf{y}_i,\mathbf{x}) + \Phi_{\rho_\mu}(w_i) \Big),$$

ここで$w_i$は測定ごとの重みであり、$\Phi_{\rho_\mu}$はそれに対する罰則項である — GMの場合$\Phi_{\rho_\mu}(w_i)=\mu\bar{c}^2(\sqrt{w_i}-1)^2$;TLSの場合$\Phi_{\rho_\mu}(w_i)=\frac{\mu(1-w_i)}{\mu+w_i}\bar{c}^2$である。各固定$\mu$において、アルゴリズムは2つのステップを交互に行う。

1. 変数更新 — $\mathbf{x}^{(t)} = \arg\min_{\mathbf{x}\in\mathcal{X}} \sum_i w_i^{(t-1)} r^2(\mathbf{y}_i,\mathbf{x})$:アウトライアのない問題の重み付き版であり、既存の非最小解法(Hornの手法、SE-Sync、メッシュ位置合わせSDPなど)によって大域的に解かれる。
2. 重み更新 — 閉形式で得られる。GNC-GMの場合、残差$\hat{r}_i^2 = r^2 (\mathbf{y}_i,\mathbf{x}^{(t)})$として:

$$w_i^{(t)} = \left( \frac{\mu\bar{c}^2}{\hat{r}_i^2 + \mu\bar{c}^2} \right)^{2};$$

GNC-TLSの場合は三分岐の規則が用いられ、$\hat{r}_i^2 \le \frac{\mu}{\mu+1}\bar{c}^2$のとき$w_i=1$、$\hat{r}_i^2 \ge \frac{\mu+1}{\mu}\bar{c}^2$のとき$w_i=0$、その間では$w_i = \frac{\bar{c}}{\hat{r}_i}\sqrt{\mu(\mu+1)} - \mu$となる。

外側のループは非凸性の量を増加させていく:GNC-GMは$\mu = 2r_{\max}^2/\bar{c}^2$で初期化し、外側の反復ごとに1.4で除算して$\mu<1$になるまで続ける;GNC-TLSは$\mu = \bar{c}^2/(2r_{\max}^2-\bar{c}^2)$で初期化し、重み付き残差和が収束するまで1.4を乗算し続ける。すべての重みは1から始まる。解法は重み付き最小二乗を解くよう求められるだけなので、GNCはCeres/g2o/GTSAMスタイルのバックエンドや証明可能な解法の周りでブラックボックスとして機能する。さらなる貢献として、本論文はシェイプアライメント(2D-3D対応からの弱透視物体ポーズ)に対する初の証明可能に最適な非最小解法を提案し、非単位四元数$\mathbf{v}=\sqrt{s}\,\mathbf{q}$における4次多項式をSOS緩和によって最小化する(経験的には常に厳密)。

実験結果

• 点群位置合わせ(Stanford Bunny、$N=100$対応、ノイズ$\sigma=0.01$):GNC-GM、GNC-TLS、RANSAC、ADAPTはいずれもアウトライア90%未満で同程度の精度を達成し、90%で破綻する;アウトライア80%における平均実行時間は218ms(RANSAC)、22ms(GNC-GM)、23ms(GNC-TLS)。TEASERはさらに頑健だが、大規模な事例では5分以上かかる。
• メッシュ位置合わせ(PASCAL+の「car-2」;点対点40、点対線80、点対面80の対応):GNC-GM、GNC-TLS、ADAPTはアウトライア80%まで頑健であり、12点最小解法を使うRANSACは50%で破綻する;GNCの反復回数はほぼ一定を保つのに対し、ADAPTのそれはアウトライア率に線形に増加する。
• ポーズグラフ最適化(汚染されたループクロージャを持つINTELとCSAIL、g2o、DCS、PCM、ADAPTと比較):GNC-TLSが支配的である — INTELではアウトライア40%まで無感応で70~80%まで許容範囲、CSAILではアウトライア90%まで頑健である;g2oは全体的に性能が悪く、DCS/PCMは徐々に劣化する。
• シェイプアライメント(FG3DCar、全600画像):GNC-GM/TLSとADAPTはアウトライア70%まで頑健;RANSACは60%で破綻;Zhouの凸緩和は急速に劣化する。1回のSOS解法は約80msかかる。

主な結論:ロバストな非最小解法はアウトライア70~80%を許容し、RANSACを上回り、専用の局所解法よりも精度が高く、専用の大域解法よりも高速である — ただしGNCの大域的最適性は保証されない。

SLAMにおける意義

アウトライア除去は、使用可能な地図と破損した地図の分かれ目であり、GNCはすべてのSLAMバックエンドに、問題固有の凸緩和を必要としない、シンプルで汎用的なロバスト化を提供する。GTSAMにはGncOptimizerとして実装されており、ロバストなポーズグラフ最適化、点群位置合わせ、回転平均化に使われている;Carloneグループ内では、証明可能な解法(SE-Sync、TEASER++)を補完する実用的で汎用的なツールとなっている。

関連ノート

• SE-Sync — 証明可能に最適なポーズグラフ最適化
• TEASER++ — GNCのアイデアも用いる証明可能でロバストな位置合わせ
• QUASAR — GNCも用いるTLSコストによる、極端なアウトライア下での証明可能な回転探索
• Robust pose-graph optimization — GNCが対処する問題設定
• ICP — GNCがロバスト化できる位置合わせパイプライン