Iteracyjny najbliższy punkt
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
[edytuj | edytuj kod]Wejście: dwa zbiory punktów, początkowe oszacowanie transformacji, kryterium zatrzymania algorytmu.
Wyjście: macierz transformacji.
Zasadnicze kroki algorytmu:
- sparowanie punktów między dwoma skanami według wybranego kryterium,
- oszacowanie parametrów transformacji minimalizującej błąd średniokwadratowy, wyznaczony na podstawie wzajemnej odległości sparowanych punktów,
- transformacja jednej z chmur według oszacowanej macierzy transformacji,
- powrót do początku algorytmu, jeżeli błąd dopasowania obu chmur punktów jest powyżej zadanego kryterium.