{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=padding-and-strides-md-1 fw=all -->\n",
    "\n",
    "# Padding and Stride\n",
    "\n",
    "Recall the example of a convolution in the figure. \n",
    "The input had both a height and width of 3\n",
    "and the convolution kernel had both a height and width of 2,\n",
    "yielding an output representation with dimension $2\\times2$.\n",
    "Assuming that the input shape is $n_\\textrm{h}\\times n_\\textrm{w}$\n",
    "and the convolution kernel shape is $k_\\textrm{h}\\times k_\\textrm{w}$,\n",
    "the output shape will be $(n_\\textrm{h}-k_\\textrm{h}+1) \\times (n_\\textrm{w}-k_\\textrm{w}+1)$: \n",
    "we can only shift the convolution kernel so far until it runs out\n",
    "of pixels to apply the convolution to. \n",
    "\n",
    "In the following we will explore a number of techniques,\n",
    "including padding, strided convolutions, and dilation,\n",
    "that offer more control over the size of the output\n",
    "and over the area of the input that each output element sees. \n",
    "As motivation, note that since kernels generally\n",
    "have width and height greater than $1$,\n",
    "after applying many successive convolutions,\n",
    "we tend to wind up with outputs that are\n",
    "considerably smaller than our input.\n",
    "If we start with a $240 \\times 240$ pixel image,\n",
    "ten unpadded layers of $5 \\times 5$ convolutions\n",
    "reduce the representation to $200 \\times 200$ pixels. The surviving outputs\n",
    "are centered away from the original boundary, and boundary pixels influence\n",
    "far fewer activations than interior pixels.\n",
    "*Padding* is the most popular tool for handling this issue.\n",
    "In other cases, we may want to reduce the dimensionality drastically,\n",
    "e.g., if we find the original input resolution to be unwieldy.\n",
    "*Strided convolutions* are a popular technique that can help in these instances."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "padding-and-strides-padding-and-stride"
   },
   "source": [
    "import torch\n",
    "from torch import nn"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=padding-and-strides-md-2 fw=all -->\n",
    "\n",
    "## Padding\n",
    "\n",
    "As described above, one tricky issue when applying convolutional layers\n",
    "is that we tend to lose pixels on the perimeter of our image. Consider the figure that depicts the pixel utilization as a function of the convolution kernel size and the position within the image. The pixels in the corners are hardly used at all. \n",
    "\n",
    "![Pixel utilization for convolutions of size $1 \\times 1$, $2 \\times 2$, and $3 \\times 3$ respectively.](../img/conv-reuse.svg)\n",
    "\n",
    "Since we typically use small kernels,\n",
    "for any given convolution\n",
    "we might only lose a few pixels\n",
    "but this can add up as we apply\n",
    "many successive convolutional layers.\n",
    "One straightforward solution to this problem\n",
    "is to add extra pixels of filler around the boundary of our input image,\n",
    "thus increasing the effective size of the image.\n",
    "Typically, we set the values of the extra pixels to zero.\n",
    "In the figure, we pad a $3 \\times 3$ input,\n",
    "increasing its size to $5 \\times 5$.\n",
    "The corresponding output then increases to a $4 \\times 4$ matrix.\n",
    "The shaded portions are the first output element as well as the input and kernel tensor elements used for the output computation: $0\\times0+0\\times1+0\\times2+0\\times3=0$.\n",
    "\n",
    "![Two-dimensional cross-correlation with padding.](../img/conv-pad.svg)\n",
    "\n",
    "In general, if we add a total of $p_\\textrm{h}$ rows of padding\n",
    "(roughly half on top and half on bottom)\n",
    "and a total of $p_\\textrm{w}$ columns of padding\n",
    "(roughly half on the left and half on the right),\n",
    "the output shape will be\n",
    "\n",
    "$$(n_\\textrm{h}-k_\\textrm{h}+p_\\textrm{h}+1)\\times(n_\\textrm{w}-k_\\textrm{w}+p_\\textrm{w}+1).$$\n",
    "\n",
    "This means that the height and width of the output\n",
    "will increase by $p_\\textrm{h}$ and $p_\\textrm{w}$, respectively.\n",
    "\n",
    "In many cases, we will want to set $p_\\textrm{h}=k_\\textrm{h}-1$ and $p_\\textrm{w}=k_\\textrm{w}-1$\n",
    "to give the input and output the same height and width.\n",
    "This will make it easier to predict the output shape of each layer\n",
    "when constructing the network.\n",
    "Assuming that $k_\\textrm{h}$ is odd here,\n",
    "we will pad $p_\\textrm{h}/2$ rows on both sides of the height.\n",
    "If $k_\\textrm{h}$ is even, one possibility is to\n",
    "pad $\\lceil p_\\textrm{h}/2\\rceil$ rows on the top of the input\n",
    "and $\\lfloor p_\\textrm{h}/2\\rfloor$ rows on the bottom.\n",
    "We will pad both sides of the width in the same way.\n",
    "\n",
    "CNNs commonly use convolution kernels\n",
    "with odd height and width values, such as 1, 3, 5, or 7.\n",
    "Choosing odd kernel sizes has the benefit\n",
    "that we can preserve the dimensionality\n",
    "while padding with the same number of rows on top and bottom,\n",
    "and the same number of columns on left and right.\n",
    "\n",
    "Moreover, this practice of using odd kernels\n",
    "and padding to precisely preserve dimensionality\n",
    "offers a clerical benefit.\n",
    "For any two-dimensional tensor `X`,\n",
    "when the kernel's size is odd\n",
    "and the number of padding rows and columns\n",
    "on all sides are the same,\n",
    "thereby producing an output with the same height and width as the input,\n",
    "we know that the output `Y[i, j]` is calculated\n",
    "by cross-correlation of the input and convolution kernel\n",
    "with the window centered on `X[i, j]`.\n",
    "\n",
    "In the following example, we create a two-dimensional convolutional layer\n",
    "with a height and width of 3\n",
    "and apply 1 pixel of padding on all sides.\n",
    "Given an input with a height and width of 8,\n",
    "we find that the height and width of the output is also 8."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "padding-and-strides-padding-1"
   },
   "source": [
    "# We define a helper function to calculate convolutions. It initializes the\n",
    "# convolutional layer weights and performs corresponding dimensionality\n",
    "# elevations and reductions on the input and output\n",
    "def comp_conv2d(conv2d, X):\n",
    "    # (1, 1) indicates that batch size and the number of channels are both 1\n",
    "    X = X.reshape((1, 1) + X.shape)\n",
    "    Y = conv2d(X)\n",
    "    # Strip the first two dimensions: examples and channels\n",
    "    return Y.reshape(Y.shape[2:])\n",
    "\n",
    "# 1 row and column is padded on either side, so a total of 2 rows or columns\n",
    "# are added\n",
    "conv2d = nn.LazyConv2d(1, kernel_size=3, padding=1)\n",
    "X = torch.rand(size=(8, 8))\n",
    "comp_conv2d(conv2d, X).shape"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "torch.Size([8, 8])"
     },
     "metadata": {},
     "execution_count": 2
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=padding-and-strides-md-3 fw=all -->\n",
    "\n",
    "When the height and width of the convolution kernel are different,\n",
    "we can make the output and input have the same height and width\n",
    "by setting different padding numbers for height and width."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "padding-and-strides-padding-2"
   },
   "source": [
    "# We use a convolution kernel with height 5 and width 3. The padding on either\n",
    "# side of the height and width are 2 and 1, respectively\n",
    "conv2d = nn.LazyConv2d(1, kernel_size=(5, 3), padding=(2, 1))\n",
    "comp_conv2d(conv2d, X).shape"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "torch.Size([8, 8])"
     },
     "metadata": {},
     "execution_count": 3
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=padding-and-strides-md-4 fw=all -->\n",
    "\n",
    "## Stride\n",
    "\n",
    "When computing the cross-correlation,\n",
    "we start with the convolution window\n",
    "at the upper-left corner of the input tensor,\n",
    "and then slide it over all locations both down and to the right.\n",
    "In the previous examples, we defaulted to sliding one element at a time.\n",
    "However, sometimes, either for computational efficiency\n",
    "or because we wish to downsample,\n",
    "we move our window more than one element at a time,\n",
    "skipping the intermediate locations. This is particularly useful if the convolution \n",
    "kernel is large since it captures a large area of the underlying image.\n",
    "\n",
    "We refer to the number of rows and columns traversed per slide as *stride*.\n",
    "So far, we have used strides of 1, both for height and width.\n",
    "Sometimes, we may want to use a larger stride.\n",
    "the figure shows a two-dimensional cross-correlation operation\n",
    "with a stride of 3 vertically and 2 horizontally.\n",
    "The shaded portions are the output elements as well as the input and kernel tensor elements used for the output computation: $0\\times0+0\\times1+1\\times2+2\\times3=8$, $0\\times0+6\\times1+0\\times2+0\\times3=6$.\n",
    "We can see that when the second element of the first column is generated,\n",
    "the convolution window slides down three rows.\n",
    "The convolution window slides two columns to the right\n",
    "when the second element of the first row is generated.\n",
    "When the convolution window continues to slide two columns to the right on the input,\n",
    "there is no output because the input element cannot fill the window\n",
    "(unless we add another column of padding).\n",
    "\n",
    "![Cross-correlation with strides of 3 and 2 for height and width, respectively.](../img/conv-stride.svg)\n",
    "\n",
    "In general, when the stride for the height is $s_\\textrm{h}$\n",
    "and the stride for the width is $s_\\textrm{w}$, the output shape is\n",
    "\n",
    "$$\\lfloor(n_\\textrm{h}-k_\\textrm{h}+p_\\textrm{h}+s_\\textrm{h})/s_\\textrm{h}\\rfloor \\times \\lfloor(n_\\textrm{w}-k_\\textrm{w}+p_\\textrm{w}+s_\\textrm{w})/s_\\textrm{w}\\rfloor.$$\n",
    "\n",
    "If we set $p_\\textrm{h}=k_\\textrm{h}-1$ and $p_\\textrm{w}=k_\\textrm{w}-1$,\n",
    "then the output shape can be simplified to\n",
    "$\\lfloor(n_\\textrm{h}+s_\\textrm{h}-1)/s_\\textrm{h}\\rfloor \\times \\lfloor(n_\\textrm{w}+s_\\textrm{w}-1)/s_\\textrm{w}\\rfloor$.\n",
    "Going a step further, if the input height and width\n",
    "are divisible by the strides on the height and width,\n",
    "then the output shape will be $(n_\\textrm{h}/s_\\textrm{h}) \\times (n_\\textrm{w}/s_\\textrm{w})$.\n",
    "\n",
    "Below, we set the strides on both the height and width to 2,\n",
    "thus halving the input height and width."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "padding-and-strides-stride-1"
   },
   "source": [
    "conv2d = nn.LazyConv2d(1, kernel_size=3, padding=1, stride=2)\n",
    "comp_conv2d(conv2d, X).shape"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "torch.Size([4, 4])"
     },
     "metadata": {},
     "execution_count": 4
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=padding-and-strides-md-5 fw=all -->\n",
    "\n",
    "Let's look at a slightly more complicated example."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "padding-and-strides-stride-2"
   },
   "source": [
    "conv2d = nn.LazyConv2d(1, kernel_size=(3, 5), padding=(0, 1), stride=(3, 4))\n",
    "comp_conv2d(conv2d, X).shape"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "torch.Size([2, 2])"
     },
     "metadata": {},
     "execution_count": 5
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=padding-and-strides-md-6 fw=all -->\n",
    "\n",
    "## Dilation\n",
    "\n",
    "Padding and stride change where the kernel is applied. A third modification\n",
    "changes the kernel's footprint itself: a *dilated convolution*\n",
    "[@yu2016dilated] places the kernel taps $d$ pixels apart\n",
    "instead of at adjacent positions,\n",
    "where $d$ is called the *dilation* (or *dilation rate*).\n",
    "A $k_\\textrm{h} \\times k_\\textrm{w}$ kernel with dilation $d$\n",
    "still has $k_\\textrm{h} k_\\textrm{w}$ weights,\n",
    "but along each axis the taps now span a window of\n",
    "\n",
    "$$k' = k + (k-1)(d-1) = d(k-1)+1$$\n",
    "\n",
    "pixels, the *effective kernel size*.\n",
    "Setting $d=1$ recovers the ordinary convolution.\n",
    "the figure shows a $3 \\times 3$ kernel at dilations 1 and 2:\n",
    "at dilation 2 the nine taps spread over a $5 \\times 5$ footprint,\n",
    "skipping every other pixel,\n",
    "while the cost of applying the kernel is unchanged.\n",
    "\n",
    "![A 3×3 kernel at dilation 1 and dilation 2: the nine taps spread over a 5×5 footprint while the cost stays fixed.](../img/arch-conv-dilation.svg)\n",
    "\n",
    "For output shapes, a dilated kernel behaves exactly like a dense kernel\n",
    "of its effective size. Substituting $k'$ into the strided formula above\n",
    "gives the general form covering padding, stride, and dilation at once:\n",
    "\n",
    "$$\\lfloor(n_\\textrm{h}-d_\\textrm{h}(k_\\textrm{h}-1)+p_\\textrm{h}+s_\\textrm{h}-1)/s_\\textrm{h}\\rfloor \\times \\lfloor(n_\\textrm{w}-d_\\textrm{w}(k_\\textrm{w}-1)+p_\\textrm{w}+s_\\textrm{w}-1)/s_\\textrm{w}\\rfloor.$$\n",
    "\n",
    "With $d_\\textrm{h}=d_\\textrm{w}=1$ this reduces to the strided formula,\n",
    "and with unit stride and no padding to the $(n-k+1)$ rule we started from.\n",
    "\n",
    "The point of dilation is receptive-field growth on a budget.\n",
    "In the receptive-field formula the equation,\n",
    "each layer contributes $k'_i - 1 = d_i(k_i - 1)$ at stride 1,\n",
    "so doubling the dilation at every layer,\n",
    "$d_i = 1, 2, 4, \\ldots, 2^{L-1}$ for $3 \\times 3$ kernels,\n",
    "yields a receptive field of side $2^{L+1}-1$:\n",
    "it grows exponentially with depth\n",
    "while every layer costs the same nine multiplications per output.\n",
    "The alternative route to a large receptive field, striding,\n",
    "pays for it by shrinking the output.\n",
    "This makes dilation the standard tool for *dense prediction* tasks\n",
    "such as semantic segmentation,\n",
    "where every pixel needs wide context\n",
    "but the output must keep the input's resolution;\n",
    "we will meet it again in the fully convolutional networks\n",
    "of that section.\n",
    "\n",
    "Let's verify the effective-size claim numerically:\n",
    "on our $8 \\times 8$ input,\n",
    "a $3 \\times 3$ kernel at dilation 2\n",
    "produces the same $4 \\times 4$ output\n",
    "as a dense $5 \\times 5$ kernel."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "padding-and-strides-dilation"
   },
   "source": [
    "# Dilation 2 gives the 3x3 kernel a 5x5 footprint, so both convolutions\n",
    "# shrink the 8x8 input to 4x4\n",
    "conv2d = nn.LazyConv2d(1, kernel_size=3, dilation=2)\n",
    "conv5 = nn.LazyConv2d(1, kernel_size=5)\n",
    "comp_conv2d(conv2d, X).shape, comp_conv2d(conv5, X).shape"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(torch.Size([4, 4]), torch.Size([4, 4]))"
     },
     "metadata": {},
     "execution_count": 6
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=padding-and-strides-md-7 fw=all -->\n",
    "\n",
    "## Summary and Discussion\n",
    "\n",
    "Padding can increase the height and width of the output and is often chosen so\n",
    "that input and output have the same spatial shape. It lets boundary pixels\n",
    "affect outputs centered near the boundary, but does not make their use identical\n",
    "to that of interior pixels: a corner pixel still belongs to fewer windows\n",
    "containing real image values. Typically we pick symmetric padding on both sides\n",
    "of the input height and width. In this case we refer to\n",
    "$(p_\\textrm{h}, p_\\textrm{w})$ padding. Most commonly we set\n",
    "$p_\\textrm{h} = p_\\textrm{w}$, in which case we simply state that we choose\n",
    "padding $p$.\n",
    "\n",
    "A similar convention applies to strides. When the vertical stride $s_\\textrm{h}$ and horizontal stride $s_\\textrm{w}$ match, we simply talk about stride $s$. The stride can reduce the resolution of the output, for example reducing the height and width of the output to only $1/n$ of the height and width of the input for $n > 1$. The same shorthand covers dilation: when $d_\\textrm{h} = d_\\textrm{w}$ we speak of dilation $d$. Dilation widens the window each output sees without adding weights or reducing resolution, which is what dense prediction needs. By default, the padding is 0 and the stride and dilation are 1.\n",
    "\n",
    "So far all padding that we discussed simply extended images with zeros. This is cheap, and operators can be engineered to handle it implicitly without allocating a larger tensor, but it is not a neutral choice: zero padding is a *boundary condition*, an assertion that the world outside the image is black. Filters whose window overlaps the border therefore see systematically different inputs from filters in the interior, and the resulting artifacts propagate deep into the feature maps [@Alsallakh.Kokhlikyan.Miglani.ea.2020]. Padding also leaks absolute position: convolution itself cannot tell where in the image it is, but a unit near the border can infer its location from how much zero \"whitespace\" it sees, and trained CNNs do exploit this signal. Alternatives such as reflect padding (mirroring the border rows and columns) or replicate padding (repeating them) remove the artificial black frame; in practice they are reached for when border artifacts become visible, for example in image generation.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Given the final code example in this section with kernel size $(3, 5)$, padding $(0, 1)$, and stride $(3, 4)$, \n",
    "   calculate the output shape to check if it is consistent with the experimental result.\n",
    "1. For audio signals, what does a stride of 2 correspond to?\n",
    "1. Implement mirror padding, i.e., padding where the border values are simply mirrored to extend tensors. \n",
    "1. What are the computational benefits of a stride larger than 1?\n",
    "1. What might be statistical benefits of a stride larger than 1?\n",
    "1. How would you implement a stride of $\\frac{1}{2}$? What does it correspond to? When would this be useful? Compare your answer with the transposed convolutions of that section.\n",
    "1. A network stacks four $3 \\times 3$ convolutions with stride 1 and dilations $1, 2, 4, 8$. Use the equation with each kernel replaced by its effective size to compute the receptive field of one output element. Which pixels inside that field does the output actually depend on? When does this *gridding* effect become a problem, and how would you choose a dilation schedule that avoids it?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=padding-and-strides-md-8 fw=pytorch -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/68)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
