Fraktaalikuvan pakkaus on häviöllinen kuvanpakkausalgoritmi , joka perustuu iteroitujen funktioiden (yleensä affinimuunnosten ) soveltamiseen kuviin. Tämä algoritmi tunnetaan siitä tosiasiasta, että joissakin tapauksissa se mahdollistaa erittäin korkeiden pakkaussuhteiden ja hyväksyttävän visuaalisen laadun saavuttamisen luonnon esineiden todellisille valokuville. Patentoinnin vaikean tilanteen vuoksi algoritmia ei käytetty laajalti.
Fraktaalikoodausmenetelmän perustana on itsekaltaisten alueiden havaitseminen kuvasta. Michael Barnsley ( englanniksi Michael Barnsley [1] ) ja Alan Sloan ( englanniksi Alan Sloan ) tutkivat ensimmäistä kertaa mahdollisuutta soveltaa iteroitujen funktioiden järjestelmien teoriaa ( English Iterated Function System, IFS ) kuvan pakkausongelmaan. ). He patentoivat ideansa vuosina 1990 ja 1991 ( US-patentti 5 065 447 ). A. Jaquin ( fr. Arnaud Jacquin ) esitteli fraktaalikoodauksen menetelmän, jossa käytetään domain- ja rank image blocks -järjestelmiä ( englanniksi domain and range subimage blocks ), neliön muotoisia koko kuvan peittäviä lohkoja. Tästä lähestymistavasta tuli perusta useimmille fraktaalikoodausmenetelmille. Yuval Fisher ja monet muut tutkijat ovat parantaneet sitä .
Tämän menetelmän mukaisesti kuva jaetaan joukoksi ei-päällekkäisiä arvoalikuvia ( eng. range subimages ) ja määritetään joukko päällekkäisiä verkkoalueen alikuvia ( eng. domain subimages ). Jokaiselle arvolohkolle koodausalgoritmi löytää sopivimman toimialuelohkon ja affiinin muunnoksen, joka kartoittaa tämän toimialuelohkon annettuun arvolohkoon. Kuvan rakenne on kartoitettu arvolohkojen, toimialuelohkojen ja muunnosten järjestelmään.
Ajatus on seuraava: oletetaan, että alkuperäinen kuva on jonkin supistuskartoituksen kiinteä piste. Sitten itse kuvan sijaan tämä kartoitus voidaan muistaa jollain tavalla, ja sen palauttamiseksi riittää, että tätä kartoitusta käytetään toistuvasti mihin tahansa aloituskuvaan.
Banachin lauseen mukaan tällaiset iteraatiot johtavat aina kiinteään pisteeseen, eli alkuperäiseen kuvaan. Käytännössä vaikeus on löytää kuvasta sopivin pakkauskartoitus ja sen kompakti tallennus. Tyypillisesti kartoitushakualgoritmit (eli pakkausalgoritmit) ovat erittäin raakaa voimaa ja laskennallisesti kalliita. Samaan aikaan palautusalgoritmit ovat varsin tehokkaita ja nopeita.
Lyhyesti sanottuna Barnsleyn ehdottama menetelmä voidaan kuvata seuraavasti. Kuva on koodattu useilla yksinkertaisilla muunnoksilla (tapauksessamme affiineilla), eli se määräytyy näiden muunnosten kertoimilla (tapauksessamme A, B, C, D, E, F).
Esimerkiksi Koch-käyrän kuva voidaan koodata neljällä affiinilla muunnolla, joka määrittää sen yksilöllisesti käyttämällä vain 24 kerrointa.
Seuraavaksi laitetaan musta piste mihin tahansa kuvan kohtaan, sovelletaan muunnoksia satunnaisessa järjestyksessä muutaman (riittävän suuren) monta kertaa (tätä menetelmää kutsutaan myös fraktaaliping-pongiksi).
Tämän seurauksena piste menee välttämättä jonnekin alkuperäisen kuvan mustan alueen sisään. Kun tällaista toimintoa on käytetty useita kertoja, kaikki musta tila täytetään, mikä palauttaa kuvan.
Fraktaalipakkauksen suurin vaikeus on se, että tarvitaan kattava haku vastaavien verkkoaluelohkojen löytämiseksi. Koska kahta taulukkoa on verrattava joka kerta, tämä operaatio osoittautuu melko pitkäksi. Suhteellisen yksinkertaisella muunnoksella se voidaan pelkistää kahden taulukon skalaaritulon operaatioon, mutta jopa skalaaritulon laskeminen vaatii melko pitkän ajan.
Tällä hetkellä[ milloin? ] tunnetaan riittävän suuri määrä algoritmeja fraktaalipakkauksen aikana tapahtuvan laskennan optimoimiseksi, koska suurin osa algoritmia tutkineista artikkeleista oli omistettu tälle ongelmalle ja aktiivisen tutkimuksen aikana (1992–1996) julkaistiin jopa 300 artikkelia vuodessa. . Kaksi tutkimusaluetta osoittautuivat tehokkaimmaksi: piirteiden erotusmenetelmä ja alueiden luokittelumenetelmä.
Michael Barnsley ja muut ovat saaneet useita patentteja fraktaalikompressioon Yhdysvalloissa ja muissa maissa. Esimerkiksi 4,941,193 , 5,065,447 , 5,384,867 , 5,416,856 ja 5,430,812 . Nämä patentit kattavat laajan valikoiman mahdollisia muunnoksia fraktaalikompressioon ja haittaavat vakavasti sen kehitystä.
Nämä patentit eivät rajoita tutkimusta tällä alueella, eli voit keksiä omia algoritmeja patentoitujen pohjalta ja julkaista niitä. Voit myös myydä algoritmeja maihin, joita patentit eivät kata. Lisäksi useimmat patentit ovat voimassa 17 vuotta hyväksymispäivästä ja vanhenevat useimpien patenttien osalta vuoden 2020 jälkeen, joten näiden patenttien kattamien menetelmien käyttö on taatusti ilmaista.
| Puristusmenetelmät _ | |||||||
|---|---|---|---|---|---|---|---|
| Teoria |
| ||||||
| Häviötön |
| ||||||
| Audio |
| ||||||
| Kuvat |
| ||||||
| Video |
| ||||||