Super 4PCS: Schnelle globale Punktwolken-Registrierung über intelligente Indizierung

Die Datenerfassung in großflächigen Szenen erfordert regelmäßig die Akkumulation von Informationen über mehrere Scans hinweg. Ein verbreiteter Ansatz besteht darin, Scan-Paare lokal mittels des Iterative Closest Point (ICP)-Algorithmus (oder seiner Varianten) auszurichten; dies setzt jedoch statische Szenen und kleine Bewegungen zwischen den Scan-Paaren voraus. Dies erschwert die Akkumulation von Daten über mehrere Scansessionen und/oder unterschiedliche Erfassungsmodalitäten (z. B. Stereo-, Tiefenscans). Alternativ kann ein globales Registrierungsverfahren verwendet werden, das Scan-Daten in beliebigen Ausgangsposen zulässt. Der derzeitige Stand der Technik im Bereich der globalen Registrierung, der 4PCS-Algorithmus, weist jedoch eine quadratische Zeitkomplexität in der Anzahl der Datenpunkte auf. Dies begrenzt seine Anwendbarkeit erheblich bei der Erfassung großer Umgebungen. Wir präsentieren Super 4PCS für die globale Punktwolkenregistrierung, das optimal ist, d. h. linear in der Anzahl der Datenpunkte läuft und zudem output-sensitiv ist bezüglich der Komplexität des Ausrichtungsproblems aufgrund des (unbekannten) Überlappungsgrades zwischen den Scan-Paaren. Technisch betrachtet, modellieren wir den Algorithmus als „Instanzproblem“ und lösen ihn effizient durch eine intelligente Indexierungsdatenorganisation. Der Algorithmus ist einfach, speichereffizient und schnell. Wir zeigen, dass Super 4PCS gegenüber alternativen Ansätzen eine erhebliche Beschleunigung ermöglicht und eine unstrukturierte, effiziente Erfassung von Szenen in bisher nicht möglichen Größenordnungen erlaubt. Der vollständige Quellcode und die verwendeten Datensätze sind für Forschungszwecke unter http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/ verfügbar.