[an error occurred while processing this directive]

Notat til sjette forelesning

Andre kodingsmetoder

Det hadde vært fristende og slutte med dette, men jeg har snakket lite om det som er blitt kalt ad-hoc metoder (som man for skams skyld bør kjenne til).

Run-length
koder i par, hvorav det ene elementet er gråtone og det andre er lengde. Finnes i 1D- og 2D-varianter. En 2D-variant er å kode startpunktet for et run i denne linjen relativt til forrige linje. Med dette utnytter vi vertikal korrelasjon i bildet, og oppnår bedre kompresjon. (Mest vanlig for binære data. Brukes for fax sammen med Huffman-koding).
Gray-code
Gray-kode er en metode for å mappe et sett av tall til et binæralfabet, slik at suksessive numeriske endringer fører til endringer bare i ett bit i den binære representasjonen. Da vil to nabopiklser med differanse 1 bare være forskjellige i et bitplan. Figur 6.1. Rabbani. s. 51.

Mange kodingsskjemaer koder bitplanene uavhengig, og da er det nødvendig å øke koheerens for bitene i planet. Gray-koderepresentasjon av bitplanene er en måte å gjøre det på.

Hybride

Differential
istedetfor pikselverdien selv, kodes differansen fra forrige piksleverdi. (kombineres med prediksjon, og da er differansen ikke mellom forrige pikselverdi og denne, men denne og en predikert verdi.)
Prediction
differansen mellom piksleverdien og en predikert verdi som basis for koding. Denne differansen bør ha liten variasjon, mindre statistisk avhengighet for påhverandrefølgende verdier. Verdiene er i gjennomsnitt små, entropien liten, sannsynlighetsfordelingen sterkt toppet (minner om en Laplace-fordeling). Antall piksler brukt i prediksjonen gir prediktorens orden, og har direkte innflytelse på resultatet av prediktoren. Rabbani har valgt å bruke en tredje ordens prediktor i sine forsøk (global = den samme for alle bildene) Xm = 0.75A - 0.5B + 0.75C. Kommer tilbake til prediksjon siden.

Bitplankoding

Jeg har stadig trukket frem en figur som deler komprimering inn i to typer, reversible og irreversibel.

Bilde

Til nå har vi snakket om koding, som kan være et element som utgjør det reversible kodingsskjema. Koding brukes i back end, for både reversible og irreversible metoder. Disse to timene skal vi imidlertid snakke om hva som eksempelvis kan gå forut for koding. Hva slags mapping/prosessering som gjøres med rådataene på forhånd, er for eksempel avhengig av dataenes format. Vi tar utgangspunkt i kapittel 6, 7 og 8 i Rabbani for denne gjennomgangen.

Run-length koding av bitplan

Forming av bitplan

Et bilde med gråtoner fra 0-255 har 8 bitplan. Vi former bitplan ved å velge for eksempel det mest sigifikante bit fra hver pikselverdi for å forme et binært bilde. Ved å gjøre dette for alle 8 bit, kan vi danne 8 bitplan. Motivasjonen for å se på et bilde som flere binære bitplan, er å kunne kode hvert bitplan hver for seg.

Gray-kode

Det er en fordel at bitpaln-kompleksiteteten er så lav som mulig. Kompleksitetet betyr i denne sammenheng antall overganger fra svart til hvitt og vice versa i hvert bitplan. Hvis vi får redusert antall overganger fra svart til hvitt og hvitt til svart i hvert bitplan, får vi redusert kompleksiteten. En vanlig binær representasjon er vanligvis nokså kompleks, fordi binær representasjon av nabogråtoneverdier kan ligge langt fra hverandre (f.eks. 127 og 128 representeres med hhv. 01111111 og 10000000, og vi har her overgang i hvert bitplan.)

Ved å konvertere gråtoneverdiene til Gray-kode, kan vi redusere kompleksiteten. Vi mapper gråtoneverdiene over på en binær representasjon som gir kun en overgang for naboverdier. Det vil si at når differansen på gråtoneverdien er en, vil vi få bare en svart/hvitt overgang i et bitplan. Generelt vil kompleksiteteten (målt som antall overganger) til bitplan l i Gray-kode være lik kompleksitetetn til bitplan l+1 binært representert.

