Structure from Motion(SfM)のオープンソース、Bundlerのアルゴリズムを追ってみます。
今回は、特徴点マッチングと、特徴点空間上の距離を使った誤対応の除去について解説してみます。
特徴点マッチング
Bundlerでは、SIFT使って特徴点検出をしています。
で、各画像間で特徴点マッチングをするわけですが、後の処理のため各特徴点に対して最も距離の小さい(似ている)特徴点だけでなく、2番目に距離の小さい特徴点も計算してやります。
ここでいう距離とは、特徴点空間上の距離のことです。
SIFTの特徴量は128次元ベクトルなので、この場合128次元空間の2点間の距離のことです。
ただ、各画像数百とか数千の特徴点があるはずなので、各画像間ですべての特徴点に対して似ている特徴点を全探索してやると、とんでもない計算量になってしまいます。
そこで、Bundlerでは最近傍探索(Nearest neighbor search: NNS)で全探索してやるのではなく、近似最近傍探索(Approximate nearest neighbor: ANN)を使って計算量を減らしています。
ANNは最も距離が小さいと思われる特徴点を高速に見つけ出す手法です。NNSでは全探索で確実に最も距離の小さい特徴点を見つけますが、ANNではおそらく最も距離の小さいであろう特徴点を見つけます。そのため、実は距離が最も小さくないこともありますが、その代わりにNNSに比べて非常に高速化されています。
ちなみに、OpenCVではcv::FlannBasedMatcherという関数でANNを使った特徴点マッチングができます。
余談ですが、Bundlerのソースコード読んだ感じ、特徴点のクロスチェックしていないっぽいです。。。
論文を読んだ感じ、Bundlerは特徴点の誤対応除去にめちゃくちゃ神経を使っているイメージだったので、ちょっと意外です。なにか理由があるんでしょうか？
(知っている人がいたら教えてください。)
特徴点空間上の距離を使った誤対応の除去
さて、ただ特徴点マッチングしただけでは、どうしても誤った特徴点の対応付けが残ってしまいます。
そこでBundlerでは、最も距離の小さい特徴点と2番目に距離の小さい特徴点を使って、誤対応を除去してやります。
まずはこちらの図をご覧ください。
この場合、最も似ている特徴点は明らかですね。
ではこちらはどうでしょう？
どっちの方が距離が小さいか、ぱっと見わからなくないですか？
そりゃ、距離を計算してみれば明らかになるわけですが、極論距離が1.00000と1.00001だと、本当に1.00000の方が正しい対応点かどうか自信がなくなってしまいますよね。
そこでBundlerでは、前者の図のように、最も似ている特徴点が明らかな点以外は削除してやります。
具体的には、この式を満たす特徴点マッチング以外は削除してやります。
$$\frac{最も似ている特徴点との距離}{２番目に似ている特徴点との距離}<0.6$$
0.6は閾値ですね。後者の図のような距離の差が少ないようなケースだと、左辺が1.0に近づくためその特徴点マッチングは削除されます。
次回は、エピポーラ幾何を使ってさらに誤対応を削除する方法について解説します。
Bundlerについての解説記事一覧はこちら
Bundlerのアルゴリズムを追ってみる 特徴点マッチング編 その1
コメント