Fraktal bildkomprimering är en bildkomprimeringsalgoritm med förluster som bygger på att tillämpa system med itererade funktioner (vanligtvis affina transformationer ) på bilder. Denna algoritm är känd för det faktum att den i vissa fall gör det möjligt att erhålla mycket höga kompressionsförhållanden med acceptabel visuell kvalitet för riktiga fotografier av naturliga objekt. På grund av den svåra situationen med patentering användes algoritmen inte i stor utsträckning.
Grunden för fraktalkodningsmetoden är upptäckten av självliknande områden i en bild. För första gången undersöktes möjligheten att tillämpa teorin om system för itererade funktioner ( English Iterated Function System, IFS ) på problemet med bildkomprimering av Michael Barnsley ( engelska Michael Barnsley [1] ) och Alan Sloan ( engelska Alan Sloan ). De patenterade sin idé 1990 och 1991 ( US Patent 5 065 447 ). A. Jaquin ( fr. Arnaud Jacquin ) presenterade en metod för fraktalkodning, som använder system av domän- och rankbildblock ( engelska domän- och intervallunderbildsblock ), kvadratiska block som täcker hela bilden. Detta tillvägagångssätt blev grunden för de flesta fraktalkodningsmetoder. Den har förbättrats av Yuval Fisher och ett antal andra forskare.
I enlighet med denna metod delas bilden upp i en uppsättning icke-överlappande rang-underbilder ( eng. range subimages ) och en uppsättning av överlappande domänunderbilder ( eng. domain subimages ) bestäms. För varje rankningsblock hittar kodningsalgoritmen det mest lämpliga domänblocket och en affin transformation som mappar detta domänblock till det givna rankningsblocket. Bildens struktur mappas till ett system av rangblock, domänblock och transformationer.
Tanken är följande: anta att den ursprungliga bilden är en fast punkt i någon sammandragningsmappning. Sedan, istället för själva bilden, kan denna mappning komma ihåg på något sätt, och för att återställa den räcker det att upprepade gånger applicera denna mappning på vilken startbild som helst.
Enligt Banachs teorem leder sådana iterationer alltid till en fast punkt, det vill säga till originalbilden. I praktiken ligger svårigheten i att hitta den mest lämpliga komprimeringsmappningen från bilden och i dess kompakta lagring. Typiskt är kartläggningssökningsalgoritmer (d.v.s. kompressionsalgoritmer) kraftigt brute-force och beräkningsmässigt dyra. Samtidigt är återställningsalgoritmer ganska effektiva och snabba.
I korthet kan metoden som föreslagits av Barnsley beskrivas enligt följande. Bilden kodas av flera enkla transformationer (i vårt fall, affin), det vill säga den bestäms av koefficienterna för dessa transformationer (i vårt fall, A, B, C, D, E, F).
Till exempel kan bilden av Koch-kurvan kodas med fyra affina transformationer, som unikt definierar den med endast 24 koefficienter.
Sedan, genom att sätta en svart prick när som helst i bilden, tillämpar vi transformationerna i slumpmässig ordning några (tillräckligt stort) antal gånger (denna metod kallas också fraktal ping-pong).
Som ett resultat kommer punkten nödvändigtvis att hamna någonstans innanför det svarta området på originalbilden. Efter att ha tillämpat en sådan operation många gånger kommer allt svart utrymme att fyllas, vilket kommer att återställa bilden.
Den största svårigheten med fraktal komprimering är att en uttömmande sökning krävs för att hitta motsvarande domänblock. Eftersom två arrayer måste jämföras varje gång, visar sig denna operation vara ganska lång. Genom en relativt enkel transformation kan den reduceras till driften av den skalära produkten av två arrayer, men även beräkningen av den skalära produkten kräver ganska lång tid.
Just nu[ när? ] ett tillräckligt stort antal algoritmer för att optimera uppräkningen som sker vid fraktal komprimering är kända, eftersom de flesta av de artiklar som studerade algoritmen ägnades åt detta problem och under aktiv forskning (1992–1996) publicerades upp till 300 artiklar per år . Två forskningsområden visade sig vara mest effektiva: funktionsextraktionsmetoden och metoden för klassificering av domäner.
Michael Barnsley och andra har fått flera patent på fraktal kompression i USA och andra länder. Till exempel 4 941 193 , 5 065 447 , 5 384 867 , 5 416 856 och 5 430 812 . Dessa patent täcker ett brett spektrum av möjliga modifieringar av fraktal kompression och hindrar allvarligt dess utveckling.
Dessa patent begränsar inte forskningen inom detta område, det vill säga du kan uppfinna dina egna algoritmer baserade på patenterade och publicera dem. Du kan också sälja algoritmer till länder som inte omfattas av patent. Dessutom är de flesta patent giltiga i 17 år från antagandet och löper ut för de flesta patent efter 2020, så användningen av metoderna som omfattas av dessa patent kommer garanterat att vara gratis.
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Förlust mindre |
| ||||||
| Audio |
| ||||||
| Bilder |
| ||||||
| Video |
| ||||||