Fraktal kompression

2 trianglar, exempel för att visa hur fraktal komprimering fungerar

Fraktalkomprimering är en förlustkompressionsmetod för digitala bilder , baserad på fraktaler . Metoden lämpar sig bäst för texturer och naturliga bilder, beroende på att delar av en bild ofta liknar andra delar av samma bild. Fraktalalgoritmer " fraktalkoder" som används för att återskapa den kodade bilden.

Itererade funktionssystem

Fraktal bildrepresentation kan beskrivas matematiskt som ett itererat funktionssystem (IFS).

För binära bilder

Vi börjar med representationen av en binär bild , där bilden kan ses som en delmängd av $\mathbb {R} ^{2}$ . En IFS är en uppsättning sammandragningsmappningar ƒ ₁ ,..., ƒ _N ,

f_{i}:\mathbb {R} ^{2}\to \mathbb {R} ^{2}.

Enligt dessa mappningsfunktioner beskriver IFS en tvådimensionell uppsättning S som den fasta punkten för Hutchinson-operatören

H(A)=\bigcup _{i=1}^{N}f_{i}(A),\quad A\subset \mathbb {R} ^{2}.

₀ Det vill säga, H är en operatör som mappar uppsättningar till uppsättningar, och S är den unika uppsättningen som uppfyller H ( S ) = S. Tanken är att konstruera IFS så att denna uppsättning S är den ingående binära bilden. Uppsättningen S kan återställas från IFS genom _{fixpunktsiteration +1} : Ak _för varje icke-tom, kompakt initialuppsättning A , konvergerar iterationen Ak = H ( ) till S.

Mängden S är sig självlik eftersom H ( S ) = S antyder att S är en förening av mappade kopior av sig själv:

S=f_{1}(S)\cup f_{2}(S)\cup \cdots \cup f_{ N}(S)

Så vi ser att IFS är en fraktal representation av S .

Förlängning till gråskala

IFS-representation kan utökas till en gråskalebild genom att betrakta bildens graf som en delmängd av $\mathbb {R} ^{3}$ . För en gråskalebild u ( x , y ), betrakta mängden S = {( x , y , u ( x , y ))}. Sedan, liknande det binära fallet, S av en IFS som använder en uppsättning sammandragningsmappningar ƒ ₁ ,..., ƒ _N , men i $\mathbb {R} ^{3}$ ,

f_{i}:\mathbb {R} ^{3}\to \mathbb {R} ^{3}.

Kodning

Ett utmanande problem med pågående forskning inom fraktal bildrepresentation är hur man väljer ƒ ₁ ,..., ƒ _N så att dess fixpunkt approximerar ingångsbilden, och hur man gör detta effektivt.

En enkel metod för att göra det är följande partitionerade itererade funktionssystem (PIFS):

Dela upp bilddomänen i intervallblock R _i med storleken s × s .
Sök i bilden för varje R _{i för att hitta ett block} D _i med storleken 2 s × 2 s som är mycket likt R _i .
Välj mappningsfunktionerna så att H ( D _i ) = R _i för varje i .

I det andra steget är det viktigt att hitta ett liknande block så att IFS exakt representerar ingångsbilden, så ett tillräckligt antal kandidatblock för D _i måste övervägas. Å andra sidan är en stor sökning med tanke på många block beräkningsmässigt kostsam. Denna flaskhals med att söka efter liknande block är anledningen till att PIFS fraktalkodning är mycket långsammare än till exempel DCT och waveletbaserad bildrepresentation.

Den initiala fyrkantiga partitioneringen och brute-force sökalgoritmen som presenteras av Jacquin ger en utgångspunkt för ytterligare forskning och förlängningar i många möjliga riktningar - olika sätt att dela upp bilden i områdesblock av olika storlekar och former; snabba tekniker för att snabbt hitta ett tillräckligt nära matchande domänblock för varje områdesblock snarare än brute-force-sökning, såsom fast motion-uppskattningsalgoritmer ; olika sätt att koda mappningen från domänblocket till intervallblocket; etc.

