kompresjon_ukesoppgaver_uke1 – Universitetet i Oslo

IN2070 - Digital bildebehandling

In [ ]:

import numpy as np
import matplotlib.pyplot as plt
import os
import heapq

from PIL import Image
from urllib.request import urlretrieve

# Setter opp noen bedre standardargumenter for plotting med bilder
plt.rcParams['figure.figsize'] = [10.24, 7.68]
plt.rcParams['image.cmap'] = 'gray'

In [ ]:

# Last ned testbilde vi skal bruke
url = 'https://www.uio.no/studier/emner/matnat/ifi/IN2070/h23/undervisningsmateriale/bilder/lena.png'
if not os.path.isfile('lena.png'):
    urllib.request.urlretrieve(url, 'lena.png')

In [ ]:

# Laster inn bilde som array med PIL og normaliserer til flyttall
image = np.array(Image.open('lena.png')) / 255

# Eksempel på en funksjon som henter ut leksikografisk skannerekkefølge
def raster_scan(height, width):
    idx = np.arange(height*width)
    xidx = idx % width
    yidx = idx // width
    return yidx, xidx

Oppgave 1:¶

La $f$ være et gråtonebilde med høyde $H$ og bredde $W$.

Oppgave 1a:¶

Skriv en funksjon som returnerer to sekvenser med indekser $(y_i)_{i=1}^{HW}, (x_i)_{i=1}^{HW}$ slik at $\big(f(x_i,y_i)\big)_{i=1}^{HW}$ returnerer gråtoneverdiene i kontinuerlig diagonal skannerekkefølge.

Eksempelvis, for et $3 \times 3$ bilde ønsker vi en rekkefølge gitt av $$ \begin{bmatrix} 1& 3& 4 \\ 2& 5& 8 \\ 6& 7& 9 \\ \end{bmatrix} $$

som gir indeksene (med start i én) $x = (1,1,2,3,2,1,2,3,3)$ og $y = (1,2,1,1,2,3,3,2,3)$.

Oppgave 1b:¶

Skriv en funksjon som returnerer indekser for en kontinuerlig spiralrekkefølge.

Eksempelvis, for et $3 \times 3$ bilde ønsker vi denne gangen en rekkefølge gitt av $$ \begin{bmatrix} 1& 2& 3 \\ 8& 9& 4 \\ 7& 6& 5 \\ \end{bmatrix} $$

Tips:¶

Det er lett å hente ut den $n$te positive diagonalen fra en matrise A med bruk av A.diagonal(n).
Dersom man ønsker en negativ diagonal kan man flippe matrisen med bruk av np.fliplr eller np.flipud.
For en kontinuerlig skannerekkefølge, kan det også være nyttig å huske at vi kan invertere rekkefølgen på et array ved hjelp av arr[::-1].
For å slå sammen to eller flere arrays langs siste dimensjon kan man bruke np.concatenate([arr1, arr2,...], axis=-1).
Det kan også være nyttig å se på eksempelfunksjonen raster_scan som implementerer den standardiserte skannerekkefølgen.

In [ ]:

...

Oppgave 2:¶

I cellen under har vi en funksjon scan_2d_to_1d som tar ett bilde og en skannerekkefølgefunksjon som parametre, og returnerer bildet som en sekvens mhp. skannerekkefølgen. Skriv en funksjon scan_1d_to_2d som rekonstruerer originalbildet gitt de éndimensjonale sekvensen, bildedimensjonene, og skannerekkefølgefunksjonen.

In [ ]:

def scan_2d_to_1d(image, scanfn):
    height, width = image.shape
    return image[scanfn(height, width)]

def scan_1d_to_2d(seq, height, width, scanfn):
    # Skriv resten av funksjonen
    return ...

Oppgave 3:¶

Oppgave 3a:¶

Skriv en funksjon som regner differansetransformen over den siste dimensjonen til en sekvens eller bilde.

Oppgave 3b:¶

Skriv en funksjon som regner invers differansetransformen over den siste dimensjonen til et signal eller bilde.

Tips:¶

Husk at indeksering i Python aksepterer det som kalles Ellipsis objektet .... Dette gjør at vi kan "hoppe over" indekser vi ikke ønsker å endre.
Det kan være nyttig å benytte indekseringstriks som arr[...,a:b:s] der a er en startindeks, b er stoppindeks, og s er steglengde.
Ett annet tips som kanskje er nyttig er at å bruke indeksering arr[...,None] utvider dimensjonen med én i siste dimensjon.
For a gjøre kumulativ summering for inverstransformen kan man med hell benytte np.cumsum.
Vi har også funksjonen np.diff i numpy som kan gjøre differansen for oss. Les litt i dokumentasjonen hvis du vil vite mer.
For å sikre at du har gjort det riktig, kall gjerne plt.matshow for å se at differanse og inverstransform er implementert korrekt.

In [ ]:

...

Oppgave 4:¶

Oppgave 4a:¶

Skriv en funksjon som kvantiserer et bilde eller sekvens fra flyttallsrepresentasjon i $[0,1]$ til heltall med bitlengde $b$.

Du trenger ikke representere tallet med korrekt antall biter i datatypen, siden ikke alle bitlengder har en egen datatype.
I stedet bruker vi metoden seq.astype(np.int64) som midlertidig representerer tallet med 64 biters presisjon.

Oppgave 4b:¶

Skriv en funksjon som kvantiserer samt regner ut entropien til et array (en sekvens eller bilde).

Oppgave 4c:¶

Regn ut entropien av image kvantisert til 4, 6, og 8 bit dybde (også kalt bitlengde), og sammenlikn dette med entropien til bilder med differansetransformen (kvantisert til samme bitdybde).

In [ ]:

...

Oppgave 5:¶

Regn ut entropien til differansetransformen av bildet med skannerekkefølgene fra oppgave 1 og sammenlign resultatene for bitdybder 4, 6, 8. Hva observerer du, og hvilken metode vil du foretrekke?

In [ ]:

...

Oppgave 6:¶

Oppgave 6a:¶

Skriv en funksjon som dekomponerer et kvantisert bilde i bitplan, og plott planene for bitdybde 8.

Oppgave 6b:¶

Skriv en funksjon som konverterer til gråkode. Bruk dekomponeringsfunksjonen til å visualisere bitplanene til gråkoden og sammenlikn med resultatet i oppgave 6a.

In [ ]:

...

Oppgave 7:¶

Til slutt skal vi implementere Huffman koding. Fra forelesningen husker vi algoritmen:

Konstruer enkeltnode Huffman-trær med hvert av de $n$ symbolene $s_i$ med tilhørende vekt $f(s_i)$.
Repeter følgende til vi ender opp med ett enkelt tre:
- Velg to trær $T_0$ og $T_1$ med minimal vekt.
- Erstatt $T_0$ og $T_1$ med et nytt tre som har $T_0$ som venstre subtre og $T_1$ som høyre subtre.

Tips:¶

Bruk av np.unique(arr, return_counts=True) er veldig lurt å bruke for å hente symboler og frekvenser.
heapq modulen i Python kan med hell benyttes

In [ ]:

...