{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-1 fw=all -->\n",
    "\n",
    "# Anchor Boxes\n",
    "\n",
    "\n",
    "Object detection algorithms usually\n",
    "sample a large number of regions in the input image, determine whether these regions contain\n",
    "objects of interest, and adjust the boundaries\n",
    "of the regions so as to predict the\n",
    "*ground-truth bounding boxes*\n",
    "of the objects more accurately.\n",
    "Different models may adopt\n",
    "different region sampling schemes. \n",
    "Here we introduce one such method:\n",
    "it generates multiple bounding boxes with varying scales and aspect ratios centered on each pixel. \n",
    "These bounding boxes are called *anchor boxes*.\n",
    "We will design an object detection model\n",
    "based on anchor boxes in that section.\n",
    "\n",
    "First, let's modify the printing accuracy\n",
    "just for more concise outputs."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-anchor-boxes"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import torch as d2l\n",
    "import torch\n",
    "\n",
    "torch.set_printoptions(2)  # Simplify printing accuracy"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-2 fw=all -->\n",
    "\n",
    "## Generating Multiple Anchor Boxes\n",
    "\n",
    "Suppose that the input image has a height of $h$ and width of $w$. \n",
    "We generate anchor boxes with different shapes centered on each pixel of the image.\n",
    "Let the *scale* be $s\\in (0, 1]$ and\n",
    "the *aspect ratio* (ratio of width to height) is $r > 0$. \n",
    "Then the width and height of the anchor box are $ws\\sqrt{r}$ and $hs/\\sqrt{r}$, respectively.\n",
    "Note that when the center position is given, an anchor box with known width and height is determined.\n",
    "\n",
    "To generate multiple anchor boxes with different shapes,\n",
    "let's set a series of scales\n",
    "$s_1,\\ldots, s_n$ and \n",
    "a series of aspect ratios $r_1,\\ldots, r_m$.\n",
    "When using all the combinations of these scales and aspect ratios with each pixel as the center,\n",
    "the input image will have a total of $whnm$ anchor boxes. Although these anchor boxes may cover all the\n",
    "ground-truth bounding boxes, the computational complexity is easily too high.\n",
    "In practice,\n",
    "we can only consider those combinations\n",
    "containing $s_1$ or $r_1$:\n",
    "\n",
    "$$(s_1, r_1), (s_1, r_2), \\ldots, (s_1, r_m), (s_2, r_1), (s_3, r_1), \\ldots, (s_n, r_1).$$\n",
    "\n",
    "That is to say, the number of anchor boxes centered on the same pixel is $n+m-1$. For the entire input image, we will generate a total of $wh(n+m-1)$ anchor boxes.\n",
    "\n",
    "The above method of generating anchor boxes is implemented in the following `multibox_prior` function. We specify the input image, a list of scales, and a list of aspect ratios, then this function will return all the anchor boxes."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-generating-multiple-anchor-boxes-1"
   },
   "source": [
    "\n",
    "def multibox_prior(data, sizes, ratios):\n",
    "    \"\"\"Generate anchor boxes with different shapes centered on each pixel.\"\"\"\n",
    "    in_height, in_width = data.shape[-2:]\n",
    "    device, num_sizes, num_ratios = data.device, len(sizes), len(ratios)\n",
    "    boxes_per_pixel = (num_sizes + num_ratios - 1)\n",
    "    size_tensor = d2l.tensor(sizes, device=device)\n",
    "    ratio_tensor = d2l.tensor(ratios, device=device)\n",
    "    # Offsets are required to move the anchor to the center of a pixel. Since\n",
    "    # a pixel has height=1 and width=1, we choose to offset our centers by 0.5\n",
    "    offset_h, offset_w = 0.5, 0.5\n",
    "    steps_h = 1.0 / in_height  # Scaled steps in y axis\n",
    "    steps_w = 1.0 / in_width  # Scaled steps in x axis\n",
    "\n",
    "    # Generate all center points for the anchor boxes\n",
    "    center_h = (torch.arange(in_height, device=device) + offset_h) * steps_h\n",
    "    center_w = (torch.arange(in_width, device=device) + offset_w) * steps_w\n",
    "    shift_y, shift_x = torch.meshgrid(center_h, center_w, indexing='ij')\n",
    "    shift_y, shift_x = shift_y.reshape(-1), shift_x.reshape(-1)\n",
    "\n",
    "    # Generate `boxes_per_pixel` number of heights and widths that are later\n",
    "    # used to create anchor box corner coordinates (xmin, xmax, ymin, ymax)\n",
    "    w = torch.cat((size_tensor * torch.sqrt(ratio_tensor[0]),\n",
    "                   sizes[0] * torch.sqrt(ratio_tensor[1:])))\\\n",
    "                   * in_height / in_width  # Handle rectangular inputs\n",
    "    h = torch.cat((size_tensor / torch.sqrt(ratio_tensor[0]),\n",
    "                   sizes[0] / torch.sqrt(ratio_tensor[1:])))\n",
    "    # Divide by 2 to get half height and half width\n",
    "    anchor_manipulations = torch.stack((-w, -h, w, h)).T.repeat(\n",
    "                                        in_height * in_width, 1) / 2\n",
    "\n",
    "    # Each center point will have `boxes_per_pixel` number of anchor boxes, so\n",
    "    # generate a grid of all anchor box centers with `boxes_per_pixel` repeats\n",
    "    out_grid = torch.stack([shift_x, shift_y, shift_x, shift_y],\n",
    "                dim=1).repeat_interleave(boxes_per_pixel, dim=0)\n",
    "    output = out_grid + anchor_manipulations\n",
    "    return output.unsqueeze(0)"
   ],
   "execution_count": 2,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-3 fw=all -->\n",
    "\n",
    "We can see that the shape of the returned anchor box variable `Y` is\n",
    "(batch size, number of anchor boxes, 4)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-generating-multiple-anchor-boxes-2"
   },
   "source": [
    "img = d2l.plt.imread('../img/catdog.jpg')\n",
    "h, w = img.shape[:2]\n",
    "\n",
    "print(h, w)\n",
    "X = torch.rand(size=(1, 3, h, w))  # Construct input data\n",
    "Y = multibox_prior(X, sizes=[0.75, 0.5, 0.25], ratios=[1, 2, 0.5])\n",
    "Y.shape"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "561 728\n"
     ]
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "torch.Size([1, 2042040, 4])"
     },
     "metadata": {},
     "execution_count": 3
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-4 fw=all -->\n",
    "\n",
    "After changing the shape of the anchor box variable `Y` to (image height, image width, number of anchor boxes centered on the same pixel, 4),\n",
    "we can obtain all the anchor boxes centered on a specified pixel position.\n",
    "In the following,\n",
    "we access the first anchor box centered on (250, 250). It has four elements: the $(x, y)$-axis coordinates at the upper-left corner and the $(x, y)$-axis coordinates at the lower-right corner of the anchor box.\n",
    "The coordinate values of both axes\n",
    "are divided by the width and height of the image, respectively."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-generating-multiple-anchor-boxes-3"
   },
   "source": [
    "boxes = Y.reshape(h, w, 5, 4)\n",
    "boxes[250, 250, 0, :]"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([0.06, 0.07, 0.63, 0.82])"
     },
     "metadata": {},
     "execution_count": 4
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-5 fw=all -->\n",
    "\n",
    "In order to show all the anchor boxes centered on one pixel in the image,\n",
    "we define the following `show_bboxes` function to draw multiple bounding boxes on the image."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-generating-multiple-anchor-boxes-4"
   },
   "source": [
    "\n",
    "def show_bboxes(axes, bboxes, labels=None, colors=None):\n",
    "    \"\"\"Show bounding boxes.\"\"\"\n",
    "\n",
    "    def make_list(obj, default_values=None):\n",
    "        if obj is None:\n",
    "            obj = default_values\n",
    "        elif not isinstance(obj, (list, tuple)):\n",
    "            obj = [obj]\n",
    "        return obj\n",
    "\n",
    "    labels = make_list(labels)\n",
    "    colors = make_list(colors, ['b', 'g', 'r', 'm', 'c'])\n",
    "    for i, bbox in enumerate(bboxes):\n",
    "        color = colors[i % len(colors)]\n",
    "        rect = d2l.bbox_to_rect(d2l.numpy(bbox), color)\n",
    "        axes.add_patch(rect)\n",
    "        if labels and len(labels) > i:\n",
    "            text_color = 'k' if color == 'w' else 'w'\n",
    "            axes.text(rect.xy[0], rect.xy[1], labels[i],\n",
    "                      va='center', ha='center', fontsize=9, color=text_color,\n",
    "                      bbox=dict(facecolor=color, lw=0))"
   ],
   "execution_count": 5,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-6 fw=all -->\n",
    "\n",
    "As we just saw, the coordinate values of the $x$ and $y$ axes in the variable `boxes` have been divided by the width and height of the image, respectively.\n",
    "When drawing anchor boxes,\n",
    "we need to restore their original coordinate values;\n",
    "thus, we define variable `bbox_scale` below. \n",
    "Now, we can draw all the anchor boxes centered on (250, 250) in the image.\n",
    "As you can see, the blue anchor box with a scale of 0.75 and an aspect ratio of 1 well\n",
    "surrounds the dog in the image."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-generating-multiple-anchor-boxes-5"
   },
   "source": [
    "d2l.set_figsize()\n",
    "bbox_scale = d2l.tensor((w, h, w, h))\n",
    "fig = d2l.plt.imshow(img)\n",
    "show_bboxes(fig.axes, boxes[250, 250, :, :] * bbox_scale,\n",
    "            ['s=0.75, r=1', 's=0.5, r=1', 's=0.25, r=1', 's=0.75, r=2',\n",
    "             's=0.75, r=0.5'])"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"233.229634pt\" height=\"185.525265pt\" viewBox=\"0 0 233.229634 185.525265\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:40:10.057964</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M -0 185.525265 \nL 233.229634 185.525265 \nL 233.229634 0 \nL -0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 46.170811 161.64714 \nL 226.029634 161.64714 \nL 226.029634 23.04714 \nL 46.170811 23.04714 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#pa3186a1d5a)\">\n    <image xlink:href=\"data:image/png;base64,\[encoded data, 75929 characters]\" id=\"image3ae6b00c18\" transform=\"scale(1 -1) translate(0 -138.96)\" x=\"46.170811\" y=\"-22.68714\" width=\"180\" height=\"138.96\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 56.207578 33.083903 \nL 160.157575 33.083903 \nL 160.157575 137.033897 \nL 56.207578 137.033897 \nL 56.207578 33.083903 \nz\n\" clip-path=\"url(#pa3186a1d5a)\" style=\"fill: none; stroke: #0000ff; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 73.532577 50.408903 \nL 142.832568 50.408903 \nL 142.832568 119.708897 \nL 73.532577 119.708897 \nL 73.532577 50.408903 \nz\n\" clip-path=\"url(#pa3186a1d5a)\" style=\"fill: none; stroke: #008000; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 90.857575 67.733904 \nL 125.507575 67.733904 \nL 125.507575 102.383897 \nL 90.857575 102.383897 \nL 90.857575 67.733904 \nz\n\" clip-path=\"url(#pa3186a1d5a)\" style=\"fill: none; stroke: #ff0000; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 34.678828 48.307029 \nL 181.686345 48.307029 \nL 181.686345 121.810782 \nL 34.678828 121.810782 \nL 34.678828 48.307029 \nz\n\" clip-path=\"url(#pa3186a1d5a)\" style=\"fill: none; stroke: #bf00bf; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_7\">\n    <path d=\"M 71.430702 11.555156 \nL 144.934445 11.555156 \nL 144.934445 158.562644 \nL 71.430702 158.562644 \nL 71.430702 11.555156 \nz\n\" clip-path=\"url(#pa3186a1d5a)\" style=\"fill: none; stroke: #00bfbf; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <defs>\n       <path id=\"mefb627add6\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mefb627add6\" x=\"46.29434\" y=\"161.64714\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0 -->\n      <g transform=\"translate(43.11309 176.245577) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_2\">\n      <g>\n       <use xlink:href=\"#mefb627add6\" x=\"95.706105\" y=\"161.64714\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 200 -->\n      <g transform=\"translate(86.162355 176.245577) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_3\">\n      <g>\n       <use xlink:href=\"#mefb627add6\" x=\"145.117869\" y=\"161.64714\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 400 -->\n      <g transform=\"translate(135.574119 176.245577) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#mefb627add6\" x=\"194.529634\" y=\"161.64714\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 600 -->\n      <g transform=\"translate(184.985884 176.245577) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-36\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_5\">\n      <defs>\n       <path id=\"m9f02c4003e\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m9f02c4003e\" x=\"46.170811\" y=\"23.170669\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 0 -->\n      <g transform=\"translate(32.808311 26.969888) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m9f02c4003e\" x=\"46.170811\" y=\"47.876551\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 100 -->\n      <g transform=\"translate(20.083311 51.67577) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m9f02c4003e\" x=\"46.170811\" y=\"72.582434\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 200 -->\n      <g transform=\"translate(20.083311 76.381653) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m9f02c4003e\" x=\"46.170811\" y=\"97.288316\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 300 -->\n      <g transform=\"translate(20.083311 101.087535) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-33\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m9f02c4003e\" x=\"46.170811\" y=\"121.994199\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 400 -->\n      <g transform=\"translate(20.083311 125.793417) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-34\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m9f02c4003e\" x=\"46.170811\" y=\"146.700081\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 500 -->\n      <g transform=\"translate(20.083311 150.4993) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-35\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_8\">\n    <path d=\"M 46.170811 161.64714 \nL 46.170811 23.04714 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_9\">\n    <path d=\"M 226.029634 161.64714 \nL 226.029634 23.04714 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_10\">\n    <path d=\"M 46.170811 161.64714 \nL 226.029634 161.64714 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_11\">\n    <path d=\"M 46.170811 23.04714 \nL 226.029634 23.04714 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"text_11\">\n    <g id=\"patch_12\">\n     <path d=\"M 24.76875 41.399059 \nL 87.646406 41.399059 \nL 87.646406 24.768746 \nL 24.76875 24.768746 \nz\n\" style=\"fill: #0000ff\"/>\n    </g>\n    <!-- s=0.75, r=1 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(28.72875 35.56734) scale(0.09 -0.09)\">\n     <defs>\n      <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-3d\" d=\"M 678 2906 \nL 4684 2906 \nL 4684 2381 \nL 678 2381 \nL 678 2906 \nz\nM 678 1631 \nL 4684 1631 \nL 4684 1100 \nL 678 1100 \nL 678 1631 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-37\" d=\"M 525 4666 \nL 3525 4666 \nL 3525 4397 \nL 1831 0 \nL 1172 0 \nL 2766 4134 \nL 525 4134 \nL 525 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-2c\" d=\"M 750 794 \nL 1409 794 \nL 1409 256 \nL 897 -744 \nL 494 -744 \nL 750 256 \nL 750 794 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-73\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(52.099609 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(135.888672 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(199.511719 0)\"/>\n     <use xlink:href=\"#DejaVuSans-37\" transform=\"translate(231.298828 0)\"/>\n     <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(294.921875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2c\" transform=\"translate(358.544922 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(390.332031 0)\"/>\n     <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(422.119141 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(463.232422 0)\"/>\n     <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(547.021484 0)\"/>\n    </g>\n   </g>\n   <g id=\"text_12\">\n    <g id=\"patch_13\">\n     <path d=\"M 44.956874 58.724059 \nL 102.10828 58.724059 \nL 102.10828 42.093746 \nL 44.956874 42.093746 \nz\n\" style=\"fill: #008000\"/>\n    </g>\n    <!-- s=0.5, r=1 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(48.916874 52.89234) scale(0.09 -0.09)\">\n     <use xlink:href=\"#DejaVuSans-73\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(52.099609 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(135.888672 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(199.511719 0)\"/>\n     <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(231.298828 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2c\" transform=\"translate(294.921875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(326.708984 0)\"/>\n     <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(358.496094 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(399.609375 0)\"/>\n     <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(483.398438 0)\"/>\n    </g>\n   </g>\n   <g id=\"text_13\">\n    <g id=\"patch_14\">\n     <path d=\"M 59.418747 76.049061 \nL 122.296403 76.049061 \nL 122.296403 59.418748 \nL 59.418747 59.418748 \nz\n\" style=\"fill: #ff0000\"/>\n    </g>\n    <!-- s=0.25, r=1 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(63.378747 70.217342) scale(0.09 -0.09)\">\n     <use xlink:href=\"#DejaVuSans-73\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(52.099609 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(135.888672 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(199.511719 0)\"/>\n     <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(231.298828 0)\"/>\n     <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(294.921875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2c\" transform=\"translate(358.544922 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(390.332031 0)\"/>\n     <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(422.119141 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(463.232422 0)\"/>\n     <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(547.021484 0)\"/>\n    </g>\n   </g>\n   <g id=\"text_14\">\n    <g id=\"patch_15\">\n     <path d=\"M 3.24 56.622185 \nL 66.117656 56.622185 \nL 66.117656 39.991873 \nL 3.24 39.991873 \nz\n\" style=\"fill: #bf00bf\"/>\n    </g>\n    <!-- s=0.75, r=2 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(7.2 50.790466) scale(0.09 -0.09)\">\n     <use xlink:href=\"#DejaVuSans-73\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(52.099609 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(135.888672 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(199.511719 0)\"/>\n     <use xlink:href=\"#DejaVuSans-37\" transform=\"translate(231.298828 0)\"/>\n     <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(294.921875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2c\" transform=\"translate(358.544922 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(390.332031 0)\"/>\n     <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(422.119141 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(463.232422 0)\"/>\n     <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(547.021484 0)\"/>\n    </g>\n   </g>\n   <g id=\"text_15\">\n    <g id=\"patch_16\">\n     <path d=\"M 35.698592 19.870313 \nL 107.162811 19.870313 \nL 107.162811 3.24 \nL 35.698592 3.24 \nz\n\" style=\"fill: #00bfbf\"/>\n    </g>\n    <!-- s=0.75, r=0.5 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(39.658592 14.038594) scale(0.09 -0.09)\">\n     <use xlink:href=\"#DejaVuSans-73\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(52.099609 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(135.888672 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(199.511719 0)\"/>\n     <use xlink:href=\"#DejaVuSans-37\" transform=\"translate(231.298828 0)\"/>\n     <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(294.921875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2c\" transform=\"translate(358.544922 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(390.332031 0)\"/>\n     <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(422.119141 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(463.232422 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(547.021484 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(610.644531 0)\"/>\n     <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(642.431641 0)\"/>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"pa3186a1d5a\">\n   <rect x=\"46.170811\" y=\"23.04714\" width=\"179.858824\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-7 fw=all -->\n",
    "\n",
    "## Intersection over Union (IoU)\n",
    "\n",
    "We just mentioned that an anchor box \"well\" surrounds the dog in the image.\n",
    "If the ground-truth bounding box of the object is known, how can \"well\" here be quantified?\n",
    "Intuitively, we can measure the similarity between\n",
    "the anchor box and the ground-truth bounding box.\n",
    "We know that the *Jaccard index* can measure the similarity between two sets. Given sets $\\mathcal{A}$ and $\\mathcal{B}$, their Jaccard index is the size of their intersection divided by the size of their union:\n",
    "\n",
    "$$J(\\mathcal{A},\\mathcal{B}) = \\frac{\\left|\\mathcal{A} \\cap \\mathcal{B}\\right|}{\\left| \\mathcal{A} \\cup \\mathcal{B}\\right|}.$$\n",
    "\n",
    "\n",
    "In fact, we can consider the pixel area of any bounding box as a set of pixels. \n",
    "In this way, we can measure the similarity of the two bounding boxes by the Jaccard index of their pixel sets. For two bounding boxes, we usually refer their Jaccard index as *intersection over union* (*IoU*), which is the ratio of their intersection area to their union area, as shown in the figure.\n",
    "The range of an IoU is between 0 and 1:\n",
    "0 means that two bounding boxes do not overlap at all,\n",
    "while 1 indicates that the two bounding boxes are equal.\n",
    "\n",
    "![IoU is the ratio of the intersection area to the union area of two bounding boxes.](../img/iou.svg)\n",
    "\n",
    "For the remainder of this section, we will use IoU to measure the similarity between anchor boxes and ground-truth bounding boxes, and between different anchor boxes.\n",
    "Given two lists of anchor or bounding boxes,\n",
    "the following `box_iou` computes their pairwise IoU\n",
    "across these two lists."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-intersection-over-union-iou"
   },
   "source": [
    "\n",
    "def box_iou(boxes1, boxes2):\n",
    "    \"\"\"Compute pairwise IoU across two lists of anchor or bounding boxes.\"\"\"\n",
    "    box_area = lambda boxes: ((boxes[:, 2] - boxes[:, 0]) *\n",
    "                              (boxes[:, 3] - boxes[:, 1]))\n",
    "    # Shape of `boxes1`, `boxes2`, `areas1`, `areas2`: (no. of boxes1, 4),\n",
    "    # (no. of boxes2, 4), (no. of boxes1,), (no. of boxes2,)\n",
    "    areas1 = box_area(boxes1)\n",
    "    areas2 = box_area(boxes2)\n",
    "    # Shape of `inter_upperlefts`, `inter_lowerrights`, `inters`: (no. of\n",
    "    # boxes1, no. of boxes2, 2)\n",
    "    inter_upperlefts = torch.max(boxes1[:, None, :2], boxes2[:, :2])\n",
    "    inter_lowerrights = torch.min(boxes1[:, None, 2:], boxes2[:, 2:])\n",
    "    inters = (inter_lowerrights - inter_upperlefts).clamp(min=0)\n",
    "    # Shape of `inter_areas` and `union_areas`: (no. of boxes1, no. of boxes2)\n",
    "    inter_areas = inters[:, :, 0] * inters[:, :, 1]\n",
    "    union_areas = areas1[:, None] + areas2 - inter_areas\n",
    "    return inter_areas / union_areas"
   ],
   "execution_count": 7,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-8 fw=all -->\n",
    "\n",
    "## Labeling Anchor Boxes in Training Data\n",
    "\n",
    "\n",
    "In a training dataset,\n",
    "we consider each anchor box as a training example.\n",
    "In order to train an object detection model,\n",
    "we need *class* and *offset* labels for each anchor box,\n",
    "where the former is\n",
    "the class of the object relevant to the anchor box\n",
    "and the latter is the offset\n",
    "of the ground-truth bounding box relative to the anchor box.\n",
    "During the prediction,\n",
    "for each image\n",
    "we generate multiple anchor boxes,\n",
    "predict classes and offsets for all the anchor boxes,\n",
    "adjust their positions according to the predicted offsets to obtain the predicted bounding boxes,\n",
    "and finally only output those \n",
    "predicted bounding boxes that satisfy certain criteria.\n",
    "\n",
    "\n",
    "As we know, an object detection training set\n",
    "comes with labels for\n",
    "locations of *ground-truth bounding boxes*\n",
    "and classes of their surrounded objects.\n",
    "To label any generated *anchor box*,\n",
    "we refer to the labeled\n",
    "location and class of its *assigned* ground-truth bounding box that is closest to the anchor box.\n",
    "In the following,\n",
    "we describe an algorithm for assigning\n",
    "closest ground-truth bounding boxes to anchor boxes. \n",
    "\n",
    "### Assigning Ground-Truth Bounding Boxes to Anchor Boxes\n",
    "\n",
    "Given an image,\n",
    "suppose that the anchor boxes are $A_1, A_2, \\ldots, A_{n_a}$ and the ground-truth bounding boxes are $B_1, B_2, \\ldots, B_{n_b}$, where $n_a \\geq n_b$.\n",
    "Let's define a matrix $\\mathbf{X} \\in \\mathbb{R}^{n_a \\times n_b}$, whose element $x_{ij}$ in the $i^\\textrm{th}$ row and $j^\\textrm{th}$ column is the IoU of the anchor box $A_i$ and the ground-truth bounding box $B_j$. The algorithm consists of the following steps:\n",
    "\n",
    "1. Find the largest element in matrix $\\mathbf{X}$ and denote its row and column indices as $i_1$ and $j_1$, respectively. Then the ground-truth bounding box $B_{j_1}$ is assigned to the anchor box $A_{i_1}$. This is quite intuitive because $A_{i_1}$ and $B_{j_1}$ are the closest among all the pairs of anchor boxes and ground-truth bounding boxes. After the first assignment, discard all the elements in the ${i_1}^\\textrm{th}$ row and the ${j_1}^\\textrm{th}$ column in matrix $\\mathbf{X}$. \n",
    "1. Find the largest of the remaining elements in matrix $\\mathbf{X}$ and denote its row and column indices as $i_2$ and $j_2$, respectively. We assign ground-truth bounding box $B_{j_2}$ to anchor box $A_{i_2}$ and discard all the elements in the ${i_2}^\\textrm{th}$ row and the ${j_2}^\\textrm{th}$ column in matrix $\\mathbf{X}$.\n",
    "1. At this point, elements in two rows and two columns in  matrix $\\mathbf{X}$ have been discarded. We proceed until all elements in $n_b$ columns in matrix $\\mathbf{X}$ are discarded. At this time, we have assigned a ground-truth bounding box to each of $n_b$ anchor boxes.\n",
    "1. Only traverse through the remaining $n_a - n_b$ anchor boxes. For example, given any anchor box $A_i$, find the ground-truth bounding box $B_j$ with the largest IoU with $A_i$ throughout the $i^\\textrm{th}$ row of matrix $\\mathbf{X}$, and assign $B_j$ to $A_i$ only if this IoU is greater than a predefined threshold.\n",
    "\n",
    "Let's illustrate the above algorithm using a concrete\n",
    "example.\n",
    "As shown in the figure (left), assuming that the maximum value in matrix $\\mathbf{X}$ is $x_{23}$, we assign the ground-truth bounding box $B_3$ to the anchor box $A_2$.\n",
    "Then, we discard all the elements in row 2 and column 3 of the matrix, find the largest $x_{71}$ in the remaining  elements (shaded area), and assign the ground-truth bounding box $B_1$ to the anchor box $A_7$. \n",
    "Next, as shown in the figure (middle), discard all the elements in row 7 and column 1 of the matrix, find the largest $x_{54}$ in the remaining  elements (shaded area), and assign the ground-truth bounding box $B_4$ to the anchor box $A_5$. \n",
    "Finally, as shown in the figure (right), discard all the elements in row 5 and column 4 of the matrix, find the largest $x_{92}$ in the remaining elements (shaded area), and assign the ground-truth bounding box $B_2$ to the anchor box $A_9$.\n",
    "After that, we only need to traverse through\n",
    "the remaining anchor boxes $A_1, A_3, A_4, A_6, A_8$ and determine whether to assign them ground-truth bounding boxes according to the threshold.\n",
    "\n",
    "![Assigning ground-truth bounding boxes to anchor boxes.](../img/anchor-label.svg)\n",
    "\n",
    "This algorithm is implemented in the following `assign_anchor_to_bbox` function. Note that this routine and the `nms` function below are written as explicit per-box Python loops to mirror the algorithm step by step for teaching; production code should instead use a vectorized/library routine such as `torchvision.ops.batched_nms`, since each in-loop `argmax` forces a device-to-host synchronization on every iteration."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-assigning-ground-truth-bounding-boxes-to-anchor-boxes"
   },
   "source": [
    "\n",
    "def assign_anchor_to_bbox(ground_truth, anchors, device, iou_threshold=0.5):\n",
    "    \"\"\"Assign closest ground-truth bounding boxes to anchor boxes.\"\"\"\n",
    "    num_anchors, num_gt_boxes = anchors.shape[0], ground_truth.shape[0]\n",
    "    # Element x_ij in the i-th row and j-th column is the IoU of the anchor\n",
    "    # box i and the ground-truth bounding box j\n",
    "    jaccard = box_iou(anchors, ground_truth)\n",
    "    # Initialize the tensor to hold the assigned ground-truth bounding box for\n",
    "    # each anchor\n",
    "    anchors_bbox_map = torch.full((num_anchors,), -1, dtype=torch.long,\n",
    "                                  device=device)\n",
    "    # Assign ground-truth bounding boxes according to the threshold\n",
    "    max_ious, indices = torch.max(jaccard, dim=1)\n",
    "    anc_i = torch.nonzero(max_ious >= iou_threshold).reshape(-1)\n",
    "    box_j = indices[max_ious >= iou_threshold]\n",
    "    anchors_bbox_map[anc_i] = box_j\n",
    "    col_discard = torch.full((num_anchors,), -1)\n",
    "    row_discard = torch.full((num_gt_boxes,), -1)\n",
    "    for _ in range(num_gt_boxes):\n",
    "        max_idx = torch.argmax(jaccard)  # Find the largest IoU\n",
    "        box_idx = (max_idx % num_gt_boxes).long()\n",
    "        anc_idx = torch.div(max_idx, num_gt_boxes, rounding_mode='floor')\n",
    "        anchors_bbox_map[anc_idx] = box_idx\n",
    "        jaccard[:, box_idx] = col_discard\n",
    "        jaccard[anc_idx, :] = row_discard\n",
    "    return anchors_bbox_map"
   ],
   "execution_count": 8,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-9 fw=all -->\n",
    "\n",
    "### Labeling Classes and Offsets\n",
    "\n",
    "Now we can label the class and offset for each anchor box. Suppose that an anchor box $A$ is assigned\n",
    "a ground-truth bounding box $B$. \n",
    "On the one hand,\n",
    "the class of the anchor box $A$ will be\n",
    "labeled as that of $B$.\n",
    "On the other hand,\n",
    "the offset of the anchor box $A$ \n",
    "will be labeled according to the \n",
    "relative position between\n",
    "the central coordinates of $B$ and $A$\n",
    "together with the relative size between\n",
    "these two boxes.\n",
    "Given varying\n",
    "positions and sizes of different boxes in the dataset,\n",
    "we can apply transformations\n",
    "to those relative positions and sizes\n",
    "that may lead to \n",
    "more uniformly distributed offsets\n",
    "that are easier to fit.\n",
    "Here we describe a common transformation.\n",
    "Given the central coordinates of $A$ and $B$ as $(x_a, y_a)$ and $(x_b, y_b)$, \n",
    "their widths as $w_a$ and $w_b$, \n",
    "and their heights as $h_a$ and $h_b$, respectively. \n",
    "We may label the offset of $A$ as\n",
    "\n",
    "$$\\left( \\frac{ \\frac{x_b - x_a}{w_a} - \\mu_x }{\\sigma_x},\n",
    "\\frac{ \\frac{y_b - y_a}{h_a} - \\mu_y }{\\sigma_y},\n",
    "\\frac{ \\log \\frac{w_b}{w_a} - \\mu_w }{\\sigma_w},\n",
    "\\frac{ \\log \\frac{h_b}{h_a} - \\mu_h }{\\sigma_h}\\right),$$\n",
    "\n",
    "where default values of the constants are $\\mu_x = \\mu_y = \\mu_w = \\mu_h = 0, \\sigma_x=\\sigma_y=0.1$, and $\\sigma_w=\\sigma_h=0.2$.\n",
    "This transformation is implemented below in the `offset_boxes` function."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-labeling-classes-and-offsets-1"
   },
   "source": [
    "\n",
    "def offset_boxes(anchors, assigned_bb, eps=1e-6):\n",
    "    \"\"\"Transform for anchor box offsets.\"\"\"\n",
    "    c_anc = d2l.box_corner_to_center(anchors)\n",
    "    c_assigned_bb = d2l.box_corner_to_center(assigned_bb)\n",
    "    offset_xy = 10 * (c_assigned_bb[:, :2] - c_anc[:, :2]) / c_anc[:, 2:]\n",
    "    offset_wh = 5 * d2l.log(eps + c_assigned_bb[:, 2:] / c_anc[:, 2:])\n",
    "    offset = d2l.concat([offset_xy, offset_wh], axis=1)\n",
    "    return offset"
   ],
   "execution_count": 9,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-10 fw=all -->\n",
    "\n",
    "If an anchor box is not assigned a ground-truth bounding box, we just label the class of the anchor box as \"background\".\n",
    "Anchor boxes whose classes are background are often referred to as *negative* anchor boxes,\n",
    "and the rest are called *positive* anchor boxes.\n",
    "We implement the following `multibox_target` function\n",
    "to label classes and offsets for anchor boxes (the `anchors` argument) using ground-truth bounding boxes (the `labels` argument).\n",
    "This function sets the background class to zero and increments the integer index of a new class by one."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-labeling-classes-and-offsets-2"
   },
   "source": [
    "\n",
    "def multibox_target(anchors, labels):\n",
    "    \"\"\"Label anchor boxes using ground-truth bounding boxes.\"\"\"\n",
    "    batch_size, anchors = labels.shape[0], anchors.squeeze(0)\n",
    "    batch_offset, batch_mask, batch_class_labels = [], [], []\n",
    "    device, num_anchors = anchors.device, anchors.shape[0]\n",
    "    for i in range(batch_size):\n",
    "        label = labels[i, :, :]\n",
    "        anchors_bbox_map = assign_anchor_to_bbox(\n",
    "            label[:, 1:], anchors, device)\n",
    "        bbox_mask = ((anchors_bbox_map >= 0).float().unsqueeze(-1)).repeat(\n",
    "            1, 4)\n",
    "        # Initialize class labels and assigned bounding box coordinates with\n",
    "        # zeros\n",
    "        class_labels = torch.zeros(num_anchors, dtype=torch.long,\n",
    "                                   device=device)\n",
    "        assigned_bb = torch.zeros((num_anchors, 4), dtype=torch.float32,\n",
    "                                  device=device)\n",
    "        # Label classes of anchor boxes using their assigned ground-truth\n",
    "        # bounding boxes. If an anchor box is not assigned any, we label its\n",
    "        # class as background (the value remains zero)\n",
    "        indices_true = torch.nonzero(anchors_bbox_map >= 0)\n",
    "        bb_idx = anchors_bbox_map[indices_true]\n",
    "        class_labels[indices_true] = label[bb_idx, 0].long() + 1\n",
    "        assigned_bb[indices_true] = label[bb_idx, 1:]\n",
    "        # Offset transformation\n",
    "        offset = offset_boxes(anchors, assigned_bb) * bbox_mask\n",
    "        batch_offset.append(offset.reshape(-1))\n",
    "        batch_mask.append(bbox_mask.reshape(-1))\n",
    "        batch_class_labels.append(class_labels)\n",
    "    bbox_offset = torch.stack(batch_offset)\n",
    "    bbox_mask = torch.stack(batch_mask)\n",
    "    class_labels = torch.stack(batch_class_labels)\n",
    "    return (bbox_offset, bbox_mask, class_labels)"
   ],
   "execution_count": 10,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-11 fw=all -->\n",
    "\n",
    "### An Example\n",
    "\n",
    "Let's illustrate anchor box labeling\n",
    "via a concrete example.\n",
    "We define ground-truth bounding boxes for the dog and cat in the loaded image,\n",
    "where the first element is the class (0 for dog and 1 for cat) and the remaining four elements are the\n",
    "$(x, y)$-axis coordinates\n",
    "at the upper-left corner and the lower-right corner\n",
    "(range is between 0 and 1). \n",
    "We also construct five anchor boxes to be labeled\n",
    "using the coordinates of\n",
    "the upper-left corner and the lower-right corner:\n",
    "$A_0, \\ldots, A_4$ (the index starts from 0).\n",
    "Then we plot these ground-truth bounding boxes \n",
    "and anchor boxes \n",
    "in the image."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-an-example-1"
   },
   "source": [
    "ground_truth = d2l.tensor([[0, 0.1, 0.08, 0.52, 0.92],\n",
    "                         [1, 0.55, 0.2, 0.9, 0.88]])\n",
    "anchors = d2l.tensor([[0, 0.1, 0.2, 0.3], [0.15, 0.2, 0.4, 0.4],\n",
    "                    [0.63, 0.05, 0.88, 0.98], [0.66, 0.45, 0.8, 0.8],\n",
    "                    [0.57, 0.3, 0.92, 0.9]])\n",
    "\n",
    "fig = d2l.plt.imshow(img)\n",
    "show_bboxes(fig.axes, ground_truth[:, 1:] * bbox_scale, ['dog', 'cat'], 'k')\n",
    "show_bboxes(fig.axes, anchors * bbox_scale, ['0', '1', '2', '3', '4']);"
   ],
   "execution_count": 11,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"220.346324pt\" height=\"173.353814pt\" viewBox=\"0 0 220.346324 173.353814\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:40:10.229210</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 173.353814 \nL 220.346324 173.353814 \nL 220.346324 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 33.2875 149.475689 \nL 213.146324 149.475689 \nL 213.146324 10.875689 \nL 33.2875 10.875689 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#p6470a33bc0)\">\n    <image xlink:href=\"data:image/png;base64,\[encoded data, 75929 characters]\" id=\"imageff288ee60d\" transform=\"scale(1 -1) translate(0 -138.96)\" x=\"33.2875\" y=\"-10.515689\" width=\"180\" height=\"138.96\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 51.396913 22.087218 \nL 126.937617 22.087218 \nL 126.937617 138.511218 \nL 51.396913 138.511218 \nL 51.396913 22.087218 \nz\n\" clip-path=\"url(#p6470a33bc0)\" style=\"fill: none; stroke: #000000; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 132.333381 38.71922 \nL 195.283974 38.71922 \nL 195.283974 132.967217 \nL 132.333381 132.967217 \nL 132.333381 38.71922 \nz\n\" clip-path=\"url(#p6470a33bc0)\" style=\"fill: none; stroke: #000000; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 33.411029 24.859219 \nL 69.382796 24.859219 \nL 69.382796 52.57922 \nL 33.411029 52.57922 \nL 33.411029 24.859219 \nz\n\" clip-path=\"url(#p6470a33bc0)\" style=\"fill: none; stroke: #0000ff; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 60.389854 38.71922 \nL 105.354562 38.71922 \nL 105.354562 66.439221 \nL 60.389854 66.439221 \nL 60.389854 38.71922 \nz\n\" clip-path=\"url(#p6470a33bc0)\" style=\"fill: none; stroke: #008000; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_7\">\n    <path d=\"M 146.722084 17.929219 \nL 191.686798 17.929219 \nL 191.686798 146.827226 \nL 146.722084 146.827226 \nL 146.722084 17.929219 \nz\n\" clip-path=\"url(#p6470a33bc0)\" style=\"fill: none; stroke: #ff0000; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_8\">\n    <path d=\"M 152.117856 73.369218 \nL 177.298094 73.369218 \nL 177.298094 121.879223 \nL 152.117856 121.879223 \nL 152.117856 73.369218 \nz\n\" clip-path=\"url(#p6470a33bc0)\" style=\"fill: none; stroke: #bf00bf; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_9\">\n    <path d=\"M 135.930557 52.57922 \nL 198.881149 52.57922 \nL 198.881149 135.73921 \nL 135.930557 135.73921 \nL 135.930557 52.57922 \nz\n\" clip-path=\"url(#p6470a33bc0)\" style=\"fill: none; stroke: #00bfbf; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <defs>\n       <path id=\"m9546aa64f9\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m9546aa64f9\" x=\"33.411029\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0 -->\n      <g transform=\"translate(30.229779 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_2\">\n      <g>\n       <use xlink:href=\"#m9546aa64f9\" x=\"82.822794\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 200 -->\n      <g transform=\"translate(73.279044 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_3\">\n      <g>\n       <use xlink:href=\"#m9546aa64f9\" x=\"132.234559\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 400 -->\n      <g transform=\"translate(122.690809 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#m9546aa64f9\" x=\"181.646324\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 600 -->\n      <g transform=\"translate(172.102574 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-36\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_5\">\n      <defs>\n       <path id=\"m09f5baae13\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m09f5baae13\" x=\"33.2875\" y=\"10.999219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 0 -->\n      <g transform=\"translate(19.925 14.798438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m09f5baae13\" x=\"33.2875\" y=\"35.705101\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 100 -->\n      <g transform=\"translate(7.2 39.50432) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m09f5baae13\" x=\"33.2875\" y=\"60.410983\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 200 -->\n      <g transform=\"translate(7.2 64.210202) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m09f5baae13\" x=\"33.2875\" y=\"85.116866\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 300 -->\n      <g transform=\"translate(7.2 88.916085) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-33\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m09f5baae13\" x=\"33.2875\" y=\"109.822748\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 400 -->\n      <g transform=\"translate(7.2 113.621967) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-34\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m09f5baae13\" x=\"33.2875\" y=\"134.528631\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 500 -->\n      <g transform=\"translate(7.2 138.327849) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-35\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_10\">\n    <path d=\"M 33.2875 149.475689 \nL 33.2875 10.875689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_11\">\n    <path d=\"M 213.146324 149.475689 \nL 213.146324 10.875689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_12\">\n    <path d=\"M 33.2875 149.475689 \nL 213.146324 149.475689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_13\">\n    <path d=\"M 33.2875 10.875689 \nL 213.146324 10.875689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"text_11\">\n    <g id=\"patch_14\">\n     <path d=\"M 38.969881 30.402374 \nL 63.823944 30.402374 \nL 63.823944 13.772062 \nL 38.969881 13.772062 \nz\n\"/>\n    </g>\n    <!-- dog -->\n    <g style=\"fill: #ffffff\" transform=\"translate(42.929881 24.570656) scale(0.09 -0.09)\">\n     <defs>\n      <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-67\" d=\"M 2906 1791 \nQ 2906 2416 2648 2759 \nQ 2391 3103 1925 3103 \nQ 1463 3103 1205 2759 \nQ 947 2416 947 1791 \nQ 947 1169 1205 825 \nQ 1463 481 1925 481 \nQ 2391 481 2648 825 \nQ 2906 1169 2906 1791 \nz\nM 3481 434 \nQ 3481 -459 3084 -895 \nQ 2688 -1331 1869 -1331 \nQ 1566 -1331 1297 -1286 \nQ 1028 -1241 775 -1147 \nL 775 -588 \nQ 1028 -725 1275 -790 \nQ 1522 -856 1778 -856 \nQ 2344 -856 2625 -561 \nQ 2906 -266 2906 331 \nL 2906 616 \nQ 2728 306 2450 153 \nQ 2172 0 1784 0 \nQ 1141 0 747 490 \nQ 353 981 353 1791 \nQ 353 2603 747 3093 \nQ 1141 3584 1784 3584 \nQ 2172 3584 2450 3431 \nQ 2728 3278 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 434 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-64\"/>\n     <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(63.476562 0)\"/>\n     <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(124.658203 0)\"/>\n    </g>\n   </g>\n   <g id=\"text_12\">\n    <g id=\"patch_15\">\n     <path d=\"M 121.377287 47.034376 \nL 143.289475 47.034376 \nL 143.289475 30.404064 \nL 121.377287 30.404064 \nz\n\"/>\n    </g>\n    <!-- cat -->\n    <g style=\"fill: #ffffff\" transform=\"translate(125.337287 41.202657) scale(0.09 -0.09)\">\n     <defs>\n      <path id=\"DejaVuSans-63\" d=\"M 3122 3366 \nL 3122 2828 \nQ 2878 2963 2633 3030 \nQ 2388 3097 2138 3097 \nQ 1578 3097 1268 2742 \nQ 959 2388 959 1747 \nQ 959 1106 1268 751 \nQ 1578 397 2138 397 \nQ 2388 397 2633 464 \nQ 2878 531 3122 666 \nL 3122 134 \nQ 2881 22 2623 -34 \nQ 2366 -91 2075 -91 \nQ 1284 -91 818 406 \nQ 353 903 353 1747 \nQ 353 2603 823 3093 \nQ 1294 3584 2113 3584 \nQ 2378 3584 2631 3529 \nQ 2884 3475 3122 3366 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-63\"/>\n     <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(54.980469 0)\"/>\n     <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(116.259766 0)\"/>\n    </g>\n   </g>\n   <g id=\"text_13\">\n    <g id=\"patch_16\">\n     <path d=\"M 26.587904 33.174376 \nL 40.234154 33.174376 \nL 40.234154 16.544063 \nL 26.587904 16.544063 \nz\n\" style=\"fill: #0000ff\"/>\n    </g>\n    <!-- 0 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(30.547904 27.342657) scale(0.09 -0.09)\">\n     <use xlink:href=\"#DejaVuSans-30\"/>\n    </g>\n   </g>\n   <g id=\"text_14\">\n    <g id=\"patch_17\">\n     <path d=\"M 53.566729 47.034376 \nL 67.212979 47.034376 \nL 67.212979 30.404064 \nL 53.566729 30.404064 \nz\n\" style=\"fill: #008000\"/>\n    </g>\n    <!-- 1 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(57.526729 41.202657) scale(0.09 -0.09)\">\n     <use xlink:href=\"#DejaVuSans-31\"/>\n    </g>\n   </g>\n   <g id=\"text_15\">\n    <g id=\"patch_18\">\n     <path d=\"M 139.898959 26.244375 \nL 153.545209 26.244375 \nL 153.545209 9.614063 \nL 139.898959 9.614063 \nz\n\" style=\"fill: #ff0000\"/>\n    </g>\n    <!-- 2 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(143.858959 20.412657) scale(0.09 -0.09)\">\n     <use xlink:href=\"#DejaVuSans-32\"/>\n    </g>\n   </g>\n   <g id=\"text_16\">\n    <g id=\"patch_19\">\n     <path d=\"M 145.294731 81.684374 \nL 158.940981 81.684374 \nL 158.940981 65.054062 \nL 145.294731 65.054062 \nz\n\" style=\"fill: #bf00bf\"/>\n    </g>\n    <!-- 3 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(149.254731 75.852655) scale(0.09 -0.09)\">\n     <use xlink:href=\"#DejaVuSans-33\"/>\n    </g>\n   </g>\n   <g id=\"text_17\">\n    <g id=\"patch_20\">\n     <path d=\"M 129.107432 60.894376 \nL 142.753682 60.894376 \nL 142.753682 44.264063 \nL 129.107432 44.264063 \nz\n\" style=\"fill: #00bfbf\"/>\n    </g>\n    <!-- 4 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(133.067432 55.062657) scale(0.09 -0.09)\">\n     <use xlink:href=\"#DejaVuSans-34\"/>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p6470a33bc0\">\n   <rect x=\"33.2875\" y=\"10.875689\" width=\"179.858824\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-12 fw=all -->\n",
    "\n",
    "Using the `multibox_target` function defined above,\n",
    "we can label classes and offsets\n",
    "of these anchor boxes based on\n",
    "the ground-truth bounding boxes for the dog and cat.\n",
    "In this example, indices of\n",
    "the background, dog, and cat classes\n",
    "are 0, 1, and 2, respectively. \n",
    "Below we add a dimension for examples of anchor boxes and ground-truth bounding boxes."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-an-example-2"
   },
   "source": [
    "labels = multibox_target(anchors.unsqueeze(dim=0),\n",
    "                         ground_truth.unsqueeze(dim=0))"
   ],
   "execution_count": 12,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-13 fw=all -->\n",
    "\n",
    "There are three items in the returned result, all of which are in the tensor format.\n",
    "The third item contains the labeled classes of the input anchor boxes.\n",
    "\n",
    "Let's analyze the returned class labels below based on\n",
    "anchor box and ground-truth bounding box positions in the image.\n",
    "First, among all the pairs of anchor boxes\n",
    "and ground-truth bounding boxes,\n",
    "the IoU of the anchor box $A_4$ and the ground-truth bounding box of the cat is the largest. \n",
    "Thus, the class of $A_4$ is labeled as the cat.\n",
    "Taking out \n",
    "pairs containing $A_4$ or the ground-truth bounding box of the cat, among the rest \n",
    "the pair of the anchor box $A_1$ and the ground-truth bounding box of the dog has the largest IoU.\n",
    "So the class of $A_1$ is labeled as the dog.\n",
    "Next, we need to traverse through the remaining three unlabeled anchor boxes: $A_0$, $A_2$, and $A_3$.\n",
    "For $A_0$,\n",
    "the class of the ground-truth bounding box with the largest IoU is the dog,\n",
    "but the IoU is below the predefined threshold (0.5),\n",
    "so the class is labeled as background;\n",
    "for $A_2$,\n",
    "the class of the ground-truth bounding box with the largest IoU is the cat and the IoU exceeds the threshold, so the class is labeled as the cat;\n",
    "for $A_3$,\n",
    "the class of the ground-truth bounding box with the largest IoU is the cat, but the value is below the threshold, so the class is labeled as background."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-an-example-3"
   },
   "source": [
    "labels[2]"
   ],
   "execution_count": 13,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[0, 1, 2, 0, 2]])"
     },
     "metadata": {},
     "execution_count": 13
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-14 fw=all -->\n",
    "\n",
    "The second returned item is a mask variable of the shape (batch size, four times the number of anchor boxes).\n",
    "Every four elements in the mask variable \n",
    "correspond to the four offset values of each anchor box.\n",
    "Since we do not care about background detection,\n",
    "offsets of this negative class should not affect the objective function.\n",
    "Through elementwise multiplications, zeros in the mask variable will filter out negative class offsets before calculating the objective function."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-an-example-4"
   },
   "source": [
    "labels[1]"
   ],
   "execution_count": 14,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[0., 0., 0., 0., 1., 1., 1., 1., 1., 1., 1., 1., 0., 0., 0., 0., 1., 1.,\n         1., 1.]])"
     },
     "metadata": {},
     "execution_count": 14
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-15 fw=all -->\n",
    "\n",
    "The first returned item contains the four offset values labeled for each anchor box.\n",
    "Note that the offsets of negative-class anchor boxes are labeled as zeros."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-an-example-5"
   },
   "source": [
    "labels[0]"
   ],
   "execution_count": 15,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[-0.00e+00, -0.00e+00, -0.00e+00, -0.00e+00,  1.40e+00,  1.00e+01,\n          2.59e+00,  7.18e+00, -1.20e+00,  2.69e-01,  1.68e+00, -1.57e+00,\n         -0.00e+00, -0.00e+00, -0.00e+00, -0.00e+00, -5.71e-01, -1.00e+00,\n          4.17e-06,  6.26e-01]])"
     },
     "metadata": {},
     "execution_count": 15
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-16 fw=all -->\n",
    "\n",
    "## Predicting Bounding Boxes with Non-Maximum Suppression\n",
    "\n",
    "During prediction,\n",
    "we generate multiple anchor boxes for the image and predict classes and offsets for each of them.\n",
    "A *predicted bounding box*\n",
    "is thus obtained according to \n",
    "an anchor box with its predicted offset.\n",
    "Below we implement the `offset_inverse` function\n",
    "that takes in anchors and\n",
    "offset predictions as inputs and applies inverse offset transformations to\n",
    "return the predicted bounding box coordinates."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-predicting-bounding-boxes-with-non-maximum-suppression-1"
   },
   "source": [
    "\n",
    "def offset_inverse(anchors, offset_preds):\n",
    "    \"\"\"Predict bounding boxes based on anchor boxes with predicted offsets.\"\"\"\n",
    "    anc = d2l.box_corner_to_center(anchors)\n",
    "    pred_bbox_xy = (offset_preds[:, :2] * anc[:, 2:] / 10) + anc[:, :2]\n",
    "    pred_bbox_wh = d2l.exp(offset_preds[:, 2:] / 5) * anc[:, 2:]\n",
    "    pred_bbox = d2l.concat((pred_bbox_xy, pred_bbox_wh), axis=1)\n",
    "    predicted_bbox = d2l.box_center_to_corner(pred_bbox)\n",
    "    return predicted_bbox"
   ],
   "execution_count": 16,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-17 fw=all -->\n",
    "\n",
    "When there are many anchor boxes,\n",
    "many similar (with significant overlap)\n",
    "predicted bounding boxes \n",
    "can be potentially output for surrounding the same object.\n",
    "To simplify the output,\n",
    "we can merge similar predicted bounding boxes\n",
    "that belong to the same object\n",
    "by using *non-maximum suppression* (NMS).\n",
    "\n",
    "Here is how non-maximum suppression works.\n",
    "For a predicted bounding box $B$,\n",
    "the object detection model calculates the predicted likelihood\n",
    "for each class.\n",
    "Denoting by $p$ the largest predicted likelihood,\n",
    "the class corresponding to this probability is the predicted class for $B$.\n",
    "Specifically, we refer to $p$ as the *confidence* (score) of the predicted bounding box $B$.\n",
    "On the same image,\n",
    "all the predicted non-background bounding boxes \n",
    "are sorted by confidence in descending order\n",
    "to generate a list $L$.\n",
    "Then we manipulate the sorted list $L$ in the following steps:\n",
    "\n",
    "1. Select the predicted bounding box $B_1$ with the highest confidence from $L$ as a basis and remove all non-basis predicted bounding boxes whose IoU with $B_1$ exceeds a predefined threshold $\\epsilon$ from $L$. At this point, $L$ keeps the predicted bounding box with the highest confidence but drops others that are too similar to it. In a nutshell, those with *non-maximum* confidence scores are *suppressed*.\n",
    "1. Select the predicted bounding box $B_2$ with the second highest confidence from $L$ as another basis and remove all non-basis predicted bounding boxes whose IoU with $B_2$ exceeds $\\epsilon$ from $L$.\n",
    "1. Repeat the above process until all the predicted bounding boxes in $L$ have been used as a basis. At this time, the IoU of any pair of predicted bounding boxes in $L$ is below the threshold $\\epsilon$; thus, no pair is too similar with each other. \n",
    "1. Output all the predicted bounding boxes in the list $L$.\n",
    "\n",
    "The following `nms` function sorts confidence scores in descending order and returns their indices."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-predicting-bounding-boxes-with-non-maximum-suppression-2"
   },
   "source": [
    "\n",
    "def nms(boxes, scores, iou_threshold):\n",
    "    \"\"\"Sort confidence scores of predicted bounding boxes.\"\"\"\n",
    "    B = torch.argsort(scores, dim=-1, descending=True)\n",
    "    keep = []  # Indices of predicted bounding boxes that will be kept\n",
    "    while B.numel() > 0:\n",
    "        i = B[0]\n",
    "        keep.append(i)\n",
    "        if B.numel() == 1: break\n",
    "        iou = box_iou(boxes[i, :].reshape(-1, 4),\n",
    "                      boxes[B[1:], :].reshape(-1, 4)).reshape(-1)\n",
    "        inds = torch.nonzero(iou <= iou_threshold).reshape(-1)\n",
    "        B = B[inds + 1]\n",
    "    return d2l.tensor(keep, device=boxes.device)"
   ],
   "execution_count": 17,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-18 fw=all -->\n",
    "\n",
    "We define the following `multibox_detection`\n",
    "to apply non-maximum suppression\n",
    "to predicting bounding boxes.\n",
    "Do not worry if you find the implementation\n",
    "a bit complicated: we will show how it works\n",
    "with a concrete example right after the implementation."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-predicting-bounding-boxes-with-non-maximum-suppression-3"
   },
   "source": [
    "\n",
    "def multibox_detection(cls_probs, offset_preds, anchors, nms_threshold=0.5,\n",
    "                       pos_threshold=0.009999999):\n",
    "    \"\"\"Predict bounding boxes using non-maximum suppression.\"\"\"\n",
    "    device, batch_size = cls_probs.device, cls_probs.shape[0]\n",
    "    anchors = anchors.squeeze(0)\n",
    "    num_classes, num_anchors = cls_probs.shape[1], cls_probs.shape[2]\n",
    "    out = []\n",
    "    for i in range(batch_size):\n",
    "        cls_prob, offset_pred = cls_probs[i], offset_preds[i].reshape(-1, 4)\n",
    "        conf, class_id = torch.max(cls_prob[1:], 0)\n",
    "        predicted_bb = offset_inverse(anchors, offset_pred)\n",
    "        keep = nms(predicted_bb, conf, nms_threshold)\n",
    "        # Find all non-`keep` indices and set the class to background\n",
    "        all_idx = torch.arange(num_anchors, dtype=torch.long, device=device)\n",
    "        combined = torch.cat((keep, all_idx))\n",
    "        uniques, counts = combined.unique(return_counts=True)\n",
    "        non_keep = uniques[counts == 1]\n",
    "        all_id_sorted = torch.cat((keep, non_keep))\n",
    "        class_id[non_keep] = -1\n",
    "        class_id = class_id[all_id_sorted]\n",
    "        conf, predicted_bb = conf[all_id_sorted], predicted_bb[all_id_sorted]\n",
    "        # Here `pos_threshold` is a threshold for positive (non-background)\n",
    "        # predictions\n",
    "        below_min_idx = (conf < pos_threshold)\n",
    "        class_id[below_min_idx] = -1\n",
    "        conf[below_min_idx] = 1 - conf[below_min_idx]\n",
    "        pred_info = torch.cat((class_id.unsqueeze(1),\n",
    "                               conf.unsqueeze(1),\n",
    "                               predicted_bb), dim=1)\n",
    "        out.append(pred_info)\n",
    "    return d2l.stack(out)"
   ],
   "execution_count": 18,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-19 fw=all -->\n",
    "\n",
    "Now let's apply the above implementations\n",
    "to a concrete example with four anchor boxes.\n",
    "For simplicity, we assume that the\n",
    "predicted offsets are all zeros.\n",
    "This means that the predicted bounding boxes are anchor boxes. \n",
    "For each class among the background, dog, and cat,\n",
    "we also define its predicted likelihood."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-predicting-bounding-boxes-with-non-maximum-suppression-4"
   },
   "source": [
    "anchors = d2l.tensor([[0.1, 0.08, 0.52, 0.92], [0.08, 0.2, 0.56, 0.95],\n",
    "                      [0.15, 0.3, 0.62, 0.91], [0.55, 0.2, 0.9, 0.88]])\n",
    "offset_preds = d2l.tensor([0] * d2l.size(anchors))\n",
    "cls_probs = d2l.tensor([[0] * 4,  # Predicted background likelihood \n",
    "                      [0.9, 0.8, 0.7, 0.1],  # Predicted dog likelihood \n",
    "                      [0.1, 0.2, 0.3, 0.9]])  # Predicted cat likelihood"
   ],
   "execution_count": 19,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-20 fw=all -->\n",
    "\n",
    "We can plot these predicted bounding boxes with their confidence on the image."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-predicting-bounding-boxes-with-non-maximum-suppression-5"
   },
   "source": [
    "fig = d2l.plt.imshow(img)\n",
    "show_bboxes(fig.axes, anchors * bbox_scale,\n",
    "            ['dog=0.9', 'dog=0.8', 'dog=0.7', 'cat=0.9'])"
   ],
   "execution_count": 20,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"220.346324pt\" height=\"173.353814pt\" viewBox=\"0 0 220.346324 173.353814\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:40:10.427547</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 173.353814 \nL 220.346324 173.353814 \nL 220.346324 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 33.2875 149.475689 \nL 213.146324 149.475689 \nL 213.146324 10.875689 \nL 33.2875 10.875689 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#p10b5ac6236)\">\n    <image xlink:href=\"data:image/png;base64,\[encoded data, 75929 characters]\" id=\"image4abb683f10\" transform=\"scale(1 -1) translate(0 -138.96)\" x=\"33.2875\" y=\"-10.515689\" width=\"180\" height=\"138.96\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 51.396913 22.087218 \nL 126.937617 22.087218 \nL 126.937617 138.511218 \nL 51.396913 138.511218 \nL 51.396913 22.087218 \nz\n\" clip-path=\"url(#p10b5ac6236)\" style=\"fill: none; stroke: #0000ff; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 47.799735 38.71922 \nL 134.131969 38.71922 \nL 134.131969 142.669222 \nL 47.799735 142.669222 \nL 47.799735 38.71922 \nz\n\" clip-path=\"url(#p10b5ac6236)\" style=\"fill: none; stroke: #008000; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 60.389854 52.57922 \nL 144.923504 52.57922 \nL 144.923504 137.125221 \nL 60.389854 137.125221 \nL 60.389854 52.57922 \nz\n\" clip-path=\"url(#p10b5ac6236)\" style=\"fill: none; stroke: #ff0000; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 132.333381 38.71922 \nL 195.283974 38.71922 \nL 195.283974 132.967217 \nL 132.333381 132.967217 \nL 132.333381 38.71922 \nz\n\" clip-path=\"url(#p10b5ac6236)\" style=\"fill: none; stroke: #bf00bf; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <defs>\n       <path id=\"m844263060f\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m844263060f\" x=\"33.411029\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0 -->\n      <g transform=\"translate(30.229779 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_2\">\n      <g>\n       <use xlink:href=\"#m844263060f\" x=\"82.822794\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 200 -->\n      <g transform=\"translate(73.279044 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_3\">\n      <g>\n       <use xlink:href=\"#m844263060f\" x=\"132.234559\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 400 -->\n      <g transform=\"translate(122.690809 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#m844263060f\" x=\"181.646324\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 600 -->\n      <g transform=\"translate(172.102574 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-36\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_5\">\n      <defs>\n       <path id=\"m6a64e4c74d\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m6a64e4c74d\" x=\"33.2875\" y=\"10.999219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 0 -->\n      <g transform=\"translate(19.925 14.798438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m6a64e4c74d\" x=\"33.2875\" y=\"35.705101\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 100 -->\n      <g transform=\"translate(7.2 39.50432) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m6a64e4c74d\" x=\"33.2875\" y=\"60.410983\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 200 -->\n      <g transform=\"translate(7.2 64.210202) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m6a64e4c74d\" x=\"33.2875\" y=\"85.116866\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 300 -->\n      <g transform=\"translate(7.2 88.916085) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-33\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m6a64e4c74d\" x=\"33.2875\" y=\"109.822748\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 400 -->\n      <g transform=\"translate(7.2 113.621967) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-34\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m6a64e4c74d\" x=\"33.2875\" y=\"134.528631\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 500 -->\n      <g transform=\"translate(7.2 138.327849) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-35\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_7\">\n    <path d=\"M 33.2875 149.475689 \nL 33.2875 10.875689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_8\">\n    <path d=\"M 213.146324 149.475689 \nL 213.146324 10.875689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_9\">\n    <path d=\"M 33.2875 149.475689 \nL 213.146324 149.475689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_10\">\n    <path d=\"M 33.2875 10.875689 \nL 213.146324 10.875689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"text_11\">\n    <g id=\"patch_11\">\n     <path d=\"M 28.042616 30.402374 \nL 74.751209 30.402374 \nL 74.751209 13.772062 \nL 28.042616 13.772062 \nz\n\" style=\"fill: #0000ff\"/>\n    </g>\n    <!-- dog=0.9 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(32.002616 24.570656) scale(0.09 -0.09)\">\n     <defs>\n      <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-67\" d=\"M 2906 1791 \nQ 2906 2416 2648 2759 \nQ 2391 3103 1925 3103 \nQ 1463 3103 1205 2759 \nQ 947 2416 947 1791 \nQ 947 1169 1205 825 \nQ 1463 481 1925 481 \nQ 2391 481 2648 825 \nQ 2906 1169 2906 1791 \nz\nM 3481 434 \nQ 3481 -459 3084 -895 \nQ 2688 -1331 1869 -1331 \nQ 1566 -1331 1297 -1286 \nQ 1028 -1241 775 -1147 \nL 775 -588 \nQ 1028 -725 1275 -790 \nQ 1522 -856 1778 -856 \nQ 2344 -856 2625 -561 \nQ 2906 -266 2906 331 \nL 2906 616 \nQ 2728 306 2450 153 \nQ 2172 0 1784 0 \nQ 1141 0 747 490 \nQ 353 981 353 1791 \nQ 353 2603 747 3093 \nQ 1141 3584 1784 3584 \nQ 2172 3584 2450 3431 \nQ 2728 3278 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 434 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-3d\" d=\"M 678 2906 \nL 4684 2906 \nL 4684 2381 \nL 678 2381 \nL 678 2906 \nz\nM 678 1631 \nL 4684 1631 \nL 4684 1100 \nL 678 1100 \nL 678 1631 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-39\" d=\"M 703 97 \nL 703 672 \nQ 941 559 1184 500 \nQ 1428 441 1663 441 \nQ 2288 441 2617 861 \nQ 2947 1281 2994 2138 \nQ 2813 1869 2534 1725 \nQ 2256 1581 1919 1581 \nQ 1219 1581 811 2004 \nQ 403 2428 403 3163 \nQ 403 3881 828 4315 \nQ 1253 4750 1959 4750 \nQ 2769 4750 3195 4129 \nQ 3622 3509 3622 2328 \nQ 3622 1225 3098 567 \nQ 2575 -91 1691 -91 \nQ 1453 -91 1209 -44 \nQ 966 3 703 97 \nz\nM 1959 2075 \nQ 2384 2075 2632 2365 \nQ 2881 2656 2881 3163 \nQ 2881 3666 2632 3958 \nQ 2384 4250 1959 4250 \nQ 1534 4250 1286 3958 \nQ 1038 3666 1038 3163 \nQ 1038 2656 1286 2365 \nQ 1534 2075 1959 2075 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-64\"/>\n     <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(63.476562 0)\"/>\n     <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(124.658203 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(188.134766 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(271.923828 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(335.546875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-39\" transform=\"translate(367.333984 0)\"/>\n    </g>\n   </g>\n   <g id=\"text_12\">\n    <g id=\"patch_12\">\n     <path d=\"M 24.445438 47.034376 \nL 71.154032 47.034376 \nL 71.154032 30.404064 \nL 24.445438 30.404064 \nz\n\" style=\"fill: #008000\"/>\n    </g>\n    <!-- dog=0.8 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(28.405438 41.202657) scale(0.09 -0.09)\">\n     <defs>\n      <path id=\"DejaVuSans-38\" d=\"M 2034 2216 \nQ 1584 2216 1326 1975 \nQ 1069 1734 1069 1313 \nQ 1069 891 1326 650 \nQ 1584 409 2034 409 \nQ 2484 409 2743 651 \nQ 3003 894 3003 1313 \nQ 3003 1734 2745 1975 \nQ 2488 2216 2034 2216 \nz\nM 1403 2484 \nQ 997 2584 770 2862 \nQ 544 3141 544 3541 \nQ 544 4100 942 4425 \nQ 1341 4750 2034 4750 \nQ 2731 4750 3128 4425 \nQ 3525 4100 3525 3541 \nQ 3525 3141 3298 2862 \nQ 3072 2584 2669 2484 \nQ 3125 2378 3379 2068 \nQ 3634 1759 3634 1313 \nQ 3634 634 3220 271 \nQ 2806 -91 2034 -91 \nQ 1263 -91 848 271 \nQ 434 634 434 1313 \nQ 434 1759 690 2068 \nQ 947 2378 1403 2484 \nz\nM 1172 3481 \nQ 1172 3119 1398 2916 \nQ 1625 2713 2034 2713 \nQ 2441 2713 2670 2916 \nQ 2900 3119 2900 3481 \nQ 2900 3844 2670 4047 \nQ 2441 4250 2034 4250 \nQ 1625 4250 1398 4047 \nQ 1172 3844 1172 3481 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-64\"/>\n     <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(63.476562 0)\"/>\n     <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(124.658203 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(188.134766 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(271.923828 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(335.546875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-38\" transform=\"translate(367.333984 0)\"/>\n    </g>\n   </g>\n   <g id=\"text_13\">\n    <g id=\"patch_13\">\n     <path d=\"M 37.035557 60.894376 \nL 83.744151 60.894376 \nL 83.744151 44.264063 \nL 37.035557 44.264063 \nz\n\" style=\"fill: #ff0000\"/>\n    </g>\n    <!-- dog=0.7 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(40.995557 55.062657) scale(0.09 -0.09)\">\n     <defs>\n      <path id=\"DejaVuSans-37\" d=\"M 525 4666 \nL 3525 4666 \nL 3525 4397 \nL 1831 0 \nL 1172 0 \nL 2766 4134 \nL 525 4134 \nL 525 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-64\"/>\n     <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(63.476562 0)\"/>\n     <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(124.658203 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(188.134766 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(271.923828 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(335.546875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-37\" transform=\"translate(367.333984 0)\"/>\n    </g>\n   </g>\n   <g id=\"text_14\">\n    <g id=\"patch_14\">\n     <path d=\"M 110.450021 47.034376 \nL 154.21674 47.034376 \nL 154.21674 30.404064 \nL 110.450021 30.404064 \nz\n\" style=\"fill: #bf00bf\"/>\n    </g>\n    <!-- cat=0.9 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(114.410021 41.202657) scale(0.09 -0.09)\">\n     <defs>\n      <path id=\"DejaVuSans-63\" d=\"M 3122 3366 \nL 3122 2828 \nQ 2878 2963 2633 3030 \nQ 2388 3097 2138 3097 \nQ 1578 3097 1268 2742 \nQ 959 2388 959 1747 \nQ 959 1106 1268 751 \nQ 1578 397 2138 397 \nQ 2388 397 2633 464 \nQ 2878 531 3122 666 \nL 3122 134 \nQ 2881 22 2623 -34 \nQ 2366 -91 2075 -91 \nQ 1284 -91 818 406 \nQ 353 903 353 1747 \nQ 353 2603 823 3093 \nQ 1294 3584 2113 3584 \nQ 2378 3584 2631 3529 \nQ 2884 3475 3122 3366 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-63\"/>\n     <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(54.980469 0)\"/>\n     <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(116.259766 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(155.46875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(239.257812 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(302.880859 0)\"/>\n     <use xlink:href=\"#DejaVuSans-39\" transform=\"translate(334.667969 0)\"/>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p10b5ac6236\">\n   <rect x=\"33.2875\" y=\"10.875689\" width=\"179.858824\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-21 fw=all -->\n",
    "\n",
    "Now we can invoke the `multibox_detection` function\n",
    "to perform non-maximum suppression,\n",
    "where the threshold is set to 0.5.\n",
    "Note that we add\n",
    "a dimension for examples in the tensor input.\n",
    "\n",
    "We can see that the shape of the returned result is\n",
    "(batch size, number of anchor boxes, 6).\n",
    "The six elements in the innermost dimension\n",
    "gives the output information for the same predicted bounding box.\n",
    "The first element is the predicted class index, which starts from 0 (0 is dog and 1 is cat). The value -1 indicates background or removal in non-maximum suppression.\n",
    "The second element is the confidence of the predicted bounding box.\n",
    "The remaining four elements are the $(x, y)$-axis coordinates of the upper-left corner and \n",
    "the lower-right corner of the predicted bounding box, respectively (range is between 0 and 1)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-predicting-bounding-boxes-with-non-maximum-suppression-6"
   },
   "source": [
    "output = multibox_detection(cls_probs.unsqueeze(dim=0),\n",
    "                            offset_preds.unsqueeze(dim=0),\n",
    "                            anchors.unsqueeze(dim=0),\n",
    "                            nms_threshold=0.5)\n",
    "output"
   ],
   "execution_count": 21,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "tensor([[[ 0.00,  0.90,  0.10,  0.08,  0.52,  0.92],\n         [ 1.00,  0.90,  0.55,  0.20,  0.90,  0.88],\n         [-1.00,  0.80,  0.08,  0.20,  0.56,  0.95],\n         [-1.00,  0.70,  0.15,  0.30,  0.62,  0.91]]])"
     },
     "metadata": {},
     "execution_count": 21
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-22 fw=all -->\n",
    "\n",
    "After removing those predicted bounding boxes\n",
    "of class -1, \n",
    "we can output the final predicted bounding box\n",
    "kept by non-maximum suppression."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "anchor-predicting-bounding-boxes-with-non-maximum-suppression-7"
   },
   "source": [
    "fig = d2l.plt.imshow(img)\n",
    "for i in d2l.numpy(output[0]):\n",
    "    if i[0] == -1:\n",
    "        continue\n",
    "    label = ('dog=', 'cat=')[int(i[0])] + str(i[1])\n",
    "    show_bboxes(fig.axes, [d2l.tensor(i[2:]) * bbox_scale], label)"
   ],
   "execution_count": 22,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"220.346324pt\" height=\"173.353814pt\" viewBox=\"0 0 220.346324 173.353814\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:40:10.572327</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 173.353814 \nL 220.346324 173.353814 \nL 220.346324 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 33.2875 149.475689 \nL 213.146324 149.475689 \nL 213.146324 10.875689 \nL 33.2875 10.875689 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#pc99bc74895)\">\n    <image xlink:href=\"data:image/png;base64,\[encoded data, 75929 characters]\" id=\"image6b1d78493c\" transform=\"scale(1 -1) translate(0 -138.96)\" x=\"33.2875\" y=\"-10.515689\" width=\"180\" height=\"138.96\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 51.396913 22.087216 \nL 126.937617 22.087216 \nL 126.937617 138.511218 \nL 51.396913 138.511218 \nL 51.396913 22.087216 \nz\n\" clip-path=\"url(#pc99bc74895)\" style=\"fill: none; stroke: #0000ff; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 132.333396 38.719222 \nL 195.283974 38.719222 \nL 195.283974 132.967217 \nL 132.333396 132.967217 \nL 132.333396 38.719222 \nz\n\" clip-path=\"url(#pc99bc74895)\" style=\"fill: none; stroke: #0000ff; stroke-width: 2; stroke-linejoin: miter\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <defs>\n       <path id=\"mb5d6d793e7\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mb5d6d793e7\" x=\"33.411029\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0 -->\n      <g transform=\"translate(30.229779 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_2\">\n      <g>\n       <use xlink:href=\"#mb5d6d793e7\" x=\"82.822794\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 200 -->\n      <g transform=\"translate(73.279044 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_3\">\n      <g>\n       <use xlink:href=\"#mb5d6d793e7\" x=\"132.234559\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 400 -->\n      <g transform=\"translate(122.690809 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#mb5d6d793e7\" x=\"181.646324\" y=\"149.475689\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 600 -->\n      <g transform=\"translate(172.102574 164.074127) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-36\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_5\">\n      <defs>\n       <path id=\"m081efe887f\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m081efe887f\" x=\"33.2875\" y=\"10.999219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 0 -->\n      <g transform=\"translate(19.925 14.798438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m081efe887f\" x=\"33.2875\" y=\"35.705101\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 100 -->\n      <g transform=\"translate(7.2 39.50432) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m081efe887f\" x=\"33.2875\" y=\"60.410983\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 200 -->\n      <g transform=\"translate(7.2 64.210202) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m081efe887f\" x=\"33.2875\" y=\"85.116866\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 300 -->\n      <g transform=\"translate(7.2 88.916085) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-33\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m081efe887f\" x=\"33.2875\" y=\"109.822748\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 400 -->\n      <g transform=\"translate(7.2 113.621967) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-34\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m081efe887f\" x=\"33.2875\" y=\"134.528631\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 500 -->\n      <g transform=\"translate(7.2 138.327849) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-35\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(127.246094 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 33.2875 149.475689 \nL 33.2875 10.875689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 213.146324 149.475689 \nL 213.146324 10.875689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_7\">\n    <path d=\"M 33.2875 149.475689 \nL 213.146324 149.475689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_8\">\n    <path d=\"M 33.2875 10.875689 \nL 213.146324 10.875689 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"text_11\">\n    <g id=\"patch_9\">\n     <path d=\"M 28.042616 30.402372 \nL 74.751209 30.402372 \nL 74.751209 13.77206 \nL 28.042616 13.77206 \nz\n\" style=\"fill: #0000ff\"/>\n    </g>\n    <!-- dog=0.9 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(32.002616 24.570654) scale(0.09 -0.09)\">\n     <defs>\n      <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-67\" d=\"M 2906 1791 \nQ 2906 2416 2648 2759 \nQ 2391 3103 1925 3103 \nQ 1463 3103 1205 2759 \nQ 947 2416 947 1791 \nQ 947 1169 1205 825 \nQ 1463 481 1925 481 \nQ 2391 481 2648 825 \nQ 2906 1169 2906 1791 \nz\nM 3481 434 \nQ 3481 -459 3084 -895 \nQ 2688 -1331 1869 -1331 \nQ 1566 -1331 1297 -1286 \nQ 1028 -1241 775 -1147 \nL 775 -588 \nQ 1028 -725 1275 -790 \nQ 1522 -856 1778 -856 \nQ 2344 -856 2625 -561 \nQ 2906 -266 2906 331 \nL 2906 616 \nQ 2728 306 2450 153 \nQ 2172 0 1784 0 \nQ 1141 0 747 490 \nQ 353 981 353 1791 \nQ 353 2603 747 3093 \nQ 1141 3584 1784 3584 \nQ 2172 3584 2450 3431 \nQ 2728 3278 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 434 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-3d\" d=\"M 678 2906 \nL 4684 2906 \nL 4684 2381 \nL 678 2381 \nL 678 2906 \nz\nM 678 1631 \nL 4684 1631 \nL 4684 1100 \nL 678 1100 \nL 678 1631 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-39\" d=\"M 703 97 \nL 703 672 \nQ 941 559 1184 500 \nQ 1428 441 1663 441 \nQ 2288 441 2617 861 \nQ 2947 1281 2994 2138 \nQ 2813 1869 2534 1725 \nQ 2256 1581 1919 1581 \nQ 1219 1581 811 2004 \nQ 403 2428 403 3163 \nQ 403 3881 828 4315 \nQ 1253 4750 1959 4750 \nQ 2769 4750 3195 4129 \nQ 3622 3509 3622 2328 \nQ 3622 1225 3098 567 \nQ 2575 -91 1691 -91 \nQ 1453 -91 1209 -44 \nQ 966 3 703 97 \nz\nM 1959 2075 \nQ 2384 2075 2632 2365 \nQ 2881 2656 2881 3163 \nQ 2881 3666 2632 3958 \nQ 2384 4250 1959 4250 \nQ 1534 4250 1286 3958 \nQ 1038 3666 1038 3163 \nQ 1038 2656 1286 2365 \nQ 1534 2075 1959 2075 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-64\"/>\n     <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(63.476562 0)\"/>\n     <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(124.658203 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(188.134766 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(271.923828 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(335.546875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-39\" transform=\"translate(367.333984 0)\"/>\n    </g>\n   </g>\n   <g id=\"text_12\">\n    <g id=\"patch_10\">\n     <path d=\"M 110.450037 47.034378 \nL 154.216755 47.034378 \nL 154.216755 30.404066 \nL 110.450037 30.404066 \nz\n\" style=\"fill: #0000ff\"/>\n    </g>\n    <!-- cat=0.9 -->\n    <g style=\"fill: #ffffff\" transform=\"translate(114.410037 41.202659) scale(0.09 -0.09)\">\n     <defs>\n      <path id=\"DejaVuSans-63\" d=\"M 3122 3366 \nL 3122 2828 \nQ 2878 2963 2633 3030 \nQ 2388 3097 2138 3097 \nQ 1578 3097 1268 2742 \nQ 959 2388 959 1747 \nQ 959 1106 1268 751 \nQ 1578 397 2138 397 \nQ 2388 397 2633 464 \nQ 2878 531 3122 666 \nL 3122 134 \nQ 2881 22 2623 -34 \nQ 2366 -91 2075 -91 \nQ 1284 -91 818 406 \nQ 353 903 353 1747 \nQ 353 2603 823 3093 \nQ 1294 3584 2113 3584 \nQ 2378 3584 2631 3529 \nQ 2884 3475 3122 3366 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-63\"/>\n     <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(54.980469 0)\"/>\n     <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(116.259766 0)\"/>\n     <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(155.46875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(239.257812 0)\"/>\n     <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(302.880859 0)\"/>\n     <use xlink:href=\"#DejaVuSans-39\" transform=\"translate(334.667969 0)\"/>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"pc99bc74895\">\n   <rect x=\"33.2875\" y=\"10.875689\" width=\"179.858824\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-23 fw=all -->\n",
    "\n",
    "In practice, we can remove predicted bounding boxes with lower confidence even before performing non-maximum suppression, thereby reducing computation in this algorithm.\n",
    "We may also post-process the output of non-maximum suppression, for example, by only keeping\n",
    "results with higher confidence\n",
    "in the final output.\n",
    "\n",
    "\n",
    "## Summary\n",
    "\n",
    "* We generate anchor boxes with different shapes centered on each pixel of the image.\n",
    "* Intersection over union (IoU), also known as Jaccard index, measures the similarity of two bounding boxes. It is the ratio of their intersection area to their union area.\n",
    "* In a training set, we need two types of labels for each anchor box. One is the class of the object relevant to the anchor box and the other is the offset of the ground-truth bounding box relative to the anchor box.\n",
    "* During prediction, we can use non-maximum suppression (NMS) to remove similar predicted bounding boxes, thereby simplifying the output.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Change values of `sizes` and `ratios` in the `multibox_prior` function. What are the changes to the generated anchor boxes?\n",
    "1. Construct and visualize two bounding boxes with an IoU of 0.5. How do they overlap with each other?\n",
    "1. Modify the variable `anchors` in that section and that section. How do the results change?\n",
    "1. Non-maximum suppression is a greedy algorithm that suppresses predicted bounding boxes by *removing* them. Is it possible that some of these removed ones are actually useful? How can this algorithm be modified to suppress *softly*? You may refer to Soft-NMS [@Bodla.Singh.Chellappa.ea.2017].\n",
    "1. Rather than being hand-crafted, can non-maximum suppression be learned?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=anchor-md-24 fw=pytorch -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/1603)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
