{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Discrete Cosine Transform" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercise 1: Fourier Series\n", "\n", "See worksheet for figures" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercise 2: Simple JPEG Encoder" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Discrete Cosine Transform is the key to JPEG compression. Blocks of $8 \\times 8$ pixels are transformed to the frequency domain to be in a format which is more suited for compression. The code template provides you with the pixel values of the given $8 \\times 8$ block of the well-known test image \\emph{Lena}.\n", "\n", "a) In a greyscale image, the pixel values are usually encoded with 8 bit with values in $[0, 255]$. The DCT, however, works on $[-128, 127]$. Write a function that normalises the pixel values.\n", "\n", "b) The DCT transforms an $8 \\times 8$ block from the spatial domain to the frequency domain. Use\n", "\n", "$$\$$F_{uv} = \\frac{1}{\\sqrt{2N}} c_u c_v \\sum_{x=0}^{N-1} \\sum_{y=0}^{N-1} f_{xy} \\cos \\left(\\frac{(2x+1)u\\pi}{2N}\\right) \\cos \\left(\\frac{(2y+1)v\\pi}{2N}\\right)\n", "\$$$$\n", "\n", "where \n", "\n", "$$\$$\n", "c_{u;v} = \\begin{cases} \\frac{1}{\\sqrt{2}} & u;v = 0 \\\\ 1 & \\text{otherwise.}\\end{cases}\n", "\$$$$\n", "What is the complexity of your DCT routine? What is the meaning of $F_{00}$? \n", "\n", "c) The coefficients $F_{uv}$ are divided by quantisation values $Q_{uv}$ and rounded to the nearest integer. Quantisation is a lossy process; high quantisation coefficients result in a high compression factor, though at the expense of image quality. Implement the quantisation step. A common choice for the quantisation matrix is given in the code template. As mentioned in the lecture, a full JPEG encoder would now apply further compression techniques. \n", "\n", "d) Derive the IDCT and write a decoder for our simple JPEG block encoder. Compare the original image with the subsequently encoded and then decoded image.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import numpy as np\n", "from matplotlib import pyplot as plt\n", "\n", "# quantisation matrix\n", "qtable = np.matrix( [[ 16, 11, 10, 16, 24, 40, 51, 61],\n", " [ 12, 12, 14, 19, 26, 58, 60, 55],\n", " [ 14, 13, 16, 24, 40, 57, 69, 56],\n", " [ 14, 17, 22, 29, 51, 87, 80, 62],\n", " [ 18, 22, 37, 56, 68, 109, 103, 77],\n", " [ 24, 35, 55, 64, 81, 104, 113, 92],\n", " [ 49, 64, 78, 87, 103, 121, 120, 101],\n", " [ 72, 92, 95, 98, 112, 100, 103, 99]])\n", "\n", "# original 8x8 block\n", "image = np.matrix([[37, 41, 53, 68, 89, 79, 54, 68],\n", " [ 36, 28, 38, 65, 100, 94, 62, 65],\n", " [ 46, 36, 46, 66, 84, 76, 59, 78],\n", " [ 84, 67, 73, 84, 86, 73, 64, 87],\n", " [ 77, 86,116,113, 77, 57, 79, 129],\n", " [ 73, 62, 76, 74, 58, 70,109, 155],\n", " [ 82, 54, 55, 57, 63,105,154, 189],\n", " [ 121, 73, 65, 86, 126,181,203, 200]], dtype=int)\n", "\n", "\n", "plt.imshow(image, cmap='gray', interpolation='nearest', vmin=0, vmax=255)\n", "#plt.savefig('origblock8x8.jpg')\n", "plt.show()\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercise 3: Discrete Cosine Transform" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We start with a dataset $f_{-N+1}, \\ldots, f_N$, which fulfills the following\n", "symmetry constraint:\n", "\$$\n", " f_{-n} = f_n \\qquad \\mbox{for n=1,\\ldots, N-1}\n", "\$$\n", "\n", "a) Show that the corresponding Fourier coefficients\n", " $$\$$\n", " F_k = \\frac{1}{2N}\n", " \\sum\\limits_{n=-N+1}^{N} f_n \\omega_{2N}^{-kn}\n", " \$$$$\n", " are real values only and can be written as:\n", " \n", " $$\$$\n", " F_k = \\frac{1}{N} \\left( \\frac{1}{2} f_0 + \\sum\\limits_{n=1}^{N-1} f_n \\cos\\left( \\frac{\\pi nk}{N} \\right)+\\frac{1}{2} f_N \\cos(\\pi k)\\right).\n", " \$$$$\n", "\n", "b) Show that the $F_k$ is symmetric too.\n", "\n", "c)\n", "Let $FFT(f,N)$ be a procedure that computes the coefficients $F_k$\n", "efficiently (according to dft equation from a field $f$\n", "which consists of $2N$ values $f_n$. (The result is written back to field $f$)\n", "\n", "Write a short procedure $DCT(g,N)$ which uses procedure $FFT$\n", "to compute the coefficients $F_k$ for $k=0,\\ldots, N$ from dft equation for the \n", "(non-symmetrical) data $f_0,\\ldots,f_N$, stored in the parameter field\n", "$g$." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# write your code here" ] } ], "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.6.4" } }, "nbformat": 4, "nbformat_minor": 1 }