Web上の膨大な写真からローマを1日で構築する方法

前回、『写真に基づく3D空間構築手法の到達点』としてバラバラの写真から3D空間を構築する手法について取り上げた。コメントで言及された人もおられたが、MicrosoftはPhotosynthとして、同様にStructure-from-Motion (SfM)を用いて写真をつなぎ合わせ、インタラクティブにブラウズできるPhotosynthを公開している。

現在、研究レベルではWeb上にアップされた不特定多数のユーザによる膨大な写真から街一つを再現するプロジェクトが推進されている。その名も"Building Rome in a Day"（ローマを一日にして成す）だ。下の動画はFlickr検索された画像から生成された3Dモデルを示している。本エントリでは、論文*1に基づき、その構築手法の概要を紹介する。本エントリ中の動画像は論文及びプロジェクトページからの引用である。

【告知】Twitterはじめました。@LunarModule7です。
興味のあるかたはフォローくださいとしばらく宣伝。

ネット上には多くのユーザが撮影した写真が無数にアップされている。たとえば、Flickrにおいて"Rome"と検索すると200万枚以上の写真がヒットする。数百、数千の視点から撮影された千差万別の写真がアップされており、たとえば有名な観光スポットであるトレビの泉単体だけ数えても検索結果は5万枚に上る。

本研究のシステムでは、これらの写真にStructure-from-Motion (SfM)を適用し、被写体のオブジェクトやシーンの形状、及びカメラの動きを復元し、街全体を構築している。本研究では、1日以内に15万枚に及ぶ画像を処理しているが、これは他の先行研究に比べて1桁ないし2桁大きい値だ。

先行研究では、厳密にキャリブレーションされたカメラで撮影され、GPSや慣性航法ユニットのデータが付与された写真を利用する事によって、解析処理を単純化している。しかし、Webから収集した写真は、多様なカメラにより撮影され、照明条件もバラバラで、地理情報は付与されていないか極めて限られている。そして多くの場合、カメラキャリブレーション情報も手に入らない。このような雑多なデータに対してSfMを適用することは難しいチャレンジとなる。また、膨大なデータを扱うためには最大限処理を並列化させる必要がある。

前処理・特徴抽出

処理対象となる画像は中央ノードから各分散ノードに処理能力に応じて配分される。中央ファイルサーバが必要になるのは全てのプロセスにおいてこの時点だけである。各分散ノードにおいて、画像の可読性チェック、EXIFタグ抽出、（もし記録されていれば）焦点距離値抽出、200万画素以上の画像の縮小処理が成される。そして、SIFT(Scale-Invariant Feature Transform)特徴量*2の抽出が行われる。SIFTは画像の回転、拡縮、照明条件等に頑強な特徴量であり、画像のマッチングやオブジェクト認識等に広く利用されるアルゴリズムである。

画像マッチング

SIFT特徴量のマッチングにはANN library*3が利用できるが、こうしたマッチングと検証を100,000画像の5,000,000,000ペアに対して適用しようとすると、500コアのCPUをフルに使っても11.5日かかる計算になる。また、"Rome"と言うような広いタグが付与される写真は実際はほとんど相互に関連しない。そこでマッチング処理を効率に行うために、本研究では多段階のパイプライン処理を実装している。次の図はその概要を示したものだ。

N枚の画像がM個の分散処理ノードに配付され、次の順序で処理される。例によって詳細は元論文を参照されたい。

SIFT特徴量の抽出を行い、k-means treeに格納して量子化する。検索で一般的に利用されるTFIDF法を利用するために、各画像の全ての特徴量に対しTF(term frequency)のカウントを行う。
全ての特徴量に対しそれを有する画像、DF(document frequency)をカウントする。
各ノードでTFIDF行列の計算を行い、その結果を全ノードにブロードキャストする。
他ノードの結果に基づき、各ノードで並列してTFIDFベクトル行列の積を計算する。
TFベースの近傍検索により、それぞれの画像に対して類似度が最も高くなる上位k₁+k₂の候補画像を導出する。
次に候補画像の検証を行うために、各ノードに必要な画像を移動させる。画像が全て単一のノードに集まっているのなら話は単純だが、画像は各ノードに分散されているので工夫する必要があるが、計算量と効果との兼ね合いから、結局シンプルなgreedy bin-packingアルゴリズムによって、センターノードが上位k₁の画像を優先的に各ノードに検証画像を割り当てている。
各ノードにおけるSIFT特徴量の光度マッチングに加え、カメラキャリブレーション情報が利用できる場合には基本行列(essential matrix)/基礎行列(fundamental matrix)の推定を行う。ここでの推定結果は後の幾何学的推定プロセスにおいて利用される。
ここでは、画像間の特徴量のマッチングを表したmatch graphを用いる。match graphでは、2つの画像間にマッチする特徴量が存在すればその画像間がエッジで繋がれる。画像に基づく再構築を行うために、match graphからなるべく多くの関連画像を結合させた結合コンポーネント(CC)を抽出する事を考える。そこで、CCのマージを行うために、各画像に対して次位k₂の画像を確認し、2つのCCにまたがることが確認されれば、その画像を組み入れてその2つのCCを連結させる。こうしてCCはどんどんマージされていく。
得られたmatch graphをより充実させるためにクエリ拡張(query expansion)として知られる検索手法を利用する。クエリ拡張は初期キーワードによって得られた検索結果に基づいた再検索によって、より良い検索結果を得ようとするアプローチだ。match graphにおいてAがB、BがCにマッチしているならば、AがCにマッチするかどうか確認する事で、画像間の結合度を密にしていく。
再度、画像間のマッチング確認を行う。
このクエリ拡張、マッチング確認処理を4回繰り返す。次の図はmatch graphがCCのマージ、4回のクエリ拡張によって拡張されている様子を示している。match graphの密度が大きく向上している事が分かるだろう。一番右のskeltal setは最終match graphの骨組みのみを示したものだ（後述）。

