Corner detection

Wykrywanie kątów (Corner detection) to jedna z najprostszych metod wyznaczania punktów charakterystycznych na obrazie.

Większość algorytmów wykrywających kąty można opisać za pomocą ogólnego schematu:

  1. W każdym punkcie obrazka analizując jego otoczenie wyznacza się miarę dopasowania (wystąpienia) kąta. Dzięki takiej procedurze dostajemy mapę dopasowania rogów.
  2. Następnie usuwa się lokalne maksima wykorzystując maskę 3 na 3, tak by nie wykryć kilka razy tego samego rogu / kąta.
  3. W trzecim kroku dokonujemy wykrycia krawędzi zadając pewien próg do binaryzacji.

Moravec Corner Detection

Moravec Corner Detection to jeden z najstarszych i najprostszych algorytmów wykrywania rogów / kątów. Algorytm przechodzi przez wszystkie piksele obrazu weryfikując czy w danym miejscu występuje kąt / róg. Algorytm wykorzystuje otoczenie piksela (najczęściej $3 \times 3$, $5 \times 5$, $7 \times 7$). Idea algorytmu opiera się na spostrzeżeniu, że w przypadku kąta / rogu przesuwając otoczenie następuje istotna zmiana. Natomiast w przypadku krawędzi lub wnętrza obiektu, ta zmiana jest niewielka.

Ilustracja. Moravec Corner Detection wykrywa kąty / rogi poprzez porównywanie otoczenia piksela z jego sąsiednimi otoczeniami. W przypadku pierwszych dwóch obrazów zmiana jest mała. W przypadku rogu ta różnica jest większa.

Jako miarę zmiany w otoczeniach używa się sumy kwadratów odległości. Dla każdego piksela (o współrzędnych $(i,j)$) musimy wyznaczyć miarę podobieństwa:

\[ E(u,v) = \sum_{x} \sum_{y} \big( f(x+u, y+v) - f(x, y) \big)^2, \]

gdzie $(u,v) \in \{ (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1) \}$ oraz mamy ustalonej wielkości okno $3 \times 3$, $5 \times 5$, $7 \times 7$.

Ilustracja. Przykład wykrywania kątów / rogów w przypadku binarnych obrazów. Na obrazku (a) widoczny jest kąt / róg natomiast na (c) jest krawędź. Przykład (b) i (d) pokazują przesunięte otoczenia. Na czerwono zanzaczone są różnice w odległościach.

Harris Corner Detection

Harris Corner Detection rożni się od metody Moravec Corner Detection tylko sposobem wyznaczania czy w danym punkcie jest kąt / róg czy nie. Zamiast używać sumy kwadratów odległości metoda Harrisa używa pochodnych cząstkowych, wag ustalonych za pomocą gęstości rozkładu normalnego oraz wartości i wektorów własnych.

Zanim przejdziemy do opisu metody przypomnijmy wzór Taylora. Niech $f \colon [a,b] \to \mathbb{R} $ będzie funkcją $(n+1)$-razy różniczkowalną na przedziale $[a,b]$ w sposób ciągły (na końcach przedziału zakłada się różniczkowalność z lewej, bądź odpowiednio, z prawej strony). Wówczas dla każdego punktu $x$ z przedziału $(a,b)$ spełniony jest wzór zwany wzorem Taylora

\[ f(x) = f(a)+ \frac{x-a}{1!}f^{(1)}(a)+\frac{(x-a)^{2}}{2!} f^{(2)}(a)+\ldots +\frac {(x-a)^{n}}{n!}f^{(n)}(a)+R_{n}(x,a) \]

Za pomocą powyższego wzoru możemy przybliżyć wartość funkcji w punkcie $x \in [a,b]$ za pomocą wartość funkcji w punkcie $a$ oraz kolejnych pochodnych.

Możemy wrócić do naszej metody wyznaczania rogów. Podobnie jak wcześniej będziemy używać sumy kwadratów odległości:

\[ E(u,v) = \sum_{x} \sum_{y} \big( f(x+u, y+v) - f(x, y) \big)^2. \]

Teraz wykorzystamy wzór Taylora (w przypadku dwuwymiarowym), co prowadzi do:

\[ E(u,v) = \sum_{x} \sum_{y}\big( f(x,y) + uf'_x +vf'_y - f(x, y) \big)^2 \]

