Wykrywanie osi obrotu z punktu obrotu

Question

Próbuję automatycznie wykryć oś obrotu w 3d pointcloud.

Innymi słowy, jeśli wziąłem mały trójwymiarowy punkt, wybrałem pojedynczą oś obrotu i wykonałem kilka kopii punktów pod różnymi kątami obrotu, wtedy dostanę większy pointcloud.

Dane wejściowe do mojego algorytmu to większa liczba punktów, a pożądanym wynikiem jest pojedyncza oś symetrii. I w końcu zamierzam obliczyć zależności pomiędzy punktami, które są wzajemnymi obrotami.

Rozmiar większego worka pointcloud jest rzędu 100K punktów, a liczba wykonanych kopii obrotowych jest nieznana.

Kąty obrotu w moim przypadku mają stałe delty, ale niekoniecznie rozciągają się o 360 stopni. Na przykład, mogę mieć 0, 20, 40, 60. Albo mogę mieć 0, 90, 180, 270. Ale nie będę miał 0, 13, 78, 212 (a jeśli tak, to nie obchodzi mnie to aby to wykryć).

Wydaje się, że jest to problem z widzeniem komputerowym, ale mam problem z ustaleniem osi. Dane wejściowe będą generalnie bardzo czyste, zbliżone do dokładności pływaka.

Nie mam oryginalnego mniejszego chmurki, która została obrócona/skopiowana, aby utworzyć większy punkt. Wiem, że dane są syntetyczne z bardzo niewielkim hałasem (generalnie jest to wynik innego programu).

Nie możemy łatwo obliczyć możliwych liczb punktów w mniejszej chmurze, ponieważ w prawo wzdłuż osi punkty nie są zdublowane, niestety. Gdybyśmy wiedzieli, które punkty znajdują się wzdłuż osi, moglibyśmy wymyślić możliwe czynniki, ale wtedy rozwiązalibyśmy problem.

-

Dziękuję wszystkim za sugestie. Wygląda na to, że mój ostateczny algorytm spróbuje wymyślić kliknięcia pasujących punktów za pomocą metryki k-nn. Każda klika da oś. Mogę następnie użyć RANSAC, aby dopasować oś do wyników wszystkich klik.

Answer 1

Cóż, poniższe podejście może być przydatne, ale zależy od konkretnych danych. Opiera się on na założeniach, że luka między sąsiednimi pozycjami jest wystarczająco duża (20 stopni jest prawdopodobnie w porządku), a mała chmura punktów zbliża się do powierzchni (ostatnia może zostać pokonana). Sugeruję użycie funkcji dopasowania lokalnego (popularna technika w wizji komputerowej).

Najpierw dla każdego punktu dużej chmury należy obliczyć lokalne deskryptory (np. SIFT lub SURF dla obrazów). Najbardziej popularny dla chmury punktów jest wirowania obraz:

Johnson, A., & Hebert, M. (1999). Używanie obrazów spinowych do efektywnego rozpoznawania obiektów w zagraconych scenach 3d. Transakcje IEEE w zakresie analizy wzoru i analizy automatycznej, 21 (5), 433-449. Citeseer. Źródło: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8816&rep=rep1&type=pdf.

Zaawansowany modyfikację używa się tutaj:

Endres, F. i Plagemann, C. Stachniss, C. & Burgard, W. (2009). Bez nadzoru Odnajdywanie klas obiektów z danych zakresu przy użyciu ukrytego przydziału Dirichleta. In Robotics: Science and Systems. Seattle, USA.

Jeśli będzie to trudne obliczeniowo, zapytaj mnie, jak zmniejszyć wymiarowość, nie tracąc wiele z mocy dyskryminacyjnej, zrobiłem to raz.

Następnie powinieneś dopasować deskryptory, tj. Znaleźć najbliższego sąsiada dla każdego z nich w ich wielowymiarowej przestrzeni. Jeśli mała chmura została obrócona 3 razy, powinno być 3 dobrych najbliższych sąsiadów. Jednak z powodu samo-skrzyżowań w chmurze mecze prawdopodobnie będą zawierać szum. Nadal musisz znaleźć oś, która pasuje do dużej ilości dopasowań (choć nie wszystkie). Tutaj możesz użyć solidnego dopasowania, takiego jak RANSAC (powinieneś trochę matematyki, aby zdefiniować prawdopodobieństwo pozycji osi w.r.t. znalezionych pasujących). Zauważ, że różni się od metod sugerowanych przez innych. Powinieneś zmieścić tylko jedną linię zamiast rodziny samolotów, bazując na deskryptorach, a nie na oryginalnych punktach (RANSAC prawdopodobnie nie będzie pasował do samolotu posiadającego 4-5 punktów poprawnych i 100K wartości odstających).

pamiętać również:

Jeśli masz małą skanowania, które nie przybliżają powierzchnię, trzeba wymyślić inny deskryptor rotacyjnie niezmienna, nie obracać obrazy.

Aby obliczyć liczbę normalną i pobrać dane, możesz przejrzeć tę bibliotekę: http://graphics.cs.msu.ru/en/science/research/3dpoint/lidark (główne wydanie już wkrótce).

Answer 2

1) Jeśli znajdziesz centroid C większej giełdy, ISTM oryginalna oś obrotu musiałaby przejść przez ten punkt.

Nieważne: nie widziałem wymogu, aby obroty nie obejmowały pełnego koła. Dla twojego 20,40,60 przykładu, środek ciężkości nie byłby na osi obrotu.

Może poniższy dokument mógłby pomóc?

