Wykrywanie krawędzi

Wykrywanie krawędzi zostało opracowane i jest wykorzystywane w kontekście zdjęć w odcieniach szarości.

Zanim zaczniemy opisywać różne metody wykrywania krawędzi musimy się zastanowić, co tak naprawdę rozumiemy przez krawędź na obrazie. Krawędziami będziemy nazywać miejsca, w których gwałtownie zmienia się jasność. Dlatego też często w kontekście wykrywania krawędzi używa się pochodnych funkcji, które mogą opisywać / wykrywać nagłe skoki jasności. Jak widać na poniższej ilustracji zachowanie się pochodnych (pierwszej i drugiej) dobrze opisuje moment skoku koloru.

Ilustracja. Fragment obrazu w odcieniach szarości oraz jego reprezentacja jako funkcji.
Na kolejnych rysunkach przedstawiona jest odpowiednio pierwsza i druga pochodna. 

 

Czasami łatwiej patrzy się na tą sytuację w kontekście funkcji jednowymiarowych:


Ilustracja. Interpretacja krawędzi w przypadku funkcji jednej zmiennej 
oraz pochodne funkcji opisującej krawędź.

Oczywiście należny zauważyć, że pochodną funkcji możemy policzyć dla funkcji ciągłych, a mamy do czynienia z obrazami czyli danymi dyskretnymi. Spróbujmy skonstruować proste uogólnienie dla przypadku dyskretnego.

Zacznijmy od funkcji jednowymiarowej.

\[ f \colon \mathbb{R} \to \mathbb{R}.\] 

Pochodna funkcji $f$ w punkcie $x_0$ względem zmiennej $x$ wyraża się wzorem:

\[ \frac{\partial f}{ \partial x}(x_0) =\lim_{h \to 0}  \frac{f(x_0 + h ) - f(x_0)}{h}. \]

W przypadku dyskretnym (a dokładniej w przypadku obrazów) nasz skok będzie wykonywany o $h=1$. W konsekwencji otrzymamy wzór:

\[ \frac{\partial f}{ \partial x}(x_0) =f(x_0 + 1 ) - f(x_0). \]

Analogicznie możemy zdefiniować drugą pochodną (jako pochodną z pochodnej). Znowu zakładając $h=1$ otrzymamy:

\[ \frac{\partial^2 f}{ \partial^2 x}(x_0) =f(x_0 + 1 ) + f(x_0-1) - 2 f(x_0). \]

Teraz możemy przejść do przestrzeni dwuwymiarowej. Tym razem będziemy liczyć pochodne cząstkowe. Rozważmy funkcję:

\[ f \colon \mathbb{Z} \times \mathbb{Z} \to \mathbb{R}.\] 

Pochodne cząstkowe wyrażają się następującym wzorem:

\[ \frac{\partial^2 f}{ \partial^2 x}(x,y) = f(x+1,y) + f(x-1,y) - 2f(x,y), \] 

\[ \frac{\partial^2 f}{ \partial^2 y}(x,y) = f(x,y+1) + f(x,y-1) - 2f(x,y). \]

Udało nam się stworzyć odpowiedniki pierwszej i drugiej pochodnej, jak i pochodnych cząstkowych w przypadku zdjęć w odcieniach szarości rozumianych jako funkcje (wartościami funkcji są odcienie szarości). Teraz pokażemy jak można tych pojęć użyć do wyszukiwania krawędzi na obrazach.

Krzyż Robertsa

Krzyż Robertsa wykorzystuje pochodne cząstkowe. W przypadku Krzyża Robertsa wykorzystuje się jego "gradient ukośny". Potrzebna jest nam pochodna cząstkowa po $x,y$:

\[ \frac{\partial^2 f}{ \partial xy}(x,y) = \frac{f(x+1,y+1) + f(x,y) }{\sqrt{2}}. \]

oraz wektor do niego prostopadły:

\[ \frac{\partial^2 f}{ \partial xy}(x,y)_{\bot} = \frac{f(x,y+1) + f(x+1,y) }{\sqrt{2}}. \]

Mianownik zwykle się pomija i wtedy można zastosować nasze wzory za pomocą operacji splotu z dwoma maskami:

