Ezw

EZW (embedded zerotree wavelet) is een compressie-algoritme met verlies van kwaliteit bij het coderen van afbeeldingen. Het EZW-algoritme probeert een zo goed mogelijke kwaliteit van de afbeelding te behouden volgens een bepaalde bitrate en doet dit op een embedded manier. Embedded betekent dat het een bitstream genereert die op elk mogelijk punt afbreekbaar is en zo dus gebruikt kan worden voor progressieve codering.

Bij een embedded code zijn de bits volgens belang geordend in de bitstream. Zo kan de encoder het coderen op ieder moment stopzetten terwijl slechts de minder belangrijkere bits verloren gaan. Het principe van het EZW-algoritme wordt ook gebruikt bij het algoritme Set Partitioning in Hierarchical Trees (SPIHT), dat een uitbreiding is op het EZW-algoritme. Daarnaast is ook het algoritme Embedded Block Coding with Optimized Truncation (EBCOT) op EZW gebaseerd. Het EBCOT-algoritme wordt gebruikt bij de JPEG 2000 standaard. EZW bestaat uit twee centrale componenten met name een zerotree datastructuur en de methode van successive approximation quantization.

Zero tree data structuur

Om het EZW-algoritme toe te kunnen passen op een afbeelding is het noodzakelijk eerst een DWT uit te voeren op die afbeelding. DWT staat voor Discrete wavelet transform en splitst een afbeelding op in vier componenten; namelijk HH, HL, LH, en LL. Op die manier ontstaat een quadtree, waarbij een root-element of parent vier children heeft, terwijl children op hun beurt ook vier children kunnen hebben. De decompositie die kan gemaakt worden aan de hand van een DWT noemt men Mallat-decompositie. Het algemene schema van een Mallat-decompositie ziet er als volgt uit:

LL	HL
LH	HH

Hierbij staat L voor ‘low frequency’, en H voor ‘high frequency’.

Zerotrees zijn quadtrees die de significant map na DWT-transformatie voorstellen. Het idee hierachter is dat, wanneer een bepaalde coëfficiënt insignificant (0) is, de kans groot is dat de coëfficiënten op dezelfde positie in lagere DWT-schalen ook nul zijn. In dat geval kunnen deze nullen eenvoudig worden voorgesteld door een zerotree symbool. De zerotree is eigenlijk een boomstructuur die bestaat uit parent- of rootelementen en children. Hieronder is de parent-childrelatie te zien in een zerotree. Per rootelement zijn er telkens vier children en die children kunnen op hun beurt ook vier children hebben.

Successive Approximation Quantization

Embedded coding bij EZW is mogelijk door het gebruik van een methode die Succesive Approximation Quantization (SAQ) genoemd wordt. Hierbij wordt gebruikgemaakt van de zerotreedatastructuur voor het efficiënt coderen van de significante map. SAQ maakt gebruik van multi-pass scanning van de waveletcoëfficiënten. Hierbij houdt de decoder een lijst van significante coëfficiënten bij. De significante coëfficiënten worden gecodeerd, de MSB’s (most significant of belangrijkste bits) eerst. De multi-pass scanning bestaat uit een dominant pass en een subordinate pass. Ook de scanvolgorde is zeer belangrijk. De pixels van de afbeelding worden niet zomaar willekeurig van links naar rechts gescand om de dominant en subordinate pass uit te voeren; EZW heeft een specifieke scanvolgorde die er als volgt uitziet:

Doordat de afbeelding op deze manier gescand wordt, wordt er nooit een children van een bepaalde parent gescand voordat de parent zelf is gescand. Dit is noodzakelijk aangezien er hier met een embedded algoritme gewerkt wordt die op elk moment afgebroken kan worden. Zo worden de belangrijkste bits, en dus de parents, eerst gescand zodat de belangrijkste informatie voorop in de bitstream verschijnt.

Voorbeeld EZW

Een willekeurige 8x8 wavelet met bijhorende pixelwaarden als input.

Op de afbeelding is de scanvolgorde van de pixels duidelijk te zien en dus kan het EZW-algoritme toegepast worden. Als eerste worden de pixelwaarden omgezet naar binaire waarden. Voor deze pixelwaarden is er maximaal 3 bit nodig, er wordt echter nog gebruikgemaakt van een vierde bit om het teken (plus of min) voor te stellen. Hier wordt positief als 1 bestempeld en negatief als 0. Volgende waarden worden dan verkregen:

Daarna kan de eerste dominant pass toegepast worden op het tweede bit (eerste bit dient niet gescand te worden aangezien dit bit enkel het teken voorstelt.) Bij EZW wordt gebruikgemaakt van vier symbolen die respectievelijk positief significant (POS), negatief significant (NEG), zerotree (ZT) en isolated zero (IZ) voorstellen. Er wordt ook telkens voor zowel dominant als subordinate pass gebruikgemaakt van diezelfde specifieke EZW-scanvolgorde.

