{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format = 'retina'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Image filtering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Image filtering theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Filtering is one of the most basic and common image operations in image processing. You can filter an image to remove noise or to enhance features; the filtered image could be the desired result or just a preprocessing step. Regardless, filtering is an important topic to understand."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Local filtering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "plt.rcParams['image.cmap'] = 'gray'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The \"local\" in local filtering simply means that a pixel is adjusted by values in some surrounding neighborhood. These surrounding elements are identified or weighted based on a \"footprint\", \"structuring element\", or \"kernel\".\n",
    "\n",
    "Let's go to back to basics and look at a 1D step-signal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "step_signal = np.zeros(100)\n",
    "step_signal[50:] = 1\n",
    "fig, ax = plt.subplots()\n",
    "ax.plot(step_signal)\n",
    "ax.margins(y=0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Now add some noise to this signal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# Just to make sure we all see the same results\n",
    "np.random.seed(0)\n",
    "\n",
    "\n",
    "noisy_signal = (step_signal\n",
    "                + np.random.normal(0, 0.35, step_signal.shape))\n",
    "fig, ax = plt.subplots()\n",
    "ax.plot(noisy_signal);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The simplest way to recover something that looks a bit more like the original signal is to take the average between neighboring \"pixels\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# Take the mean of neighboring pixels\n",
    "smooth_signal = (noisy_signal[:-1] + noisy_signal[1:]) / 2.0\n",
    "fig, ax = plt.subplots()\n",
    "ax.plot(smooth_signal);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What happens if we want to take the *three* neighboring pixels? We can do the same thing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "smooth_signal3 = (noisy_signal[:-2] + noisy_signal[1:-1]\n",
    "                  + noisy_signal[2:]) / 3\n",
    "fig, ax = plt.subplots()\n",
    "ax.plot(smooth_signal, label='mean of 2')\n",
    "ax.plot(smooth_signal3, label='mean of 3')\n",
    "ax.legend(loc='upper left');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "For averages of more points, the expression keeps getting hairier. And you have to worry more about what's going on in the margins. Is there a better way?\n",
    "\n",
    "It turns out there is. This same concept, nearest-neighbor averages, can be expressed as a *convolution* with an *averaging kernel*. Note that the operation we did with `smooth_signal3` can be expressed as follows:\n",
    "\n",
    "* Create an output array called `smooth_signal3`, of the same length as `noisy_signal`.\n",
    "* At each element in `smooth_signal3` starting at point 1, and ending at point -2, place the average of the sum of: 1/3 of the element to the left of it in `noisy_signal`, 1/3 of the element at the same position, and 1/3 of the element to the right.\n",
    "* discard the leftmost and rightmost elements.\n",
    "\n",
    "This is called a *convolution* between the input image and the array `[1/3, 1/3, 1/3]`. (We'll give a more in-depth explanation of convolution in the next section)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# Same as above, using a convolution kernel\n",
    "# Neighboring pixels multiplied by 1/3 and summed\n",
    "mean_kernel3 = np.full((3,), 1/3)\n",
    "smooth_signal3p = np.convolve(noisy_signal, mean_kernel3,\n",
    "                              mode='valid')\n",
    "fig, ax = plt.subplots()\n",
    "ax.plot(smooth_signal3p)\n",
    "\n",
    "print('smooth_signal3 and smooth_signal3p are equal:',\n",
    "      np.allclose(smooth_signal3, smooth_signal3p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def convolve_demo(signal, kernel):\n",
    "    ksize = len(kernel)\n",
    "    convolved = np.correlate(signal, kernel)\n",
    "    def filter_step(i):\n",
    "        fig, ax = plt.subplots()\n",
    "        ax.plot(signal, label='signal')\n",
    "        ax.plot(convolved[:i+1], label='convolved')\n",
    "        ax.legend()\n",
    "        ax.scatter(np.arange(i, i+ksize),\n",
    "                   signal[i : i+ksize])\n",
    "        ax.scatter(i, convolved[i])\n",
    "    return filter_step\n",
    "\n",
    "from ipywidgets import interact, widgets\n",
    "\n",
    "i_slider = widgets.IntSlider(min=0, max=len(noisy_signal) - 3,\n",
    "                             value=0)\n",
    "\n",
    "interact(convolve_demo(noisy_signal, mean_kernel3),\n",
    "         i=i_slider);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The advantage of convolution is that it's just as easy to take the average of 11 points as 3:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mean_kernel11 = np.full((11,), 1/11)\n",
    "smooth_signal11 = np.convolve(noisy_signal, mean_kernel11,\n",
    "                              mode='valid')\n",
    "fig, ax = plt.subplots()\n",
    "ax.plot(smooth_signal11);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "i_slider = widgets.IntSlider(min=0, max=len(noisy_signal) - 11,\n",
    "                             value=0)\n",
    "\n",
    "interact(convolve_demo(noisy_signal, mean_kernel11),\n",
    "         i=i_slider);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, to take the mean of 11 values, we have to move further and further away from the edges, and this starts to be noticeable. You can use `mode='same'` to pad the edges of the array and compute a result of the same size as the input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "smooth_signal3same = np.convolve(noisy_signal, mean_kernel3,\n",
    "                                 mode='same')\n",
    "smooth_signal11same = np.convolve(noisy_signal, mean_kernel11,\n",
    "                                  mode='same')\n",
    "\n",
    "fig, ax = plt.subplots(1, 2)\n",
    "ax[0].plot(smooth_signal3p)\n",
    "ax[0].plot(smooth_signal11)\n",
    "ax[0].set_title('mode=valid')\n",
    "ax[1].plot(smooth_signal3same)\n",
    "ax[1].plot(smooth_signal11same)\n",
    "ax[1].set_title('mode=same');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But now we see edge effects on the ends of the signal...\n",
    "\n",
    "This is because `mode='same'` actually pads the signal with 0s and then applies `mode='valid'` as before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def convolve_demo_same(signal, kernel):\n",
    "    ksize = len(kernel)\n",
    "    padded_signal = np.pad(signal, ksize // 2,\n",
    "                           mode='constant')\n",
    "    convolved = np.correlate(padded_signal, kernel)\n",
    "    def filter_step(i):\n",
    "        fig, ax = plt.subplots()\n",
    "        x = np.arange(-ksize // 2,\n",
    "                      len(signal) + ksize // 2)\n",
    "        ax.plot(signal, label='signal')\n",
    "        ax.plot(convolved[:i+1], label='convolved')\n",
    "        ax.legend()\n",
    "        start, stop = i, i + ksize\n",
    "        ax.scatter(x[start:stop]+1,\n",
    "                   padded_signal[start : stop])\n",
    "        ax.scatter(i, convolved[i])\n",
    "        ax.set_xlim(-ksize // 2,\n",
    "                    len(signal) + ksize // 2)\n",
    "    return filter_step\n",
    "\n",
    "\n",
    "i_slider = widgets.IntSlider(min=0, max=len(noisy_signal)-1,\n",
    "                             value=0)\n",
    "\n",
    "interact(convolve_demo_same(noisy_signal, mean_kernel11),\n",
    "         i=i_slider);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise** Look up the documentation of `scipy.ndimage.convolve`. Apply the same convolution, but using a different `mode=` keyword argument to avoid the edge effects we see here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### A difference filter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Let's look again at our simplest signal, the step signal from before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "ax.plot(step_signal)\n",
    "ax.margins(y=0.1) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Can you predict what a convolution with the kernel `[-1, 0, 1]` does? Try thinking about it before running the cells below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "result_corr = np.correlate(step_signal, np.array([-1, 0, 1]),\n",
    "                           mode='valid')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "result_conv = np.convolve(step_signal, np.array([-1, 0, 1]),\n",
    "                          mode='valid')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "ax.plot(step_signal, label='signal')\n",
    "ax.plot(result_conv, linestyle='dashed', label='convolved')\n",
    "ax.plot(result_corr, linestyle='dashed', label='correlated',\n",
    "        color='C3')\n",
    "ax.legend(loc='upper left')\n",
    "ax.margins(y=0.1) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(For technical signal processing reasons, convolutions actually occur \"back to front\" between the input array and the kernel. Correlations occur in the signal order, so we'll use correlate from now on.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Whenever neighboring values are close, the filter response is close to 0. Right at the boundary of a step, we're subtracting a small value from a large value and and get a spike in the response. This spike \"identifies\" our edge."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Commutativity and assortativity of filters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What if we try the same trick with our noisy signal?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "noisy_change = np.correlate(noisy_signal, np.array([-1, 0, 1]))\n",
    "fig, ax = plt.subplots()\n",
    "ax.plot(noisy_signal, label='signal')\n",
    "ax.plot(noisy_change, linestyle='dashed', label='change')\n",
    "ax.legend(loc='upper left')\n",
    "ax.margins(0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oops! We lost our edge!\n",
    "\n",
    "But recall that we smoothed the signal a bit by taking its neighbors. Perhaps we can do the same thing here. Actually, it turns out that we can do it *in any order*, so we can create a filter that combines both the difference and the mean:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mean_diff = np.correlate([-1, 0, 1], [1/3, 1/3, 1/3], mode='full')\n",
    "print(mean_diff)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Note:* we use `np.convolve` here, because it has the option to output a *wider* result than either of the two inputs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can use this to find our edge even in a noisy signal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "smooth_change = np.correlate(noisy_signal, mean_diff,\n",
    "                             mode='same')\n",
    "fig, ax = plt.subplots()\n",
    "ax.plot(noisy_signal, label='signal')\n",
    "ax.plot(smooth_change, linestyle='dashed', label='change')\n",
    "ax.margins(0.1)\n",
    "ax.hlines([-0.5, 0.5], 0, 100, linewidth=0.5, color='gray');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** The Gaussian filter with variance $\\sigma^2$ is given by:\n",
    "\n",
    "$$\n",
    "k_i = \\frac{1}{\\sqrt{2\\pi}\\sigma}\\exp{\\left(-\\frac{(x_i - x_0)^2}{2\\sigma^2}\\right)}\n",
    "$$\n",
    "\n",
    "1. Create this filter (for example, with width 9, center 4, sigma 1). (Plot it)\n",
    "2. Convolve it with the difference filter (with appropriate mode). (Plot the result)\n",
    "3. Convolve it with the noisy signal. (Plot the result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xi = np.arange(9)\n",
    "x0 = 9 // 2  # 4\n",
    "x = xi - x0\n",
    "...  # complete this code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Local filtering of images"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Now let's apply all this knowledge to 2D images instead of a 1D signal. Let's start with an incredibly simple image:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "bright_square = np.zeros((7, 7), dtype=float)\n",
    "bright_square[2:5, 2:5] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This gives the values below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(bright_square)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "and looks like a white square centered on a black square:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "ax.imshow(bright_square);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### The mean filter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "For our first example of a filter, consider the following filtering array, which we'll call a \"mean kernel\". For each pixel, a kernel defines which neighboring pixels to consider when filtering, and how much to weight those pixels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "mean_kernel = np.full((3, 3), 1/9)\n",
    "\n",
    "print(mean_kernel)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Now, let's take our mean kernel and apply it to every pixel of the image."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Applying a (linear) filter essentially means:\n",
    "* Center a kernel on a pixel\n",
    "* Multiply the pixels *under* that kernel by the values *in* the kernel\n",
    "* Sum all the those results\n",
    "* Replace the center pixel with the summed result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This process is known as convolution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let's take a look at the numerical result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import scipy.ndimage as ndi\n",
    "\n",
    "%precision 2\n",
    "print(bright_square)\n",
    "print(ndi.correlate(bright_square, mean_kernel))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The meaning of \"mean kernel\" should be clear now: Each pixel was replaced with the mean value within the 3x3 neighborhood of that pixel. When the kernel was over `n` bright pixels, the pixel in the kernel's center was changed to n/9 (= n * 0.111). When no bright pixels were under the kernel, the result was 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This filter is a simple smoothing filter and produces two important results:\n",
    "1. The intensity of the bright pixel decreased.\n",
    "2. The intensity of the region near the bright pixel increased."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see a convolution in action.\n",
    "\n",
    "(Execute the following cell, but don't try to read it; its purpose is to generate an example.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#--------------------------------------------------------------------------\n",
    "#  Convolution Demo\n",
    "#--------------------------------------------------------------------------\n",
    "from skimage import color\n",
    "from scipy import ndimage as ndi\n",
    "from matplotlib import patches\n",
    "\n",
    "def mean_filter_demo(image, vmax=1):\n",
    "    mean_factor = 1.0 / 9.0  # This assumes a 3x3 kernel.\n",
    "    iter_kernel_and_subimage = iter_kernel(image)\n",
    "\n",
    "    image_cache = []\n",
    "\n",
    "    def mean_filter_step(i_step):\n",
    "        while i_step >= len(image_cache):\n",
    "            filtered = image if i_step == 0 else image_cache[-1][-1][-1]\n",
    "            filtered = filtered.copy()\n",
    "\n",
    "            (i, j), mask, subimage = next(iter_kernel_and_subimage)\n",
    "            filter_overlay = color.label2rgb(mask, image, bg_label=0,\n",
    "                                             colors=('cyan', 'red'))\n",
    "            filtered[i, j] = np.sum(mean_factor * subimage)\n",
    "            image_cache.append(((i, j), (filter_overlay, filtered)))\n",
    "\n",
    "        (i, j), images = image_cache[i_step]\n",
    "        fig, axes = plt.subplots(1, len(images), figsize=(10, 5))\n",
    "        \n",
    "        for ax, imc in zip(axes, images):\n",
    "            ax.imshow(imc, vmax=vmax)\n",
    "            rect = patches.Rectangle([j - 0.5, i - 0.5], 1, 1, color='yellow', fill=False)\n",
    "            ax.add_patch(rect)\n",
    "            \n",
    "        plt.show()\n",
    "    return mean_filter_step\n",
    "\n",
    "\n",
    "def mean_filter_interactive_demo(image):\n",
    "    from ipywidgets import IntSlider, interact\n",
    "    mean_filter_step = mean_filter_demo(image)\n",
    "    step_slider = IntSlider(min=0, max=image.size-1, value=0)\n",
    "    interact(mean_filter_step, i_step=step_slider)\n",
    "\n",
    "\n",
    "def iter_kernel(image, size=1):\n",
    "    \"\"\" Yield position, kernel mask, and image for each pixel in the image.\n",
    "\n",
    "    The kernel mask has a 2 at the center pixel and 1 around it. The actual\n",
    "    width of the kernel is 2*size + 1.\n",
    "    \"\"\"\n",
    "    width = 2*size + 1\n",
    "    for (i, j), pixel in iter_pixels(image):\n",
    "        mask = np.zeros(image.shape, dtype='int16')\n",
    "        mask[i, j] = 1\n",
    "        mask = ndi.grey_dilation(mask, size=width)\n",
    "        #mask[i, j] = 2\n",
    "        subimage = image[bounded_slice((i, j), image.shape[:2], size=size)]\n",
    "        yield (i, j), mask, subimage\n",
    "\n",
    "\n",
    "def iter_pixels(image):\n",
    "    \"\"\" Yield pixel position (row, column) and pixel intensity. \"\"\"\n",
    "    height, width = image.shape[:2]\n",
    "    for i in range(height):\n",
    "        for j in range(width):\n",
    "            yield (i, j), image[i, j]\n",
    "\n",
    "\n",
    "def bounded_slice(center, xy_max, size=1, i_min=0):\n",
    "    slices = []\n",
    "    for i, i_max in zip(center, xy_max):\n",
    "        slices.append(slice(max(i - size, i_min), min(i + size + 1, i_max)))\n",
    "    return tuple(slices)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mean_filter_interactive_demo(bright_square)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Incidentally, the above filtering is the exact same principle behind the *convolutional neural networks*, or CNNs, that you might have heard much about over the past few years. The only difference is that while above, the simple mean kernel is used, in CNNs, the values inside the kernel are *learned* to find a specific feature, or accomplish a specific task. Time permitting, we'll demonstrate this in an exercise at the end of the notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Slight aside:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "outputs": [],
   "source": [
    "print(np.sum(mean_kernel))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Note that all the values of the kernel sum to 1. Why might that be important?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Downsampled image"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Let's consider a real image now. It'll be easier to see some of the filtering we're doing if we downsample the image a bit. We can slice into the image using the \"step\" argument to sub-sample it (don't scale images using this method for real work; use `skimage.transform.rescale`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from skimage import data\n",
    "\n",
    "image = data.camera()\n",
    "pixelated = image[::10, ::10]\n",
    "fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(10, 5))\n",
    "ax0.imshow(image)\n",
    "ax1.imshow(pixelated) ;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Here we use a step of 10, giving us every tenth column and every tenth row of the original image. You can see the highly pixelated result on the right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are actually going to be using the pattern of plotting multiple images side by side quite often, so we are going to make the following helper function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from skimage import img_as_float\n",
    "\n",
    "def imshow_all(*images, titles=None):\n",
    "    images = [img_as_float(img) for img in images]\n",
    "\n",
    "    if titles is None:\n",
    "        titles = [''] * len(images)\n",
    "    vmin = min(map(np.min, images))\n",
    "    vmax = max(map(np.max, images))\n",
    "    ncols = len(images)\n",
    "    height = 5\n",
    "    width = height * len(images)\n",
    "    fig, axes = plt.subplots(nrows=1, ncols=ncols,\n",
    "                             figsize=(width, height))\n",
    "    for ax, img, label in zip(axes.ravel(), images, titles):\n",
    "        ax.imshow(img, vmin=vmin, vmax=vmax)\n",
    "        ax.set_title(label)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Mean filter on a real image"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Now we can apply the filter to this downsampled image:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "filtered = ndi.correlate(pixelated, mean_kernel)\n",
    "imshow_all(pixelated, filtered, titles=['pixelated', 'mean filtered'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Comparing the filtered image to the pixelated image, we can see that this filtered result is smoother: Sharp edges (which are just borders between dark and bright pixels) are smoothed because dark pixels reduce the intensity of neighboring pixels and bright pixels do the opposite."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Essential filters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "If you read through the last section, you're already familiar with the essential concepts of image filtering. But, of course, you don't have to create custom filter kernels for all of your filtering needs. There are many standard filter kernels pre-defined from half a century of image and signal processing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Gaussian filter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The classic image filter is the Gaussian filter. This is similar to the mean filter, in that it tends to smooth images. The Gaussian filter, however, doesn't weight all values in the neighborhood equally. Instead, pixels closer to the center are weighted more than those farther away."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "outputs": [],
   "source": [
    "# Rename module so we don't shadow the builtin function\n",
    "from skimage import filters\n",
    "\n",
    "smooth_mean = ndi.correlate(bright_square, mean_kernel)\n",
    "sigma = 1\n",
    "smooth = filters.gaussian(bright_square, sigma)\n",
    "imshow_all(bright_square, smooth_mean, smooth,\n",
    "           titles=['original', 'result of mean filter', 'result of gaussian filter'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "For the Gaussian filter, `sigma`, the standard deviation, defines the size of the neighborhood.\n",
    "\n",
    "For a real image, we get the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from skimage import img_as_float\n",
    "# The Gaussian filter returns a float image, regardless of input.\n",
    "# Cast to float so the images have comparable intensity ranges.\n",
    "pixelated_float = img_as_float(pixelated)\n",
    "smooth = filters.gaussian(pixelated_float, sigma=1)\n",
    "imshow_all(pixelated_float, smooth)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This doesn't look drastically different than the mean filter, but the Gaussian filter is typically preferred because of the distance-dependent weighting, and because it does not have any sharp transitions (consider what happens in the Fourier domain!). For a more detailed image and a larger filter, you can see artifacts in the mean filter since it doesn't take distance into account:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "size = 20\n",
    "structuring_element = np.ones((3*size, 3*size))\n",
    "smooth_mean = filters.rank.mean(image, structuring_element)\n",
    "smooth_gaussian = filters.gaussian(image, size)\n",
    "titles = ['mean', 'gaussian']\n",
    "imshow_all(smooth_mean, smooth_gaussian, titles=titles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "(Above, we've tweaked the size of the structuring element used for the mean filter and the standard deviation of the Gaussian filter to produce an approximately equal amount of smoothing in the two results.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Incidentally, for reference, let's have a look at what the Gaussian filter actually looks like. Technically, the value of the kernel at a pixel that is $r$ rows and $c$ cols from the center is:\n",
    "\n",
    "$$\n",
    "k_{r, c} = \\frac{1}{2\\pi \\sigma^2} \\exp{\\left(-\\frac{r^2 + c^2}{2\\sigma^2}\\right)}\n",
    "$$\n",
    "\n",
    "Practically speaking, this value is pretty close to zero for values more than $4\\sigma$ away from the center, so practical Gaussian filters are truncated at about $4\\sigma$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sidelen = 45\n",
    "sigma = (sidelen - 1) // 2 // 4\n",
    "spot = np.zeros((sidelen, sidelen), dtype=float)\n",
    "spot[sidelen // 2, sidelen // 2] = 1\n",
    "kernel = filters.gaussian(spot, sigma=sigma)\n",
    "\n",
    "imshow_all(spot, kernel / np.max(kernel))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise** (Chapter 0 reminder!) Plot the profile of the gaussian kernel at its midpoint, i.e. the values under the line shown here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "\n",
    "ax.imshow(kernel, cmap='inferno')\n",
    "ax.vlines(22, -100, 100, color='C9')\n",
    "ax.set_ylim((sidelen - 1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "...  # add your plotting code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Basic edge filtering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "For images, edges are boundaries between light and dark values. The detection of edges can be useful on its own, or it can be used as preliminary step in other algorithms (which we'll see later)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Difference filters in 2D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "For images, you can think of an edge as points where the gradient is large in one direction. We can approximate gradients with difference filters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "vertical_kernel = np.array([\n",
    "    [-1],\n",
    "    [ 0],\n",
    "    [ 1],\n",
    "])\n",
    "\n",
    "gradient_vertical = ndi.correlate(pixelated.astype(float),\n",
    "                                  vertical_kernel)\n",
    "fig, ax = plt.subplots()\n",
    "ax.imshow(gradient_vertical);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## <span style=\"color:cornflowerblue\">Exercise:</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Add a horizontal kernel to the above example to also compute the horizontal gradient, $g_y$\n",
    "- Compute the magnitude of the image gradient at each point: $\\left|g\\right| = \\sqrt{g_x^2 + g_y^2}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "...  # add your horizontal and gradient magnitude code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Sobel edge filter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The Sobel filter, the most commonly used edge filter, should look pretty similar to what you developed above. Take a look at the vertical and horizontal components of the Sobel kernel to see how they differ from your earlier implementation:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* http://scikit-image.org/docs/dev/api/skimage.filters.html#skimage.filters.sobel_v\n",
    "* http://scikit-image.org/docs/dev/api/skimage.filters.html#skimage.filters.sobel_h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "imshow_all(bright_square, filters.sobel(bright_square))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Notice that the size of the output matches the input, and the edges aren't preferentially shifted to a corner of the image. Furthermore, the weights used in the Sobel filter produce diagonal edges with reponses that are comparable to horizontal or vertical edges.\n",
    "\n",
    "Like any derivative, noise can have a strong impact on the result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "pixelated_gradient = filters.sobel(pixelated)\n",
    "imshow_all(pixelated, pixelated_gradient)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Smoothing is often used as a preprocessing step in preparation for feature detection and image-enhancement operations because sharp features can distort results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "gradient = filters.sobel(smooth)\n",
    "titles = ['gradient before smoothing', 'gradient after smoothing']\n",
    "# Scale smoothed gradient up so they're of comparable brightness.\n",
    "imshow_all(pixelated_gradient, gradient*1.8, titles=titles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Notice how the edges look more continuous in the smoothed image."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise: the simplest neural network.** Let's pretend we have an image and a \"ground truth\" image of what we want to detect:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "target = (filters.sobel_h(image) > 0.07)\n",
    "imshow_all(image, target, titles=['source', 'target'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can we use machine learning to find a 3x3 convolutional filter that recovers this target?\n",
    "\n",
    "- use `skimage.util.view_as_windows` and `np.reshape` to view the image as a set of (approximately) `npixels` 3x3 patches. (Hint: why is it only approximate? Think of `mode=valid` convolutions.)\n",
    "- use `np.reshape` again to see it as `npixels` \"linear\" patches of 9 pixels.\n",
    "- Now you have an `(npixels, 9)` \"feature\" matrix, `X`.\n",
    "- Use slicing and `np.ravel` to get an `npixels`-length array of target values.\n",
    "- Use `sklearn.linear_model.LogisticRegression` to learn the relationship between our pixel neighborhoods (of size 9) and the target.\n",
    "- Look at your `model.coef_`. How do they compare to the Sobel coefficients?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Denoising filters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "At this point, we make a distinction. The earlier filters were implemented as a *linear dot-product* of values in the filter kernel and values in the image. The following kernels implement an *arbitrary* function of the local image neighborhood. Denoising filters in particular are filters that preserve the sharpness of edges in the image.\n",
    "\n",
    "As you can see from our earlier examples, mean and Gaussian filters smooth an image rather uniformly, including the edges of objects in an image. When denoising, however, you typically want to preserve features and just remove noise. The distinction between noise and features can, of course, be highly situation-dependent and subjective."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Median Filter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The median filter is the classic edge-preserving filter. As the name implies, this filter takes a set of pixels (i.e. the pixels within a kernel or \"structuring element\") and returns the median value within that neighborhood. Because regions near a sharp edge will have many dark values and many light values (but few values in between) the median at an edge will most likely be either light or dark, rather than some value in between. In that way, we don't end up with edges that are smoothed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from skimage.morphology import disk\n",
    "neighborhood = disk(radius=1)  # \"selem\" is often the name used for \"structuring element\"\n",
    "median = filters.rank.median(pixelated, neighborhood)\n",
    "titles = ['image', 'gaussian', 'median']\n",
    "imshow_all(pixelated, smooth, median, titles=titles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This difference is more noticeable with a more detailed image."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "neighborhood = disk(10)\n",
    "coins = data.coins()\n",
    "mean_coin = filters.rank.mean(coins, neighborhood)\n",
    "median_coin = filters.rank.median(coins, neighborhood)\n",
    "titles = ['image', 'mean', 'median']\n",
    "imshow_all(coins, mean_coin, median_coin, titles=titles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Notice how the edges of coins are preserved after using the median filter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Further reading"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "`scikit-image` also provides more sophisticated denoising filters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from skimage.restoration import denoise_tv_bregman\n",
    "denoised = denoise_tv_bregman(image, 4)\n",
    "d = disk(4)\n",
    "median = filters.rank.median(image, d)\n",
    "titles = ['image', 'median', 'denoised']\n",
    "imshow_all(image, median, denoised, titles=titles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* [Denoising examples](http://scikit-image.org/docs/dev/auto_examples/plot_denoise.html)\n",
    "* [Rank filters example](http://scikit-image.org/docs/dev/auto_examples/applications/plot_rank_filters.html)\n",
    "* [Restoration API](http://scikit-image.org/docs/stable/api/skimage.restoration.html)\n",
    "\n",
    "Take a look at this [neat feature](https://github.com/scikit-image/scikit-image/pull/2647) merged last year:\n",
    "\n",
    "![cycle spinning](../images/cycle_spin.png)"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}