3D Gebäudemotoroptimierung

Die Arbeit beginnt mit der Definition des zentralen Problems: Die Reduktion der Datenmenge von 3D-Gebäudemodellen bei gleichzeitiger Erhaltung des maximalen Informationsgehalts für die jeweilige Anwendung. Dies stellt ein Optimierungsproblem mit widersprüchlichen Zielen dar: Minimierung der Datenmenge und Maximierung des Informationsgehalts. Zusätzliche Nebenbedingungen betreffen die Verarbeitbarkeit der resultierenden Features durch die Anwendung. Schon einfache Versionen grundlegender Teilprobleme, wie die Aggregation einfacher Gebäudemodelle oder die Vereinfachung einfacher Fassadenstrukturen, erweisen sich als NP-hart. Mixed Integer Programming (MIP) wird als mächtiges Werkzeug zur Bestimmung global optimaler Lösungen solcher komplexer Probleme identifiziert. Die Dissertation entwickelt MIP-basierte Ansätze für die Gebäudeaggregation und Fassadenvereinfachung. Diese optimierenden Ansätze sind zwar rechenintensiv, dienen aber als Benchmark für heuristische Verfahren. Die steigende Leistungsfähigkeit moderner Rechnerhardware ermöglicht zwar Simulationen mit immer detaillierteren Modellen, erhöht aber den Aufwand für die Datenerfassung. Die Generalisierung bestehender, hochdetaillierter Modelle bietet daher eine effiziente Alternative zur Vermeidung neuer Erfassungskampagnen.

Ein zentraler Punkt der Arbeit ist die Feststellung, dass das Problem der 3D-Gebäudemodell-Generalisierung, selbst in seinen einfachsten Ausprägungen, NP-hart ist. Dies wird anhand von Beispielen wie der Aggregation von LOD-1-Gebäudemodellen und der Vereinfachung einfacher Fassadenstrukturen belegt. Die NP-Härte impliziert, dass die Berechnung einer optimalen Lösung in polynomieller Zeit unwahrscheinlich ist. Daher ist die Entwicklung effizienter heuristischer Ansätze essentiell. Die Arbeit entwickelt und evaluiert solche heuristischen Ansätze, insbesondere für das Problem der LOD-1-Aggregierung. Dabei wird das optimale Ergebnis aus der Lösung des MIP-Problems als Referenz verwendet. Es zeigt sich, dass bereits einfache, lokal optimierte iterative Lösungen sehr gute Ergebnisse liefern können, was die Praktikabilität heuristischer Ansätze unterstreicht. Der Vergleich mit den rechenintensiven, optimalen Lösungen durch MIP dient als Validierung der heuristischen Verfahren.

Der Hausdorff-Abstand wird als Qualitätsmaß für die Generalisierung betrachtet. Die Arbeit analysiert jedoch die Grenzen der ursprünglichen Definition des Hausdorff-Abstands im Kontext der Gebäudemodellierung. Es wird gezeigt, dass die strikte Anwendung des Hausdorff-Abstands in manchen Fällen zu unrealistischen Ergebnissen führt, z.B. bei der Berücksichtigung von Details wie Antennen, die im Verhältnis zum Gesamtgebäude sehr klein sind. Die Arbeit argumentiert, dass die ursprüngliche Definition des Hausdorff-Abstands die Möglichkeiten für Generalisierungsoperatoren zu stark einschränkt, besonders bei unterschiedlichen Skalierungen und der Berücksichtigung relativer Genauigkeit. Die Problematik wird anhand von Beispielen mit unterschiedlichen Ausdehnungen in verschiedenen Dimensionen (z.B. die Dicke einer Wand im Vergleich zu ihrer Länge) veranschaulicht. Aus diesem Grund werden zusätzliche Regeln eingeführt, um relevante Features zu erhalten und ein realistischeres Qualitätsmaß zu etablieren. Die Arbeit betont die Notwendigkeit von Anpassungen des Hausdorff-Abstands, um die spezifischen Herausforderungen der 3D-Gebäudemodellierung zu bewältigen und die Generalisierungsoperationen sinnvoll zu steuern.

