Kompresja fraktalna

Article on other languages:

• Fraktale_Bildkompression
• Fractal_compression
• Compression_fractale
• Compressione_frattale
• フラクタル圧縮
• Алгоритм_фрактального_сжатия

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się na stronie dyskusji tego artykułu w sekcji Dopracować Po wyeliminowaniu wskazanych powyżej niedoskonałości prosimy usunąć szablon {{Dopracować}} z kodu tego artykułu.

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ć jakiś obraz najpierw należy podzielić go na mniejsze części, następnie poszukać podobieństw między małymi częściami a jakimiś 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, ISBN 83-7243-094-2