Wykrywanie okręgów (elips) w chmurze punktów 2D

14

Biorąc pod uwagę zestaw punktów (2D), czyli temperatura mętnienia (PC), pytanie jest o robust, accuratea computing-friendlymetoda na znalezienie okręgi (lub elipsy w zaawansowanej wersji).

Intuicyjnym pomysłem jest użycie funkcji wyszukiwania siłowego we wszystkich możliwych punktach (jako centrum) {nieskończony!} I promieniach (ponownie nieskończony!). Jest to bardzo wolne i nieefektywne.

Jak pokazano poniżej, każdy dopasowany okrąg byłby uszeregowany w oparciu o liczbę punktów ( nn) umieszczonych na obwodzie koła w odległości mniejszej niż próg ( t). Zatem należy derrprzedstawić średni dystans.

W formie zaawansowanej interesujące są elipsy.

Wszelkie pomysły, burza mózgów, doświadczenia, komentarze? wprowadź opis zdjęcia tutaj

Deweloper
źródło
Dobre pytanie. Jakiego programu użyłeś do wygenerowania tego diagramu?
Jason R
@JasonR Jak zawsze Python + MatPlotLib .
Deweloper

Odpowiedzi:

14

Najlepsze pomysły, które dokładnie próbują rozwiązać ten problem, to Hough Transform .

Zasadniczo sygnał w dużej przestrzeni będzie r, x, ywspółrzędnymi. Tutaj r oznacza promień i x,yśrodek. Każdy punkt może należeć do jednego lub wielu kręgów. Więc w samolocie Hougha przejdź przez wszystkie możliwe koła, do których ten punkt mógłby należeć, i po prostu zrób +1. To nie jest wyszukiwanie, tylko kolekcja.

Teraz, jeśli istnieje prawdziwy krąg, zostanie dodanych tyle punktów, a wynik takiego r, x, ybędzie znacznie wyższy niż wszystkie inne. Wybranie takiego punktu pozwoli ci wybrać odpowiednie okręgi.

Oto klasyczna papierowa droga z 1971 roku (zanim się urodziłem!), Która wymyśliła tę koncepcję.

  1. WYKORZYSTANIE GORĄCEJ TRASFORMACJI DO WYKRYWANIA LINII I KRZYW NA OBRAZACH Autor: Richard O. Duda, raport Peter E. Hart Tech Centrum Sztucznej Inteligencji z kwietnia 1971 r.

Do samouczka zasugeruję poniższe odniesienia:

  1. HIPR2 - Link
  2. Amos Storkey
  3. Referencje IDL

W szczególności w przypadku wykrywania okręgu możesz zapoznać się z tym poniżej:

  1. AI Shack
  2. Raport techniczny z Chicago Univ.
  3. Notatki z wykładu z Rochester Institute

Te metody są bardzo wydajne i bardzo przyjazne dla komputera.

Dipan Mehta
źródło
1
Mogę poręczyć za artykuły AI Shack, one naprawdę pomagają zrozumieć bardziej rygorystyczną matematykę, którą przeczytasz gdzie indziej.
Ivo Flipse
1
Dobra odpowiedź. Znam już Hough Transform (HT). Ten, którego użyłem, był do wykrywania linii. Określenie segmentów linii było nieco trudne. Zalecono więc użycie probabilistycznej transformaty Hougha (PHT). Nie miałem jasnego pojęcia o rozszerzeniu. Pomyślałem, że może to być tak skomplikowane dla kręgów lub może wydawać się inne trudności. Jeśli chodzi o moje doświadczenia, HT jest dobre, ale nie doskonałe. Zależy mi również na rozszerzeniu HT na 3D. Spróbuję przejrzeć dostarczone linki. Twoja odpowiedź jest dość dobra, aby być kandydatem jako odpowiedź.
Deweloper
AI Shack i raport techniczny z linków Chicaco są martwe
Mehdi