Rozpoznawanie wzoru punktowego

Mając dwa różne rozmiary zestawów punktów (2D dla uproszczenia) rozproszone w dwóch kwadratach o różnych rozmiarach, pytanie brzmi:

1 - jak znaleźć wystąpienie małego od dużego przez duże?
2- Jakiś pomysł, jak uszeregować zdarzenia, jak pokazano na poniższym rysunku?

Oto prosta demonstracja pytania i pożądanego rozwiązania:

Aktualizacja 1:
Poniższy rysunek pokazuje nieco bardziej realistyczny widok badanego problemu.

W odniesieniu do komentarzy obowiązują następujące właściwości:

• dostępna jest dokładna lokalizacja punktów
• dostępna jest dokładna wielkość punktów
  • rozmiar może wynosić zero (~ 1) = tylko punkt
• wszystkie punkty są czarne na białym tle
• nie ma efektu skali szarości / antyaliasingu

Oto moja implementacja metody przedstawionej przez endolithz niewielkimi zmianami (obróciłem cel zamiast źródła, ponieważ jest mniejszy i szybszy w rotacji). Zaakceptowałem odpowiedź endolitu, ponieważ wcześniej o tym myślałem. O RANSAC Jak dotąd nie mam doświadczenia. Ponadto implementacja RANSAC wymaga dużej ilości kodu.

Nie jest to najlepsze rozwiązanie, ale to rozwiązanie. Chciałbym nauczyć się lepszych technik:

Jeśli nie miałyby być obracane ani skalowane, można użyć prostej korelacji krzyżowej obrazów. Tam, gdzie pojawia się mały obraz na dużym obrazie, będzie jasny szczyt.

• Rejestrowanie obrazu przy użyciu znormalizowanej korelacji krzyżowej
• Dopasowywanie i konwolucja oparte na szablonach

Możesz przyspieszyć korelację krzyżową za pomocą metody FFT, ale jeśli po prostu dopasowujesz mały obraz źródłowy do dużego obrazu docelowego, metoda wielokrotnego dodawania i dodawania brutalnej siły jest czasami (zwykle) szybsza.

Źródło:

Cel:

Korelacja krzyżowa:

Dwa jasne punkty to pasujące lokalizacje.

Ale zrobić mieć parametr rotacji W przykładzie obrazu, tak że nie będzie działać sama. Jeśli dozwolony jest tylko obrót, a nie skalowanie, nadal można zastosować korelację krzyżową, ale trzeba skorelować krzyżowo, obrócić źródło, skorelować go z całym obrazem docelowym, obrócić go ponownie itp. Dla wszystkie obroty.

Pamiętaj, że to niekoniecznie zawsze znajdzie obraz. Jeśli obrazem źródłowym jest szum losowy, a celem jest szum losowy, nie można go znaleźć, dopóki nie wyszukasz dokładnie pod odpowiednim kątem. W normalnych sytuacjach prawdopodobnie go znajdzie, ale zależy to od właściwości obrazu i kątów wyszukiwania.

Ta strona pokazuje przykład, jak by to zrobić, ale nie podaje algorytmu.

Każde przesunięcie, w którym suma jest powyżej pewnego progu, jest zgodne. Możesz obliczyć stopień dopasowania, skorelując obraz źródłowy ze sobą i dzieląc wszystkie swoje sumy przez tę liczbę. Idealne dopasowanie to 1.0.

Będzie to jednak bardzo trudne obliczeniowo i prawdopodobnie istnieją lepsze metody dopasowywania wzorów kropek (o których chciałbym wiedzieć).

Szybki przykład w Pythonie przy użyciu skali szarości i metody FFT:

from __future__ import division
from pylab import *
import Image
import ImageOps

source_file = 'dots source.png'
target_file = 'dots target.png'

# Load file as grayscale with white dots
target = asarray(ImageOps.invert(Image.open(target_file).convert('L')))

close('all')
figure()
imshow(target)
gray()
show()

source_Image = ImageOps.invert(Image.open(source_file).convert('L'))

for angle in (0, 180):
    source = asarray(source_Image.rotate(angle, expand = True))
    best_match = max(fftconvolve(source[::-1,::-1], source).flat)

    # Cross-correlation using FFT
    d = fftconvolve(source[::-1,::-1], target, mode='same')

    figure()
    imshow(source)


    # This only finds a single peak.  Use something that finds multiple peaks instead:
    peak_x, peak_y = unravel_index(argmax(d),shape(d))

    figure()    
    plot(peak_y, peak_x,'ro')
    imshow(d)

    # Keep track of all these matches:
    print angle, peak_x, peak_y, d[peak_x,peak_y] / best_match

1-kolorowe bitmapy

W przypadku bitmap jednokolorowych byłoby to jednak znacznie szybsze. Korelacja krzyżowa staje się:

• Umieść obraz źródłowy nad obrazem docelowym
  • bitowo-ORAZ wszystkie nakładające się piksele (znacznie szybsze niż mnożenie)
  • zsumuj wszystkie 1s na nakładającym się obszarze
