{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=rcnn-md-1 fw=all -->\n",
    "\n",
    "# Region-based CNNs (R-CNNs)\n",
    "\n",
    "Besides single shot multibox detection\n",
    "described in that section,\n",
    "region-based CNNs or regions with CNN features (R-CNNs)\n",
    "are also among many pioneering\n",
    "approaches of\n",
    "applying\n",
    "deep learning to object detection\n",
    "[@Girshick.Donahue.Darrell.ea.2014].\n",
    "In this section, we will introduce\n",
    "the R-CNN and its series of improvements: the fast R-CNN\n",
    "[@Girshick.2015], the faster R-CNN [@Ren.He.Girshick.ea.2015], and the mask R-CNN\n",
    "[@He.Gkioxari.Dollar.ea.2017].\n",
    "Due to limited space, we will only\n",
    "focus on the design of these models.\n",
    "\n",
    "\n",
    "## R-CNNs\n",
    "\n",
    "\n",
    "The *R-CNN* first extracts\n",
    "many (e.g., 2000) *region proposals*\n",
    "from the input image\n",
    "(e.g., anchor boxes can also be considered\n",
    "as region proposals),\n",
    "labeling their classes and bounding boxes (e.g., offsets).\n",
    "[@Girshick.Donahue.Darrell.ea.2014]\n",
    "Then a CNN is used to\n",
    "perform forward propagation on each region proposal\n",
    "to extract its features.\n",
    "Next, features of each region proposal\n",
    "are used for\n",
    "predicting the class and bounding box\n",
    "of this region proposal.\n",
    "\n",
    "\n",
    "![The R-CNN model.](../img/r-cnn.svg)\n",
    "\n",
    "the figure shows the R-CNN model. More concretely, the R-CNN consists of the following four steps:\n",
    "\n",
    "1. Perform *selective search* to extract multiple high-quality region proposals on the input image [@Uijlings.Van-De-Sande.Gevers.ea.2013]. These proposed regions are usually selected at multiple scales with different shapes and sizes. Each region proposal will be labeled with a class and a ground-truth bounding box.\n",
    "1. Choose a pretrained CNN and truncate it before the output layer. Resize each region proposal to the input size required by the network, and output the extracted features for the region proposal through forward propagation.\n",
    "1. Take the extracted features and labeled class of each region proposal as an example. Train multiple support vector machines to classify objects, where each support vector machine individually determines whether the example contains a specific class.\n",
    "1. Take the extracted features and labeled bounding box of each region proposal as an example. Train a linear regression model to predict the ground-truth bounding box.\n",
    "\n",
    "\n",
    "Although the R-CNN model uses pretrained CNNs to effectively extract image features,\n",
    "it is slow.\n",
    "Imagine that we select\n",
    "thousands of region proposals from a single input image:\n",
    "this requires thousands of\n",
    "CNN forward propagations to perform object detection.\n",
    "This massive\n",
    "computing load makes it infeasible to\n",
    "widely use R-CNNs in real-world applications.\n",
    "\n",
    "## Fast R-CNN\n",
    "\n",
    "The main performance bottleneck of\n",
    "an R-CNN lies in\n",
    "the independent CNN forward propagation\n",
    "for each region proposal,\n",
    "without sharing computation.\n",
    "Since these regions usually have\n",
    "overlaps,\n",
    "independent feature extractions lead to\n",
    "much repeated computation.\n",
    "One of the major improvements of\n",
    "the *fast R-CNN* from the\n",
    "R-CNN is that\n",
    "the CNN forward propagation\n",
    "is only performed on\n",
    "the entire image [@Girshick.2015].\n",
    "\n",
    "![The fast R-CNN model.](../img/fast-rcnn.svg)\n",
    "\n",
    "the figure describes the fast R-CNN model. Its major computations are as follows:\n",
    "\n",
    "\n",
    "1. Compared with the R-CNN, in the fast R-CNN the input of the CNN for feature extraction is the entire image, rather than individual region proposals. Moreover, this CNN is trainable. Given an input image, let the shape of the CNN output be $1 \\times c \\times h_1 \\times w_1$.\n",
    "1. Suppose that selective search generates $n$ region proposals. These region proposals (of different shapes) mark regions of interest (of different shapes) on the CNN output. Then these regions of interest further extract features of the same shape (say height $h_2$ and width $w_2$ are specified) in order to be easily concatenated. To achieve this, the fast R-CNN introduces the *region of interest (RoI) pooling* layer: the CNN output and region proposals are input into this layer, outputting concatenated features of shape $n \\times c \\times h_2 \\times w_2$ that are further extracted for all the region proposals.\n",
    "1. Using a fully connected layer, transform the concatenated features into an output of shape $n \\times d$, where $d$ depends on the model design.\n",
    "1. Predict the class and bounding box for each of the $n$ region proposals. More concretely, in class and bounding box prediction, transform the fully connected layer output into an output of shape $n \\times q$ ($q$ is the number of classes) and an output of shape $n \\times 4$, respectively. The class prediction uses softmax regression.\n",
    "\n",
    "\n",
    "The region of interest pooling layer proposed in the fast R-CNN is different from the pooling layer introduced in that section.\n",
    "In the pooling layer,\n",
    "we indirectly control the output shape\n",
    "by specifying sizes of\n",
    "the pooling window, padding, and stride.\n",
    "In contrast,\n",
    "we can directly specify the output shape\n",
    "in the region of interest pooling layer.\n",
    "\n",
    "For example, let's specify\n",
    "the output height and width\n",
    "for each region as $h_2$ and $w_2$, respectively.\n",
    "For any region of interest window\n",
    "of shape $h \\times w$,\n",
    "this window is divided into a $h_2 \\times w_2$ grid\n",
    "of subwindows,\n",
    "where the shape of each subwindow is approximately\n",
    "$(h/h_2) \\times (w/w_2)$.\n",
    "In practice,\n",
    "the height and width of any subwindow shall be rounded up, and the largest element shall be used as output of the subwindow.\n",
    "Therefore, the region of interest pooling layer can extract features of the same shape\n",
    "even when regions of interest have different shapes.\n",
    "\n",
    "\n",
    "As an illustrative example,\n",
    "in the figure,\n",
    "the upper-left $3\\times 3$ region of interest\n",
    "is selected on a $4 \\times 4$ input.\n",
    "For this region of interest,\n",
    "we use a $2\\times 2$ region of interest pooling layer to obtain\n",
    "a $2\\times 2$ output.\n",
    "Note that\n",
    "each of the four divided subwindows\n",
    "contains elements\n",
    "0, 1, 4, and 5 (5 is the maximum);\n",
    "2 and 6 (6 is the maximum);\n",
    "8 and 9 (9 is the maximum);\n",
    "and 10.\n",
    "\n",
    "![A $2\\times 2$ region of interest pooling layer.](../img/roi.svg)\n",
    "\n",
    "Below we demonstrate the computation of the region of interest pooling layer. Suppose that the height and width of the CNN-extracted features `X` are both 4, and there is only a single channel."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "rcnn-fast-r-cnn-1"
   },
   "source": [
    "from d2l import jax as d2l\n",
    "import jax\n",
    "from jax import numpy as jnp\n",
    "import numpy as np\n",
    "\n",
    "X = jnp.arange(16.).reshape(1, 1, 4, 4)\n",
    "X"
   ],
   "execution_count": 1,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Array([[[[ 0.,  1.,  2.,  3.],\n         [ 4.,  5.,  6.,  7.],\n         [ 8.,  9., 10., 11.],\n         [12., 13., 14., 15.]]]], dtype=float32)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=rcnn-md-2 fw=all -->\n",
    "\n",
    "Let's further suppose\n",
    "that  the height and width of the input image are both 40 pixels and that selective search generates two region proposals on this image.\n",
    "Each region proposal\n",
    "is expressed as five elements:\n",
    "its object class followed by the $(x, y)$-coordinates of its upper-left and lower-right corners."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "rcnn-fast-r-cnn-2"
   },
   "source": [
    "rois = jnp.array([[0, 0, 0, 20, 20], [0, 0, 10, 30, 30]])"
   ],
   "execution_count": 2,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=rcnn-md-3 fw=all -->\n",
    "\n",
    "Because the height and width of `X` are $1/10$ of the height and width of the input image,\n",
    "the coordinates of the two region proposals\n",
    "are multiplied by 0.1 according to the specified `spatial_scale` argument.\n",
    "Then the two regions of interest are marked on `X` as `X[:, :, 0:3, 0:3]` and `X[:, :, 1:4, 0:4]`, respectively.\n",
    "Finally in the $2\\times 2$ region of interest pooling,\n",
    "each region of interest is divided\n",
    "into a grid of sub-windows to\n",
    "further extract features of the same shape $2\\times 2$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "rcnn-fast-r-cnn-3"
   },
   "source": [
    "# JAX does not have a built-in ROI pooling operator, so we implement it\n",
    "def roi_pool(X, rois, pooled_size, spatial_scale):\n",
    "    num_rois = rois.shape[0]\n",
    "    c = X.shape[1]\n",
    "    ph, pw = pooled_size\n",
    "    outputs = []\n",
    "    for i in range(num_rois):\n",
    "        roi = rois[i]\n",
    "        batch_idx = int(roi[0])\n",
    "        x1 = int(np.round(float(roi[1]) * spatial_scale))\n",
    "        y1 = int(np.round(float(roi[2]) * spatial_scale))\n",
    "        x2 = int(np.round(float(roi[3]) * spatial_scale))\n",
    "        y2 = int(np.round(float(roi[4]) * spatial_scale))\n",
    "        x2, y2 = max(x2, x1 + 1), max(y2, y1 + 1)\n",
    "        roi_feat = X[batch_idx, :, y1:y2, x1:x2]\n",
    "        # Divide into ph x pw bins and take the max of each\n",
    "        h, w = roi_feat.shape[1], roi_feat.shape[2]\n",
    "        bin_h = np.linspace(0, h, ph + 1).astype(int)\n",
    "        bin_w = np.linspace(0, w, pw + 1).astype(int)\n",
    "        pooled = jnp.zeros((c, ph, pw))\n",
    "        for pi in range(ph):\n",
    "            for pj in range(pw):\n",
    "                sub = roi_feat[:, bin_h[pi]:bin_h[pi+1], bin_w[pj]:bin_w[pj+1]]\n",
    "                pooled = pooled.at[:, pi, pj].set(sub.max(axis=(1, 2)))\n",
    "        outputs.append(pooled)\n",
    "    return jnp.stack(outputs, axis=0).reshape(num_rois, c, ph, pw)\n",
    "\n",
    "roi_pool(X, rois, pooled_size=(2, 2), spatial_scale=0.1)"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Array([[[[ 0.,  1.],\n         [ 4.,  5.]]],\n\n\n       [[[ 4.,  6.],\n         [ 8., 10.]]]], dtype=float32)"
     },
     "metadata": {},
     "execution_count": 3
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=rcnn-md-4 fw=all -->\n",
    "\n",
    "## Faster R-CNN\n",
    "\n",
    "To be more accurate in object detection,\n",
    "the fast R-CNN model\n",
    "usually has to generate\n",
    "a lot of region proposals in selective search.\n",
    "To reduce region proposals\n",
    "without loss of accuracy,\n",
    "the *faster R-CNN*\n",
    "proposes to replace selective search with a *region proposal network* [@Ren.He.Girshick.ea.2015].\n",
    "\n",
    "\n",
    "![The faster R-CNN model.](../img/faster-rcnn.svg)\n",
    "\n",
    "\n",
    "the figure shows the faster R-CNN model. Compared with the fast R-CNN,\n",
    "the faster R-CNN only changes\n",
    "the region proposal method\n",
    "from selective search to a region proposal network.\n",
    "The rest of the model remains\n",
    "unchanged.\n",
    "The region proposal network\n",
    "works in the following steps:\n",
    "\n",
    "1. Use a $3\\times 3$ convolutional layer with padding of 1 to transform the CNN output to a new output with $c$ channels. In this way, each unit along the spatial dimensions of the CNN-extracted feature maps gets a new feature vector of length $c$.\n",
    "1. Centered on each pixel of the feature maps, generate multiple anchor boxes of different scales and aspect ratios and label them.\n",
    "1. Using the length-$c$ feature vector at the center of each anchor box, predict the binary class (background or objects) and bounding box for this anchor box.\n",
    "1. Consider those predicted bounding boxes whose  predicted classes are objects. Remove overlapped results using non-maximum suppression. The remaining  predicted bounding boxes for objects are the region proposals required by the region of interest pooling layer.\n",
    "\n",
    "\n",
    "It is worth noting that,\n",
    "as part of the faster R-CNN model,\n",
    "the region\n",
    "proposal network is jointly trained\n",
    "with the rest of the model.\n",
    "In other words, the objective function of\n",
    "the faster R-CNN includes\n",
    "not only the class and bounding box prediction\n",
    "in object detection,\n",
    "but also the binary class and bounding box prediction\n",
    "of anchor boxes in the region proposal network.\n",
    "As a result of the end-to-end training,\n",
    "the region proposal network learns\n",
    "how to generate high-quality region proposals,\n",
    "so as to stay accurate in object detection\n",
    "with a reduced number of region proposals\n",
    "that are learned from data.\n",
    "\n",
    "\n",
    "## Mask R-CNN\n",
    "\n",
    "In the training dataset,\n",
    "if pixel-level positions of object\n",
    "are also labeled on images,\n",
    "the *mask R-CNN* can effectively leverage\n",
    "such detailed labels\n",
    "to further improve the accuracy of object detection [@He.Gkioxari.Dollar.ea.2017].\n",
    "\n",
    "\n",
    "![The mask R-CNN model.](../img/mask-rcnn.svg)\n",
    "\n",
    "As shown in the figure,\n",
    "the mask R-CNN\n",
    "is modified based on the faster R-CNN.\n",
    "Specifically,\n",
    "the mask R-CNN replaces the\n",
    "region of interest pooling layer with the\n",
    "*region of interest (RoI) alignment* layer.\n",
    "This region of interest alignment layer\n",
    "uses bilinear interpolation\n",
    "to preserve the spatial information on the feature maps, which is more suitable for pixel-level prediction.\n",
    "The output of this layer\n",
    "contains feature maps of the same shape\n",
    "for all the regions of interest.\n",
    "They are used\n",
    "to predict\n",
    "not only the class and bounding box for each region of interest,\n",
    "but also the pixel-level position of the object through an additional fully convolutional network.\n",
    "More details on using a fully convolutional network to predict pixel-level semantics of an image\n",
    "will be provided\n",
    "in subsequent sections of this chapter.\n",
    "\n",
    "\n",
    "## Summary\n",
    "\n",
    "\n",
    "* The R-CNN extracts many region proposals from the input image, uses a CNN to perform forward propagation on each region proposal to extract its features, then uses these features to predict the class and bounding box of this region proposal.\n",
    "* One of the major improvements of  the fast R-CNN from the R-CNN is that the CNN forward propagation is only performed on  the entire image. It also introduces the region of interest pooling layer, so that features of the same shape can be further extracted for regions of interest that have different shapes.\n",
    "* The faster R-CNN replaces the selective search used in the fast R-CNN with a jointly trained region proposal network, so that the former can stay accurate in object detection with a reduced number of region proposals.\n",
    "* Based on the faster R-CNN, the mask R-CNN additionally introduces a fully convolutional network, so as to leverage pixel-level labels to further improve the accuracy of object detection.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Can we frame object detection as a single regression problem, such as predicting bounding boxes and class probabilities? You may refer to the design of the YOLO model [@Redmon.Divvala.Girshick.ea.2016].\n",
    "1. Compare single shot multibox detection with the methods introduced in this section. What are their major differences? You may refer to Figure 2 of @Zhao.Zheng.Xu.ea.2019 ."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=rcnn-md-5 fw=jax -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/1409)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-jax",
   "display_name": "d2l (JAX)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