Die Arbeit vergleicht die Modellierung von Gebäuden in 2D und 3D und betont die deutlich höhere Komplexität in 3D. In 2D wird ein Gebäude im Wesentlichen durch seinen Grundriss (Footprint) und semantische Informationen (z.B. Gebäudehöhe, Anzahl der Stockwerke) repräsentiert. Die 3D-Modellierung hingegen erfordert die Erfassung und Modellierung einer Vielzahl zusätzlicher Entitäten: Wände, Dächer, Fenster, Türen, Balkone usw. Die unterschiedlichen Maßstäbe der einzelnen Features (z.B. die Größe eines Balkons im Vergleich zum gesamten Gebäude) führen zu zusätzlichen Herausforderungen. Das Problem der Okklusion, d.h. das verdeckte Liegen von Objekten, wird als weiterer wichtiger Unterschied zwischen 2D und 3D hervorgehoben. Im Gegensatz zu 2D-Darstellungen, die vollständig in einer einzigen statischen Ansicht (Karte) abgebildet werden können, gibt es in 3D keine kanonische Darstellung aufgrund von Okklusionen. Dies hat erhebliche Auswirkungen auf die Generalisierung von 3D-Daten und die Wahl geeigneter Darstellungs- und Verarbeitungstechniken.

Die vorgestellte Arbeit beschreibt eine erweiterbare Basis-Infrastruktur zur Kombination verschiedener Generalisierungsmodule für unterschiedliche Teile eines hierarchischen Feature-Modells. Diese Architektur zielt darauf ab, verschiedene Generalisierungsansätze flexibel zu kombinieren und an verschiedene Gegebenheiten anzupassen. Die Infrastruktur soll erweiterbar sein für unterschiedliche Feature-Typen und Generalisierungsalgorithmen. Ein wichtiger Aspekt ist die Nutzung generativer Aspekte des zugrundeliegenden Basismodells, um die Komplexität der Konfliktlösung im Generalisierungsprozess zu reduzieren. Konflikte können beispielsweise bei der sequenziellen Anwendung verschiedener Generalisierungsoperationen auftreten, wenn das Ergebnis vom ursprünglichen Modell abweicht. Durch die modulare Struktur und die Integration generativer Aspekte wird angestrebt, diese Konflikte effizient zu lösen und eine robustere und flexiblere Generalisierung zu ermöglichen. Die Verwendung einer hierarchischen Struktur ermöglicht es, die Komplexität zu bewältigen und die Generalisierung in überschaubare Teilschritte zu zerlegen.

Die Arbeit beschreibt ein hierarchisches Gebäudemodell, welches als Grundlage für die Generalisierung dient. Diese hierarchische Struktur ermöglicht es, verschiedene Generalisierungsansätze auf unterschiedlichen Ebenen des Modells anzuwenden. Die Architektur ist so konzipiert, dass sie verschiedene Feature-Typen und Generalisierungsalgorithmen unterstützt. Die Berücksichtigung der Feature-Typen ist wichtig, da verschiedene Features unterschiedliche Eigenschaften haben und daher mit verschiedenen Algorithmen generalisiert werden müssen. Die effiziente Verarbeitung und Übertragung der Modelle ist ein wichtiger Aspekt, der durch die selektive Expansion der benötigten Features sichergestellt wird. Dies vermeidet die unnötige Erzeugung und Verarbeitung von Daten, die für die jeweilige Anwendung nicht benötigt werden. Insbesondere bei impliziten Ordnungen der Teile eines Features ist diese Eigenschaft äußerst nützlich. Ein Beispiel hierfür ist ein Zeltdach, dessen Visualisierung ohne die Konstruktion aller Oberflächeneigenschaften direkt aus den Parametern des Grundrisses berechnet werden kann.

