Wykryj wzory kołowe w danych chmury punktów

10

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):

wprowadź opis zdjęcia tutaj

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ę.

Cjauvin
źródło
Prostsze pytanie: jak poszedłbyś w sprawie wykrywania segmentów linii w danych dwuwymiarowych?
charles.y.zheng
„.. jak te w przykładach”? Jakie przykłady Czy możesz dodać link?
onestop
Transformacja Hougha jest oczywistym wyborem. Powinno działać dobrze.
whuber
Tymczasem mam wystarczającą reputację, aby dodać przykład obrazu, o którym mówiłem.
cjauvin
3
To nie jest problem klastrowania. W statystyce „klastry” składają się ze zbiorów obiektów, które są do siebie bliższe niż inne obiekty. Bliskość nie uchwyca okrągłości: dlatego ani K-średnie, ani żaden inny algorytm grupowania nie będą działać. Z tego powodu to pytanie prawdopodobnie lepiej pasuje do przetwarzania obrazu lub witryn GIS, gdzie można znaleźć ekspertów w tej kwestii.
whuber

Odpowiedzi:

9

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.

Whuber
źródło
Spróbowałbym połączyć wszystkie sugerowane podejścia: pierwszy klaster oparty na samej odległości, jak omówiono w oryginalnym plakacie, który da ci klastry, które mogą składać się z wielu kręgów. Następnie użyj Hougha, aby wykryć podzbiory planarne w każdym klastrze. Następnie w każdym podzbiorze planarnym ponownie użyj Hougha, aby znaleźć koła. Jeśli ten ostatni krok jest kosztowny, być może uda ci się wykonać skuteczne zwieranie: spróbuj kilku potrójnie, zgadnij koło i sprawdź, czy znaczna część punktów w twoim podzbiorze leży bardzo blisko tego okręgu. Jeśli tak, zapisz to koło i usuń wszystkie te punkty, a następnie kontynuuj.
Erik P.
3
Ten ostatni pomysł nazywa się RANSAC i prawdopodobnie mógłby być używany samodzielnie, zwłaszcza jeśli liczba kół na obrazie jest niewielka.
SheldonCooper
Dzięki za wspaniałe pomysły! Wielostopniowa transformacja Hougha wydaje mi się najmocniejszym i najogólniejszym rozwiązaniem, ale RANSAC naprawdę wygląda na łatwiejszy do wdrożenia i może być wystarczający w moim kontekście. Jednym z problemów, który szybko z tym zauważyłem, jest przypadek, w którym masz wzory o niezrównoważonych rozmiarach, co oczywiście przesuwa próbkowanie w kierunku większych obiektów. Masz jakieś przemyślenia na temat tego problemu?
cjauvin
Po wykryciu większego koła usuń z niego wszystkie punkty, które do niego należą.
SheldonCooper
0

numer

sdgaw erzswer
źródło