{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 简介"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在如今计算机视觉领域，卷积（Convolution）可能是出现得最频繁的术语。当然这是因为卷积神经网络被广泛地用于解决多种计算机视觉任务，已经成为计算机视觉领域的一种默认的工具。但是卷积这个术语并不来自于计算机科学领域，而是来自于信号处理领域。卷积是信号处理中的一个重要操作。什么是卷积呢？顾名思义，就是先“卷”，再“积”。用专业术语来说，卷积的输入是两个函数，卷积操作先将一个函数翻转，然后将其对另一个函数进行滑动叠加，然后得到输出结果。在函数连续的情况下，叠加指的是对两个函数的乘积求积分；而在离散情况下是对函数加权求和，为简单起见我们统一称之为叠加。\n",
    "\n",
    "那么卷积这样一个操作有什么意义呢？为什么要先对输入的函数进行翻转呢？信号处理的教材通常会这样解释：卷积的结果不仅仅和当前输入的信号响应值有关，也和该信号在过去所有时刻的输入响应值有关系。这表明卷积不仅仅考虑当下的情况，也考虑过去时刻的情况，它是一种对相应效果的累积，所以有一个先“卷”再“积”的过程。这么描述仍然很抽象，我们举一个实际生活中的例子。试想你站在一个池塘边，往池塘里扔石子。扔一颗石子，池塘里就会产生水波，然后慢慢衰退，水面重新平静。这里扔石子就是输入信号，产生的水波就是对输入的响应。那么如果按一定速度不停地往池塘中扔石子呢？这种情况下，在水面上某处某一时刻的水波的大小如何计算？根据常识，我们知道当前时刻某处的水波大小不但和当前时刻扔的石子产生的水波有关，还和之前所有扔的石子产生的水波有关，是这些水波的累积结果。这便是先“卷”再“积”的过程，“卷”考虑了与当前输入相关的所有输入，而“积”则把这些输入的效果进行叠加。\n",
    "\n",
    "类似的，在图像处理中，卷积的计算是把每个像素周边相关的像素进行某种加权叠加，考虑了每个像素周边的信息，从而提取图像中的特征，这也为图像识别等计算机视觉任务打下了基础。\n",
    "\n",
    "在这一章节中，我们以一维卷积为引子，介绍卷积的数学定义与代码实现，然后推广到二维卷积。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 一维卷积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据卷积的定义，一维卷积的公式如下：\n",
    "$$f(x) * k(x) = \\int f(\\tau)k(x-\\tau)d\\tau$$\n",
    "一维卷积的输入是一个一维信号$f(x)$和一个一维卷积核$k(x)$,$f(x)$是需要被卷积的对象，$k(x)$是用来进行卷积操作的函数，卷积核的长度一般是奇数，这是为了对称而设计的。通常情况下，输入向量$f(x)$的长度远远大于卷积核$k(x)$的长度。而输出向量的长度往往是由卷积操作的填充方式决定的。\n",
    "\n",
    "<img src=\"example.jpeg\">\n",
    "\n",
    "卷积的具体操作如上图所示。我们可以得出卷积操作的计算步骤：\n",
    "1. 变换：改变输入信号的横坐标，自变量由$x$变成$\\tau$；\n",
    "2. 反转：将其中一个信号反转；\n",
    "3. 平移：反转后的信号随变量$\\tau$平移，得到$k(x-\\tau)$。若$\\tau>0$，则向右平移，反之向左平移；\n",
    "4. 相乘：将$f(\\tau)$和$k(x-\\tau)$相乘；\n",
    "5. 积分：$f(\\tau)$和$k(x-\\tau)$乘积曲线下的面积即为在$x$时刻的卷积值。\n",
    "\n",
    "OK，根据以上步骤，我们可以定义一维卷积的函数如下。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 一维卷积\n",
    "def conv(lst1, lst2):\n",
    "    l1 = len(lst1)\n",
    "    l2 = len(lst2) \n",
    "    c=[0 for x in range(0,l1+l2-1)]  \n",
    "    for i in range(0,len(c)): \n",
    "           for j in range(0,l2): \n",
    "                if (i-j)>=0 and (i-j)<=(len(c)-l2): \n",
    "                    c[i]=c[i] + lst1[i-j]*lst1[j]\n",
    "    return c\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们分别定义两个向量a和b，并计算他们的卷积："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[16, 24, 17, 70, 49, 16, 64]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [4,3,1,8]\n",
    "b = [4,3,1,8]\n",
    "conv(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了更直观的查看结果，我们分别绘制a、b与它们卷积得到的向量："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7fa2692e4b10>]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 14956 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.figure(1)\n",
    "plt.subplot(1, 2, 1) #图一包含1行2列子图，当前画在第一行第一列图上\n",
    "plt.title('a')\n",
    "plt.plot(a)\n",
    "\n",
    "plt.figure(1)\n",
    "plt.subplot(1, 2, 2)#当前画在第一行第2列图上\n",
    "plt.title('b')\n",
    "plt.plot(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7fa269453690>]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 16844 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(conv(a,b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "重新设置a与b，并绘制相应的卷积图像："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7fa26957a0d0>]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 16936 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "a = [4,3,1,8,5]\n",
    "b = [0,0,1,0,0]\n",
    "conv(a,b)\n",
    "\n",
    "plt.figure(1)\n",
    "plt.subplot(1, 2, 1) #图一包含1行2列子图，当前画在第一行第一列图上\n",
    "plt.title('a')\n",
    "plt.plot(a)\n",
    "\n",
    "plt.figure(1)\n",
    "plt.subplot(1, 2, 2)#当前画在第一行第2列图上\n",
    "plt.title('b')\n",
    "plt.plot(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7fa2695faed0>]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 16792 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(conv(a,b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "同加减乘除一样，卷积作为一种计算操作，也有如下几种性质：\n",
    "1. 交换律：$f(x) * k(x) = k(x) * f(x)$；\n",
    "2. 结合律：$[f(x) * g(x)] * k(x) = f(x) * [g(x) * k(x)]$；\n",
    "3. 分配律：$f(x) * [g(x) + k(x)] = f(x) * g(x) + f(x) * k(x)$。\n",
    "\n",
    "<!-- 4. 微分:$\\frac{d}{dx}[f(x) * k(x)] = \\frac{df(x)}{dx} * k(x) = f(x) * \\frac{dk(x)}{dx}$ -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 二维卷积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一副数字图像可以看作一个二维空间的离散函数，可以表示为$f(x, y)$。假设图像宽为a，高为b，设置卷积核k(x,y)(在某些情况下，卷积核$k(x,y)$也被称为“滤波器”)，可以得到二维卷积的公式：\n",
    "$$k(x,y) * f(x,y) = \\sum_{s=-a}^{s=a}\\sum_{t=-b}^{t=b}f(x-s,y-t)k(s,t)$$\n",
    "\n",
    "我们将卷积的概念从一维扩展到二维，其结果非常类似，只不过变成了矩阵的“卷和”操作。卷和就是离散的卷积，卷积是积分，而卷和是点与点的乘法和加法。一个二维图像 (矩阵) 同一个二维滤波器卷积的过程是这样的：\n",
    "1. 将二维滤波器对应的矩阵水平翻转，竖直翻转。\n",
    "2. 把这个滤波器矩阵，覆盖到图像上方。\n",
    "3. 将滤波器矩阵的每一个元素，同下方图像的每一个元素相乘，再把所有的乘积加起来，并不断移动这个滤波器矩阵。\n",
    "\n",
    "下图描述了二维卷积的计算过程：\n",
    "<img src='2w1.jpeg'>\n",
    "<img src='2w2.jpeg'>\n",
    "\n",
    "不难发现，由于卷积核的大小限制，我们没法直接对左上角的像素点“105”进行卷积操作。因此，在计算最边缘的一行和一列的输出结果时，我们一般对原矩阵外围补零，再进行矩阵的卷和操作。\n",
    "<img src='2w3.jpeg'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了更直观的展示卷积在图片处理上的效果，我们先导入一张图片，并将其转化为灰度照片："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-0.5, 255.5, 255.5, -0.5)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from PIL import Image\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "img = Image.open('lena.BMP')\n",
    "plt.axis(\"off\")\n",
    "plt.imshow(img)\n",
    "\n",
    "# 以灰度显示图片\n",
    "gray = img.convert('L')\n",
    "plt.figure()\n",
    "plt.imshow(gray, cmap='gray')\n",
    "plt.axis('off')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将图片转换成矩阵的形式保存："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[171, 171, 169, ..., 180, 183, 145],\n",
       "       [171, 171, 169, ..., 180, 183, 145],\n",
       "       [173, 167, 169, ..., 166, 157, 111],\n",
       "       ...,\n",
       "       [ 25,  26,  30, ...,  65,  81,  80],\n",
       "       [ 17,  24,  25, ...,  81,  93,  88],\n",
       "       [ 17,  27,  25, ...,  93,  93,  98]], dtype=uint8)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 将图片转化为numpy矩阵\n",
    "\n",
    "import numpy as np\n",
    "np.array(img)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义卷积核："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#定义卷积核（3*3）\n",
    "k = np.array([\n",
    "    [0,1,2],\n",
    "    [2,2,0],\n",
    "    [0,1,2]\n",
    "])\n",
    "\n",
    "data = np.array(img)\n",
    "n,m = data.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据二维卷积的定义，我们编写二维卷积函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义二维卷积\n",
    "def convolution(k, data):\n",
    "    n,m = data.shape\n",
    "    img_new = []\n",
    "    for i in range(n-3):\n",
    "        line = []\n",
    "        for j in range(m-3):\n",
    "            a = data[i:i+3,j:j+3]\n",
    "            line.append(np.sum(np.multiply(k, a)))\n",
    "        img_new.append(line)\n",
    "    return np.array(img_new)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将图片与卷积核进行卷积操作，并展示图片："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-0.5, 252.5, 252.5, -0.5)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 65588 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "img_new = convolution(k, data)#卷积过程\n",
    " \n",
    "#卷积结果可视化\n",
    "plt.imshow(img_new, cmap='gray')\n",
    "plt.axis('off')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "接下来我们展示另外两种不同的卷积核，并展示他们的作用："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 垂直边缘检测\n",
    "k1 = np.array([\n",
    "    [1,0,-1],\n",
    "    [1,0,-1],\n",
    "    [1,0,-1]\n",
    "])\n",
    "\n",
    "# 水平边缘检测\n",
    "k2 = np.array([\n",
    "    [1,1,1],\n",
    "    [0,0,0],\n",
    "    [-1,-1,-1]\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-0.5, 252.5, 252.5, -0.5)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 65696 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "img_new = convolution(k1, data)#卷积过程\n",
    " \n",
    "# k1卷积结果可视化\n",
    "plt.imshow(img_new, cmap='gray')\n",
    "plt.axis('off')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-0.5, 252.5, 252.5, -0.5)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 65136 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "img_new = convolution(k2, data)#卷积过程\n",
    " \n",
    "# k2卷积结果可视化\n",
    "plt.imshow(img_new, cmap='gray')\n",
    "plt.axis('off')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "除此之外，你也可以仿照上面的过程，自己动手设置卷积核，并在图片上测试。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