Andra forskare försöker hitta algoritmer för att automatiskt koda en godtycklig bild som RIFS (recurrent iterated function systems) eller global IFS, snarare än PIFS; och algoritmer för fraktal videokomprimering inklusive rörelsekompensation och tredimensionella itererade funktionssystem.

Fraktal bildkomprimering har många likheter med vektorkvantiseringsbildkomprimering .

Funktioner

Med fraktal komprimering är kodning extremt beräkningsmässigt dyrt på grund av sökningen som används för att hitta självlikheterna. Avkodningen går dock ganska snabbt. Även om denna asymmetri hittills har gjort det opraktiskt för realtidsapplikationer, blir fraktalkomprimering mer konkurrenskraftig när video arkiveras för distribution från disklagring eller nedladdning av filer.

Vid vanliga komprimeringsförhållanden, upp till cirka 50:1, ger fraktal komprimering liknande resultat som DCT-baserade algoritmer som JPEG . Vid höga kompressionsförhållanden kan fraktalkomprimering erbjuda överlägsen kvalitet. För satellitbilder har förhållanden på över 170:1 uppnåtts med acceptabla resultat. Fraktalvideokomprimeringsförhållanden på 25:1–244:1 har uppnåtts inom rimliga komprimeringstider (2,4 till 66 sek/bildruta).

Kompressionseffektiviteten ökar med högre bildkomplexitet och färgdjup, jämfört med enkla gråskalebilder .

Upplösningsoberoende och fraktal skalning

En inneboende egenskap hos fraktalkomprimering är att bilder blir upplösningsoberoende efter att ha konverterats till fraktalkod. Detta beror på att de itererade funktionssystemen i den komprimerade filen skala på obestämd tid. Denna obestämda skalningsegenskap hos en fraktal är känd som "fraktalskalning".

Fraktal interpolation

Upplösningsoberoendet för en fraktalkodad bild kan användas för att öka visningsupplösningen för en bild. Denna process är också känd som "fraktal interpolation". Vid fraktal interpolation kodas en bild till fraktalkoder via fraktalkomprimering och dekomprimeras därefter i en högre upplösning. Resultatet är en uppsamplad bild där itererade funktionssystem har använts som interpolant . Fraktal interpolation upprätthåller geometriska detaljer mycket väl jämfört med traditionella interpolationsmetoder som bilinjär interpolation och bikubisk interpolation . Eftersom interpolationen inte kan vända Shannon-entropin, slutar den med att bilden skärper genom att lägga till slumpmässiga i stället för meningsfulla detaljer. Man kan till exempel inte förstora en bild av en folkmassa där varje persons ansikte är en eller två pixlar och hoppas kunna identifiera dem.

Historia

Michael Barnsley ledde utvecklingen av fraktalkompression 1987 och beviljades flera patent på tekniken. Den mest kända praktiska fraktalkomprimeringsalgoritmen uppfanns av Barnsley och Alan Sloan. Barnsleys doktorand Arnaud Jacquin implementerade den första automatiska algoritmen i mjukvara 1992. Alla metoder är baserade på fraktaltransformationen med itererade funktionssystem . Michael Barnsley och Alan Sloan bildade Iterated Systems Inc. 1987 som beviljades över 20 ytterligare patent relaterade till fraktal komprimering.

Ett stort genombrott för Iterated Systems Inc. var den automatiska fraktaltransformationsprocessen som eliminerade behovet av mänskligt ingripande under komprimering som var fallet i tidiga experiment med fraktalkompressionsteknologi. 1992 fick Iterated Systems Inc. ett statligt anslag på 2,1 miljoner USD för att utveckla en prototyp för digital bildlagring och dekompressionschip med hjälp av fraktaltransformeringsteknik för bildkomprimering.

