Iteracyjny najbliższy punkt

Ilustracja algorytmu iteracyjnego najbliższego punktu

Iteracyjny najbliższy punkt, ICP (ang. Iterative Closest Point) – algorytm stosowany w celu zminimalizowania różnicy między dwiema chmurami punktów. ICP jest powszechnie stosowany do rekonstrukcji trójwymiarowego otoczenia na podstawie serii jego skanów, na przykład w architekturze do łączenia kolejnych skanów budynków, celem utworzenia ich pełnego modelu 3D, w lokalizacji robotów, zwłaszcza do aktywnego planowania trasy (zazwyczaj tam, gdzie odometria jest niewiarygodna ze względu na śliski teren) itp.

Algorytm jest bardzo prosty i jest powszechnie stosowany. Niestety dla części zastosowań jest zdecydowanie za wolny.

Działanie

Wejście: dwa zbiory punktów, początkowe oszacowanie transformacji, kryterium zatrzymania algorytmu.

Wyjście: macierz transformacji.

Zasadnicze kroki algorytmu:

1. sparowanie punktów między dwoma skanami według wybranego kryterium,
2. oszacowanie parametrów transformacji minimalizującej błąd średniokwadratowy, wyznaczony na podstawie wzajemnej odległości sparowanych punktów,
3. transformacja jednej z chmur według oszacowanej macierzy transformacji,
4. powrót do początku algorytmu, jeżeli błąd dopasowania obu chmur punktów jest powyżej zadanego kryterium.