Iteracyjny najbliższy punkt
Iteracyjny najbliższy punkt ( ICP ) to algorytm stosowany w celu zminimalizowania różnicy między dwiema chmurami punktów . ICP jest często używany do rekonstrukcji powierzchni 2D lub 3D z różnych skanów, do lokalizacji robotów i uzyskania optymalnego planowania ścieżki (zwłaszcza gdy odometria koła jest niewiarygodna ze względu na śliski teren), do wspólnej rejestracji modeli kości itp.
Przegląd
Algorytm iteracyjnego najbliższego punktu utrzymuje stałą chmurę punktów, odniesienie lub cel, podczas gdy druga, źródło, jest przekształcana tak, aby jak najlepiej pasowała do odniesienia. Transformacja (kombinacja translacji i rotacji) jest szacowana iteracyjnie w celu zminimalizowania metryki błędu, zazwyczaj sumy kwadratów różnic między współrzędnymi dopasowanych par. ICP jest jednym z szeroko stosowanych algorytmów wyrównywania modeli trójwymiarowych, biorąc pod uwagę wstępne odgadnięcie sztywnej transformacji . Algorytm ICP został po raz pierwszy wprowadzony przez Chena i Medioniego oraz Besla i McKaya.
Algorytm iteracyjnego najbliższego punktu różni się od algorytmu Kabscha i innych rozwiązań ortogonalnego problemu Procrustesa tym, że algorytm Kabscha wymaga zgodności między zbiorami punktów jako danych wejściowych, podczas gdy iteracyjny najbliższy punkt traktuje zgodność jako zmienną do oszacowania.
Dane wejściowe: chmury punktów referencyjnych i źródłowych, wstępne oszacowanie transformacji w celu dopasowania źródła do odniesienia (opcjonalnie), kryteria zatrzymania iteracji.
Wynik: udoskonalona transformacja.
Zasadniczo kroki algorytmu to:
- Dla każdego punktu (z całego zestawu wierzchołków określanego zwykle jako gęsty lub wybranych par wierzchołków z każdego modelu) w źródłowej chmurze punktów dopasuj najbliższy punkt w referencyjnej chmurze punktów (lub wybranym zbiorze).
- Oszacuj kombinację rotacji i translacji za pomocą techniki minimalizacji metryki odległości od punktu do punktu, która najlepiej dopasuje każdy punkt źródłowy do jego dopasowania znalezionego w poprzednim kroku. Ten krok może również obejmować ważenie punktów i odrzucanie wartości odstających przed wyrównaniem.
- Przekształć punkty źródłowe, korzystając z uzyskanej transformacji.
- Iteruj (ponownie powiąż punkty itd.).
Zhang proponuje zmodyfikowany algorytm drzewa k -d dla wydajnego obliczania najbliższego punktu. W tej pracy metoda statystyczna oparta na rozkładzie odległości jest stosowana do radzenia sobie z wartościami odstającymi, okluzją, pojawianiem się i znikaniem, co umożliwia dopasowanie podzbioru do podzbioru.
Istnieje wiele wariantów ICP, z których najpopularniejsze są połączenia punkt-punkt i punkt-płaszczyzna. Ten ostatni zwykle działa lepiej w środowiskach ustrukturyzowanych.
Implementacje
- MeshLab to narzędzie do przetwarzania siatki o otwartym kodzie źródłowym, które obejmuje implementację algorytmu ICP na licencji GNU General Public License.
- CloudCompare to otwarte narzędzie do przetwarzania punktów i modeli, które zawiera implementację algorytmu ICP. Wydany na licencji GNU General Public License.
- PCL (Point Cloud Library) to platforma typu open source do n-wymiarowych chmur punktów i przetwarzania geometrii 3D. Zawiera kilka wariantów algorytmu ICP.
- Otwarte implementacje C++ algorytmu ICP są dostępne w bibliotekach VTK , ITK i Open3D .
- libpointmatcher to implementacja ICP point-to-point i point-to-plane wydana na licencji BSD.
- simpleICP to implementacja dość prostej wersji algorytmu ICP w różnych językach.