\[ G_1 =  \begin{bmatrix} 1 & 0 \\ 0 & -1  \end{bmatrix} * f  \mbox{ oraz } G_2 = \begin{bmatrix} 0 & 1 \\ -1 & 0  \end{bmatrix}* f. \]

Następnie ostateczny wynik uzyskujemy za pomocą jednej z operacji:

\[ \sqrt{ G_1^2 + G_2^2 } \qquad \mbox{ lub } \qquad |G_1|+|G_2|. \]

  

 

Ilustracja. Oryginalny obrazek i odpowiednio $G_1$, $G_2$, $|G_1|+|G_2|$.

Powyższy efekt można uzyskać za pomocą kodu w OpenCV (C++).

Prewitt

Inną metodą wykorzystującą pierwsze pochodne jest metoda Prewitt. Wykorzystuje ona maski odpowiadające różnego typu gradientom. Podstawowe z nich to:

\[h_1 = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ -1 & -1 & -1 \end{bmatrix} \quad   h_2 = \begin{bmatrix} 0 & 1 & 1 \\ -1 & 0 & 1\\ -1 & -1 & 0 \end{bmatrix}  \]

\[h_3 =  \begin{bmatrix} -1 & 0 & 1 \\ -1 & 0 & 1 \\ -1 & 0 & 1 \end{bmatrix} \quad  h_4 =  \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & -1 \\ 0 & -1 & -1 \end{bmatrix} \]

\[h_5 =  \begin{bmatrix} -1 & -1 & -1 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix} \quad   h_6 = \begin{bmatrix} 0 & -1 & -1 \\ 1 & 0 & -1\\ 1 & 1 & 0 \end{bmatrix}  \]

\[h_7 =  \begin{bmatrix} 1 & 0 & -1 \\ 1 & 0 & -1 \\ 1 & 0 & -1 \end{bmatrix} \quad   h_8 = \begin{bmatrix} -1 & -1 & 0 \\ -1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} \]

W filtrze / metodzie Prewitt-a używa się zwykle dwóch ortogonalnych / przeciwstawnych masek. Najczęściej używa się $h_1$ i $h_3$.

  

 

Ilustracja. Oryginalny obrazek i odpowiednio $h_1$, $h_3$, $|h_1|+|h_3|$.

Powyższy efekt można uzyskać za pomocą kodu w OpenCV (C++)

Sobol

Metoda Sobola jest prostą modyfikacją powyższej metody. Aby zmniejszyć wpływ szumu uśrednia się wartości w pionie:

