Filia Uniwersytetu w Białymstoku

Wydział ekonomiczno – informatyczny

Zastosowanie fraktali w Informatyce

Wykonała: Wioleta P.

Grupa: L1

Wilno, 2012

Co to jest fraktal?

Fraktal, według definicji encyklopedycznej to obiekt, dla którego wymiar fraktalny (Hausdorffa-Besicovitcha) jest większy od wymiaru topologicznego.

Według definicji „potocznej” fraktal jest obiektem samopodobnym – tzn. takim, którego części są podobne do całości – lub „nieskończenie subtelny” czyli taki, który ukazuje subtelne detale nawet w wielokrotnym powiększeniu danego obrazu.

Ze względu na olbrzymią różnorodność przykładów matematycy obecnie unikają podawania ścisłej definicji i proponują określać fraktal jako zbiór, który:

• ma nietrywialną strukturę w każdej skali

• struktura ta nie daje się łatwo opisać w języku tradycyjnej geometrii euklidesowej

• jest samopodobny, jeśli nie w sensie dokładnym, to w przybliżonym lub stochastycznym

• jego wymiar Hausdorffa jest większy niż jego wymiar topologiczny

• ma względnie prostą definicję rekurencyjną

• ma naturalny wygląd („poszarpany”, „kłębiasty”, itp.)

Fraktale w Informatyce

W 1991 roku podczas zjazdu SIGGRAPH (Special Interest Group of the Association for Computing Machinery (ACM)) przedstawiono zastosowanie geometrii fraktalnej do analizy obrazu. Zaprezentowano techniki binarnego cieniowania, stosowanego do wprowadzenia odcieni szarości do monochromatycznego urządzenia graficznego, takiego jak np. drukarka laserowa. Innym zastosowaniem jest analiza graficzna z wykorzystaniem transformacji fraktalnych oraz kompresja fraktalna. Jak wiadomo za pomocą prostej rekurencji można uzyskać skomplikowany fraktal i to założenie stało się istotą pomysłu na kompresję fraktalną. Definiując - kompresja polega na takiej zmianie struktury danych, aby w efekcie zmniejszyły one swój rozmiar. Kompresja dzieli się na:

• jakościową, w której dane ulegają zmianie i nie są identyczne jak ich pierwowzór, jednakże zazwyczaj nie są to znaczne straty,

• ilościową (bezstratną), nie powodującą żadnych zmian w danych.

Kompresja fraktalna to system kompresji stratnej opierający się na wykorzystaniu fraktali do reprezentacji danych. Używany jest prawie wyłącznie do kompresji obrazów. Najpopularniejszym zestawem fraktali są systemy funkcji iterowanych (IFS - Iterated Functions System). Kompresja fraktalna daje dobre wyniki zarówno przy bardzo wysokim stopniu kompresji (czyli niskiej jakości) jak i wtedy gdy chcemy zachować wysoką jakość, jednak w tym drugim przypadku skompresowanie obrazu jest operacją bardzo czasochłonną.

Kolejnym elementem wartym omówienia jest współczynnik kompresji. Jest to miara stosunku rozmiaru danych pierwotnych do ich rozmiaru po kompresji. Jeśli rozmiar danych po kompresji zmalał dwukrotnie, to współczynnik kompresji wynosi 2:1. Im ten współczynnik jest większy, tym kompresja jest silniejsza. Programy komputerowe mogą osiągnąć maksymalnie współczynnik kompresji rzędu 16:1. Przeciętnie 2:1 - 5:1. Oficjalny format wykorzystujący kompresję fraktalną to IFS (Iterative Function Systems) firmy Iterative Systems. Algorytmy jej produkcji pozwalają uzyskać kompresję o współczynniku nawet 10000:1. Kompresja trwa bardzo długo, natomiast dekompresja jest błyskawiczna. Kompresja fraktalna polega na znajdowaniu podobieństwa pomiędzy poszczególnymi fragmentami obrazu.

Obraz najpierw dzielony jest na niewielkie obszary zwane płatkami, które całkowicie pokrywają jego powierzchnie. Następnie, dla każdego płatka wyszukuje się taki inny obszar obrazu, który po odpowiednich transformacjach będzie najbardziej zbliżony do oryginału. Kiedy znajdzie się przekształcenia dla wszystkich płatków, uzyskamy informacje wystarczające do zapisu pliku. Samopodobieństwo fragmentów obrazu jest opisywane za pomocą systemu IFS, więc przy szukaniu przekształcenia stosuje się tutaj wszelkiego rodzaju symetrie, obroty i skalowania. Dodatkowo wykorzystuje się różnicę jasności. Opisy tych transformacji składają się z niewielkiej ilości informacji, co daje w rezultacie wysoki stopień kompresji. Oto bardziej szczegółowy opis podobnego ale prostszego algorytmu: obraz jest dzielony na kwadratowe płatki o rozmiarze 2x2, 4x4, 8x8 lub 16x16 pikseli. Następnie obrazek rozdziela się na trzy składowe (RGB lub YUV) i każdy kompresuje osobno jako obraz w odcieniach jasności. Algorytm w trakcie działania powiększa każdy płatek dwukrotnie, przyciemnia i szuka na całej powierzchni obrazu takiego fragmentu, który jest najbardziej do niego podobny, uwzględniając wszelkiego rodzaju transformacje. Do pliku wynikowego, zapisywane są współrzędne obszaru przekształcenia oraz względne rozjaśnienie.

Analiza fraktalna ma również znaczny wymiar estetyczny. Chodzi o CorelPhotoPaint program graficzny, który posiada moduł JuliaSetExplorer. Zastosowane w nim filtry fraktalne komponują wymieszane 24-bitowe tło dookoła położeń fraktala Julii lub żuka Mandelbrota – kontrolując pętlę, liczbę powtórzeń i kątowe położenie spirali. Pewne własności przestrzeni fraktalnej takie jak uniwersalność oraz wyostrzanie nieliniowe pewnych fragmentów obrazu kosztem innych powodują, iż analiza fraktalna znajduje coraz szersze zastosowanie. W każdym punkcie wykresu Mandelbrota istnieje inna czterowymiarowa przestrzeń zespolona, wewnątrz której leży nieskończony obszar Julii. Pozwala to na uzyskiwanie niekiedy wręcz niewiarygodnych efektów graficznych jak na rysunku, pamiętając jednak wciąż o tym, iż dla stworzenia kształtu fraktala Maldenbrota wystarczy kilka zaledwie linijek kodu programowego. Wydaje się, iż to właśnie metody nieliniowe w najbliższym czasie spowodują znaczny postęp zarówno w analizie jak i przesyłaniu sieciowym obrazu.

Tworzenie grafiki komputerowej - przy pomocy algorytmu możemy generować zarówno krzywe fraktalne jak i figury z nich złożone, które w rzeczywistości wyglądają jak linie brzegowe, całe wyspy, góry czy chmury. Zapamiętując jedynie dwa początkowe punkty i wysokości trójkątów, możemy zapamiętać dowolną łamaną używając stosunkowo niewielkiej ilości pamięci.

Powiększanie obrazów – dzięki zastosowaniu algorytmu wykorzystującego fraktale, możemy powiększać dany obraz, ponieważ obraz będzie miał nieskończoną rozdzielczość. Brakujące fragmenty nie będą co prawda odtwarzane dokładnie, lecz piksele staną się punktami, a nie kwadratami jak w grafice rastrowej.