Ukeoppgave 12 - INF2310 vår 2017

Oppgave 1 - Differansetransform og Huffman-koding

Vi har gitt følgende gråtonebilde:

a)

Hvor mange biter brukes i gjennomsnitt per piksel etter Huffman-koding av dette bildet - hvis vi ser bort fra den plassen som trengs for å lagre kodeboken?

b)

Finn differansetransformen av gråtonebildet (se seksjon 18.4.1 i kompendiet).

c)

Beregn det gjennomsnittlige antall biter per piksel etter Huffman-koding av det differansetransformerte bildet - igjen når vi ser bort fra den plassen som trengs for å lagre kodeboken.

d)

Entropien til gråtonebildet vi startet med er omtrent 1,86. Hvorfor ble det gjennomsnittlige antall biter per piksel større enn entropien i deloppgave a), men mindre enn entropien i deloppgave c)?

Oppgave 2 - Løpelengdetransform og Huffman-koding
... og "differansetransform" i tid

Vi har gitt følgende gråtonebilde:

a)

Hvor mange biter brukes i gjennomsnitt per piksel etter Huffman-koding av dette bildet - hvis vi ser bort fra den plassen som trengs for å lagre kodeboken?

b)

Utfør løpelengdetransformen på hver rad av gråtonebildet.

c)

Hvert av tallparene du fikk etter løpelengdetransformen består av en gråtoneintensitet og en løpelengde. Beregn hvor mange biter Huffman-koden av disse løpelengdene bruker, og tilsvarende hvor mange biter Huffman-koden av disse gråtoneintensitetene bruker (du skal her altså bruke histogrammet av gråtoneintensitetene i tallparene som løpelengdetransformen fant, ikke histogrammet av gråtonebildets intensiteter). Summer de to antallene og divider på antall piksler i det opprinnelige bildet for å finne hvor mange biter det i gjennomsnitt brukes per piksel etter denne kompresjonsprosedyren (løpelengdetransform + 2xHuffman-koding). Vi ser igjen bort fra den plassen som trengs for å lagre Huffman-kodebøkene.

d)

Istedetfor å Huffman-kode løpelengdene og gråtoneintensitetene separat, så kan vi Huffman-kode hele tallparet (gråtoneintensitet, løpelengde). Beregn hvor mange biter Huffman-koden av tallparene bruker. Divider på antall piksler i det opprinnelige bildet for å finne hvor mange biter det i gjennomsnitt brukes per piksel etter denne kompresjonsprosedyren (løpelengdetransform + Huffman-koding). Vi ser igjen bort fra den plassen som trengs for å lagre Huffman-kodeboken.

e)

Anta at gråtonebildet vi startet denne oppgaven med er det første bilde i en bildesekvens, og at det andre bildet i bildesekvensen er gråtonebildet vi hadde gitt i oppgave 1. Beregn differansen mellom gråtonebildet fra forrige oppgave og gråtonebildet fra denne oppgaven. Hvor mange biter må du bruke per piksel for å kode dette differansebildet dersom vi skal kode hver differanse for seg selv - hvis vi igjen ser bort fra den plassen som trengs for å lagre kodeboken?

Oppgave 3 - Løpelengdetransform av binære bilder

I denne oppgaven skal du undersøke når det er plassbesparende å løpelengdetransformere binære bilder.

Anta vi har et bilde som har størrelse 2ⁿ-1 x 2ⁿ-1 og at det benyttes naturlig binærkoding av løpelengdene. Du skal anta at vi bruker n biter på å representere hver løpelengde, selv om det i mange bilder ikke vil være behov for flere av de lengste løpelengdene og vi dermed for noen bilder kunne brukt færre biter per løpelengde selv ved naturlig binærkode. Videre definerer vi at første løpelengde skal angi antall hvite piksler som raden starter med - hvis radens første piksel er svart vil denne løpelengden være 0.

a)

Finn et uttrykk for det høyeste antall løpelengder vi kan ha i en rad i bildet hvis løpelengdetransformen skal gi noen kompresjon i forhold til å ikke komprimere raden.

b)

Hva er det høyeste antall løpelengder du kan ha i en rad i bildet når n=4, n=8 og n=10, og vi fortsatt oppnår noen kompresjon i forhold til å ikke kromprimere raden?

c)

Finn et uttrykk for forholdet mellom "bredden av bildet" og den øvre grensen til "det høyeste antall løpelengder vi kan ha og fortsatt oppnå kompresjon". Forklar med ord hva dette forholdet angir. Hva betyr det at dette forholdet stiger ettersom n, som definerer bildets bredde, øker?

