{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第4章 模板匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.1 简介"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在这一章中，我们将重点介绍模板匹配的原理以及应用实战。模板匹配是数字图像处理的重要组成部分之一，把不同传感器或同一传感器在不同时间、不同成像条件下对同一景物获取的两幅或多幅图像在空间上对准，或根据已知模式到另一幅图中寻找相应模式的处理方法就叫做模板匹配。简单来说，在计算机视觉中，模板匹配的目的是要在一张图片中找到与模板图片相似度最高的那一部分。根据目标的数目，我们可以将模板匹配分为单目标模板匹配和多目标模板匹配。那么接下来，就让我们一起来学习模板匹配的相关知识。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.2 模板匹配原理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2.1 计算步骤"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们已经知晓模板匹配任务的具体内容。对于一张模板图像$T$和输入图像$I$，令其大小分别为$w\\times h$、$W\\times H$，我们可以遵循以下的计算流程去在$I$中寻找与$T$最相似的图像：\n",
    "\n",
    "1. 令模板图像在输入图像上进行滑动，比较在模板图像下模板与输入图像的子图的相似度；\n",
    "2. 当模板图像在输入图像上滑动完毕后，我们将得到一个相似度矩阵，每一个元素在矩阵中所处的位置表示模板图像滑动到输入图像中左上角的位置，元素的值表示在该位置处模板模板与输入图像子图的相似度。不难得出，矩阵的大小为$(W-w+1,H-h+1)$；\n",
    "3. 获得相似度矩阵之后，查找元素最大值所在的位置，并将其作为输入图像中匹配区域左上角的坐标，将$(w,h)$作为匹配区域的宽度和高度。该区域便是输入图像中与模板图像最相似的区域。\n",
    "\n",
    "\n",
    "<center>\n",
    "    <img style=\"border-radius: 0.3125em;\" \n",
    "    src=\"muban.png\" width=500>\n",
    "    <br>\n",
    "    <div style=\"color:orange; \n",
    "    display: inline-block;\n",
    "    color: #999;\n",
    "    padding: 2px;\">图4-1 模板匹配示意</div>\n",
    "</center>\n",
    "\n",
    "\n",
    "\n",
    "如图 4-1 所示，我们需要在右边的图中寻找与左图最相似的部分，因此我们将模板图像从输入图像的左上角开始（即右图中黄色框的位置），进行滑动，分别计算每一个位置的相似度，并将具有最大相似度的子图作为输出。如此一来，我们便可实现模板匹配的相关功能。\n",
    "\n",
    "不过，我们该如何计算相似度呢？接下来，我们将介绍几种相似度的度量指标。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2.2 相似度度量指标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在开始介绍之前，我们先对一些数学符号进行定义。$T$表示模板图片，$I$表示输入图片，$R$表示相似度矩阵，$(x,y)$表示输入图像中的某一个位置。为了更好的表示，我们将计算模板图片与输入图像中$(x,y)$处子图的相似度函数。我们选择以下两种不同的度量指标分别进行介绍："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.2.2.1 标准化差值平方和匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "该指标计算模板与某个子图的对应像素的差值平方和，越相似值越小。计算公式为：\n",
    "\n",
    "$$R(x, y)=\\frac{\\sum_{x^{\\prime}, y^{\\prime}}\\left(T\\left(x^{\\prime}, y^{\\prime}\\right)-I\\left(x+x^{\\prime}, y+y^{\\prime}\\right)\\right)^{2}}{\\sqrt{\\sum_{x^{\\prime}, y^{\\prime}} T\\left(x^{\\prime}, y^{\\prime}\\right)^{2} \\sum_{x^{\\prime}, y^{\\prime}} I\\left(x+x^{\\prime}, y+y^{\\prime}\\right)^{2}}}$$\n",
    "\n",
    "其中，$(x,y)$是$I$中模板滑动到的位置左上角的坐标，$(x^{\\prime}, y^{\\prime})$是相对于模板而言当前子图的像素点的坐标。换言之，$(x+x^{\\prime}, y+y^{\\prime})$是当前子图的像素点相对于$I$的绝对坐标。\n",
    "\n",
    "我们使用标准化是为了保证图像和模板同时变亮或变暗时，相关度不发生变化，也增加了该度量指标的鲁棒性。该指标可以用cv2.TM_SQDIEF_NORMED()实现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.2.2.2 标准化相关匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将模板与子图的对应位置元素相乘并求和，再加以标准化即可，越相似值越大，公式为：\n",
    "\n",
    "$$R(x, y)=\\frac{\\sum_{x^{\\prime}, y^{\\prime}}\\left(T\\left(x^{\\prime}, y^{\\prime}\\right) \\times I\\left(x+x^{\\prime}, y+y^{\\prime}\\right)\\right)}{\\sqrt{\\sum_{x^{\\prime}, y^{\\prime}} T\\left(x^{\\prime}, y^{\\prime}\\right)^{2} \\sum_{x^{\\prime}, y^{\\prime}} I\\left(x+x^{\\prime}, y+y^{\\prime}\\right)^{2}}}$$\n",
    "\n",
    "和标准化差值平方和匹配相同，当图像和模板同时变亮或变暗时，利用标准化相关匹配计算的相似度不发生变化。该度量指标可以通过cv2.TM_CCORR_NORMED()实现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.3 模板匹配示例"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "接下来，我们将在代码中进行模板匹配方法的编写。我们先进行单目标匹配，并用不同的相似度度量指标进行评价。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cv2\n",
    "from matplotlib import pyplot as plt\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, cmap='gray')\n",
    "        plt.title('Template Image'), plt.xticks([]), plt.yticks([])\n",
    "        plt.show()\n",
    "\n",
    "        plt.imshow(self.img, cmap='gray')\n",
    "        plt.title('Target Image'), plt.xticks([]), plt.yticks([])\n",
    "        plt.show()\n",
    "    \n",
    "    def match(self):\n",
    "        w, h = self.temp.shape[::-1]\n",
    "        methods = ['cv2.TM_SQDIFF_NORMED', 'cv2.TM_CCORR_NORMED']\n",
    "        for i, meth in enumerate(methods):\n",
    "            # 进行模板匹配\n",
    "            method = eval(meth)\n",
    "            res = cv2.matchTemplate(self.img, self.temp, method)\n",
    "            min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(res)\n",
    "\n",
    "            # 两种方法一种是值越大越相似，另一种相反，因此需分类讨论\n",
    "            if method is cv2.TM_SQDIFF_NORMED:\n",
    "                top_left = min_loc\n",
    "            else:\n",
    "                top_left = max_loc\n",
    "            bottom_right = (top_left[0] + w, top_left[1] + h)\n",
    "            cv2.rectangle(self.img, top_left, bottom_right, 255, 2)\n",
    "            plt.imshow(self.img, cmap='gray')\n",
    "            plt.title('Matching Result by {}'.format(meth)), plt.xticks([]), plt.yticks([])\n",
    "            plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 39328 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 102248 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "img = cv2.imread('lena.jpeg', 0)\n",
    "template = cv2.imread('lena_small.png', 0)\n",
    "\n",
    "test = temp_match_single(img, template)\n",
    "test.show_origin()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 99420 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 99432 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "test.match()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "不难看出，使用不同的指标均可以达到相同的结果，我们也成功的在图片中找到了与模板最为相似的部分。\n",
    "\n",
    "在下面的实验中，我们将进行多目标模板匹配。与单目标模板匹配不同的是，在多目标任务中，我们需要设定一个阈值。当相似度大于（或小于）该阈值时，即可认为输入图像的子图即为需要匹配的对象。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "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, cmap='gray')\n",
    "        plt.title('Template Image'), plt.xticks([]), plt.yticks([])\n",
    "        plt.show()\n",
    "\n",
    "        plt.imshow(self.img, cmap='gray')\n",
    "        plt.title('Target Image'), plt.xticks([]), plt.yticks([])\n",
    "        plt.show()\n",
    "        \n",
    "    def match(self):\n",
    "        w, h = self.temp.shape[::-1]\n",
    "        method = eval('cv2.TM_CCORR_NORMED')\n",
    "        res = cv2.matchTemplate(self.img, self.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), 2)\n",
    "        plt.imshow(self.img, cmap='gray')\n",
    "        plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 13016 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 25048 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "img = cv2.imread('img.jpeg', 0)\n",
    "template = cv2.imread('temp.jpg', 0)\n",
    "\n",
    "test_multi = temp_match_multi(img, template)\n",
    "test_multi.show_origin()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 28272 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "test_multi.match()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.4 总结"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在本章中，我们学习了模板匹配的原理及其应用。我们首先学习模板匹配的计算流程，并就不同的相关系数进行相应的介绍，接着，我们分别进行了单目标和多目标的模板匹配任务的实现。我们使用的方法主要是对图像的像素值进行直接处理计算所得，除此之外，也有一些别的方法可以实现模板匹配，比如利用梯度与模板边缘信息等等进行匹配，这里不一一介绍，感兴趣的同学可以自行查阅相关资料。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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": 2
}
