Ukesoppgaver IN2070: Kompresjon og Koding II¶

Oppgave 1:¶

I denne oppgaven skal vi kode DCT-II transformen; f?rst med en naiv matrisemultiplikasjon, s? med en fast Fourier transform (fft) variant.

1a: Enkel DCT¶

Skriv en funksjon som regner ut DCT-II matrisen. Formelen er gitt ved

$$ \begin{align} \tilde x_k = \sum_{n=0}^{N-1} x_n \cos\big(k\pi (n + 1/2) / N\big), \end{align} $$

hvor $(x_n)_{n=0}^{N-1}$ er et 1D signal (tenk rad eller kolonne i bildet). Skriv ogs? en funksjon som anvender seperabilitet for bilder for ? regne ut DCT transformen gitt matrisen. Merk: DCT utregningen er i standardform, og ikke ortonormal

Tips:

• Vi vil ha indekser for $k=0,...,N-1$ kolonner og $n=0,...,N-1$ rader i bildet. Her kan np.meshgrid benyttes med hell.
• Gitt arrayene k, n s? er det enkelt ? vektorisere utregningene i Numpy med np.cos.
• For separabilitet har vi $\tilde X = \mathcal{C} X \mathcal{C}^{\intercal}$ der $X$ er orginalbildet med dimensjon $N \times N$.
• Hva skjer hvis bildet har forskjellige dimensjoner for h?yde og bredde? Tenk litt p? dette.

1b: Invers DCT¶

Invers til DCT-II fra 1a (gjerne kalt DCT-III eller iDCT) er gitt ved

$$ \begin{align} x_k = \frac{2}{N}\Big(\frac{1}{2}x_0 + \sum_{n=1}^{N-1} \tilde x_n \cos\big(n\pi (k + 1/2) / N\big)\Big), \end{align} $$

Lag en funksjon som regner ut iDCT matrisen. Bekreft implementasjonen ved ? skrive en funksjon som foretar iDCT og inverter deretter transformen fra 1a.

Oppgave 2:¶

2a: WHT Matrise¶

Skriv en funksjon som regner ut Walsh-Hademard transformen. Bruk Hademard form av matrisen, gitt ved rekursjonen $$ W^{(2n)} = \begin{bmatrix} W^{(n)} & W^{(n)}\\ W^{(n)} & -W^{(n)}\\ \end{bmatrix} $$

og bruk nullutvidelse for ? utvide bildet til n?rmeste potensverdi av 2.

2b: WHT vs. DCT¶

Regn ut WHT og DCT for bildet, og estimer glissenhet (sparsity) ved ? ta det s?kalte Euclid-in-a-Taxicab forholdet gitt ved

$$ \frac{\lVert x \rVert_1}{\lVert x \rVert_2} = \frac{\sum_{m=0}^{N-1} \lvert x_m \rvert}{\sqrt{\sum_{n=0}^{N-1} x_n^2}}. $$

Jo lavere forhold (teoretisk minimum 1), jo mer glissen er transformasjonen.

Oppgave 3: LZW transform¶

3a: LZW Enkoder¶

Skriv en LZW Enkoder ved ? benytte f?lgende steg:

1. Initialisering: Start med en ordliste (dictionary) som inneholder alle tegn i ASCII-tegnsettet, hver med sin unike kode.
2. Lesing: Les inn tegn fra dataene som skal komprimeres sekvensielt.
3. S?k i ordlisten: For hver nye tegnsekvens, sjekk om sekvensen finnes i ordlisten.
   • Hvis den finnes, fortsett ? legge til tegn til sekvensen og gjenta s?ket.
   • Hvis den ikke finnes, utf?r f?lgende trinn:
4. Lagre til ordlisten: Legg til den nye tegnsekvensen i ordlisten med en ny unik kode.
5. Skriv ut kode: Skriv ut koden som tilsvarer den lengste sekvensen som finnes i ordlisten.
6. Fortsett prosessen: Start den nye sekvensen med det tegnet som ikke ble funnet i ordlisten og gjenta prosessen.
7. Slutten av data: N?r det ikke er flere tegn ? lese, skriv ut koden for den siste sekvensen.
8. Output: Komprimerte data vil v?re en sekvens av koder som representerer de lengre strengene i originaldataene.

Tips: ASCII kodesettet kan hentes ut ved chr(i) for i in range(256). Det kan v?re lurt ? teste med en liten streng underveis.

3b: LZW Dekoder¶

Skriv s? en LZW dekoder, ved f?lgende steg:

1. Initialisering: Opprett en ordliste (dictionary) identisk med den som ble brukt i kompressoren.
2. Les f?rste kode: Les den f?rste koden fra de komprimerte dataene og oversett den til det tilsvarende tegnet eller tegnsekvensen fra ordlisten. Skriv ut denne sekvensen til output.
3. Forrige sekvens: Lagre den dekodede tegnsekvensen som den forrige sekvensen.
4. Prosesser p?f?lgende koder: For hver p?f?lgende kode:
   • Finn i ordlisten: Oversett koden til en sekvens ved ? se den opp i ordlisten.
     • Hvis koden ikke finnes i ordlisten, er det en spesiell situasjon. Sekvensen m? v?re den forrige sekvensen pluss dens f?rste tegn. Generer denne sekvensen.
     • Hvis koden finnes, er det direkte oversettelsen av koden til en sekvens.
   • Skriv ut sekvens: Skriv ut den dekodede sekvensen til output.
   • Oppdater ordlisten: Legg til en ny sekvens i ordlisten som er lik den forrige sekvensen pluss det f?rste tegnet i den n?v?rende dekodede sekvensen.
   • Oppdater forrige sekvens: Sett den n?v?rende dekodede sekvensen som den forrige sekvensen for neste iterasjon.
5. Fortsett til enden: Fortsett prosessen til alle kodene er lest og dekodet.
6. Output: Det dekodede outputtet skal n? v?re en eksakt kopi av de originale dataene f?r de ble komprimert.

3c: Enkod teksten¶

Den vakre teksten greatlyric gir frysninger til alle som v?ger lese den. Enkod teksten, sjekk at den dekodes korrekt, og regn ut kompresjonsraten gitt ved

$$ \frac{\mathrm{original\,\,lengde}}{\mathrm{enkodet\,\,lengde}} $$

Er kompresjonsraten som forventet?