全5687文字
PR

 それが今年になりオーストラリアUniversity of AdelaideのÁlvaro Parraら(前者のEriksson氏らも含む)が、これを改良し、最適解を得られかつ効率的に推定できる手法を提案した4)。計算量は入力数に対し線形であり、入力視点数が千を増えても高速に計算でき、従来手法と比べ数十倍近く高速に解を求めることができる。現在でも入力画像数が千や万のオーダーとなると、姿勢推定に数十分や数時間かかる商用ソフトウエアも多い中、それらが数秒から数十秒で求められることになり大きなインパクトがある。これらについて説明していく。

Rotation Averaging

 はじめにRotation Averagingを説明する。この問題は無向グラフ上で定義される。グラフは$n$個の頂点からなり、枝$(i,j)$は頂点$i$と頂点$j$間の相対回転姿勢$\tilde{R}_{i,j}$を表す。目標は全ての枝$E$について$R_i \tilde{R}_{ij} =R_j$ができるだけ成り立つような絶対姿勢$R_1, R_2, \ldots, R_n$を推定することである。この式は$R_i$をさらに$R_{ij}$だけ回転させたら$R_j$になるはずという幾何制約からきている。相対回転姿勢の推定誤差を考慮し、距離関数$d$を使って、次のような最適化問題を解くことで絶対姿勢を推定するタスクをRotation Averagingとよぶ。

\[ \arg \min_{R_1,\ldots, R_n \in SO(3)} \sum_{(i, j) \in E} d(R_i R_{i j}, R_j) \quad (1) \]

ここで$SO(3)$は回転群を表し、サイズが$3 \times 3$の回転行列、つまり直交行列かつ行列式が$1$であるような行列の集合で表される(一意性を保障するため鏡像反転に対応する行列式が$-1$であるような行列は除く)。

 オリジナルの問題は複数の回転姿勢の推定$\{R_1, \ldots,R_n\}$が与えられた時、距離関数$d$上での平均を求めるものであったためRotation Averagingという名がつけられていた。

\[ \arg \min_{R \in SO(3)} \sum_{i=1}^n d(R_i, R) \]

そして、今回扱う問題は複数の回転(絶対回転と相対回転の積)の平均を同時に求めるような問題とみなすことができる。このRotation Averagingは簡単そうに見えるが回転行列$SO(3)$が凸集合でないことから全体は非凸最適化問題であり最適化が難しい。

Rotation Averagingの強双対性

 Eriksson氏らは2-3)、このRotation Averagingの双対問題はある条件下では強双対性を持ち、双対問題(実際は双対問題の双対問題)を解くことで最適解を得られることを示した。

 まず、距離として双対問題が扱いやすくなるコーダル距離$d(A, B) := ||A -B||_F^2$を利用する。コーダル距離は$R$、$S$がそれぞれ回転行列である場合、$d(R, S) = 4(1 - \cos \alpha)$、ただし$\alpha$は$R$と$S$の相対角度であり、相対角度が小さいほど$0$に近づくような距離関数である。

 次に式$(1)$を次のように整理する。 コーダル距離は行列積のTrace(対角和)で表すことができる。 \[ ||R_i \tilde{R}_{ij} - R_J||_F^2 = \mathrm{Tr}(R_i\tilde{R}_{ij}R_j^T) \]

 また、枝$ij$が存在する時$a_{ij}=1$、そうでない時は$a_{ij}=0$と定め、$ij$ブロック目を$a_{ij} R_{ij}$としたサイズが$3n \times 3n$の行列$\tilde{R}$を用意する。また$n$個の回転行列を並べたサイズ$3 \times n$の行列$R = \left [ R_1 R_2 \ldots R_n \right]$を用意する。

 最後に、回転行列が行列式が$1$を持つという制約を除く(集合は$O(3)^n$)。この場合、直交行列が行列式が$1$を持つ集合と$-1$を持つ集合と2つの集合に分割され、元の問題の極小解は新しい問題の極小解になっている保障がある。解を得た後に行列式の値が$-1$であれば反転させれば良い。これらによって、式(1)は次のように整理される。これを主問題とする。

\[ \min -\mathrm{tr}(R \tilde{R} R^T) \]

\[ s.t. \quad R \in O(3)^n \]

次に、この問題のラグランジュ未定乗数法を考える。

\[ L(R, \Lambda) = -\mathrm{tr}(R \tilde{R} R^T) - \mathrm{tr}(\Lambda (I - R^T R)) \]

\[ = \mathrm{tr}(R(\Lambda - \tilde{R}) R^T) - \mathrm{tr}(\Lambda) \quad (2) \]

ここで、$\Lambda$は制約$R \in O(3)^n$に対応するラグランジュ乗数であり$3 \times 3$のブロック行列が対角に並んでいるサイズが$3n \times 3n$のブロック対角行列である。この極値条件を調べるため、$L(R, \Lambda)$を$R$について微分をとり$0$となる条件を求めると

\[ (\Lambda^* - \tilde{R}) R^{*T} = 0 \quad (3) \]