• Przenieś obraz źródłowy o 1 piksel
  • bitowo-ORAZ wszystkie nakładające się piksele
  • zsumuj wszystkie 1
• ...

Przekroczenie progu obrazu w skali szarości do pliku binarnego, a następnie zrobienie tego może być wystarczające.

Chmura punktów

Jeśli źródłem i celem są wzory kropek, szybszą metodą byłoby znalezienie środków każdej kropki (skorelowanie raz ze znaną kropką, a następnie znalezienie pików) i przechowywanie ich jako zestawu punktów, a następnie dopasowanie źródła aby celować, obracając, tłumacząc i znajdując błąd najmniejszych kwadratów między najbliższymi punktami w dwóch zestawach.

Z perspektywy widzenia komputerowego: podstawowym problemem jest oszacowanie homografii między docelowym zestawem punktów a podzbiorem punktów w dużym zestawie. W twoim przypadku, tylko z rotacją, będzie to afiniczna homografia. Powinieneś przyjrzeć się metodzie RANSAC . Został zaprojektowany, aby znaleźć dopasowanie w zestawie z wieloma wartościami odstającymi. Masz więc dwa ważne słowa kluczowe: homografię i RANSAC .

OpenCV oferuje narzędzia do obliczania tych rozwiązań, ale możesz także użyć MATLAB. Oto przykład RANSAC z wykorzystaniem OpenCV . I kolejne pełne wdrożenie .

Typową aplikacją może być znalezienie okładki książki na zdjęciu. Masz zdjęcie okładki książki i zdjęcie książki na stole. Podejście to nie polega na dopasowywaniu szablonów, ale znajdowaniu wyraźnych narożników na każdym obrazie i porównywaniu tych zestawów punktów. Twój problem wygląda jak druga połowa tego procesu - znalezienie punktu ustawionego w dużej chmurze. RANSAC został zaprojektowany tak, aby robić to solidnie.

Sądzę, że metody korelacji krzyżowej mogą również działać, ponieważ dane są tak czyste. Problem polega na tym, że dodajesz kolejny stopień swobody wraz z obrotem, a metoda staje się bardzo wolna.

Jeśli wzór jest rzadki, można wykonać prostą kowariancję wektorów współrzędnych zamiast obrazów. Weź współrzędne punktów w podoknie posortowane w lewo, utwórz wektor ze wszystkich współrzędnych i oblicz kowariancję za pomocą wektora utworzonego ze współrzędnych punktów wzoru posortowanych w lewo. Możesz także użyć ciężarków. Następnie dokonaj brutalnej siły najbliższego sąsiada, aby wyszukać maksimum kowariancji na jakiejś siatce w dużym oknie (a także na siatce w kątach obrotu). Po znalezieniu przybliżonych współrzędnych za pomocą wyszukiwania możesz zawęzić je za pomocą przeważonej metody najmniejszych kwadratów.

PS Idea polega na tym, że zamiast pracy z obrazem możesz pracować ze współrzędnymi niezerowymi pikselami. Wspólne wyszukiwanie najbliższego sąsiada. Powinieneś przeprowadzić wyczerpujące przeszukiwanie całej przestrzeni wyszukiwania, zarówno translacyjnej, jak i obrotowej, używając jakiejś siatki, czyli pewnego kroku we współrzędnych i kącie rotacji. Dla każdej współrzędnej / kąta bierzesz podzbiór pikseli w oknie ze środkiem z tą współrzędną obróconą do tego kąta, weź ich współrzędne (względem środka) i porównaj je ze współrzędnymi piksela poszukiwanego wzoru. Powinieneś upewnić się, że w obu zestawach punkty posortowane w ten sam sposób. Znajdziesz współrzędne z minimalną różnicą (maksymalna kowariancja). Po tym szorstkim dopasowaniu możesz znaleźć precyzyjne dopasowanie z pewną metodą optymalizacji. Przepraszam, nie mogę przekazać tego prostszego niż to.

Jestem bardzo zaskoczony, dlaczego nikt nie wspomniał o metodach rodziny Generalized Hough Transform . Rozwiązują bezpośrednio ten konkretny problem.

Oto, co proponuję:

1. Weź szablon i utwórz tabelę R , indeksując krawędzie szablonu. Wybrane przeze mnie krawędzie to:

2. Użyj domyślnej implementacji OpenCV uogólnionej transformacji Hougha, aby uzyskać:

gdzie zaznaczone są pasujące lokalizacje. Ta sama metoda byłaby nadal funkcjonalna, nawet jeśli krawędzie zmniejszą się do jednego punktu, ponieważ metoda ta nie wymaga intensywności obrazu.

Ponadto obsługa rotacji jest bardzo naturalna w przypadku schematów Hougha. W rzeczywistości w przypadku 2D jest to tylko dodatkowy wymiar w akumulatorze. Na wypadek, gdybyś chciał przejść do szczegółów, jak sprawić, by był naprawdę skuteczny, M. Ulrich wyjaśnia wiele sztuczek w swoim artykule .

Jest to dobra aplikacja do haszowania geometrycznego. Strona Wikipedii z hashowaniem geometrycznym