Reconstruction of Large Scale 3D Models from Images

In this thesis, we focus on methods for automatic reconstruction of large 3D scenes directly from images. In the literature, methods solving this problem are referred to as multi-view stereo (MVS) algorithms, and they are a very interesting alternative to the acquisition of geometry with laser scanners, as the equipment - digital cameras - is not expensive. As the MVS reconstruction is a well-researched topic, current efforts are shifted towards a large scale reconstruction. City models require millions of images to capture their geometry. Processing such amounts of data requires a lot of computa- tional effort, even for current super-computers. Exploiting parallelization is often not sufficient, as it leads only to a linear improvement in computational complexity. This effort can be reduced, as described in this thesis, not only by using parallelization, but also with a smart algorithmic approach. The need of quality evaluation for MVS algorithms and a large number of different approaches has led researchers to establish a ranking [SCD+ 06]. The most promising approaches are from the year 2009, and recently two new publications were released in 2011, which shows a loss of interest in improving the quality, as there is not much improvement to achieve. It can be clearly seen, that the focus of research in this area has shifted to the application of current methods to large data sets. In this thesis, we present a new approach to the large scale reconstruction problem. The general outline of this approach is as follows: First we gather data as video or image sequences. We extract image features and build compact descriptors for each sequence. We calibrate cameras for each sequence to obtain camera parameters and sparse 3D point clouds. With our compact descriptors, we compute a similarity graph, where each node is a sequence, and edges are joining sequences representing scenes with overlapping geometry. The next step is to compute transformation matrices be- tween sparse 3D point clouds obtained during the camera calibration process. We com- pute transformations of sub-models to a global coordinate system. We perform a large scale bundle adjustment to improve camera matrices, 3D points, and transformation matrices. For each image sequence, we compute a dense point cloud with traditional MVS methods. Using the matrices, we bring dense sub-models to a global coordinate system, to obtain a final large model. As it can be seen, the most time consuming steps of the algorithm can be performed in parallel. However, there are certain steps of our approach, that do not parallelize in an easy, natural way. These are the similarity graph construction, and the large scale bundle adjustment. Thanks to our compact descriptor and our large scale bundle adjustment algorithm these steps can be performed on a single PC. One of the big advantages of our approach is a possibility of incremental model construction. The data does not need to be available at the beginning of the process, and the quality of the global model will be refined as more data will become available.In dieser Arbeit konzentrieren wir uns auf Methoden zur automatischen Rekonstruktion großer 3D-Szenen basierend auf Bildern. In der Literatur werden Lösungsmethoden dieses Problems als Multi-View Stereo (MVS) Algorithmen bezeichnet, und stellen eine sehr interessante Alternative zum Erwerb von Geometriedaten mittels Laserscanner dar, nachdem die dafür notwendige Ausrüstung - Digitalkameras - wesentlich preiswerter ist. Die Grundlagen von Multi-View Stereo Algorithmen sind Gegenstand zahlreicher wissenschaftlicher Arbeiten und demnach gut erforscht, weshalb sich derzeitige Bemühungen in Richtung Verarbeitung großer Datenmengen verschoben haben. Realistische Modelle von Städten erfordern je nach Größe zur Erfassung ihrer Geometrie Millionen von Bildern. Die Verarbeitung solcher enormen Mengen an Daten erfordert viel Rechenleistung und führt selbst High Performance Computer teilweise an ihre Grenzen. Selbst der Einsatz von Techniken zur Parallelisierung ist oft nicht ausreichend, da sie in den meisten Fällen nur zu einer linearen Verbesserung des Rechenaufwandes führen. Ziel dieser Arbeit ist es, zu zeigen, dass dieser Aufwand nicht nur durch Parallelisierung, sondern auch durch den Einsatz von intelligenteren algorithmischen Ansätzen reduziert werden kann. Die Notwendigkeit einer qualitativen Bewertung von MVS Algorithmen und die Vielzahl verschiedener Ansätze und deren algorithmische Umsetzungen führten dazu, dass Forscher ein Ranking etablierten \cite{Seitz:2006:CEM:1153170.1153518}. Die vielversprechendsten Ansätze datieren aus dem Jahre 2009, jedoch zeigen neuere Veröffentlichungen (2011) in diesem Ranking eindeutig einen Trend hin zur Verarbeitung großer Datensätze bei gleichbleibender Qualität der Rekonstruktionen. Generell ist deutlich zu erkennen, dass sich der Schwerpunkt der Forschung in diesem Bereich in Richtung Adaptierung bekannter Methoden auf große Datenmengen verschoben hat. In dieser Arbeit präsentieren wir einen neuen Ansatz für die Rekonstruktion von Geometrie basierend auf Bilddaten. Die Grundzüge dieses Ansatzes sind wie folgt: Zuerst werden die Daten aus Video- oder Bildersequenzen gewonnen, um anschließend aus jeder einzelnen Sequenz Bildmerkmale zu extrahieren und kompakte Deskriptoren zu generieren. Mittels einer Kalibrierung der Kameras werden für jede Sequenz Kamera Parameter und erste dünn besetzte Punktwolken errechnet. Mit den zuvor generierten kompakten Deskriptoren, berechnen wir einen ähnlichkeitsgraphen, wobei jeder Knoten innerhalb dieses Graphen eine Sequenz darstellt und die Kanten Verbindungssequenzen mit überlappender Geometrie kennzeichnen. Im nächsten Schritt werden die Transformationsmatrizen der zuvor einzeln während der Kamerakalibrierung generierten 3D-Punktwolken zu einem globalen Koordinatensystem berechnet. Im darauf folgenden Schritt wird zur Verbesserung der bereits berechneten Kamera Parameter, 3D Punkte und der Transformationsmatrizen ein umfassender Bündel-Ausgleich durchgeführt. Abschließend werden dichte Punktwolken anhand traditioneller MVS Methoden erstellt und mittels der optimierten Transformationsmatrizen zu einem Gesamtmodell in einem globalen Koordinatensystem zusammengefügt. Wir werden zeigen, dass die zeitintensivsten Berechnungsschritte unseres Algorithmus parallel ausgeführt werden können. Jedoch gibt es auch Schritte in dem vorgestellten Ansatz, welche nicht auf einfache und natürliche Art und Weise zu parallelisieren sind. Als Beispiele für derartige Schritte wären hier die Konstruktion des ähnlichkeitsgraphen und der hochdimensionale Bündel-Ausgleich zu nennen