Iterative Closest Point Algorithm

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Racine carrée bleue.svg
Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen.

Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion! (Artikel eintragen)

Der Iterative Closest Point Algorithm 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.

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ächstliegenden 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.

Der Algorithmus wird vor allem zur relativen Orientierung (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[Bearbeiten | Quelltext bearbeiten]