{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第4章 模板匹配\n",
    "\n",
    "## 4.1 简介"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "图像匹配（matching），即找到不同图像中相同或相似物体的几何对应关系，是计算机视觉的一个基础问题。基于图像匹配，我们可以完成图像检索、图像拼接和图像识别等一系列计算机视觉任务。最基础最简单的图像匹配就是模板匹配：给定一张模板图像，在另一张图像中找到与该模板相似度最高的目标位置。例如如图4-1所示，给定金币为模板图像，我们需要找到该图中是否含有金币，如果有，则需要确定金币的位置。根据目标的数目，我们可以将模板匹配分为单目标模板匹配和多目标模板匹配。在这一章中，我们将介绍模板匹配的计算步骤以及用于匹配的相似度度量。\n",
    "\n",
    "<center>\n",
    "    <img style=\"border-radius: 0.3125em;\" \n",
    "    src=\"https://storage.googleapis.com/kagglesdsdata/datasets/2176885/3648317/img.jpeg?X-Goog-Algorithm=GOOG4-RSA-SHA256&X-Goog-Credential=databundle-worker-v2%40kaggle-161607.iam.gserviceaccount.com%2F20220521%2Fauto%2Fstorage%2Fgoog4_request&X-Goog-Date=20220521T075313Z&X-Goog-Expires=345599&X-Goog-SignedHeaders=host&X-Goog-Signature=a6c60d5aa2f2e2ca59c965df3320651aa454c20beba955120604cc669824211ee687cabd68b7bffbfaec7815c4bd0697b962db918eb4021d45f1e7d0e9d7cf1ee72c9e438ce9537e6279b0894cd71446bc03ab00c2747994291a579401ee09af6e6d9c5676c2387d9cf2b538a39ae2e944ae52a26fdd52eedae8f1cb80302a2896d9bd615700b6a39eb81460998a2bdf74d2d5ac4c529179b658b88117ce29911302f3f9f61fb1855d9fbb944d76970ff309a493cf7ac431a6e03b23002c6dc60793cd3f2c50df7f1de39d49737bb61a68343ee598fc52f7aa3bc202180f60ee11207ec7535e47c84794845cd669ef3ab242eb12c908e33df3b0393579d4e8e6\" width=500>\n",
    "    <br>\n",
    "    <div style=\"color:orange; \n",
    "    display: inline-block;\n",
    "    color: #999;\n",
    "    padding: 2px;\">图4-1 马里奥和他的金币</div>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.2 模板匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2.1 匹配步骤"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于一张模板图像$\\mathbf{T}$和输入图像$\\mathbf{I}$，令其大小分别为$w\\times h$和$W\\times H$ （$w{\\leq}W$，$h{\\leq}H$），我们按照以下匹配流程在$\\mathbf{I}$中寻找与$\\mathbf{T}$最相似的目标位置：\n",
    "\n",
    "1. 让模板图像在输入图像上滑动，在每个滑动位置$[i,j]$，计算模板与以$[i,j]$为左上角顶点，以$w\\times h$为大小的输入图像子图的相似度；\n",
    "2. 当上述滑动结束后，我们将得到一个相似度矩阵$\\mathbf{R}$，矩阵的每个元素$\\mathbf{R}[i,j]$是上述在滑动位置$[i,j]$处计算得到的相似度。不难得出，矩阵$\\mathbf{R}$的大小为$(W-w+1)\\times (H-h+1)$；\n",
    "3. 获得相似度矩阵之后，查找元素最大值所在的位置$[i^\\ast,j^\\ast]$。在输入图像中以$[i^\\ast,j^\\ast]$为左上角的坐标，以$w,h$为宽高的区域便是输入图像中与模板图像最相似的区域，也就是我们要找的目标的位置。\n",
    "\n",
    "\n",
    "<center>\n",
    "    <img style=\"border-radius: 0.3125em;\" \n",
    "    src=\"https://storage.googleapis.com/kagglesdsdata/datasets/2176885/3648317/muban.png?X-Goog-Algorithm=GOOG4-RSA-SHA256&X-Goog-Credential=databundle-worker-v2%40kaggle-161607.iam.gserviceaccount.com%2F20220523%2Fauto%2Fstorage%2Fgoog4_request&X-Goog-Date=20220523T152019Z&X-Goog-Expires=345599&X-Goog-SignedHeaders=host&X-Goog-Signature=94c8ffc193e5571f41493d39ee08d81421c21067207c87374d85dde2f5783b206a5106497417c48d03982f233fb16291b49be7ade7d21f8bffcbeed51919030ac435345b38cacd567ac644eaf1dc141da1238f57a1f2fa68e97dde9d65e7fed8696a7f9c10020b1c22511c5828b6d35c0e04ca0a53e0a686c21de084424b135b42d033d6c6663d7f280b44e643f5c2351c4174fe38be4c2cf2e5d5203723433e3bcf0eed07fa926f127183fda185c6e7dba6dc2c9f4e715fb9267cd171f4cb7303e98ae4b14c6a462b432e104d2c1cbf1eed9819be18d54e9268ffc3a52a5004a5a121cf3e276a43d0fe0d6945c38ca3847db7ac7f83e466e0eebfcb27ca6a4c\" width=500>\n",
    "    <br>\n",
    "    <div style=\"color:orange; \n",
    "    display: inline-block;\n",
    "    color: #999;\n",
    "    padding: 2px;\">图4-2 模板匹配示意</div>\n",
    "</center>\n",
    "\n",
    "\n",
    "\n",
    "如图 4-2 所示，我们需要在右图（输入图像）中寻找与左图（模板图像）最相似的区域，因此我们将模板图像从输入图像的左上角开始（即右图中黄色框的位置），进行滑动，分别计算每一个位置的相似度，并将具有最大相似度的子图作为输出。从而实现输入图像中的模板匹配。\n",
    "\n",
    "不过，我们该如何计算相似度呢？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2.2 相似度度量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.2.2.1 互相关"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们先介绍一种最基本的相似度度量——互相关（cross-corelation）：将模板与输入图像子图的对应位置元素相乘并求和。在位置$[i,j]$处（即以$[i,j]$为左上角顶点）模板与输入图像子图互相关计算公式为：\n",
    "\n",
    "$$\\mathbf{R}[i,j]={\\sum_{m}\\sum_n\\mathbf{I}[m,n] \\cdot \\mathbf{T}[m-i, n-j]}$$\n",
    "\n",
    "其中，$[m,n]$是输入图像坐标系下任一像素点的坐标，则$[m-i, n-j]$是模板上对应该像素点的坐标。\n",
    "\n",
    "不知大家是否觉得上式似曾相识？回顾第二章二维卷积的公式，它们之间的差别仅仅只有$\\mathbf{T}$是否翻转！而在深度学习的主流工具开发包中，如Pytorch和Caffe，都是假设卷积神经网络的卷积核是已经翻转过的，也就是说实际上我们平时用的卷积神经网络的代码，其实计算的是互相关。这也难怪不少人工智能的大佬认为卷积神经网络其实是在做模板匹配。如已故著名物理学家史蒂夫·霍金（Stephen Hawking）的学生——艾伦·尤尔（Alan Yuille）教授，他是人工智能领域的先驱，曾不止一次向笔者提到卷积神经网络在做模板匹配。\n",
    "\n",
    "这里笔者只是转述不同的学术见解，并不作评价。我们言归正传，接下来我们编程实现一下上述互相关公式，并测试下是否可以找到我们想要的模板匹配效果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2022-05-24T02:48:57.975361Z",
     "iopub.status.busy": "2022-05-24T02:48:57.974952Z",
     "iopub.status.idle": "2022-05-24T02:48:58.257253Z",
     "shell.execute_reply": "2022-05-24T02:48:58.255946Z",
     "shell.execute_reply.started": "2022-05-24T02:48:57.975263Z"
    }
   },
   "outputs": [],
   "source": [
    "import cv2\n",
    "from matplotlib import pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "def CCORR(img, temp):\n",
    "    w, h = temp.shape[::-1]\n",
    "    W, H = img.shape[::-1]\n",
    "    img = np.array(img, dtype='float')\n",
    "    temp = np.array(temp, dtype='float')\n",
    "    res = np.zeros((W - w + 1, H - h + 1))\n",
    "    for i in range(W - w + 1):\n",
    "        for j in range(H - h + 1):\n",
    "            res[i, j] = np.sum(temp * img[j:j + h, i:i + w])\n",
    "    return res\n",
    "    \n",
    "    \n",
    "class temp_match_single():\n",
    "    def __init__(self, img, temp):\n",
    "        self.img = img\n",
    "        self.temp = temp\n",
    "    \n",
    "    def show_origin(self):\n",
    "        plt.imshow(self.temp[:, :, ::-1])\n",
    "        plt.title('Template Image'), plt.xticks([]), plt.yticks([])\n",
    "        plt.show()\n",
    "\n",
    "        plt.imshow(self.img[:, :, ::-1])\n",
    "        plt.title('Target Image'), plt.xticks([]), plt.yticks([])\n",
    "        plt.show()\n",
    "    \n",
    "\n",
    "        \n",
    "    def match(self):\n",
    "        img = cv2.cvtColor(self.img, cv2.COLOR_BGR2GRAY)\n",
    "        temp = cv2.cvtColor(self.temp, cv2.COLOR_BGR2GRAY)\n",
    "        w, h = temp.shape[::-1]\n",
    "        res = CCORR(img, temp)\n",
    "        loc = np.where(res == np.max(res))\n",
    "        top_left = (int(loc[0]), int(loc[1]))\n",
    "        bottom_right = (top_left[0] + w, top_left[1] + h)\n",
    "        cv2.rectangle(self.img, top_left, bottom_right, (255,255,255), 1)\n",
    "        plt.imshow(self.img[:, :, ::-1])\n",
    "        plt.title('Matching Result by CCORR') \n",
    "        plt.xticks([])\n",
    "        plt.yticks([])\n",
    "        plt.show()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2022-05-24T02:48:58.260253Z",
     "iopub.status.busy": "2022-05-24T02:48:58.259509Z",
     "iopub.status.idle": "2022-05-24T02:49:02.109078Z",
     "shell.execute_reply": "2022-05-24T02:49:02.107929Z",
     "shell.execute_reply.started": "2022-05-24T02:48:58.260204Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 59488 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 157980 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 158720 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "img = cv2.imread('lena_tri.jpg')\n",
    "template = cv2.imread('lena_small.png')\n",
    "\n",
    "test = temp_match_single(img, template)\n",
    "test.show_origin()\n",
    "\n",
    "test.match()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "结果有没有出乎大家的意料？我们并没有匹配到正确目标！问题出在哪里呢？给大家一点时间思考。\n",
    "\n",
    "大家仔细观察互相关的公式，其结果是模板图像像素值和输入图像子图像素值直接相乘，那么在模板一定的情况下，子图整体像素值越大（也就是越亮），那么它们之间的乘积也就越大。所以互相关更容易找到输入图像中亮度高的区域，而不是和模板最相似的区域。那么如何解决这个问题呢？显然我们需要该相似度度量与输入图像整体像素值大小无关，这就需要标准化。接下来我们引入另一种度量指标——标准化互相关。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.2.2.2 标准化互相关"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "标准化互相关需对模板和输入图像子图做归一化，去除像素值整体大小的影响。模板与输入图像子图标准化互相关计算公式为：\n",
    "\n",
    "$$\\mathbf{R}(x, y)=\\frac{\\sum_{m}\\sum_n\\mathbf{I}[m,n] \\cdot \\mathbf{T}[m-i, n-j]}{\\sqrt{\\sum_{m}\\sum_n\\mathbf{I}^2[m,n] }\\sqrt{\\sum_{m}\\sum_n\\mathbf{T}^2[m-i, n-j]}}$$\n",
    "\n",
    "我们按照上述公式，编程实现标准化互相关，这里我们重写CCORR函数，再试试是否可以找到我们想要的目标区域。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2022-05-24T02:49:02.110630Z",
     "iopub.status.busy": "2022-05-24T02:49:02.110347Z",
     "iopub.status.idle": "2022-05-24T02:49:08.986928Z",
     "shell.execute_reply": "2022-05-24T02:49:08.985777Z",
     "shell.execute_reply.started": "2022-05-24T02:49:02.110597Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 158468 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def CCORR(img, temp, normalize=True):\n",
    "    w, h = temp.shape[::-1]\n",
    "    W, H = img.shape[::-1]\n",
    "    res = np.zeros((W-w+1, H-h+1))\n",
    "    img = np.array(img, dtype='float')\n",
    "    temp = np.array(temp, dtype='float')\n",
    "    t = np.sqrt(np.sum(temp**2))\n",
    "    for i in range(W-w+1):\n",
    "        for j in range(H-h+1):\n",
    "            res[i,j] = np.sum(temp*img[j:j+h, i:i+w])\n",
    "            if normalize:\n",
    "                res[i,j] = res[i,j] / t / np.sqrt(np.sum(img[j:j+h, i:i+w]**2)) \n",
    "    return res\n",
    "    \n",
    "img = cv2.imread('lena_tri.jpg')\n",
    "template = cv2.imread('lena_small.png')\n",
    "\n",
    "test = temp_match_single(img, template)\n",
    "#test.show_origin()\n",
    "\n",
    "test.match()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由结果可见，我们通过标准化，消除了输入图像子图整体亮度变化对相似度计算的影响，提升了互相关度量的鲁棒性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.3 多目标模板匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "接下来，我们将实现多目标模板匹配。与单目标模板匹配不同的是，在多目标匹配任务中，我们需要设定一个阈值。当相似度大于（或小于）该阈值时，即可认为输入图像的子图即为需要匹配的对象。\n",
    "\n",
    "为了方便，我们将直接使用标准化互相关作为度量指标，并直接调用库函数cv2.TM_CCORR_NORMED来完成标准化互相关。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2022-05-24T02:49:08.989444Z",
     "iopub.status.busy": "2022-05-24T02:49:08.989039Z",
     "iopub.status.idle": "2022-05-24T02:49:09.001273Z",
     "shell.execute_reply": "2022-05-24T02:49:09.000237Z",
     "shell.execute_reply.started": "2022-05-24T02:49:08.989411Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "\n",
    "class temp_match_multi():\n",
    "    def __init__(self, img, temp):\n",
    "        self.img = img\n",
    "        self.temp = temp\n",
    "        \n",
    "    def show_origin(self):\n",
    "        plt.imshow(self.temp[:, :, ::-1])\n",
    "        plt.title('Template Image'), plt.xticks([]), plt.yticks([])\n",
    "        plt.show()\n",
    "\n",
    "        plt.imshow(self.img[:, :, ::-1])\n",
    "        plt.title('Target Image'), plt.xticks([]), plt.yticks([])\n",
    "        plt.show()\n",
    "        \n",
    "    def match(self):\n",
    "        temp = cv2.cvtColor(self.temp, cv2.COLOR_BGR2GRAY)\n",
    "        img = cv2.cvtColor(self.img, cv2.COLOR_BGR2GRAY)\n",
    "\n",
    "        w, h = temp.shape[::-1]\n",
    "        method = eval('cv2.TM_CCORR_NORMED')\n",
    "        res = cv2.matchTemplate(img, temp, method)\n",
    "        threshold = 0.98\n",
    "        loc = np.where(res >= threshold)\n",
    "        for pt in zip(*loc[::-1]):\n",
    "            cv2.rectangle(self.img, pt, (pt[0] + w, pt[1] + h), (255,255,255), 1)\n",
    "            plt.imshow(self.img[:, :, ::-1]), plt.xticks([]), plt.yticks([])\n",
    "        plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2022-05-24T02:49:09.003325Z",
     "iopub.status.busy": "2022-05-24T02:49:09.002910Z",
     "iopub.status.idle": "2022-05-24T02:49:18.173485Z",
     "shell.execute_reply": "2022-05-24T02:49:18.172456Z",
     "shell.execute_reply.started": "2022-05-24T02:49:09.003281Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 25276 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 42588 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 40380 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "img = cv2.imread('img.jpeg')\n",
    "template = cv2.imread('temp.jpg')\n",
    "\n",
    "test_multi = temp_match_multi(img, template)\n",
    "test_multi.show_origin()\n",
    "test_multi.match()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.4 总结"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在本章中，我们学习了模板匹配，这个计算机视觉中最基本的图像匹配任务。我们首先学习模板匹配的步骤，然后就不同的匹配相似度度量进行了讨论，并在单目标模板匹配任务上进行了验证。最后，我们实现了多目标模板匹配。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.5 习题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 习题 4.1：本章中我们所用的实验数据其模板和输入图像中的目标是完全一样的。如果图像中的目标发生了一些光照上的变化，比如亮度对比度发生了变化：一部分像素的亮度值增加，一部分像素的亮度减小，那么基于标准化互相关仍然能匹配到我们想要的目标吗？如果不行，请提出在这种情况下还能成功匹配的相似度度量，并实现验证。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