Oppgave 4 - Løpelengdetransform, differansetransform og Huffman-koding

Vi har gitt følgende 512x512 gråtonebilde med 8 bitplan:

Langs venstre kant i dette bildet er intensitetsverdien 0, og den øker med 32 i jevne ”trappetrinn” mot høyre, slik at det dannes åtte vertikale, monotone striper.

a)

Hvor mange biter vil vi måtte bruke per rad hvis vi løpelengdetransformerer dette gråtonebildet og bruker 8-biters naturlig binærkoding av både intensitetsverdier og løpelengder, og bruker løpelengdeparet (0,0) for å indikere slutten av en rad (EOL)?

b)

Finn en felles Huffman-kode for begge verdiene av alle løpelengdeparene (du skal altså ende opp med kun én kodebok, og symbolene i denne kodeboken vil generelt være heltall mellom 0 og 512). Anta fortsatt at vi bruker løpelengdeparet (0,0) for å indikere EOL.

c)

Beregn hvor mange biter vi i gjennomsnitt vil bruke per piksel (av det opprinnelige bildet) etter denne Huffman-kodingen av løpelengdeparene. Angi også hvilken kompresjonsrate dette tilsvarer.

d)

Anta at du hadde gjort en differansetransform av gråtonebildet. Før et enkelt resonnement som forklarer hvorfor kompresjonsraten ved best mulig koding av enkeltpiksler etter differansetransformen er nøyaktig 3 ganger så høy som den beste kompresjonsraten vi kan oppnå ved enkeltpikselkoding av det opprinnelige gråtonebildet.

Oppgave 5 - Lempel-Ziv-Welch-transform

Anta at vi har gitt følgende to meldinger:

1. ababcabcdabcdaabcdadaabcdadcaabcdadc
2. abbcdbabacacdaadaaaccdabcddadbaaccdb

Begge meldingene inneholder nøyaktig de samme symbolene, og forekomsttabellen (til hver av dem) er:

Vi skal videre anta at LZW-koderen og LZW-dekoderen er enige om et alfabet som utelukkende består av de fire symbolene i meldingene ovenfor, dvs. "a", "b", "c" og "d", og at disse symbolene har koder 0, 1, 2 og 3, henholdsvis.

a)

Forklar hvorfor naturlig binærkode er én optimal kode dersom vi begrenser oss til å kode symbolene enkeltvis. Hint: Huffman-koding gir en optimal kode under denne begrensningen.

b)

Beregn LZW-koden av den første meldingen. Du skal i denne oppgaven ikke sette noen begrensning på størrelsen av listen. Tips: Senderens liste vil etter koding bestå av 16 symbolsekvenser (med tilhørende koder), inkluderte de 4 symbolsekvensene (med tilhørende koder) som listen ble initiert med fra alfabetet.

c)

Hvor mange biter vil vi i gjennomsnitt bruke per symbol (av den opprinnelige meldingen) etter naturlig binærkoding av LZW-kodene du fant i deloppgave b)?

d)

Entropien til den første meldingen (og dermed også den andre meldingen) er omtrent 1,95. Forklar hvorfor det kan være slik som det er i dette tilfellet, at naturlig binærkoding av LZW-kodene resulterer i et gjennomsnittlig bitforbruk per symbol som er lavere enn entropien.

e)

Beregn LZW-koden av den andre meldingen når du igjen ikke setter noen begrensning på størrelsen av listen. Tips: Senderens liste vil etter koding bestå av 27 symbolsekvenser (med tilhørende koder), inkluderte de 4 symbolsekvensene (med tilhørende koder) som listen ble initiert med fra alfabetet.

f)

Hvor mange biter vil vi i gjennomsnitt bruke per symbol (av den opprinnelige meldingen) etter naturlig binærkoding av LZW-kodene du fant i deloppgave e)?

g)

Du fant i deloppgave f) at naturlig binærkoding av LZW-kodene av den andre meldingen ikke vil resultere i noen plassbesparing i forhold til direkte naturlig binærkoding av symbolene - faktisk vil det å legge til LZW-transformeringen resultere i et økt bitforbruk. Vi kan begrunne dette ut ifra at den andre meldingen er en tilfeldig permutering (dvs. "omstokking") av den første meldingen. Bruk dette til å angi et generelt nødvendig kriterium for at LZW-transformering skal føre til plassreduksjon.