A Direct Approach for the Segmentation of Unorganized Points and Recognition of Simple Algebraic Surfaces

In Reverse Engineering a physical object is digitally reconstructed from a set of boundary points. In the segmentation phase these points are grouped into subsets to facilitate consecutive steps as surface fitting. In this thesis we present a segmentation method with subsequent classification of simple algebraic surfaces. Our method is direct in the sense that it operates directly on the point set in contrast to other approaches that are based on a triangulation of the data set. The reconstruction process involves a fast algorithm for $k$-nearest neighbors search and an estimation of first and second order surface properties. The first order segmentation, that is based on normal vectors, provides an initial subdivision of the surface and detects sharp edges as well as flat or highly curved areas. One of the main features of our method is to proceed by alternating the steps of segmentation and normal vector estimation. The second order segmentation subdivides the surface according to principal curvatures and provides a sufficient foundation for the classification of simple algebraic surfaces. If the boundary of the original object contains such surfaces the segmentation is optimized based on the result of a surface fitting procedure.Im Reverse Engineering wird ein existierendes Objekt aus einer Menge von Oberflächenpunkten digital rekonstruiert. Während der Segmentierungsphase werden diese Punkte in Teilmengen zusammengefügt, um die nachfolgenden Schritte wie Flächenerkennung (surface fitting) zu vereinfachen. Wir präsentieren in dieser Arbeit eine Methode zur Segmentierung der Punkte und die anschließende Klassifikation einfacher algebraischen Flächen. Unser Verfahren ist direkt in dem Sinne, dass es direkt an den Punkten arbeitet, im Gegensatz zu anderen Verfahren, die auf einer Triangulierung der Punktmenge basieren. Der Rekonstruktionsprozess schließt einen neuen Algorithmus zur Berechnung der k-nächsten Nachbarn eines Oberflächenpunktes und Verfahren zur Schätzung der Flächeneigenschaften ersten und zweiten Grades ein. Die normalenbasierte Segmentierung (Segmentierung ersten Grades) liefert eine Aufteilung des Objektes und detekiert scharfe Kanten, sowie flache oder stark gekrümmte Gebiete des Objektes. Ein zentrales Element unserer Methode ist die Wiederholung der Schritte der Segmentierung und der Schätzung der Normalen. Erst die Iteration ermöglicht die Schätzung der Normalen in der benötigten Genauigkeit und die Generierung einer zufriedenstellender Segmentierung. Die Segmentierung zweiten Grades teilt die Oberfläche nach den Hauptkrümmungen auf und bietet eine zuverlässige Grundlage für die Klassifizierung einfacher algebraischen Flächen. Falls der Rand des Ausgangsobjektes solche Flächen enthält, wird der Segmentierungsprozess auf der Grundlage des Ergebnisses der Flächenerkennungsprozedur optimiert