{ "metadata": { "name": "" }, "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}\n", "F_{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", "\n", "Assume you have a procedure that can compute all coefficients $G_{k}$, $k=0,\\ldots, N-1$\n", "efficiently, 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}\n", "How 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\n", "symmetry constraint:\n", "\\begin{equation}\n", " f_{-n} = f_n \\qquad \\mbox{for $n=1,\\ldots, N-1$}\n", "\\end{equation}\n", "\n", "a) 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", "\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", "collapsed": false, "input": [ "# write your code here" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 1 }, { "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.\n", "Divide the dataset $f_n$ of length $2N$ into a dataset $g_n := f_{2n}$, containing all values with\n", "an even index, and a dataset $h_n := f_{2n-1}$, with all values with odd index.\n", "Which symmetries can be found in $g_n$ and $h_n$? Of which kind (Cosine/Sine\n", "Transformation, DFT with real data) are the according DFTs of length $N$? Which symmetries can be found\n", "if the dataset $f_n$ fulfills the following symmetry constraint:\n", "\n", "\\begin{equation}\n", " f_{-n} = f_{n+1}.\n", "\\end{equation}" ] } ], "metadata": {} } ] }