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ą operacje 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
- Khalid Sayood, Kompresja danych - wprowadzenie, RM 2002,