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 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

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

Het volgende voorbeeld toont dit aan:

We werken met een binaire. Stel dat de kansen voor de ingangswaarde de volgende zijn: $P(0)=0{,}3$ $P(1)=0{,}7$ De nulde-orde-entropie wordt dan gegeven door: $H(S)=-0{,}3\cdot \lg _{2}(0{,}3)-0{,}7\cdot \lg _{2}(0{,}7)=0{,}88$. Stel nu dat voor dit experiment geldt dat als de vorige gebeurtenis $0$ was, de kans op een huidige gebeurtenis $0$ gelijk is aan $0{,}8$ en dat als de vorige gebeurtenis $1$ was, de waarschijnlijk op een huidige $1$ gelijk is aan $0{,}1$. De vorige gebeurtenis wordt dan beschouwd als context en kan waarden $0$ en $1$ aannemen. De input kan nu opgedeeld worden in twee sets die overeenkomen met respectievelijk context $0$ en context $1$. De entropie voor elk van die sets wordt gegeven door: $H(S_{1})=-0{,}8\cdot \lg _{2}(0{,}8)-0{,}2\cdot \lg _{2}(0{,}2)=0{,}72$ $H(S_{2})=-0{,}1\cdot \lg _{2}(0{,}1)-0{,}9\cdot \lg _{2}(0{,}9)=0{,}47$ Dit leidt tot een gemiddelde bitrate van $0{,}3\cdot 0{,}72+0{,}7\cdot 0{,}47=0{,}55$, wat beduidend minder is dan de nulde-orde-entropie.

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 $a,b,c$ en $d$ eerste gescand worden, voor $x$ dus. Men spreekt in dit verband ook weleens van een causale context.

Voorspelling

In deze stap wordt de waarde van de volgende sample $x'$ 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

${\hat {a}}'=\left\{{\begin{matrix}\min(a,b)&c\geq \max(a,b)\\\max(a,b)&c\leq \min(a,b)\\a+b-c&\mathrm {anders} \end{matrix}}\right.$

Door deze predictor worden verticale en horizontale kleurovergangen gedetecteerd. Wanneer er links naast de huidige pixel een verticale overgang is, dan wordt de output $a$. Is er een horizontale rand boven de huidige pixel, dan wordt de output $b$. Werd er geen duidelijke overgang gedetecteerd, dan wordt er $a+b-c$ 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 $Q=(q_{1},q_{2},q_{3})$ met

• $q_{1}=d-b$

• $q_{2}=b-c$

• $q_{3}=c-a$

$q_{1},$ $q_{2}$ en $q_{3}$ stellen de lokale overgangen (verschillen) of gelijkenissen voor.

Omdat $q_{1},$ $q_{2}$ en $q_{3}$ 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 $q_{1},$ $q_{2}$ en $q_{3}$ kunnen voorstellen met een beperkt aantal waarden. Bij JPEG-LS wordt er gewerkt met de grenzen $-T,...,-1,0,1,...T$ met $T=4$. Bijkomend worden alle contextvectoren $Q$ waarvan het eerste element een negatief getal is, vervangen door $-Q$. Zo kunnen er maximaal ${\frac {(2\cdot T+1)^{3}+1}{2}}=365$ contexten voorkomen. De contextvector $Q$ kan zo gemapt worden naar een integer uit het interval ${\begin{bmatrix}0,&364\end{bmatrix}}$.

Residu-codering

Voor eender welke afbeelding zal het residu van de voorspelling een eindig getal $\alpha$ zijn. Voor een gegeven voorspelling ${\hat {x}}$ geldt dus voor het residu $\epsilon$: $-x\leq \epsilon \leq \alpha -x$. Dit zorgt ervoor dat het residu $\epsilon$ door modulo $\alpha$ te rekenen gemapt kan worden tot een waarde die ligt tussen $-\left\lfloor {\frac {\alpha }{2}}\right\rfloor$ en $\left\lceil {\frac {\alpha }{2}}\right\rceil -1$. 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

JPEG-LS voorziet ook een bijna-lossless mode waarin de gereconstrueerde samples een maximale afwijking $\delta$ hebben ten opzichte van het originele beeld. De lossless mode kan eigenlijk beschouwd worden als een speciaal geval van bijna-lossless waarbij $\delta =0$. Bij bijna-lossless compressie worden de residues gekwantiseerd door intervallen met lengte $2\cdot \delta +1$. De gekwantiseerde waarden van $\epsilon$ worden dan gegeven door $Q(\epsilon )=\operatorname {sign} (\epsilon )\left\lfloor {\frac {|\epsilon |+\delta }{2\cdot \delta +1}}\right\rfloor$. Aangezien $\delta$ 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

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

Bronnen, noten en/of referenties

• Li Z, Drew M.S. (2004) Fundamentals of Multimedia (International Edition), Prenice Hall - Pearson Education International.

Bestandsformaten voor compressie van multimedia