纯前端实现图片的模板匹配

四月 25, 2020

基础介绍

模板匹配是指在当前图像A里寻找与图像B最相似的部分，本文中将图像A称为模板图像，将图像B称为搜索匹配图像。

引言：一般在Opencv里实现此种功能非常方便：直接调用

result = cv2.matchTemplate(templ, search, method)

templ 为原始图像
search 为搜索匹配图像，它的尺寸必须小于或等于原始图像
method 表示匹配方式

method一般取值：

差值平方和匹配 CV_TM_SQDIFF, 以方差为依据进行匹配。如果完全匹配，结果为0，不匹配则值为很大
标准化差值平方和匹配 CV_TM_SQDIFF_NORMED, 这个方法其实和差值平方和算法是类似的。只不过对图像和模板进行了标准化操作，这种标准化操作可以保证当模板和图像各个像素的亮度都乘上了同一个系数时，相关度不发生变化
相关匹配, CV_TM_CCORR, 这类方法采用模板和图像的互相关计算作为相似度的度量方法，所以较大的数表示匹配程度较高，0标识最坏的匹配效果
标准化相关匹配 CV_TM_CCORR_NORMED, 这个方法和标准化差值平方和匹配类似，都是去除了亮度线性变化对相似度计算的影响。可以保证图像和模板同时变亮或变暗k倍时结果不变
相关系数匹配 CV_TM_CCOEFF, 这种方法也叫做相关匹配，但是和上面的 CV_TM_CCORR 匹配方法还是有不通过的。简单的说，这里是把图像和模板都减去了各自的平均值，使得这两幅图像都没有直流分量
标准相关系数匹配 CV_TM_CCOEFF_NORMED, 这是 OpenCV 支持的最复杂的一种相似度算法。这里的相关运算就是数理统计学科的相关系数计算方法。具体的说，就是在减去了各自的平均值之外，还要各自除以各自的方差。经过减去平均值和除以方差这么两步操作之后，无论是我们的待检图像还是模板都被标准化了，这样可以保证图像和模板分别改变光照亮不影响计算结果。计算出的相关系数被限制在了 -1 到 1 之间，1 表示完全相同，-1 表示两幅图像的亮度正好相反，0 表示两幅图像之间没有线性关系

参考 OpenCV 学习笔记（模板匹配）

当然这里我们不是主要将Opencv的api的，只是单独提出来，说明在前端实现对应的算法，就能进行模板匹配。

比如以CV_TM_SQDIFF算法为例：

遍历的起始坐标从原图A的左数第1各像素值开始
以搜索匹配B图的大小（w h）匹配比较原图上对应空间上(w h)的像素值
依次进行A图右移一像素去匹配B图，直到A图右侧(w)小于B图的w，然后换行再匹配
重复进行到A图距离底部不支持h大于B图的高度
最后找出最小误差值

我们的目标是实现这两张图的匹配：
原图A
搜索图B

这里实现对应的js算法

/**
 * 差值平方和匹配 CV_TM_SQDIFF
 * @param template 匹配的图片灰度值[x,x,x,...] w * h 长度的灰度图片数据
 * @param search 搜索的图片灰度值[x,x,x,...] w * h 长度的灰度图片数据
 * @param tWidth 匹配图片的width
 * @param tHeight 匹配图片的height
 * @param sWidth 搜索图片的width
 * @param sHeight 搜索图片的height
 * @param type 匹配方式
 */
const cvTmSqDiff = (template, search, tWidth, tHeight, sWidth, sHeight) => {
  let minValue = Infinity;
  let x = -1;
  let y = -1;
  for (let th = 0; th < tHeight; th += 1) {
    for (let tW = 0; tW < tWidth; tW += 1) {
      if (tW + sWidth > tWidth || th + sHeight > tHeight) {
        continue;
      }
      let sum = 0;
      for (let sH = 0; sH < sHeight; sH += 1) {
        for (let sW = 0; sW < sWidth; sW += 1) {
          const tValue = template[(th + sH) * tWidth + tW + sW];
          const sValue = search[sH * sWidth + sW];
          sum += (tValue - sValue) * (tValue - sValue);
        }
      }
      if (minValue > sum) {
        minValue = sum;
        x = tW;
        y = th;
      }
      if (sum === 0) {
        return { x, y };
      }
    }
  }
  return { x, y };
};

