ML0120EN-2.1-Review-Understanding_Convolutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href=\"https://www.bigdatauniversity.com\"><img src = \"https://ibm.box.com/shared/static/jvcqp2iy2jlx2b32rmzdt0tx8lvxgzkp.png\" width = 300, align = \"center\"></a>\n",
    "\n",
    "<h1 align=center><font size = 5> UNDERSTANDING CONVOLUTIONS</font></h1>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lesson\n",
    "In this lesson, we will learn more about the key concepts behind the CNNs (Convolutional Neural Networks from now on).\n",
    "This lesson is not intended to be a reference for _machine learning, deep learning, convolutions or TensorFlow_. The intention is to give notions to the user about these fields. \n",
    "\n",
    "### Audience\n",
    "- Data scientists. General public related to computer science and machine learning.\n",
    "\n",
    "- Readers interested on TensorFlow and in need of a cloud platform like Workbench Data Scientist.\n",
    "\n",
    "### Pre-requisites:\n",
    "Basic knowledge of linear algebra, Python, Neural Networks and TensorFlow."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Table of contents\n",
    "\n",
    "<div class=\"alert alert-block alert-info\" style=\"margin-top: 20px\">\n",
    "<font size = 3><strong>Clik on the links to see the sections:</strong></font>\n",
    "<br>\n",
    "- <p><a href=\"#ref1\">Analogies</a></p>\n",
    "- <p><a href=\"#ref2\">Understanding and coding with Python</a></p>\n",
    "- <p><a href=\"#ref3\">Coding with TensorFlow</a></p>\n",
    "- <p><a href=\"#ref4\">Convolution applied on images</a></p>\n",
    "- <p><a href=\"#ref5\">Conclusion</a></p>\n",
    "<p></p>\n",
    "</div>\n",
    "<br>\n",
    "\n",
    "\n",
    "----------------\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"ref1\"></a>\n",
    "# Analogies\n",
    "\n",
    "There are several ways to understand Convolutional Layers without using a mathematical approach. We are going to explore some of the ideas proposed by the Machine Learning community.\n",
    "\n",
    "### Instances of Neurons\n",
    "\n",
    "When you start to learn a programming language, one of the first phases of your development is the learning and application of functions. Instead of rewriting pieces of code everytime that you would, a good student is encouraged to code using functional programming, keeping the code organized, clear and concise.\n",
    "CNNs can be thought of as a simplification of what is really going on, a special kind of neural network which uses identical copies of the same neuron. These copies include the same parameters (shared weights and biases) and activation functions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Location and type of connections\n",
    "\n",
    "In a fully connected layer NN, each neuron is connected to every neuron in the previous layer, and each connection has it's own weight. This is a totally general purpose connection pattern and makes no assumptions about the features in the input data thus not using any advantage that the knowledge of the data being used can bring. These types of layers are also very expensive in terms of memory and computation.\n",
    "\n",
    "In contrast, in a convolutional layer each neuron is only connected to a few nearby local neurons in the previous layer, and the same set of weights is used to connect to them. For example, in the following image, the neurons in the h1 layer are connected only to some input units (pixels).\n",
    "      \n",
    "<img src=\"https://ibm.box.com/shared/static/mev168hepixnmc9zhh4hsr3t2ks3rpcc.png\" alt=\"HTML5 Icon\" style=\"width:500px;height:500px;\">\n",
    "<center> A figure presented in one of Lecun's papers. It shows the spatial relation and how the connections are modified until the output layer<a> [[ref]](http://help.sketchup.com/en) </a> </center> \n",
    "\n",
    "\n",
    "      \n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Feature Learning\n",
    "\n",
    "Feature engineering is the process of extracting useful patterns from input data that will help the prediction model to understand better the real nature of the problem. A good feature learning will present patterns in a way that increase significantly the accuracy and performance of the applied machine learning algorithms in a way that would be impossible or too expensive by the machine learning itself.\n",
    "\n",
    "Feature learning algorithms find the common patterns that are important to distinguish between the wanted classes and extract them automatically. After this process, they are ready to be used in a classification or regression problem. \n",
    "\n",
    "The great advantage of CNNs is that they are uncommonly good at finding features in images that grow after each level, resulting in high-level features in the end. The final layers (can be one or more) use all these generated features for classification or regression. \n",
    "\n",
    "Basically, Convolutional Neural Networks are your best friend today to __automatically do Feature Engineering__ (Feature Learning) without wasting too much time creating your own codes and with no need of expertise in the field of Feature Engineering.\n",
    "\n",
    "<img src=\"https://ibm.box.com/shared/static/urzzkc7o5loqrlezcvn4kr594mxi9ftx.png\" alt=\"HTML5 Icon\" style=\"width:650px;height:250px;\">\n",
    "<center> Example of feature learning (automatically feature engineering), starting with simple features and ending with high-level features like human faces. <a> [[ref]](https://devblogs.nvidia.com/parallelforall/deep-learning-nutshell-core-concepts/) </a> </center> \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Image Filter\n",
    "\n",
    "__How to create a convolved freature from an image ?__  \n",
    "The image below is a 8x8 matrix of an image's pixels, converted to binary values in the next image(left), where 1 means a white pixel and 0 a black pixel. Later we will find out that typically this is a normalization, these values can actually have different scales. The most commmon usage is values between 0 and 255 for 8-bit grayscale images.  \n",
    "\n",
    "<img src=\"https://ibm.box.com/shared/static/0s5v7doe2p5xuzifs47bxmmuwrn3kra2.bmp\" alt=\"HTML5 Icon\" style=\"width:200px;height:200px;\">\n",
    "<center> An example of a low resolution image to be recognized. <a> [[ref]](http://help.sketchup.com/en) </a> </center> \n",
    "\n",
    "In the below image, with an animation, you can see how the two-dimensional convolution operation would operate on the images. This operation is performed in most of the Deep Learning frameworks in their first phase. We need a sliding windows to create the convolved matrix:\n",
    "\n",
    "$\n",
    "kernel=\n",
    "\\begin{bmatrix}\n",
    "     1          & 0      & 1     \\\\\n",
    "     0          & 1    & 0     \\\\\n",
    "     1          & 0    & 1\n",
    "\\end{bmatrix}\n",
    "\\\\\n",
    "$ \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "The sliding window (a.k.a kernel, filter or feature detector) with a preset calculation ([[x1, x0,x1], [x0,x1,x0], [x1,x0,x1]]) goes through the image and creates a new matrix (feature map)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " <img src=\"https://ibm.box.com/shared/static/fvutcm8jwa5j2o7xv2zzqyz2yu3zwhz4.gif\" alt=\"HTML5 Icon\" style=\"width:450px;height:300px;\">\n",
    "<center>  Animations showing how a kernel interact with a matrix representing an image. <a> [[ref]](http://cs231n.github.io/convolutional-networks/) </a> </center>  \n",
    " \n",
    " \n",
    "In the example above we used a 3×3 filter (5x5 could also be used, but would be too complex). The values from the filter were multiplied element-wise with the original matrix (input image), then summed up. To get the full convolved matrix, the algorithm keep repeating this small procedure for each element by sliding the filter over the whole original matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://ibm.box.com/shared/static/7maczejdeej0qoz3pzkysw0y8qb70g2h.png\" alt=\"HTML5 Icon\" style=\"width:500px;height:200px;\"> \n",
    "<center>  Illustration of the operation for one position of the kernel. <a> [[ref]](http://colah.github.io/posts/2014-07-Understanding-Convolutions/) </a> </center>\n",
    "\n",
    "Just like the referenced example, we can think of a one-dimensional convolution as sliding function (1x1 or 1x2 filter) multiplying and adding on top of an array (1 dimensional array, instead of the original matrix).  \n",
    " \n",
    "__What is the output of applying a kernel on an image?__   \n",
    "The famous GIMP (Open Source Image Editor) has an explanation about the convolution operation applied to images that can help us understand how Neural Networks will interact with this tool."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://ibm.box.com/shared/static/wixvbo9pk0f6r6ln879ah9jjo0ua0fo5.png\" alt=\"HTML5 Icon\" style=\"width:700px;height:350px;\"> \n",
    "<center>   Applying the left kernel to the image will result into a blurr effect.<a> [[ref]](http://colah.github.io/posts/2014-07-Understanding-Convolutions/) </a> </center>\n",
    "\n",
    "\n",
    "Well, this is very good if you want nice effects for your social media photos, but in the field of computer vision you need detailed patterns (remember feature learning) that are almost erased using a kernel like that. A more suitable example would be the Kernel/filter that shows edges from photos (the first recognizable feature of an image).\n",
    "\n",
    "\n",
    "__Lets try another kernel: __  \n",
    "Taking the values −1 and 1 on two adjacent pixels and zero everywhere else for the kernel, result in the following image. That is, we subtract two adjacent pixels. When side by side pixels are similar, this gives us approximately zero. On edges, however, adjacent pixels are very different in the direction perpendicular to the edge. Knowing that results distant from zero will result in brighter pixels, you can already guess the result of this type of kernel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://ibm.box.com/shared/static/z673yijcsfqs5rd8auc1dwmtkejyizv0.png\" alt=\"HTML5 Icon\" style=\"width:700px;height:350px;\">\n",
    "<center> Applying the new left kernel to the image will result into a edge detection, this output is normallly useful for the initial layers of a CNN.<a> [[ref]](http://colah.github.io/posts/2014-07-Understanding-Convolutions/) </a> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"ref2\"></a>\n",
    "# Understanding and coding with Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Convolution: 1D operation with Python (Numpy/Scipy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mathematical notation\n",
    "In this first example, we will use the pure mathematical notation. Here we have a one dimensional convolution operation. Lets say h is our image and x is our kernel: \n",
    "  \n",
    "x[i] = { 3, 4, 5 }  \n",
    "h[i] = { 2, 1, 0 }  \n",
    "\n",
    "where i = index\n",
    "\n",
    "To use the convolution operation between the two arrays try the code below to see how it's easy to do in Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "h = [2,1,0]\n",
    "x = [3,4,5]\n",
    " \n",
    "\n",
    "y = np.convolve(x,h)\n",
    "y  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "sliding x window over h:   \n",
    "- 6  = 2\\*3  \n",
    "- 11 = 1\\*3 + 2\\*4  \n",
    "- 14 = 0\\*3 + 1\\*4 + 2\\*5  \n",
    "- 5  = 0\\*4 + 1\\*5  \n",
    "- 0  = 0\\*5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Now we are going to verify what Python did, because we don't trust computer outputs while we are learning. Using the equation of convolution for y[n]: \n",
    "  \n",
    "$$y[n] = \\sum x[k] \\cdot h[n-k] $$\n",
    "\n",
    "\n",
    "And then, executing manually the computation:\n",
    "\n",
    "$ \n",
    "y[0]= \\sum\\limits_{k\\to\\infty}^\\infty x[k]\\cdot h[0-k]= x[0]\\cdot h[0]=3\\cdot 2=6 \\\\\n",
    "y[1]= \\sum\\limits_{k\\to\\infty}^\\infty x[k]\\cdot h[1-k]= x[0]\\cdot h[1-0]+x[1]\\cdot h[1-1] + \\space... \\\\ \n",
    "\\qquad\\qquad\\qquad\\qquad\\qquad   = x[0]\\cdot h[1] + x[1]\\cdot h[0]= 3\\cdot1+4\\cdot 2=11 \\\\\n",
    "y[2]= \\sum\\limits_{k\\to\\infty}^\\infty x[k]\\cdot h[2-k]= x[0]\\cdot h[2-0]+x[1]\\cdot h[2-1]+x[2]\\cdot h[2-2]+ \\space ... \\\\ \n",
    "\\qquad\\qquad\\qquad\\qquad\\qquad   = x[0]\\cdot h[2] + x[1]\\cdot h[1]+x[2]\\cdot h[0]= 3\\cdot0+4\\cdot 1 +5\\cdot 2=14 \\\\\n",
    "y[3]= \\sum\\limits_{k\\to\\infty}^\\infty x[k]\\cdot h[3-k]= x[0]\\cdot h[3-0]+x[1]\\cdot h[3-1]+x[2]\\cdot h[3-2]+ x[3]\\cdot h[3-3] + \\space... \\\\ \n",
    "\\qquad\\qquad\\qquad\\qquad\\qquad   = x[0]\\cdot h[3] +x[1]\\cdot h[2]\\cdot + x[2]\\cdot h[1]+x[3]\\cdot h[0]=0+0+5 \\cdot 1 +0=5 \\\\\n",
    "y[4]= \\sum\\limits_{k\\to\\infty}^\\infty x[k]\\cdot h[4-k]= x[0]\\cdot h[4-0]+x[1]\\cdot h[4-1]+x[2]\\cdot h[4-2]+\\space... =0\\\\ \n",
    "$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print(\"Compare with the following values from Python: y[0] = {0} ; y[1] = {1}; y[2] = {2}; y[3] = {3}; y[4] = {4}\".format(y[0],y[1],y[2],y[3],y[4])) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are three methods to apply kernel on the matrix, __with padding (full)__, __with padding(same)__ and __without padding(valid)__:  \n",
    "\n",
    "### 1) Visually understanding the operation with padding (full)\n",
    "\n",
    "Lets think of the kernel as a sliding window. We have to come with the solution of padding zeros on the input array. Ths is a very famous implementation and will be easier to show how it works with a simple example, consider this case:\n",
    "  \n",
    "x[i] = [6,2]  \n",
    "h[i] = [1,2,5,4]  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the zero padding, we can calculate the convolution.\n",
    " \n",
    "You have to invert the filter x, otherwise the operation would be cross-correlation.\n",
    "First step, (now with zero padding): "
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "[2  6]\n",
    " |  |\n",
    " V  V\n",
    " 0 [1 2 5 4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "= 2 \\* 0 + 6 * 1 = 6 \n",
    " \n",
    "Second step:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "  [2  6]  \n",
    "   |  |  \n",
    "   V  V  \n",
    "0 [1  2  5  4]  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "= 2 \\* 1 + 6 * 2 = 14 (the arrows represent the connection between the kernel and the input)\n",
    "\n",
    "Third step:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "     [2  6]  \n",
    "      |  |  \n",
    "      V  V  \n",
    "0 [1  2  5  4]  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "= 2 \\* 2 + 6 * 5 = 34  \n",
    "  \n",
    "Fourth step:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "        [2  6]\n",
    "         |  |\n",
    "         V  V\n",
    "0 [1  2  5  4]  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "= 2 \\* 5 + 6 * 4 = 34\n",
    "\n",
    "Fifth step:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "           [2  6]\n",
    "            |  |\n",
    "            V  V\n",
    "0 [1  2  5  4] 0  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "= 2 \\* 4 + 6 * 0 = 8\n",
    " \n",
    "The result of the convolution for this case, listing all the steps, would then be: Y = [6 14 34 34 8]\n",
    "\n",
    "Below we verify with numpy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "x= [6,2]\n",
    "h= [1,2,5,4]\n",
    "\n",
    "y= np.convolve(x,h,\"full\")  #now, because of the zero padding, the final dimension of the array is bigger\n",
    "y  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2) Visually understanding the operation with \"same\"\n",
    "In this approach, we just add the zero to left (and top of the matrix in 2D). That is, only the first 4 steps of \"full\" method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "x= [6,2]\n",
    "h= [1,2,5,4]\n",
    "\n",
    "y= np.convolve(x,h,\"same\")  #it is same as zero padding, but withgenerates same \n",
    "y  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3) Visually understanding the operation with no padding (valid)\n",
    "\n",
    "In the last case we only applied the kernel when we had a compatible position on the h array, in some cases you want a dimensionality reduction. For this purpose, we simple ignore the steps tha would need padding:\n",
    "    \n",
    "x[i] = [6 2] \n",
    "h[i] = [1 2 5 4]\n",
    "\n",
    "You have to invert the filter x, otherwise the operation would be cross-correlation.\n",
    "First step, (now without zero padding):"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "[2  6]  \n",
    " |  |  \n",
    " V  V  \n",
    "[1  2  5  4]  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "= 2 \\* 1 + 6 * 2 = 14 (the arrows represent the connection between the kernel and the input)\n",
    "\n",
    "Second step: "
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "   [2  6]  \n",
    "    |  |   \n",
    "    V  V  \n",
    "[1  2  5  4]  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "= 2 \\* 2 + 6 * 5 = 34  \n",
    "  \n",
    "Third step:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "      [2  6]\n",
    "       |  |\n",
    "       V  V\n",
    "[1  2  5  4]  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "= 2 \\* 5 + 6 * 4 = 34\n",
    "\n",
    "The result of the convolution for this mode would then be Y= [14 34 34] = [ First, second, third step]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's verify with numpy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "x= [6,2]\n",
    "h= [1,2,5,4]\n",
    "\n",
    "y= np.convolve(x,h,\"valid\")  #we will understand why we used the argument valid in the next example\n",
    "y  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Convolution: 2D operation with Python (Numpy/Scipy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The 2D convolution operation is defined as:\n",
    "\n",
    "<font size=\"4\">$$ I'= \\sum\\limits_{u,v} I(x-u,y-v)g(u,v) $$ </font> \n",
    " \n",
    " \n",
    "Below we will apply the equation to an image represented by a 3x3 matrix according to the function g = (-1 1). Please note that when we apply the kernel we always use its inversion. \n",
    " \n",
    "$\n",
    "I=\n",
    "\\begin{bmatrix}\n",
    "     255          & 7      & 3     \\\\\n",
    "     212          & 240    & 4     \\\\\n",
    "     218          & 216    & 230\n",
    "\\end{bmatrix}\n",
    "\\\\\n",
    "$ \n",
    "\n",
    "$\n",
    "g=\n",
    "\\begin{bmatrix}\n",
    "     -1          & 1      \n",
    "\\end{bmatrix}\n",
    "\\\\\n",
    "$ \n",
    "  \n",
    "$\n",
    "\\begin{bmatrix}\n",
    "    \\textbf{1}\\cdot \\textbf{0}      & \\textbf{-1} \\ast \\textbf{255}  & 7      & 3     \\\\\n",
    "    0              & 212          & 240    & 4     \\\\\n",
    "    0              & 218          & 216    & 230\n",
    "\\end{bmatrix}\n",
    "\\rightarrow\n",
    "\\begin{bmatrix}\n",
    "    \\textbf{-255}  & 7      & 3     \\\\\n",
    "    212            & 240    & 4     \\\\\n",
    "    218            & 216    & 230\n",
    "\\end{bmatrix}\n",
    "\\\\\n",
    "$\n",
    "\n",
    "$\n",
    "\\begin{bmatrix}\n",
    "    \\textbf{1}\\ast \\textbf{255}      & \\textbf{-1} \\ast \\textbf{7}  & 3    \\\\\n",
    "    212          & 240    & 4     \\\\\n",
    "    218          & 216    & 230\n",
    "\\end{bmatrix}\n",
    "\\rightarrow\n",
    "\\begin{bmatrix}\n",
    "    -255           & \\textbf{248}      & 3     \\\\\n",
    "    212            & 240    & 4     \\\\\n",
    "    218            & 216    & 230\n",
    "\\end{bmatrix}\n",
    "\\\\\n",
    "$\n",
    "\n",
    "$\n",
    "\\begin{bmatrix}\n",
    "    255          & \\textbf{1}\\ast\\textbf{7}  & \\textbf{-1}\\ast\\textbf{3}    \\\\\n",
    "    212          & 240    & 4     \\\\\n",
    "    218          & 216    & 230\n",
    "\\end{bmatrix}\n",
    "\\rightarrow\n",
    "\\begin{bmatrix}\n",
    "    -255           & 248      & \\textbf{4}     \\\\\n",
    "    212            & 240      & 4     \\\\\n",
    "    218            & 216      & 230\n",
    "\\end{bmatrix}\n",
    "\\\\\n",
    "$\n",
    "\n",
    "  \n",
    "$\n",
    "\\begin{bmatrix}\n",
    "    0              & 255          & 7          & 3     \\\\\n",
    "    \\textbf{1}\\ast \\textbf{0}    & \\textbf{-1} \\ast \\textbf{212}  & 240     & 4     \\\\\n",
    "    0              & 218          & 216    & 230\n",
    "\\end{bmatrix}\n",
    "\\rightarrow\n",
    "\\begin{bmatrix}\n",
    "    \\textbf{-255}  & 248    & 4     \\\\\n",
    "    -212            & 240    & 4     \\\\\n",
    "    218            & 216    & 230\n",
    "\\end{bmatrix}\n",
    "\\\\\n",
    "$\n",
    " \n",
    " \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We don't have to finish the calculations, we have the computer at our side. So, let's see what is the code to proceede with this operation: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from scipy import signal as sg\n",
    "\n",
    "I= [[255,   7,  3],\n",
    "    [212, 240,  4],\n",
    "    [218, 216, 230],]\n",
    "\n",
    "g= [[-1,1]]\n",
    "\n",
    "print ('Without zero padding \\n')\n",
    "print ('{0} \\n'.format(sg.convolve( I, g, 'valid')))\n",
    "# The 'valid' argument states that the output consists only of those elements \n",
    "# that do not rely on the zero-padding.\n",
    "\n",
    "print ('With zero padding \\n')\n",
    "print (sg.convolve( I, g))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a more difficult case where h= [ [-1  1] , [2   3] ]\n",
    "\n",
    "$\n",
    "\\begin{bmatrix}\n",
    "    \\textbf{3}\\ast \\textbf{0}      & \\textbf{2} \\ast \\textbf{0}     & 0      & 0     \\\\\n",
    "    \\textbf{1}\\ast \\textbf{0}      & \\textbf{-1} \\ast \\textbf{255}  & 7      & 3     \\\\\n",
    "    0              & 212          & 240    & 4     \\\\\n",
    "    0              & 218          & 216    & 230\n",
    "\\end{bmatrix}\n",
    "\\rightarrow\n",
    "\\begin{bmatrix}\n",
    "    \\textbf{-255}  & 7      & 3     \\\\\n",
    "    212            & 240    & 4     \\\\\n",
    "    218            & 216    & 230\n",
    "\\end{bmatrix}\n",
    "\\\\\n",
    "$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from scipy import signal as sg\n",
    "\n",
    "I= [[255,   7,  3],\n",
    "    [212, 240,  4],\n",
    "    [218, 216, 230],]\n",
    "\n",
    "g= [[-1,  1],\n",
    "    [ 2,  3],]\n",
    "\n",
    "print ('With zero padding \\n')\n",
    "print ('{0} \\n'.format(sg.convolve( I, g, 'full')))\n",
    "# The output is the full discrete linear convolution of the inputs. \n",
    "# It will use zero to complete the input matrix\n",
    "\n",
    "print ('With zero padding_same_ \\n')\n",
    "print ('{0} \\n'.format(sg.convolve( I, g, 'same')))\n",
    "# The output is the full discrete linear convolution of the inputs. \n",
    "# It will use zero to complete the input matrix\n",
    "\n",
    "\n",
    "print ('Without zero padding \\n')\n",
    "print (sg.convolve( I, g, 'valid'))\n",
    "# The 'valid' argument states that the output consists only of those elements \n",
    "#that do not rely on the zero-padding."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----------------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"ref3\"></a>\n",
    "# Coding with TensorFlow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Numpy is great because it has high optmized matrix operations implemented in a backend using C/C++. However, if our goal is to work with DeepLearning, we need much more. TensorFlow does the same work, but instead of returning to Python everytime, it creates all the operations in the form of graphs and execute them once with the highly optimized backend.\n",
    "\n",
    "Suppose that you have two tensors:\n",
    "\n",
    "* 3x3 filter (4D tensor = [3,3,1,1] = [width, height, channels, number of filters])\n",
    "* 10x10 image (4D tensor = [1,10,10,1] = [batch size, width, height, number of channels]\n",
    "\n",
    "The output size for zero padding 'SAME' mode will be:  \n",
    "* the same as input = 10x10  \n",
    "\n",
    "The output size without zero padding 'VALID' mode:  \n",
    "* input size - kernel dimension +1 = 10 -3 + 1 = 8 = 8x8 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import tensorflow as tf\n",
    "\n",
    "#Building graph\n",
    "\n",
    "input = tf.Variable(tf.random_normal([1,10,10,1]))\n",
    "filter = tf.Variable(tf.random_normal([3,3,1,1]))\n",
    "op = tf.nn.conv2d(input, filter, strides=[1, 1, 1, 1], padding='VALID')\n",
    "op2 = tf.nn.conv2d(input, filter, strides=[1, 1, 1, 1], padding='SAME')\n",
    "\n",
    "#Initialization and session\n",
    "init = tf.global_variables_initializer()\n",
    "with tf.Session() as sess:\n",
    "    sess.run(init)\n",
    "\n",
    "    print(\"Input \\n\")\n",
    "    print('{0} \\n'.format(input.eval()))\n",
    "    print(\"Filter/Kernel \\n\")\n",
    "    print('{0} \\n'.format(filter.eval()))\n",
    "    print(\"Result/Feature Map with valid positions \\n\")\n",
    "    result = sess.run(op)\n",
    "    print(result)\n",
    "    print('\\n')\n",
    "    print(\"Result/Feature Map with padding \\n\")\n",
    "    result2 = sess.run(op2)\n",
    "    print(result2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----------------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"ref4\"></a>\n",
    "# Convolution applied on images"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Upload your own image (drag and drop to this window) and type its name on the input field on the next cell (press _shift + enter_). The result of this pre-processing will be an image with only a greyscale channel.\n",
    "\n",
    "You can type _bird.jpg_ to use a default image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# download standard image\n",
    "!wget --quiet https://ibm.box.com/shared/static/cn7yt7z10j8rx6um1v9seagpgmzzxnlz.jpg --output-document bird.jpg\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "\n",
    "#Importing\n",
    "import numpy as np\n",
    "from scipy import signal\n",
    "from scipy import misc\n",
    "import matplotlib.pyplot as plt\n",
    "from PIL import Image\n",
    "\n",
    "im = Image.open('bird.jpg')  # type here your image's name\n",
    "\n",
    "# uses the ITU-R 601-2 Luma transform (there are several \n",
    "# ways to convert an image to grey scale)\n",
    "\n",
    "image_gr = im.convert(\"L\")    \n",
    "print(\"\\n Original type: %r \\n\\n\" % image_gr)\n",
    "\n",
    "# convert image to a matrix with values from 0 to 255 (uint8) \n",
    "arr = np.asarray(image_gr) \n",
    "print(\"After conversion to numerical representation: \\n\\n %r\" % arr) \n",
    "### Activating matplotlib for Ipython\n",
    "%matplotlib inline\n",
    "\n",
    "### Plot image\n",
    "\n",
    "imgplot = plt.imshow(arr)\n",
    "imgplot.set_cmap('gray')  #you can experiment different colormaps (Greys,winter,autumn)\n",
    "print(\"\\n Input image converted to gray scale: \\n\")\n",
    "plt.show(imgplot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we will experiment using an edge detector kernel."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "kernel = np.array([\n",
    "                        [ 0, 1, 0],\n",
    "                        [ 1,-4, 1],\n",
    "                        [ 0, 1, 0],\n",
    "                                     ]) \n",
    "\n",
    "grad = signal.convolve2d(arr, kernel, mode='same', boundary='symm')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "print('GRADIENT MAGNITUDE - Feature map')\n",
    "\n",
    "fig, aux = plt.subplots(figsize=(10, 10))\n",
    "aux.imshow(np.absolute(grad), cmap='gray')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we change the kernel and start to analyse the outputs we would be acting as a CNN. The difference is that a Neural Network do all this work automatically (the kernel adjustment using different weights). In addition, we can understand how biases affect the behaviour of feature maps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Please note that when you are dealing with most of the real applications of CNNs, you usually convert the pixels values to a range from 0 to 1. This process is called normalization._"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "type(grad)\n",
    "\n",
    "grad_biases = np.absolute(grad) + 100\n",
    "\n",
    "grad_biases[grad_biases > 255] = 255\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "print('GRADIENT MAGNITUDE - Feature map')\n",
    "\n",
    "fig, aux = plt.subplots(figsize=(10, 10))\n",
    "aux.imshow(np.absolute(grad_biases), cmap='gray')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"ref5\"></a>\n",
    "# Conclusion\n",
    "\n",
    "This understanding of how convolutions work are the foundation of how Convolutional Neural Networks work. After this tuorial you are supposed to understand the underlying mathematical concepts and how to apply them using| Python (numpy) and Tensorflow. The next setp is to extrapolate this knowledge to Machine Learning applications."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Want to learn more?\n",
    "\n",
    "Running deep learning programs usually needs a high performance platform. PowerAI speeds up deep learning and AI. Built on IBM's Power Systems, PowerAI is a scalable software platform that accelerates deep learning and AI with blazing performance for individual users or enterprises. The PowerAI platform supports popular machine learning libraries and dependencies including Tensorflow, Caffe, Torch, and Theano. You can download a [free version of PowerAI](https://cocl.us/ML0120EN_PAI).\n",
    "\n",
    "Also, you can use Data Science Experience to run these notebooks faster with bigger datasets. Data Science Experience is IBM's leading cloud solution for data scientists, built by data scientists. With Jupyter notebooks, RStudio, Apache Spark and popular libraries pre-packaged in the cloud, DSX enables data scientists to collaborate on their projects without having to install anything. Join the fast-growing community of DSX users today with a free account at [Data Science Experience](https://cocl.us/ML0120EN_DSX)This is the end of this lesson. Hopefully, now you have a deeper and intuitive understanding regarding the LSTM model. Thank you for reading this notebook, and good luck on your studies."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Thanks for completing this lesson!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Created by <a href = \"https://linkedin.com/in/luisotsm\"> Luis O. Silveira Martins</a> ,  <a href = \"https://linkedin.com/in/erich-natsubori-sato\">Erich Natsubori Sato </a></h4> , <a href = \"https://linkedin.com/in/saeedaghabozorgi\"> Saeed Aghabozorgi </a></h4>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# REFERENCES"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://github.com/joanbruna/stat212b/blob/master/lec1.pdf  \n",
    "http://deeplearning.stanford.edu/wiki/index.php/Feature_extraction_using_convolution  \n",
    "http://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm  "
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.6.5"
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}