{
 "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://pic4.zhimg.com/80/v2-3b52c4e7dedf6dcb7a9de7e9b733718f_1440w.webp\" 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://pic2.zhimg.com/80/v2-60b470a9c3fa3a90457fb40fe9e31af9_1440w.jpg\" 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-correlation）：将模板与输入图像子图的对应位置元素相乘并求和。在位置$[i,j]$处（即以$[i,j]$为左上角顶点）模板与输入图像子图互相关计算公式为：\n",
    "\n",
    "$$\\mathbf{R}[i,j]={\\sum_{m=i}^{i+w-1}\\sum_{n=j}^{j+h-1}\\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": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2022-09-20T10:50:04.158223Z",
     "iopub.status.busy": "2022-09-20T10:50:04.157747Z",
     "iopub.status.idle": "2022-09-20T10:50:04.170652Z",
     "shell.execute_reply": "2022-09-20T10:50:04.169792Z",
     "shell.execute_reply.started": "2022-09-20T10:50:04.158159Z"
    }
   },
   "outputs": [],
   "source": [
    "# utils 为之前章节已经撰写完成的函数包\n",
    "from utils import *\n",
    "\n",
    "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",
    "    \n",
    "    # 利用循环计算互相关的值\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",
    "# 构建单目标匹配类\n",
    "class temp_match_single():\n",
    "    def __init__(self, img, temp):\n",
    "        self.img = img\n",
    "        self.temp = temp\n",
    "        \n",
    "    def match(self):\n",
    "        # 输入目标图像\n",
    "        img = cv2.cvtColor(self.img, cv2.COLOR_BGR2GRAY)\n",
    "        # 输入模板图像\n",
    "        temp = cv2.cvtColor(self.temp, cv2.COLOR_BGR2GRAY)\n",
    "        w, h = temp.shape[::-1]\n",
    "        \n",
    "        # 计算互相关\n",
    "        res = CCORR(img, temp)\n",
    "        \n",
    "        # 找到互相关值最大的位置\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",
    "        \n",
    "        # 将其框出\n",
    "        cv2.rectangle(self.img, top_left, bottom_right, (255,255,255), 1)\n",
    "        plot_image(self.img[:, :, ::-1], 'Matching Result by CCORR')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们导入一张图像和一个模板，进行模板匹配。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2022-09-20T10:50:35.989432Z",
     "iopub.status.busy": "2022-09-20T10:50:35.989174Z",
     "iopub.status.idle": "2022-09-20T10:50:38.902199Z",
     "shell.execute_reply": "2022-09-20T10:50:38.901617Z",
     "shell.execute_reply.started": "2022-09-20T10:50:35.989409Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 185324 characters]\n",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 382748 characters]\n",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 385972 characters]\n",
      "text/plain": [
       "<Figure size 640x480 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",
    "plot_image(test.temp[:, :, ::-1], 'Template Image')\n",
    "plot_image(test.img[:, :, ::-1], 'Target Image')\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}(i,j)=\\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": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2022-09-20T10:51:26.021336Z",
     "iopub.status.busy": "2022-09-20T10:51:26.020999Z",
     "iopub.status.idle": "2022-09-20T10:51:31.220148Z",
     "shell.execute_reply": "2022-09-20T10:51:31.219543Z",
     "shell.execute_reply.started": "2022-09-20T10:51:26.021308Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 385920 characters]\n",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 对原有CCORR()函数进行改写，定义标准化互相关\n",
    "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",
    "            # 在这里进行归一化操作\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",
    "\n",
    "test.match()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由结果可见，我们通过标准化，消除了输入图像子图整体亮度变化对相似度计算的影响，提升了互相关度量的鲁棒性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.3 多目标模板匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "接下来，将实现多目标模板匹配。与单目标模板匹配不同的是，在多目标匹配任务中，需要设定一个阈值。当模板与某个输入图像子图的相似度大于该阈值时，即可认为该输入图像子图即为需要匹配的对象。\n",
    "\n",
    "这里，我们需要额外对阈值的选择进行说明。如果阈值设定的过小，那么图像中会有很多子图被认为和模板匹配，造成很多虚假匹配；而一旦阈值设定的过大，则图像中也许没有任何子图可以和模板匹配上。因此，在多目标模板匹配中，需要选择一个合适的阈值。设定需要匹配的个数$k$，并将阈值设定为第$k+1$大的相似度的值。\n",
    "\n",
    "为了方便，我们将直接使用标准化互相关作为度量指标，并直接调用库函数cv2.TM_CCORR_NORMED来完成标准化互相关。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2022-09-20T10:55:27.060527Z",
     "iopub.status.busy": "2022-09-20T10:55:27.060279Z",
     "iopub.status.idle": "2022-09-20T10:55:27.075334Z",
     "shell.execute_reply": "2022-09-20T10:55:27.073972Z",
     "shell.execute_reply.started": "2022-09-20T10:55:27.060502Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# 利用快速排序算法找到数列中第k大的值\n",
    "def findKth(s, k):\n",
    "    return findKth_c(s, 0, len(s) - 1, k)\n",
    "\n",
    "\n",
    "def findKth_c(s, low, high, k):\n",
    "    m = partition(s, low, high)\n",
    "    if m == len(s) - k:\n",
    "        return s[m]\n",
    "    elif m < len(s) - k:\n",
    "        return findKth_c(s, m + 1, high, k)\n",
    "    else:\n",
    "        return findKth_c(s, low, m - 1, k)\n",
    "\n",
    "\n",
    "def partition(s, low, high):\n",
    "    pivot, j = s[low], low\n",
    "    for i in range(low + 1, high + 1):\n",
    "        if s[i] <= pivot:\n",
    "            j += 1\n",
    "            s[i], s[j] = s[j], s[i]\n",
    "    s[j], s[low] = s[low], s[j]\n",
    "    return j\n",
    "\n",
    "\n",
    "# 构建多目标模板匹配类\n",
    "class temp_match_multi():\n",
    "    def __init__(self, img, temp, k=50):\n",
    "        self.img = img\n",
    "        self.temp = temp\n",
    "        # 定义需要匹配的个数\n",
    "        self.k = k\n",
    "        \n",
    "    def match(self):\n",
    "        # 输入模板图像和目标图像\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",
    "        temp = list(np.array(res).flatten())\n",
    "        \n",
    "        # 寻找res中第k大的值\n",
    "        threshold = findKth(temp, self.k+1)\n",
    "        print('设定的阈值为：', threshold)\n",
    "        loc = np.where(res >= threshold)\n",
    "        \n",
    "        # 将找到的子图框选出\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": 7,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2022-09-20T10:55:29.521602Z",
     "iopub.status.busy": "2022-09-20T10:55:29.521098Z",
     "iopub.status.idle": "2022-09-20T10:55:36.166260Z",
     "shell.execute_reply": "2022-09-20T10:55:36.165446Z",
     "shell.execute_reply.started": "2022-09-20T10:55:29.521542Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 37884 characters]\n",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 41316 characters]\n",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "设定的阈值为： 0.99798167\n"
     ]
    },
    {
     "data": {
      "image/png": "[encoded data, 40032 characters]\n",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "img = cv2.imread('img.png')\n",
    "template = cv2.imread('temp.png')\n",
    "\n",
    "test_multi = temp_match_multi(img, template, k=50)\n",
    "plot_image(test_multi.temp[:, :, ::-1], 'Template Image')\n",
    "plot_image(test_multi.img[:, :, ::-1], 'Target Image')\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：本章中我们所用的实验数据其模板和输入图像中的目标是完全一样的。如果图像中的目标发生了一些光照上的变化，比如亮度对比度发生了变化：一部分像素的亮度值增加，一部分像素的亮度减小，那么基于标准化互相关仍然能匹配到我们想要的目标吗？如果不行，请提出在这种情况下还能成功匹配的相似度度量，并实现验证。\n",
    "\n",
    "#### 习题 4.2：请计算在模板匹配中使用标准化互相关作为相似度度量的计算复杂度，其中图像大小为$H\\times W$，模板大小为$h\\times w$。\n",
    "\n",
    "#### 习题 4.3：如果模板的大小发生变化，会对模板匹配的结果有影响吗？请使用提供的img.png和temp.png、temp_large.png，进行实验测试。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