Bilde

Figuren viser Gray-kode 4 bits representasjon for tallene 0 til 15. 0 er vist som som hvitt og 1 som sort. MSB plan er likt for de to representasjonen

Konvertering fra binær til Gray-kode gjøres som følger:

  1. Start med MSB av binærkode representasjon, la alle 0'ere være i fred til en 1'er finnes.
  2. La 1'erene i fred, men komplementer påfølgende bit til en 0'er finnes.
  3. 0'eren komplementeres, men la de påfølgende bit være i fred til en 1'er finnes.
  4. Tilbake til skritt 2.

Bilde

Eksempel på konvertering fra binær til Gray-kode.

Den inverse mapping blir noe tilsvarende.

På side 52 og 53 i boka, ser dere bitplan og Gray-koderepresentasjon av Lena-bildet. Disse bitplanbildene er ment å demonstrere at kompleksiteten i bitplanene øker ned mot de lavere bitplan, og at kompleksiteten av Gray-kodebitplan alltid er mindre enn det korresponderende binære bitplan.

Run-length koding av Gray-kodete bitplan
Vi har såvidt nevnt run-length koding tidligere. (Angi antall i et run.) Run-length koding av binærbilder (eller bitplan) kan gjøres i 1 eller 2 dimensjoner. I 1D run-length koding blir run av 0 og 1 variabel lengdekodet, med separate Huffmantabeller, tilpasset statistikken for 0'ere og 1'ere.

Det finnes mange varianter av 2D run-length koding, og basisideen er å kode startposisjon for et run i den nåværende linjen relativt til forrige linje. Dette utnytter vertikal korrelasjon, og vi kan oppnå bedre komprimering.

For å beregne entropi av 1D run-length brukes i Rabbani

H=(H0+H1) / (r0+r1)

hvor H0 og H1 er entropi av bits/runlength symbol av hhv. 0 og 1 run, og r0 og r1 er gjennomsnittlig lengde av run av hhv 0 og 1. Denne H kan betraktes som en nedre grense for hva vi kan oppnå av kompresjon ved 1D run-lengthkoding. I praksis vil resultatet kanskje vise en noe høyere bitrate.

Bilde

Tabell 6.1 på side 55 viser resultater. Resultater for Lena av kombinasjonen i figuren over:

Bitplan binary code Gray code
7 0.274 0.274
6 0.452 0.282
5 0.614 0.390
4 0.838 0.714
3 0.965 0.908
2 0.999 0.996
1 1.000 1.000
0 1.000 1.000
Totalt 6.142 5.564

Aritemtisk koding av bitplan

Bilde

Bitplankoding med Q-koder

En annen måte å kode bitplan på vil være å benytte aritemtisk koding istedet for run-length koding på bitplan.

IBM Q-koder

IBM Q-koder er en adaptiv aritemtisk binærkoder. For å kunne bruke denne, må meldingen vi skal kode være en binær strøm. En ikke-binær kilde må oversettes til en binær sekvens for å kunne bruke Q-koderen. Det passer derfor godt å bruke denne på separate bitplan.

Som vi husker er er meldingen representert ved et reelt tall mellom 0 og 1 i aritmetisk koding. Før noe kodes, er området for meldingen hele det halvåpne intervallet [0, 1). Etter hvert som symbolene prosesseres, blir intervallområdet smalere, og man velger den delen av intervallområdet som er allokert til symbolet.

For alfabet med bare to symboler, binæralfabetet, trenger den kumulative frekvensarrayen bare ha et element, som spesifiserer delingen mellom sannsynlighet for 0 og 1.

Encodesymbol(symbol, cumprob):
  if symbol = 0 then high := low + (high-low) * cumprob; /*leave low alone*/
  if symbol = 1 then low := low + (high-low) * cumprob;  /*leave high alone*/

Decodesymbol(cumprob)
  if value < cumprob then symbol := 0; high := low + (high-low) * cumprob;
  if value >= cumprob then symbol := 1; low := low + (high-low) * cumprob;
