Dopasowywanie wzorców - Template matching
Dopasowywanie szablonów to technika w cyfrowym przetwarzaniu obrazu służąca do znajdowania małych części obrazu, które pasują do obrazu szablonu. Może być stosowany w produkcji jako element kontroli jakości, sposób poruszania się robotem mobilnym lub jako sposób wykrywania krawędzi na obrazach.
Główne wyzwania w zadaniu dopasowywania szablonów to: okluzja, wykrywanie niesztywnych transformacji, zmiany oświetlenia i tła, bałagan w tle i zmiany skali.
Podejście oparte na funkcjach
Podejście oparte na cechach polega na wyodrębnianiu cech obrazu, takich jak kształty, tekstury, kolory, aby dopasować je do docelowego obrazu lub ramki. To podejście jest obecnie osiągane przy użyciu sieci neuronowych i klasyfikatorów Deep Learning, takich jak VGG, AlexNet , ResNet . Głębokie konwolucyjne sieci neuronowe przetwarzają obraz, przepuszczając go przez różne ukryte warstwy i na każdej warstwie wytwarzają wektor z informacjami klasyfikacyjnymi obrazu. Te wektory są pobierane z sieci i używane jako cechy obrazu. Wyodrębnianie funkcji za pomocą głębokich sieci neuronowych jest niezwykle skuteczne i dlatego jest standardem w najnowocześniejszych algorytmach dopasowywania szablonów.
Ta metoda jest uważana za bardziej niezawodną i najnowocześniejszą, ponieważ może dopasować szablony z transformacją niesztywną i poza płaszczyzną , może pasować do dużego bałaganu w tle i zmian oświetlenia.
Podejście oparte na szablonach
W przypadku szablonów bez mocnych funkcji lub gdy większość obrazu szablonu stanowi pasujący obraz, podejście oparte na szablonach może być skuteczne. Jak wspomniano powyżej, ponieważ dopasowanie oparte na szablonach może potencjalnie wymagać próbkowania dużej liczby punktów, możliwe jest zmniejszenie liczby punktów próbkowania poprzez zmniejszenie rozdzielczości obrazów wyszukiwania i szablonów o ten sam współczynnik i wykonanie operacji na wynikowym zmniejszone obrazy (multirezwolucja lub piramida ), zapewniające okno wyszukiwania punktów danych w wyszukiwanym obrazie, dzięki czemu szablon nie musi przeszukiwać każdego opłacalnego punktu danych lub kombinacji obu.
Śledzenie ruchu i obsługa okluzji
W przypadkach, w których szablon może nie zapewniać bezpośredniego dopasowania, przydatne może być zaimplementowanie użycia przestrzeni własnych - szablonów, które szczegółowo opisują pasujący obiekt w wielu różnych warunkach, takich jak różne perspektywy, iluminacje, kontrasty kolorów lub akceptowalny dopasowany obiekt „Pozy”. Na przykład, jeśli użytkownik szukał twarzy, przestrzenie własne mogą składać się z obrazów (szablonów) twarzy w różnych pozycjach względem kamery, w różnych warunkach oświetleniowych lub z różnymi wyrazami twarzy.
Możliwe jest również, że pasujący obraz zostanie zasłonięty lub zasłonięty przez obiekt; w takich przypadkach nieracjonalne jest dostarczanie wielu szablonów do pokrycia każdej możliwej okluzji. Na przykład wyszukiwanym obrazem może być karta do gry, a na niektórych wyszukiwanych obrazach karta jest zasłonięta palcami osoby trzymającej kartę, inną kartą na niej lub jakimkolwiek przedmiotem przed kamerą. z tego powodu. W przypadkach, gdy obiekt jest plastyczny lub możliwy do ułożenia, ruch również staje się problemem, a problemy dotyczące zarówno ruchu, jak i okluzji stają się niejednoznaczne. W takich przypadkach jednym możliwym rozwiązaniem jest podzielenie obrazu szablonu na wiele podobrazów i wykonanie dopasowania na każdym podobraziu.
Odkształcalne szablony w anatomii obliczeniowej
Dopasowywanie szablonów jest głównym narzędziem w anatomii obliczeniowej (CA). Model odkształcalnego szablonu modeluje przestrzeń ludzkich anatomii i orbit pod wpływem grupowego działania dyfeomorfizmów. Dopasowanie szablonu pojawia się jako problem w dopasowaniu nieznanego diffeomorfizmu, który działa na szablonie, aby dopasować obraz docelowy.
Algorytmy dopasowywania szablonów w CA zaczęto nazywać mapowaniem metryk dyfeomorficznym dużych deformacji (LDDMM); są teraz algorytmy dopasowywania szablonów LDDMM do dopasowywania punktów orientacyjnych, krzywych, powierzchni, objętości .
Dopasowanie oparte na szablonach wyjaśnione za pomocą korelacji krzyżowej lub sumy różnic bezwzględnych
Podstawowa metoda dopasowywania szablonów wykorzystuje łatkę (szablon) obrazu, dostosowaną do określonej cechy wyszukiwanego obrazu, którą chcemy wykryć. Technikę tę można łatwo zastosować na szarych obrazach lub obrazach krawędzi . Wynik korelacji krzyżowej będzie najwyższy w miejscach, w których struktura obrazu jest zgodna ze strukturą maski, gdzie duże wartości obrazu są mnożone przez duże wartości masek.
Ta metoda jest zwykle implementowana poprzez wybranie najpierw części wyszukiwanego obrazu do wykorzystania jako szablon: Nazwiemy obraz wyszukiwania S (x, y) , gdzie (x, y) reprezentują współrzędne każdego piksela w wyszukiwanym obrazie . Nazwiemy szablon T (x t , y t ) , gdzie (x t , y t ) reprezentują współrzędne każdego piksela w szablonie. Następnie po prostu przesuwamy środek (lub początek) szablonu T (x t , y t ) na każdy (x, y) punkt w wyszukiwanym obrazie i obliczamy sumę iloczynów między współczynnikami w S (x, y) i T (x t , y t ) na całej powierzchni rozpiętej przez szablon. Ponieważ brane są pod uwagę wszystkie możliwe pozycje szablonu względem wyszukiwanego obrazu, najlepszą pozycją jest pozycja z najwyższym wynikiem. Ta metoda jest czasami nazywana „liniowym filtrowaniem przestrzennym”, a szablon nazywany jest maską filtru .
Innym sposobem rozwiązywania problemów z tłumaczeniem obrazów za pomocą dopasowywania szablonów jest porównanie intensywności pikseli za pomocą miary SAD ( suma różnic bezwzględnych ).
Piksel w wyszukiwanym obrazie o współrzędnych (x s , y s ) ma intensywność I s (x s , y s ), a piksel w szablonie o współrzędnych (x t , y t ) ma intensywność I t (x t , y t ) . Zatem bezwzględna różnica w intensywności pikseli jest definiowana jako Diff (x s , y s , x t , y t ) = | I s (x s , y s ) - I t (x t , y t ) | .
Matematyczne przedstawienie idei przechodzenia przez piksele w wyszukiwanym obrazie, gdy tłumaczymy pochodzenie szablonu na każdy piksel i mierzymy SAD, jest następujące:
S wiersze i S coli oznaczają wiersze i kolumny poszukiwanego obrazu, a T wiersze i T cols oznaczają odpowiednio wiersze i kolumny obrazu szablonu. W tej metodzie najniższy wynik SAD daje oszacowanie najlepszej pozycji szablonu w wyszukiwanym obrazie. Metoda jest prosta do wdrożenia i zrozumienia, ale jest jedną z najwolniejszych metod.
Realizacja
W tej prostej implementacji zakłada się, że wyżej opisana metoda jest stosowana do szarych obrazów: z tego powodu Gray jest używany jako intensywność pikseli. Ostateczna pozycja w tej implementacji podaje lewą górną lokalizację, w której obraz szablonu najlepiej pasuje do obrazu wyszukiwania.
minSAD = VALUE_MAX;
// loop through the search image
for ( size_t x = 0; x <= S_cols - T_cols; x++ ) {
for ( size_t y = 0; y <= S_rows - T_rows; y++ ) {
SAD = 0.0;
// loop through the template image
for ( size_t j = 0; j < T_cols; j++ )
for ( size_t i = 0; i < T_rows; i++ ) {
pixel p_SearchIMG = S[y+i][x+j];
pixel p_TemplateIMG = T[i][j];
SAD += abs( p_SearchIMG.Grey - p_TemplateIMG.Grey );
}
// save the best found position
if ( minSAD > SAD ) {
minSAD = SAD;
// give me min SAD
position.bestRow = y;
position.bestCol = x;
position.bestSAD = SAD;
}
}
}
Jednym ze sposobów dopasowania szablonu na kolorowych obrazach jest rozłożenie pikseli na ich składowe koloru i zmierzenie jakości dopasowania między szablonem koloru a wyszukiwanym obrazem przy użyciu sumy SAD obliczonej dla każdego koloru osobno.
Przyspieszenie procesu
W przeszłości ten typ filtrowania przestrzennego był zwykle używany tylko w dedykowanych rozwiązaniach sprzętowych ze względu na złożoność obliczeniową operacji, jednak możemy zmniejszyć tę złożoność, filtrując ją w domenie częstotliwości obrazu, zwaną `` filtrowaniem w dziedzinie częstotliwości '' , 'odbywa się to za pomocą twierdzenia o splotach .
Innym sposobem na przyspieszenie procesu dopasowywania jest użycie piramidy obrazu. Jest to seria obrazów w różnych skalach, które są tworzone przez wielokrotne filtrowanie i podpróbkowanie oryginalnego obrazu w celu wygenerowania sekwencji obrazów o zmniejszonej rozdzielczości. Te obrazy o niższej rozdzielczości można następnie przeszukiwać pod kątem szablonu (z podobnie zmniejszoną rozdzielczością), aby uzyskać możliwe pozycje początkowe do wyszukiwania w większych skalach. Większe obrazy można następnie przeszukiwać w małym oknie wokół pozycji początkowej, aby znaleźć najlepszą lokalizację szablonu.
Inne metody mogą rozwiązać problemy, takie jak translacja, skala, obrót obrazu, a nawet wszystkie transformacje afiniczne.
Poprawa dokładności dopasowania
Można ulepszyć metodę dopasowywania, używając więcej niż jednego szablonu (przestrzeni własnych), te inne szablony mogą mieć różne skale i rotacje.
Możliwe jest również zwiększenie dokładności metody dopasowywania poprzez hybrydyzację podejść opartych na cechach i szablonach. Oczywiście wymaga to, aby obrazy wyszukiwania i szablony miały funkcje, które są wystarczająco widoczne, aby obsługiwać dopasowywanie funkcji.
Podobne metody
Inne podobne metody to „ dopasowanie stereo ”, „ rejestracja obrazu ” i „ niezmienna w skali transformacja cech ”.
Przykłady użycia
Dopasowywanie szablonów ma różne zastosowania i jest wykorzystywane w takich dziedzinach, jak rozpoznawanie twarzy (patrz system rozpoznawania twarzy ) i przetwarzanie obrazów medycznych. W przeszłości opracowano i stosowano systemy do zliczania twarzy przechodzących przez część mostu w określonym czasie. Inne systemy obejmują automatyczne wykrywanie zwapnionych guzków w cyfrowych promieniach rentgenowskich klatki piersiowej. Niedawno metoda ta została zaimplementowana w symulacji geostatystycznej, która mogła zapewnić szybki algorytm.