2.0-tl-image-filter.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Excercise 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Import packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import scipy.ndimage\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "import skimage.io\n",
    "import skimage.color\n",
    "import skimage.exposure\n",
    "\n",
    "import time\n",
    "import math\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1\n",
    "(2 points)\n",
    "1. Use $f = loss(100)$ which creates a 1D array that mimics a loss curve of some neural network.\n",
    "2. Implement the naive $\\mathcal{O}(n w)$ mean filter to smooth the loss.\n",
    "3. Implement the improved $\\mathcal{O}(n)$ mean filter to smooth the loss.\n",
    "4. Show all three curves in a single plot with a legend.\n",
    "5. Compare the runtime between the naive and improved implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1.\n",
    "def loss(n):    \n",
    "    return 1.0 / (0.01 * (np.arange(0, n) + 1)) + 3.0 * np.random.uniform(-1.00, 1.00, n)\n",
    "\n",
    "# TODO: generate f with loss helper function\n",
    "\n",
    "\n",
    "# 2.\n",
    "def naive_running_mean(f, w):\n",
    "    '''\n",
    "    Apply the naive running mean filter and return the smoothed values.\n",
    "\n",
    "    f -- contains the values\n",
    "    w -- window size\n",
    "    '''\n",
    "    \n",
    "    return g\n",
    "\n",
    "# 3.\n",
    "def improved_running_mean(f, w):\n",
    "    '''\n",
    "    Apply the improved running mean filter and return the smoothed values.\n",
    "\n",
    "    f -- contains the values\n",
    "    w -- window size\n",
    "    '''\n",
    "    \n",
    "    return g\n",
    "\n",
    "# 4.\n",
    "ws = 5\n",
    "\n",
    "# TODO: Plot all three curves in a single plot\n",
    "\n",
    "\n",
    "# 5.\n",
    "\n",
    "# TODO: Measure and print the runtime of both methods in Milliseconds\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2\n",
    "(4 points)\n",
    "1. Create numpy arrays for the horizontal and vertical Sobel kernel.\n",
    "$$\n",
    "S_x =\\begin{bmatrix}\n",
    "-1 & -2 & -1 \\\\\n",
    "0 & 0 & 0 \\\\\n",
    "1 & 2 & 1\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "S_y =\\begin{bmatrix}\n",
    "-1 & 0 & 1 \\\\\n",
    "-2 & 0 & 2 \\\\\n",
    "-1 & 0 & 1\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "2. Implement the $\\textit{convolve}$ function with four nested loops.\n",
    "3. Load the image from the last exercise and detect its edges using the Sobel kernels and the $\\textit{convolve}$ function.\n",
    "4. Implement the 1D $\\textit{convolve_fast}$ function. Apply the seperated Sobel operators $u$ and $v$. Plot the result together with $\\textit{convolve(S_x)}$ and compare the runtime.\n",
    "5. Implement a function that seperates a 2D kernel into 2 1D kernels.\n",
    "6. (Bonus) Use the function for a gaussian blur kernel and apply it on the image."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1\n",
    "# TODO Create S_x and S_y\n",
    "\n",
    "\n",
    "print('Horizontal Sobel kernel:\\n', S_x)\n",
    "print('Vertical Sobel kernel:\\n', S_y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2\n",
    "def convolve(arr, ker):\n",
    "    '''\n",
    "    Convolve the array using kernel K with four nested for loops.\n",
    "    \n",
    "    arr -- 2D array that gets convolved\n",
    "    ker   -- kernel\n",
    "    '''\n",
    "    \n",
    "    return arr_conv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 3\n",
    "# TODO: load ./data/pepo.jpg as a grayscale image\n",
    "\n",
    "\n",
    "# TODO: Use the Sobel filter for edge detection:\n",
    "#       Compute the Gradient Magnitude using both Sobel kernels\n",
    "\n",
    "\n",
    "# Show results\n",
    "_, axis = plt.subplots(1, 2)\n",
    "axis[0].imshow(image, cmap='gray')\n",
    "axis[1].imshow(edges,cmap='gray')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 4\n",
    "u = np.array([[1], [2], [1]])\n",
    "v = np.array([[-1, 0, 1]])\n",
    "S_x = np.dot(u, v)\n",
    "print('u   =\\n', u)\n",
    "print('v   =\\n', v)\n",
    "print('S_x =\\n', S_x)\n",
    "\n",
    "def convolve_fast(arr, K_u, K_v):\n",
    "    '''\n",
    "    Convolve the array using kernel K_u and K_v.\n",
    "    \n",
    "    arr -- 2D array that gets convolved\n",
    "    K_u -- kernel u\n",
    "    K_v -- kernel v\n",
    "    '''\n",
    "\n",
    "    return g\n",
    "\n",
    "# TODO: Run both methods and compare their runtime\n",
    "\n",
    "\n",
    "# Show results\n",
    "_, axis = plt.subplots(1, 2)\n",
    "axis[0].imshow(edges_naive, cmap='gray')\n",
    "axis[1].imshow(edges_improved,cmap='gray')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 5\n",
    "print('rank of s_x:', np.linalg.matrix_rank(S_x))\n",
    "print('rank of s_y:', np.linalg.matrix_rank(S_y))\n",
    "\n",
    "def separate(K):\n",
    "    '''\n",
    "    Seperate the 2D kernel into 2 1D kernels.\n",
    "    \n",
    "    K -- 2D kernel\n",
    "    '''\n",
    "    \n",
    "    return K_u, K_v\n",
    "\n",
    "K_u, K_v = separate(S_x)\n",
    "print('K_u =\\n', K_u)\n",
    "print('K_v =\\n', K_v)\n",
    "print('K   =\\n', np.dot(K_u, K_v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 6 Bonus\n",
    "def gaussian_kernel(kernel_size, sigma):\n",
    "    '''\n",
    "    Return a 2D gaussian kernel.\n",
    "    \n",
    "    kernel_size -- size of the kernel\n",
    "    sigma       -- sigma of the gaussian blur\n",
    "    '''\n",
    "   \n",
    "    return h\n",
    "\n",
    "K = gaussian_kernel(15, 15)\n",
    "\n",
    "K_u, K_v = separate(K)\n",
    "\n",
    "# TODO: Run both methods and compare their runtime\n",
    "\n",
    "# Plot the results\n",
    "_, axis = plt.subplots(1, 2)\n",
    "axis[0].imshow(conv_x_naive, cmap='gray')\n",
    "axis[1].imshow(conv_x_improved,cmap='gray')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 3\n",
    "(4 points)\n",
    "\n",
    "1. Implement the naive max function using nested loops.\n",
    "2. Implement the $\\mathcal{O}(n log w)$ faster max function using a binary tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#1\n",
    "def naive_max(arr, ws):\n",
    "    '''\n",
    "    Return the maximum-filtered array\n",
    "    \n",
    "    arr -- 2D array\n",
    "    ws -- window size\n",
    "    '''\n",
    "    \n",
    "    return g\n",
    "\n",
    "# Generate some random data to filter\n",
    "f = []\n",
    "for i in range(25):\n",
    "    f.append(random.randint(0, 100))\n",
    "\n",
    "print('input = ', f)\n",
    "print('naive_max =', naive_max(f, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#2\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.max = -np.inf # value of this node\n",
    "        self.top = None    # reference to parent node\n",
    "        self.left = None   # left child node\n",
    "        self.right = None  # right child node\n",
    "        \n",
    "        # HINT: this list will hold a reference to all leaf nodes that\n",
    "        #       are children of this node.\n",
    "        #       You will need later to add new and replace old values\n",
    "        #       in the tree.\n",
    "        self.elems = []    # list of all child leaf nodes\n",
    "    \n",
    "    \n",
    "    def build_tree(self, depth, top=None):\n",
    "        '''\n",
    "        Build up a tree of certain depth\n",
    "        \n",
    "        depth -- tree depth\n",
    "        top -- parent node\n",
    "        '''\n",
    "        self.top = top\n",
    "        \n",
    "        if depth > 0:\n",
    "            # TODO: recursively initialize all children\n",
    "           \n",
    "            \n",
    "            # TODO: concatenate elems lists of children\n",
    "            # HINT: nodes that are not leafes should not be added\n",
    "            #       to self.elems\n",
    "            \n",
    "        \n",
    "        else:\n",
    "            # TODO: this is a leaf node\n",
    "            # HINT: this node has to be added to the elems list\n",
    "            \n",
    "        \n",
    "        return self.elems\n",
    "    \n",
    "    \n",
    "    def update(self):\n",
    "        '''\n",
    "        Update the value (self.max) of this node\n",
    "        and its parent nodes recursively\n",
    "        '''\n",
    "        \n",
    "        pass\n",
    "\n",
    "\n",
    "class MaxTree:\n",
    "    def __init__(self, ws):\n",
    "        '''\n",
    "        ws -- window size\n",
    "        '''\n",
    "        # TODO: compute number of leafes and tree depth (length = 2 * ws + 1)\n",
    "        \n",
    "        \n",
    "        # TODO: initialize root node \n",
    "        \n",
    "        \n",
    "        # init pointer to next element to be replaced\n",
    "        self.ptr = 0\n",
    "        \n",
    "    def replace_elem(self, value):\n",
    "        '''\n",
    "        Replace an element (value of leaf node) in the tree\n",
    "\n",
    "        value -- value of new element\n",
    "        '''\n",
    "        # HINT: use self.ptr as a pointer to the next\n",
    "        #       element that has to be replaced\n",
    "        \n",
    "        pass\n",
    "\n",
    "    \n",
    "    def get_max(self):\n",
    "        return self.root.max\n",
    "\n",
    "tree = MaxTree(3)\n",
    "\n",
    "def fast_max(arr, ws):\n",
    "    '''\n",
    "    Return the maximum-filtered array\n",
    "    \n",
    "    arr -- 2D array\n",
    "    ws -- window size\n",
    "    '''\n",
    "    max_arr = []\n",
    "    \n",
    "    # TODO: initialize tree\n",
    "    \n",
    "    \n",
    "    # TODO: compute maximum-filtered output array\n",
    "    \n",
    "    \n",
    "    return max_arr\n",
    "\n",
    "\n",
    "print('input = ', f)\n",
    "print('fast_max =', fast_max(f, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now use your implementation to filter an image with different window sizes.\n",
    "Note, that for small windows, the naive method is indeed faster due to the lower overhead.\n",
    "However, as it has a much better time complexity, the tree method is much faster for large windows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Nothing to do here ;)\n",
    "def image_max(arr, ws, method):\n",
    "    '''\n",
    "    Apply a max-filter to an image\n",
    "    \n",
    "    arr -- input image\n",
    "    ws -- window size\n",
    "    method -- filter function\n",
    "    '''\n",
    "    out = np.zeros_like(arr)\n",
    "    \n",
    "    for y in range(arr.shape[0]):\n",
    "        out[y] = method(arr[y], ws)\n",
    "    \n",
    "    for x in range(arr.shape[1]):\n",
    "        out[:, x] = method(out[:, x], ws)\n",
    "    \n",
    "    \n",
    "    return out\n",
    "\n",
    "for ws in [2, 4, 8, 16, 32]:\n",
    "    print('\\nFilter with window size {}'.format(ws))\n",
    "    start_time = time.time()\n",
    "    max_img_naive = image_max(image, ws, naive_max)\n",
    "    naive_time = time.time() - start_time\n",
    "    print('Naive implementation took {:.3f} ms'.format(1000 * naive_time))\n",
    "\n",
    "    start_time = time.time()\n",
    "    max_img_improved = image_max(image, ws, fast_max)\n",
    "    improved_time = time.time() - start_time\n",
    "    print('Improved implementation took {:.3f} ms'.format(1000 * improved_time))\n",
    "\n",
    "    _, axis = plt.subplots(1, 2)\n",
    "    axis[0].imshow(max_img_naive, cmap='gray')\n",
    "    axis[1].imshow(max_img_improved,cmap='gray')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}