Wykrywanie krawędzi

Wykrywanie krawędzi – proces polegający na zaznaczeniu 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.

Przykład wykrywania krawędzi

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 liczbę 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) lub 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

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 czy 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ż linią o grubości małej liczby 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, zostały jednakże 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

Krawędzie na zdjęciach przedstawiających świat rzeczywisty nie są przykładem granic 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\to -\infty }f(x),$ a prawa strona $I_{r}=\lim _{x\to \infty }f(x),$ gdzie $\sigma$ jest nazywane 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 z 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

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 przedstawionym 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 możemy kontrolować oświetlenie.

Liczenie pierwszej pochodnej

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ą (ang. 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

Obliczanie drugiej pochodnej

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, jest natomiast 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żna 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

Gdy mamy już obliczone nasze pochodne, następnym krokiem jest zastosowanie progu, 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

• pierwszego rodzaju: krzyż Robertsa, Prewitt, Sobel, Canny, Scharr,
• drugiego rodzaju: Marr-Hildreth, detekcja przejścia przez zero drugiej pochodnej zmiany luminancji obrazu.

Obecnie operator Canny’ego (lub wariacje tego operatora) są 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 (ang. 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° 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,$

co 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},\dots L_{yyy}$ są częściowymi pochodnymi.

Redukcja szumu

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

• Cezary Bołdak: Cyfrowe Przetwarzanie Obrazów – Wykład 4 – Wykrywanie cech w obrazach cyfrowych. Politechnika Białostocka. [dostęp 2010-01-16].
• Pratt W. K.: Digital image processing. John Willey &Sons, Inc, 2001.Sprawdź autora:1.brak strony w książce str. 443-509
• Canny, J., A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714 (1986).