INF2310 v?r 2019 - L?sningshint 13

Oppgave 1 - Differansetransform og Huffman-koding

a)

Histogrammet til gr?tonebildets intensitetsverdier er h = [11 22 15 6], dvs. at h(0) = 11, h(1) = 22, h(2) = 15 og h(3) = 6. Fra dette histogrammet ser vi at Huffman-algoritmen vil: Totalt gj?r dette at lengdene av Huffman-kodeordene blir 3, 1, 2 og 3 for henholdsvis intensitet 0, 1, 2 og 3, noe som gir et gjennomsnittlige antall biter per piksel etter Huffman-koding av dette bildet p? omtrent 1,91.

1. Sl? sammen gruppen som best?r av 3 og gruppen som best?r av 0, som gir en ny gruppe med total forekomst p? 17,
2. Sl? sammen gruppen som best?r av 2 og gruppen som best?r av 0 og 3, som gir en ny gruppe med total forekomst p? 32,
3. Sl? sammen gruppen som best?r av 1 og gruppen som best?r av 0, 2 og 3.

b)

Differansetransformen av bildet er:

c)

Histogrammet til differansebildet er gitt ved h(-1) = 6, h(0) = 29, h(1) = 17 og h(2) = 2, som kan skrives som h = [6 29 17 2] under forst?else om at intervallet er heltallene mellom -1 og 2. Det er greit ? innse at Huffman-algoritmen vil resultere i n?yaktig samme kodebok for dette histogrammet som for histogrammet til det opprinnelige gr?tonebildets intensitetsverdier (se deloppgave 1), med unntak av at intensitetsverdiene som Huffman-kodeordene representerer n? er byttet ut med differanseverdier som har ¨¦n lavere verdi. Dermed vil lengdene av Huffman-kodeordene v?re 3, 1, 2 og 3 for henholdsvis differansene -1, 0, 1 og 2, noe som gj?r at vi vil bruke omtrent 1,61 biter per piksel i gjennomsnitt etter Huffman-koding av differansebildet.

d)

Entropien av gr?tonebildet gir en nedre grense for hvor kompakt gr?tonebildet kan kodes dersom vi bare koder ett piksel av gangen. Videre vet vi at denne grensen bare oppn?s n?r alle sannsynlighetene i det normaliserte histogrammet kan skrives som 1/2^k for (muligens forskjellige) heltallige k. Ettersom dette kravet ikke er oppfylt i det opprinnelige gr?tonebildet, er det en n?dvendighet at Huffman-kodingen resulterer i et gjennomsnittlig antall biter per piksel som er h?yere enn entropien.

N?r vi bruker differansetransformen ser vi ikke bare p? ett piksel av gangen. ? Huffman-kode differansebildet endrer ikke dette; i den totale kompresjonsprosedyren vil man (fors?ke ?) b?de redusere intersampel redundans (ved differansetransformen) og kodingsredundans (Huffman-kodingen). Entropien til det opprinnelige gr?tonebildet gir ikke noen nedre grense for kompresjonsraten i dette tilfellet, og det er derfor mulig ? oppn? h?yere kompresjonsrater enn entropien tilsier (som vi gj?r her).

Bemerkning: Siden vi Huffman-koder differansebildet vil entropien av differansebildet gi oss en nedre grense for hvor mange biter per piksel vi i gjennomsnitt m? bruke etter kodingen (som blir et m?l p? informasjonen i differansebildet n?r vi ser p? differanseverdiene enkeltvis). Denne entropien er omtrent 1,53, s? vi ser at ogs? her vil Huffman-kodingen resultere i lav kodingsredundans.

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

a)

Histogrammet til gr?tonebildets intensitetsverdier er h = [6 19 21 8], dvs. at h(0) = 6, h(1) = 19, h(2) = 21 og h(3) = 8. Fra dette histogrammet ser vi at Huffman-algoritmen vil: Totalt gj?r dette at lengdene av Huffman-kodeordene blir 3, 2, 1 og 3 for henholdsvis intensitet 0, 1, 2 og 3, noe som gir et gjennomsnittlige antall biter per piksel etter Huffman-koding av dette bildet p? omtrent 1,87.

1. Sl? sammen gruppen som best?r av 0 og gruppen som best?r av 3, som gir en ny gruppe med total forekomst p? 14,
2. Sl? sammen gruppen som best?r av 0 og 3 og gruppen som best?r av 1, som gir en ny gruppe med total forekomst p? 33,
3. Sl? sammen gruppen som best?r av 2 og gruppen som best?r av 0, 1 og 3.