因此根据上述算法的可行性，我们可以先将A图和B图进行RGB值转Gary值：
借鉴OpenCV中的转换方式

Gray = 0.299*r + 0.587*g + 0.114*b

再将转换好A图和B图的灰度值进行匹配比较：

const {x, y} = cvTmSqDiff(template, search, tWidth, tHeight, sWidth, sHeight);

得到的x、y则是在原图A上的对应匹配成功的坐标，加上对应B图的大小，我们则可以在原图的基础上画出一个矩形框表示匹配的区域：
result

前端分步实现

上面大概讲了匹配的大致实现思路，下面开始正式的js代码实现：

1、加载原图A和原图B

Promise.all([imgLoader("./lena.png"), imgLoader("./search.png")]).then(
    (values: any) => {
        ...
    }
);

2、得到图片数据的rgb值，并转化为灰度值

Promise.all([getImageData(values[0]), getImageData(values[1])]).then(
    (dataValues: any) => {
        const model = rgbToGary(dataValues[0]);
        const search = rgbToGary(dataValues[1]);
        ...
    }
);

3、获取对应的匹配坐标

const posi = getTemplatePos(
    model,
    search,
    dataValues[0].width,
    dataValues[0].height,
    dataValues[1].width,
    dataValues[1].height,
    "CV_TM_CCOEFF_NORMED"
);

4、绘制原图和匹配到矩形框

const canvas = document.createElement("canvas");
canvas.width = dataValues[0].width;
canvas.height = dataValues[0].height;
const ctx = canvas.getContext("2d");

ctx.drawImage(values[0], 0, 0);
ctx.strokeStyle = "red";
ctx.strokeRect(
    posi.x,
    posi.y,
    dataValues[1].width,
    dataValues[1].height
);
document.body.appendChild(canvas);

上述所用的的函数imgLoader getImageData rgbToGary getTemplatePos 都可以在这里找到xy-imageloader
也可以npm安装：npm i xy-imageloader

完整代码

import imgLoader, { getImageData, rgbToGary } from "xy-imageloader";
import { getTemplatePos } from "xy-imageloader/lib/utils";
Promise.all([imgLoader("./lena.png"), imgLoader("./search.png")]).then(
    (values: any) => {
        Promise.all([getImageData(values[0]), getImageData(values[1])]).then(
            (dataValues: any) => {
            const model = rgbToGary(dataValues[0]);
            const search = rgbToGary(dataValues[1]);
            const posi = getTemplatePos(
                model,
                search,
                dataValues[0].width,
                dataValues[0].height,
                dataValues[1].width,
                dataValues[1].height,
                "CV_TM_CCOEFF_NORMED"
            );
            const canvas = document.createElement("canvas");
            canvas.width = dataValues[0].width;
            canvas.height = dataValues[0].height;
            const ctx = canvas.getContext("2d");

            ctx.drawImage(values[0], 0, 0);
            ctx.strokeStyle = "red";
            ctx.strokeRect(
                posi.x,
                posi.y,
                dataValues[1].width,
                dataValues[1].height
            );
            document.body.appendChild(canvas);
            }
        );
    }
);

附算法思想：

CV_TM_SQDIFF
CV_TM_SQDIFF_NORMED
CV_TM_CCORR
CV_TM_CCORR_NORMED
CV_TM_CCOEFF
CV_TM_CCOEFF_NORMED

算法具体实现可参考 xy-imageloader

← DDA算法文章 →