が得られる。この式を変形し、$\tilde{R}$の定義も踏まえると、最適値$\Lambda^*$は次のような形をとる。

\[ \Lambda_i^* = \sum_{j \neq i} a_{ij}\tilde{R}_{ij}R_j^{*T} R_i^* \]

 このラグランジュ未定乗数法を元に次の双対問題を考える。

\[ \max_{\Lambda} \min_{R} L(R, \Lambda) \]

$\min_R L(R, \Lambda)$は$(2)$から、$\Lambda - \tilde{R} \succeq 0$の時、$- \mathrm{tr}(\Lambda)$、そうで無い場合は$-\infty$をとる($A\succeq 0$は$A$が半正定値行列であると定義)。ここで、$\Lambda^*(I - R^T R) = 0$であることと、$(3)$から

\[ - \mathrm{tr}(\Lambda^*) = - \mathrm{tr}(\Lambda^* R^{*T}R^*) = -\mathrm{tr}(R^* \tilde{R} R^{*T}) \]

が成り立つ。つまり、$\Lambda^* - R \succeq 0$が成り立つ時、双対問題と主問題の解にギャップが無い強双対性が成り立ち、双対問題の最適解が主問題の最適解を与えることがわかる。

 この$\Lambda^* - R \succeq 0$が成り立つ条件も解析的に求めることができ、$\tilde{R}$が真の値と大きくずれていない場合に達成される2-3)。例えばグラフが完全グラフであれば、それぞれが42.9度以下の誤差であれば成り立つことが示される。

 この条件は観測ノイズとしては十分許容できるようにみえるが、実際は相対回転姿勢は別の推定手法(対応点検出など)を使って推定するため大きく間違えてしまう場合も多い。この保障については最後に述べる。

双対問題をどのように解くのか

 この双対問題は主問題とは違って任意の初期値から最適解が得られる保障がある半正定値凸最適化問題であり、内点法などを使って解けるが入力点数に対しスケールしない。そこで、再度、この双対問題を最適化問題としてみた場合の双対問題を考え、その上で最適化問題解くことを考える。

\[ \min _Y -\mathrm{tr}(\tilde{R}Y) \quad (4) \]

\[ s.t. Y_{ii} = I_3, Y \succeq 0 \]

ここで行列$Y$は$3n\times3n$の行列であり、最適解は主問題の最適解と一致することが示せる。この問題は小さいブロック毎に半正定値計画問題を解析的に解くブロック座標降下法を使って解くことができる。内点法より速いものの、計算量は入力数の2乗に比例してしまう問題があった。

 今年に入って提案された回転座標降下法3)はこの最適化変数を$Y=QQ^T$と分解された形で表現した上で$(4)$を解く。$Y$は最適値のみ$Y^*= Q^* Q^{*T}$という行列分解が存在でき、他は分解できる保障がないが、最適化途中では常にこのような分解が可能であることを示し、$Q$上で最適化を行う。さらに、最適化の途中で$Q$の行列式が$-1$であれば$1$に変換することで現在の回転候補として使うことも可能であり、局所的な情報を使った最適化などを行うことも可能である。このように更新することで、計算量を入力に対して線形に減らし、数十倍という劇的な高速化を達成することができる。

検証可能な幾何認識

 近年このRotation Averaging以外にも、幾何認識タスクで認識が成功しているかどうかを検証できる手法が多く登場してきている(例えば文献5))。これによってSLAMやSfMなどの復元に使え、ミッションクリティカルなタスクで認識が失敗していることを検知できるようになってくる。今後、高速、高精度かつ高信頼な認識技術が発展してくると考えられる。

本記事はロボットとAI技術の専門誌『日経Robotics』のデジタル版です
本記事はロボットとAI技術の専門誌『日経Robotics』のデジタル版です
1)R. Hartley,“Rotation Averaging,” International Journal of Computer Vision, vol.103, no.3, pp.267-305, 2013.
2)A. Eriksson et al.,“Rotation Averaging and Strong Duality,” CVPR 2018, https://openaccess.thecvf.com/content_cvpr_2018/CameraReady/0984.pdf
3)A. Eriksson et al.,“Rotation Averaging with the Chordal Distance: Global Minimizers and Strong Duality,” IEEE Transactions on Pattern Analysis and Machine Intelligence,vol.43, issue 1, pp.256-268.
4)A. Parra et al.,“Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging,” CVPR 2021, https://arxiv.org/abs/2103.08292
5)H. Yang et al.,“One ring to rule them all: Certifiably robust geometric perception with outliers,” NeurIPS 2020, https://papers.nips.cc/paper/
岡野原 大輔(おかのはら・だいすけ)
Preferred Networks 代表取締役 最高執行責任者
岡野原 大輔(おかのはら・だいすけ) 2006年にPreferred Infrastructureを共同創業。2010年、東京大学大学院博士課程修了。博士(情報理工学)。未踏ソフト創造事業スーパークリエータ認定。東京大学総長賞。