Canny

Canny – metoda detekcji krawędzi występujących w obrazie. Opracowana została ona przez Johna F. Canny w 1986 roku. Wykorzystuje wielostopniowy algorytm w celu detekcji wielu różnych krawędzi w obrazie. Najważniejszy jednak pozostaje fakt, że Canny przedstawił teorię obliczeniową wyjaśniającą zasadę działania tej metody.

Rozwój algorytmu Canny

Celem metody Canny jest określenie optymalnego algorytmu detekcji. Słowo „optymalny” oznacza tu:

• dobrą detekcję – algorytm powinien wykryć tak dużo krawędzi jak to tylko możliwe.
• dobre umiejscowienie – oznaczona krawędź powinna być jak najbliżej rzeczywistej krawędzi na obrazie.
• minimalną odpowiedź – konkretna krawędź powinna być oznaczona tylko raz, i jeśli tylko możliwe, zakłócenia (szum) w obrazie nie powinny tworzyć fałszywych krawędzi.

Aby spełnić powyższe wymagania Canny wykorzystał rachunek wariacyjny – technikę która wyszukuje funkcję, która optymalizuje dany funkcjonał. Optymalna funkcja w detektorze Canny’ego opisana jest przez sumę czterech wykładniczych warunków, ale może być przybliżona pierwszą pochodną funkcji Gaussa.

Kroki algorytmu Canny’ego

Redukcja szumu

Detektor krawędzi Canny’ego wykorzystuje filtr bazujący na pierwszej pochodnej funkcji Gaussa, ponieważ jest czuły na obecność szumu w surowym nieobrobionym obrazie. Więc, aby zacząć, należy dokonać splotu obrazu z filtrem Gaussa. Efektem tego działania jest lekko rozmazany obraz, który nie jest dotknięty pojedynczymi zakłóceniami w żaden znaczący sposób.

Poniżej mamy przykład filtru Gaussa 5x5, wykorzystywanego do obróbki obrazu z $\sigma$ = 1.4:

$\mathbf {B} ={\frac {1}{159}}{\begin{bmatrix}2&4&5&4&2\\4&9&12&9&4\\5&12&15&12&5\\4&9&12&9&4\\2&4&5&4&2\end{bmatrix}}*\mathbf {A}$

Szukanie natężenia gradientu obrazu

Krawędź na obrazie może być skierowana w różnych kierunkach. Algorytm Canny’ego wykorzystuje więc cztery filtry do detekcji poziomych, pionowych oraz przekątnych krawędzi na wygładzonym obrazie. Operatory detekcji krawędzi (np. Krzyż Robertsa, Prewitt, Sobel) zwracają wartości pierwszej pochodnej dla kierunku poziomego (Gy) i kierunku pionowego (Gx). Nachylenie (gradient, szybkość narastania) krawędzi oraz jej kierunek mogą być określone na podstawie poniższych wzorów:

$\mathbf {G} ={\sqrt {{\mathbf {G} _{x}}^{2}+{\mathbf {G} _{y}}^{2}}}\qquad \qquad \mathbf {\Theta } =\operatorname {arctan} \left({\frac {\mathbf {G} _{y}}{\mathbf {G} _{x}}}\right)$

Kąt detekcji krawędzi zaokrąglony jest do czterech przypadków reprezentujących pion, poziom oraz dwóch przekątnych (np. 0, 45, 90 i 135 stopni)

Usuwanie niemaksymalnych pikseli

Trzeci etap obejmuje „pocienianie” krawędzi w sposób zapewniający ich ciągłość. Efektem jest ciągła linia złożona z pojedynczych pikseli.

Progowanie z histerezą

Ostatni etap – progowanie ma na celu usunięcie nieistotnych krawędzi, które mają nachylenie (stromość) poniżej ustawionego progu. Progowanie z histerezą powoduje, że do już wykrytych krawędzi są dołączane następne piksele mimo spadku nachylenia, aż do osiągnięcia dolnego progu wykrywania. Takie postępowanie zapobiega dzieleniu krawędzi w miejscach słabszego kontrastu.

Podsumowanie

Algorytm Canny’ego można wykorzystać w wielu różnych środowiskach. Jego parametry pozwalają na takie ich modyfikacje, aby dostosować go do rozpoznawania krawędzi o różnych cechach, w zależności od aktualnych oczekiwań. Oryginalna praca Canny’ego, pochodne optymalnych filtrów prowadziła do Filtr o skończonej odpowiedzi impulsowej.

Bibliografia

• Canny, J., A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714 (1986).
• R. Deriche: Using Canny’s criteria to derive a recursively implemented optimal edge detector. The International Journal of Computer Vision, 1(2):167-187, maj 1987.brak strony w książce

Linki zewnętrzne

• John Canny’s home page
• Free Java implementation of Canny edge detector
• Canny edge detector implementation in ActionScript for the Flash Platform
• Canny edge detector in Mathematica
• Cezary Bołdak, Cyfrowe przetwarzanie obrazów. s. 36–48