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

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?

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.