Hoe werkt Wavelet en Fractal compressie

De jpeg-techniek kan bestanden weliswaar makkelijk twintig keer zo klein maken, het nadeel van deze methode is dat afbeeldingen daardoor zichtbaar in kwaliteit verliezen. Voortbordurend op de jpeg-techniek zijn daarom exotische methodes ontwikkeld. In het derde deel van de serie over datacompressie komen twee van deze technieken, wavelets en fractals, aan bod.

Het verhaal achter deze technieken begon lang geleden, toen de wereld van de wiskunde, die lange tijd netjes geordend had geleken, in 1807 volledig op zijn kop werd gezet door Joseph Fourier. Deze wetenschapper ontdekte dat de klassieke families van wiskundige functies, zoals exponenten, trigonometrie, enzovoort, niet echt onafhankelijk van elkaar waren. Fourier toonde aan dat repeterende functies kunnen worden beschreven door de som van harmonisch aan elkaar gerelateerde sinus- en cosinusfuncties. Niet herhalende functies konden ook op deze manier worden beschreven, zei het door deze op te delen in vensters, er daarbij vanuit gaande dat ieder venster wordt omringd door vele vrijwel identieke vensters.

Venster

De Fourier-analyse van functies wordt onder andere gebruikt voor de jpeg-compressie. Het venster heeft, zoals te lezen valt in het tweede deel van deze serie, bij jpeg een grootte van 8 bij 8 pixels en wordt geanalyseerd door 64 cosinusfuncties. Deze analyse is bij jpeg de transformatie die de grijswaarden van de lichte partijen op een vaste plek in het venster bij elkaar zet en de grijswaarden van de donkere partijen. Fourier realiseerde zich dat het werken met vensters fouten introduceert: de vensters zijn eindig, terwijl cosinusfuncties tot in het oneindige doorgaan. Dit leidt tot afwijkingen ten opzichte van het origineel, die voornamelijk zichtbaar worden aan de randen van de vensters. Wiskundigen zochten daarom naar elegantere functies, die buiten een bepaalde zone bijna nul zijn en daarmee de fout aan de rand van het venster reduceren tot bijna nul. De functiefamilies die dit kunnen, worden aangeduid met de verzamelnaam wavelets.

Wavelet

Er zijn in principe vele wavelet-functies waarmee afbeeldingen kunnen worden gecomprimeerd. Slechts een beperkt aantal levert echter goede resultaten op en kost niet al te veel rekenkracht. Het vinden van deze wavelets is behoorlijk ingewikkeld, maar welke functie ook wordt gebruikt, het compressiealgoritme blijft gelijk. De analyse van een afbeelding start met de keuze voor een specifieke wavelet-functie. Daarna wordt de schaal van deze functie zo ingesteld, dat de gekozen wavelet het gehele beeld bedekt. Dit wordt ook wel de moederwavelet genoemd. Net als bij jpeg-compressie wordt de beeldinformatie in vensters met rijen en kolommen opgedeeld en vervolgens getransformeerd, alleen nu op basis van de wavelet. Het resultaat hiervan bestaat uit een deel van de afbeelding dat vrij accuraat wordt gerepresenteerd door de wavelet en het resterend deel met de details. Het accurate deel is een getal dat wordt bewaard in het uiteindelijke gecomprimeerde bestand.

wavelet_fractal_01
Afbeelding 1
Details

De tweede stap (iteratie) bestaat uit de analyse van de details. Hiervoor wordt een wavelet gebruikt met dezelfde vorm als de moederwavelet, maar slechts half zo groot. Deze babywavelet bedekt dus slechts een kwart van de afbeelding. Net als bij de eerste stap wordt de afbeelding weer getransformeerd, alleen nu in vier kleinere delen, die elk eveneens een accuraat deel hebben en een resterend deel met de details. De details van de rijen uit de vensters komen in het kwadrant linksonder te staan (DY-01), de kolommen rechtsboven (DX-01) en de diagonale delen rechtsonder (DXY-01). Het accurate deel linksboven wordt wederom als getal opgeslagen in het gecomprimeerde bestand. De drie resterende kwadranten (details) worden in de derde iteratie opnieuw getransformeerd, met een babywavelet die weer half zo groot is als de eerste babywavelet, resulterend in vier nog kleinere kwadranten, enzovoort.

