SfMとかSLAMの3D系の研究を始めると、必ず出てくるのがバンドル調整(Bundle Adjustment)です。ぶっちゃけただの非線形の最小二乗法なんですけど、今回はこのバンドル調整について解説します。
バンドル調整、またはバンドル調整法とはずばり
「内部パラメータ、外部パラメータ、世界座標点群を最適化する非線形最小二乗法」
です。
まぁ、この説明で理解できる人はそもそもこの記事なんか見ないと思いますので、もう少し説明してみます。
バンドル調整の考え方
まず、SIFTとかSURFとかを使って、画像から検出した特徴点があるとします。
そして、内部パラメータと外部パラメータ、抽出した特徴点の世界座標点が推定できているとします。この推定したパラメータを使って、世界座標点を画像座標点へ透視投影変換をしてみましょう。
この変換した画像座標点、理想的には画像から抽出した特徴点とピッタリ合わないといけないんですが、様々なノイズの影響でそう上手くはいかないんですよね。。。
ちなみに、この２つの点の距離のことを「再投影誤差」といいます。
(もしピッタリ合っちゃったら、バンドル調整は不必要になりますw)
すなわち！ピッタリと合うようなパラメータ、世界座標点を見つけることができれば、それが正しい推定結果だろう、という考え方がバンドル調整です。
バンドル調整では、内部、外部パラメータと世界座標点をちょっとずつちょっとずつ微調整してやって、ピッタリと合うように調整してやります。
数式で表すとこうなりますね
\(\boldsymbol{A}\)は内部パラメータ、\(\boldsymbol{R}\)は回転行列、\(\boldsymbol{t}\)は並進ベクトル、そして\(\boldsymbol{X_w}\)(ベクトル)は世界座標点です。こいつらを微調整していくわけですね。
なぜこの式になるかわからない人は、こちらの記事を一度読んでみてください。
実際には特徴点は複数あって、ついでに画像も複数枚あるのが普通なので、すべてをピッタリ合わせるのは現実的には不可能です。
そこで、特徴点と透視投影変換した画像座標点の距離の和が、全体で最小になるように内部、外部パラメータと世界座標点の座標を調整します。
数式で表すとこうなります。
\(n\)が画像の枚数、\(m\)は世界座標点数です。
\(I_{ij}\)は\(i\)番目の世界座標点が\(j\)番目の画像に写っていれば1、写っていなければ0になる関数です。全部の世界座標点が全部の画像に移るわけじゃないですからね！
この式を頑張って偏微分して、レーベンマーク・マーカート法とか使って最小化してやれば、再投影誤差の和が一番小さい、一番それっぽい内部、外部パラメータと世界座標点を得ることができちゃうわけです。
(この記事で紹介した式は理解しやすさを第一に置いているので、この式が実際の研究で使われることはほぼないです。なのでこの式を頑張って偏微分しちゃわないようにしましょうw)
バンドル調整は内部パラメータも最適化すべきなのか
バンドル調整において、外部パラメータと世界座標点群は必ずと言っていいほど最適化するのですが、内部パラメータは最適化したりしなかったりします。
SLAMとかだとあらかじめ内部パラメータをキャリブレーションしておくことがほとんどなので、内部パラメータは最適化するパラメータには含めません。
bundlerやVisualSfMのようなネットから集めた画像を対象にしたSfMだと含めることが多いです。
最適化するパラメータは多いほど意図しない局所解に落ちやすくなるので、それなりの精度で内部パラメータがわかっているならば、含めない方が個人的には無難だと思います。
(昔私が実装したSfMでは、見事に局所解にハマって一部の実験データで焦点距離がマイナスになったことがありますw)
より詳しく知りたいなら
より深くバンドル調整を理解したい人は、こちらの論文がおすすめです。内容は少々難しめな気がしますが、日本語でバンドル調整を解説した論文としては一番しっかりしていると思います。
岩元祐輝, 菅谷保之, 金谷健一. “3 次元復元のためのバンドル調整の実装と評価.” コンピュータビジョンとイメージメディア (CVIM) 2011.19 (2011): 1-8.
早くバンドル調整を使いたいなら
いやいや、この記事に書いてることは理解できたから、とにかく使いたい！！っていうせっかちな人は、このライブラリがおすすめです。
非線形最小二乗問題を扱うときに非常に面倒な評価関数の微分を内部で自動でやってくれるので、実質評価関数を突っ込むだけで最適化問題を解いてくれます。
バンドル調整のサンプルコードもあるので、お手軽に試せます。かなり複雑な評価関数でも扱えてしまうので、バンドル調整に限らずいろんな場面で役に立ってくれるはず！
WindowsでのこのCeres Solverのビルド方法を記事にしてまとめてあるので、よければ参考にしてください。
Ceres Solverの注意事項としては、ライブラリ内部でやってるのはあくまで数値微分ということです。なので、どうしても本来の微分結果とは誤差があると思います。
ですので、ライブラリに頼らず手動で頑張って微分した方が、もしかすると精度は上がるかもしれません。
(個人的には十分な精度のライブラリだと思いますが、0.01%でも精度を追い求めたい人は頭の隅に置いておきましょう)
コメント