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
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.
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
- Khalid Sayood, Kompresja danych – wprowadzenie, Tomasz Jurdziński (tłum.), Paweł Rychlikowski (tłum.), Marcin Młotkowski (tłum.), Warszawa: RM, 2002, ISBN 83-7243-094-2, OCLC 68662782.
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.