Multiplikasjonen kan fjernes, og vi får en raskere algoritme.

Q-koderen vedlikeholder imidlertid en mer sofistikert enn en enkel DMS. m nabopiksler former konteksten c. Med denne modellen antar vi at bildet genereres av en m'te ordens Markov-modell hvor hver tilstand bestemmes av en viss kombinasjon av m nabopiksler. Generellt vil m binærverdipiksler utgjøre 2m tilstander, hvor hver tilstand utgjør en kontekst.

Siden sannsynligheten av hvert binære symbol kan avhenge av naboer, kan man definere et antall distinkte tilstander hvor sannsynlighetsestimater vedlikeholdes. Hver tilstand refereres til som kontekst. Input til Q-koderen vil være det binære kildesymbol, sammen med 6-bit kontekstverdier.

I kodingsprosessen av kildesymbolet, blir sannsynlighetsestimatet oppdatert og lagret. Sannsynligheten (for LPS) kan anta en av 30 lovlige verdier. En lovlig verdi blant de 30 verdiene finnes ved oppslag i en tabell. (Tabellen er valgt ut fra empiri). Sannsynligheten approksimeres altså ved subtraksjoner og tabelloppslag, snarere enn multiplikasjoner.

Det kreves ikke noe forhåndsestimat av sannsynligheter for kontekstene, for de fremkommer etter at symbolet er kodet noen få ganger, sannsynlighetene oppdateres etterhvert som en tilstand har vært besøkt flere ganger.

Kodingen av et bestemt kildesymbol kan resultere i ingen eller flere outputbit, avhengig av sannsynligheten av symbolet i denne spesielle konteksten.

Som sagt vil m nabopiksler former konteksten c. I eksempelt har man brukt 7 nabopiksler. Bildet antas generert av en 7'ende ordens Markov-modell hvor hver tilstand bestemmes av kombinasjon av de 7 nabopiksler vist i figuren under. De 7 binærverdipikslene utgjør altså 27 = 128 tilstander, (hvor hver tilstand utgjør en kontekst).

Bilde

Hvis vi lar konteksten være som i figur 6.4, er resultatet av å bruke Q-koderen på bitplan gitt i tabell under (kolonne 1 og 2). BP 4, 5 og 6 viser størst differanse for BC og GC representasjon av dataene. For de tre minst signifikante bitplan (BP 0, 1 og 2) av LENA får vi ekspansjon av dataene. (fordi Q-koderen er ineffektiv til å kode stasjonære kilder). Det hadde altså vært bedre å la være å kode bitplanene.

Konteksten kan endres til å være naboer i et tidligere kodet plan istedet for alle naboer fra samme plan. BC og G fjernes fra fig. 6.4 og vi bruker istedet for xA og E fra forrige bitplan. Som vi ser av tabellen under (kolonne 3 og 4), får vi bedre kompresjon enn for en 2D kontekst. 3D kontekst utgjør en bedre modell av kilden, og gir derfor litt bedre komprimeringsresultat. Fortsatt har vi ekspansjon av noen bitplan.

Bitplan 2D Qcoder BC 2D Qcoder GC 3D Qcoder BC 3D Qcoder GC
7 0.144 0.144 0.144 0.144
6 0.279 0.150 0.162 0.153
5 0.450 0.235 0.263 0.237
4 0.736 0.571 0.541 0.540
3 0.955 0.860 0.753 0.788
2 1.039 1.027 0.976 0.982
1 1.043 1.042 1.040 1.039
0 1.043 1.042 1.042 1.042
Totalt 5.689 5.071 4.921 4.925

Bitrate for 2D- og 3D-kontekst for binærkode og Gray-kode

Hvis vi igjen betrakter figuren på side 52 og 53, kan vi se at bitplan med rimelig "orden" kan vi greie Å kode ganske bra, mens bitplanenen fulle av "støy" og tilfeldig variasjon i pikslene er det vanskelig å kode med et godt resultat. Dette er en generell trend. En følge av at entropien varierer.

Kap 7 - Lossless prediktiv koding

