Normal estimation of very large point clouds

Abstract

In dieser Diplomarbeit werden Methoden vorgestellt um extern sortieren und um schnell die k nächsten Nachbarn in sehr großen Punktwolken finden zu können.<br />Wobei sehr große Punktwolken jene Datensätze sind die nicht komplett im Hauptspeicher verarbeitet werden können. Das führt zu einigen Anforderungen die von solchen Methoden erfüllt werden müssen. Die wichtigsten Anforderungen sind out-of-core Speicherverwaltung und sequentielle Datenverarbeitungsalgorithmen.<br />Die Arbeit "Stream-Processing Points" von Renator Pajarola zeigt einen Weg, um einen Entwurf so zu gestalten, dass nur eine kleine Menge der großen Punktwolke verarbeitet wird. Eine kleine Menge ist dabei definiert als eine räumlich kontinuierliche Region die eine vordefinierte Menge an Punkten beinhält. Diese Diplomarbeit basiert auf der vorher genannten Arbeit und verbessert den darin vorgestellten Datenstrom Verarbeitungsablauf. Der vorgeschlagene Algorithmus um die k nächsten Nachbarn zu finden hat eine Komplexität von O(N * log(M)), wobei N alle Punkte in der Punktwolke und M alle Punkte im Hauptspeicher sind, was gleich ist zu den im Hauptspeicher verarbeitenden Algorithmen die Stand der Technik sind.<br />

This diploma thesis introduces methods for external sorting and fast k nearest neighbor searching for very large point clouds. Very large point clouds are datasets that can not be processed in main memory. This leads to certain requirements for any used reconstruction technique. The most important ones are out-of-core memory management and sequential data handling algorithms. The paper ``Stream-Processing Points'' by Renato Pajarola shows a way to design a framework which allows to process a subset of very large point clouds. A subset is defined as a spatially continuous region holding a predefined number of points. This diploma thesis is based on the aforementioned paper and improves on the stream processing pipeline presented therein. The proposed algorithm for searching the k nearest neighbors has a complexity of O(N * log(M)), where N are all points in the point cloud and M are all points in main memory, which is similar to current state of the art algorithms for in-core processed data sets.