Pochodne i krawędzie

20.04.2010 - Krzysztof Dryś
TrudnośćTrudnośćTrudnośćTrudność

Więcej informacji

Jak policzyć przybliżenie $ f_y(x,y) $, czyli pochodnej względem drugiego argumentu? Tak samo jak liczyliśmy przybliżenie $ f_x(x,y) $. Otóż $ f_y(x,y) = {f(x+h,y) - f(x,y) \over h} + O(h) $. Oznacza to, że możemy tę pochodną szacować przez $ u[x,y+1] - u[x,y] $. Czy w ten sposób dowiemy się czegoś nowego o naszym obrazku? Najlepiej sprawdzić to na przykładzie. Popatrzmy na program:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 u - obrazek wejściowy
 v - obrazek wyjsciowy
 p - paramter algorytmu
 Dla i = 1..n
    Dla j = 1..m
        v[i,j] = |u[i,j+1] - u[i,j]|
 k = p-kwantyl tablicy v
 Dla i = 1..n
    Dla j = 1..m
        jeżeli v[i,j] > k
            w v[i,j] jest krawędź
            v[i,j] = 255
        w przeciwnym razie
            w v[i,j] nie ma krawędzi
            v[i,j] = 0
Jedyne co się, zmieniło to to, że piszemy $ v[i,j] = |u[i,j+1] - u[i,j]| $, zamiast $ v[i,j] = |u[i+1,j] - u[i,j]| $. Przyjrzyjmy się obrazkowi, który ten program wygeneruje:

alternative text Wynik działania naszego algorytmu dla $ p=80\% $.

Obrazek ma podobne wady, jak poprzednie. Ale jest trochę inny. To znaczy: inne punkty zostały oznaczone jako krawędzie. Czyli niesie ze sobą dodatkowe informacje, które możemy wykorzystać. Postaramy się to zrobić w następnym programie.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 u - obrazek wejściowy
 ux - przybliżenie pochodnej względem x
 uy - przybliżenie pochodnej względem y 
 v - obrazek wyjściowy
 p - parametr algroytmu
 Dla i = 1..n
    Dla j = 1..m
        ux[i,j] = |u[i+1,j] - u[i,j]|
        uy[i,j] = |u[i,j+1] - u[i,j]|
        v[i,j] = ux[i,j] * ux[i,j] + uy[i,j] * uy[i,j]
 k = p-kwantyl tablicy v
 Dla i = 1..n
    Dla j = 1..m
        jeżeli v[i,j] > k
            w v[i,j] jest krawędź
            v[i,j] = 255
        w przeciwnym razie
            w v[i,j] nie ma krawędzi
            v[i,j] = 0
Jak działa ten algorytm? Pochodna z $ f(x,y) $ składa się z dwóch składników: $ f_x(x,y) $ i $ f_y(x,y) $. Pamiętamy, że długość wektora $ v = (x,y) $ to $ \sqrt{x^2 + y^2} $. Nasz algorytm liczy w każdym punkcie wektor pochodnej $ (f_x(x,y), f_y(x,y)) $, a następnie wybiera te punkty, w których wektor ma największą długość. W ten sposób wykorzystuje informację o obydwu pochodnych.

alternative text Wynik działania ostatniego algorytmu dla $ p=80\% $.

Obrazek wyprodukowany przez ten algorytm wygląda całkiem nieźle. Zastanówmy się jednak, jak spełnia założenia, które postawiliśmy sobie na początku. Krawędzie rzeczywiście mają szerokość jednego piksela. Jednak nie tworzą zamkniętych kształtów. Ponadto nasz algorytm wykrył nie tylko krawędzie, ale też dużo przypadkowych rzeczy - na przykład w lewej części obrazka widać dużo pojedynczych kropek, które zupełnie nie układają się w krawędzie!

Lepsze przybliżenie

Na koniec spróbujmy czegoś bardziej skomplikowanego. Do tej pory przybliżaliśmy $ f_{x} $ przez $ u[i+1,j] - u[i,j] $. Możemy jednak znaleźć lepsze przybliżenia! Na przykład takie:

$ f_{x}(x,y) = { - f(x+2h,y) + 8 f(x+h,y) - 8 f(x-h,y) + f(x02h,y) \over 12 h} + O(h^4) $

To oznacza, że jeżeli $ h $ zmniejszy się dwa razy, to błąd przybliżenia zmniejszy się przynajmniej $ 2^4 = 16 $ razy. Czyli to przybliżenie jest lepsze od tego, które stosowaliśmy poprzednio. Napiszemy teraz algorytm, który wykorzysta przybliżenia:

$ f_{x}(x,y) \approx { - u[x+2,y] + 8 u[x+1,y] - 8 u[x-1,y] + u[x-2,y] \over 12 h} $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 u - obrazek wejściowy
 ux - przybliżenie pochodnej względem x
 uy - przybliżenie pochodnej względem y 
 v - obrazek wyjściowy
 p - parametr algroytmu
 Dla i = 1..n
    Dla j = 1..m
        ux[i,j] = |- u[x,y + 2] + 8 u[x,y +1] - 8 u[x,y-1] + u[x,y - 2]|
        uy[i,j] = |- u[x,y + 2] + 8 u[x,y +1] - 8 u[x,y-1] + u[x,y - 2]|
        v[i,j] = ux[i,j] * ux[i,j] + uy[i,j] * uy[i,j]
 k = p-kwantyl tablicy v
 Dla i = 1..n
    Dla j = 1..m
        jeżeli v[i,j] > k
            w v[i,j] jest krawędź
            v[i,j] = 255
        w przeciwnym razie
            w v[i,j] nie ma krawędzi
            v[i,j] = 0
alternative text Wynik działania ostatniego algorytmu dla $ p=80\% $.

Dzięki zastosowaniu lepszego przybliżenia pochodnej, ten algorytm daje lepsze rezultaty. Krawędzie nie urywają się w połowie obrazka. Mniej jest też szumów. Za to część krawędzi jest grubsza - mają więcej niż jeden piksel szerokości. Co więcej, ten algorytm jest bardziej czasochłonny od poprzedniego, gdyż wyliczanie lepszego przybliżenia pochodnej zajmuje więcej czasu.

5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com