„Przebudowa nawierzchni rewolucji z częściowego pobierania próbek” http://portal.acm.org/citation.cfm?id=980064

Answer 3

Niektóre punkty :)

1. Jeśli mamy 1 punkt początkowy nie obraca to istnieje nieskończona liczba osi.
2. Jeśli mamy 1 punkt początkowy obrócony 1 razy, to istnieje również nieskończona liczba osi.
3. Jeśli mamy 1 punkt początkowy i obracamy go 2 razy, wówczas możemy ustalić oś, ponieważ 3 punkty jednoznacznie określają płaszczyznę. Prostopadle do której przez punkt równo oddalony od każdego z 3 punktów (1 początkowy + 2 obrócony) jest oś.
4. Należy pamiętać, że obracanie przez 360 nie ma sensu.

---

1. wybrać jedno punktu (P) z chmury.
2. Śledzenie położenia (L) punktu P (gdy P obraca się wokół pewnej osi, L powinno być okręgiem)
3. Prostopadła do płaszczyzny koła (L) przechodzącej przez jego środek jest osią obrót chmury.

Co mam na myśli to, że oś obrotu sztywnego ciała jest taka sama jak oś obrotu pojedynczej cząsteczki ciała. Nie musimy przejmować się wszystkimi pozostałymi punktami.

Answer 4

Wybierz dowolny punkt i znajdź dwa inne punkty, które znajdują się w równej odległości od niego. To powinno zająć O (n^2) najgorszy przypadek, ale heurystyka może to znacznie zmniejszyć. Te trzy punkty jednoznacznie określają okrąg. Jeśli jest czwarty punkt w tej samej odległości od pierwszego lub trzeciego punktu, to znacznie zwiększa twoje zaufanie do koła.

Środek okręgu jest punktem na osi, a wektor normalny do okręgu jest kierunkowym wektorem osi.

Uwzględniając oś, można określić kąt pomiędzy obrotami i sprawdzić swoje przypuszczenia z kilkoma innymi punktami. Jeśli jest źle, wybierz inny punkt i zacznij od początku.

Edycja: Przy okazji, oczywiście jest to niedeterministyczne, ale jeśli twoje dane punktowe są tak czyste, jak mówisz i korzystasz z dobrej heurystyki, to powinno być całkiem dokładne.

Answer 5

Spójrz na techniki używane w stereo wizji, aby obliczyć homografię między dwoma obrazami - Twój problem z zestawami chmur punktów wydaje się być analogiczny do dopasowania punktów na wielu obrazach tego samego obiektu/sceny. Wygląda na to, że można zastosować algorytm RANSAC do obliczenia transformacji pomiędzy zestawami chmur punktów.

Answer 6

Szalony pomysł ...

Jeżeli ten sam punkt obraca się wokół tej samej osi kilka razy, wszystkie punkty leżą w tej samej płaszczyźnie. W zależności od zestawu danych możliwe jest wykrycie tej płaszczyzny za pomocą metody ransac.

Oś obrotu będzie prostopadła do tej płaszczyzny, a ustalenie jej położenia powinno być stosunkowo łatwe.

Answer 7

Założono, że są 3 lub więcej kopii. Zastanów się nad wypukłym kadłubem dużego obłoku. Znajdź dwie równoległe twarze. Oś obrotu będzie prostopadła do nich. Jeśli znajdziesz więcej niż jedną parę, po prostu przetestuj każdą orientację.

Oczywiście to nie działa, jeśli najbardziej ekstremalne punkty w stosunku do osi znajdują się na osi, jednak w ogólnym przypadku jest to bardzo rzadkie.

Answer 8

Są 2 rzeczy, które należy rozważyć:

1. kątowa rozpiętość chmury punktów.
2. Kąt obrotu.

Teraz, jeśli (obrót> rozpiętość) rozwiązanie jest prostsze, ponieważ trzeba szukać podrzędnego wzorca i na podstawie jego występowania, spróbuj dopasować większy wzór.

w przypadku (obrót < przęsła), będziesz musiał przejrzeć efekty brzegowe, ponieważ w obszarze (po pierwszym obrocie, przed ostatnim obróceniem) nadal będziesz miał symetryczną chmurę punktów, pod kątem symetria = kąt rozpiętości; jak w powyższym przypadku.

Jeśli nie wiesz, w jakiej kategorii upadniesz, możesz bezpiecznie założyć w drugim.

Jak wspomniano wcześniej, RANSAC jest najlepszym sposobem dopasowywania wzorców, ponieważ zajmuje mniej czasu i daje przyzwoite wyniki. Jedynym problemem, z którym się Państwo zetknęli jest kąt oszacowania zakresu chmury punktów mini podczas inicjalizacji. oszacowanie to jest trudne.Więc jeśli masz wystarczająco dużo mocy obliczeniowej/czasu, sugerowałbym iterację z krokiem 1 stopnia. zaczynając od skromnego 5 stopni, aby powiedzieć 45 stopni. Gdy wyniki zaczynają się zbierać, zwiększ dokładność kątową.

Answer 9

Ponieważ przy topnienia jest mała, najprostszym rozwiązaniem może być RANSAC:

1. Odbiór trzy punkty losowo
2. obliczyć oś obrotu dla tych punktów (prostopadła do koła i przechodzi chociaż centrum)
3. Czy inne punkty się zgadzają?
4. razie iteracji aż do właściwej osi znaleziono

Prawdopodobieństwo poprawnego pomiaru wynosi 1/((n-1) (n-2)), gdzie n jest liczbą punktów, w których oryginalny chmury . Ponieważ każdy test można wykonać bardzo szybko, może to być przydatne podejście.