Punkty skalo-niezmiennicze

 

W tym rozdzile opiszemy metodę wykrywającą skaloniezmiennicze przekształcenie cech (Scale-invariant feature transform, w skrócie SIFT).

Algorytm SIFT (skaloniezmiennicze przekształcenie cech) został opracowany w celu wykrywania powtarzających się sekwencji. Używany jest również do śledzenia, rozpoznawania obiektów jak również do łączenia obrazów w panoramy. Celem algorytmu jest wyznaczenia punktów, które są nizmiennicze ze względu na skalowanie i obroty, a częściowo niezminnicze na zmiany oświetlenia i punktu widzenia (zmiany perspektywy).

Punkty skaloniezmiennicze są wydobywane w kilku krokach:

  1. Wykrywanie punktów ekstremalnych (scale space extrema detection).
  2. Dokładna lokalizacja punktów charakterystycznych (accurate keypoint location).
  3. Przypisanie orientacji punktom charakterystycznym (keypoint orientation assignment).
  4. Tworzenie deskryptorów punktów charakterystycznych (keypoint descriptors).

Ponadto omówimy możliwość dopasowania obrazu do obrazu. 

Wykrywanie punktów ekstremalnych (scale space extrema detection).

W celu wykrycia punktów, które są niezmiennicze względem skalowania algorytm używa obrazów przeskalowanych do różnych wielkości. W tak przygotowanych sekwencjach obrazów wykrywane są punkty ekstremalne lub inaczej charakterystyczne. Podobnie jak w przypadku wykrywania krawędzi używa się w tym celu filtra Laplace'a (który obliczny jest za pomocom fitru Gaussa).

Ilustracja 1. Algorytm SIFT używa zdjęcia w rożnych rozmiarach oraz rozmycia Gaussowskiego z różnymia parametrami $\sigma$. 

Filtr Laplace'a można uzyskać za pomocą odjęcia dwóch wyników rozmycia Gaussowskiego z różnymi parametrami $\sigma$. Ta zależność wynika z równanie przewodnictwa ciepła. Nie jest tu naszym celem opisywanie tej zależności, ale dla pełności rozważań pokażemy intuicję stojącą. Przypomnijmy, że równanie przewodnictwa ciepła ma postać:

\[ \frac{\partial G}{\partial \sigma} = \sigma \Delta^2 G \].

Nie jest to klasyczna wypowiedź (parametr $t$ został zamieniony z $\sigma$). Ponadto została ona troszkę uproszczony ale dla naszych potrzeb wystarczy. W naszych obliczeniach wykorzystamy (podobnie jak w poprzednich rozdziałach) przybliżenie pochodnej za pomocą iloczynu różnicowego.

\[ \sigma \Delta^2 G = \frac{\partial G(x,y,\sigma)}{\partial \sigma}= \frac{G(x,y,\sigma)-G(x,y,k\sigma)}{ k\sigma - \sigma}\].

\[ G(x,y,\sigma)-G(x,y,k\sigma) \approx (k - 1)\sigma^2 \Delta^2 G \].

Jak widzimy Laplasjan może być przybliżany za pomocą gęstości rozkładu normalnego z różnymi parametrami $\sigma$. W konsekwencji filtr Laplace uzyskujemy za pomocą odjęcia dwóch obrazów na których został wykonany filtr Gaussa (najczęściej używa się $k=\sqrt{2}$ oraz $\sigma=1.6$). W praktyce wykonuje się filtr Gaussa na obrazach z różnymi parametrami $\sigma$ (na poniższym obrazie jest to pierwsza kolumna zdjęć) a następnie filtr Gaussa uzyskuje się przez ich odjęcie (druga kolumna). Przypomnijmy, że filtr Gaussa można uzyskać za pomocą operacji splotu.

\[ L_n (i, j, k, \sigma) = G(i, j, k^n \sigma)* f (i, j) \mbox{ gdzie } n = 0, 1, 2, 3, \ldots \]

Ilustracja 2. Algorytm SIFT wykorzystuje filtr Laplace, który otrzymujemy przez odjęcie obrazów otrzymanych przez filtr Gaussa z różnymi parametrami $\sigma$.

