LABORATORIUM

PRZETWARZANIA DŹWIĘKÓW I OBRAZÓW

Ćwiczenie nr 10

Kompresja fraktalna

Opracowali

Piotr Worobiej Janusz Trzeszewski

Janusz Popielewski

Dariusz Leśny

1.WSTĘP

Kompresja fraktalna jest jedną z metod kompresji obrazu opartą na jego samopodobieństwie. Pierwsze publikacje na temat fraktalnej kompresji obrazów ukazały się w roku 1986. Dopiero jednak 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. Na przykład o ile w roku 1993 ilość publikacji na temat fraktalnej kompresji obrazów wynosiła 21, to w roku 1994 tylko do maja ukazało się 18 prac na ten temat. Fraktalna kompresja obrazów wydaje się być bowiem dobrym narzędziem - daje wysoki stopień kompresji ze stosunkowo małym zniekształceniem obrazu.

Powstaje pytanie o definicję fraktala. W materiałach do których dotarliśmy za pośrednictwem internetu spotkaliśmy się ze stwierdzenie: "fraktalem jest wszystko". Jest ono zupełnie nieprecyzyjne. Mandelbrot w swej pracy „Fractal Geometry of Nature” podaje trzy główne własności fraktali:

• 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ą

Wymienione wyżej własności nie mogą jednak stać się podstawa do definicji ze względu na niejednoznaczności, które zawierają. 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.

Dzięki programowi Professor Compressor mogliśmy zapoznać się z efektami kompresji fraktalnej obrazów.

2.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. Oto wyniki:

nazwa pliku	rozmiar oryginału [kB]	rozmiar pliku po kompresji [kB]	stopień kompresji
BLONDE.FIF	374	17	22:1
BRIDGE.FIF	1116	41	27:1
COMPUTER.FIF	261	26	11:1
DOLPHIN.FIF	675	23	30:1
JUMBOJET.FIF	966	26	37:1

Jak widzimy kompresja fraktalna daje nam dobre rezultaty. W każdym z badanych przypadków stopień kompresji wynosił od kilkunastu do kilkudziesięciu. Jest to więc już znaczący rezultat. Ponadto dzięki opcji „zoom” poznaliśmy jeszcze jedną jakże ważną zaletę plików w formacie FIF (Fractal Image Format). Otóż podczas wyświetlania grafiki w różnych rozdzielczościach dużym problemem jest skalowanie cyfrowo zapisanych obrazów - powiększane tracą sporo na jakości. Format graficzny FIF zapewnia natomiast 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. Standard FIF staje się obecnie coraz bardziej popularny, gdyż korzysta z niego wiele aplikacji multimedialnych.

3. Program FractalVision

Korzystając z programu FractalVision wygenerowaliśmy trójkąt Sierpińskiego, który uzyskaliśmy pokrywając trójkąt równoboczny jego trzema pomniejszonymi o połowę kopiami pozostawiając pusty środek. IFS tej figury przedstawia poniższy rysunek.

W efekcie uzyskujemy następujący rysunek fraktalny:

Ze względu na to, że musięliśmy przedstawić to w formie czarno-białej efekt nie jest może tak czytelny, ale w formie kolorowej wygląda znacznie lepiej. Widzimy, że kolejne struktury w każdym z coraz mniejszych trójkątów są pomniejszonym odbiciem struktury IFS. Cała struktura rozbudowuje się jak gdyby coraz bardziej „w głąb”. Wymiar fraktalny tej figury wynosi 1,957337

Bardzo wiele satysfakcji przyniosła nam możliwość tworzenia własnych aproksymacji fraktalnych. Dwa, naszym zdaniem najbardziej efektowne owoce naszej pracy przedstawiamy poniżej:

IFS EFEKT

Wymiar fraktalny tej figury wynosi 1,852745.

IFS EFEKT

Wymiar fraktalny tej figury wynosi 1,722711

Zauważyliśmy, że im więcej pomniejszonych kopii figury wyjściowej zamieścimy w IFS-ie, tym gwiazdka jest bardziej gęsta, a drzewo posiada więcej gałązek i liści.

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.

---