Wykryj wzory kołowe w danych chmury punktów

W przypadku niektórych algorytmów rekonstrukcji objętości, nad którymi pracuję, muszę wykryć dowolną liczbę wzorów kołowych w danych punktów 3d (pochodzących z urządzenia LIDAR). Wzory mogą być dowolnie zorientowane w przestrzeni i można założyć, że leżą (choć nie idealnie) w cienkich płaszczyznach 2D. Oto przykład z dwoma okręgami na tej samej płaszczyźnie (choć pamiętaj, że jest to przestrzeń 3D):

Próbowałem wielu podejść .. najprostszym (ale tym, który działa najlepiej do tej pory) jest grupowanie oparte na rozłącznych zestawach wykresu najbliższego sąsiedztwa. Działa to dość dobrze, gdy wzory są daleko od siebie, ale mniej w przypadku okręgów takich jak w przykładzie, bardzo blisko siebie.

Próbowałem K-średnich, ale nie robi to dobrze: podejrzewam, że ustawienie punktu okrągłego może nie być do tego odpowiednie. Dodatkowo mam dodatkowy problem, że nie znam z góry wartości K.

Próbowałem bardziej skomplikowanych podejść, opartych na wykrywaniu cykli na wykresie najbliższego sąsiada, ale otrzymałem albo zbyt delikatne, albo kosztowne obliczeniowo.

Czytałem również o wielu powiązanych tematach (transformacja Hougha itp.), Ale nic nie wydaje się idealnie pasować w tym konkretnym kontekście. Doceniamy każdy pomysł lub inspirację.

Uogólniona transformacja Hougha jest dokładnie tym, czego chcesz. Trudność polega na tym, aby zrobić to skutecznie, ponieważ przestrzeń okręgów w 3D ma sześć wymiarów (trzy dla środka, dwa dla zorientowania płaszczyzny, jeden dla promienia). Wydaje się, że wyklucza to bezpośrednie obliczenia.

Jedną z możliwości jest przemycenie wyniku przez sekwencję prostszych transformacji Hougha. Na przykład możesz zacząć od (zwykłej) transformacji Hougha, aby wykryć podzbiory planarne: do obliczeń wymagają one tylko siatki 3D. Dla każdego wykrytego płaskiego podzbioru wytnij oryginalne punkty wzdłuż tej płaszczyzny i wykonaj uogólnioną transformację Hougha w celu wykrycia okręgu. Powinno to działać dobrze, pod warunkiem, że oryginalny obraz nie ma wielu współpłaszczyznowych punktów (innych niż te utworzone przez koła), które mogłyby zagłuszyć sygnał generowany przez koła.

Jeśli rozmiary kół mają ustaloną górną granicę, możesz potencjalnie zaoszczędzić wiele obliczeń: zamiast patrzeć na wszystkie pary lub trzy punkty punktów na oryginalnym obrazie, możesz skupić się na parach lub potrójnych granicach w obrębie ograniczonego sąsiedztwa każdego punktu.

$\textit{number}$