トラック生成

最終段階では全てのマッチング情報対から画像間で一貫性のあるトラックを生成する事である。マッチング情報は各ノードに分散して配置されているので、このプロセスは2段階に分けて行われる（パイプライン図の(k)〜(m)）。まず各ノードでローカルに利用可能な情報だけを用いてトラックが生成される。データはマスターノードに集められて、全てのノードにブロードキャストされる。各CCのトラックは独立して計算され、統合時に矛盾箇所の整理が行われる。

トラックが生成されると特徴点の2D座標を抽出すると共に、後に3Dレンダリングに利用するための特徴点のピクセルカラーを抽出する。これらは各CCごとに並列して処理され、センターノードに集められて、ブロードキャストされる。

幾何学的推定

トラックが生成されれば、各CCに対しStructure-from-Motion (SfM)を適用してカメラ位置と3D座標の特定を行う。効率的に計算を行うために、まずskeltal set抽出手法*4を用いて骨組みを抽出し、それに対してSfMを適用、ベースモデルを構築後、残りの画像を追加していくと言うアプローチをとる。

適用結果

ローマ(Rome)

Flickrにおいて"Rome"もしくは"Roma"タグが付けられた150,000枚の写真をデータセットとして利用している。496コアでマッチングと再構成に21時間かかっている。マッチングの結果、画像はローマの有名なランドマークに対応するいくつかのグループに分類されている。コロッセオ(Colosseum)、サン・ピエトロ寺院(St. Peter's Basilica)、トレビの泉(Building Rome in a Day)、パンテオン(Pantheon)などを見つける事ができる。コミュニティの写真コレクションを使う事の利点の一つは非常に多様な視点からの写真を利用する事ができる点だ。


Colosseum: 2,097 images, 819,242 points		Trevi Fountain: 1,935 images, 1,055,153 points



Pantheon: 1,032 images, 530,076 points		Hall of Maps: 275 images, 230,182 points

ヴェネツィア(Venice)

ヴェネツィアのデータセットはこれまでの中で最も大きいものである。496コアでマッチングに27時間、3D再構築に38時間かかっている。大運河(Grand Canal)、サンマルコ広場(San Marco square)、ドゥカーレ宮殿(Doge's Palace)の3つの大きなコンポーネントが生成されている。サンマルコ広場は現時点で最も大きな再構成モデルであり、14,000枚の画像と450万以上の3Dポイントから構成されている。



San Marco Square: 13,699 images, 4,515,157 points


Grand Canal: 3,272 images, 561,389 points

ドゥブロブニク(Dubrovnik)

実験時においてFlickrには世界遺産でもあるドゥブロブニクの写真が僅か58,000枚しか無かった。それでもこの街全体を再現する事に成功している。マッチングは352コアで僅か5時間で完了し、最大かつ最も興味深いコンポーネントは古い町全体を包括している。再構成時間は17.5時間とローマのケースに比べて長くかかっている。これはデータセットがどのように構成されているかに依存している。ローマの場合データセットは基本的に巨大でシンプルなランドマークに集中していたが、ドゥブロブニクの場合は複雑な路地等を含む街全体を包括するように分散していたからだ。次に4視点からの写真と生成された対応する画像を示す。街全体をストリート上も屋根の上からも再現していることに注目して欲しい。再現モデルは4,585枚の画像と11,839,682個の特徴を有する2,662,981の3Dポイントから構成されている。




The old city of Dubrovnik, 4,619 images, 3,485,717 points

処理時間

次に上記の3つのデータセットに対する処理時間を示す。数十万枚に上るデータセットに基づく3Dモデルの再構築が数日のオーダーで完成している事が分かる。

						Time (hrs)
Data set	Images	Cores	Registered	Pairs verified	Pairs found	Matching	Skeletal sets	Reconstruction
Rome	150,000	496	36,658	8,825,256	2,712,301	13	1	7
Venice	250,000	496	47,925	35,465,029	6,119,207	27	21.5	16.5
Dubrovnik	57,845	352	11,868	2,658,264	498,982	5	1	16.5

まとめ

以上に紹介したように、Flickrに代表される写真共有サービスに、世界中の様々な人が、自分たちのカメラで撮影した、撮影日時も、季節も、天候も、場所も、カメラ位置も、方向も、カメラも、レンズ性能も、照明効果も異なる全くバラバラな写真から、数日で街全体を再構築する事が可能になりつつある。

今はまだ何となく街の形が分かる程度だが、アップされるメディアの質・量が増加し、手法が洗練され、利用できるコンピューティングパワーが増加すれば、よりリアルな3Dモデルを構築する事ができるようになるだろう。かけがえのない一瞬を留め置くカメラが発明されてから2世紀──そして今や、その一瞬を再構築し追体験できる段階に進みつつあるのだ。