Synthese und Optimierung von Konstruktionsbäumen aus unstrukturierten räumlichen Daten

Friedrich, Markus (2022): Synthese und Optimierung von Konstruktionsbäumen aus unstrukturierten räumlichen Daten. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

Sensorsysteme für die dreidimensionale Abtastung von Objektoberflächen sind in vielen Bereichen des täglichen Lebens omnipräsent. Moderne Smartphones und Spielekonsolen im Heimanwenderbereich sowie professionelle Systeme, z.B. eingesetzt zur Qualitätssicherung in Fertigungsprozessen, beinhalten Hard- und Softwarekomponenten zur Ermittlung räumlicher Daten. Aus entsprechenden Quellen stammende Datensätze bestehen meist aus einzelnen dreidimensionalen Punkten, die in unstrukturierter Form und potentiell messfehlerbehaftet vorliegen. Oft ist die Erzeugung dieser Punktwolke nur der erste Schritt innerhalb eines komplexen Verarbeitungsprozesses, an dessen Ende eine Repräsentation der räumlichen Daten steht, die für den entsprechenden Anwendungsfall als optimal angesehen wird. Ein solcher Anwendungsfall ist z.B. die automatische Erzeugung von Architekturplänen oder das Reverse Engineering (RE), also die Analyse des Aufbaus und der Funktionsweise eines Produkts. In beiden Fällen ist eine Repräsentation von Vorteil, die unnötige Details abstrahiert und dabei weiterführende Information über den Aufbau des Objekts und dessen elementare Bausteine beinhaltet. Eine solche Darstellung ist die sog. Constructive Solid Geometry (CSG)-Repräsentation, die Modelle als Baumstruktur bestehend aus Booleschen Mengenoperatoren in den inneren Knoten und geometrischen Primitiven in den äußeren Knoten beschreibt. Dabei ist die manuelle Erzeugung dieses sog. Konstruktionsbaums (KB) aus einer Punktwolke zeitaufwendig und für komplexe Datensätze kaum zu bewerkstelligen. Aus diesem Grund werden in dieser Arbeit Methoden vorgestellt, die das Problem der automatischen Synthese von KBs aus fehlerbehafteten Punktwolken robust und effizient lösen. Die vorgestellten Verfahren werden dabei in eine eigens entwickelte Prozess-Pipeline eingebettet und miteinander verknüpft. Den Anfang macht die Einführung eines Systems, das geometrische Primitive, wie Kugeln, Zylinder und allgemeine konvexe Polytope, mittels Maschinellem Lernen (ML) und Evolutionären Algorithmen (EA) in der Eingabepunktwolke detektiert und in diese einpasst. Dieser folgt die Vorstellung einer Methode, die das eigentliche KB-Syntheseproblem für bekannte Primitive löst und dazu auf graphbasierte Partitionierungs- und Vereinfachungsstrategien zur Steigerung von Laufzeiteffizienz und Robustheit zurückgreift. Da die Repräsentation als KB nicht eindeutig ist, lassen sich zusätzliche Metriken, wie z.B. die Baumgröße, bestimmen und existierende KBs entsprechend optimieren. Dieses Problem steht abschließend im Fokus dieser Arbeit, zu dessen vorgestellter Lösung ein Spektrum unterschiedlicher Lösungsstrategien evaluiert und diskutiert wird.

Abstract

Sensor systems for three-dimensional object surface scanning are omnipresent in many areas of daily life. Modern smartphones and game consoles for home users and professional systems, e.g., used for quality assurance in manufacturing processes, contain hard- and software components for measuring spatial data. Data sets originating from such sources usually consist of individual three-dimensional points which are unstructured and potentially subject to measurement errors. Often, the generation of this so-called point cloud is only the first step within a complex processing procedure which results in a spatial data representation that is considered optimal for a specific use case. Such a use case is, for example, the automatic generation of architectural plans or Reverse Engineering (RE), i.e., the analysis of a product's structure and functionality without any prior knowledge. In both cases, it is advantageous to obtain a representation that abstracts unnecessary details while providing more information about an object's structure and elementary building blocks. Such a representation is called Constructive Solid Geometry (CSG), which describes models as a tree structure consisting of Boolean set operators in the inner nodes and geometric primitives in the outer nodes. However, the manual generation of these so-called Construction Trees (CTs) based on a measured point cloud is time-consuming and hardly feasible for complex data sets. For this reason, this work presents methods that can robustly and efficiently solve the problem of automatically synthesizing CTs from error-prone point clouds. The presented methods are thereby embedded and interconnected in a newly developed process pipeline. At first, a system is introduced that detects and fits geometric primitives such as spheres, cylinders and general convex polytopes in the input point cloud using Machine Learning (ML) and Evolutionary Algorithms (EA). This is followed by an introduction of a method that solves the automatic CT synthesis problem for known primitives using graph-based partitioning and simplification strategies to increase runtime efficiency and robustness. Since the representation as CTs is not unique additional metrics such as tree size can be determined, and existing CTs can be optimized accordingly. This problem is the last this work addresses for which a spectrum of different solution strategies is evaluated and discussed.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Themengebiete: 000 Allgemeines, Informatik, Informationswissenschaft ; 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Deutsch
• Datum der mündlichen Prüfung: 13. April 2022
• 1. Bericht­erstatter:in: Linnhoff-Popien, Claudia