INF2310 vår 2012 - UKEOPPGAVER 10

Oppgave 1 - Løpelengdekoding av binære bilder

Tiltenkte hjelpemidler: Ingen

I denne oppgaven skal du undersøke når det er plassbesparende å løpelengdetransformere binære bilder. Vi antar at bildet har størrelse 2ⁿ-1 x 2ⁿ-1 og at det benyttes naturlig binærkode for å representere løpelengdene. Videre definerer vi at første løpelengde skal representere antall hvite piksler som raden starter med - hvis radens første piksel er svart vil denne løpelengden være 0.

1. Finn et uttrykk for det høyeste antall løpelengder som du under disse forutsetningene kan ha i en rad i bildet hvis løpelengdetransformen skal gi noen kompresjon i forhold til det ukomprimerte binære bildet?
2. Hva blir det høyeste antall løpelengder du kan ha i en rad i bildet når n=4, n=8 og n=10?
3. Hva er forholdet mellom den øvre grensen til "det høyeste antall løpelengder vi kan ha og fortsatt oppnå kompresjon" og "bredden av bildet"? Hva betyr det at dette forholdet synker ettersom n, som definerer bildets bredde, øker?

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

Tiltenkte hjelpemidler: Ingen

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 8 vertikale, monotone striper.

1. Hvor mange biter vil vi måtte bruke per rad hvis vi løpelengdetransformerer dette gråtonebildet og bruker en felles naturlig binærkode for både intensitetsverdier og løpelengder, og bruker løpelengdeparet (0,0) for å indikere slutten av en rad (EOL)?
2. Finn en felles Huffman-kode for begge verdiene av alle løpelengdeparene (du skal altså ende opp med kun én kodebok). Anta fortsatt at vi bruker løpelengdeparet (0,0) for å indikere EOL.
3. Beregn omtrentlig hvor mange biter vi i gjennomsnitt vil bruke per piksel (av det opprinnelige bildet) etter denne Huffman-kodingen av løpelengdeparene. Angi også omtrentlig hvilken kompresjonsrate dette tilsvarer.
4. Anta at du hadde gjort en differansetransform av gråtonebildet. Før et enkelt resonnement som forklarer hvorfor kompresjonsraten ved kompresjon 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 3 - Lempel-Ziv-Welch-koding

Tiltenkte hjelpemidler: Ingen

Anta at vi har gitt følgende to ord:

1. ababcabcdabcdaabcdadaabcdadcaabcdadc
2. abbcdbabacacdaadaaaccdabcddadbaaccdb

Begge ordene 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 ordene ovenfor, dvs. "a", "b", "c" og "d", og at disse symbolene har koder 0, 1, 2 og 3, henholdsvis.

1. 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.
2. Beregn LZW-koden av det første ordet (se seksjon 18.7.3 i kompendiet eller s. 8-10 i forelesningsnotatet). Du skal i denne oppgaven ikke sette noen begrensning på størrelsen av listen (selv om man typisk ville gjort det i praksis). 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.
3. Anta at vi bruker naturlig binærkode for å representere LZW-kodene fra deloppgave 2. Hvor mange biter vil vi i gjennomsnitt bruk per symbol (av det opprinnelige ordet) etter LZW-kodingen?
4. Entropien til det første ordet (og dermed også det andre ordet) er omtrent 1,95. Forklar hvorfor LZW-kodingen resulterer i et bitforbruk som er lavere enn entropien tilsvarer.
5. Beregn LZW-koden av det andre ordet 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.
6. Anta at vi bruker naturlig binærkode for å representere LZW-kodene fra deloppgave 5. Hvor mange biter vil vi i gjennomsnitt bruk per symbol (av det opprinnelige ordet) etter LZW-kodingen?
7. Du fant i deloppgave 6 at LZW-kodingen av den andre ordet ikke vil resultere i noen plassbesparing i forhold til naturlig binærkoding - faktisk vil kodingen resultere i et økt bitforbruk. Vi kan begrunne dette ut ifra at det andre ordet er en tilfeldig permutering (dvs. "omstokking") av det første ordet. Bruk dette til å angi et generelt nødvendig kriterium for at LZW-koding skal føre til plassreduksjon.

Oppgave 4 - Aritmetisk koding

Tiltenkte hjelpemidler: Kalkulator

Vi har gitt ord: adcdcdddba

1. Beregn det gjennomsnittlige bitforbruket per symbol etter Huffman-koding av dette ordet.
2. Beregn den aritmetiske koden av dette ordet etterfulgt av symbolet END-OF-DATA (EOD) (se seksjon 18.7.4 i kompendiet eller s. 13-15 og 19-22 i forelesningsnotatet). Du skal bruke følgende modell:
   

   Symbol	a	b	c	d	EOD
   Sannsynlighet	2/11	1/11	2/11	5/11	1/11

3. Hvor mange biter brukes det i gjennomsnitt per symbol etter den aritmetiske kodingen?
4. Entropien til ordet er omtrent 1,73. Siden entropien er høyere enn det gjennomsnittlige antall biter per symbol etter aritmetisk koding, vet vi at den aritmetiske kodingen må (i dette tilfellet) redusere minst én annen type redundans enn kodingsredundansen. Hvilken type redundans er dette? Kan dette betraktes som en tiltenkt oppførsel ved aritmetisk koding av denne typen eller skjer denne reduksjonen bare ved en tilfeldighet?

Oppgave 5 - Implementasjon av aritmetisk koding

Tiltenkte hjelpemidler: MATLAB

Implementer en MATLAB-funksjon (eller en metode i et annet programmeringsspråk) som ved bruk av et histogram beregner en aritmetisk kode av en sekvens av symboler. Funksjonen/metoden skal først finne intervallgrensene og deretter finne en kortest mulig binær representasjon av et tall i intervallet.

Du kan selv velge hvordan du vil behandle stoppeproblemet. F.eks. kan du anta at brukeren av funksjonen/metoden har laget histogrammet slik at det inneholder symbolet END-OF-DATA (EOD) og at sekvensen av symboler som skal kodes inneholder dette symbolet én gang, som siste symbol.

Tips 1 (MATLAB): For å regne nøyaktig med brøktall i MATLAB kan du bruke sym-kommandoen: http://www.mathworks.se/help/toolbox/symbolic/f1-5556.html

Tips 2 (Java): For å regne nøyaktig med brøktall i Java kan du bruke følgende klasse: http://introcs.cs.princeton.edu/java/92symbolic/BigRational.java.html