Quantitative evaluation of irregular sampling methods
Final Report Abstract
Schon seit den 80er Jahren werden zur Vermeidung von Aliasing-Artefakten irreguläres Sampling verwendet. Anfangs gab es hauptsächlich drei verschiedene Muster zum Abtasten: Zufälliges Sampling, stratifiziertes Sampling (zufälliges Sampling mit gegebener Punktdichte pro Flache) und Poisson-Disk Sampling. Wegen der herausragenden Qualität wurde besonderes Augenmerk auf das Poisson-Disk Sampling gerichtet. Ziel dieser Verteilung ist, Punkte unregelmäßig aber mit bestimmtem Mindestabstand zu verteilen. Diese Verteilung kommt nicht nur beim Sampling vor, sondern schon bei vorherigen Arbeiten, wie z.B. beim nicht-photorealistischem Rendering oder bei der Objektverteilung oder Textursynthese. Die Erzeugung von Punktemengen mit Poisson-Disk Eigenschaft ist aber nicht einfach. Erste Methoden beruhen auf dart throwing, wobei Punkte schrittweise zufällig erzeugt werden und nur die Punkte behalten werden, die diesen Mindestabstand zu den anderen Punkten nicht unterschreiten. Hierbei verlängert sich jedoch die Rechenzeit pro hinzugefügtem Punktesatz, da immer mehr Punkte dieses Kriterium nicht erfüllen und somit immer mehr Punkte wieder gelöscht werden. Da die Anzahl an bisher entstandenen Algorithmen sehr groß ist, wurde im ersten Arbeitspaket eine Datenbasis erstellt. In dieser wurden verschiedene State of the Art-Algorithmen gespeichert bzw. implementiert. Diese dient hauptsächlich dazu, eine Datenbank an Samplingmustern, Rekonstruktionsverfahren und Testszenen aufzubauen, um später Vergleiche mit diesen durchzuführen. Teilweise konnte hier auf vorige Arbeiten zurückgegriffen werden. Darüber hinaus werden diese dann in den weiteren Schritten dazu verwendet, einen empirischen Vergleich herzustellen. Desweiteren wurden quantitative Evaluationsmethoden der Qualität von Bildern untersucht. Dies diente dazu, eine Evaluationsmethode auszuwählen, um Abtastmuster, die in einem späteren Arbeitspaket erstellt werden, in Bezug auf diese Evaluationsmethode zu optimieren. Um strukturierte Bildfehler, wie Moire-Patterns zu unterdrücken, werden in der Computergraphik irreguläre Abtastmuster verwendet. Im Allgemeinen ging es im dritten Arbeitspaket darum, dass untersucht wird, ob und inwiefern die Bildqualität verbessert werden kann, die durch irreguläre Abtastverfahren erzeugt wurden. Durch die Arbeit, die ein Maß für lokales Rauschen entwickelte, konnten weitere Methoden zur Rauschunterdrückung erstellt werden. Im folgenden Arbeitspaket konnten dann die zuvor erworbenen Erkenntnisse verwendet werden, um neue Algorithmen zu entwickeln. Als Ausgangspunkt wurde hierbei eine Arbeit von Heck et al. (2013) gewählt, da die spektralen Konstruktionsmuster aus dieser Arbeit am erfolgversprechendsten waren. Mittels der vorangehenden Arbeitspakete war es möglich, gezielte Probleme zu lösen, um so einen Algorithmus zu erzeugen, der einerseits effizient ist und andererseits die Problematiken abdeckt, die durch die Quantifizierung der Qualität aufgedeckt wurde. Im speziellen ist dies bezogen auf die spektralen Eigenschaften der schon bestehenden Abtastmuster. Um die vorangehende Forschung zu vertiefen, wurden Projekte eingeleitet, den numerischen Fehler des Samplingverfahrens direkt in einen Zusammenhang mit den entstanden Aliasing Artefakten zu stellen. Aufbauend auf eine Sichtweise, welche diesen Zusammenhang mittels der Fourier Analyse anschnitt, konnten wir dieses Themenfeld weiter erörtern. Desweiteren und auch parallel zu diesem Arbeitspaket haben wir den Algorithmus effizient implementiert, um so auch zu überprüfen, ob die Entwicklung des Algorithmus relevante Vorteile bringt. Dies wurde mittels normalen Laufzeittests durchgeführt, um so abzuschätzen, in welchem Zeitverhältnis die Algorithmen, die in Arbeitspaket 2 implementiert wurden, zu den neu entwickelten Algorithmen stehen. Zusätzlich wurde dann noch die Qualität der Bilder ermittelt und verglichen.
Publications
- Aa patterns for point sets with controlled spectral properties. ACM Trans. Graph., 34(6):212:1– 212:8, October 2015
Abdalla G. M. Ahmed, Hui Huang, and Oliver Deussen
(See online at https://doi.org/10.1145/2816795.2818139) - Low-discrepancy blue noise sampling. ACM Trans. Graph., 35(6):247:1–247:13, November 2016
Abdalla G. M. Ahmed, Hélène Perrier, David Coeurjolly, Victor Ostromoukhov, Jianwei Guo, Dong-Ming Yan, Hui Huang, and Oliver Deussen
(See online at https://doi.org/10.1145/2980179.2980218) - A simple push-pull algorithm for blue-noise sampling. IEEE Transactions on Visualization and Computer Graphics, 23(12):2496–2508, Dec 2017
A. G. M. Ahmed, J. Guo, D. Yan, J. Franceschia, X. Zhang, and O. Deusse
(See online at https://doi.org/10.1109/TVCG.2016.2641963) - An adaptive point sampler on a regular lattice. ACM Trans. Graph., 36(4):138:1–138:13, July 2017
Abdalla G. M. Ahmed, Till Niese, Hui Huang, and Oliver Deussen
(See online at https://doi.org/10.1145/3072959.3073588) - Grid-Based Techniques for Semi-Stochastic Sampling. PhD thesis, Universität Konstanz, Konstanz, 2018
Abdalla G. M. Ahmed
