Bestimmung der Punktpaare

Der erste Schritt des ICP-Algorithmus verfolgt das Ziel, Punktpaare zu ermitteln. Für jeden Punkt der Menge $D$ muss der nächste Punkt in der Menge $M$ bestimmt werden. Abbildung 3.2 zeigt zwei Scans des Flurs im FhG-AIS Gebäude C2, wobei der zweite Scan 2 Meter ,,hinter`` dem ersten liegt. Streng genommen liegt der zweite Scan im ersten. Die Scanpunkte des ersten Scans sind schwarz, die des zweiten blau dargestellt. Zu jedem Punkt des zweiten Scans wurde der nächstgelegene im ersten Scan bestimmt und die Verbindung der beiden Punkte durch eine rote Linie gekennzeichnet. Die größere Punktdichte im Überlappungsbereich lässt sich dadurch erklären, dass der zweite Scan im ersten liegt. Auch müssen sich aus diesem Grund mehrere Punkte des zweiten Scans einen Punkt des ersten Scans als nächsten Punkt teilen, wie die vergrößerten Ausschnitte in der Abbildung zeigen.

Abbildung 3.2: Die nächsten Punkte zweier Scans. Links oben: Zwei Scans, zweiter Scan 2 Meter in $z$-Richtung aufgenommen. Rechts oben: Die nächsten Punkte sind durch eine rote Linie verbunden. Unten: Vergrößerte Ausschnitte.

Die Performanzanalyse des ICP-Algorithmus hat gezeigt, dass seine Geschwindigkeit von der Suche nach den Punktpaaren dominiert wird. Dies ist der zeitaufwendigste Schritt des ICP-Algorithmus. Daher setzen alle Optimierungsversuche dort an. Zwei sich nicht ausschließende Strategien können hierbei verfolgt werden:

Reduktion der Punkte.

Es werden nur Teilmengen der ursprünglichen Punktmengen betrachtet. Sowohl das im Folgenden vorgestellte Verfahren (Scanmatching mit REDUZIERTEN PUNKTEN) als auch das kantenbasierte Matching (Kapitel 3.4) wenden diese Strategie an.

Beschleunigung des Datenzugriffs.

Verschiedene Datenstrukturen, wie beispielsweise mehrdimensionale Binärbäume oder Buckets, beschleunigen den Zugriff auf die gesuchten
nächsten Punkte.