JPEG LS

bestandsformaat van Joint Photographic Experts Group

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.

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 compressiemethoden zoals GIF en PNG zijn enkel efficiënt bij het comprimeren van afbeeldingen die slechts een beperkt aantal 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 nulde orde.

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

De nulde-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 nulde-orde-entropie.

Het volgende voorbeeld toont dit aan:

LOCO-I maakt gebruik van een context model 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 methoden 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 tweezijdige 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.

bewerken
  • (en) LOCO-I (officiële website)
  • (en) JPEG-LS (officiële website)
  • (en) Compressiesoftware