Algorytm SIFT wykorzystuje filtr Gaussa z rożnymi parametrami na obrazach o różnych wielkościach. Odbywa się to w wielu oktawach (przestrzeń skal), gdzie każda oktawa odpowiada podwojeniu odchylenia standardowego. Różnicę rozkładów Gaussowskich (DoG) oznaczać będziemy: 

\[ D_n(i, j, k, \sigma) = L_{n+1}(i, j, k, \sigma) − L_n (i, j, k, \sigma). \]

Ilustracja 3. W pierwszym wierszu widzimy efekt rozmycia Gaussowskiego a w drugim wynik ich odjęcia (DoG).

Filtr Laplace'a można rozumieć jako detektor "blobów" (czyli rozmytych kół w $R^2$), patrz Ilustracja 4. W zależności jak duży jest szukany obiekt (koło na osi $OX$) to pik pojawi się w w wyniku filtru w odpowiedniej skali (oś $OX$).

Ilustracja 4. Filtr Laplace'a można rozumieć jako detektor "blobów". W zależności jak duży jest szukany obiekt (koło na osi $OX$) to pik pojawi się w w wyniku filtru w odpowiedniej skali (oś $OY$).

Następnym krokiem jest wyznaczenie ekstremów na obrazie uzyskanym za pomocą DoG (drugi wiersz na Ilustracja 3.). W tym celu wykorzystuje się binaryzację wyznaczając lokalne minima i maksima.

Dokładna lokalizacja punktów charakterystycznych (accurate keypoint location).

Aby wyznaczyć minima oraz maksima na obrazie uzyskanym za pomocą filtr Laplace'a będziemy używać obrazów w różnych skalach. Rozważmy obraz w trzech różnych skalach (patrz Ilustracja 5.).

Ilustracja 5. Aby wyznaczyć minima oraz maksima na obrazie uzyskanym za pomocą filtr Laplace'a będziemy używać obrazów w różnych skalach oraz otoczenia o wymiarach $3$ na $3$.