\[ E(u,v) = \sum_{x} \sum_{y}\big( uf'_x +vf'_y \big)^2 \]

\[ E(u,v) = \sum_{x} \sum_{y}\left(\begin{bmatrix} u & v \end{bmatrix} \begin{bmatrix} f'_x \\ f'_y \end{bmatrix}\right)^2 \]

\[ E(u,v) = \sum_{x} \sum_{y}\left(\begin{bmatrix} u & v \end{bmatrix} \begin{bmatrix} f'_x \\ f'_y \end{bmatrix} \begin{bmatrix} f'_x & f'_y \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} \right) \]

\[ E(u,v) = \begin{bmatrix} u & v \end{bmatrix} \left( \sum_{x} \sum_{y} \begin{bmatrix} f'_x \\ f'_y \end{bmatrix} \begin{bmatrix} f'_x & f'_y \end{bmatrix} \right) \begin{bmatrix} u \\ v \end{bmatrix} \]

Oznaczmy:

\[ M= \sum_{x} \sum_{y} \begin{bmatrix} f'_x \\ f'_y \end{bmatrix} \begin{bmatrix} f'_x & f'_y \end{bmatrix} \]

Otrzymujemy:

\[ E(u,v) = \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix} \].

Macierz $M$ możemy przedstawić w następującej postaci:

\[ M= \sum_{x} \sum_{y} \begin{bmatrix} f'_x \\ f'_y \end{bmatrix} \begin{bmatrix} f'_x & f'_y \end{bmatrix} = \begin{bmatrix} f'_x f'_x & f'_x f'_y \\ f'_x f'_y & f'_y f'_y \end{bmatrix} \]

Aby dokończyć opis metody będziemy potrzebować podstawowych własności wektorów i wartości własnych.

Wektory i wartości własne 

Zacznijmy od wyjaśnienia wektorów własnych. Niech będzie dana macierz $A$. Wektor własny $x$, to taki wektor, który jak przemnożymy go przez macierz $A$, to otrzymamy ten sam wektor przeskalowany przez jakąś stałą $\lambda$.

\[Ax = \lambda x\]

W takim przypadku $x$ nazywa się wektorem własnym, a $\lambda$ nazywa się wartością własną $A$. Dla formalności podamy formalną definicję z algebry liniowej.

Definicja 
Niech $X$ będzie przestrzenią liniową nad ciałem $K$, zaś $A$ oznacza pewien jej endomorfizm, tzn. przekształcenie liniowe tej przestrzeni w siebie. Jeśli dla pewnego niezerowego wektora $x$ przestrzeni spełniony jest warunek:
\[A x=\lambda x,\],
gdzie $\lambda$ jest pewnym skalarem, to $x$ nazywa się wektorem własnym, a $\lambda$ nazywa się wartością własną $A$.

Aby obliczyć wektory i wartości własne macierzy należy rozwiązać równanie:

\[ \det(A-\lambda I) = 0\]

Rozważmy prosty przykład.

\[ A = \begin{bmatrix} 2 & 7 \\ -1 & -6 \end{bmatrix} \]

Najpierw rozwiązujemy równanie:

\[ \det\left(A-\lambda I\right) = 0\]

\[ \det\left(\begin{bmatrix} 2 & 7 \\ -1 & -6 \end{bmatrix}-\lambda \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\right) = 0\]

\[ \det\left(\begin{bmatrix} 2 -\lambda & 7 \\ -1 & - 6 - \lambda \end{bmatrix} \right) = 0\]

\[ \det\left(A-\lambda I\right) = (2-\lambda)(-6-\lambda)+7 = \lambda^2+4\lambda-5=(\lambda+5)(\lambda-1) = 0\]

Otrzymujemy dwa rozwiązania $\lambda_1=-5$ oraz $\lambda_2=1$. Dla każdej z wartości własnych możemy wyznaczyć wektor własny. Aby to zrobić podstawiamy nasze wartości własne do

\[ (A-\lambda I) x = 0\]

Następnie rozwiązujemy układ równań, gdzie $x$ jest szukanym wektorem własnym. Wyznaczmy wektor własny dla $\lambda_1=-5$ (dla drugiej wartości własnej obliczenia wykonuje się analogicznie). Otrzymujemy układ równań liniowych:

\[ \begin{bmatrix} 7 & 7 \\ -1 & -1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}\]

Otrzymujemy:

