{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 代码实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们编程实现互相关公式，并测试下是否可以达到想要的模板匹配效果。"
   ]
  },
  {
   "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]",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 382748 characters]",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 385972 characters]",
      "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": [
    "再编程实现标准化互相关，这里重写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]",
      "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": [
    "接下来，将实现多目标模板匹配。\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]",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "[encoded data, 41316 characters]",
      "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]",
      "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()"
   ]
  }
 ],
 "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.8.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