\[h_1 = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 0 & 0 \\ -1 & -2 & -1 \end{bmatrix} \quad h_3 = \begin{bmatrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{bmatrix}  \]

  

 

lustracja. Oryginalny obrazek i odpowiednio $h_1$, $h_3$, $|h_1|+|h_3|$.

Powyższy efekt można uzyskać za pomocą kodu w OpenCV (C++)

Gradient i orientacja

Powyższe metody używają pierwszej pochodnej aby wyznaczyć nagłe zmiany koloru - krawędzie. Można to rozumieć jako wyznaczanie gradientu funkcji. Z matematycznego punktu widzenia gradient dla obrazu (czyli funkcji  $ f \colon \mathbb{Z} \times \mathbb{Z} \to \mathbb{R}$) dany jest wzorem:

\[ \nabla f = \left[\frac{\partial f}{ \partial x} , \frac{\partial f}{ \partial y} \right].\] 

 Intuicyjnie, gradient określa kierunek najszybszego spadku. Ponadto, możemy wyznaczyć szybkość spadku (odpowiada ona kątowi nachylenia gradientu):   

\[ \measuredangle = \mathrm{arc tag} \left( \frac{\partial f}{ \partial y} {\Large / } \frac{\partial f}{ \partial x} \right). \]

Spadek można wykorzystać do zacienienia krawędzi. A mówiąc bardziej szczegółowo musimy wybrać środkowy punkt krawędzi. Operacja ta odbywa się przy użyciu informacji o orientacji każdego punktu. Sprawdza spadek dla punktów znajdujących się obok rozważanego piksela, a następnie tłumi bieżący punkt, gdy jego nachylenie jest mniejsze od nachylenia obu swoich sąsiadów. 

Ilustracja. Orientacja w każdym punkcie obrazu gdzie spadek gradientu reprezentowany jest przez kierunek strzałek,
a szybkość przez długość strzałki. Centrum konturu krawędzi jest zaznaczona na szaro.
Gradient pikseli A jest większy niż gradienty pikseli B i C.
Piksel D będzie tłumił, jego nachylenie jest mniejsze niż nachylenia pikse
li E i F

Dla wszystkich punktów $(i,j)$
  Rozważamy dwa punkty prostopadłe do krawędzi
    if( $gradient(i,j)$ < gradient obu punktów)
      $output(i,j) = 0$
    else
      $output(i,j) = gradient(i,j)$.

Wykrywanie krawędzi za pomocą drugiej pochodnej    

Wykorzystanie drugiej pochodnej do wykrywania krawędzi opiera się na wykrywaniu / analizowaniu jak szybkości zmiany gradientu. W odróżnieniu od zastosowania pierwszej pochodnej nie będziemy się koncentrować na wyszukiwaniu zmian kolorów, tylko będziemy szukać miejsc gdzie szybkość wzrostu / spadku koloru się zmienia.

Filtr Laplacea

Filt Laplacea wykorzystuje drugie pochodne. Z matematycznego punktu widzenia jest:

\[ \nabla f = \frac{\partial^2 f}{ \partial^2 x} + \frac{\partial^2 f}{ \partial^2 y} \]

Odpowiednio wstawiając wzory ze wstępu łatwo jest pokazać, że aby otrzymać filt Laplacea należy użyć maski:

\[ \begin{bmatrix} 0 & 1 & 0 \\ 1 & -4 & 1 \\ 0 & 1 & 0 \end{bmatrix}  \]

Czasami używa się również

\[ \begin{bmatrix} 0 & 1 & 0 \\ 1 & -8 & 1 \\ 0 & 1 & 0 \end{bmatrix}  \]

  

Ilustracja. Oryginalny obraz oraz krawędzie wyznaczone za pomocą dwóch różnych masek.

Powyższy efekt można uzyskać za pomocą kodu w OpenCV (C++).

Z powodu dużej wrażliwości filtru Laplacea na szum, często poprzedza się go wygładzeniem filtrem Gaussa (dokładny opis znajduje się w rozdziale Filtry). Przypomnijmy tylko wzór na dwuwymiarowy rozkład normalny o średniej równej zero i diagonalnej macierzy kowariancji z wartością $\sigma$ na przekątnej (pomijamy czynnik normalizujący):

\[ G(x,y)=  \exp\left( - \frac{x^2+y^2}{2\sigma^2} \right) \]

W takiej sytuacji możemy uzyskać filtr z rozmyciem dzięki operacji splotu

\[ (I*Gauss)*laplasjan = I*(Gauss*laplasjan) \]

Dzięki przemienności operacji splotu możemy wykonać filtr Laplacea z rozmyciem Gaussa za pomocą splotu z funkcją ($Gauss*laplasjan$). 

Ilustracja. Funkcja: $Gauss*laplasjan$.

 

 

Ilustracja. Oryginalny obraz oraz wynik algorytmu Laplacea z rozmyciem Gaussa.

Powyższy efekt można uzyskać za pomocą kodu w OpenCV (C++).

Metoda detekcji krawędzi - Canny

Metoda detekcji krawędzi Canny została opracowana przez Johna F. Canny w 1986 roku. Metoda używa zarówno pierwszych, jak i drugich pochodnych w celu wyznaczenia orjętacji oraz szybkości spadku gradientu.

Metoda Canny optymalizuje trzy podstawowe kryteria:

  1. minimalizować liczbę błednych detekcji, przy czym błędem detekcji jest zarówno detekcja krawędzi fałszywych (błędna odpowiedź pozytywna, false-positive detection), jak i pomijanie rzeczywistych krawędzi w obrazie (błędna odpowiedź negatywna, false-negative detection),
  2. zapewniać dokładną lokalizację krawędzi – punkt sklasyfikowany jako punkt krawędzi powinien być jak najbliższy środkowemu punktowi rzeczywistej krawędzi,
  3. generować pojedynczą odpowiedź dla kazdej rzeczywistej krawędzi w obrazie – jest to równoważne generowaniu krawędzi o grubości jednego piksela.

 

Ilustracja. Oryginalny obraz oraz wynik algorytmu Canny.

Powyższy efekt można uzyskać za pomocą kodu w OpenCV (C++).