Dla każdego punktu obrazu rozważmy jego otoczenie w różnych skalach (po filtrze Laplace'a z różnymi parametrami). W danym punkcie występuje minimum lub maksimum gdy centralny punkt jest powyżej (lub poniżej) wszystkie sąsiadów (w tym obrazie i w obrazach sąsiadujących).

Taka procedura powoduje wykrycie bardzo dużej ilości punktów charakterystycznych. Nie wszystkie z nich spełniają wymagane warunki. W celu usunięcia nadmiaru punktów wykorzystuje się dwa testy. Chcemy wybrać tylko to punkty, które są skaloniezmiennicze.

Pierwszy test usuwa płytkie lub lokalne minima, które występują na jednolitym tle. Drugi test sprawdza czy wyznaczone punkty leżą na odcinku, czy są jego końcami. Naszym celem jest wyznaczenie punktów charakterystycznych, których będziemy używać do połączenia dwóch obrazów. W konsekwencji nie chcemy znajdować elementów należących do tła (wnętrza jednobarwnych obszarów) lub wnętrz krawędzi, gdyż są one ciężkie do zlokalizowania. Powyższe testy pozwolą nam usunąć te dwie sytuacje.

Ilustracja 6. Wszystkie punkty ekstremalne (obrazek z lewej). Wynik usuwania płytkich oraz lokalnych minimów (środkowy obrazek), Wynik usuwania punktów wewnątrz krawędzi (obrazek z prawej).

W pierwszym teście naszym celem jest usunięcie płytkich lub lokalnych minimów. Podobnie jak wcześniej użyjemy rozwinięcia funkcji w szereg Taylora.

\[ D(x) = D + \frac{\partial D}{\partial x}^T x + \frac{1}{2}x^T\frac{\partial^2 D}{\partial x^2} x + \ldots, \mbox{ gdzie } x = (i,j,k,\sigma) \].

Rozważając szereg Taylora tylko do pierwszej potęgi. W takim przypadku możemy spróbować wyznaczyć minima. W tym celu różniczkujemy funkcję i przyrównujemy do zera

\[ \frac{\partial D}{\partial x} = \frac{\partial D^2}{\partial x^2} x + \frac{\partial D}{\partial x} = 0 \].

W konsekwencji minimum lub maksimum może wystąpić w punkcie:

\[ x_0 = -\frac{\partial^2 D}{\partial x^2}^{-1}\frac{\partial D}{\partial x}\].

Pierwszy filtr polega na pozostawieniu tylko tych wartości funkcji $D$ dla których wartość funkcji w punktach $x_0$ sa większe od zadanego progu $th$

\[ | H(x_0) | > th \]

Wynik takiego testu przedstawiamy na Ilustracja 6. (środkowy obrazek).

W drugim teście użyjemy analogicznej metody jak przy wykrywaniu kątów/rogów metodą Harris'a. Będzimy wykorzystywać Hessian $H$:

\[ H = \begin{bmatrix} A & B \\ C & D \end{bmatrix} = \begin{bmatrix} \sum_{(i,j)\in W} \frac{\partial^2 D_{n}(i,j,k,\sigma) }{ \partial i^2 } & \sum_{(i,j)\in W} \frac{\partial D_{n}(i,j,k,\sigma) }{ \partial i } \frac{\partial D_{n}(i,j,k,\sigma) }{ \partial j } \\ \sum_{(i,j)\in W} \frac{\partial D_{n}(i,j,k,\sigma) }{ \partial i } \frac{\partial D_{n}(i,j,k,\sigma) }{ \partial j } & \sum_{(i,j)\in W} \frac{\partial^2 D_{n}(i,j,k,\sigma) }{ \partial j^2 } \end{bmatrix} \]

W powyższym wzorze pochodne są przybliżane (analogicznie jak w poprzednich rozdziałach) różnicy sąsiednich punktów. Podobnie jak w metodzie Harris'a będziemy analizować wartości własne macierzy $H$. Podobnie jak wcześniej możemy uniknąć obliczania wartości własnych, ponieważ używać będziemy tylko ich stosunku. Niech $\lambda_1$ będzie wartością własną o największej wielkości a $\lambda_2$ będzie tą o mniejszej wartości. Podobnie jak wcześniej wykorzystamy wzór na wyznacznik i ślad macierzy.

\[ \det(H) = \lambda_1\lambda_2 = AC+B^2 \]

\[ \mathrm{tr}(H)= \lambda_1 + \lambda_2 = A+C \]

Oznaczmy przez $r$ stosunek największej wartości własnej do mniejszej

\[ r = \frac{\lambda_1}{\lambda_2}\]

W zależności od stosunku wartości własnych, a nie ich poszczególnych wartości będziemy podejmować decyzję czy dany punkt powinniśmy usunąć czy zostawić.

Kwadrat śladu macierzy $H$ podzielony przez wyznacznik $H$ , możemy wyrazić za pomocą stosunku wartości własnych $r$

\[ \frac{\mathrm{tr}(H)^2}{\det(H)} = \frac{(\lambda_1 + \lambda_2)^2}{(\lambda_1\lambda_2)}= \frac{(r\lambda_2 + \lambda_2)^2}{(r\lambda_2\lambda_2)}=\frac{(r+1)^2}{r}\]

Powyższe wyrażenie przyjmuje minimum dla $r=1$, czyli w przypadku gdy wartości własne są równe. W konsekwencji aby usunąć lokalne minima oraz elementy na krawędziach musimy zapewnić, że stosunek wartości własnych $r$ jest powyżej pewnej ustalonej wartości (najczęściej używa się $r > 10$). Wynik takiego filtrowania widoczny jest na Ilustracji 6. (obrazek z lewej strony).

Przypisanie orientacji punktom charakterystycznym (keypoint orientation assignment).

Mamy wyznaczone punkty niezmiennicze względem skalowania. Następnym krokiem jest wyznaczenie orientacji punktów charakterystycznego. Posłuży to do stworzenia punktów niezmienniczych względem orientacji. Dzięki wyznaczeniu głównego kierunku dla punktu charakterystycznego będziemy mogli ustawić nasze okno tak by wskazywało ten kierunek.

Aby wyznaczyć orientację punktu użyjemy rozmytych obrazów $L_n(i,j,k,\sigma)$ w najlepszej skali. W wyniku poprzedniego kroku otrzymamy punkty nieimiennicze na skale oraz parametr $n$ czyli skale dla której maksimum zostało wyznaczone.

Dla każdego punktu obrazu (w najlepszej skali), $L_n (i, j, k, \sigma)$ wyznaczmy wielkość gradientu $\Delta f(i, j)$, i orientacji $\phi(i, j)$:

\[ \Delta f(i,j) = \sqrt{ ( L_n(i+1,j,k,\sigma) - L_n(i-1,j,k,\sigma) )^2 + ( L_n(i,j+1,k,\sigma) - L_n(i,j-1,k,\sigma) )^2 }\]

\[ \phi(i,j) = \mathrm{argtan} \big( L_n(i+1,j,k,\sigma) - L_n(i-1,j,k,\sigma) )^2 / ( L_n(i,j+1,k,\sigma) - L_n(i,j-1,k,\sigma) )^2 \big) \]

