Structure from Motionで多分一番有名なOSSである、Bundlerの処理を追ってみます。
何回かに記事を分けて解説していくつもりなので、途中で力尽きたらごめんなさい。。。
Bundlerの公式サイトはこちらです。
Bundler: Structure from Motion (SfM) for Unordered Image Collections
最新版はv0.4になっていますが、Githubのコミット履歴を見た感じ、今でも細々と有志による更新が行われているみたいですね。
v1.0が出ることは永遠になさそうw
公式サイトによるとBundlerの基になった論文は２本あるみたいです。SIGGRAPH 2006とIJCV2007の論文なので、おそらくSIGGRAPH で発表した内容をIJCVで詳細にジャーナル論文にまとめた感じだと思います。
IJCVの論文はこちらです。
この論文をベースに、論文に乗っていない細かなところはコードを見ながら、Bundlerの流れを追っていきたいと思います。
Bundlerの大まかな流れ
Bundlerの大まかな流れは一般的なSfMと変わりません。というか、Bundlerの論文に技術的な新規性はほとんどありません。
この論文のすごいところは既存の技術を組み合わせて、時系列順でもない大規模な画像に対してSfMを成功させたところだと僕は思っています。
１．各画像間の特徴点マッチング
まずは何はともあれ各画像間で特徴点をします。BundlerではSIFTを使って対応点を求めています。
ただ、如何に精度の良い特徴量でも、単純な特徴点マッチングではどうしても誤対応が含まれてしまいます。
Bundlerでは、この誤対応を
- 特徴点空間上の距離を使った除去
- エピポーラ幾何を使った除去
- 特徴点追跡による除去
の3つの方法を使って排除しています。
２．１組の画像間で３次元復元
Bundlerは初めに２枚の画像で３次元復元を行い、徐々に画像を追加して復元結果を大きくしていく、といった手法をとっています。
この手の手法の最終的な復元精度は、最初の２枚の復元精度によって決まるといっても過言ではないので、最初の２枚の選び方がものすごく重要です。これがすべてといってもいいほどです。
Bundlerでは最初の２画像の理想的な関係として、
- ２画像間の対応点が多い
- ２枚の画像の撮影位置が離れている
の２つを挙げ、モホグラフィ変換を利用してこの２つの条件を満たす２画像を探す方法を説明しています。
その後、5-point algorithmとTriangulationとかを使って、選ばれた最初の２画像の３次元復元をしています。
３．画像を１枚追加して３次元復元
最初の２画像で３次元復元ができたら、新しく画像を１枚ずつ追加して、復元結果を大きくしていきます。
順番としては、
３次元座標が既知の特徴点が多い画像
から追加していきます。
追加する画像は特徴点とその３次元座標がわかっているので、DLT法を使って内部パラメータ、外部パラメータを求めているみたいです。
そして、Triangulationでまだ３次元座標が求まっていなかった特徴点の３次元座標を計算しています。
最後に、バンドル調整で各画像のパラメータと３次元点を最適化してやってます。
これを、追加する画像がなくなるまで続けてるみたいです。
以上が、Bundlerのおおよその流れになります。
記事にしてみると意外と実装できちゃいそうな気がしますが、実際は精度を高めるためのテクニックが至る所に使われてるっぽくて、なかなか骨が折れそうです。
次回から頑張って詳細な流れを解読していきたいと思います。
Bundlerについての解説記事一覧はこちら
Bundlerのアルゴリズムを追ってみる 特徴点マッチング編 その1
コメント