Ch08_Convolutional_Neural_Networks/Convolutions_For_Images.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Convolutions for Images\n",
    "\n",
    ":label:`chapter_conv_layer`\n",
    "\n",
    "\n",
    "Now that we understand how convolutional layers work in theory,\n",
    "we are ready to see how this works in practice.\n",
    "Since we have motivated convolutional neural networks\n",
    "by their applicability to image data,\n",
    "we will stick with image data in our examples,\n",
    "and begin by revisiting the convolutional layer\n",
    "that we introduced in the previous section.\n",
    "We note that strictly speaking, *convolutional* layers are a slight misnomer,\n",
    "since the operations are typically expressed as cross correlations.\n",
    "\n",
    "\n",
    "## The Cross-Correlation Operator\n",
    "\n",
    "In a convolutional layer, an input array\n",
    "and a correlation kernel array are combined\n",
    "to produce an output array through a cross-correlation operation.\n",
    "Let's see how this works for two dimensions.\n",
    "In our example, the input is a two-dimensional array\n",
    "with a height of 3 and width of 3.\n",
    "We mark the shape of the array as $3 \\times 3$ or (3, 3).\n",
    "The height and width of the kernel array are both 2.\n",
    "Common names for this array in the deep learning research community\n",
    "include *kernel* and *filter*.\n",
    "The shape of the kernel window (also known as the convolution window)\n",
    "is given precisely by the height and width of the kernel\n",
    "(here it is $2 \\times 2$).\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg height=\"83pt\" version=\"1.1\" viewBox=\"0 0 209 83\" width=\"209pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol id=\"glyph0-0\" overflow=\"visible\">\n",
       "<path d=\"M 1.125 0 L 1.125 -5.625 L 5.625 -5.625 L 5.625 0 Z M 1.265625 -0.140625 L 5.484375 -0.140625 L 5.484375 -5.484375 L 1.265625 -5.484375 Z M 1.265625 -0.140625 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-1\" overflow=\"visible\">\n",
       "<path d=\"M 2.90625 0 L 2.90625 -1.546875 L 0.109375 -1.546875 L 0.109375 -2.265625 L 3.046875 -6.4375 L 3.703125 -6.4375 L 3.703125 -2.265625 L 4.578125 -2.265625 L 4.578125 -1.546875 L 3.703125 -1.546875 L 3.703125 0 Z M 2.90625 -2.265625 L 2.90625 -5.171875 L 0.890625 -2.265625 Z M 2.90625 -2.265625 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-2\" overflow=\"visible\">\n",
       "<path d=\"M 0.375 -1.703125 L 1.171875 -1.8125 C 1.265625 -1.363281 1.414062 -1.039062 1.625 -0.84375 C 1.84375 -0.644531 2.113281 -0.546875 2.4375 -0.546875 C 2.800781 -0.546875 3.109375 -0.671875 3.359375 -0.921875 C 3.617188 -1.179688 3.75 -1.503906 3.75 -1.890625 C 3.75 -2.253906 3.628906 -2.550781 3.390625 -2.78125 C 3.160156 -3.019531 2.863281 -3.140625 2.5 -3.140625 C 2.34375 -3.140625 2.15625 -3.109375 1.9375 -3.046875 L 2.03125 -3.75 C 2.082031 -3.738281 2.125 -3.734375 2.15625 -3.734375 C 2.488281 -3.734375 2.789062 -3.820312 3.0625 -4 C 3.332031 -4.175781 3.46875 -4.445312 3.46875 -4.8125 C 3.46875 -5.101562 3.367188 -5.34375 3.171875 -5.53125 C 2.972656 -5.71875 2.71875 -5.8125 2.40625 -5.8125 C 2.101562 -5.8125 1.847656 -5.710938 1.640625 -5.515625 C 1.441406 -5.328125 1.3125 -5.039062 1.25 -4.65625 L 0.453125 -4.796875 C 0.554688 -5.328125 0.773438 -5.738281 1.109375 -6.03125 C 1.453125 -6.320312 1.878906 -6.46875 2.390625 -6.46875 C 2.742188 -6.46875 3.066406 -6.390625 3.359375 -6.234375 C 3.660156 -6.085938 3.890625 -5.882812 4.046875 -5.625 C 4.203125 -5.363281 4.28125 -5.085938 4.28125 -4.796875 C 4.28125 -4.515625 4.203125 -4.257812 4.046875 -4.03125 C 3.898438 -3.800781 3.679688 -3.617188 3.390625 -3.484375 C 3.773438 -3.398438 4.070312 -3.21875 4.28125 -2.9375 C 4.488281 -2.664062 4.59375 -2.320312 4.59375 -1.90625 C 4.59375 -1.34375 4.382812 -0.863281 3.96875 -0.46875 C 3.5625 -0.0820312 3.046875 0.109375 2.421875 0.109375 C 1.859375 0.109375 1.390625 -0.0546875 1.015625 -0.390625 C 0.640625 -0.722656 0.425781 -1.160156 0.375 -1.703125 Z M 0.375 -1.703125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-3\" overflow=\"visible\">\n",
       "<path d=\"M 0.421875 -5.59375 L 0.421875 -6.359375 L 4.59375 -6.359375 L 4.59375 -5.75 C 4.1875 -5.3125 3.78125 -4.726562 3.375 -4 C 2.96875 -3.28125 2.65625 -2.535156 2.4375 -1.765625 C 2.28125 -1.234375 2.179688 -0.644531 2.140625 0 L 1.328125 0 C 1.335938 -0.507812 1.4375 -1.117188 1.625 -1.828125 C 1.8125 -2.546875 2.082031 -3.238281 2.4375 -3.90625 C 2.800781 -4.570312 3.179688 -5.132812 3.578125 -5.59375 Z M 0.421875 -5.59375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-4\" overflow=\"visible\">\n",
       "<path d=\"M 4.53125 -0.765625 L 4.53125 0 L 0.265625 0 C 0.265625 -0.1875 0.296875 -0.367188 0.359375 -0.546875 C 0.472656 -0.835938 0.648438 -1.125 0.890625 -1.40625 C 1.128906 -1.6875 1.472656 -2.007812 1.921875 -2.375 C 2.617188 -2.957031 3.085938 -3.414062 3.328125 -3.75 C 3.578125 -4.082031 3.703125 -4.398438 3.703125 -4.703125 C 3.703125 -5.015625 3.585938 -5.273438 3.359375 -5.484375 C 3.140625 -5.703125 2.851562 -5.8125 2.5 -5.8125 C 2.113281 -5.8125 1.804688 -5.695312 1.578125 -5.46875 C 1.347656 -5.238281 1.234375 -4.921875 1.234375 -4.515625 L 0.421875 -4.609375 C 0.472656 -5.210938 0.679688 -5.671875 1.046875 -5.984375 C 1.410156 -6.304688 1.898438 -6.46875 2.515625 -6.46875 C 3.128906 -6.46875 3.613281 -6.296875 3.96875 -5.953125 C 4.332031 -5.609375 4.515625 -5.1875 4.515625 -4.6875 C 4.515625 -4.425781 4.460938 -4.171875 4.359375 -3.921875 C 4.253906 -3.671875 4.078125 -3.40625 3.828125 -3.125 C 3.585938 -2.851562 3.1875 -2.476562 2.625 -2 C 2.144531 -1.601562 1.835938 -1.332031 1.703125 -1.1875 C 1.566406 -1.039062 1.457031 -0.898438 1.375 -0.765625 Z M 4.53125 -0.765625 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-5\" overflow=\"visible\">\n",
       "<path d=\"M 0.375 -1.6875 L 1.203125 -1.765625 C 1.265625 -1.359375 1.40625 -1.050781 1.625 -0.84375 C 1.851562 -0.644531 2.125 -0.546875 2.4375 -0.546875 C 2.820312 -0.546875 3.144531 -0.6875 3.40625 -0.96875 C 3.675781 -1.257812 3.8125 -1.640625 3.8125 -2.109375 C 3.8125 -2.566406 3.679688 -2.925781 3.421875 -3.1875 C 3.171875 -3.445312 2.84375 -3.578125 2.4375 -3.578125 C 2.175781 -3.578125 1.941406 -3.515625 1.734375 -3.390625 C 1.535156 -3.273438 1.375 -3.128906 1.25 -2.953125 L 0.515625 -3.046875 L 1.140625 -6.359375 L 4.34375 -6.359375 L 4.34375 -5.59375 L 1.765625 -5.59375 L 1.421875 -3.875 C 1.804688 -4.132812 2.210938 -4.265625 2.640625 -4.265625 C 3.203125 -4.265625 3.675781 -4.070312 4.0625 -3.6875 C 4.445312 -3.300781 4.640625 -2.800781 4.640625 -2.1875 C 4.640625 -1.601562 4.472656 -1.097656 4.140625 -0.671875 C 3.722656 -0.148438 3.15625 0.109375 2.4375 0.109375 C 1.851562 0.109375 1.375 -0.0507812 1 -0.375 C 0.632812 -0.707031 0.425781 -1.144531 0.375 -1.6875 Z M 0.375 -1.6875 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-6\" overflow=\"visible\">\n",
       "<path d=\"M 3.359375 0 L 2.5625 0 L 2.5625 -5.046875 C 2.375 -4.859375 2.125 -4.671875 1.8125 -4.484375 C 1.5 -4.304688 1.222656 -4.175781 0.984375 -4.09375 L 0.984375 -4.859375 C 1.421875 -5.054688 1.804688 -5.300781 2.140625 -5.59375 C 2.472656 -5.894531 2.707031 -6.1875 2.84375 -6.46875 L 3.359375 -6.46875 Z M 3.359375 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-7\" overflow=\"visible\">\n",
       "<path d=\"M 0.5 -1.484375 L 1.25 -1.5625 C 1.3125 -1.207031 1.429688 -0.945312 1.609375 -0.78125 C 1.796875 -0.625 2.035156 -0.546875 2.328125 -0.546875 C 2.566406 -0.546875 2.773438 -0.597656 2.953125 -0.703125 C 3.140625 -0.816406 3.289062 -0.96875 3.40625 -1.15625 C 3.53125 -1.34375 3.628906 -1.59375 3.703125 -1.90625 C 3.785156 -2.21875 3.828125 -2.539062 3.828125 -2.875 C 3.828125 -2.90625 3.820312 -2.957031 3.8125 -3.03125 C 3.65625 -2.78125 3.441406 -2.578125 3.171875 -2.421875 C 2.898438 -2.265625 2.601562 -2.1875 2.28125 -2.1875 C 1.75 -2.1875 1.296875 -2.378906 0.921875 -2.765625 C 0.554688 -3.148438 0.375 -3.660156 0.375 -4.296875 C 0.375 -4.953125 0.566406 -5.476562 0.953125 -5.875 C 1.335938 -6.269531 1.820312 -6.46875 2.40625 -6.46875 C 2.820312 -6.46875 3.203125 -6.351562 3.546875 -6.125 C 3.890625 -5.90625 4.148438 -5.585938 4.328125 -5.171875 C 4.515625 -4.753906 4.609375 -4.148438 4.609375 -3.359375 C 4.609375 -2.535156 4.519531 -1.878906 4.34375 -1.390625 C 4.164062 -0.898438 3.898438 -0.523438 3.546875 -0.265625 C 3.191406 -0.015625 2.773438 0.109375 2.296875 0.109375 C 1.796875 0.109375 1.382812 -0.03125 1.0625 -0.3125 C 0.75 -0.59375 0.5625 -0.984375 0.5 -1.484375 Z M 3.734375 -4.328125 C 3.734375 -4.785156 3.609375 -5.144531 3.359375 -5.40625 C 3.117188 -5.675781 2.832031 -5.8125 2.5 -5.8125 C 2.144531 -5.8125 1.835938 -5.664062 1.578125 -5.375 C 1.316406 -5.09375 1.1875 -4.722656 1.1875 -4.265625 C 1.1875 -3.859375 1.304688 -3.523438 1.546875 -3.265625 C 1.796875 -3.015625 2.101562 -2.890625 2.46875 -2.890625 C 2.84375 -2.890625 3.144531 -3.015625 3.375 -3.265625 C 3.613281 -3.523438 3.734375 -3.878906 3.734375 -4.328125 Z M 3.734375 -4.328125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-8\" overflow=\"visible\">\n",
       "<path d=\"M 4.484375 -4.859375 L 3.6875 -4.796875 C 3.625 -5.109375 3.523438 -5.335938 3.390625 -5.484375 C 3.179688 -5.703125 2.921875 -5.8125 2.609375 -5.8125 C 2.347656 -5.8125 2.125 -5.742188 1.9375 -5.609375 C 1.6875 -5.421875 1.488281 -5.15625 1.34375 -4.8125 C 1.207031 -4.46875 1.132812 -3.972656 1.125 -3.328125 C 1.3125 -3.609375 1.539062 -3.816406 1.8125 -3.953125 C 2.09375 -4.097656 2.382812 -4.171875 2.6875 -4.171875 C 3.21875 -4.171875 3.664062 -3.976562 4.03125 -3.59375 C 4.40625 -3.207031 4.59375 -2.707031 4.59375 -2.09375 C 4.59375 -1.6875 4.503906 -1.304688 4.328125 -0.953125 C 4.148438 -0.609375 3.910156 -0.34375 3.609375 -0.15625 C 3.304688 0.0195312 2.960938 0.109375 2.578125 0.109375 C 1.921875 0.109375 1.382812 -0.128906 0.96875 -0.609375 C 0.550781 -1.097656 0.34375 -1.898438 0.34375 -3.015625 C 0.34375 -4.253906 0.570312 -5.160156 1.03125 -5.734375 C 1.425781 -6.222656 1.96875 -6.46875 2.65625 -6.46875 C 3.15625 -6.46875 3.566406 -6.320312 3.890625 -6.03125 C 4.210938 -5.75 4.410156 -5.359375 4.484375 -4.859375 Z M 1.25 -2.09375 C 1.25 -1.8125 1.304688 -1.546875 1.421875 -1.296875 C 1.535156 -1.054688 1.695312 -0.867188 1.90625 -0.734375 C 2.113281 -0.609375 2.332031 -0.546875 2.5625 -0.546875 C 2.894531 -0.546875 3.179688 -0.675781 3.421875 -0.9375 C 3.660156 -1.207031 3.78125 -1.578125 3.78125 -2.046875 C 3.78125 -2.492188 3.660156 -2.84375 3.421875 -3.09375 C 3.191406 -3.351562 2.894531 -3.484375 2.53125 -3.484375 C 2.175781 -3.484375 1.875 -3.351562 1.625 -3.09375 C 1.375 -2.84375 1.25 -2.507812 1.25 -2.09375 Z M 1.25 -2.09375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-9\" overflow=\"visible\">\n",
       "<path d=\"M 1.59375 -3.5 C 1.257812 -3.613281 1.015625 -3.78125 0.859375 -4 C 0.703125 -4.226562 0.625 -4.5 0.625 -4.8125 C 0.625 -5.28125 0.789062 -5.671875 1.125 -5.984375 C 1.46875 -6.304688 1.914062 -6.46875 2.46875 -6.46875 C 3.03125 -6.46875 3.484375 -6.300781 3.828125 -5.96875 C 4.171875 -5.644531 4.34375 -5.25 4.34375 -4.78125 C 4.34375 -4.488281 4.265625 -4.226562 4.109375 -4 C 3.953125 -3.78125 3.710938 -3.613281 3.390625 -3.5 C 3.785156 -3.363281 4.085938 -3.148438 4.296875 -2.859375 C 4.503906 -2.578125 4.609375 -2.238281 4.609375 -1.84375 C 4.609375 -1.289062 4.410156 -0.828125 4.015625 -0.453125 C 3.628906 -0.078125 3.117188 0.109375 2.484375 0.109375 C 1.847656 0.109375 1.332031 -0.078125 0.9375 -0.453125 C 0.550781 -0.828125 0.359375 -1.296875 0.359375 -1.859375 C 0.359375 -2.273438 0.460938 -2.625 0.671875 -2.90625 C 0.890625 -3.195312 1.195312 -3.394531 1.59375 -3.5 Z M 1.4375 -4.828125 C 1.4375 -4.523438 1.53125 -4.273438 1.71875 -4.078125 C 1.914062 -3.890625 2.171875 -3.796875 2.484375 -3.796875 C 2.796875 -3.796875 3.046875 -3.890625 3.234375 -4.078125 C 3.429688 -4.273438 3.53125 -4.515625 3.53125 -4.796875 C 3.53125 -5.078125 3.429688 -5.316406 3.234375 -5.515625 C 3.035156 -5.710938 2.785156 -5.8125 2.484375 -5.8125 C 2.179688 -5.8125 1.929688 -5.710938 1.734375 -5.515625 C 1.535156 -5.328125 1.4375 -5.097656 1.4375 -4.828125 Z M 1.171875 -1.859375 C 1.171875 -1.628906 1.222656 -1.410156 1.328125 -1.203125 C 1.441406 -0.992188 1.601562 -0.832031 1.8125 -0.71875 C 2.019531 -0.601562 2.25 -0.546875 2.5 -0.546875 C 2.875 -0.546875 3.179688 -0.664062 3.421875 -0.90625 C 3.671875 -1.144531 3.796875 -1.453125 3.796875 -1.828125 C 3.796875 -2.210938 3.671875 -2.53125 3.421875 -2.78125 C 3.171875 -3.03125 2.851562 -3.15625 2.46875 -3.15625 C 2.09375 -3.15625 1.78125 -3.03125 1.53125 -2.78125 C 1.289062 -2.53125 1.171875 -2.222656 1.171875 -1.859375 Z M 1.171875 -1.859375 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-10\" overflow=\"visible\">\n",
       "<path d=\"M 0.375 -3.171875 C 0.375 -3.929688 0.453125 -4.546875 0.609375 -5.015625 C 0.765625 -5.484375 0.992188 -5.84375 1.296875 -6.09375 C 1.609375 -6.34375 2 -6.46875 2.46875 -6.46875 C 2.820312 -6.46875 3.128906 -6.394531 3.390625 -6.25 C 3.648438 -6.113281 3.863281 -5.914062 4.03125 -5.65625 C 4.195312 -5.394531 4.328125 -5.078125 4.421875 -4.703125 C 4.523438 -4.328125 4.578125 -3.816406 4.578125 -3.171875 C 4.578125 -2.421875 4.5 -1.8125 4.34375 -1.34375 C 4.1875 -0.882812 3.953125 -0.523438 3.640625 -0.265625 C 3.335938 -0.015625 2.945312 0.109375 2.46875 0.109375 C 1.851562 0.109375 1.367188 -0.113281 1.015625 -0.5625 C 0.585938 -1.09375 0.375 -1.960938 0.375 -3.171875 Z M 1.1875 -3.171875 C 1.1875 -2.117188 1.304688 -1.414062 1.546875 -1.0625 C 1.796875 -0.71875 2.101562 -0.546875 2.46875 -0.546875 C 2.832031 -0.546875 3.140625 -0.71875 3.390625 -1.0625 C 3.640625 -1.414062 3.765625 -2.117188 3.765625 -3.171875 C 3.765625 -4.234375 3.640625 -4.9375 3.390625 -5.28125 C 3.140625 -5.632812 2.832031 -5.8125 2.46875 -5.8125 C 2.101562 -5.8125 1.8125 -5.660156 1.59375 -5.359375 C 1.320312 -4.960938 1.1875 -4.234375 1.1875 -3.171875 Z M 1.1875 -3.171875 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-11\" overflow=\"visible\">\n",
       "<path d=\"M 0.4375 -3.140625 C 0.4375 -4.203125 0.722656 -5.035156 1.296875 -5.640625 C 1.867188 -6.253906 2.609375 -6.5625 3.515625 -6.5625 C 4.109375 -6.5625 4.644531 -6.414062 5.125 -6.125 C 5.601562 -5.84375 5.96875 -5.445312 6.21875 -4.9375 C 6.46875 -4.425781 6.59375 -3.851562 6.59375 -3.21875 C 6.59375 -2.5625 6.460938 -1.972656 6.203125 -1.453125 C 5.941406 -0.941406 5.566406 -0.550781 5.078125 -0.28125 C 4.597656 -0.0195312 4.078125 0.109375 3.515625 0.109375 C 2.910156 0.109375 2.367188 -0.0351562 1.890625 -0.328125 C 1.410156 -0.617188 1.046875 -1.019531 0.796875 -1.53125 C 0.554688 -2.039062 0.4375 -2.578125 0.4375 -3.140625 Z M 1.3125 -3.125 C 1.3125 -2.34375 1.519531 -1.726562 1.9375 -1.28125 C 2.351562 -0.84375 2.878906 -0.625 3.515625 -0.625 C 4.148438 -0.625 4.675781 -0.847656 5.09375 -1.296875 C 5.507812 -1.742188 5.71875 -2.382812 5.71875 -3.21875 C 5.71875 -3.738281 5.628906 -4.191406 5.453125 -4.578125 C 5.273438 -4.972656 5.015625 -5.28125 4.671875 -5.5 C 4.328125 -5.71875 3.945312 -5.828125 3.53125 -5.828125 C 2.925781 -5.828125 2.40625 -5.617188 1.96875 -5.203125 C 1.53125 -4.785156 1.3125 -4.09375 1.3125 -3.125 Z M 1.3125 -3.125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-12\" overflow=\"visible\">\n",
       "<path d=\"M 3.65625 0 L 3.65625 -0.6875 C 3.289062 -0.15625 2.796875 0.109375 2.171875 0.109375 C 1.898438 0.109375 1.644531 0.0546875 1.40625 -0.046875 C 1.164062 -0.160156 0.984375 -0.296875 0.859375 -0.453125 C 0.742188 -0.609375 0.664062 -0.800781 0.625 -1.03125 C 0.59375 -1.1875 0.578125 -1.4375 0.578125 -1.78125 L 0.578125 -4.671875 L 1.359375 -4.671875 L 1.359375 -2.078125 C 1.359375 -1.660156 1.378906 -1.382812 1.421875 -1.25 C 1.460938 -1.039062 1.5625 -0.875 1.71875 -0.75 C 1.882812 -0.632812 2.085938 -0.578125 2.328125 -0.578125 C 2.566406 -0.578125 2.789062 -0.632812 3 -0.75 C 3.207031 -0.875 3.351562 -1.039062 3.4375 -1.25 C 3.519531 -1.457031 3.5625 -1.765625 3.5625 -2.171875 L 3.5625 -4.671875 L 4.359375 -4.671875 L 4.359375 0 Z M 3.65625 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-13\" overflow=\"visible\">\n",
       "<path d=\"M 2.328125 -0.703125 L 2.4375 -0.015625 C 2.207031 0.0351562 2.007812 0.0625 1.84375 0.0625 C 1.550781 0.0625 1.328125 0.015625 1.171875 -0.078125 C 1.015625 -0.171875 0.898438 -0.289062 0.828125 -0.4375 C 0.765625 -0.582031 0.734375 -0.890625 0.734375 -1.359375 L 0.734375 -4.046875 L 0.15625 -4.046875 L 0.15625 -4.671875 L 0.734375 -4.671875 L 0.734375 -5.828125 L 1.53125 -6.296875 L 1.53125 -4.671875 L 2.328125 -4.671875 L 2.328125 -4.046875 L 1.53125 -4.046875 L 1.53125 -1.328125 C 1.53125 -1.097656 1.539062 -0.953125 1.5625 -0.890625 C 1.59375 -0.828125 1.640625 -0.773438 1.703125 -0.734375 C 1.765625 -0.691406 1.851562 -0.671875 1.96875 -0.671875 C 2.0625 -0.671875 2.179688 -0.679688 2.328125 -0.703125 Z M 2.328125 -0.703125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-14\" overflow=\"visible\">\n",
       "<path d=\"M 0.59375 1.78125 L 0.59375 -4.671875 L 1.3125 -4.671875 L 1.3125 -4.0625 C 1.476562 -4.300781 1.664062 -4.476562 1.875 -4.59375 C 2.09375 -4.707031 2.359375 -4.765625 2.671875 -4.765625 C 3.066406 -4.765625 3.414062 -4.660156 3.71875 -4.453125 C 4.019531 -4.253906 4.25 -3.96875 4.40625 -3.59375 C 4.5625 -3.21875 4.640625 -2.8125 4.640625 -2.375 C 4.640625 -1.894531 4.550781 -1.460938 4.375 -1.078125 C 4.207031 -0.691406 3.960938 -0.394531 3.640625 -0.1875 C 3.316406 0.0078125 2.972656 0.109375 2.609375 0.109375 C 2.347656 0.109375 2.113281 0.0507812 1.90625 -0.0625 C 1.695312 -0.175781 1.523438 -0.316406 1.390625 -0.484375 L 1.390625 1.78125 Z M 1.3125 -2.3125 C 1.3125 -1.707031 1.429688 -1.257812 1.671875 -0.96875 C 1.921875 -0.6875 2.21875 -0.546875 2.5625 -0.546875 C 2.90625 -0.546875 3.203125 -0.691406 3.453125 -0.984375 C 3.710938 -1.285156 3.84375 -1.75 3.84375 -2.375 C 3.84375 -2.96875 3.71875 -3.410156 3.46875 -3.703125 C 3.226562 -4.003906 2.9375 -4.15625 2.59375 -4.15625 C 2.257812 -4.15625 1.960938 -3.992188 1.703125 -3.671875 C 1.441406 -3.359375 1.3125 -2.90625 1.3125 -2.3125 Z M 1.3125 -2.3125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-15\" overflow=\"visible\">\n",
       "<path d=\"M 0.65625 0 L 0.65625 -6.4375 L 1.515625 -6.4375 L 1.515625 -3.25 L 4.71875 -6.4375 L 5.859375 -6.4375 L 3.171875 -3.828125 L 5.984375 0 L 4.859375 0 L 2.5625 -3.265625 L 1.515625 -2.234375 L 1.515625 0 Z M 0.65625 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-16\" overflow=\"visible\">\n",
       "<path d=\"M 3.78125 -1.5 L 4.609375 -1.40625 C 4.472656 -0.925781 4.226562 -0.550781 3.875 -0.28125 C 3.53125 -0.0195312 3.085938 0.109375 2.546875 0.109375 C 1.867188 0.109375 1.328125 -0.0976562 0.921875 -0.515625 C 0.523438 -0.941406 0.328125 -1.535156 0.328125 -2.296875 C 0.328125 -3.078125 0.53125 -3.679688 0.9375 -4.109375 C 1.34375 -4.546875 1.867188 -4.765625 2.515625 -4.765625 C 3.140625 -4.765625 3.644531 -4.550781 4.03125 -4.125 C 4.425781 -3.707031 4.625 -3.113281 4.625 -2.34375 C 4.625 -2.289062 4.625 -2.21875 4.625 -2.125 L 1.140625 -2.125 C 1.171875 -1.613281 1.316406 -1.222656 1.578125 -0.953125 C 1.835938 -0.679688 2.164062 -0.546875 2.5625 -0.546875 C 2.851562 -0.546875 3.097656 -0.617188 3.296875 -0.765625 C 3.503906 -0.921875 3.664062 -1.164062 3.78125 -1.5 Z M 1.1875 -2.78125 L 3.796875 -2.78125 C 3.765625 -3.175781 3.664062 -3.472656 3.5 -3.671875 C 3.25 -3.972656 2.921875 -4.125 2.515625 -4.125 C 2.148438 -4.125 1.84375 -4 1.59375 -3.75 C 1.351562 -3.507812 1.21875 -3.1875 1.1875 -2.78125 Z M 1.1875 -2.78125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-17\" overflow=\"visible\">\n",
       "<path d=\"M 0.578125 0 L 0.578125 -4.671875 L 1.296875 -4.671875 L 1.296875 -3.953125 C 1.472656 -4.285156 1.640625 -4.503906 1.796875 -4.609375 C 1.953125 -4.710938 2.125 -4.765625 2.3125 -4.765625 C 2.570312 -4.765625 2.84375 -4.679688 3.125 -4.515625 L 2.84375 -3.78125 C 2.65625 -3.894531 2.460938 -3.953125 2.265625 -3.953125 C 2.097656 -3.953125 1.941406 -3.898438 1.796875 -3.796875 C 1.660156 -3.691406 1.5625 -3.546875 1.5 -3.359375 C 1.414062 -3.078125 1.375 -2.769531 1.375 -2.4375 L 1.375 0 Z M 0.578125 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-18\" overflow=\"visible\">\n",
       "<path d=\"M 0.59375 0 L 0.59375 -4.671875 L 1.3125 -4.671875 L 1.3125 -4 C 1.644531 -4.507812 2.140625 -4.765625 2.796875 -4.765625 C 3.078125 -4.765625 3.332031 -4.710938 3.5625 -4.609375 C 3.800781 -4.515625 3.976562 -4.382812 4.09375 -4.21875 C 4.207031 -4.0625 4.289062 -3.867188 4.34375 -3.640625 C 4.375 -3.492188 4.390625 -3.238281 4.390625 -2.875 L 4.390625 0 L 3.59375 0 L 3.59375 -2.84375 C 3.59375 -3.164062 3.5625 -3.40625 3.5 -3.5625 C 3.4375 -3.71875 3.328125 -3.84375 3.171875 -3.9375 C 3.015625 -4.039062 2.832031 -4.09375 2.625 -4.09375 C 2.289062 -4.09375 2 -3.984375 1.75 -3.765625 C 1.507812 -3.554688 1.390625 -3.148438 1.390625 -2.546875 L 1.390625 0 Z M 0.59375 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-19\" overflow=\"visible\">\n",
       "<path d=\"M 0.578125 0 L 0.578125 -6.4375 L 1.359375 -6.4375 L 1.359375 0 Z M 0.578125 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph0-20\" overflow=\"visible\">\n",
       "<path d=\"M 0.84375 0 L 0.84375 -6.4375 L 1.6875 -6.4375 L 1.6875 0 Z M 0.84375 0 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-0\" overflow=\"visible\">\n",
       "<path d=\"M 2.25 0 L 2.25 -11.25 L 11.25 -11.25 L 11.25 0 Z M 2.53125 -0.28125 L 10.96875 -0.28125 L 10.96875 -10.96875 L 2.53125 -10.96875 Z M 2.53125 -0.28125 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-1\" overflow=\"visible\">\n",
       "<path d=\"M 0.5625 -10.515625 L 0.96875 -11.765625 C 1.894531 -11.441406 2.570312 -11.160156 3 -10.921875 C 2.882812 -11.972656 2.828125 -12.703125 2.828125 -13.109375 L 4.09375 -13.109375 C 4.070312 -12.523438 4.003906 -11.796875 3.890625 -10.921875 C 4.492188 -11.222656 5.1875 -11.503906 5.96875 -11.765625 L 6.375 -10.515625 C 5.625 -10.273438 4.894531 -10.113281 4.1875 -10.03125 C 4.539062 -9.71875 5.046875 -9.164062 5.703125 -8.375 L 4.640625 -7.625 C 4.296875 -8.082031 3.894531 -8.710938 3.4375 -9.515625 C 3 -8.679688 2.617188 -8.050781 2.296875 -7.625 L 1.25 -8.375 C 1.9375 -9.207031 2.425781 -9.757812 2.71875 -10.03125 C 1.957031 -10.175781 1.238281 -10.335938 0.5625 -10.515625 Z M 0.5625 -10.515625 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "<symbol id=\"glyph1-2\" overflow=\"visible\">\n",
       "<path d=\"M 9.515625 -7.578125 L 1 -7.578125 L 1 -9.046875 L 9.515625 -9.046875 Z M 9.515625 -3.671875 L 1 -3.671875 L 1 -5.140625 L 9.515625 -5.140625 Z M 9.515625 -3.671875 \" style=\"stroke:none;\"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface1\">\n",
       "<rect height=\"83\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;\" width=\"209\" x=\"0\" y=\"0\"/>\n",
       "<rect height=\"83\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;\" width=\"209\" x=\"0\" y=\"0\"/>\n",
       "<path d=\"M 242.214844 157.214844 L 260.214844 157.214844 L 260.214844 175.214844 L 242.214844 175.214844 Z M 242.214844 157.214844 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"193.210829\" xlink:href=\"#glyph0-1\" y=\"66.069003\"/>\n",
       "  <use x=\"198.216629\" xlink:href=\"#glyph0-2\" y=\"66.069003\"/>\n",
       "</g>\n",
       "<path d=\"M 224.214844 157.214844 L 242.214844 157.214844 L 242.214844 175.214844 L 224.214844 175.214844 Z M 224.214844 157.214844 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"175.210829\" xlink:href=\"#glyph0-2\" y=\"66.069003\"/>\n",
       "  <use x=\"180.216629\" xlink:href=\"#glyph0-3\" y=\"66.069003\"/>\n",
       "</g>\n",
       "<path d=\"M 242.214844 139.214844 L 260.214844 139.214844 L 260.214844 157.214844 L 242.214844 157.214844 Z M 242.214844 139.214844 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"193.210829\" xlink:href=\"#glyph0-4\" y=\"48.069003\"/>\n",
       "  <use x=\"198.216629\" xlink:href=\"#glyph0-5\" y=\"48.069003\"/>\n",
       "</g>\n",
       "<path d=\"M 224.214844 139.214844 L 242.214844 139.214844 L 242.214844 157.214844 L 224.214844 157.214844 Z M 224.214844 139.214844 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"175.210829\" xlink:href=\"#glyph0-6\" y=\"48.069003\"/>\n",
       "  <use x=\"180.216629\" xlink:href=\"#glyph0-7\" y=\"48.069003\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"68.88507\" xlink:href=\"#glyph1-1\" y=\"64.562496\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"143.0735\" xlink:href=\"#glyph1-2\" y=\"59.921786\"/>\n",
       "</g>\n",
       "<path d=\"M 72 166.617188 L 90 166.617188 L 90 184.617188 L 72 184.617188 Z M 72 166.617188 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"25.497314\" xlink:href=\"#glyph0-3\" y=\"75.471833\"/>\n",
       "</g>\n",
       "<path d=\"M 72 130.617188 L 90 130.617188 L 90 148.617188 L 72 148.617188 Z M 72 130.617188 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"25.497314\" xlink:href=\"#glyph0-6\" y=\"39.471833\"/>\n",
       "</g>\n",
       "<path d=\"M 72 148.617188 L 90 148.617188 L 90 166.617188 L 72 166.617188 Z M 72 148.617188 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"25.497314\" xlink:href=\"#glyph0-1\" y=\"57.471833\"/>\n",
       "</g>\n",
       "<path d=\"M 54 166.617188 L 72 166.617188 L 72 184.617188 L 54 184.617188 Z M 54 166.617188 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"7.497314\" xlink:href=\"#glyph0-8\" y=\"75.471833\"/>\n",
       "</g>\n",
       "<path d=\"M 90 148.617188 L 108 148.617188 L 108 166.617188 L 90 166.617188 Z M 90 148.617188 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"43.497314\" xlink:href=\"#glyph0-5\" y=\"57.471833\"/>\n",
       "</g>\n",
       "<path d=\"M 54 148.617188 L 72 148.617188 L 72 166.617188 L 54 166.617188 Z M 54 148.617188 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"7.497314\" xlink:href=\"#glyph0-2\" y=\"57.471833\"/>\n",
       "</g>\n",
       "<path d=\"M 90 166.617188 L 108 166.617188 L 108 184.617188 L 90 184.617188 Z M 90 166.617188 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"43.497314\" xlink:href=\"#glyph0-9\" y=\"75.471833\"/>\n",
       "</g>\n",
       "<path d=\"M 90 130.617188 L 108 130.617188 L 108 148.617188 L 90 148.617188 Z M 90 130.617188 \" style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"43.497314\" xlink:href=\"#glyph0-4\" y=\"39.471833\"/>\n",
       "</g>\n",
       "<path d=\"M 54 130.617188 L 72 130.617188 L 72 148.617188 L 54 148.617188 Z M 54 130.617188 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"7.497314\" xlink:href=\"#glyph0-10\" y=\"39.471833\"/>\n",
       "</g>\n",
       "<path d=\"M 144.03125 157.214844 L 162.03125 157.214844 L 162.03125 175.214844 L 144.03125 175.214844 Z M 144.03125 157.214844 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"97.529614\" xlink:href=\"#glyph0-4\" y=\"66.069003\"/>\n",
       "</g>\n",
       "<path d=\"M 162.03125 157.214844 L 180.03125 157.214844 L 180.03125 175.214844 L 162.03125 175.214844 Z M 162.03125 157.214844 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"115.529614\" xlink:href=\"#glyph0-2\" y=\"66.069003\"/>\n",
       "</g>\n",
       "<path d=\"M 162.03125 139.214844 L 180.03125 139.214844 L 180.03125 157.214844 L 162.03125 157.214844 Z M 162.03125 139.214844 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"115.529614\" xlink:href=\"#glyph0-6\" y=\"48.069003\"/>\n",
       "</g>\n",
       "<path d=\"M 144.03125 139.214844 L 162.03125 139.214844 L 162.03125 157.214844 L 144.03125 157.214844 Z M 144.03125 139.214844 \" style=\"fill-rule:nonzero;fill:rgb(69.802856%,85.096741%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" transform=\"matrix(1,0,0,1,-53,-103)\"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"97.529614\" xlink:href=\"#glyph0-10\" y=\"48.069003\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"175.70741\" xlink:href=\"#glyph0-11\" y=\"13.352783\"/>\n",
       "  <use x=\"182.70761\" xlink:href=\"#glyph0-12\" y=\"13.352783\"/>\n",
       "  <use x=\"187.70981\" xlink:href=\"#glyph0-13\" y=\"13.352783\"/>\n",
       "  <use x=\"190.21001\" xlink:href=\"#glyph0-14\" y=\"13.352783\"/>\n",
       "  <use x=\"195.21221\" xlink:href=\"#glyph0-12\" y=\"13.352783\"/>\n",
       "  <use x=\"200.21441\" xlink:href=\"#glyph0-13\" y=\"13.352783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"95.49219\" xlink:href=\"#glyph0-15\" y=\"13.352783\"/>\n",
       "  <use x=\"101.49519\" xlink:href=\"#glyph0-16\" y=\"13.352783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"106.50099\" xlink:href=\"#glyph0-17\" y=\"13.352783\"/>\n",
       "  <use x=\"109.49799\" xlink:href=\"#glyph0-18\" y=\"13.352783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"114.50379\" xlink:href=\"#glyph0-16\" y=\"13.352783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"119.50959\" xlink:href=\"#glyph0-19\" y=\"13.352783\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use x=\"18.99146\" xlink:href=\"#glyph0-20\" y=\"13.352783\"/>\n",
       "  <use x=\"21.49166\" xlink:href=\"#glyph0-18\" y=\"13.352783\"/>\n",
       "  <use x=\"26.49386\" xlink:href=\"#glyph0-14\" y=\"13.352783\"/>\n",
       "  <use x=\"31.49606\" xlink:href=\"#glyph0-12\" y=\"13.352783\"/>\n",
       "  <use x=\"36.49826\" xlink:href=\"#glyph0-13\" y=\"13.352783\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import SVG\n",
    "SVG(filename = '../img/correlation.svg')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fig:Two-dimensional cross-correlation operation. The shaded portions are the first output element and the input and kernel array elements used in its computation: $0\\times0+1\\times1+3\\times2+4\\times3=19$. \n",
    "\n",
    "In the two-dimensional cross-correlation operation,\n",
    "we begin with the convolution window positioned\n",
    "at the top-left corner of the input array\n",
    "and slide it across the input array,\n",
    "both from left to right and top to bottom.\n",
    "When the convolution window slides to a certain position,\n",
    "the input subarray contained in that window\n",
    "and the kernel array are multiplied (element-wise)\n",
    "and the resulting array is summed up\n",
    "yielding a single scalar value.\n",
    "This result if precisely the value of the output array\n",
    "at the corresponding location.\n",
    "Here, the output array has a height of 2 and width of 2\n",
    "and the four elements are derived from\n",
    "the two-dimensional cross-correlation operation:\n",
    "\n",
    "$$\n",
    "0\\times0+1\\times1+3\\times2+4\\times3=19,\\\\\n",
    "1\\times0+2\\times1+4\\times2+5\\times3=25,\\\\\n",
    "3\\times0+4\\times1+6\\times2+7\\times3=37,\\\\\n",
    "4\\times0+5\\times1+7\\times2+8\\times3=43.\n",
    "$$\n",
    "\n",
    "Note that along each axi, the output is slightly *smaller* than the input.\n",
    "Because the kernel has a width greater than one,\n",
    "and we can only computer the cross-correlation\n",
    "for locations where the kernel fits wholly within the image,\n",
    "the output size is given by the input size $H \\times W$\n",
    "minus the size of the convolutional kernel $h \\times w$\n",
    "via $(H-h+1) \\times (W-w+1)$.\n",
    "This is the case since we need enough space\n",
    "to 'shift' the convolutional kernel across the image\n",
    "(later we will see how to keep the size unchanged\n",
    "by padding the image with zeros around its boundary\n",
    "such that there's enough space to shift the kernel).\n",
    "Next, we implement the above process in the `corr2d` function.\n",
    "It accepts the input array `X` with the kernel array `K`\n",
    "and outputs the array `Y`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch\n",
    "from torch import nn\n",
    "\n",
    "# This function has been saved in the d2l package for future use\n",
    "def corr2d(X, K):\n",
    "    h, w = K.shape\n",
    "    Y = torch.zeros((X.shape[0] - h + 1, X.shape[1] - w + 1))\n",
    "\n",
    "    for i in range(Y.shape[0]):\n",
    "        for j in range(Y.shape[1]):\n",
    "            Y[i, j] = (X[i: i + h, j: j + w] * K).sum()\n",
    "    return Y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can construct the input array `X` and the kernel array `K`\n",
    "from the figure above\n",
    "to validate the output of the above implementations\n",
    "of the two-dimensional cross-correlation operation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[19., 25.],\n",
       "        [37., 43.]])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X = torch.Tensor([[0, 1, 2], [3, 4, 5], [6, 7, 8]])\n",
    "K = torch.Tensor([[0, 1], [2, 3]])\n",
    "corr2d(X, K)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Convolutional Layers\n",
    "\n",
    "A convolutional layer cross-correlates the input and kernels\n",
    "and adds a scalar bias to produce an output.\n",
    "The parameters of the convolutional layer\n",
    "are precisely the values that constitute the kernel and the scalar bias.\n",
    "When training the models based on convolutional layers,\n",
    "we typically initialize the kernels randomly,\n",
    "just as we would with a fully-connected layer.\n",
    "\n",
    "We are now ready to implement a two-dimensional convolutional layer\n",
    "based on the `corr2d` function defined above.\n",
    "In the `__init__` constructor function,\n",
    "we declare `weight` and `bias` as the two model parameters.\n",
    "The forward computation function `forward`\n",
    "calls the `corr2d` function and adds the bias.\n",
    "As with $h \\times w$ cross-correlation\n",
    "we also refer to convolutional layers\n",
    "as $h \\times w$ convolutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "attributes": {
     "classes": [],
     "id": "",
     "n": "70"
    }
   },
   "outputs": [],
   "source": [
    "class Conv2D(nn.Module):\n",
    "    def __init__(self, kernel_size, **kwargs):\n",
    "        super(Conv2D, self).__init__(**kwargs)\n",
    "        self.weight = torch.rand(kernel_size,dtype=torch.float32,requires_grad=True)\n",
    "        self.bias = torch.zeros((1,),dtype=torch.float32,requires_grad=True)\n",
    "\n",
    "    def forward(self, x):\n",
    "        \n",
    "        return corr2d(x, self.weight) + self.bias"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Object Edge Detection in Images\n",
    "\n",
    "Let's look at a simple application of a convolutional layer:\n",
    "detecting the edge of an object in an image\n",
    "by finding the location of the pixel change.\n",
    "First, we construct an 'image' of $6\\times 8$ pixels.\n",
    "The middle four columns are black (0) and the rest are white (1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "attributes": {
     "classes": [],
     "id": "",
     "n": "66"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[1., 1., 0., 0., 0., 0., 1., 1.],\n",
       "        [1., 1., 0., 0., 0., 0., 1., 1.],\n",
       "        [1., 1., 0., 0., 0., 0., 1., 1.],\n",
       "        [1., 1., 0., 0., 0., 0., 1., 1.],\n",
       "        [1., 1., 0., 0., 0., 0., 1., 1.],\n",
       "        [1., 1., 0., 0., 0., 0., 1., 1.]])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X = torch.ones((6, 8))\n",
    "X[:, 2:6] = 0\n",
    "X"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we construct a kernel `K` with a height of 1 and width of 2.\n",
    "When we perform the cross-correlation operation with the input,\n",
    "if the horizontally adjacent elements are the same,\n",
    "the output is 0. Otherwise, the output is non-zero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "attributes": {
     "classes": [],
     "id": "",
     "n": "67"
    }
   },
   "outputs": [],
   "source": [
    "K = torch.Tensor([[1, -1]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Enter `X` and our designed kernel `K`\n",
    "to perform the cross-correlation operations.\n",
    "As you can see, we will detect 1 for the edge from white to black\n",
    "and -1 for the edge from black to white.\n",
    "The rest of the outputs are 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "attributes": {
     "classes": [],
     "id": "",
     "n": "69"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[ 0.,  1.,  0.,  0.,  0., -1.,  0.],\n",
       "        [ 0.,  1.,  0.,  0.,  0., -1.,  0.],\n",
       "        [ 0.,  1.,  0.,  0.,  0., -1.,  0.],\n",
       "        [ 0.,  1.,  0.,  0.,  0., -1.,  0.],\n",
       "        [ 0.,  1.,  0.,  0.,  0., -1.,  0.],\n",
       "        [ 0.,  1.,  0.,  0.,  0., -1.,  0.]])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Y = corr2d(X, K)\n",
    "Y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's apply the kernel to the transposed image.\n",
    "As expected, it vanishes. The kernel `K` only detects vertical edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[0., 0., 0., 0., 0.],\n",
       "        [0., 0., 0., 0., 0.],\n",
       "        [0., 0., 0., 0., 0.],\n",
       "        [0., 0., 0., 0., 0.],\n",
       "        [0., 0., 0., 0., 0.],\n",
       "        [0., 0., 0., 0., 0.],\n",
       "        [0., 0., 0., 0., 0.],\n",
       "        [0., 0., 0., 0., 0.]])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "corr2d(X.t(), K)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Learning a Kernel\n",
    "\n",
    "Designing an edge detector by finite differences `[1, -1]` is neat\n",
    "if we know this is precisely what we are looking for.\n",
    "However, as we look at larger kernels,\n",
    "and consider successive layers of convolutions,\n",
    "it might be impossible to specify\n",
    "precisely what each filter should be doing manually.\n",
    "\n",
    "Now let's see whether we can learn the kernel that generated `Y` from `X`\n",
    "by looking at the (input, output) pairs only.\n",
    "We first construct a convolutional layer\n",
    "and initialize its kernel as a random array.\n",
    "Next, in each iteration, we will use the squared error\n",
    "to compare `Y` and the output of the convolutional layer,\n",
    "then calculate the gradient to update the weight.\n",
    "For the sake of simplicity, in this convolutional layer,\n",
    "we will ignores the bias.\n",
    "\n",
    "We previously constructed the `Conv2D` class.But here we are using the `nn.Conv2D` from the Pytorch libraries. The custom class `Conv2D` that we created can be used similarly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "attributes": {
     "classes": [],
     "id": "",
     "n": "83"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "batch 2, loss 5.672\n",
      "batch 4, loss 1.359\n",
      "batch 6, loss 0.395\n",
      "batch 8, loss 0.134\n",
      "batch 10, loss 0.051\n"
     ]
    }
   ],
   "source": [
    "# Construct a convolutional layer with 1 output channel\n",
    "# (channels will be introduced in the following section)\n",
    "# and a kernel array shape of (1, 2)\n",
    "\n",
    "conv2d = nn.Conv2d(1,1, kernel_size=(1, 2),bias=False) #For sake of simplicity ignoring bias\n",
    "\n",
    "# The two-dimensional convolutional layer uses four-dimensional input and\n",
    "# output in the format of (example channel, height, width), where the batch\n",
    "# size (number of examples in the batch) and the number of channels are both 1\n",
    "\n",
    "X = X.reshape((1, 1, 6, 8))\n",
    "Y = Y.reshape((1, 1, 6, 7))\n",
    "\n",
    "\n",
    "for i in range(10):\n",
    "    Y_hat = conv2d(X)\n",
    "    l = (Y_hat - Y) ** 2\n",
    "   \n",
    "    conv2d.zero_grad()\n",
    "    l.sum().backward()\n",
    "    # For the sake of simplicity, we ignore the bias here\n",
    "    conv2d.weight.data[:] -= 3e-2 * conv2d.weight.grad\n",
    "    if (i + 1) % 2 == 0:\n",
    "        print('batch %d, loss %.3f' % (i + 1, l.sum()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the error has dropped to a small value after 10 iterations. Now we will take a look at the kernel array we learned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[ 1.0121, -0.9671]])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "conv2d.weight.data.reshape((1, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Indeed, the learned kernel array is remarkably close\n",
    "to the kernel array `K` we defined earlier.\n",
    "\n",
    "## Cross-correlation and Convolution\n",
    "\n",
    "Recall the observation from the previous section\n",
    "that cross-correlation and convolution are equivalent.\n",
    "In the figure above it is easy to see this correspondence.\n",
    "Simply flip the kernel from the bottom left to the top right.\n",
    "In this case the indexing in the sum is reverted,\n",
    "yet the same result can be obtained.\n",
    "In keeping with standard terminology with deep learning literature,\n",
    "we will continue to refer to the cross-correlation operation\n",
    "as a convolution even though, strictly-speaking, it is slightly different.\n",
    "\n",
    "## Summary\n",
    "\n",
    "* The core computation of a two-dimensional convolutional layer is a two-dimensional cross-correlation operation. In its simplest form, this performs a cross-correlation operation on the two-dimensional input data and the kernel, and then adds a bias.\n",
    "* We can design a kernel to detect edges in images.\n",
    "* We can learn the kernel through data.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Construct an image `X` with diagonal edges.\n",
    "    * What happens if you apply the kernel `K` to it?\n",
    "    * What happens if you transpose `X`?\n",
    "    * What happens if you transpose `K`?\n",
    "1. How do you represent a cross-correlation operation as a matrix multiplication by changing the input and kernel arrays?\n",
    "1. Design some kernels manually.\n",
    "    * What is the form of a kernel for the second derivative?\n",
    "    * What is the kernel for the Laplace operator?\n",
    "    * What is the kernel for an integral?\n",
    "    * What is the minimum size of a kernel to obtain a derivative of degree $d$?\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}