Pochodne i krawędzie

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

Nadciąga druga pochodna

Naszym celem jest znalezienie miejsca, gdzie $ f(x,y) $ zmienia się najbardziej. Gdybyśmy operowali na funkcji jednej zmiennej $ g(x) $, oznaczałoby to rozwiązanie równania $ g''(x) = 0 $. My, żeby znaleźć krawędzie w dwóch wymiarach, będziemy rozwiązywać równanie: $ f_{xx}(x,y) + f_{yy}(x,y) = 0  $. Przez $ f_{xx} $ rozumiemy dwukrotne wzięcie pochodnej względem pierwszej zmiennej. Innymi słowy: $ f_{xx}(x,y) = \lim { f_x(x+h,y) - f_x(x,y) \over h } $.

Jak rozwiązać nasze równanie? W taki sam sposób, jak poprzednio - należy policzyć $ f_{xx}(x,y) + f_{yy}(x,y) $ w każdym pikselu i poszukać zer. Ważne jest, że znowu wyrażenie $ f_{xx}(x,y) + f_{yy}(x,y) $ również daje się ładnie przybliżyć za pomocą $ u[i,j] $. Na przykład można $ f_{xx}(x,y) + f_{yy}(x,y) $ przybliżyć takim wyrażeniem:

$$u[i+2,j] + 2u[i+1,j] + 2u[i-1,j] + u[i-2,j] + $$
$$u[i,j+2] + 2u[i,j+1] + 2u[i,j-1] + u[i,j-2] - 16 u[i,j]$$

To pozwoli zapisać nam następujący algorytm:

1
2
3
4
5
6
 u - obrazek wejściowy
 v - obrazek wyjściowy
 Dla i = 1..n
    Dla j = 1..m
        v[i,j] = przybliżenie fxx + fyy
 Znajdź zera v[i,j] i oznacz je jako krawędzie

Jak znaleźć zera v[i,j]? Oczywiście najprościej zrobić to tak:

1
2
3
4
 Dla i = 1..n
    Dla j = 1..m
        Jeżeli v[i,j] == 0
            v ma w (i,j) zero
Proste prawda? Niestety, za proste. W ten sposób wielu miejsc zerowych $ f_{xx}(x,y) + f_{yy}(x,y) $ zwyczajnie nie wykryjemy. Dlaczego? Jeżeli v[i,j] = 1 oraz v[i+1,j] = -1, to wiemy że gdzie między punktem (i,j) a (i+1,j) jest zero. Ale nasz algorytm tego nie wykryje. Dlatego rzeczywiste algorytmy nie szukają tych pikseli, gdzie v[i,j] jest równe zero, tylko tych, gdzie v[i,j] zmienia znak.

alternative text Wynik działania powyższego algorytmu. Na obrazku jest zdecydowanie za dużo krawędzi. I sporo szumów. Ale krawędzie tworzą zamknięte kształty. A większość z nich ma szerokość jednego piksela.

Spróbujmy ocenić powyższy obrazek. Wydaje się, że jest w nim za dużo krawędzi. Dlaczego tak jest? Spróbujmy jeszcze raz użyć nasz intuicji z jednego wymiaru. Szukamy miejsc, gdzie funkcja $ g(x) $ zmienia się najszybciej. W tym celu szukamy lokalnych maksimów funkcji $ g'(x) $ rozwiązując równanie $ g''(x) = 0 $. Ale w ten sposób popełniamy dwa błędy. Po pierwsze $ g''(x) = 0 $ jest warunkiem koniecznym, ale nie wystarczającym na maksimum funkcji $ g'(x) $. Jego rozwiązania mogą być również punktami przegięcia, albo (co gorsza!) jej minimami.

Czy to nie zaskakujące, że sprawy takie jak: punkt przegięcia, maksimum i minimum, kojarzące się z czystą (i nudną!) teorią znajdują tutaj zastosowanie? Fajnie się przekonać, że wiedza z analizy matematycznej przydaje się w praktyce.

Po drugie, nawet jeżeli w $ x $ jest lokalne maksimum, to nie wiemy jeszcze, czy jest ono wystarczająco duże z globalnego punktu widzenia. Innymi słowy: nawet jeżeli w $ x $ jest lokalne maksimum funkcji $ g'(x) $, to nie jesteśmy jeszcze pewnie, czy wartości funkcji $ g'(x) $ jest tam na tyle duża, byśmy uznali ten punkt za krawędź.

Jak temu zaradzić? W artykule proste przetwarzanie obrazów można przeczytać o rozmywaniu obrazka. Zastosujemy ten trik, mając nadzieję, że po rozmyciu na obrazku zostaną na nim tylko ważne krawędzie. Daje nam to następujący algorytm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 u - obrazek wejściowy
 v - obrazek wyjściowy
 Rozmyj obrazek u
 Dla i = 1..n
    Dla j = 1..m
        v[i,j] = u[i+1,j] + u[i,j-1] + u[i,j+1] + u[i-1,j] - 4 u[i,j]
 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

Sposób rozmycia obrazka $ u $ jest parametrem algorytmu. To znaczy: zależnie od tego, jakiej metody użyjmy i jak bardzo go rozmyjemy, dostaniemy różne wyniki.

alternative text Wynik działania algorytmu naszego przy zastosowaniu średniego rozmycia.
alternative text Wynik działania algorytmu naszego przy zastosowaniu mocnego rozmycia. Spowodowało ono, że krawędzie nie zostały zachowane i rozpłynęły się na wiele maksimów i minimów lokalnych. Na tym przykładzie widać, że wszystkich metod należy używać z umiarem i zastanowieniem. Trochę rozmycia daje dobre efekty, ale za dużo powoduje niespodziewane skutki.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com