Chapter 5 - Image Filtering.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "# Chapter 5 - Image Filtering\n",
    "\n",
    "In this chapter, we're introducing the concept of Image Filtering. \n",
    "Filters can be applied on 2D Image data either for various applications. We can broadly differenciate low-pass filters smooth images\n",
    "(retrain low-frequenciy components) and high-pass filters (retain contours / edges, e.g. high frequencies). \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "## Low-pass filters\n",
    "Low pass filters are typically applied to reduce noise in images. Noise can be seen as random artifacts in an image. \n",
    "For example, salt & pepper noise describes the random occurrence of black / white pixels in the image, while\n",
    "gaussian noise is a random increase/decrease in each pixel’s color value, following a gaussian distribution.\n",
    "\n",
    "![Different noise types](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/1_different_noise_types.png)\n",
    "*Figure 1: Different noise types. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "Low-pass filters assume that the pixel variation in the image should be lower than perceived, e.g. pixels should have a\n",
    "color value close to their neighbours. Low-pass filters therefore replace each pixels value with an average of the values in \n",
    "the pixels neighbourhood. The neighbours can either be weighted based on their distance to the center pixel, or equally. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "Moving a filter over all possible positions in an image is called a *convolution*, the filter is called a *Kernel* or *Mask* \n",
    "and denoted *H*. \n",
    "When convoluting a filter over an image, we flip the kernel by 180° before performing at each position before computing the weighted \n",
    "average between the filter values and the pixel. If we do not flip the kernel, we speak of a cross-correlation instead of a convolution.\n",
    "For symmetric filters like \"Gaussian Filter\" or \"Median Filter\", a convolution and a cross-correlation will of course produce\n",
    "the same results. \n",
    "\n",
    "![Convolution vs. Cross-corelation formula](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/3_convolution_vs_cross-correlation.png)\n",
    "*Figure 2: Convolution vs. Cross-corelation formula. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "In the following example, a smoothing averaging filter is applied to a 1D signal, bringing the neighbouring values significantly closer together and reducing outliers.\n",
    "\n",
    "![Filter example, p. 15](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/2_smoothed_signal.png)\n",
    "*Figure 3: World Coordinates -> Pixel Coordinates. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "The same principle can be applied to 2D Data like images. In the following example, a 2D Filter with size 1/1 averages a neighbourhood of 9 pixels, overwriting the central pixel with an equally weighted average of all 9 pixels. \n",
    "Such a filter is called a \"box\" filter.\n",
    "\n",
    "![Box filter](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/4_before_filtering_image_with_box_filter.png)\n",
    "*Figure 4: Illustration of a box filter over a black image with a white square. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*\n",
    "\n",
    "The output is - of course - a blurred version of the very same image.\n",
    "\n",
    "![Box filter output](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/5_after_filtering_image_with_box_filter.png)\n",
    "*Figure 5: Output of a smoothed image using a box-filter. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "While the box filter smoothens an image quite well, it produces horizontal and vertical aftifacts since the filter itself has\n",
    "sharp edges. These artifacts are also called \"aliasing\" and is caused by the high frequency components of the box filter.\n",
    "A better way to smooth an image is with a gaussian filter, a filter implementing the 2D gaussian function. \n",
    "For perfect results, take a large gaussian filters with smooth edges, e.g. low standard derivation that ensures that the outermost\n",
    "values of the filter are close to 1 while preserving a smooth derivative. \n",
    "\n",
    "![Gaussian filter visualization](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/7_gaussian_filter_comparison.png)\n",
    "*Figure 6: Gaussian filter visualization. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*\n",
    "\n",
    "![Gaussian Filter comparison, p. 26](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/17_gaussian_filter_comparison.png)\n",
    "*Figure 7: Gaussian Filter comparison. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "When we apply any filter on an image, the question remains how to deal with the image boundary. Since - in most cases - we don't\n",
    "want the resulting image to be smaller than the input image, we have to simulate additional boundary pixels. \n",
    "There are different strategies with varying results, like zero-padding (surrounding black pixels), wrap-around (repeating the image),\n",
    "copy-edge (always use outermost pixel values) or reflect accross edge (mirroring around edge, gives best results). \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "### Non-linear Low-pass filters\n",
    "\n",
    "Gaussian filters or box-filters do not denoise salt & pepper noise since they get influenced by outliers by a high degree. \n",
    "That's where **median filters** come into play. They can not be interpreted as a classical convolution filter like a Gaussian\n",
    "filter, it rather takes the median pixel value from the neighbourhood. The median filter is therefore much less influenced\n",
    "by strong noise, while he also preserves edges much better than the linear smoothing filters. \n",
    "\n",
    "![Gaussian Filter comparison, p. 26](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/8_median_filtered_image.png)\n",
    "*Figure 8: Median Filter removing Salt & Pepper Noise. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "Another such filter is the **billateral filter**. It acts like a median filter with preserving edges even more by adapting the kernel\n",
    "locally to the intensitiy profile of the underlaying image. They only average pixels with similar brightness: Pixels that fall below\n",
    "a brightness difference compared to the center pixel. \n",
    "\n",
    "![Bilateral filer with mask, p. 26](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/9_billateral_filter_demonstration.png)\n",
    "*Figure 9: Bilateral filer with mask. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*\n",
    "\n",
    "The extend to which neighbouring pixels have to be similar to the central pixel is controlled via a factor *sigma*.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "## High-pass filters\n",
    "\n",
    "High-pass filters are mainly used for edge detection since react to sharp change in pixel intensity. Edges are sharp changes in\n",
    "an image functions intensity value. Applying the first derivative on an image would leave us with an image where sharp edges \n",
    "are shown. \n",
    "\n",
    "![Image derivative detecting edges](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/10_image_first_derivative_demonstration.png)\n",
    "*Figure 10: Image derivative detecting edges. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*\n",
    "\n",
    "We therefore construct a filter that acts like a derivative by approximating the image derivative \n",
    "*dI(x,y) / dx ~ I(x+1, y) - I(x,y)* and *dI(x,y) / dy ~ I(x, y+1) - I(x,y)*. \n",
    "So we essentially compare each pixel to its direct neighbour and take the difference as an output. \n",
    "\n",
    "![Partial derivative filter](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/11_partial_derivative_filters.png)\n",
    "*Figure 11: Partial derivative filter. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "More advanced filters are larger in size and therefore produce less artifacts. The sobel-filter is an example for a larger\n",
    "derivative filter:\n",
    "\n",
    "![Prewitt & Sobel filter](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/12_prewitt_sobel_filter.png)\n",
    "*Figure 12: Prewitt & Sobel filter. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*\n",
    "\n",
    "The direction of the edge can be determined by calculating the pixel regions gradient, so the diretion of fastest intensity change.\n",
    "The gradient direction is given by *angle = arctan2(dI/dx, dI/dy)*, so the two dimensional arcus tangens of the image derivative\n",
    "values. The edge strenght is given by the gradients magnitude: *strength = sqrt((dI/dx)^2 + (dI/dy)^2).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "A big problem for high-pass filters is gaussian noise: there will always be a steep difference between two neighbouring pixels, caused\n",
    "by normal gaussian noise produced by the image sensor. It is therefore best practice to softly filter the image first with a \n",
    "gaussian filter before applying a high-pass filter. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "In the following graphic, we see the original image I, the kernel H, the resulting image when H is applied I*H as well as the derrived\n",
    "image d(I*H)/dx\n",
    "\n",
    "![Process steps for edge detection](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/13_individual_processing_steps_for_edge_detection.png)\n",
    "*Figure 13: Process steps for edge detection. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*\n",
    "\n",
    "A way better approach is to directly include the smoothing in the filter itself, giving us the filter dH/dx as seen in\n",
    "the following image:\n",
    "\n",
    "![Gaussian smoothing within a derivative filter](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/14_gaussian_smoothing_and_derivative_filter.png)\n",
    "*Figure 13: Gaussian smoothing within a derivative filter. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "This is called a \"derivative of gaussian\" filter: it multiplies a normal gaussian filters with a high-pass 2x1 derivative filter. \n",
    "\n",
    "![Difference of Gaussians filter](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/15_difference_of_gaussians_filter.png)\n",
    "*Figure 14: Difference of Gaussians filter. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "Since we deal with two partial derivatives, we'd need to filter the image twice. A solution to this is given by the \n",
    "\"Laplacian of Gaussian\"-Filter, which finds the derivative in all directions simultaniously. It is constructed by\n",
    "subtracting a smaller radius gaussian Filter from a large radius gaussian filter.\n",
    "\n",
    "![Laplacian of Gaussian](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/18_laplacian_of_gaussian.png)\n",
    "*Figure 15: Laplacian of Gaussian. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "metadata": false
    }
   },
   "source": [
    "## Canny edge detection\n",
    "\n",
    "Canny edge detection uses partial gaussian derivative filters to find all corners in an image. It then sets all pixelsvalues to 0 that\n",
    "fall under a given threshold. Finally, Canny takes the local maximum of any corner along the gradient direction, e.g. it only\n",
    "takes the peak of a wide edge. \n",
    "\n",
    "![Canny edge detection](https://github.com/joelbarmettlerUZH/PyVisualOdometry/raw/master/img/chapter_5/16_canny_edge_detection.png)\n",
    "*Figure 16: Canny edge detection. [source](http://rpg.ifi.uzh.ch/docs/teaching/2019/04_filtering.pdf)*\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Overview summary\n",
    "\n",
    "Let me quickly illustrate the main differences of Smoothing and Derivaitve filters.\n",
    "\n",
    "Smoothing filters always contain positive filter values that sum to 1 to preserve the overall brightness of constant regions. They are constructed to remove high-frequency components. \n",
    "\n",
    "In contrast, derivative filters have two regions with opposite signs to get a high response in regions of high contrast. Their components sum to 1 to create no response on images with constant color. They are created to highlight high-frequency, not to remove them. "
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}