Farthest Point Sampling

Auch genannt: FPS, furthest point sampling
Kategorie: Sensing › Perception outputs
Schlagwörter: point-cloud, sampling, 3d-perception, preprocessing, deep-learning

Ein gieriges Verfahren, um eine feste Zahl von Punkten aus einer Punktwolke so auszuwählen, dass sie sich gleichmäßig über die Form verteilen, indem wiederholt der Punkt gewählt wird, der am weitesten von den bereits gewählten entfernt ist.

Definition

Farthest Point Sampling (FPS) wählt aus einer Menge von N Punkten eine Teilmenge von M Punkten aus. Es beginnt mit einem Punkt, zufällig gewählt oder fest vorgegeben, und fügt in jedem Schritt den Punkt hinzu, dessen Abstand zu seinem nächstgelegenen bereits ausgewählten Punkt am größten ist. Eine Implementierung speichert für jeden Eingabepunkt seinen Abstand zum nächstgelegenen ausgewählten Punkt und aktualisiert diesen Wert nach jeder Hinzufügung, sodass der Aufwand mit N mal M wächst. Das Ergebnis deckt die ganze Form gleichmäßig ab, unabhängig von der Dichte der ursprünglichen Abtastung. Dieselbe gierige Regel ist die klassische 2-Approximation für das k-Center-Clustering-Problem, angegeben von Gonzalez im Jahr 1985.

Im Deep Learning auf Punktwolken wurde FPS durch PointNet++ bekannt, das damit in jeder Schicht die Zentren lokaler Nachbarschaften wählt, und viele spätere Netze nutzen es, um Eingabewolken vor der Inferenz auf eine feste Größe herunterzurechnen. Verglichen mit zufälliger Abtastung, die der Dichte der Eingabe folgt und dünne oder spärlich beobachtete Teile verfehlen kann, erhält FPS die Abdeckung des ganzen Objekts. Verglichen mit Voxelgitter-Downsampling liefert es eine exakte Zahl von Punkten, die Netze mit festen Eingabegrößen benötigen.

FPS hat Zielkonflikte. Es bevorzugt bewusst Ausreißer: Ein isolierter Rauschpunkt ist weit von allem anderen entfernt und wird früh gewählt, daher werden Wolken normalerweise zuerst gefiltert. Das Verfahren ist sequenziell, was es bei sehr großen Wolken langsam macht; GPU-Implementierungen parallelisieren die Abstandsaktualisierungen innerhalb jedes Schritts, und approximative Varianten arbeiten auf räumlichen Partitionen. Die Ausgabe hängt vom Startpunkt ab, und auf Netzen messen geodätische Varianten den Abstand entlang der Oberfläche statt auf geraden Linien.

Warum es wichtig ist

Punktwolkennetze brauchen Eingaben fester Größe, und Tiefensensoren erzeugen weit mehr Punkte, als sie verarbeiten können. Gleichmäßige Abdeckung bedeutet, dass kleine, aber wichtige Teile wie Griffe, Ränder und Ausgüsse das Downsampling überstehen, was für die Vorhersage von Griffen und Affordanzen wichtig ist.

Wichtige Anwendungen

Vorverarbeitung von Punktwolken auf eine feste Größe für neuronale Netze
Wahl von Nachbarschaftszentren in hierarchischen Punktnetzen
Downsampling von Wolken vor der Berechnung der Chamfer- oder Earth-Mover's-Distanz
Auswahl gut verteilter Kandidatenpunkte für Griffe oder Kontakte
Auswahl vielfältiger Keypoints oder Stichproben für die Abdeckung

In der Praxis

Eine Tiefenkamera über einer Werkbank erzeugt pro Bild mehrere hunderttausend Punkte. Die Pipeline schneidet den Arbeitsbereich zu, entfernt statistische Ausreißer, führt ein Voxel-Downsampling durch, um den Aufwand zu senken, und wendet dann FPS an, um genau die Zahl von Punkten zu erhalten, mit der das Netz trainiert wurde, etwa 2048. Das Team verwendet im Training und auf dem Roboter dasselbe Abtastverfahren, denn ein auf FPS-abgetasteten Wolken trainiertes Netz sieht eine andere Punktverteilung als eines, das auf Zufallsstichproben trainiert wurde.

Häufige Missverständnisse

FPS liefert eine gleichverteilte Zufallsstichprobe — es ist deterministisch, sobald der Startpunkt feststeht, und verteilt Punkte gleichmäßig im Raum, statt zufällig abzutasten
FPS ist robust gegenüber Rauschen — Ausreißer sind weit von allem anderen entfernt und werden früh gewählt, daher werden Wolken normalerweise zuerst gefiltert
FPS erhält die Dichteinformation des Scans — es gleicht die Dichte bewusst aus, was der Abdeckung hilft, aber den Hinweis darauf entfernt, wo der Sensor mehr Punkte gesehen hat

Wer das wissen sollte

Ingenieure für 3D-Wahrnehmung
Machine-Learning-Forschende, die an Punktwolkennetzen arbeiten
Manipulationsingenieure, die Punktwolken-Policies einsetzen

Open Source Robotics