Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Moderne 3D scanners maken het mogelijk om heel snel grote hoeveelheden 3D data te genereren. Dit resulteert in een steeds groeiend aantal toepassingen, gaande van digitalisatie van historische objecten tot gezichtsauthenticatie. In deze thesis stellen we een aantal nieuwe algoritmen voor om de data, verkregen met behulp van een 3D scanner, te verwerken. Deze data worden een puntenwolk genoemd en bestaan uit een verzameling punten bemonsterd van het 3D oppervlak van een object. De voorgestelde algoritmen betreffen enkele fundamentele topics in puntenwolkverwerking: triangulatie, vereffening en randbepaling. We analyseren de algoritmen vanuit het standpunt van efficiëntie, praktische toepasbaarheid en de volledigheid van de onderliggende theorie. Randbepaling is een veel voorkomend probleem in toepassingen waar het nodig is om te weten waar de gaten en externe randen liggen in een puntenwolk. In dit werk ontwikkelen we een nieuw algoritme voor het bepalen van randen, die we als gesloten, veelhoekige randlussen voorstellen. Het resultaat van dit algoritme wordt verder gebruikt door de andere algoritmen besproken in de thesis. Een andere fundamentele operatie is de triangulatie van puntenwolken. Het resultaat van deze operatie is een driehoekig rooster dat de buurpunten op een consistente manier met elkaar verbindt en zo de connectiviteitsinformatie toevoegt aan de puntenwolk. Wij bespreken twee aanpakken voor het trianguleren van puntenwolken. De eerste aanpak is gebaseerd op de zogenaamde roosterloze parameterisatietechniek en de tweede aanpak wordt het volumetrisch projectie-algoritme genoemd en steunt op de volumetrische voorstelling van de puntenwolk. Elke aanpak heeft zijn voor- en nadelen en kan verschillende soorten input-puntenwolken behandelen. Roosterloze parameterisatie is geschikt voor puntenwolken met schijftopologie en het volumetrisch projectie-algoritme is toepasbaar op gesloten puntenwolken van willekeurige genus en zonder randen. Vereffening is een frequent gebruikte operatie. Het is nodig om de ruis in opgemeten puntenwolken te verwijderen en op die manier de verdere verwerking gemakkelijker te maken. In het laatste deel van deze thesis stellen wij een nieuw vereffeningsalgoritme voor, dat geformuleerd wordt als een lineaire algebra optimalisatieprobleem met beperkingen. Één van de voordelen van het algoritme is zijn algemeenheid, in de zin dat het niet alleen op puntenwolken toegepast kan worden, maar ook op triangulaties, grafieken, curvenetwerken en in het algemeen op functies gedefinieerd in de knopen van een grafe. Het algoritme steunt op een efficiënte kleinste-kwadratensolver en heeft gegarandeerde convergentie. Bovendien heeft het algoritme interessante theoretische eigenschappen, wegens zijn verwantschap met de geometrie-bewuste basissen en Tikhonov-regularisatie. De gepresenteerde algoritmen dragen bij tot het domein van digital geometry processing en trachten de vraag naar efficiënte puntenwolkverwerkingsalgoritmen te beantwoorden. Modern 3D scanners make it possible to collect large amounts of 3D data in just a few seconds. This technological progress results in a growing number of applications ranging from the digitalization of historical artifacts to facial authentication. In this thesis we propose a number of novel algorithms for the processing of data obtained using 3D scanners. Such data is called a point cloud and it consists of a collection of points sampled from the surface of a 3D object. The proposed algorithms address some fundamental topics in point cloud processing, i.e. triangulation, smoothing and boundary extraction. We analyze the algorithms from the viewpoint of efficiency, practicality and the soundness of the underlying theory. Boundary extraction is required in many applications, where it is useful to know where the holes and exterior boundaries of the point cloud are situated. Using concepts from graph theory we develop a novel algorithm for the extraction of closed polygonal boundary loops in point clouds. This boundary information is used by other algorithms discussed in this thesis. Another fundamental operation, often performed on point clouds, is triangulation. The result of this operation is a triangular mesh, which connects the neighboring points with each other in a consistent way, thereby adding connectivity information to the point cloud. We discuss two approaches for triangulating point clouds. One is based on the so-called meshless parameterization technique and the other is called volumetric snapping and relies on a volumetric representation of the point data. Each approach has its advantages and can handle different types of input point clouds. Meshless parameterization is suitable for point clouds with disc topology and the volumetric snapping algorithm handles closed point clouds of arbitrary genus without boundaries. Smoothing is a frequently used operation on point clouds. It is required to remove noise and to make further processing easier. In the last part of the thesis we propose a new smoothing algorithm, which is formulated as a constrained linear algebra optimization problem. The advantage of the algorithm is its generality, in the sense that it can be applied not only to point clouds, but also to triangulations, plots, curve networks and in general to functions defined on graphs. The algorithm relies on an efficient least squares solver and has guaranteed convergence. Furthermore, it possesses interesting theoretical properties, because of its connection with the geometry-aware bases and Tikhonov regularization. The presented algorithms contribute to the new field of digital geometry processing and help to address the demand for efficient point cloud processing techniques. Moderne 3D scanners maken het mogelijk om heel snel grote hoeveelheden 3D data te genereren. Dit resulteert in een steeds groeiend aantal toepassingen, gaande van digitalisatie van historische objecten tot gezichtsauthenticatie. In veel gevallen is het resultaat van een scan een puntenwolk, ofwel een verzameling punten die het oppervlak van het object voorstellen. In alle toepassingen die met puntenwolken te maken hebben is het noodzakelijk om de grote hoeveelheden punten op een efficiënte manier te verwerken. Een van de veelvoorkomende operaties is bijvoorbeeld de triangulatie van een puntenwolk, waarbij een driehoekig rooster wordt opgesteld bestaande uit driehoekige facetten. Zo een triangulatie is een handige voorstelling van het object, omdat het topologische informatie bevat (zoals gaten en randen) en is gemakkelijk om mee te werken. In deze thesis trachten we de vraag naar puntenwolkverwerkingstechnieken te beantwoorden en stellen een aantal nieuwe algoritmen voor. In het bijzonder behandelen we enkele fundamentele topics in puntenwolkverwerking: triangulatie, vereffening en randbepaling. We analyseren de algoritmen vanuit het standpunt van efficiëntie, praktische toepasbaarheid en de volledigheid van de onderliggende theorie.

Academic collection --- 681.3*G13 <043> --- 681.3*I3 <043> --- 519.65 <043> --- 681.3*I3 <043> Computer graphics (Computing methodologies)--Dissertaties --- Computer graphics (Computing methodologies)--Dissertaties --- Numerical linear algebra: conditioning; determinants; eigenvalues and eigenvectors; error analysis; linear systems; matrix inversion; pseudoinverses; singular value decomposition; sparse, structured, and very large systems (direct and iterative methods)--Dissertaties --- Approximation. Interpolation--Dissertaties --- Theses