Die Architektur der Generalisierungsinfrastruktur basiert auf der konsistenten Verwendung von Schnittstellen, die von verschiedenen konkreten Klassen im Gebäudemodell realisiert werden können. Ein einzelnes Generalisierungsmodul deckt in vielen Fällen nur sein Basis-Feature (Link) für die generischeren Feature-Typen ab. Ein Beispiel hierfür ist ein BuildingPart, das nur weiß, dass es aus einem BuildingBody und einem Roof besteht, die beide recht komplexe Strukturen haben können. Ein generisches BuildingPart-Generalisierungsmodul muss sich daher auf externe Module für die Vereinfachung des BuildingBody und des Roofs verlassen und nur eine grundlegende Prüfung durchführen, ob keine Lücke zwischen den resultierenden Dach- und Körperobjekten besteht. Diese modulare Architektur erlaubt es, verschiedene Generalisierungsmodule flexibel zu kombinieren und so einen anpassungsfähigen und skalierbaren Prozess für die Generalisierung von 3D-Gebäudemodellen zu schaffen. Die konsistente Verwendung von Schnittstellen erlaubt es, neue Module einfach hinzuzufügen oder bestehende Module auszutauschen, ohne die gesamte Architektur verändern zu müssen.

Die Vereinfachung von Gebäudegrundrissen (Footprints) wird als essentieller erster Schritt in der Generalisierung von Datensätzen mit LOD1-Gebäudemodellen beschrieben. Oftmals liegen hochdetaillierte Grundrisse mit zentimetergenauer Genauigkeit vor, jedoch fehlen Informationen über Dachformen oder Fassadenstrukturen. Für eine allgemeine Auflösung, die nicht speziell auf die Form des Grundrisses fokussiert ist, ist die hohe Genauigkeit des Footprints oft irrelevant, da die Dach- und Fassadenstrukturen Größenordnungen von mehreren Metern haben können. Die Erhaltung feinräumiger Strukturen im Grundriss würde somit eine Genauigkeit vortäuschen, die vom Modell nicht garantiert werden kann und zu einer enormen Datenmenge führt. Die Arbeit argumentiert daher für eine Vereinfachung der Grundrisse, um die Datenmenge zu reduzieren und die Rechenzeit zu verkürzen, ohne relevante Informationen zu verlieren. Der Fokus liegt dabei auf der Erzeugung von sinnvollen Eingangsdaten für die Generalisierung von LOD1-Gebäudemodellen, die ein sinnvolles Verhältnis zwischen Datenmenge und Informationsgehalt aufweisen.

Ein Algorithmus zur Grundrissvereinfachung wird vorgestellt, der auf einer modifizierten Hough-Transformation und einem flexiblen Least-Squares-Fitting basiert. Die Hough-Transformation wird verwendet, um Liniensegmente im Grundriss zu detektieren und zu gruppieren. Dabei werden Beziehungen wie Parallelität und Kollinearität, die in den meisten Gebäudegrundrissen vorherrschen, explizit berücksichtigt. Das Least-Squares-Fitting dient zur optimalen Anpassung der erkannten Liniensegmente an die ursprünglichen Datenpunkte. Die Gewichtung der Beobachtungen im Least-Squares-Verfahren wird iterativ angepasst, um die Betonung der Beziehungen (Parallelität, Kollinearität) zu verstärken und die Anpassung der Segmente an die Daten zu optimieren. Das Verfahren vereinfacht den Gebäudegrundriss durch die Extraktion relevanter Liniensegmente, wodurch unnötige Details entfernt werden und ein vereinfachtes Polygon entsteht, das immer noch die wesentlichen Merkmale des Gebäudes repräsentiert. Diese Vereinfachung ist wichtig für die effiziente Verarbeitung und Analyse der Daten im weiteren Generalisierungsprozess.

Die Arbeit diskutiert die Komplexität des Problems, ein optimales Polygon zu finden, das den ursprünglichen Grundriss approximiert. Obwohl das Problem auf den ersten Blick als kontinuierliches Optimierungsproblem erscheinen mag, wird argumentiert, dass es für sinnvolle Definitionen von Optimalität sogar komplexer als das diskrete Problem der Auswahl einer optimalen Teilmenge der ursprünglichen Eckpunkte ist (Estkowski und Mitchell (2001)). Die Komplexität liegt in der subtilen kombinatorischen Beziehung zwischen den Teilen des ursprünglichen Polygons (in diesem Fall den abgetasteten Punkten) und dem approximierenden Polygon (den extrahierten Liniensegmenten). Dies gilt insbesondere dann, wenn das approximierende Polygon frei von Selbstüberschneidungen sein soll. Die Arbeit betont somit die Herausforderungen, die bei der Entwicklung eines effizienten Algorithmus zur optimalen Approximation des Gebäudegrundrisses auftreten. Die Komplexität des Problems unterstreicht die Bedeutung der gewählten heuristischen Ansätze, die trotz ihrer Näherungslösungen zu guten Ergebnissen führen.

