{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c8710153",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Ukesoppgaver IN 3370: Kompresjon og Koding I"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d842cba6-86e9-4aca-9122-1c73b74067d7",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import os\n",
    "import heapq\n",
    "\n",
    "from PIL import Image\n",
    "from urllib.request import urlretrieve\n",
    "\n",
    "# Setter opp noen bedre standardargumenter for plotting med bilder\n",
    "plt.rcParams['figure.figsize'] = [10.24, 7.68]\n",
    "plt.rcParams['image.cmap'] = 'gray'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "905640f6-9d26-47f4-8c17-3d440b59a91b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Last ned testbilde vi skal bruke\n",
    "url = '/studier/emner/matnat/ifi/IN3370/h25/undervisningsmateriale/bilder/lena.png'\n",
    "if not os.path.isfile('lena.png'):\n",
    "    urlretrieve(url, 'lena.png')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "5ce7a1c0-5983-4e51-8191-a09083398e70",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Laster inn bilde som array med PIL og normaliserer til flyttall\n",
    "image = np.array(Image.open('lena.png')) / 255\n",
    "\n",
    "# Eksempel på en funksjon som henter ut leksikografisk skannerekkefølge\n",
    "def raster_scan(height, width):\n",
    "    idx = np.arange(height*width)\n",
    "    xidx = idx % width\n",
    "    yidx = idx // width\n",
    "    return yidx, xidx"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab12e05b-00a2-442b-be80-c655464ce223",
   "metadata": {},
   "source": [
    "### Oppgave 1:\n",
    "\n",
    "La $f$ være et gråtonebilde med høyde $H$ og bredde $W$. \n",
    "\n",
    "#### Oppgave 1a:\n",
    "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. \n",
    "\n",
    "Eksempelvis, for et $3 \\times 3$ bilde ønsker vi en rekkefølge gitt av\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "1& 3& 4 \\\\ \n",
    "2& 5& 8 \\\\\n",
    "6& 7& 9 \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "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)$.\n",
    "\n",
    "#### Oppgave 1b:\n",
    "Skriv en funksjon som returnerer indekser for en kontinuerlig spiralrekkefølge. \n",
    "\n",
    "Eksempelvis, for et $3 \\times 3$ bilde ønsker vi denne gangen en rekkefølge gitt av\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "1& 2& 3 \\\\ \n",
    "8& 9& 4 \\\\\n",
    "7& 6& 5 \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "### Tips:\n",
    "\n",
    "- Det er lett å hente ut den $n$te positive diagonalen fra en matrise `A` med bruk av `A.diagonal(n)`. \n",
    "- Dersom man ønsker en negativ diagonal kan man flippe matrisen med bruk av `np.fliplr` eller `np.flipud`.\n",
    "- 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]`.\n",
    "- For å slå sammen to eller flere arrays langs siste dimensjon kan man bruke `np.concatenate([arr1, arr2,...], axis=-1)`.\n",
    "- Det kan også være nyttig å se på eksempelfunksjonen `raster_scan` som implementerer den standardiserte skannerekkefølgen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5bb4a9d4-e89d-4d66-a217-c619704a6a5a",
   "metadata": {},
   "outputs": [],
   "source": [
    "..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "162159c1-9899-4b0a-9795-a332871fb678",
   "metadata": {},
   "source": [
    "### Oppgave 2:\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "04d92df6-993c-4095-a9fb-a98c09dd4a77",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def scan_2d_to_1d(image, scanfn):\n",
    "    height, width = image.shape\n",
    "    return image[scanfn(height, width)]\n",
    "\n",
    "def scan_1d_to_2d(seq, height, width, scanfn):\n",
    "    # Skriv resten av funksjonen\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7e9e225-6992-4f26-a24c-7ebca66a6379",
   "metadata": {},
   "source": [
    "### Oppgave 3:\n",
    "\n",
    "#### Oppgave 3a:\n",
    "Skriv en funksjon som regner differansetransformen over den siste dimensjonen til en sekvens eller bilde.\n",
    "\n",
    "#### Oppgave 3b:\n",
    "Skriv en funksjon som regner invers differansetransformen over den siste dimensjonen til et signal eller bilde.\n",
    "\n",
    "#### Tips:\n",
    "- Husk at indeksering i Python aksepterer det som kalles `Ellipsis` objektet `...`. Dette gjør at vi kan \"hoppe over\" indekser vi ikke ønsker å endre.\n",
    "- Det kan være nyttig å benytte indekseringstriks som `arr[...,a:b:s]` der `a` er en startindeks, `b` er stoppindeks, og `s` er steglengde.\n",
    "- Ett annet tips som kanskje er nyttig er at å bruke indeksering `arr[...,None]` utvider dimensjonen med én i siste dimensjon.\n",
    "- For a gjøre kumulativ summering for inverstransformen kan man med hell benytte `np.cumsum`.\n",
    "- Vi har også funksjonen `np.diff` i numpy som kan gjøre differansen for oss. Les litt i [dokumentasjonen](https://numpy.org/doc/stable/reference/generated/numpy.diff.html) hvis du vil vite mer.\n",
    "- For å sikre at du har gjort det riktig, kall gjerne `plt.matshow` for å se at differanse og inverstransform er implementert korrekt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "34a4e356-388a-4c8a-80b5-eae0d926cc58",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f910093-6b19-47fd-8fa3-80067c706f65",
   "metadata": {},
   "source": [
    "### Oppgave 4:\n",
    "\n",
    "#### Oppgave 4a:\n",
    "Skriv en funksjon som kvantiserer et bilde eller sekvens fra flyttallsrepresentasjon i $[0,1]$ til heltall med bitlengde $b$. \n",
    "- Du trenger ikke representere tallet med korrekt antall biter i datatypen, siden ikke alle bitlengder har en egen datatype. \n",
    "- I stedet bruker vi metoden `seq.astype(np.int64)` som midlertidig representerer tallet med 64 biters presisjon.\n",
    "\n",
    "#### Oppgave 4b:\n",
    "Skriv en funksjon som kvantiserer samt regner ut entropien til et array (en sekvens eller bilde).\n",
    "\n",
    "#### Oppgave 4c:\n",
    "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)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1da1633-0493-41f8-bd6d-5c5feec0152f",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bd72c6e-53fc-44ef-ac50-b8e1177a067d",
   "metadata": {},
   "source": [
    "### Oppgave 5:\n",
    "\n",
    "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?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6fe1e3c6-68ce-4b3d-a90f-f5f38927e3ed",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ff86e6f-5dde-442a-a0c9-e593169883ca",
   "metadata": {},
   "source": [
    "### Oppgave 6:\n",
    "\n",
    "#### Oppgave 6a:\n",
    "Skriv en funksjon som dekomponerer et kvantisert bilde i bitplan, og plott planene for bitdybde 8.\n",
    "\n",
    "#### Oppgave 6b:\n",
    "Skriv en funksjon som konverterer til gråkode. Bruk dekomponeringsfunksjonen til å visualisere bitplanene til gråkoden og sammenlikn med resultatet i oppgave 6a.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8a946bff-636e-4eeb-b633-4daae9b3ad7d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cc1da43-3d82-431c-89b7-233c4b03b0d3",
   "metadata": {},
   "source": [
    "### Oppgave 7:\n",
    "\n",
    "Til slutt skal vi implementere Huffman koding. Fra forelesningen husker vi algoritmen:\n",
    "1. Konstruer enkeltnode Huffman-trær med hvert av de $n$ symbolene $s_i$ med tilhørende vekt $f(s_i)$.\n",
    "2. Repeter følgende til vi ender opp med ett enkelt tre:\n",
    "    - Velg to trær $T_0$ og $T_1$ med minimal vekt. \n",
    "    - Erstatt $T_0$ og $T_1$ med et nytt tre som har $T_0$ som venstre subtre og $T_1$ som høyre subtre.\n",
    "\n",
    "#### Tips:\n",
    "- Bruk av `np.unique(arr, return_counts=True)` er veldig lurt å bruke for å hente symboler og frekvenser.\n",
    "- `heapq` modulen i Python kan med hell benyttes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e6832bf9-b836-496f-a2c8-9092d2d4b886",
   "metadata": {},
   "outputs": [],
   "source": [
    "..."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}