LABORATORIUM
PRZETWARZANIA DŹWIĘKÓW I OBRAZÓW
Ćwiczenie nr 10
Kompresja fraktalna
Opracowali:
Mariusz Szulc SiST
Adam Wiechnik SiST
1.WSTĘP
Kompresja fraktalna jest jedną z metod kompresji obrazu opartą na jego samopodobieństwie. W roku 1990 Jacquin podał pierwszy, w pełni automatyczny, algorytm fraktalnej kompresji obrazów. Od tamtej pory obserwuje się stały wzrost zainteresowania tym tematem. Fraktalna kompresja obrazów jest dobrym narzędziem - daje wysoki stopień kompresji ze stosunkowo małym zniekształceniem obrazu. Ogólnie zniekształcenia , które wprowadza są mniej odczuwalne przez oko ludzkie niż w najpopularniejszej obecnie metodzie kompresji JPEG gdzie efektem ubocznym jest charakterystyczne zblokowanie pikseli.
Definicja fraktala:
- wedlug Mandelbrot'a „Fractal Geometry of Nature”:
nie są określone wzorem matematycznym, tylko zależnością rekurencyjną
maja cechę samopodobieństwa
są obiektami, których wymiar nie jest liczba całkowitą
Fraktalem na płaszczyźnie nazywamy dowolny niepusty i zwarty podzbiór płaszczyzny.
Teoria fraktali dala bardzo dobre narzędzie do modelowania obiektów samopodobnych. Chodzi tu oczywiście o IFS. Dzięki temu odpada niejako problem zapamiętywania całych atraktorow, wystarczy zapamiętać jedynie IFS, którego atraktor nas interesuje. Potem dokonujemy kolejnych iteracji, aż obraz nas zadowoli. Istotą fraktalnej kompresji obrazów jest potraktowanie obrazu jako atraktora pewnego zbioru odwzorowań zwężających. Jednak w przypadku rzeczywistych obrazów pojawiają się dwa główne
problemy:
w obrazie rzadko pojawia się podobieństwo typu fragment - podfragment, obserwowane we fraktalach. Zwykle mamy do czynienia z podobieństwem typu fragment - inny fragment. Przy tym jeszcze rzadziej zdarza się, żeby było to podobieństwo idealne. Zwykle trzeba uwzględnić jakąś miarę podobieństwa;
w przeciwieństwie do fraktali, w obrazach występuje skala szarości (kompresja fraktala dotyczy wyłącznie obrazów z poziomami szarości, obrazy kolorowe koduje się osobno dla każdej składowej). Dlatego też oprócz podobieństwa kształtu, trzeba również uwzględnić podobieństwo oraz transformacje skali szarości.
2.Kompresja „JPG”
Do oceny metody JPEG używano programu Corel Photo-Paint 8. Korzystano z przykładowych plików w formacie .bmp, które następnie zapisywane były w formacie JPEG przy różnych ustawieniach stopnia kompresji oraz wygładzania krawędzi. Zaobserwowano, że w zależności od ustawień metody współczynnik kompresji wahał się w granicach 1:1 do ponad 1:100, przy czym dla ustawień powyżej 1:20 dosyć wyraźne zaczynają być efekty uboczne kompresji, czyli zblokowanie pikseli a także rozmycie krawędzi. Efekty te uwidoczniają się jeszcze wcześniej jeśli plik wejściowy nie jest bitmapą 24-bitową a np. 256-kolorową. W praktyce często stosowane są prostsze implementacje tego algorytmu, niż w programie Corel Photo-Paint 8 umożliwiające np. ustawienie wymaganego stopnia kompresji bez możliwości kontroli jakości obrazu lub wręcz odwrotnie - zadawana jest żądana jakość
Obraz powiększony wygląda jak podzielony na wiele kwadratów, to widać przy GIF-ach i JPEG-ach
3.Program Professor Compressor
Korzystając z aplikacji Professor Compressor obejrzeliśmy obrazy zakodowane fraktalnie. Przy pomocy opcji „zoom” mogliśmy dokonać powiększeń oglądanego rysunku, zaś opcja „open” pozwoliła nam zapoznać się z parametrami kompresji.
nazwa pliku |
rozmiar oryginału |
rozmiar po komporesji |
stosunek kompresji |
bus.fif |
279 |
12 |
22 do 1 |
cions.fif |
1052 |
40 |
26 do 1 |
dolfins.fif |
675 |
23 |
30 do 1 |
highjump.fif |
1052 |
284 |
37 do 1 |
night.fif |
279 |
13 |
21 do 1 |
Widać, że kompresja fraktalna daje dobre efekty w każdym z badanych przypadków stopień kompresji jest stosunkowo wysoki. Dzięki opcji „zoom” dowiedziliśmy się że format FIF (Fractal Image Format) zapewnia możliwość „bezstratnego” powiększania fotografii i grafiki. Przy powiększaniu nie widać efektów ubocznych w postaci zblokowanych pikseli charakterystycznych np. dla metody JPEG. Ponadto wielkość zapisanych w tym formacie obrazów jest jeszcze mniejsza niż dla plików JPEG.
3. Program FractalVision
Żądany trójkąt Sierpińskiego, uzyskaliśmy pokrywając trójkąt równoboczny jego trzema pomniejszonymi o połowę kopiami pozostawiając pusty środek. Oto IFS tej figury :
W efekcie uzyskujemy następujący rysunek fraktalny:
Wymiar fraktalny tej figury wynosi 1,957337
Teraz przedstawiamy naszą prace:
IFS EFEKT
Wymiar fraktalny tej figury wynosi
Ponadto przeprowadziliśmy kilka doświadczeń aby zbadać związek między postacią uzyskanego atraktora a dokładnością pokrycia wyjściowej figury jej pomniejszonymi kopiami.
W tym celu wzięliśmy kwadrat i jego wnętrze wypełniliśmy dokładnie czterema zmniejszonymi o połowę kwadracikami. W efekcie uzyskaliśmy figurę będącą kwadratem o wymiarach kwadratu wejściowego. Ten sam eksperyment przeprowadziliśmy także dla trójkąta równobocznego wypełniając w przeciwieństwie do trójkąta Sierpińskiego także środek. Efekt był podobny jak dla kwadratu. Nie uzyskaliśmy takiego obrazu jaki przedstawiliśmy powyżej jako trójkąt Sierpińskiego, a jednolity trójkąt o wymiarach figury wejściowej.
IFS EFEKT
Wnioskować można z tego że im dokładniej pokryjemy figurę wyjściową jej pomniejszonymi kopiami tym „mniej efektowny” obraz uzyskamy. Jeśli znamy już sposób powstawania obrazu fraktalnego (a na podstawie poprzednich przykładów mięliśmy okazję go poznać) to taki efekt końcowy jest jak najbardziej logiczny. Ponadto zauważyliśmy, że im bardziej obraz wyjściowy jest pokryty kopiami tym jego wymiar fraktalny jest bardziej zbliżony do liczby 2.