b)

Resultatet etter og utf?rt l?pelengdetransformen p? hver rad blir:

1. (0,2), (1,3), (2,4)
2. (0,2), (1,4), (2,3)
3. (1,2), (0,2), (1,2), (2,3)
4. (1,2), (2,4), (3,3)
5. (1,3), (2,4), (3,2)
6. (1,3), (2,3), (3,3)

c)

Histogrammet til tallparenes intensitetsverdier er h = [3 7 6 3], dvs. at h(0) = 3, h(1) = 7, h(2) = 6 og h(3) = 3. Fra dette histogrammet ser vi at Huffman-algoritmen vil:

1. Sl? sammen gruppen som best?r av 0 og gruppen som best?r av 3, som gir en ny gruppe med total forekomst p? 6,
2. Sl? sammen gruppen som best?r av 0 og 3 og gruppen som best?r av 2, som gir en ny gruppe med total forekomst p? 12,
3. Sl? sammen gruppen som best?r av 1 og gruppen som best?r av 0, 2 og 3.

Totalt gj?r dette at lengdene av Huffman-kodeordene blir 3, 1, 2 og 3 for henholdsvis intensitet 0, 1, 2 og 3, noe som gj?r at Huffman-koden vil bruke 37 biter p? ? representere disse intensitetene.

Histogrammet til tallparenes l?pelengder er gitt ved h(2) = 7, h(3) = 8 og h(4) = 4, som kan skrives som h = [7 8 4] under forst?else om at intervallet er heltallene mellom 2 og 4. Det er rimelig enkelt ? innse at Huffman-algoritmen vil f?rst kombineres 4 og 2, for s? ? kombinere 3 med den forrige kombinasjonen. Dermed vil lengdene av Huffman-kodeordene blir 2, 1 og 2 for henholdsvis l?pelengde 2, 3 og 4, noe som gj?r at Huffman-koden vil bruke 30 biter p? ? representere disse l?pelengdene.

Siden det er 54 piksler i det opprinnelige bildet, vil det gjennomsnittlige antall biter per piksel etter denne kompresjonsprosedyren bli omtrent 1,24.

d)

Histogrammet til tallparene er [3 3 3 1 3 3 1 2] under forst?elsen av at posisjonene i histogrammet representerer henholdsvis tallparet (0,2), (1,2), (1,3), (1,4), (2,3), (2,4), (3,2) og (3,3). Fra dette histogrammet ser vi at Huffman-algoritmen vil:

1. Sl? sammen gruppen som best?r av (1,4) og gruppen som best?r av (3,2), som gir en ny gruppe med total forekomst p? 2,
2. Sl? sammen gruppen som best?r av (3,3) og gruppen som best?r av (1,4) og (3,2), som gir en ny gruppe med total forekomst p? 4,
3. Sl? sammen gruppen som best?r av (2,3) og gruppen som best?r av (2,4), som gir en ny gruppe med total forekomst p? 6,
4. Sl? sammen gruppen som best?r av (1,2) og gruppen som best?r av (1,3), som gir en ny gruppe med total forekomst p? 6,
5. Sl? sammen gruppen som best?r av (0,2) og gruppen som best?r av (1,4), (3,2) og (3,3), som gir en ny gruppe med total forekomst p? 7,
6. Sl? sammen gruppen som best?r av (1,2) og (1,3) og gruppen som best?r av (2,3) og (2,4), som gir en ny gruppe med total forekomst p? 12,
7. Sl? sammen gruppen som best?r av (0,2), (1,4), (3,2) og (3,3) og gruppen som best?r av (1,2), (1,3), (2,3) og (2,4).

Totalt gj?r dette at lengdene av Huffman-kodeordene blir 2, 3, 3, 4, 3, 3, 4 og 3 for tallparene n?r de er oppgitt i samme rekkef?lge som i histogrammet, noe som gj?r at Huffman-koden vil bruke 56 biter p? ? representere disse tallparene. Siden det er 54 piksler i det opprinnelige bildet, vil det gjennomsnittlige antall biter per piksel etter denne kompresjonsprosedyren bli omtrent 1,04.

e)

Differansebildet blir:

Dette bildet inneholder kun to forskjellige symboler, noe som gj?r at vi b?de kan og m? bruke 1 bit per piksel for ? kode dette bildet dersom vi skal kode hvert symbol for seg selv.

Oppgave 3 - L?pelengdetransform av bin?re bilder

a)

