INF2310 v?r 2019 - Ukeoppgave 13

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.