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 = '/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 [ ]:

...