Hvis vi har N l?pelengder i en rad s? kommer vi til ? bruke nN biter for ? representere dette med en n-biters naturlig bin?rkode, mens vi trenger 2ⁿ-1 biter for ? representere raden uten kompresjon. For ? oppn? plassreduksjon m? l?pelengderepresentasjonen ta mindre biter enn det ukomprimerte bildet, alts? m? nN < 2ⁿ-1, noe som vi kan omskrive til N < (2ⁿ-1)/n.

b)

For n=4 f?r vi: N < (2⁴-1)/4 = 15/4 (= 3,75). Alts? m? antall l?pelengder i raden v?re mindre eller lik 3 for ? oppn? plassreduksjon n?r n=4. PS: Antall piksler i raden er da 2⁴-1 = 15, s? middelverdien av l?pelengdene m? minst v?re 15/3 = 5 for at vi skal oppn? kompresjon.
For n=8 f?r vi: N < (2⁸-1)/8 = 255/8 (= 31,875). Alts? m? antall l?pelengder i raden v?re mindre eller lik 31 for ? oppn? plassreduksjon n?r n=8. PS: Antall piksler i raden er da 2⁸-1 = 255, s? middelverdien av l?pelengdene m? minst v?re 255/31, omtrent 8,2, for at vi skal oppn? kompresjon.
For n=10 f?r vi: N < (2¹⁰-1)/10 = 1023/10 (= 102,3). Alts? m? antall l?pelengder i raden v?re mindre eller lik 102 for ? oppn? plassreduksjon n?r n=10. PS: Antall piksler i raden er da 2¹⁰-1 = 1023, s? middelverdien av l?pelengdene m? minst v?re 1023/102, omtrent 10,0, for at vi skal oppn? kompresjon.

c)

Forholdet mellom "bredden p? bildet" og den ?vre grensen til "det h?yeste antall l?pelengder vi kan ha og fortsatt oppn? kompresjon" er (2ⁿ-1) / ((2ⁿ-1)/n) = n.
Dette forholdet angir en nedre grense for hva middelverdien av l?pelengdene kan v?re og vi fortsatt oppn?r kompresjon; middelverdien av l?pelengdene m? v?re ekte st?rre enn n for at vi skal oppn? kompresjon.

Kombinert med uttrykket fra deloppgave a) har vi derfor at: For store bilder kan vi tillate oss ? ha mange l?pelengder (den ?vre grensen for N er da stor), men likevel m? hver l?pelengde v?re st?rre i gjennomsnitt enn for mindre bilder (n stiger, dog ganske langsomt sett i sammenheng med at den definerer bildets bredde ved 2ⁿ-1).

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

a)

Hver rad vil best? av 8 l?pelengder, og alle l?pelengdene er lik 512/8 = 64. Ved bruk av 8-biters naturlig bin?rkoding av b?de intensitetsverdier og l?pelengder vil vi totalt bruke 8 * (8*2 + 2) = 8*18 = 144 biter per rad.

b)

Bildet inneholder 512 like rader. Derfor vil Huffman-koden av en rad v?re den samme som Huffman-koden av hele bildet.

Etter l?pelengdetransform kan hver rad skrives som: 0 64 32 64 64 64 96 64 128 64 160 64 192 64 224 64 0 0. Vi kan bruke disse hyppighetene til ? finne et Huffman-kodetre:

Dette gir oss f?lgende Huffman-kodebok:

c)

Fra tabellen over ser vi kodeordet og antall forekomster av hvert symbol for hver rad. Multipliserer vi hver kodeordlengde med de tilsvarende hyppighetene f?r vi det totale antall biter som blir brukt til ? representere l?pelengdetransformen og EOL-merket; 1*9 + 3*3 + 6*(4*1) = 9+9+24 = 42 biter per rad. Siden det er 512 piksler per rad i det opprinnelige bildet, tilsvarer dette et gjennomsnittlig bitforbruk per piksel p? 42/512 = 21/256, som er omtrent 0,08. Ettersom vi bruker 8 biter per piksel i det ukomprimerte bildet, f?r vi en omtrentlig kompresjonsrate p? 8/0,08 = 100 (eksakt regning hadde gitt omtrent 97,5). Siden alle radene er like vil b?de bitforbruket og kompresjonsraten gjelde for hver rad s?vel som for hele bildet.

Hvis det hadde blitt bedt om ? beregne det gjennomsnittlige antall biter per l?pelengdekoeffisient (alts?, per ene verdi av l?pelengdeparene), inklusivt EOL-merket, ville svaret v?rt 42/18 = 7/3, som er omtrent 2,33.

