JPEG LS
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 
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 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 
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 
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.

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

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 
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 
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 
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 
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 
 LOCO-I (Officiële website)
 JPEG-LS (officiële website)
 Compressiesoftware

Compressieformaat
Afbeeldingsformaat