Następnie w małym otoczeniu punktu tworzymy histogram orientacji. Bierzemy każdy element zadanego otoczenia i wyznaczamy orientacje. Wykorzystujemy tylko 36 wartości, które odpowiadają kątom $10^{o},20^{o},\ldots,360^{o}$ (jeżeli kont jest inny to zaokrąglamy wartość do najbliższej wartości z zadanego zbioru). Następnie z tych wartości tworzymy histogram, patrz Ilustracja 7. Każdy punkt dodajemy z wagą odpowiadająca gradientowi i odległość do rozważanego punktu charakterystycznego. Piki w histogramie odpowiadają orientacji punktu charakterystycznego.

Ilustracja 7. W małym otoczeniu punktu tworzymy histogram orientacji.

Tworzenie deskryptorów punktów charakterystycznych (keypoint descriptors).

Końcowy etapem jest tworzenie deskryptorów na podstawie otoczenia punktów charakterystycznych. Ponownie używamy rozmytego obrazu w najlepszej skali (tym razem rozważamy dużo większe otoczenie). Podobnie jak wcześniej obliczamy gradienty oraz orientacje. Następnie obracamy obrazki w kierunku wskazanym przez optymalną autorotację.

 

Ilustracja 8. Tworzenie deskryptorów na podstawie otoczenia punktów charakterystycznych. 

Region wokół punktu charakterystycznego (w optymalnej skali) jest dzielony na cztery podregiony (czasami używa się większej ilości takich części). W każdym z regionów wyznaczany jest histogram kierunków (analogicznie jak wcześniej). Kierunki są mapowane/kwantyzowane do ośmiu głównych kierunków/wartości, patrz Ilustracja 8. A następnie zapisywane w wektorze. Wektor jest sortowany tak by był niezależny od rozpatrywania kolejności (orientacji), patrz Ilustracja 9.

Ilustracja 9. Tworzenie deskryptorów na podstawie otoczenia punktów charakterystycznych. 

Wynik algorytmu można otrzymać za pomocą następującego kodu OpenCV (C++).

 

Ilustracja 10. Wynik działania algorytmu SIFT.

Dopasowanie punktów charakterystycznych

Jednym z wielu zastosowań punktów niezmienniczych jest możliwość dopasowania elementów na dwóch zdjęciach. Możemy ta metodę wykorzystać do odnajdywania elementów na zdjęciu lub próby połączenia dwóch zdjęć, które na siebie zachodzą. Rozważmy prę zdjęć (patrz Ilustracja 12.), które mają część wspólną.

 

Ilustracja 12. Zdjęcia, które mają część wspólną.

W pierwszym kroku możemy wyznaczyć punkty niezmiennicze/charakterystyczne metodą SIFT.

 

Ilustracja 13. Wynik działania algorytmu SIFT.

Następnie dopasowujemy najbardziej podobne punkty. Jak widać na powyższym rysunku nie jest to proste zadania,  OpenCV (C++).

Ilustracja 14. Dopasowanie wszystkich punktów.

Wybierając tylko kilka nalepie pasujących punktów otrzymujemy poprawne dopasowanie,  OpenCV (C++).

Ilustracja 15. Dopasowanie kilku najlepszych punktów.

Aby zlokalizować poprawne połączenia musimy porównać punkty charakterystyczne z obrazków (tak naprawdę ich deskryptory). Najlepsze dopasowanie tych punktów może być zdefiniowana jako minimalizowanie odległości Euklidesowej. W ten sposób wszystkie punkty będzie dopasowane. Jak pokazuje powyższy przykład musimy rozróżnić pasujące punkty od tych, które nie mają odpowiedników. Jedną z możliwości jest użycie globalnego progu w odległości euklidesowej. Bardzo często wprowadza się próg zależny od maksymalnej i minimalnej wartości tej odległości.