A fraktál képtömörítés egy veszteséges képtömörítési algoritmus , amely iterált függvényrendszerek (általában affin transzformációk ) képekre történő alkalmazásán alapul. Ez az algoritmus arról ismert, hogy bizonyos esetekben nagyon magas tömörítési arányt tesz lehetővé elfogadható vizuális minőség mellett a természeti objektumok valódi fényképeihez. A szabadalmaztatás nehéz helyzete miatt az algoritmust nem alkalmazták széles körben.
A fraktálkódolási módszer alapja a képen lévő önhasonló területek detektálása. Először Michael Barnsley ( angol Michael Barnsley [1] ) és Alan Sloan ( angol Alan Sloan ) vizsgálta az iterált függvényrendszerek elméletének ( angol Iterated Function System , IFS ) alkalmazásának lehetőségét a képtömörítés problémájára. ). 1990-ben és 1991-ben szabadalmaztatták ötletüket (5 065 447 számú amerikai egyesült államokbeli szabadalom ). A. Jaquin ( fr. Arnaud Jacquin ) egy fraktálkódolási módszert mutatott be, amely a teljes képet lefedő, tartomány és rang képblokkok ( angol domain and range subimage blocks ) rendszereit használja, négyzet alakú blokkokat. Ez a megközelítés lett a legtöbb fraktálkódolási módszer alapja. Yuval Fisher és számos más kutató fejlesztette tovább .
Ezzel a módszerrel a képet nem átfedő rang-alképekre ( eng. range subimages ) osztjuk, és átfedő tartomány-alképeket ( eng. domain subimages ) határozunk meg. A kódoló algoritmus minden rangblokkhoz megtalálja a legmegfelelőbb tartományblokkot és egy affin transzformációt, amely ezt a tartományblokkot leképezi az adott rangblokkra. A kép szerkezete rangblokkok, tartományblokkok és transzformációk rendszerébe van leképezve.
Az ötlet a következő: tegyük fel, hogy az eredeti kép valamilyen összehúzódási leképezés fix pontja. Ekkor maga a kép helyett ezt a leképezést lehet valamilyen módon megjegyezni, és ennek visszaállításához elegendő ezt a leképezést többször alkalmazni bármely kezdő képre.
Banach tétele szerint az ilyen iterációk mindig egy fix ponthoz vezetnek, vagyis az eredeti képhez. A gyakorlatban a nehézséget a legmegfelelőbb tömörítési leképezés megtalálása a képből és annak kompakt tárolása jelenti. A leképezési keresési algoritmusok (azaz a tömörítési algoritmusok) jellemzően rendkívül brute-force-ok és számításilag költségesek. Ugyanakkor a helyreállítási algoritmusok meglehetősen hatékonyak és gyorsak.
Röviden, a Barnsley által javasolt módszer a következőképpen írható le. A képet több egyszerű transzformáció kódolja (esetünkben affin), vagyis ezen transzformációk (esetünkben A, B, C, D, E, F) együtthatói határozzák meg.
Például a Koch-görbe képe négy affin transzformációval kódolható, egyedileg definiálva azt mindössze 24 együttható használatával.
Ezután a kép tetszőleges pontjára fekete pontot helyezve néhány (elég nagy) számú alkalommal véletlenszerű sorrendben alkalmazzuk a transzformációkat (ezt a módszert fraktál ping-pongnak is nevezik).
Ennek eredményeként a pont szükségszerűen valahova az eredeti kép fekete területén belül lesz. Egy ilyen művelet többszöri alkalmazása után az összes fekete hely kitöltésre kerül, ami visszaállítja a képet.
A fraktáltömörítés fő nehézsége az, hogy kimerítő keresésre van szükség a megfelelő tartományblokkok megtalálásához. Mivel minden alkalommal két tömböt kell összehasonlítani, ez a művelet meglehetősen hosszadalmasnak bizonyul. Egy viszonylag egyszerű transzformációval két tömb skalárszorzatának műveletére redukálható, de még a skalárszorzat kiszámítása is meglehetősen hosszú időt vesz igénybe.
Pillanatnyilag[ mikor? ] kellően nagy számú algoritmus ismert a fraktáltömörítés során fellépő felsorolás optimalizálására, mivel az algoritmust tanulmányozó cikkek többsége ennek a problémának szólt, és az aktív kutatás során (1992–1996) évente akár 300 cikk is megjelent. . Két kutatási terület bizonyult a leghatékonyabbnak: a jellemző-kinyerési módszer és a tartományok osztályozási módszere.
Michael Barnsley és mások számos szabadalmat kaptak a fraktáltömörítésre az Egyesült Államokban és más országokban. Például 4,941,193 , 5,065,447 , 5,384,867 , 5,416,856 és 5,430,812 . Ezek a szabadalmak a fraktáltömörítés lehetséges módosításainak széles skáláját fedik le, és súlyosan akadályozzák annak fejlődését.
Ezek a szabadalmak nem korlátozzák a kutatást ezen a területen, vagyis szabadalmaztatottak alapján saját algoritmusokat találhatsz ki és publikálhatsz. Ezenkívül eladhat algoritmusokat olyan országokban, amelyekre nem vonatkoznak szabadalmak. Ráadásul a legtöbb szabadalom az elfogadástól számított 17 évig érvényes, és a legtöbb szabadalom esetében 2020 után jár le, így az ezen szabadalmak által lefedett módszerek használata garantáltan ingyenes lesz.
| Tömörítési módszerek | |||||||
|---|---|---|---|---|---|---|---|
| Elmélet |
| ||||||
| Veszteségmentes |
| ||||||
| Hang |
| ||||||
| Képek |
| ||||||
| Videó |
| ||||||