Die Arbeit beschreibt das Problem der Gebäudeaggregation als ein Optimierungsproblem, bei dem eine minimale Anzahl von Gebäudeclustern gefunden werden soll, wobei die Höhenunterschiede zwischen Gebäuden innerhalb eines Clusters durch einen Schwellenwert (∆h) begrenzt sind. Die Gebäude sind dabei durch einen Nachbarschaftsgraphen (G) miteinander verbunden. Es wird ein detaillierter Beweis geliefert, der zeigt, dass dieses Problem, selbst bei planarem Graphen G und nur drei anfänglichen Höhenstufen, NP-hart ist. Dies bedeutet, dass ein Algorithmus, der für alle Eingaben in akzeptabler Zeit (polynomiale Laufzeit) das exakte Optimum findet, unwahrscheinlich ist. Die NP-Härte des Problems unterstreicht die Notwendigkeit, heuristische Ansätze für die Lösung dieses Problems zu entwickeln und zu untersuchen. Diese Erkenntnis motiviert die Entwicklung und den Vergleich heuristischer und optimaler Lösungsansätze im weiteren Verlauf der Arbeit. Die Beschränkung der maximalen Höhendifferenz innerhalb eines Clusters ist ein wichtiger Aspekt, der die Komplexität des Problems beeinflusst und die Auswahl der Aggregationsschritte steuert.

Für das Gebäudeaggregationsproblem werden heuristische Ansätze entwickelt und mit den optimalen Lösungen, die durch Mixed Integer Programming (MIP) berechnet werden, verglichen. Dabei werden ein Best-First- und ein Greedy-Algorithmus eingesetzt. Ein grundlegendes Problem aller heuristischen Ansätze besteht darin, dass keine Backtracking-Optionen vorhanden sind. Sobald die Entscheidung getroffen wurde, zwei Cluster zu verschmelzen, kann diese Entscheidung nicht mehr rückgängig gemacht werden. Ein weiteres Problem tritt auf, wenn verschiedene Nebenbedingungen erfüllt werden müssen. Der Best-First-Ansatz kann in Schwierigkeiten geraten, wenn verschiedene Aggregationsschritte eine Bedingung begünstigen, aber bezüglich einer anderen nachteilig sind. Heuristische Ansätze müssen daher Strategien enthalten, um in solchen Situationen eine sinnvolle Wahl zu treffen. Beispielsweise kann bei kumulativen Nebenbedingungen, wie der eingeschränkten Gesamtänderung des Pseudovolumens, jedem Nebenbedingungswert ein Gewicht zugewiesen werden, das mit dem Anteil, zu dem der entsprechende Pool aufgebraucht wurde, zunimmt. Die Ergebnisse zeigen die Stärken und Schwächen der heuristischen Verfahren im Vergleich zur optimalen Lösung.

Die Arbeit vergleicht die Ergebnisse der heuristischen Ansätze (Best-First und Greedy) mit dem Ergebnis des optimierenden Ansatzes (MIP). Ein Beispiel zeigt, wie die heuristischen Ansätze aufgrund ihrer eingeschränkten Suchstrategie zu suboptimalen Lösungen führen können. Der optimierende Ansatz liefert zwar die kleinste Anzahl aggregierter Gebäude, dafür aber eine höhere Volumenänderung. Die heuristischen Ansätze erreichen zwar eine geringere Volumenänderung, benötigen dafür aber mehr aggregierte Gebäude. Der Einfluss des Parameters für die maximale durchschnittliche (skalierte) Pseudo-Volumenänderung auf die Performance der heuristischen Ansätze wird hervorgehoben. Restriktivere Werte erhöhen die Wahrscheinlichkeit, dass die heuristischen Ansätze in lokalen Optima stecken bleiben und keine optimale Lösung finden. Die Ergebnisse werden für verschiedene Auflösungen (definiert durch den Schwellenwert für die maximale Höhenänderung innerhalb eines Clusters) verglichen. Dies zeigt den Einfluss der Parameter auf die Ergebnisse und die Notwendigkeit einer sorgfältigen Parameterwahl für eine effiziente und effektive Gebäudeaggregation.

