Dopasowywanie wzorców

Dopasowywanie szablonów to technika cyfrowego przetwarzania obrazu służąca do znajdowania małych części obrazu, które pasują do obrazu szablonu. Może być używany do kontroli jakości w produkcji, nawigacji robotów mobilnych lub wykrywania krawędzi na obrazach.

Główne wyzwania w zadaniu dopasowywania szablonów to wykrywanie okluzji, gdy poszukiwany obiekt jest częściowo ukryty na obrazie; wykrywanie przekształceń niesztywnych, gdy obiekt jest zniekształcony lub obrazowany pod różnymi kątami; wrażliwość na oświetlenie i zmiany tła; bałagan w tle; i zmiany skali.

Podejście oparte na funkcjach

Warstwa ukryta generuje wektor, który przechowuje informacje o klasyfikacji obrazu i jest używany w algorytmie dopasowywania szablonów jako cechy obrazu

Podejście oparte na funkcjach do dopasowywania szablonów opiera się na wyodrębnianiu cech obrazu , takich jak kształty, tekstury i kolory, które pasują do docelowego obrazu lub ramki. Takie podejście jest zwykle osiągane przy użyciu sieci neuronowych i klasyfikatorów głębokiego uczenia, takich jak VGG, AlexNet i ResNet . ^{[ potrzebne źródło ]} Konwolucyjne sieci neuronowe (CNN), na których opiera się wiele nowoczesnych klasyfikatorów, przetwarzają obraz, przepuszczając go przez różne ukryte warstwy, tworząc wektor na każdej warstwie z informacjami o klasyfikacji obrazu. Wektory te są pobierane z sieci i wykorzystywane jako cechy obrazu. Ekstrakcja cech za pomocą głębokich sieci neuronowych , takich jak CNN, okazała się niezwykle skuteczna i stała się standardem w najnowocześniejszych algorytmach dopasowywania szablonów.

To podejście oparte na funkcjach jest często bardziej niezawodne niż podejście oparte na szablonach opisane poniżej. Jako taka, stała się najnowocześniejszą metodą dopasowywania szablonów, ponieważ może dopasowywać szablony z transformacjami niesztywnymi i pozapłaszczyznowymi, a także z dużym bałaganem w tle i zmianami oświetlenia.

Podejście oparte na szablonach

W przypadku szablonów bez silnych funkcji lub gdy większość obrazu szablonu stanowi pasujący obraz jako całość, podejście oparte na szablonach może być skuteczne. Ponieważ dopasowywanie oparte na szablonie może wymagać próbkowania dużej liczby punktów danych, często pożądane jest zmniejszenie liczby punktów próbkowania poprzez zmniejszenie rozdzielczości obrazów wyszukiwania i szablonów o ten sam współczynnik przed wykonaniem operacji na wynikowych obrazach o zmniejszonym rozmiarze. Ta wstępnego przetwarzania tworzy wieloskalową lub piramidę , reprezentacja obrazów, zapewniająca ograniczone okno wyszukiwania punktów danych w wyszukiwanym obrazie, dzięki czemu szablon nie musi być porównywany z każdym realnym punktem danych. Reprezentacje piramid to metoda redukcji wymiarowości , wspólny cel uczenia maszynowego na zbiorach danych, które cierpią z powodu przekleństwa wymiarowości .

Wspólne wyzwania

W przypadkach, gdy szablon może nie zapewniać bezpośredniego dopasowania, przydatne może być zaimplementowanie przestrzeni własnych w celu utworzenia szablonów, które szczegółowo opisują pasujący obiekt w wielu różnych warunkach, takich jak różne perspektywy, oświetlenie, kontrasty kolorów lub pozy obiektu . Na przykład, jeśli algorytm szuka twarzy, jego szablonowe przestrzenie własne mogą składać się z obrazów (tj. szablonów) twarzy w różnych pozycjach względem kamery, w różnych warunkach oświetleniowych lub z różnymi wyrazami twarzy (tj. pozami).

Możliwe jest również, że pasujący obraz zostanie zasłonięty lub przesłonięty przez obiekt. W takich przypadkach nieuzasadnione jest dostarczanie mnóstwa szablonów, aby pokryć każdą możliwą okluzję. Na przykład obiektem wyszukiwania 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 wierzchu lub innym obiektem przed Aparat. W przypadkach, gdy obiekt jest plastyczny lub można go ustawić, ruch staje się dodatkowym problemem, a problemy dotyczące zarówno ruchu, jak i okluzji stają się niejednoznaczne. W takich przypadkach jednym z możliwych rozwiązań jest podzielenie obrazu szablonu na wiele obrazów podrzędnych i wykonanie dopasowania w każdym podpodziale.