Deze tabel stelt het tweede bit van elke pixel voor.

De eerste dominant pass ziet er dan als volgt uit.

D0 = {ZT,IZ,ZT,ZT,IZ,POS,ZT,IZ,ZT,IZ,ZT,IZ,IZ,POS,IZ,IZ,IZ,IZ,IZ,IZ,IZ,POS,IZ,IZ,IZ,POS,IZ}

Er is te zien dat het eerst coëfficiënt een zerotree voorstelt, dit is makkelijk af te leiden uit de tabel met het tweede bit van elke pixel; er is te zien dat de parentwaarde 0 is, als er dan naar de children van deze parent wordt gekeken zijn deze ook 0 en dus vormt dit een zerotree. Na de eerste dominant pass volgt de eerste subordinate pass. Deze gaat na of de waarden die bij de eerste dominant pass positief waren, nog steeds positief zijn in de tabel waarin het derde bit van elke pixel voorgesteld wordt. Dit wordt aangegeven met True of False.

Deze tabel stelt het derde bit van elke pixel voor.

De waarden die bij de eerste dominant pass positief waren, zijn hier in het rood aangeduid ter verduidelijking voor de subordinate pass.

Er worden bij de eerste subordinate pass volgende waarden verkregen:

S0 = {False,False,False,False}

Op het derde bit wordt ook nog een dominante pass toegepast:

D1 = {POS,IZ,NEG,IZ,NEG,IZ,IZ,POS,IZ,IZ,IZ,POS,POS,NEG,POS,POS,IZ,NEG,IZ,NEG,IZ,IZ,POS,IZ,IZ, IZ,POS,POS,NEG,POS,POS,IZ,NEG,IZ,NEG, IZ,IZ,POS,IZ,IZ,IZ,POS,POS,NEG,POS,POS,IZ,NEG, IZ,NEG,IZ,IZ,POS,IZ,IZ,IZ,POS,POS,NEG,POS}

Als laatste stap wordt het vierde en laatste bit behandeld door zowel een subordinate pass als een dominant pass uit te voeren op dit bit.

Deze tabel stelt het vierde bit van elke pixel voor. De waarden die bij de tweede dominant pass positief waren, zijn hier ook in het rood aangeduid ter verduidelijking voor de tweede subordinate pass.

Er worden volgende waarden verkregen:

S1 = {False,True,True,False,False,False,False,False,True,False,True,True,False, False,False,False,False,True,False,True,True,False,False,False,False,False, True,False,True,True,False,False,False,False,False,True}

D2 = {POS,IZ,IZ,IZ,POS,IZ,POS,POS,IZ,IZ,IZ,POS,IZ,POS,POS,IZ,IZ,IZ,POS,IZ,POS, POS,IZ,IZ,IZ,POS,IZ,POS

Uiteindelijk ziet de output van de verschillende dominant en subordinate passes er als volgt uit:

D0 = {ZT,IZ,ZT,ZT,IZ,POS,ZT,IZ,ZT,IZ,ZT,IZ,IZ,POS,IZ,IZ,IZ,IZ,IZ,IZ,IZ,POS,IZ,IZ,IZ,POS,IZ}

S0 = {False,False,False,False}

D1 = {POS,IZ,NEG,IZ,NEG,IZ,IZ,POS,IZ,IZ,IZ,POS,POS,NEG,POS,POS,IZ,NEG,IZ,NEG,IZ,IZ,POS,IZ,IZ,IZ,POS,POS,NEG,POS,POS,IZ,NEG,IZ,NEG,IZ,IZ,POS,IZ,IZ, IZ,POS,POS,NEG,POS,POS,IZ,NEG,IZ,NEG,IZ,IZ,POS,IZ,IZ,IZ,POS,POS,NEG,POS}

S1 = {False,True,True,False,False,False,False,False,True,False,True,True,False,False,False,False,False,True,False,True,True,False,False,False,False, False,True,False,True,True,False,False,False,False,False,True}

D2 = {POS,IZ,IZ,IZ,POS,IZ,POS, POS,IZ,IZ,IZ,POS,IZ,POS, POS,IZ,IZ,IZ,POS,IZ,POS, POS,IZ,IZ,IZ,POS,IZ,POS}

Referenties

Boek: Fundamentals of Multimedia, Pearson Prentice Hall, Ze-Nian Li & Mark S. Drew, 2004.

Zie de categorie EZW van Wikimedia Commons voor mediabestanden over dit onderwerp.