Złożone algorytmy detekcji krawędzi
 

przygotował
Cezary Aniśko
cezary@anisko.net

 
 
        Właściwie wszystkie koncepcje detekcji krawędzi zmierzają do znalezienia kompromisu pomiędzy wygładzaniem obrazu i jego następnym różniczkowaniem.
        Zajmę się teraz zagadnieniem splatania funkcji, gdyż, jak się okazuje, jest ono przydatne przy detekcji krawędzi. Splot dwóch funkcji f i h można zdefiniować jako nową funkcję g, taką, że:



Podstawiając u=x-t można łatwo wykazać, że f*h=h*f



Granice całkowania są w nieskończoności, ale funkcja h może mieć ograniczoną dziedzinę, czyli przyjmować niezerowe wartości w ograniczonym przedziale. Funkcja h jest nazywana filtrem albo matrycą.
        Omówioną wyżej funkcję splatania można wykorzystać do detekcji krawędzi, wprowadzając taki operator, który równocześnie wygładza i różniczkuje funkcję. Załóżmy, że f jest przekształcaną funkcją (obrazy, jak pamiętamy można traktować jako funkcje) a h filtrem wygładzającym. Wygładzanie prowadzi do funkcji g, zdefiniowanej wyżej. Ponieważ wygładzony obraz chcemy różniczkować, sprowadza się to do poszukiwania funkcji:



        Zakładając, że w nieskończoności funkcja h i jej pochodne osiągają wartość zero, otrzymujemy po całkowaniu przez części:



        Zatem cykl operacji wygładzania przez funkcję h i następnego różniczkowania można zredukować do wygładzania za pomocą pochodnej funkcji h ze znakiem minus: „-h”. Powyższe spostrzeżenie ma istotne znaczenie, gdyż wszystkie omawiane teraz przekształcenia wymagają znacznej liczby obliczeń i, w konsekwencji czasu.

        Omówię teraz bliżej jeden z bardziej zaawansowanych filtrów do detekcji krawędzi.
 

Gradient Canny-Deriche

        Canny zaproponował sposób detekcji krawędzi wykorzystujący zoptymalizowane filtry oparte na gradientach (gradientach! nie na laplasjanach). Wychodząc z teorii sygnałów zaproponował trzy kryteria charakteryzujące ilościowo własności filtru:

  • Pierwszym kryterium jest stosunek sygnału do szumu filtru zastosowanego do jednowymiarowego progu zakłóconego szumem – a ta cecha mówi nam, jak czuły na zakłócenia jest sam filtr.
  • Drugim kryterium jest odchylenie standardowe miejsca lokalizacji krawędzi przy tym samym, co wyżej, modelu – ten wskaźnik określa dokładność filtru.
  • Trzeci wskaźnik podaje liczbę krawędzi wykrytych w białym szumie i jest używany do ustalenia najmniejszej odległości pomiędzy wykrywanymi punktami krawędzi.
        Wszystkie te parametry mogą być wprowadzone na podstawie znajomości filtru i jego pochodnych.
        Naturalnie, pierwsze dwa kryteria stanowią swoje przeciwieństwo: radykalne wygładzenie da wprawdzie duży stosunek sygnału do szumu, ale może spowodować duże błędy przy lokalizacji krawędzi. W wyborze odpowiedniego optymalnego rozwiązania pomaga trzecie kryterium, które musi być minimalizowane w celu uniknięcia wielokrotnej detekcji jednej i tej samej krawędzi.
        Canny wprowadził optymalne filtry o ograniczonej dziedzinie, natomiast, Deriche rozszerzył zakres filtrów na zbiór funkcji o nieograniczonej dziedzinie. Stąd też zwykle omawiany algorytm detekcji krawędzi jest nazywany filtrem Canny-Deriche.

Filtr Canny-Deriche ma postać:



Natomiast pochodna:



h’ jest optymalnym filtrem z punktu widzenia kryteriów Canny.



        W przypadku funkcji dwóch zmiennych (a taką funkcją jest właśnie obraz) filtr Canny-Deriche przyjmuje postać:


        Omawiany filtr wymaga ogromnej liczby obliczeń. Dla filtru o rozmiarze n dla każdego punktu trzeba n2 operacji. Liczbę tę można zredukować do 2n, jeżeli ograniczymy się do dwóch liniowych filtrów: poziomego i pionowego. Ostateczny wynik otrzymujemy jako maksimum z tych dwóch cząstkowych obrazów. Obserwacja powyższego rysunku wskazuje, że taka aproksymacja daje poprawne wyniki.
        Odrębnym praktycznym problemem jest tutaj obliczanie wartości całki w granicach od minus do plus nieskończoności. Zamiast zawężania przedziału całkowania, co nieuchronnie prowadzi do utraty dokładności, stosuje się iteracyjne algorytmy, wykorzystujące technikę kolejnych przybliżeń.
 
        Na zakończenie rozważań o detekcji krawędzi warto wspomnieć o jeszcze jednym etapie analizy, który jest niekiedy stosowany, a mianowicie o wektoryzacji. Wektoryzacja polega na zamianie formy zapisu krawędzi: zamiast zbioru punktów traktuje je jako ciąg wektorów (ich długość zależy od stopnia uproszczenia obrazu). Taka zamiana pozwala na wykorzystanie do analizy na przykład metod geometrii analitycznej i jest przydatna m.in. przy:
 - analizie stereoskopowej,
 - rozpoznawaniu obiektów (np. sterowanie robotów),
 - rozpoznawaniu pisma.
Jednocześnie wektoryzacja ułatwia rozwiązywanie niektórych zagadnień pomiarowych, w szczególności pomiar długości.
 
Podsumowując podane informacje o detekcji krawędzi, można zaproponować następujący tok postępowania przy tej czynności:
  • wstępna obróbka obrazu (normalizacja, kontrast, itp.),
  • wygładzanie i różniczkowanie (mamy do dyspozycji dwie podstawowe drogi: gradienty i laplasjany),
  • wybór punktów należących do krawędzi (poprzez wyszukiwanie miejsc zerowych, binaryzacje lub binaryzacje z histerezą),
  • szkieletyzacja grubych linii (nie dotyczy to przypadku, gdy stosujemy detekcję miejsc zerowych),
  • ewentualna wektoryzacja.
Niestety taki tok postępowania nie gwarantuje dobrych wyników dla wszystkich analizowanych obrazów. Poprawna detekcja krawędzi w dużym stopniu zależy od właściwego doboru nie tylko sekwencji przekształceń, ale też i parametrów. Nawet przy sporym doświadczeniu zwykle będzie konieczne zastosowanie metody prób i błędów. Zwykle, mimo naszych starań, nie uda nam się otrzymać ciągłego obrazu krawędzi (albo będzie on niezbyt dokładnym odzwierciedleniem rzeczywistości). Problem ten szczególnie mocno dotyka automatyzacji algorytmów detekcji krawędzi.
 
 

  literatura (źródła)
 powrót do góry