Huffmankoding brukt til koding av differanser i bildet

Bilde

På side 61 viser Figur 7.2 histogrammet for originalbildene LENA, og figur 7.3 viser histogram av differansen mellom en pikselverdi og en predikert verdi (basert på prediktoren Xm = 0.75A - 0.50B + 0.75C hvor ABC er naboer av Xm på denne og forrige linje). Differansen mellom to 8-bits verdierrepresenteres med 9 bit, dvs. et tall fra [-255, 255]. Histogrammet viser at dataene basert på differanse har mindre varians, og de er vesentlig mindre korrelerte. Standardavviket for originalbildene LENA er redusert fra s = 47.94 til se = 6.94 for det differansebaserte histogrammet.

Studier viser at differansebaserte histogrammer for bilder røft sett har den samme fasongen, og at variasjonen finnes i variansen. Fasongen har en høy peak rundt 0, og fordelingen er kjent som LaPlace-fordeling.

Bilde

For å kode det differansebaserte bildet med en "lokal" Huffmankode, kan vi benytte en to-pass algoritme. Første pass benyttes til å beregne differansen, bestemme histogrammet, og konstruere kodeboken. Det andre passet foretar kodingen ved bruk av kodeboken. En måte å elliminere to pass på, er å benytte en "global" Huffman; man konstruerer en kodebok basert på et gjennomsnittlig differansebasert histogram laget ved å benytte seg av flere bilder som er typiske for bildematerialet. (Lokal og global er brukt på en måte som kan virke forvirrende på meg, lokal brukes i dette tilfellet om et bilde, global om flere bilder. Vanligvis snakker vi ofte om global og lokal innenfor ett bilde). Implementasjonskompleksiteten kan ytterligere reduseres ved å bruke modifisert Huffman. Denne kan gjøres ytterligere effektiv ved å bruke den reelle 8-bits pikselverdien i stedet for differansen i forbindelse med kodeordet avsatt til de verdier som faller utenfor kodeboken. F.eks. som i tabell 7.1. Kodetabellen har 34 elementer, en Huffmankode for verdiene fra [-16, 16] , og en prefikskode for verdiene som faller utenfor dette intervallet. Dette gjør at de mest sannsynlige verdiene i intervallet [-16, 16] blir kodet med et lite antall bit, og at verdiene med mindre sannsynlighet utenfor intervallet kodes med 13 bit (5 bit prefix, og 8 bit pikselverdi).

Resultatet av å bruke reversibel differanskoding for LENA og BOOTS vises i Tabell 7.2.

Først ser vi 0'te ordens entropi av originalbildene, beregnet fra histogrammene. (EN DMS med 256 symboler, med sannsynlighet gitt ved histogrammet). Siden dette ikke avspeiler korrelasjon piksler i mellom, ligger denne entropien nær 8 bit. Entropien beregnet for differansbildet (fra dettes histogram, en DMS med 511 symboler) er en nedre grense for bitraten vi kan få ved kodingskjemaer som koder sekvensen som uavhengige symboler. Denne entropien er vesentlig mindre enn 0'te ordens entropi for originalbildet, siden pikselkorrelasjonen i hovedsak er fjernet gjennom prediksjonsprosessen. De neste elementene i tabellen er bitrater for forskjellige Huffmankoder. Bitraten av lokal Huffman er typisk svært nær entropien av differansebildet (mindre enn 1% i testbildene). Den globale Huffmankoden er basert på et gjennomsnittshistogram laget ved hjelp av 10 bilder, inkludert de to testbildene selv. Forskjellen mellom global og lokal metode er i vårt eksempel små (få prosent). Resultatet fra modifisert Huffmann fra [-64, 64] skiller seg vesentlig fra full kodebok. Selv om den modifiserte Huffmankoden gradvis blir større når kodeboken blir mindre, er tapet i effektivitet mindre enn 5%. Dette gjør at global modifisert Huffmankode er en levedyktig metode i applikasjoner hvor det er viktig å ha små kodebøker.

Aritmetisk koding av differansebildet

Bilde

