Bundlerのアルゴリズムを追ってみる 概要編

画像処理

Structure from Motionで多分一番有名なOSSである、Bundlerの処理を追ってみます。
何回かに記事を分けて解説していくつもりなので、途中で力尽きたらごめんなさい。。。

Bundlerの公式サイトはこちらです。

Bundler: Structure from Motion (SfM) for Unordered Image Collections

最新版はv0.4になっていますが、Githubのコミット履歴を見た感じ、今でも細々と有志による更新が行われているみたいですね。
v1.0が出ることは永遠になさそうw

 

公式サイトによるとBundlerの基になった論文は2本あるみたいです。SIGGRAPH 2006とIJCV2007の論文なので、おそらくSIGGRAPH で発表した内容をIJCVで詳細にジャーナル論文にまとめた感じだと思います。
IJCVの論文はこちらです。

Snavely, Noah, Steven M. Seitz, and Richard Szeliski. “Modeling the world from internet photo collections.” International journal of computer vision 80.2 (2008): 189-210.

この論文をベースに、論文に乗っていない細かなところはコードを見ながら、Bundlerの流れを追っていきたいと思います。

 

Bundlerの大まかな流れ

Bundlerの大まかな流れは一般的なSfMと変わりません。というか、Bundlerの論文に技術的な新規性はほとんどありません。
この論文のすごいところは既存の技術を組み合わせて、時系列順でもない大規模な画像に対してSfMを成功させたところだと僕は思っています。

1.各画像間の特徴点マッチング

まずは何はともあれ各画像間で特徴点をします。BundlerではSIFTを使って対応点を求めています。
ただ、如何に精度の良い特徴量でも、単純な特徴点マッチングではどうしても誤対応が含まれてしまいます。

Bundlerでは、この誤対応を

  1. 特徴点空間上の距離を使った除去
  2. エピポーラ幾何を使った除去
  3. 特徴点追跡による除去

の3つの方法を使って排除しています。

2.1組の画像間で3次元復元

Bundlerは初めに2枚の画像で3次元復元を行い、徐々に画像を追加して復元結果を大きくしていく、といった手法をとっています。
この手の手法の最終的な復元精度は、最初の2枚の復元精度によって決まるといっても過言ではないので、最初の2枚の選び方がものすごく重要です。これがすべてといってもいいほどです。

Bundlerでは最初の2画像の理想的な関係として、

  1. 2画像間の対応点が多い
  2. 2枚の画像の撮影位置が離れている

の2つを挙げ、モホグラフィ変換を利用してこの2つの条件を満たす2画像を探す方法を説明しています。

その後、5-point algorithmとTriangulationとかを使って、選ばれた最初の2画像の3次元復元をしています。

3.画像を1枚追加して3次元復元

最初の2画像で3次元復元ができたら、新しく画像を1枚ずつ追加して、復元結果を大きくしていきます。

順番としては、

3次元座標が既知の特徴点が多い画像

から追加していきます。

追加する画像は特徴点とその3次元座標がわかっているので、DLT法を使って内部パラメータ、外部パラメータを求めているみたいです。
そして、Triangulationでまだ3次元座標が求まっていなかった特徴点の3次元座標を計算しています。

最後に、バンドル調整で各画像のパラメータと3次元点を最適化してやってます。

これを、追加する画像がなくなるまで続けてるみたいです。

 

 

以上が、Bundlerのおおよその流れになります。
記事にしてみると意外と実装できちゃいそうな気がしますが、実際は精度を高めるためのテクニックが至る所に使われてるっぽくて、なかなか骨が折れそうです。

次回から頑張って詳細な流れを解読していきたいと思います。

 

Bundlerについての解説記事一覧はこちら

Bundlerのアルゴリズムを追ってみる 概要編

Bundlerのアルゴリズムを追ってみる 特徴点マッチング編 その1

Bundlerのアルゴリズムを追ってみる 特徴点マッチング編 その2

Bundlerのアルゴリズムを追ってみる 特徴点マッチング編 その3

コメント

  1. […] Bundlerのアルゴリズムを追ってみる 概要編 […]

  2. […] Bundlerのアルゴリズムを追ってみる 概要編 […]

  3. […] Bundlerのアルゴリズムを追ってみる 概要編 […]

%d人のブロガーが「いいね」をつけました。