wavelet_fractal_02
Afbeelding 2
Lossless

Dit algoritme kan net zo lang doorgaan totdat er niets meer valt te analyseren. De wavelet-compressie is dan lossless, en de mate van compressie is dan iets hoger dan de in het eerste deel van deze serie behandelde LZW-methode. De meeste wavelet-toepassingen houden al veel eerder op met analyseren, om informatie op te offeren aan de in sommige gevallen zeer hoge compressiegraad. Het uitpakken van de afbeelding start met het renderen van de moederwavelet op basis van het eerste getal van de analyse. Daarna wordt de afbeelding steeds verder verfijnd met de babywavelets en bijbehorende getal.

Fractals

Sommige wavelets hebben een vorm die zichzelf op kleiner niveau herhaalt. Functies met deze eigenschap worden fractals genoemd, een door wiskundigen als Mandelbrot en Lorenz veelvuldig beschreven verschijnsel. Deze specifieke, relatief eenvoudige functies bleken na honderden of duizenden iteraties prachtige, zichzelf oneindig herhalende figuren op te leveren. Het mooie aan deze fractals is dat de afbeelding die ze genereren in principe oneindig detail (resolutie) bezit: op iedere plek van de afbeelding kan worden ingezoomd, waarna met hetzelfde detail weer vergelijkbare patronen ontstaan, enzovoort. Een afbeelding met een resolutie van duizenden pixels per inch met een formaat van een gevel, en dus vele terrabytes groot, is daardoor te reduceren tot de grootte van de formule waarmee deze wordt berekend. Tot enkele bytes dus. Enig nadeel is dat er een supercomputer nodig is om de afbeelding binnen acceptabele tijd te berekenen…

wavelet_fractal_03
Afbeelding 3
Transformatie

Een eenvoudiger voorbeeld dan de kleurrijke Julia-fractal laat de werking van fractals zien. Stel een kopieerapparaat voor dat van ieder origineel drie verkleinde kopieën van gelijke grootte maakt. Het resultaat van deze kopie (de transformatie) wordt vervolgens gebruikt als input voor de volgende kopie, enzovoort. Of het kopiëren nu start met de letter ‘O’ of ‘A’, al na drie transformaties beginnen de kopieën sterk op elkaar te lijken. Wanneer het origineel een driehoek zou zijn geweest, ontstaat na drie transformaties een zichzelf eeuwig herhalend figuur, dat lijkt op de figuren die uit de ‘O’ en ‘A’ worden opgebouwd. Deze wiskundige ‘varen’ heeft detail op elk niveau, hoe sterk we ook inzoomen. Dit is het principe van de fractal: zijn vorm en positie van het uitgangspunt bekend, dan kan de rest van het beeld worden opgebouwd door herhaald te transformeren.

wavelet_fractal_04
Afbeelding 4
Opblazen

Deze specifieke afbeeldingen kunnen heel sterk worden gereduceerd zonder verlies aan informatie, iets dat we met bestanden ook zouden willen doen. Helaas bestaat de werkelijkheid uit afbeeldingen waarvan de zichzelf herhalende patronen een stuk lastiger zijn te vinden. Het zoeken van de juiste serie functies om een afbeelding te omschrijven, is net als bij de wavelet-compressie feitelijk het lastigste karwei. Het principe wijkt niet veel af van de wavelet-compressie: het beeld wordt geanalyseerd met behulp van functies, waarbij zo veel mogelijk wordt gelet op zichzelf herhalende patronen. Fractal-compressie gold lange tijd als veelbelovend, maar wavelet-compressie levert over het algemeen toch betere resultaten op. De bedrijven die compressiesoftware ontwikkelen, gebruiken daarom wavelets vaak om afbeeldingen stevig te comprimeren en fractals om een afbeelding ver boven de oorspronkelijke resolutie op te blazen. Het zichzelf herhalend karakter van fractals is hiervoor zeer geschikt, omdat bij het opblazen van beelden de verhoudingen immers gelijk blijven. Dit kan worden beschouwd als het zichzelf herhalen van beeld, alleen dan op een andere schaal.

Scroll Up

Pin It on Pinterest