Compresia imaginii fractale este un algoritm de compresie a imaginii cu pierderi bazat pe aplicarea sistemelor de funcții iterate (de obicei transformări afine ) imaginilor. Acest algoritm este cunoscut pentru faptul că în unele cazuri permite obținerea unor rapoarte de compresie foarte mari cu o calitate vizuală acceptabilă pentru fotografii reale ale obiectelor naturale. Din cauza situației dificile cu brevetarea, algoritmul nu a fost utilizat pe scară largă.
Baza metodei de codificare fractală este detectarea zonelor auto-similare dintr-o imagine. Pentru prima dată, posibilitatea aplicării teoriei sistemelor de funcții iterate ( English Iterated Function System, IFS ) la problema compresiei imaginii a fost investigată de Michael Barnsley ( engleză Michael Barnsley [1] ) și Alan Sloan ( engleză Alan Sloan ). ). Ei și-au brevetat ideea în 1990 și 1991 ( brevetul SUA 5.065.447 ). A. Jaquin ( fr. Arnaud Jacquin ) a prezentat o metodă de codificare fractală, care utilizează sisteme de blocuri de imagini de domeniu și rang ( în engleză domain and range subimage blocks ), blocuri de formă pătrată care acoperă întreaga imagine. Această abordare a devenit baza pentru majoritatea metodelor de codificare fractală. Acesta a fost îmbunătățit de Yuval Fisher și de o serie de alți cercetători.
În conformitate cu această metodă, imaginea este împărțită într-un set de subimagini de rang care nu se suprapun ( de exemplu, subimagini de interval ) și este determinat un set de subimagini de domeniu suprapuse (de exemplu , subimagini de domeniu ). Pentru fiecare bloc de rang, algoritmul de codificare găsește cel mai potrivit bloc de domeniu și o transformare afină care mapează acest bloc de domeniu la blocul de rang dat. Structura imaginii este mapată într-un sistem de blocuri de rang, blocuri de domenii și transformări.
Ideea este următoarea: să presupunem că imaginea originală este un punct fix al unei mapări de contracție. Apoi, în locul imaginii în sine, această mapare poate fi amintită într-un fel și pentru a o restabili, este suficient să aplicați în mod repetat această mapare oricărei imagini de pornire.
După teorema lui Banach, astfel de iterații conduc întotdeauna la un punct fix, adică la imaginea originală. În practică, dificultatea constă în găsirea celei mai potrivite mape de compresie din imagine și în stocarea sa compactă. De obicei, algoritmii de căutare de cartografiere (adică algoritmii de compresie) sunt puternic de forță brută și costisitoare din punct de vedere computațional. În același timp, algoritmii de recuperare sunt destul de eficienți și rapidi.
Pe scurt, metoda propusă de Barnsley poate fi descrisă după cum urmează. Imaginea este codificată prin mai multe transformări simple (în cazul nostru, afină), adică este determinată de coeficienții acestor transformări (în cazul nostru, A, B, C, D, E, F).
De exemplu, imaginea curbei Koch poate fi codificată cu patru transformări afine, definind-o în mod unic folosind doar 24 de coeficienți.
Apoi, punând un punct negru în orice punct al imaginii, aplicăm transformările în ordine aleatorie de câteva (destul de mare) de ori (această metodă se mai numește și ping-pong fractal).
Ca rezultat, punctul va merge neapărat undeva în interiorul zonei negre de pe imaginea originală. După aplicarea unei astfel de operații de mai multe ori, tot spațiul negru va fi umplut, ceea ce va restabili imaginea.
Principala dificultate a compresiei fractale este că este necesară o căutare exhaustivă pentru a găsi blocurile de domenii corespunzătoare. Deoarece două matrice trebuie comparate de fiecare dată, această operație se dovedește a fi destul de lungă. Printr-o transformare relativ simplă, se poate reduce la operarea produsului scalar a două matrice, dar chiar și calcularea produsului scalar necesită un timp destul de lung.
Pentru moment[ când? ] se cunosc un număr suficient de mare de algoritmi pentru optimizarea enumerarii care apare în timpul compresiei fractale, deoarece majoritatea articolelor care au studiat algoritmul au fost consacrate acestei probleme și în timpul cercetării active (1992–1996) au fost publicate până la 300 de articole pe an. . Două domenii de cercetare s-au dovedit a fi cele mai eficiente: metoda de extracție a caracteristicilor și metoda clasificării domeniilor.
Michael Barnsley și alții au primit mai multe brevete privind compresia fractală în SUA și în alte țări. De exemplu, 4.941.193 , 5.065.447 , 5.384.867 , 5.416.856 și 5.430.812 . Aceste brevete acoperă o gamă largă de posibile modificări ale compresiei fractale și împiedică serios dezvoltarea acesteia.
Aceste brevete nu limitează cercetarea în acest domeniu, adică vă puteți inventa proprii algoritmi pe baza celor patentați și îi puteți publica. De asemenea, puteți vinde algoritmi în țări care nu sunt acoperite de brevete. În plus, majoritatea brevetelor sunt valabile timp de 17 ani de la data adoptării și expiră pentru majoritatea brevetelor după 2020, astfel că utilizarea metodelor acoperite de aceste brevete va fi garantată a fi gratuită.
| Metode de compresie | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Fara pierderi |
| ||||||
| Audio |
| ||||||
| Imagini |
| ||||||
| Video |
| ||||||