Parameter Optimization at the example of Surface Reconstruction

Abstract

In dieser Arbeit vergleichen wir unterschiedliche Algorithmen zur Parameter-Optimierung am Beispiel von Screened Poisson Surface Reconstruction. Um dies zu erreichen, implementierten wir zuerst fünf aktuelle Algorithmen. GEIST ist ein Graphen-basierter Algorithmus, der den Parameter-Raum in einen `optimalen' und einen `nicht-optimalen' Bereich aufteilt um die nächsten Konfigurationen auszuwählen. Iterated F-Race platziert eine Normalverteilung für die Auswahl der nächsten Konfigurationen über die besten Konfigurationen der letzten Iteration. ParamILS verwendet iterative lokale Suche um einen besseren Nachbarn zu finden und damit schlussendlich ein Optimum. PostSelection verwendet eine verkürzte Version eines Algorithmus um vielversprechende Kandidaten zu finden, und eine detailliertere Version um diese auszuwerten. Als simplen Vergleich implementierten wir außerdem eine Version von Brute-Force.Für alle diese Algorithmen führen wir zuerst eine Reihe an Tests durch um eine gute Konfiguration für deren Ausführung zu finden. Danach testen wir sie an Punktwolken aus zwei Datensets. Jedes Datenset enthält alle Wolken in unterschiedlichen Qualitäten, wir sind also in der Lage unterschiedliche Input Qualitäten als auch Typen zu testen. Wir zeigen, dass jeder der implementierten Algorithmen in der Lage ist bessere Parameter-Konfigurationen zu finden als den Screened Poisson Surface Reconstruction Standard. In den meisten Fällen erreichen GEIST und PostSelection die besten Resultate, brauchen dafür aber auch am längsten. ParamILS und Iterated F-Race führen zu guten Resultaten in einer deutlich kürzeren Zeit. Brute-Force ist nicht konkurrenzfähig wenn es um hochqualitative Konfigurationen geht, verbessert aber noch immer den Standard in den meisten Fällen.Um unsere Resultate über verschiedene Typen und Qualitäten zusammenzufassen kann man sagen, dass die Standardkonfiguration akzeptable, aber nicht ideale, Ergebnisse für Punktwolken von glatten Objekten mit wenigen Störungen erzielt. Wir schlagen eine Alternative hierführ vor. Ist die Oberfläche rauer so muss idealerweise das Gewicht stärker auf die Position der Punkte gelegt werden. Gibt es sehr viele Störungen in den Daten, so muss dieses Gewicht und die Octree Tiefe reduziert werden.Wir diskutieren die Vorteile und Nachteile von jedem implementierten Algorithmus und vergleichen ihre Resultate um empfehlen zu können welchen man verwenden sollte. Wir beschreiben unsere Implementierung von jedem und beschreiben kurz was an weiterer Arbeit verrichtet werden könnte um diese Arbeit zu erweitern. Zum Schluss geben wir Empfehlungen ab, welche Konfiguration für welche Typen und Punktwolken verwendet werden sollten. Für sehr genaue Daten sollten depth und pointWeight höher gewählt werden, als für ungenaue. Ist die Topologie des Objekts sehr komplex, dann sollte pointWeight sehr hoch eingestellt werden. Wir kommen zu dem Schluss, dass in den meisten Fällen IF-Race der beste Kompromiss zwischen Geschwindigkeit und Rekonstruktionsqualität ist. Wenn die Laufzeit kein relevanter Faktor ist, dann stellt GEIST eine Alternative dar, die sehr hoch qualitative Ergebnisse liefert.

In this thesis, we compare different parameter-optimization algorithms on the example of Screened Poisson Surface Reconstruction. To do this, we first implemented five state-of-the-art algorithms. GEIST is a graph-based algorithm that splits the parameter space into an `optimal' and a `non-optimal' set to select new configurations. Iterated F-Race places a normal distribution of selection probabilities on the best configurations of the last iteration and uses that to choose the next configurations. ParamILS uses iterative local search to select a better neighbor and find an optimum this way. PostSelection uses a shortened version of an algorithm to find promising candidates and a second, more detailed one to evaluate these. As a simple baseline we also implemented Brute-Force.For all of these algorithms, we first conduct several tests to find a good configuration to run them with. After that, we test them on point clouds from two datasets. Each dataset contains each cloud in different qualities, so we are able to test varying input qualities as well as types. We show that each of the implemented algorithms is able to find better parameter configurations than the default Screened Poisson Surface Reconstruction configuration. In most cases, GEIST and PostSelection lead to the best results but also have the longest run times, while ParamILS and Iterated F-Race lead to good results in a far shorter time period. Brute-Force is not competitive when it comes to high-quality configurations, but still leads to an improvement over the default in most cases.To summarize the results over different types and qualities, the default configuration yields acceptable but not ideal results for point clouds of smooth meshes with little noise and we suggest an alternative. If the surface is rougher, the importance weight of the points should ideally be set higher. If there is a lot of noise, this weight as well as the Octree depth should be reduced.We discuss the advantages and disadvantages of each implemented algorithm and compare their results to recommend which one to use. We describe our implementations of each and quickly mention what work could be done to expand on this thesis. Finally, we give recommendations as to which configurations to use for different types of point clouds. For data with higher accuracy, depth and pointWeight should be higher than for data with lower accuracy. If the topology of the object is very complex, pointWeight is best set very high in comparison to simpler point clouds. We find that for most cases, IF-Race is the best compromise to use between speed and resulting quality of reconstruction. If time is of no concern, GEIST is an alternative that yields high-quality results.