JPEG LS

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

JPEG-LS is de huidige ISO/ITU-standaard voor lossless (zonder kwaliteitsverlies) of bijna-lossless compressie en maakt deel uit van een uitgebreidere ISO-standaard voor het beter comprimeren van medische beelden.

Intro[bewerken]

Lossless (verliesvrije) compressie is van zeer groot belang bij afbeeldingen die kritische informatie bevatten. Dat kan het geval zijn bij beelden uit de medische wereld of bij afbeeldingen die moeilijk en duur zijn om te produceren. Eerdere lossless compressiemethodes zoals GIF en PNG zijn enkel efficiënt bij het comprimeren van afbeeldingen die slechts een beperkte hoeveelheid kleuren bevatten. JPEG-LS maakt het mogelijk om ook afbeeldingen met meerdere kleuren verliesvrij te comprimeren. Ook de nieuwe JPEG 2000-standaard voorziet een lossless mode. Het algoritme dat daarbij gebruikt wordt is echter veel complexer dan het JPEG-LS-algoritme.

Lossless: LOCO-I[bewerken]

Het kernalgoritme van JPEG-LS draagt de naam LOw COmplexity LOssless COmpression for Images (LOCO-I) en werd ontwikkeld door Hewlett-Packard. Het achterliggende idee van LOCO-I is dat het vereenvoudigen van een algoritme vaak tot betere resultaten leidt dan uitbreiding van het algoritme. Een uitbreiding maakt het algoritme immers meer complex en zorgt vaak voor slechts een kleine compressietoename.

Context modeling[bewerken]

LOCO-I maakt gebruik van een concept dat context modeling wordt genoemd. Tijdens het compressieproces wordt immers berekend wat de voorwaardelijke kans is dat een bepaalde pixel zal volgen op een andere pixel in de afbeelding. Deze extra informatie wordt de context genoemd en zal mee als input worden gebruikt voor de compressie. Zo wordt het mogelijk om een compressie uit te voeren die minder bits nodig heeft dan een entropie van de 0-de orde.

We werken met een binaire. Stel dat de kansen voor de ingangswaarde de volgende zijn:

De 0-de orde entropie wordt dan gegeven door:

.

Stel nu dat voor dit experiment geldt dat als de vorige gebeurtenis was, de kans op een huidige gebeurtenis gelijk is aan en dat als de vorige gebeurtenis was, de waarschijnlijk op een huidige gelijk is aan . De vorige gebeurtenis wordt dan beschouwd als context en kan waarden en aannemen.

De input kan nu opgedeeld worden in twee sets die overeenkomen met respectievelijk context en context . De entropie voor elk van die sets wordt gegeven door:

Dit leidt tot een gemiddelde bitrate van , wat beduidend minder is dan de 0-de orde entropie.

Het volgende voorbeeld toont dit aan:

LOCO-I maakt gebruik van een contextmodel dat wordt weergegeven door het volgende patroon:

c a d
b x ...

Bij het scannen van het raster zullen de contextpixels en eerste gescand worden, voor dus. Men spreekt in dit verband ook weleens van een causale context.

Voorspelling[bewerken]

In deze stap wordt de waarde van de volgende sample voorspeld. Dit gebeurt door het uitvoeren van een primitieve test die steeds dezelfde is. Het zo eenvoudig mogelijk houden van deze test is een van de sleutels voor het eenvoudige compressie algoritme van LOCO-I. De test wordt gegeven door


Door deze predictor worden verticale en horizontale kleurovergangen gedetecteerd. Wanneer er links naast de huidige pixel een verticale overgang is, dan wordt de output . Is er een horizontale rand boven de huidige pixel, dan wordt de output . Werd er geen duidelijke overgang gedetecteerd, dan wordt er teruggegeven.

Contextbepaling[bewerken]

Aangezien het slechts om een voorspelling gaat, zal er steeds sprake zijn van een mogelijke fout. Deze wordt de voorspellingsfout of residu genoemd. Het context model dat dit residu bepaalt wordt aangeduid door de contextvector met

en stellen de lokale overgangen (verschillen) of gelijkenissen voor.

Omdat en een groot aantal verschillende waarden kunnen aannemen, is het onderliggende context model enorm uitgebreid. Daarom maakt men gebruik van methodes die het aantal parameters verminderen, zoals kwantisatie. Dit zorgt ervoor dat we en kunnen voorstellen met een beperkt aantal waarden. Bij JPEG-LS wordt er gewerkt met de grenzen met . Bijkomend worden alle contextvectoren waarvan het eerste element een negatief getal is, vervangen door . Zo kunnen er maximaal contexten voorkomen. De contextvector kan zo gemapt worden naar een integer uit het interval .

Residu codering[bewerken]

Voor eender welke afbeelding zal het residu van de voorspelling een eindig getal zijn. Voor een gegeven voorspelling geldt dus voor het residu : . Dit zorgt ervoor dat het residu door modulo te rekenen gemapt kan worden tot een waarde die ligt tussen en . Er kan dan aangetoond worden dat het residu tweezijdig geometrisch verdeeld is. Ten slotte wordt het residu dan gecodeerd met behulp van Golomb codes, die ideaal zijn voor het coderen van twijzijdige geometrische verdelingen.

Bijna-lossless mode[bewerken]

JPEG-LS voorziet ook een bijna-lossless mode waarin de gereconstrueerde samples een maximale afwijking hebben ten opzichte van het originele beeld. De lossless mode kan eigenlijk beschouwd worden als een speciaal geval van bijna-lossless waarbij . Bij bijna-lossless compressie worden de residues gekwantiseerd door intervallen met lengte . De gekwantiseerde waarden van worden dan gegeven door . Aangezien slechts een beperkt aantal integerwaarden kan aannemen, kan er gewerkt worden met lookup tables. Bij bijna-lossles compressie wordt de voorspelling en de contextbepaling die hierboven worden beschreven volledig uitgevoerd op basis van de gekwantiseerde waarden.

Externe links[bewerken]