Die Fassadenhomogenisierung wird als ein Problem der minimalen rechteckigen Kachelung (Tiling) einer Matrix (2D-Gitterstruktur) modelliert. Ziel ist es, Zellgruppen in geclusterte Regionen zu gruppieren, in denen die Parameter aller Features einheitliche Werte erhalten. Um das Speicherersparnispotenzial voll auszuschöpfen und die spätere Typisierung zu vereinfachen, müssen die resultierenden Regionen Rechtecke bilden. Das Problem wird als Mixed Integer Programming (MIP)-Problem formuliert, wobei Kosten nur für das Hinzufügen von Kacheln und für die Änderung von Parameterwerten entstehen. Die Anzahl der benötigten Kacheln wird durch die Optimierungsfunktion minimiert, unter Berücksichtigung der Nebenbedingungen, die die Rechteckigkeit der Kacheln und die Einheitlichkeit der Parameter innerhalb der Kacheln gewährleisten. Die Arbeit beschreibt, wie die Struktur der Kachelung und die Parameterwerte der Fassadenelemente im MIP-Modell repräsentiert werden. Die Optimierung zielt darauf ab, eine minimale Anzahl von Kacheln zu verwenden, um die Fassadenstruktur darzustellen, wobei die Ähnlichkeit der Parameterwerte innerhalb der Kacheln maximiert wird.

Das MIP-Modell zur Fassadenhomogenisierung wird durch Constraints definiert, die die Struktur der Kachelung und die Einheitlichkeit der Parameterwerte innerhalb der Kacheln sicherstellen. Es werden Constraints eingeführt, die die Rechteckigkeit der Kacheln gewährleisten und Mehrdeutigkeiten vermeiden. Um die Performance des MIP-Solvers zu verbessern, werden Constraints verwendet, die sicherstellen, dass nur die ersten k Kachel-Platzhalter verwendet werden, wenn k Kacheln in der Lösung vorhanden sind (∀f ∈ {1, ..., Nf − 1} : Af ≤ Af−1). Für jede Fassaden-Gitterzelle wird das Fassadenstück durch eine Liste von Parameterwerten modelliert (z.B. Breite und Höhe von Fenstern und Türen, Farbe der Wand). Die Zielfunktion des MIP-Problems minimiert die Kosten, die durch das Hinzufügen von Kacheln und das Ändern von Parameterwerten entstehen. Zusätzliche Terme in der Zielfunktion können verwendet werden, um bestimmte Ausrichtungen von Kacheln zu bevorzugen, z.B. die Ausrichtung mit der Hauptfassadenebene. Die Wahl der Constraints und der Zielfunktion ist entscheidend für die Effizienz und die Qualität der Lösung.

Die Arbeit zeigt, wie die Performance des MIP-Solvers durch eine weniger direkte Modellierung des Problems und die Verwendung von Heuristiken für Spezialfälle (z.B. Flussprobleme) verbessert werden kann. Ein Vergleich zwischen zwei Versionen des MIP-Modells zeigt, dass die zweite Version, die weniger Mehrdeutigkeiten aufweist, eine drastische Verbesserung der Laufzeit und der Ressourcencharakteristiken erreicht. Die Fassadenhomogenisierung wird als degenerierter Fall einer Typisierung betrachtet, bei der eine Menge von k Features durch eine Menge von k' identischen symbolischen Features ersetzt wird (k' = k für Homogenisierung, k' < k für Typisierung). Die Arbeit diskutiert die Problematik der Anwendung randomisierter Approximationsverfahren wie Simulated Annealing, genetische Algorithmen oder Monte-Carlo-Methoden für die Fassadenhomogenisierung. Diese Verfahren sind aufgrund des Mangels an gültigen Lösungen in der Nachbarschaft einer gegebenen Lösung problematisch. Die Arbeit verweist auf die NP-Härte des Problems der minimalen rechteckigen Kachelung (RTile-Problem), welches eng mit der Fassadenhomogenisierung verwandt ist und in der Literatur diskutiert wird (Khanna et al. (1998), Grigni und Manne (1996), Berman et al. (2001), Nichterlein et al. (2011)).