Neighborhood Data Structures, Manifold Properties, and Processing of Point Set Surfaces

Abstract

The thesis covers three topics all centered in the context of point set processing. In the following, we will shortly present each topic with its motivation, explain the performed research, and highlight the contributions. In case the presented results have been published prior to the publication of this thesis, the corresponding reference is given.

The first topic concerns notions of neighborhood and corresponding data structures. Many researchers have recognized the importance of high-quality neighborhood relations. For example, the authors Lange and Polthier in their CAGD article from 2005 report that the results of their anisotropic smoothing algorithm heavily depend on the neighborhood structure imposed on the point set. Despite their advantages in storage space and easy acquisition, the missing neighborhood relation is a significant downside to point set representations. The purpose of this first part is to discuss neighborhood concepts as well as a data structure for fast single-core and fast parallelized computation respectively.

The second main topic of this thesis deals with manifold structures for point set surfaces. From a significant amount of real-world objects, while 3D-scanning them, only the surface is acquired for further processing in CAD or other applications. When the surface of the underlying real-world geometry has the structure of a manifold, it can be expected that this structure is reflected by any point set acquired from the geometry. Even when the faces of the geometry are smooth manifold patches, there is no theory available in the setting of point sets to reflect their manifold properties.

Third and finally, algorithms have to work efficiently and robustly on the point set. While meshed geometries provide an intuitive and natural weighting by the areas of the faces, point sets can at most work with distances between the points. This introduces a new level of difficulty to be overcome by any point set processing algorithm. This final chapter introduces a novel weighting scheme to counteract non-uniformity in point sets, a feature detection algorithm with mathematical guarantees, and an iterative denoising scheme for point sets.

Die Arbeit beschäftigt sich mit drei Bereichen, die jeweils im Umfeld der Verarbeitung von Punktwolken verortet sind. Der erste Bereich betrifft Konzepte von Nachbarschaften sowie zugehörige Datenstrukturen. In der Forschung wurde bereits mehrfach auf die Wichtigkeit von qualitativ hochwertigen Nachbarschaftsrelationen auf Punktwolken hingewiesen. Die Autoren Polthier und Lange berichten in ihrer CAGD Publikation von 2005 beispielsweise, dass die Ergebnisse ihres anisotropen Glättungsverfahrens stark von den Nachbarschaften abhängen, die sie für die prozessierte Punktwolke berechnen. Während bereits mehrere kombinatorisch oder metrisch basierte Konzepte für Nachbarschaften auf Punktwolken vorgestellt wurden, berücksichtigt keines dieser Konzepte die Informationen der Normalen, bzw. der Krümmung. Die Doktorarbeit stellt daher ein neues Verfahren für die Bestimmung von Nachbarschaften vor, die sich an der lokalen Form der Geometrie orientieren. Jegliche Nachbarschaftskonzepte sind nur dann von praktischer Relevanz, wenn sie auch schnell in unterschiedlichen Anwendungen berechnet werden können. Hierfür fällt die Wahl häufig auf die Datenstruktur der k-d Bäume von Friedman, Bentley und Finkel. Dies liegt vor allem an der bewiesenen Laufzeit einer Nachbarschaftsabfrage von erwartet O(log(n)) auf n Punkten. Die Doktorarbeit präsentiert eine ausführliche Ausarbeitung dieser Laufzeitberechnung. Schließlich werden solche Datenstrukturen immer wichtiger, die von massiver Parallelisierung - z.B. auf Grafikkarten - profitieren. Eine solche stellt das Nachbarschaftsgitter dar, das von Joselli et al. eingeführt wurde. Die Doktorarbeit beantwortet mehrere offene Fragen zur Kombinatorik und zur Qualität der Nachbarschaften dieser Struktur.

Der zweite große Bereich der Arbeit zielt auf Mannigfaltigkeitsstrukturen für durch Punktwolken dargestellte Oberflächen. Immer, wenn die zugrundeliegende Geometrie die Struktur einer glatten Mannigfaltigkeit hat, kann erwartet werden, dass diese Struktur auch durch eine Stichprobe in Form einer Punktwolke abgebildet wird. Jedoch gibt es für Punktwolken bisher keine Konstruktion, die diese Struktur abbildet. Eine Lösung für diese Forschungslücke wird in der Doktorarbeit präsentiert. Außerdem ist das wichtigste Element für die Repräsentation von Mannigfaltigkeiten ein Atlas aus Karten mit entsprechenden Kartenwechselabbildungen. Die Doktorarbeit präsentiert einen Ansatz, bei dem Karten aus möglichst großen flachen Stücken der Punktwolke generiert werden. Diese flachen Stücke können dann einfach in anderen Verfahren genutzt werden.

Der abschließende dritte Teil der Arbeit beschäftigt sich mit effizienten und robusten Algorithmen für die Verarbeitung von Punktwolken. Wie oben bereits vermerkt, bieten Punktwolken - im Gegensatz zu Netzen mit ihren Flächenstücken -- keine natürlichen Gewichtungen für ihre Elemente. Hier können nur die paarweisen Distanzen zwischen Punkten genutzt werden. Dies erschwert die Handhabung von Punktwolken mit uneinheitlicher Verteilung. Um diesem Problem entgegenzuwirken präsentiert die Arbeit neuartige Gewichte für die Verwendung in Diskretisierungen - z.B. von Differentialoperatoren - die für eine Verarbeitung wie im Falle einer einheitlichen Stichprobe sorgen. Abseits hiervon spielt in Anwendungen vor allem auch die Identifikation von Merkmalen einer Geometrie - Ecken, Kanten und Flächen - eine Rolle. Die Arbeit präsentiert daher einen auf dem Verfahren der bewegten kleinsten Quadrate basierenden Ansatz für die Erkennung von Geometriemerkmalen. Die Arbeit schließt mit der Vorstellung eines Glättungsalgorithmus für Punktwolken. Dieser entfernt bei der Akquise der Punkte fälschlicherweise erzeugtes Rauschen ohne dabei die oben angesprochenen Merkmale der Geometrie zu verwischen. Die Arbeit schlägt somit einen Bogen von der Erfassung von Punktwolken über theoretische Konstruktionen hin zur praktischen Verarbeitung.