Algebraic, logical and stochastic reasoning for the automatic prediction of 3d building structures

Abstract

3D building models are nowadays an important prerequisite for many applications such as rescue management or navigation tasks. However, most approaches for the automatic reconstruction of buildings rely on high-resolution data that cannot always be provided due to occlusions or high cost of the acquisition of data. Instead, reasoning methods have to cope with sparse and possibly incomplete data. This thesis presents a novel reasoning approach for the prediction of building substructures in the absence of dense measurements. The developed reasoner benefits from a strong profound prior knowledge of functional dependencies and probability density distributions in a model-driven top-down approach that is legitimated by strong regularities and symmetries in man-made objects. It thereby holds the view that it is easier to verify or falsify predicted hypotheses than to reconstruct buildings bottom-up from measurements and automatically generates a small number of qualified hypotheses based only on sparse observations such as footprints. However, the mathematical model for buildings is a priori characterized by multimodal probability density functions as well as non-linear relations with both discrete and continuous parameters that in general leads to approximate stochastic inference instead of exact inference. One substantial design decision in order to use well established exact algorithms of parameter estimation is the representation of distributions by Gaussian mixtures. For efficient reasoning in hybrid models, the key idea of this thesis is to divide the problem into a combinatorial (discrete) and stochastic (continuous) part and to combine constraint logic programming with Bayesian networks. Constraint programming reduces the search space by constraint propagation and intelligent search strategies and determines the discrete parameters first. Afterwards this intermediate result is refined by stochastic inference to evaluate and determine the continuous parameters and finding the most likely hypotheses out of an a priori large hypothesis space. The method has been demonstrated to predict façade structures on the one hand. As the seemless outdoor/indoor modeling gets more and more attention the developed approach was adapted to the prediction of indoor models on the other hand. As models are a prerequisite of model-based reasoning, tools are needed that facilitate the development of redundancy-free and consistent prototyped models providing prior knowledge during model prediction. At the same time, it is useful to make implicit constraints explicit for supporting the interpretation of measurements for building reconstruction. Recognizing that the task of checking redundancy and consistency is equivalent to proving that one constraint follows from a set of premises this thesis complements the reasoning with methods of automatic theorem proving. In order to handle the increasing complexity of symbolic reasoning in the 3D space a novel approach is presented that combines algebraic and logical reasoning based on an appropriate representation of the envisaged constraint-based model using multivariate polynomials and first-order predicate logic. Algebraic reasoning is based on Wu's method of pseudodivision and characteristic sets and identifies redundancy, inconsistency and implicit knowledge. Rule-based reasoning based on logical facts and rules supports the reasoning process using known implications. The aspect of uncertainty that is inevitable in the context of geoinformation systems (GIS) is handled in the developed reasoning methods by the incorporation of probability density functions, graphical models and uncertain projective geometry.

<strong>Algebraisches, logisches und stochastisches Reasoning für die automatische Prädiktion von 3D Gebäudestrukturen</strong> <br> 3D Gebäudemodelle sind heutzutage eine wichtige Voraussetzung für viele Anwendungen wie z.B. Rettungszenarien oder Navigationsaufgaben. Die meisten Ansätze für eine automatische Rekonstruktion von Gebäuden basieren jedoch auf hochaufgelösten Daten, welche durch Verdeckungen oder hohe Kosten der Datenerhebung nicht immer zur Verfügung stehen. Stattdessen müssen Reasoning-Methoden mit dünnen und möglicherweise unvollständigen Daten umgehen. In dieser Arbeit wird ein neuer Reasoning-Ansatz für die Prädiktion von Gebäuden und ihrer Bestandteile vorgestellt, welcher ohne dichte Messungen auskommt. Der entwickelte Reasoner profitiert von einem starken Vorwissen über funktionale Abhängigkeiten und Wahrscheinlichkeitsdichteverteilungen in einem modellgetriebenen Top-Down-Ansatz, der durch starke Regelmäßigkeiten und Symmetrien in von Menschenhand geschaffenen Objekten legitimiert ist. Dabei wird die Ansicht vertreten, dass es einfacher ist, prädizierte Hypothesen zu verifizieren oder zu falsifizieren, als Gebäude "bottom-up" aus Messungen zu rekonstruieren. Das Ergebnis ist eine kleine Anzahl qualifizierter Hypothesen, welche auf nur wenigen Beobachtungen basieren. Das mathematische Modell zeichnet sich jedoch a priori durch multimodale Wahrscheinlichkeitsdichtefunktionen sowie nichtlineare Relationen von diskreten als auch kontinuierlichen Parametern aus, was im Allgemeinen zu einer approximativen stochastischen anstelle einer exakten Inferenz führt. Eine wesentliche Entwurfsentscheidung, um etablierte exakte Algorithmen der Parameterschätzung zu verwenden, ist die Repräsentation von Verteilungen durch Gaußsche Mischverteilungen. Darauf aufbauend besteht die Kernidee dieser Arbeit darin, das Problem in einen kombinatorischen und einen stochastischen Teil zu unterteilen und logische Constraintprogrammierung mit Bayes'schen Netzwerken zu kombinieren. Die Constraintprogrammierung reduziert den Suchraum und bestimmt zunächst die diskreten Parameter. Anschließend wird dieses Zwischenergebnis durch stochastische Inferenz verfeinert, um die kontinuierlichen Parameter zu bestimmen und die wahrscheinlichsten Hypothesen aus einem a priori großen Hypothesenraum zu finden. Die Methode hat sich einerseits zur Prädiktion von Fassadenstrukturen bewährt. Da die nahtlose Außen-/Innenmodellierung immer mehr Beachtung findet, wurde der entwickelte Ansatz andererseits an die Prädiktion von Innenmodellen angepasst. Für das modellbasierte Reasoning werden darüber hinaus Werkzeuge benötigt, die die Entwicklung redundanzfreier und konsistenter Prototypmodelle erleichtern. Gleichzeitig ist es nützlich, implizite Constraints explizit zu machen, um die Interpretation von Messungen für die Gebäuderekonstruktion zu unterstützen. Da die Überprüfung von Redundanz und Konsistenz gleichbedeutend ist mit dem Nachweis, dass ein Fakt aus einer Reihe von Prämissen folgt, ergänzt diese Arbeit das Reasoning mit Methoden des automatischen Theorembeweisens. Um der zunehmenden Komplexität im 3D-Raum gerecht zu werden, wird ein neuartiger Ansatz vorgestellt, der algebraisches und logisches Reasoning unter Verwendung multivariater Polynome und Prädikatenlogik kombiniert. Das algebraische Reasoning basiert auf der Methode von Wu mittels Pseudodivision und "Characteristic Sets" und identifiziert Redundanz, Inkonsistenz und implizites Wissen. Das regelbasierte Schließen mit logischen Fakten und Regeln unterstützt das Reasoning durch bekannte Implikationen. Der Aspekt der Unsicherheit, der im Zusammenhang mit Geoinformationssystemen (GIS) unvermeidlich ist, wird in dieser Arbeit durch die Verwendung von Wahrscheinlichkeitsdichtefunktionen, graphischen Modellen und unsicherer projektiver Geometrie behandelt.