d)

I det opprinnelige bildet er det ?tte forskjellige gr?toner og alle er like sannsynlige. Dette gj?r at enhver 3-biters bin?rkode som tilordner kodeord til de ?tte forskjellige gr?tonene er en optimal kode n?r vi koder enkeltpiksler. Kompresjonsraten blir da 8/3.

(Vi kunne i stedet argumentert med at entropien til dette bildet er eksakt 3; 8*(-(1/8)log₂(1/8)) = 8*3/8 = 3, og videre at dette optimumet opplagt kan oppn?s i dette tilfellet, nettopp ved en 3-biters bin?rkode.)

I det differansetransformerte bildet vil vi for hver rad finne sju elementer lik 32 (ved overgangen mellom ¡±trappetrinnene¡±), mens ellers bare 0 (i alt 505 elementer). Ettersom det bare finnes to verdier i bildet, vi ett bit per piksel v?re det beste vi i praksis kan oppn? n?r vi bare koder enkeltdifferanser. Vi f?r dermed en kompresjonsrate p? 8/1= 8. Alts? f?r vi 3 ganger h?yere kompresjonsrate etter differansetransformen enn originalt, dersom vi i begge tilfeller koder enkeltsymboler p? en best mulig m?te.

Oppgave 5 - Lempel-Ziv-Welch-transform

a)

Fra det oppgitte histogrammet ser vi at ¨¦n gyldig fremgangsm?te for Huffman-algoritmen er: I den resulterende Huffman-kodingen vil alle kodeordene ha lengde 2. Siden Huffman-koding er optimal under begrensningen at vi koder enkeltsymboler, s? betyr dette at alle kodinger der alle kodeordene har lengde 2 er optimale p? samme m?te som Huffman-koden. Naturlig bin?rkoding er ¨¦n slik koding.

1. Sl? sammen gruppen som best?r av "b" og gruppen som best?r av "c", som gir en ny gruppe med total forekomst p? 15,
2. Sl? sammen gruppen som best?r av "a" og gruppen som best?r av "d", som gir en ny gruppe med total forekomst p? 21,
3. Sl? sammen gruppen som best?r av "a" og "d" og gruppen som best?r av "b" og "c".

b)

F?lg oppskriften for senderen og du vil ende opp med f?lgende LZW-kodesekvens: 0 1 4 2 6 3 8 0 10 9 12 7 14.

c)

Kodesekvensen fra deloppgave 2 inneholder 13 koder, og med naturlig bin?rkoding bruker vi 4 biter p? ? representere hver av dem. Totalt vil vi derfor bruke 4*13 = 52 biter p? den f?rste meldingen. Siden denne meldingen inneholder 36 symboler, tilsvarer dette et gjennomsnittlig bitforbruk per symbol (av den opprinnelige meldingen) p? 52/36 = 13/9, som er omtrent 1,44.

d)

Entropien er en nedre grense for hvor mange biter vi trenger per symbol n?r vi koder symbolene enkeltvis. LZW-koding koder derimot ikke symbolene enkeltvis. Dermed er ikke LZW-koding begrenset av entropien slik som Shannon-Fano-koding og Huffman-koding er.

(Vi kunne alternativt argumentert med at LZW-koding pr?ver ? redusere b?de intersampel redundans og kodingsredundans, og at entropien kun er knyttet til kodingsredundansen.)

e)

F?lg oppskriften for senderen og du vil ende opp med f?lgende LZW-kodesekvens: 0 1 1 2 3 1 4 0 2 11 3 0 0 14 15 2 7 4 7 14 8 18 7 1.

f)

Kodesekvensen fra deloppgave 5 inneholder 24 koder, og med naturlig bin?rkoding bruker vi 5 biter p? ? representere hver av dem. Totalt vil vi derfor bruke 5*24 = 120 biter p? den andre meldingen. Siden denne meldingen inneholder 36 symboler, tilsvarer dette et gjennomsnittlig bitforbruk per symbol (av den opprinnelige meldingen) p? 120/36 = 10/3, som er omtrent 3,33.

g)

LZW-transformen utnytter m?nstre i meldingen. Et n?dvendig kriterium for at LZW-transformering skal resultere i plassreduksjon er derfor at det finnes m?nstre i meldingen som komprimeres. Det vil det normalt ikke gj?re i en melding som best?r av symboler som er plassert p? tilfeldige posisjoner i meldingen, som i den andre meldingen i denne oppgaven.