{ "metadata": { "name": "Worksheet_3" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": "Discrete Cosine Transformation" }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": "Exercise 1: Two-dimensional Cosine Transformation" }, { "cell_type": "markdown", "metadata": {}, "source": "The JPEG-method computes the coefficients $F_{kl}$ from the image data $f_{nm}$ using the following formula\n\n\\begin{equation}\nF_{kl} = \\frac{1}{N\\cdot M}\n \\sum\\limits_{n=0}^{N-1} \\sum\\limits_{m=0}^{M-1} f_{nm}\n \\cos \\left( \\frac{\\pi k \\left(n + \\frac{1}{2} \\right)}{N} \\right)\n \\cos \\left( \\frac{\\pi l \\left(m + \\frac{1}{2} \\right)}{M} \\right)\n\\end{equation}\n\nAssume you have a procedure that can compute all coefficients $G_{k}$, $k=0,\\ldots, N-1$\nefficiently, according to the formula\n\\begin{equation}\n G_{k} = \\frac{1}{N}\n \\sum\\limits_{n=0}^{N-1} f_{n}\n \\cos \\left( \\frac{\\pi k \\left(n + \\frac{1}{2} \\right)}{N} \\right).\n\\end{equation}\nHow can you compute the coefficients $\\widetilde{F}_{kl}$ using this procedure?" }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": "Exercise 2: Discrete Cosine Transformation" }, { "cell_type": "markdown", "metadata": {}, "source": "We start with a dataset $f_{-N+1}, \\ldots, f_N$, which fulfills the following\nsymmetry constraint:\n\\begin{equation}\n f_{-n} = f_n \\qquad \\mbox{for $n=1,\\ldots, N-1$}\n\\end{equation}\n\na) Show that the corresponding Fourier coefficients\n \\begin{equation} \\label{eq:dft}\n F_k = \\frac{1}{2N}\n \\sum\\limits_{n=-N+1}^{N} f_n \\omega_{2N}^{-kn}\n \\end{equation}\n are real values only and can be written as:\n\n \\begin{equation} \\label{eq:dct}\n F_k = \\frac{1}{N} \\left(\n \\frac{1}{2} f_0\n + \\sum\\limits_{n=1}^{N-1} f_n \\cos\\left( \\frac{\\pi nk}{N} \\right)\n + \\frac{1}{2} f_N \\cos(\\pi k)\n \\right).\n \\end{equation}\n\nb) Show that the $F_k$ is symmetric too.\n\nc)\nLet $FFT(f,N)$ be a procedure that computes the coefficients $F_k$\nefficiently (according to dft equation from a field $f$\nwhich consists of $2N$ values $f_n$. (The result is written back to field $f$)\n\nWrite a short procedure $DCT(g,N)$ which uses procedure $FFT$\nto 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", "collapsed": false, "input": "from scipy.fftpack import *\n\ndef naive_dct(g):\n f = g + g[-2:0:-1]\n print \"f = \" + str(f)\n F = fft(f)\n return F[:len(g)]\n #return F\n\ng = [0.0, -1.0, 2.0, 4.0, 5.0, 6.0]\n\nprint \"naive_dct: \" + str(naive_dct(g).real)\nprint \"dct : \" + str(dct(g, type=1))\n", "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": "f = [0.0, -1.0, 2.0, 4.0, 5.0, 6.0, 5.0, 4.0, 2.0, -1.0]\nnaive_dct: [ 26. -16.94427191 -1.23606798 0.94427191 3.23606798 2. ]\ndct : [ 26. -16.94427191 -1.23606798 0.94427191 3.23606798 2. ]\n" } ], "prompt_number": 12 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": "Exercise 3: Fast Discrete Cosine Transformation" }, { "cell_type": "markdown", "metadata": {}, "source": "Formulate the butterfly scheme for dft equation from exercise 1.\nDivide the dataset $f_n$ of length $2N$ into a dataset $g_n := f_{2n}$, containing all values with\nan even index, and a dataset $h_n := f_{2n-1}$, with all values with odd index.\nWhich symmetries can be found in $g_n$ and $h_n$? Of which kind (Cosine/Sine\nTransformation, DFT with real data) are the according DFTs of length $N$? Which symmetries can be found\nif the dataset $f_n$ fulfills the following symmetry constraint:\n\n\\begin{equation}\n f_{-n} = f_{n+1}.\n\\end{equation}" } ], "metadata": {} } ] }