Laboration 1: Distorsionsfri kodning av ljud och stillbilder

Uppgift

Målet med laborationen är att göra enkla stokastiska modeller för några olika signaler (musik och bilder), beräkna entropier samt att beräkna datatakter givet att man gör en huffmankodning av signalerna. Det är inte nödvändigt att ta fram själva kodorden i huffmankoderna, utan det räcker att ni beräknar den resulterande datatakten.

Arbetet ska utföras i grupper om 1 eller 2 studenter.

Ljudsignaler

Ljudsignalerna består av två musiksignaler och en talsignal. Musiksignalerna är i mono, samplade med 44.1 kHz samplingsfrekvens och kvantiserade till 8 bitar/sampel. Den finns två korta stycken, med lite olika karaktär. Talsignalen är i mono, samplad med 8 kHz samplingsfrekvens och kvantiserad till 8 bitar/sampel.

I Matlab kan man enkelt läsa WAV-filer med funktionen audioread. Den ger en vektor med samplen skalade så de ligger mellan -1 och 1. För att få heltal mellan -128 och 127 multiplicerar ni bara signalen med 128.

Entropiskattningar

För att få en uppfattning om vilka teoretiska prestanda som kan förväntas ska ni skatta några entropier. De entropier som ska skattas är H(X_i), H(X_i,X_i+1) (parentropi) och H(X_i+1 | X_i) (betingad entropi).

Minnesfri huffmankodning

Beräkna vilken datatakt man får när man huffmankodar enskilda sampel, oberoende av tidigare sampel.

Om ni inte vill skriva er egen huffmankodningsalgoritm, kan ni använda den funktion som finns upplagd här (läs gärna koden för att förstå hur den fungerar).

Huffmankodning av skillnader

För att utnyttja det minne (beroende) som finns mellan närliggande sampel ska ni pröva prediktiv kodning, där ni först gör en prediktion P_i och sen huffmankodar skillnaden Y_i = X_i-P_i. Pröva följande prediktorer:

P_i = X_i-1
P_i = 2*X_i-1-X_i-2

Tänkta sampel innan det första samplet i testsignalerna kan antas vara 0.

Jämför resultaten med entropierna.

Lyssna på musiksnuttarna och kommentera hur musikens karaktär påverkar datatakter och entropier.

Stillbilder

Bilderna är i gråskala kvantiserad till 8 bitar/bildpunkt, dvs varje bildpunkt tar värden mellan 0 (svart) och 255 (vitt). Det finns tre bilder med lite olika karaktär:

Bilderna kan läsas in i Matlab med hjälp av funktionen imread. Den returnerar en tvådimensionell matris av typen uint8. För att ni enklare ska kunna manipulera data bör ni omvandla bilden till datatypen double (x=double(x);).

Entropiskattningar

För att få en uppfattning om vilka teoretiska prestanda som kan förväntas ska ni skatta några entropier. De entropier som ska skattas är H(X_i,j), H(X_i,j,X_i+1,j), H(X_i,j,X_i,j+1) (parentropi horisontellt och vertikalt), H(X_i+1,j | X_i,j) och H(X_i,j+1 | X_i,j) (betingad entropi horisontellt och vertikalt).

Minnesfri huffmankodning

Beräkna vilken datatakt man får när man huffmankodar enskilda bildpunkter, oberoende av omgivande bildpunkter.

Huffmankodning av skillnader

För att utnyttja det minne (beroende) som finns mellan närliggande bildpunkter ska ni pröva prediktiv kodning, där ni först gör en prediktion P_i,j och sen huffmankodar skillnaden Y_i,j = X_i,j-P_i,j. Pröva följande prediktorer:

P_i,j = X_i-1,j
P_i,j = X_i,j-1
P_i,j = X_i-1,j+X_i,j-1-X_i-1,j-1

Tänkta bildpunkter utanför bildens kanter kan antas vara grå, dvs ha värdet 128.

Jämför resultaten med entropierna.

Kommentera hur bildernas utseende påverkar datatakter och entropier.

Redovisning

Resultatet redovisas med en skriftlig rapport som beskriver hur ni löste uppgiften och vilka resultat ni får.

Lämna en papperskopia av rapporten direkt till Harald, eller skicka en elektronisk version (PDF) via email.

Ange namn, personnummer och epostadress för alla gruppmedlemmar.