poniedziałek, 5 marca 2012

Algorytm Perona-Malik

Pełny kod źródłowy
Jak usunąć szum z obrazu nie tracąc przy okazji cennej informacji o lokalizacji krawędzi? Odpowiedź na to pytanie można znaleźć w mojej Rozprawie doktorskiej w rozdziale 3.2 - Nieliniowe wygładzenie obrazu bazujące na funkcji Gaussa. Rozpoczyna się on tak:

Pomimo tego, że rozmycie funkcją Gaussa lepiej sobie radzi z zachowaniem granic między obiektami niż zastosowanie średniej arytmetycznej, to w rzeczywistości każdy punkt jest tak samo przetwarzany, niezależnie od tego czy leży wewnątrz obiektu, czy też w pobliżu jego granicy. Jest to znana cecha filtrów liniowych. Skuteczniejszym rozwiązaniem mogłoby się okazać indywidualne traktowanie każdego punktu w zależności od jego lokalizacji, tak aby proces filtracji był wzmocniony na obszarach jednolitych, a zahamowany w pobliżu krawędzi. Jedną z pierwszych prac w tym zakresie był artykuł Perona i Malika[53].

[53] P. Perona, J. Malik. Scale-space and edge detection using anisotropic diffusion. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(7):629–639,July 1990.
[Rozprawa doktorska, str. 28]

Nie będę tutaj powtarzał treści, którą można doczytać we właściwym tekście rozprawy. Chciałbym jedynie podzielić się dodatkowymi materiałami, które opracowałem przy okazji jej pisania.

Najpierw chciałbym polecić rozprawę doktorską Bartosza Jabłońskiego "Równania różniczkowe cząstkowe w problemach filtracji obrazów i trajektorii przestrzennych" jako świetne wprowadzenie do tematyki nieliniowej filtracji obrazów. Jest ona w całości dostępna w sieci jako plik PDF. Drugi rozdział tej pracy "Porównanie metod filtracji dla obrazów dwuwymiarowych" to w mojej opinii najlepszy polskojęzyczny materiał na ten temat.

Ja osobiście poza krótkim opisem w rozprawie jak działa algorytm Perona-Malik i porównaniem tego algorytmu do klasycznej filtracji Gaussa mogę podzielić się jeszcze jego implementacją. Opracowałem ją na podstawie książki "Mathematical Problems in Image Processing" (autorzy: Gilles Aubert i Pierre Kornprobst) z wykorzystaniem biblioteki CImg. Kod jest dostępny w moim publicznym repozytorium GitHub.

I jeszcze na "deser" prezentacja działania algorytmu Perona-Malik dla kilku wybranych obrazów.

7 komentarze:

Anonimowy pisze...

Czy podobnych efektów nie uzyska się przez zastosowanie po prostu filtracji medianowej (pod warunkiem, że nie zależy nam bardzo na wprowadzeniu nowych wartości uśrednionych przez okno filtru konwolucyjnego)?
Mediana nie wymaga ona liczenia gradientu w celu wykrycia krawędzi a zachowuje brzegi obszarów. Podejrzewam, że filtr medianowy może być obliczony szybciej niż złożenie dwóch filtrów splotowych + gradient (szczególnie dla obrazów 3D).
Całkiem fajny artykuł ;-)

Rafał Petryniak pisze...

Oczywiście, zgadzam się, mediana i średnia są znacznie szybsze od filtrów iteracyjnych. Jeśli to tylko możliwe to najlepiej korzystać najpierw ze średniej, później z mediany, a na końcu z filtrów bardziej zaawansowanych.

Co do samej mediany to prawda, że daje ona zazwyczaj lepsze efekty od średniej. Wynika to jednak tylko z tego, że nie jest ona tak czuła na skrajne wartości jak średnia. Nic poza tym. Osobiście nie zaliczyłbym tej funkcji do funkcji jakoś szczególnie "inteligentnych". Nie zastanawia się ona co jest na obrazie i traktuje każdy punkt praktycznie tak samo. Inaczej jest z funkcjami anizotropowymi, które starają się najpierw sprawdzić, co jest na obrazie, a dopiero później wykonać stosowne wygładzenie.

Co po porównania mediany i algorytmu Perona-Malik to napisałem na ten temat parę zdań w swojej rozprawie na stronie:
http://www.scribd.com/fullscreen/81685046?start_page=41

Wprowadzenie nowych wartości to też nic strasznego. Jeśli poprzednie nie były "najlepsze" to po co się przy nich upierać. I tak nie mamy pewności, czy oryginalne wartości odpowiadają wartościom "właściwym" - przecież są i tak zmienione przez szum.

Anonimowy pisze...

Fajnie! Dzięki za odpowiedź. Może skoro filtr P-M to iteracyjny algorytm działający lokalnie to warto by go zaimplementować na GPU? Z video "na oko" efekty prawie takie same jak po medianie, no nie?

T. H.

Rafał Petryniak pisze...

Co po go implementować skoro ktoś inny to już zrobił: http://www.mathworks.com/matlabcentral/fileexchange/24299-gpu-perona-malik-anisotropic-diffusion ;-)

Anonimowy pisze...

To dziecko na zdjęciu jest jakieś takie smutne... to nie może dobrze działać ;-)

Kachna pisze...

Bardzo ciekawy wpis, gratuluję też bloga. Interesują mnie podobne zagadnienia, zwłaszcza algorytmika

Rafał Petryniak pisze...

Dziękuję. To jest tematyka, którą jak się pogłębi to można robić wiele ciekawych rzeczy. Nie zawsze jednak wszystko wychodzi tak jakbyśmy sobie tego życzyli. W przetwarzaniu obrazu jest trochę magii. Niestety nie każde zaklęcie działa :-)

Prześlij komentarz