Pochodne i krawędzie

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

Analiza matematyczna i analiza obrazów

Do tej pory nasz obraz był przechowywany w tablicy $ u[i,j] $. Załóżmy przez chwilę, że tak naprawdę obraz nasz jest funkcją $ f(x,y) $. Ta funkcja mówi jaka jest jasność poszczególnych punktów obrazu. Ale tym razem te punkty, to nie piksele. To punkty w sensie matematycznym. O ile pisząc $ u[i,j] $ zakładamy, że znamy jasność skończonej ilości punktów, to pisząc $ f(x,y) $ mamy na myśli rzeczywisty obraz, więc x oraz y mogą być dowolne.

Jak szukalibyśmy krawędzi, gdybyśmy mieli dostęp do $ f(x,y) $? Krawędź to takie miejsce, gdzie $ f(x,y) $ zmienia się najbardziej gwałtownie. Miarą zmienność funkcji, jest jej pochodna. Tak więc miejsce, gdzie pochodna $ f(x,y) $ zmienia się najszybciej, to właśnie krawędzi. Aha, problemem może być to, że $ f(x,y) $ jest funkcją dwóch zmiennych. Jak policzyć jej pochodną?

Najpierw przypomnijmy sobie, jak liczyć pochodne funkcji jednej zmiennej. Pochodną funkcji $ g(x) $ jest $ g'(x) = \lim {g(x+h) - g(x) \over h} $. Podobnie można zdefiniować pochodną funkcji $ f(x,y) $. Tylko, że funkcja dwóch zmiennych ma nie jedną a dwie pochodne! Jak to możliwe?

Pochodna $ f(x,y) $, względem pierwszego argumentu to: $ f_x(x,y) = \lim {f(x+h,y) - f(x,y) \over h} $. Natomiast pochodna $ f(x,y) $ względem drugiego argumentu to: $ f_y(x,y) = \lim {f(x,y+h) - f(x,y) \over h} $.

Pochodne funkcji wielu zmiennych to dosyć skomplikowana sprawa. Ale my nie chcemy ich zrozumieć. My chcemy je wykorzystać! Dlatego, na razie wystarczy nam wiedzieć, że liczy się je bardzo podobnie do zwykłych pochodnych. I mają bardzo podobne właściwości.

Jaki to wszystko ma związek z szukaniem krawędzi? My zamiast funkcji $ f(x,y) $ mamy do dyspozycji macierz $ u[i,j] $. Co prawda, nie można policzyć pochodnej z macierzy, ale można policzyć przybliżenie pochodnej. Co to znaczy? Popatrzmy na wzór:

$ g'(x) = { g(x) + g(x+h) \over h} + O(h) $

Mówi on, że pochodną można przybliżyć przez wyrażenie $ { g(x) + g(x+h) \over h} $. Błąd przybliżenia wynosi $ O(h) $. Co to oznacza? Mówiąc najprościej: w najgorszym razie jest wprost proporcjonalny do $ h $. Innymi słowy: jeżeli zmniejszymy $ h $ dwa razy, to błąd zmniejszy się również (przynajmniej) dwa razy!

alternative text Wykres funkcji $ x \rightarrow f(x,200) $, czyli inaczej mówiąc przebieg jednego wiersza naszego obrazka. Gwałtowne zmiany funkcji odpowiadają krawędziom.
alternative text Wykres funkcji $ x \rightarrow f_x(x,200) $, czyli inaczej mówiąc przebieg przybliżenia pochodnej w jednym wierszu naszego obrazka. Miejsca, gdzie funkcja jest największa (bądź najmniejsza), odpowiadają krawędziom.

I co z tego? Załóżmy, że w tablicy u[i,j] pamiętamy wartości funkcji $ f(x,y) $ dla całkowitych par $ (x,y) $ z pewnego przedziału. Wtedy, na podstawie tego co zobaczyliśmy przed chwilą, możemy wywnioskować, że $ u[i+1,j] - u[i,j] $ jest przybliżeniem $ f_x(x,y) = \lim {f(x+h,y) - f(x,y) \over h} $. Oznacza to, że na samym początku, nawet o tym nie wiedząc, liczyliśmy przybliżoną wartość pochodnej. Potem, wyznaczyliśmy punkty w których przybliżona pochodna ma największą wartość. I właśnie je oznaczyliśmy, jako zawierające krawędź.

Wiemy już, jak działa nasz prosty filtr. Liczy on przybliżenie pochodnej, a następnie patrzy gdzie jest ono maksymalne. Czy teraz możemy go jakoś ulepszyć? Można zrobić to na dwa sposoby:

  • Póki co,żeby znaleźć miejsca, gdzie $ f(x,y) $ zmienia się najbardziej korzystaliśmy tylko $ f_x(x,y) $, czyli pochodnej względem pierwszego argumentu. Warto jednak wykorzystać również $ f_y(x,y) $, czyli pochodną względem drugiego argumentu.
  • Chcemy znaleźć miejsce, gdzie pochodna $ f(x,y) $ jest największa. Ale w tym celu również najlepiej użyć pochodnych! Warunkiem koniecznym na maksimum $ g'(x) $ jest $ g''(x) = 0 $.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com