Iterative Closest Point Algorithm

Der Iterative Closest Point Algorithm (ICP) ist ein Algorithmus, der es ermöglicht, Punktwolken aneinander anzupassen. Für die Anwendung des Verfahrens müssen die Punktwolken bereits vorab näherungsweise aufeinander ausgerichtet sein.

Idee hinter dem Closest Point Algorithm

Algorithmus

Bei der Durchführung des Algorithmus wird versucht, die Punktwolken mittels Rotation und Translation möglichst gut miteinander in Deckung zu bringen. Ausgehend von einem Satz von näherungsweise bestimmten anfänglichen Transformationsparametern für Rotation und Translation wird dazu für jeden Punkt aus der einen Punktwolke der jeweils nächste Punkt (closest point) aus der anderen Punktwolke bestimmt. Anschließend wird die Summe S der Quadrate der Abstände über alle diese Punktepaare gebildet. Damit hat man ein Maß für die Güte der Übereinstimmung zwischen den Punktwolken. Das Ziel ist es, dieses Optimierungsmaß, also die vorstehende Summe S, durch die Veränderung der Transformationsparameter zu minimieren. Für die Bestimmung der geeigneten Transformationsparameter gibt es unterschiedliche Ansätze, die z. T. auf der Struktur der zugrundeliegenden Punktwolken basieren. In jedem Falle handelt es sich dabei um einen iterativen Prozess, der so lange fortgeführt wird, bis ein akzeptables Optimum gefunden ist.

• Schritt 0: Näherungsweises Bestimmen der anfänglichen Transformationsparameter für Rotation R(0) und Translation T(0)
• ...
• Schritt n.1: Anwendung der Transformation mit den Parametern R(n-1) und T(n-1)
• Schritt n.2: Für jeden Punkt aus der einen Punktwolke Bestimmung des jeweils nächstgelegenen Punktes (closest point) aus der anderen Punktwolke
• Schritt n.3: Berechnung der Summe S der Abstandsquadrate der vorgenannten Punktepaare
• Schritt n.4: Bestimmung von neuen Transformationsparametern R(n) und T(n) [abgeleitet aus der Struktur der Punktwolken]
• ...
• Abbruch der Iteration, wenn im n-ten Schritt die Summe S(n) eine definierte Schwelle unterschreitet.

Anwendungen

Der Algorithmus wird vor allem zur relativen Registrierung von Punktwolken verwendet, womit aus mehreren Punktwolken ein Gesamtmodell erzeugt werden kann. Die Einzelpunktwolken können dabei z. B. durch Laserscanning oder photogrammetrische Verfahren der automatischen Bildzuordnung (dense image matching) erzeugt werden.

Ein weiteres Anwendungsgebiet ist die Lokalisierung in der Robotik, ein Teilproblem von Simultaneous Localization and Mapping.

Weblinks

• PCL (Point Cloud Library) ist ein Open-Source-Framework für n-dimensionale Punktwolken und 3D-Geometrieverarbeitung. Es umfasst mehrere Varianten des ICP-Algorithmus.
• FastICP paper – Vergleich verschiedener ICP-Varianten (PDF-Datei; 784 kB)
• Grundlage für ICP – Das Überführen von Koordinatensystemen ineinander mit Hilfe von Quaternionen (PDF-Datei; 1,6 MB)