\[ 7 x_1+ 7 x_2 = 0 \]

Czyli:

\[ x_1= - x_2 \]

Otrzymujemy nieskończenie wiele rozwiązań, z których wybieramy jedno (np. $[-1,1]$). Można wybrać dowolne, ale najczęściej wybiera się taki wektor, który jest unormowany (długości jeden).

Umiemy już wyznaczać wartości i wektory własne. Możemy teraz podać dwie przydatne własności. Niech $A$ będzie macierzą o wartościach własnych $\lambda_1, \ldots, \lambda_n$, wtedy:

\[ \mathrm{tr}(A)=\sum_{i=1}^{n} A_{ii} =\sum_{i=1}^{n}\lambda_{i}=\lambda_{1}+\lambda_{2}+\cdots +\lambda_{n}, \]

\[ \det(A)=\prod_{i=1}^{n}\lambda_{i}=\lambda_{1}\lambda_{2}\cdots \lambda_{n}. \]

Na koniec tego podrozdziału podamy intuicją, która stoi za wektorami i wartościami własnymi macierzy.

Mając zadaną macierz $A$, możemy ją interpretować jako wzór na elipsę. Wektory własne (unormowane) wskazują główne półosie elipsy. Natomiast pierwiastki z wartości własnych $\sqrt{\lambda_1}$, $\sqrt{\lambda_2}$, to promienie elipsy (patrz poniższy rysunek).

Teraz możemy wrócić do Harris Corner Detection.

Wracamy do Harris Corner Detection

Przed naszą dygresją o wartościach i wektorach własnych skończyliśmy na równaniu:

\[ E(u,v) = \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix}, \quad \mbox{ gdzie } M = \begin{bmatrix} f'_x f'_x & f'_x f'_y \\ f'_x f'_y & f'_y f'_y \end{bmatrix} \]

Naszym celem jest stwierdzenie czy w danym punkcie występuje krawędź na podstawie macierzy $M$. W tym celu użyjemy analizy wektorów i wartości własnych. Użyjemy intuicji z powyższej sekcji. W zależności od stosunku wartości własnych wiemy czy gradient spada w którymś kierunku szybciej lub wolniej, a w konsekwencji, czy występuje mała zmiana albo duża.

W konsekwencji:

  1. Jeżeli obie wartości własne są duże, to mamy kąt / róg (zmiana jest duża w obu kierunkach).
  2. Jeżeli jedna wartość jest większa, to mamy krawędź.
  3. Jeżeli obie wartości własne są małe, to jesteśmy w środku zbioru.

Relację miedzy wartościami własnymi możemy mierzyć za pomocą następujących wzoru:

\[ R = \det(M) - k(\mathrm{tr}(M)^2),\],

gdzie $k$ jest stałą.

Co można wyrazić w języku wartości własnych:

\[ R = \lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2.\]

W konsekwencji:

  1. Jeżeli $R<0$, to mamy kąt / róg (zmiana jest duża w obu kierunkach).
  2. Jeżeli $R>0$, to mamy krawędź.
  3. Jeżeli $R$ jest małe, to jesteśmy w środku zbioru.

 b

Ilustracja. Wynik działania algorytmu Harris Corner Detection.

Powyższą ilustrację można otrzymać za pomocą następującego kodu OpenCV (C++).

FAST Corner Detection

Metoda FAST Corner Detection rożni się od wcześniej opisanych podejść do tego problemu Metoda ta koncentruje się na analizie brzegu otoczenia (czyli okręgu) każdego punktu (otoczenie o promieniu 3, czyli 16 pikseli). Rozpatrywany piksel $p$ jest uznawany za kąt / róg, jeżeli istnieje 9 pikseli na okręgu o zadanym promieniu, które są wszystkie jaśniejsze lub ciemniejsze niż piksel $p$ (czasami używa się średniej z kolorów w otoczeniu $p$).

Ilustracja. Algorytm rozważa dany punkt oraz 16 pikseli leżących na okręgu o promieniu 3.

Algorytm często wykrywa punkty, które nie leżą na krawędziach i często interpretowany jest jako algorytm wykrywania punktów charakterystycznych (niekoniecznie kątów / rogów).

 

Ilustracja. Efekt działania algorytmu FAST Corner Detection.

Powyższą ilustrację można otrzymać za pomocą następującego kodu OpenCV (C++).