Differansebildet vi laget (i forbindlese med Huffman-forelesning), består av k+1 bit ord. Direkte bruk av Q-koderen er ikke mulig. Det bygges et desisjonstre, som i figur 7.4. Først avgjøres om differnsen er 0 eller ei, deretter om den er positiv eller ei. de etterfølgende desisjoner bestemmer størrelsesorden av differansen. Etter maksimalt 256 desisjoner kan enhver verdi i området (-255, 255) bestemmes. Gjennomsnittlig lengde for hver desisjon er mye mindre. Hver desisjon kodes av Q-koderen med en passende kontekst.

Entropien av desisjonstreet tilsvarer 0'te ordens entropi. For å komme i nærheten av denne entropien med binær aritmetisk koding, må vi velge konteksten slik at hver desisjon kodes under en separat kontekst (primærkontekst). Dette gir et stort antall primærkontekster. En måte å redusere antallet av disse på, er å kode noen av de mindre sannsynlig binære desisjonene under samme kontekst (det vil si bruke samme sannsynlighetsestimat for de desisjonene). Videre kan desisjoner med noenlunde lik sannsynlighet også kodes under samme kontekst. Vi kan for eksemepl bruke 5 primærkontekster (to for å kode de første to desisjonene, 0?, + el. -?, to kontektster for en differanse verdi +1 eller -1, og til slutt en kontekst for de gjenværende 506 desisjoner.)

Entropien vi får ved å bruke disse fem primærkontekstene for LENA, er 4.59 bit/piksel. Hvis vi hadde brukt alle 510 kontekstene, ville vi for LENA fått 4.56 bits/piksel, og denne er altså ikke noe særlig mindre.

For å oppnå bitrater mindre enn 0'te ordens entropi, må noen av eller alle de binære desisjoner baseres på informasjon fra naboer. Hver primærkontekst kan deles inn i mengder av nabokontekster. Målet er å konstruere få og effektive nabokontekster.

Nabokontekstene kan defineres på mange måter. I eksemplet i Rabbani, baseres nabokonteksten på naboene rett over, og rett til venstre for det aktuelle pikslet, og man får totalt 45 kontekster. Se tabell 7.2 for beregning av entropien og bit-rate oppnåd med Q-koderen. Som ventet er bitraten litt større enn entropiverdien.

Kap 8 - lossy plus lossless residual encoding

I mange applikasjoner finnes det et krav om kort overføringshastighet (og dermed lav bitrate) som utelukker bruk av reversible metoder i utgangspunktet. I noen applikasjoner er det imidlertid kanskje nødvendig å sende en reversibel versjon på et senere stadium av overføringen, feks. innen medisin hvor to leger diskuterer et bilde over distanse. Generelt vil et skjema hvor man først sender en irreversibel versjon for så å følge opp med resten siden være:

Skjemaet kan ses på som en to-nivå progressiv overføringsmetode. Et irreversibel kodet bilde pluss en rest, kan tydes som en predikitv metode hvor det irreversibelt kodete bildet er en ikke-lineær prediksjon. Prediksjonen i dette tilfellet baseres ikke på nylig transmittert informasjon, og differansen må eksplisitt transmitteres som overhead.

Valg av reversibel metode bestemmer hvor mye infomrasjon som skal transmitteres, og hvor mye som blir til overs i resten.

Tabell 8.1 fra Rabbani viser DCT fra JPEG brukt som irreversibel metode. Man har deretter regnet ut 0'te ordens entropi i differansebildet. Som ventet vil øking av bitraten i det irreversibelt kodete bildet redusere entropien i resten (differansebidlet).

Konklusjon hybride

Rabbani omtaler i Kap 6 og 7 sammenstilling av forskjellige metoder, noen av dem har vi allerede vært inne på:

  1. resultat av Huffman og den adaptive binære aritmetiske koderen (Q-koder) på bitplan i bildet
  2. resultat av statisk og semi-adaptiv Huffmankoding på differanse mellom piksleverdi og predikert verdi og resultat av aritmetisk koding på differanse mellom piksleverdi og predikert verdi
  3. Koding av rest etter en lossy metode

[an error occurred while processing this directive]