{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Discrete Cosine Transform"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 1: 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",
"$$\\begin{equation}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",
"\\end{equation}$$\n",
"\n",
"where \n",
"\n",
"$$\\begin{equation}\n",
"c_{u;v} = \\begin{cases} \\frac{1}{\\sqrt{2}} & u;v = 0 \\\\ 1 & \\text{otherwise.}\\end{cases}\n",
"\\end{equation}$$\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 2: 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",
"\\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}\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}\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",
" \\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",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# write your code here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 3: Fast Discrete Cosine Transform"
]
},
{
"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": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.6"
}
},
"nbformat": 4,
"nbformat_minor": 0
}