Fractal bildkomprimering har använts i ett antal kommersiella tillämpningar: onOne Software, utvecklad under licens från Iterated Systems Inc., Genuine Fractals 5 som är ett Photoshop -plugin som kan spara filer i komprimerad FIF (Fractal Image Format). Hittills är den mest framgångsrika användningen av stillbildsfraktal bildkomprimering av Microsoft i dess Encarta multimediauppslagsverk, också under licens.

Iterated Systems Inc. levererade en shareware-kodare (Fractal Imager), en fristående avkodare, en Netscape-plugin-avkodare och ett utvecklingspaket för användning under Windows. Eftersom wavelet-baserade metoder för bildkomprimering förbättrades och lättare licensierades av kommersiella programvaruleverantörer misslyckades antagandet av Fractal Image Format att utvecklas. ^{[ citat behövs ]} Omfördelningen av "dekomprimerings-DLL" som tillhandahålls av ColorBox III SDK styrdes av restriktiva per-disk- eller år för år-licensieringsregimer för proprietära mjukvaruleverantörer och av ett diskretionärt system som innebar främjandet av Iterated Systems produkter för vissa klasser av andra användare.

Under 1990-talet använde Iterated Systems Inc. och dess partners avsevärda resurser för att få fraktalkomprimering till video. Även om komprimeringsresultaten var lovande, saknade dåtidens datorhårdvara processorkraften för fraktal videokomprimering för att vara praktisk utöver ett fåtal utvalda användningsområden. Upp till 15 timmar krävdes för att komprimera en enda minuts video.

ClearVideo – även känd som RealVideo (Fractal) – och SoftVideo var tidiga fraktala videokomprimeringsprodukter. ClearFusion var Iterateds fritt distribuerade plugin för strömmande video för webbläsare. 1994 licensierades SoftVideo till Spectrum Holobyte för användning i dess CD-ROM- spel inklusive Falcon Gold och Star Trek: The Next Generation A Final Unity .

1996 tillkännagav Iterated Systems Inc. en allians med Mitsubishi Corporation för att marknadsföra ClearVideo till sina japanska kunder. Den ursprungliga ClearVideo 1.2-avkodardrivrutinen stöds fortfarande av Microsoft i Windows Media Player även om kodaren inte längre stöds.

Två företag, Total Multimedia Inc. och Dimension, hävdar båda att de äger eller har exklusiv licens till Iterateds videoteknik, men ingen av dem har ännu släppt en fungerande produkt. Den tekniska grunden verkar vara Dimensions amerikanska patent 8639053 och 8351509, som har analyserats avsevärt. Sammanfattningsvis är det ett enkelt quadtree-blockkopieringssystem med varken bandbreddseffektiviteten eller PSNR-kvaliteten hos traditionella DCT-baserade codecs. I januari 2016 meddelade TMMI att de helt och hållet överger fraktalbaserad teknologi.

Forskningsartiklar mellan 1997 och 2007 diskuterade möjliga lösningar för att förbättra fraktala algoritmer och kodningshårdvara.

Genomföranden

Ett bibliotek som heter Fiasco skapades av Ullrich Hafner. 2001 behandlades Fiasco i Linux Journal . Enligt Fiasco- manualen 2000-04 kan Fiasco användas för videokomprimering. Netpbm - biblioteket inkluderar Fiasco -biblioteket.

Femtosoft utvecklade en implementering av fraktal bildkomprimering i Object Pascal och Java .

Se även

Anteckningar

externa länkar

Pulcini och Verrandos kompressor
Keith Howells 1993 M.Sc. avhandling Fractal Image Compression for Spaceborne Transputers
My Main Squeeze: Fractal Compression , nov 1993, Wired.
Fractal Basics beskrivning på FileFormat.Info
Superfractals webbplats ägnas åt fraktaler av uppfinnaren av fraktal komprimering