Wykrywanie krawędzi

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Przykład wykrywania krawędzi

Wykrywanie krawędzi – celem detekcji krawędzi jest zaznaczenie punktów cyfrowego obrazu w których gwałtownie zmienia się luminancja. Ostre krawędzie na obrazie przeważnie odzwierciedlają ważne zdarzenia i zmiany w przedmiotach przedstawionych na zdjęciach. Zmiany luminancji mogą być wywołane:

  • zmianą głębokości,
  • zmianą orientacji powierzchni
  • zmianą właściwości materiału
  • różnorodnością oświetlenia scen.

Wykrywanie krawędzi jest częścią badań zajmujących się przetwarzaniem obrazu i postrzeganiem świata przez maszyny, z naciskiem na przyszłe jego wykorzystanie.

Wykrywanie krawędzi na obrazie zmniejsza znacząco ilość danych i filtruje informacje które mogą być postrzegane jako mniej znaczące, zachowując ważne własności struktur znajdujących się na obrazie. Jest wiele metod detekcji krawędzi, ale większość z nich może zostać zgrupowana w dwie kategorie, wykorzystujące badanie pierwszej pochodnej (metody gradientowe) i wykorzystujące badanie drugiej pochodnej. Pierwsze metody wykrywają krawędzie poprzez wyszukiwanie maksimów i minimów pierwszej pochodnej obrazu. Drugie metody poszukują przejścia przez zero w drugiej pochodnej obrazu. W celu znalezienia krawędzi, przeważnie stosuje się przejście przez zero operatora Laplace'a lub przejście przez zero nieliniowej różniczki.

Własności krawędzi[edytuj | edytuj kod]

Krawędzie mogą zależeć od punktu patrzenia – czyli krawędzie, które mogą się zmieniać wraz ze zmianą punktu patrzenia, typowo odzwierciedlające geometrię scen np. otaczanie obiektów przez inne. Lub mogą być niezależne od punktu patrzenia – odzwierciedlają one właściwości oglądanych obiektów takie jak znaki na powierzchni oraz kształty powierzchni. W przypadku dwu i więcej wymiarów powinno się rozważyć rodzaj perspektywy.

Typowe krawędzie mogą być np. granicą pomiędzy dwoma kolorami (czerwonym i żółtym); lub też linia może być małą liczbą pikseli innego koloru na niezmiennym tle. W takim wypadku będzie po jednej krawędzi po każdej stronie linii. Krawędzie grają ogromną rolę w wielu aplikacjach zajmujących się przetwarzaniem obrazu. Podczas ostatnich lat, jednakże, zostały przeprowadzone znaczące (i udane) badania nad postrzeganiem świata przez maszyny (ang. computer vision) które to nie do końca polegają na detekcji krawędzi jako pierwszym kroku przetwarzania.

Prosty model krawędzi[edytuj | edytuj kod]

Krawędzie na zdjęciach przedstawiających świat rzeczywisty nie są przykładem idealnych. Przeważnie są one obciążone jednym bądź większą liczbą niżej wymienionych efektów:

  • optyczne rozmazanie spowodowane skończoną głębokością obrazu.
  • półcieniowe rozmazanie spowodowane przez cień powstały od źródła światła o niezerowym promieniu.
  • cieniowanie na obiektach o łagodnych krawędziach.
  • lokalne odbicia lub wewnętrzne odbicia w krawędzi obiektu.

Chociaż poniższy model nie może być uważany za dokładny, funkcja błędu \operatorname{erf} jest powszechnie wykorzystywana przez programy w modelowaniu efektu rozmazania krawędzi. Tak więc jednowymiarowy obraz f który ma dokładnie jedną krawędź dla x = 0 może zostać przedstawiony w następujący sposób:

f(x) = \frac{I_r - I_l}{2} \left( \operatorname{erf}\left(\frac{x}{\sqrt{2}\sigma}\right) + 1\right) + I_l

