模板匹配概述

模板匹配是通过一张模板图片去另一张图中找到与模板相似部分的一种算法。一个模板是一张小图片，这个图片有一定的尺寸，有角度（一般是不旋转的矩形， 角度为0）。

基于像素匹配算法

模板匹配算法一般是通过滑窗的方式在待匹配的图像上滑动，通过比较模板与子图的相似度，找到相似度最大的子图。这种算法最核心部分在于如何设计一个相似性函数。
最容易想到的一个相似性函数便是欧式距离：

欧式距离相似性函数

将这个相似性函数展开，可以得：

展开后相似性函数

可以看出，只有第二项是有意义的，因为第一项和第三项的值在选定模板后是固定的。对于欧式距离相似函数，值越大表示越不相似，也就是说，第二项的值越小则越不相似。

将第二项进行归一化：

归一化相似性函数

那么当R(i, j)为1时，表示模板与子图完全相等。

opencv实现

cv::matchTemplate(const CvArr* image, 　　//欲搜索的图像。它应该是单通道、8-比特或32-比特 浮点数图像
const CvArr* template,　　//搜索模板，不能大于输入图像，且与输入图像具有一样的数据类型
CvArr* result, 　　　　//比较结果的映射图像。单通道、32-比特浮点数.
　　　　　　　　　　　　若图像是W×H而templ是w×h，则result一定是(W-w+1）×(H-h+1）
int method　　　　　　//CV_TM_SQDIFF、CV_TM_SQDIFF_NORMED、CV_TM_CCORR、
　　　　　　　　　　　　CV_TM_CCORR_NORMED、CV_TM_CCOEFF、CV_TM_CCOEFF_NORMED
);

函数来进行模板匹配。其中的method参数具体如下:

• CV_TM_SQDIFF 平方差匹配法：该方法采用平方差来进行匹配；最好的匹配值为0；匹配越差，匹配值越大。
• CV_TM_CCORR 相关匹配法：该方法采用乘法操作；数值越大表明匹配程度越好。
• CV_TM_CCOEFF 相关系数匹配法：1表示完美的匹配；-1表示最差的匹配。
• CV_TM_SQDIFF_NORMED 归一化平方差匹配法
• CV_TM_CCORR_NORMED 归一化相关匹配法
• CV_TM_CCOEFF_NORMED 归一化相关系数匹配法

在通过matchTemplate函数进行模板匹配后，可以得到一个映射图，这张图中最大值的地方便是匹配度最大的子图的左上角坐标，可以使用cv::minMaxLoc函数获得子图位置和相应分数，再进行后续操作。

基于像素模板匹配的提速方案

• 使用局部匹配，即刚开始匹配时，并不是把所有的点同时进行匹配，而是选择隔行隔列进行匹配，当匹配度达到自己所规定的阈值时，再继续匹配剩下的没匹配的行列。
• 构建<a href="http://www.jianshu.com/p/b2da54d961ee">图像金字塔</a>进行逐步匹配，就是进行缩小扩大操作

传统模板匹配的缺陷在于不具有旋转不变形，若待匹配的图进行了旋转，那么这种滑窗的模板匹配方法当即失效。

可应对旋转缩放的模板匹配算法

使用传统的模板匹配速度较快，但是无法应对旋转和缩放问题。要解决旋转不变的 问题，必须要得到旋转不变的特征量，例如特征点。

SIFT/SURF/ORB特征匹配

使用SIFT或SURF计算得到模板和待匹配图像的特征点，然后使用RANSAC或者FLANN进行特征点匹配， 最后进行仿射变换便可得到匹配的位置。

• 特征点提取
• 特征点匹配
• 仿射变化
  这种方法的缺点有几个：
• 速度慢
• 对于很小的图提取不到足够多的特征点

python opencv实现（surf）：
# -- coding:utf-8 --
author = 'Microcosm'

import cv2
from image_process .image_process import *
import numpy as np

def filter_matches(kp1, kp2, matches, ratio = 0.75):
    mkp1, mkp2 = [], []
    for m in matches:
        if len(m) == 2 and m[0].distance < m[1].distance * ratio:
            m = m[0]
            mkp1.append( kp1[m.queryIdx] )
            mkp2.append( kp2[m.trainIdx] )
    p1 = np.float32([kp.pt for kp in mkp1])
    p2 = np.float32([kp.pt for kp in mkp2])
    kp_pairs = zip(mkp1, mkp2)
    return p1, p2, kp_pairs

def explore_match(win, img1, img2, kp_pairs, status = None, H = None):
    h1, w1 = img1.shape[:2]
    h2, w2 = img2.shape[:2]
    vis = np.zeros((max(h1, h2), w1+w2), np.uint8)
    vis[:h1, :w1] = img1
    vis[:h2, w1:w1+w2] = img2
    vis = cv2.cvtColor(vis, cv2.COLOR_GRAY2BGR)
    # get the position of template object find in detected image
    if H is not None:
        corners = np.float32([[0, 0], [w1, 0], [w1, h1], [0, h1]])
        img2 = cv2.warpPerspective(img2, H, (img2.shape[1], img2.shape[0]))
        # cv2.imshow('jj', img2)
        # cv2.waitKey()
        corners = np.int32( cv2.perspectiveTransform(corners.reshape(1, -1, 2), H).reshape(-1, 2) + (w1, 0) )
        cv2.polylines(vis, [corners], True, (0, 0, 255)) 
    # draw lines that connect match feature points
    if status is None:
        status = np.ones(len(kp_pairs), np.bool)
    p1 = np.int32([kpp[0].pt for kpp in kp_pairs])
    p2 = np.int32([kpp[1].pt for kpp in kp_pairs]) + (w1, 0)

    green = (0, 255, 0)
    red = (0, 0, 255)
    white = (255, 255, 255)
    kp_color = (51, 103, 236)
    for (x1, y1), (x2, y2), inlier in zip(p1, p2, status):
        if inlier:
            col = green
            cv2.circle(vis, (x1, y1), 2, col, -1)
            cv2.circle(vis, (x2, y2), 2, col, -1)
        else:
            col = red
            r = 2
            thickness = 3
            cv2.line(vis, (x1-r, y1-r), (x1+r, y1+r), col, thickness)
            cv2.line(vis, (x1-r, y1+r), (x1+r, y1-r), col, thickness)
            cv2.line(vis, (x2-r, y2-r), (x2+r, y2+r), col, thickness)
            cv2.line(vis, (x2-r, y2+r), (x2+r, y2-r), col, thickness)
    vis0 = vis.copy()
    for (x1, y1), (x2, y2), inlier in zip(p1, p2, status):
        if inlier:
            cv2.line(vis, (x1, y1), (x2, y2), green)

    cv2.imshow(win, vis)

import time
start = time.time()
img1 = cv2.imread("../image/timg.png")
img2 = cv2.imread("../image/timg.jpg")

img1_gray = cv2.cvtColor(img1, cv2.COLOR_BGR2GRAY)
img2_gray = cv2.cvtColor(img2, cv2.COLOR_BGR2GRAY)
# img2_gray=rotate_about_center(img2_gray, 90)
#img2_gray = cv2.resize(img2_gray, (img1_gray.shape[1], img1_gray.shape[0]))

start = time.time()
sift = surf = cv2.xfeatures2d.SURF_create()

kp1,des1 = sift.detectAndCompute(img1_gray, None)
kp2,des2 = sift.detectAndCompute(img2_gray, None)

end = time.time()
print "Extract feature time:" + str(end-start)

start = time.time()
# BFmatcher with default parms
bf = cv2.BFMatcher(cv2.NORM_L2)
matches = bf.knnMatch(des1, des2, k=2)
p1,p2,kp_pairs = filter_matches(kp1,kp2,matches,ratio=0.8)
end = time.time()
print "KNN match time:" + str(end-start)

if len(p1) >= 4:
    H , status = cv2.findHomography(p1 , p2 , cv2.RANSAC , 5.0)
    print H
    print '%d / %d  inliers/matched' % (np.sum(status) , len(status))
    # do not draw outliers (there will be a lot of them)
    kp_pairs = [kpp for kpp , flag in zip(kp_pairs , status) if flag]
else:
    H , status = None , None
    print '%d matches found, not enough for homography estimation' % len(p1)
explore_match('matches', img1_gray,img2_gray,kp_pairs, H=H)
# img3 = cv2.drawMatchesKnn(img1_gray,kp1,img2_gray,kp2,good[:10],flag=2)
end = time.time()
print "time"+str(end-start)
cv2.waitKey(0)
cv2.destroyAllWindows()

运行的具体信息如下：
操作系统：ubuntu 14.04
运行环境：
opencv版本：opencv 3.0
模板大小：126x96 png
匹配图像大小：750x407 jpg
特征提取时间：0.15 s
KNN匹配时间：0.0024s
匹配效果：

匹配结果图，左侧为模板，右侧为待匹配图， 红色部分为匹配结果

opencv reg