Odkształcalne szablony w anatomii obliczeniowej

Dopasowywanie szablonów jest głównym narzędziem w anatomii obliczeniowej (CA). W tej dziedzinie odkształcalny model szablonowy służy do modelowania przestrzeni anatomii człowieka i jego orbit w grupie dyfeomorfizmów , czyli funkcji płynnie odkształcających obiekt. Dopasowywanie szablonów powstaje jako podejście do znajdowania nieznanego dyfeomorfizmu, który działa na obraz szablonu w celu dopasowania obrazu docelowego.

Algorytmy dopasowywania szablonów w CA zaczęto nazywać mapowaniami dyfeomorficznymi metrycznymi dużych deformacji (LDDMM). Obecnie istnieją algorytmy dopasowywania szablonów LDDMM do dopasowywania anatomicznych 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, czasami nazywana „liniowym filtrowaniem przestrzennym”, wykorzystuje łatkę obrazu (tj. „obraz szablonu” lub „maskę filtra”) dostosowaną do określonej cechy wyszukiwania obrazów do wykrycia. ^{[ Potrzebne źródło ]} Ta technika może być łatwo zastosowana na obrazach w odcieniach szarości lub na krawędziach , gdzie dodatkowa zmienna koloru jest albo nieobecna, albo nieistotna. Korelacja krzyżowa techniki porównują podobieństwa obrazów wyszukiwania i szablonów. Ich wyniki powinny być najwyższe w miejscach, w których struktura obrazu odpowiada strukturze szablonu, tj. tam, gdzie duże wartości obrazu wyszukiwania są mnożone przez wartości dużego obrazu szablonu.

Ta metoda jest zwykle wdrażana przez wybranie części wyszukiwanego obrazu do użycia jako szablonu. Niech reprezentuje wartość wyszukiwanego piksela obrazu, gdzie $y ) {\ Displaystyle S (x, y)}$ $\ Displaystyle (x, y)}$ S ( x , obraz. Dla uproszczenia załóżmy, że wartości pikseli są skalarne, jak na obrazie w skali szarości . Podobnie niech ${\ textstyle T (x_ {t}, y_ {t})}$ reprezentuje wartość piksela szablonu, gdzie ${\ textstyle (x_ {t}, y_ {t})}$ reprezentuje współrzędne piksela w obrazie szablonu. Aby zastosować filtr, po prostu przesuń środek (lub początek) obrazu szablonu nad każdy punkt w wyszukiwanym obrazie i oblicz sumę iloczynów, podobnie jak iloczyn skalarny, między wartościami pikseli w wyszukiwaniu a obrazami szablonu w całym obszar objęty szablonem. Bardziej formalnie, jeśli ${\ Displaystyle (0,0)}$ to środek (lub początek) obrazu szablonu, a następnie korelacja krzyżowa w każdym punkcie $y)}$ $T \ star S}$ ${\ Displaystyle$ w wyszukiwanym obrazie można obliczyć jako:

{\ Displaystyle (T \ gwiazda S )(x,y)=\suma _{(x_{t},y_{t})\in T}T(x_{t},y_{t})\cdot S(x_{t}+x,y_ {t}+y)}

Dla wygody oznacza zarówno wartości pikseli obrazu szablonu

,

jak i jego domenę granice szablonu. Należy zauważyć, że uwzględniane są wszystkie możliwe pozycje szablonu względem wyszukiwanego obrazu. Ponieważ wartości korelacji krzyżowej są największe, gdy wartości pikseli wyszukiwania i szablonu są wyrównane, najlepiej pasująca pozycja

{\ Displaystyle (x_ {m}, y_ {m})}

odpowiada maksymalnej wartości

{\ Displaystyle T \ gwiazda S}

nad

{\ displaystyle S}

.

Innym sposobem radzenia sobie z problemami z translacją obrazów za pomocą dopasowywania szablonów jest porównywanie intensywności pikseli przy użyciu miary sumy różnic bezwzględnych (SAD). Aby to sformułować, niech ${\ Displaystyle I_ {S} (x_ {s}, y_ {s})}$ i ${\ Displaystyle I_ {T} (x_{t},y_{t})}$ oznaczają natężenie światła pikseli w wyszukiwaniu i obrazach szablonów ze współrzędnymi $},$ , $x_$ odpowiednio. $wyszukiwanym$ szablonu do punktu na , jak poprzednio, sumę bezwzględnych między szablonem a intensywnością piksela wyszukiwania w tym punkcie wynosi:

{\ Displaystyle SAD (x, y) = \ suma _ {(x_ {t}, y_ {t}) \ w T} \ lewo \ vert I_ {T} (x_ {t}, y_ {t}) -I_ {S}(x_{t}+x,y_{t}+y)\right\vert }

W przypadku tej miary najniższy SAD daje najlepszą pozycję dla szablonu, a nie najwyższy, jak w przypadku korelacji krzyżowej. SAD wydaje się być stosunkowo prosty do wdrożenia i zrozumienia, ale jest również stosunkowo powolny w wykonaniu. Poniżej przedstawiono prostą implementację dopasowywania szablonów SAD w języku C++ .

Realizacja

W tej prostej implementacji zakłada się, że opisana powyżej metoda jest stosowana do obrazów w odcieniach szarości: dlatego jako intensywność pikseli użyto szarości . Końcowa pozycja w tej implementacji to górne lewe miejsce, w którym obraz szablonu najlepiej pasuje do wyszukiwanego obrazu.

  


     0        
         0        
          

        
          minSAD  =  WARTOŚĆ_MAX  ;  // przeglądanie szukanego obrazu  for  (  size_t  x  =  ;  x  <=  S_cols  -  T_cols  ;  x  ++  )  {  for  (  size_t  y  =  ;  y  <=  S_rows  -  T_rows  ;  y  ++  )  {  SAD  =  0.0  ;  // pętla przez obraz szablonu  dla  (     0     
                 0      

                   
                   
		
                 rozmiar_t  j  =  ;  j  <  T_kolumny  ;  j  ++  )  for  (  size_t  ja  =  ;  ja  <  T_wiersze  ;  ja  ++  )  {  piksel  p_SearchIMG  =  S  [  y  +  ja  ][  x  +  j  ];  piksel  p_TemplateIMG  =  T  [  i  ][  j  ];  SMUTNY       
            

        
               
              
            
              
              
               +=  abs  (  p_SearchIMG  .  Gray  -  p_TemplateIMG  .  Gray  );  }  // zapisz najlepszą znalezioną pozycję  if  (  minSAD  >  SAD  )  {  minSAD  =  SAD  ;  // podaj min  pozycję SAD   .  najlepszywiersz  =  y  ;  pozycja  .  najlepszaKolumna  =  x  ;  pozycja  .  bestSAD  =  SAD  ; 
        
    
    
 }  }  }

Jednym ze sposobów przeprowadzania dopasowywania szablonu na kolorowych obrazach jest rozłożenie pikseli na składowe kolorów i zmierzenie jakości dopasowania między szablonem kolorów a wyszukiwanym obrazem przy użyciu sumy SAD obliczonej dla każdego koloru oddzielnie.

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 go w dziedzinie częstotliwości obrazu, określanej jako „filtrowanie w dziedzinie częstotliwości ”, odbywa się to za pomocą twierdzenia o splotach .

Innym sposobem na przyspieszenie procesu dopasowywania jest zastosowanie piramidy obrazkowej. 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ć w poszukiwaniu 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ą poradzić sobie z problemami, takimi jak translacja, skala, obrót obrazu, a nawet wszystkie przekształcenia afiniczne.

Poprawa dokładności dopasowania

Można wprowadzić ulepszenia w metodzie 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ż poprawienie dokładności metody dopasowywania poprzez hybrydyzację podejścia opartego na cechach i szablonach. Oczywiście wymaga to, aby obrazy wyszukiwania i szablony miały cechy, które są wystarczająco widoczne, aby obsługiwać dopasowywanie funkcji.

Podobne metody

Inne podobne metody to „Dopasowanie stereo”, „ Rejestracja obrazu ” i „ Przekształcenie funkcji niezmiennej w skali ”.

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 opracowywano i stosowano systemy do liczenia twarzy przechodzących przez część mostu w określonym czasie. Inne systemy obejmują automatyczne wykrywanie zwapniałych guzków w ramach cyfrowych zdjęć rentgenowskich klatki piersiowej. Niedawno metoda ta została zaimplementowana w symulacji geostatystycznej, co może zapewnić szybki algorytm.

Zobacz też

Linki zewnętrzne