Zatem, lewa strona krawędzi ma natężenie I_l = \lim_{x \rightarrow -\infty}f(x), a prawa strona I_r = \lim_{x \rightarrow \infty} f(x);gdzie \sigma jest nazywany wielkością rozmycia krawędzi. Należy zauważyć że f może również zostać zapisane jako splot f = g_\sigma * u gdzie g_\sigma jest funkcją Gaussa ze odchyleniem standardowym \sigma, a u jest funkcją skokową zdefiniowaną :

u(x)=\left\{\begin{matrix} I_l \ \mathrm{dla}\ x \leqslant 0\\ I_r \ \mathrm{dla}\ x > 0 \end{matrix}\right.

Detekcja krawędzi[edytuj | edytuj kod]

Pierwsza i druga pochodna na krawędzi luminancji.

Weźmy krawędź, którą można opisać jako zmianę luminancji, która to zmienia się na przestrzeni kilku, kilkunastu pikseli, algorytmy stosowane w takim przypadku w większości stosują obliczanie pierwszej pochodnej na przestrzeni zmian luminancji. Aby uprościć, możemy rozważyć detekcję krawędzi w jednowymiarowej przestrzeni. W takim przypadku, naszymi danymi będzie pojedyncza linia pikseli o różnej jasności. Na przykład, intuicyjnie możemy powiedzieć, że powinna być krawędź pomiędzy 4. a 5. pikselem na przedstawiony poniżej jednowymiarowym strumieniu danych:

5 7 6 4 152 148 149

Aby być dokładnym, określenie konkretnej wielkości skoku luminancji pomiędzy dwoma pikselami, aby można było stwierdzić że jest pomiędzy nimi krawędź nie zawsze jest łatwym zadaniem. Właśnie przez ten próg detekcja krawędzi nie jest łatwym problemem, chyba że obiekty w przestrzeni są wyjątkowo proste i mamy możliwość kontroli oświetlenia.

Liczenie pierwszej pochodnej[edytuj | edytuj kod]

Wiele metod detekcji krawędzi bazuje na pierwszej pochodnej luminancji – daje to nam stopień przyrostu (gradient) wartości oryginalnych danych. Wykorzystując tę informację możemy szukać ekstremów pierwszej pochodnej luminancji (gradientu luminancji).

Jeśli I(x) odzwierciedla luminancję piksela x, a I′(x) jest pierwszą pochodną (intensity gradient) piksela x, można zapisać :

I'(x)=-1/2\cdot I(x-1) + 0 \cdot I(x) + 1/2 \cdot I(x+1).\,

W celu przyspieszenia przetwarzania obrazu, pierwszą pochodną można obliczać (w 1D) za pomocą dyskretnej funkcji splotu, danych z maską:

−1/2 0 +1/2

Liczenie drugiej pochodnej[edytuj | edytuj kod]

Inne metody detekcji opierają się na drugiej pochodnej luminancji. Przedstawia ona tempo zmian pierwszej pochodnej luminancji (gradientu luminancji). W przypadku idealnej funkcji ciągłej, ustalenie przejścia przez zero w drugiej pochodnej określa lokalne ekstremum pierwszej pochodnej (gradientu). Detekcja szczytu w drugiej pochodnej natomiast, jest metodą określenia linii, jeśli tylko operator jest zaprojektowany na odpowiednią skalę. Jak zostało wspomniane wcześniej, linia posiada dwie krawędzie, w związku z tym zauważymy narastanie wartości pierwszej pochodnej po pierwszej stronie linii oraz odwrotną sytuację po drugiej stronie linii. Możemy więc zaobserwować bardzo duże zmiany gradientu luminancji (wartości pierwszej pochodnej po luminancji) w miejscu znajdowania się linii.

Aby znaleźć linię możemy także szukać przejść przez zero drugiej pochodnej gradientu luminancji (współczynnika nachylenia stycznej luminancji).

Jeśli I(x) reprezentuje luminancję punktu x, a I"(x) jest drugą pochodną w punkcie x:

I''(x) = 1\cdot I(x-1) - 2 \cdot I(x) + 1 \cdot I(x+1).\,

Tak samo jak w przypadku poprzednim większość algorytmów wykorzystuje splot danych z maską w celu przyspieszenia obróbki obrazu:

+1 −2 +1

Ustalanie progu[edytuj | edytuj kod]

Gdy mamy już obliczone nasze pochodne, następnym krokiem jest zastosować próg, aby określić miejsca które rzeczywiście są krawędziami a nie szumem. Im mniejszy próg, tym więcej linii zostanie wykrytych i wynik będzie w dużej mierze zależał od szumu oraz wykrywane będą nieistotne szczegóły znajdujące się w obrazie. W odwrotnym przypadku duży próg może spowodować przeoczenie niewyraźnych lub podzielonych linii.

Powszechnie używanym kompromisem jest wykorzystywanie progu z histerezą. Metoda ta wykorzystuje wiele progów w celu znalezienia krawędzi. Zaczyna się od górnego progu w celu znalezienia początku linii. Gdy mamy już punkt początkowy, podążamy ścieżką krawędzi na obrazie piksel za pikselem, zaznaczając krawędź gdy jesteśmy powyżej dolnego progu. Kończymy zaznaczanie w miejscach w których wartości są poniżej dolnego progu. To podejście zakłada, że krawędzie są ciągłymi liniami i dzięki temu pozwala nam podążać mało wyraźnymi krawędziami, bez świadomości że każdy piksel obarczony błędem w obrazie będzie zaznaczony jako krawędź.

Operatory wykorzystywane w detekcji krawędzi[edytuj | edytuj kod]

Obecnie, operator Canny'ego (lub wariacje tego operatora) jest najczęściej używaną metodą detekcji krawędzi. Opublikowana została duża liczba funkcji wykrywania krawędzi, ale – jak dotychczas – żadna z nich nie ukazała znaczącej przewagi nad operatorem Canny'ego w ogólnych sytuacjach. Podczas tworzenia algorytmu Canny zajmował się problemem stworzenia optymalnego filtru wygładzającego przed detekcją krawędzi, wykazał on dzięki temu że takim filtrem z dużą dokładnością może być funkcja bazująca na pierwszej pochodnej funkcji Gaussa.

Canny wprowadził także algorytm usuwania niemaksymalnych pikseli (non-maximum suppression). Na płaszczyźnie dyskretnej non-maximum suppression może zostać zaimplementowany jako wyznaczenie wektora kierunkowego za pomocą pierwszej pochodnej, następnie zaokrąglenie kierunku z dokładnością do 45 stopni i ostateczne porównanie wartości wielkości wyznaczonych wektorów kierunkowych. Bardziej wyrafinowanym sposobem otrzymywania krawędzi z dokładnością pomiędzypikselową jest wykorzystanie różniczki w detekcji przejść przez zero w drugiej pochodnej zgodnie z kierunkiem wektora (Lindeberg 1998):

L_x^2 \, L_{xx} + 2 \, L_x \,  L_y \, L_{xy} + L_y^2 \, L_{yy} = 0,

to wystarcza do określenia znaku trzeciej pochodnej tego samego wektora kierunkowego.

L_x^3 \, L_{xxx} + 3 \, L_x^2 \, L_y \, L_{xxy} + 3 \, L_x \, L_y^2 \, L_{xyy} + L_y^3 \, L_{yyy} < 0, gdzie L_x, L_y ... L_{yyy} są częściowymi pochodnymi

Redukcja szumu[edytuj | edytuj kod]

Oprócz rzeczywistych krawędzi podczas detekcji powstają także krawędzie fałszywe, związane jest to z występowaniem szumu w obrazie. Dzięki technikom redukcji szumu zastosowanym przed detekcją krawędzi, może zostać zmniejszona ilość fałszywych krawędzi

Bibliografia[edytuj | edytuj kod]

  • Canny, J., A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714 (1986).