Kompresja fraktalna

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

W USA kompresja fraktalna jest objęta wieloma patentami na oprogramowanie. Ze względu na problemy patentowe i istnienie znacznie lepszej metody falek kompresja fraktalna nigdy nie była szerzej stosowana w praktyce.

Zasada działania

Sposób podziału obrazu na części

Chcąc skompresować obraz najpierw należy podzielić go na mniejsze części, następnie poszukać podobieństw między małymi częściami a większymi od nich fragmentami obrazu. Na przykładowym obrazku łatwo można zauważyć, że części nr 2 i 3 wyglądają dokładnie tak jak pomniejszona całość. Jak się za chwilę okaże informacja ta plus informacja, że część nr 1 jest biała a część nr 4 czarna pozwoli odtworzyć cały obraz.

Rekonstrukcja obrazu – wygląd po pierwszej iteracji

Aby rozpakować nasz obrazek, bierzemy dowolny losowy obraz (na przykładzie szare tło) i malujemy część nr 1 na biało a część nr 4 na czarno, następnie zmniejszamy obraz czterokrotnie i wklejamy w miejsca 2,3 – powstało coś co przypomina schody, jeśli ponownie zmniejszymy całość i wkleimy w obszary 2 i 3 schody staną się drobniejsze. Powtarzając tę operację odpowiednio wiele razy "schodki" staną się mniejsze od wymiarów jednego pixela uzyskamy wówczas obraz bardzo podobny do oryginalnego.

Warto w tym miejscu zauważyć, że gdybyśmy rozpakowywanie rozpoczęli od większego obrazu to po wykonaniu najwyżej kilku powtórzeń więcej również uzyskamy ostrą krawędź. Możliwe jest więc powiększanie obrazu tak jak i innych fraktali

Użyte w przykładzie polecenia "weź kawałek obrazu z miejsca x pomniejsz i wklej w miejscu y" są właśnie tytułowymi funkcjami. Poza zmniejszaniem mogą one wykonywać też inne operacje na obrazie jak obroty czy zmianę jasności. Udowodniono matematycznie, że jeśli stosowane funkcje są odwzorowaniami zwężającymi, to niezależnie od jakiego obrazu zaczniemy proces dekompresji, kolejne iteracje zawsze będą przybliżać go do obrazu właściwego.

Bibliografia

• KhalidK. Sayood KhalidK., Kompresja danych – wprowadzenie, TomaszT. Jurdziński (tłum.), PawełP. Rychlikowski (tłum.), MarcinM. Młotkowski (tłum.), Warszawa: RM, 2002, ISBN 83-7243-094-2, OCLC 68662782 .