Shape Shifting: A Multiscale Optimal Transport Approach to 3D Point Cloud Comparison

Abstract

Fortschritte in der Vermessungstechnik und der dreidimensionalen Bildverarbeitung haben die Geschwindigkeit und Präzision, mit der Objekte und Landschaften in der realen Welt eingefangen und rekonstruiert werden können, erheblich verbessert. Diese virtuellen Rekonstruktionen sind relevant für Vermessungsanwendungen und werden häufig als Punktwolken abgespeichert, d.h., eine Reihe von 3D Koordinaten, mit optionalen zusätzlichen Attributen wie Farben und Normalen. Häufig werden solche Rekonstruktionen mehrmals über einen längeren Zeitraum hinweg aufgenommen, um Veränderung einzufangen. Intuitive vergleichende Visualisierungen können dabei helfen den Wandel dieser Rekonstruktionen zu veranschaulichen. Jedoch bergen die Ausmaße solcher Daten Herausforderungen für Methoden der Visualisierung. Des Weiteren ist es einfacher denn je, große Datensätze solcher Rekonstruktionen zu sammeln, selbst für unerfahrene Anwender. Jedoch gibt es abseits der zeitintensiven Algorithmen, die für den medizinischen Bereich konzipiert sind, wenige Anwendungen die ermöglichen Unterschiede in solchen Ensembles von Formen zu vergleichen. Die verfügbaren Algorithmen basieren auf Nachbarschaftsbeziehungen, welche bei der Anwendung mit komplexen Formen nicht gut skalieren und keine Strukturierung der Daten unterstützen. Umfangreiche Ensembles von räumlichen Daten zu ordnen kann die Analyse vereinfachen, wenn keine chronologische Sortierung vorliegt.Wir haben ein Framework entworfen und implementiert, um die vergleichende Visualisierung von Ensembles von Punktwolken zu unterstützen. Wir nutzen dafür die umfangreiche mathematische Theorie des optimalen Transports und umgehen damit die Nachteile von Ansätzen, die auf Nachbarschaftsbeziehungen basieren. Wenn es keine implizite Reihenfolge der Daten gibt, ermöglicht unsere Methode das automatische Arrangieren der einzelnen Punktwolken, um Beziehungen zwischen ihnen herzustellen und die Analyse zu vereinfachen. Die visuelle Hervorhebung von Abweichungen innerhalb der Daten erleichtert das Auffinden von Mustern. Durch das Nutzen von massiv parallelen Implementierungen ermöglichen wir einen animierten Übergang zwischen den Punktwolken. Die visuelle Betonung von Charakteristiken und Veränderungen jeder einzelnen Form unterstützt dabei die Klarheit der Visualisierung. Unsere Methode prozessiert die Daten schnell und bietet eine umfangreiche Auswahl an Werkzeugen, um ein ganzes Ensemble von Punktwolken zu analysieren.

Advances in measurement technologies and 3D vision have significantly enhanced the speed and precision with which real-world objects and landscapes can be captured and reconstructed. These virtual reconstructions are relevant for surveying applications and are often encoded as point clouds, i.e., a set of 3D coordinates, possibly accompanied by additional attributes like colors or normals. Often, reconstructions of objects or landscapes are acquired over time to monitor their changes. Intuitive visualization that allows one to comprehend the shifts over time in such reconstructions could be of help, but the vast size of the data imposes challenges on comparative visualization pipelines. On the other hand, it is simpler than ever to amass numerous reconstructions of real-world objects, even for novice users. Still, outside of computationally intensive algorithms tailored to applications for the medical domain, there is a gap in approaches that allow for comparing differences within ensembles of shapes. Available algorithms outside of medicine are built upon nearest neighbor queries, which do not scale well to complex shapes and lack guidance for the comparison. Extensive ensembles of spatial data need to be delivered in a structured way to avoid time-intensive manual ordering when there is no chronological ordering implied or known. We designed and implemented a framework to support the comparative visualization of ensembles of point clouds. By utilizing the mature mathematical framework of optimal transport, we circumvent shortcomings of commonly employed nearest neighbor-based approaches and allow our method to compare a whole ensemble of reconstructions in a comprehensive representation. If there is no inherent ordering, our method enables the automatic arrangement of individual point clouds, establishing their relationships and simplifying the analysis process. We derive additional metrics about the whole ensemble, which are then used to enrich the visualization and help to detect patterns of variation within the data. By leveraging fast GPU-based implementations, we enable a smooth transition between displayed point clouds in an animation and offer visual aids that highlight the characteristics of each shape and how these change. Our method processes the data fast and provides comprehensive means to browse through a large ensemble of point clouds.