Fraktal billedkomprimering er en tabsgivende billedkomprimeringsalgoritme baseret på anvendelse af systemer med itererede funktioner (normalt affine transformationer ) på billeder. Denne algoritme er kendt for, at den i nogle tilfælde gør det muligt at opnå meget høje kompressionsforhold med acceptabel visuel kvalitet for rigtige fotografier af naturlige objekter. På grund af den vanskelige situation med patentering blev algoritmen ikke udbredt.
Grundlaget for fraktalkodningsmetoden er påvisningen af selv-lignende områder i et billede. For første gang blev muligheden for at anvende teorien om systemer med itererede funktioner ( English Iterated Function System, IFS ) på problemet med billedkomprimering undersøgt af Michael Barnsley ( engelsk Michael Barnsley [1] ) og Alan Sloan ( engelsk Alan Sloan ). ). De patenterede deres idé i 1990 og 1991 ( US Patent 5.065.447 ). A. Jaquin ( fr. Arnaud Jacquin ) præsenterede en metode til fraktal kodning, som bruger systemer med domæne- og rangbilledblokke ( engelsk domæne- og rækkeunderbilledeblokke ), firkantede blokke, der dækker hele billedet. Denne tilgang blev grundlaget for de fleste fraktale kodningsmetoder. Det er blevet forbedret af Yuval Fisher og en række andre forskere.
I overensstemmelse med denne fremgangsmåde opdeles billedet i et sæt ikke-overlappende rang-underbilleder ( eng. range subimages ), og et sæt af overlappende domæne-subimages ( eng. domain subimages ) bestemmes. For hver rangblok finder kodningsalgoritmen den bedst egnede domæneblok og en affin transformation, der mapper denne domæneblok til den givne rangblok. Billedets struktur er kortlagt i et system af rangblokke, domæneblokke og transformationer.
Ideen er som følger: antag, at det originale billede er et fast punkt i en sammentrækningskortlægning. Så, i stedet for selve billedet, kan denne mapping huskes på en eller anden måde, og for at gendanne den er det nok at gentagne gange anvende denne mapping på ethvert startbillede.
Ifølge Banachs sætning fører sådanne iterationer altid til et fast punkt, det vil sige til det originale billede. I praksis ligger vanskeligheden i at finde den bedst egnede komprimeringsmapping fra billedet og i dets kompakte lagring. Typisk er kortlægningssøgealgoritmer (dvs. kompressionsalgoritmer) stærkt brute-force og beregningsmæssigt dyre. Samtidig er gendannelsesalgoritmer ret effektive og hurtige.
Kort fortalt kan metoden foreslået af Barnsley beskrives som følger. Billedet er kodet af flere simple transformationer (i vores tilfælde affin), det vil sige, det bestemmes af koefficienterne for disse transformationer (i vores tilfælde A, B, C, D, E, F).
For eksempel kan billedet af Koch-kurven kodes med fire affine transformationer, der unikt definerer det ved hjælp af kun 24 koefficienter.
Ved at sætte en sort prik på et hvilket som helst tidspunkt i billedet anvender vi derefter transformationerne i tilfældig rækkefølge nogle (stort nok) antal gange (denne metode kaldes også fraktal ping-pong).
Som et resultat vil punktet nødvendigvis gå et sted inden for det sorte område på det originale billede. Efter at have anvendt en sådan operation mange gange, vil hele det sorte rum blive fyldt, hvilket vil genoprette billedet.
Den største vanskelighed ved fraktal komprimering er, at der kræves en udtømmende søgning for at finde de tilsvarende domæneblokke. Da to arrays skal sammenlignes hver gang, viser denne operation sig at være ret lang. Ved en relativt simpel transformation kan det reduceres til driften af skalarproduktet af to arrays, men selv beregning af skalarproduktet kræver ret lang tid.
I øjeblikket[ hvornår? ] et tilstrækkeligt stort antal algoritmer til at optimere opregningen, der sker under fraktal kompression, er kendt, da de fleste af de artikler, der studerede algoritmen, var viet til dette problem, og under aktiv forskning (1992-1996) blev der publiceret op til 300 artikler om året . To forskningsområder viste sig at være de mest effektive: feature-ekstraktionsmetoden og klassificering af domæner-metoden.
Michael Barnsley og andre har modtaget adskillige patenter på fraktal kompression i USA og andre lande. For eksempel 4.941.193 , 5.065.447 , 5.384.867 , 5.416.856 og 5.430.812 . Disse patenter dækker en bred vifte af mulige modifikationer af fraktal kompression og hæmmer dens udvikling alvorligt.
Disse patenter begrænser ikke forskningen på dette område, det vil sige, at du kan opfinde dine egne algoritmer baseret på patenterede og udgive dem. Du kan også sælge algoritmer til lande, der ikke er omfattet af patenter. Derudover er de fleste patenter gyldige i 17 år fra vedtagelsesdatoen, og udløber for de fleste patenter efter 2020, så brugen af metoderne omfattet af disse patenter vil med garanti være gratis.
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Tabsfri |
| ||||||
| Lyd |
| ||||||
| Billeder |
| ||||||
| Video |
| ||||||