模式匹配

模式匹配，

• 即寻找待匹配图像和全体图像中最相似的部分，用于物体检测任务。将图像A在图像B中匹配的图像框起来
• 算法基本原理

1. 原图像记为I(H×W)，待匹配图像为T(h×w)：
2. 对于图像I：，for ( j = 0, H-h) for ( i = 0, W-w)在一次移动1像素的过程中，原图像I的一部分I(i:i+w,j:j+h)与待匹配图像计算相似度S。
3. S最大或最小的地方即为匹配的位置。
4. S的计算方法主要有 SSD(误差平方和算法)、SAD（绝对值差和算法）、NCC（归一化交叉相关算法）、ZNCC（零均值归一化交叉相关）等。对于不同的方法，我们需要选择出最大值或者最小值。

使用误差平方和算法（Sum of Squared Difference）进行模式匹配

• 使用误差平方和SSD（Sum of Squared Difference）。SSD计算像素值的差的平方和，S取误差平方和最小的地方。
  

img = cv2.imread("imori.jpg").astype(np.float32)#读取原始图像
H, W, C = img.shape#读取图像尺寸
# Read templete image
temp = cv2.imread("imori_part.jpg").astype(np.float32)#读取需要匹配的图像
Ht, Wt, Ct = temp.shape#读取需要匹配图像的尺寸
# Templete matching
i, j = -1, -1#给一个匹配坐标的初始值
v = 255 * H * W * C#给一个误差平方和的初始值
for y in range(H-Ht):#匹配y方向上终点y坐标
    for x in range(W-Wt):#匹配x方向上终点x坐标
        _v = np.sum((img[y:y+Ht, x:x+Wt] - temp) ** 2)#依次计算误差平方和的值
        if _v < v:#如果误差平方和有所减小，就更新v
            v = _v
            i, j = x, y#同时更新匹配上的坐标点
out = img.copy()
cv2.rectangle(out, pt1=(i, j), pt2=(i+Wt, j+Ht), color=(0,0,255), thickness=1)#最终画框
out = out.astype(np.uint8)
cv2.imshow('out.jpg',out)

• 可以预见的是，尺度变化和旋转变化对匹配的结果影响非常大

使用绝对值差和（Sum of Absolute Differences）进行模式匹配

img = cv2.imread("imori.jpg").astype(np.float32)
H, W, C = img.shape
# Read templete image
temp = cv2.imread("imori_part.jpg").astype(np.float32)
Ht, Wt, Ct = temp.shape
# Templete matching
i, j = -1, -1
v = 255 * H * W * C
for y in range(H-Ht):
    for x in range(W-Wt):
        _v = np.sum(np.abs(img[y:y+Ht, x:x+Wt] - temp))
        if _v < v:
            v = _v
            i, j = x, y
out = img.copy()
cv2.rectangle(out, pt1=(i, j), pt2=(i+Wt, j+Ht), color=(0,0,255), thickness=1)
out = out.astype(np.uint8)
cv2.imshow('out.jpg',out)

• 与上面的误差平方和算法非常相似，只是将误差平方和换成了绝对值平方和

使用归一化交叉相关（Normalization Cross Correlation）进行模式匹配

• 
• S 最后的范围在−1≤S<=1。NCC对变化十分敏感

img = cv2.imread("123.jpg").astype(np.float32)
H, W, C = img.shape

# Read templete image
temp = cv2.imread("4.jpg").astype(np.float32)
Ht, Wt, Ct = temp.shape
# Templete matching
i, j = -1, -1
v = -1
for y in range(H - Ht):
    for x in range(W - Wt):
        _v = np.sum(img[y:y + Ht, x:x + Wt] * temp)
        _v /= (np.sqrt(np.sum(img[y:y + Ht, x:x + Wt] ** 2)) * np.sqrt(np.sum(temp ** 2)))
        if _v > v:
            v = _v
            i, j = x, y
out = img.copy()
cv2.rectangle(out, pt1=(i, j), pt2=(i + Wt, j + Ht), color=(0, 0, 255), thickness=1)
out = out.astype(np.uint8)

使用零均值归一化交叉相关（Zero-mean Normalization Cross Correlation）进行模式匹配

• 零均值归一化交叉相关（Zero-mean Normalization Cross Correlation）求出两个图像的相似度，匹配S最大处的图像。
• 图像I的平均值记为mi，图像T的平均值记为mt。使用下式计算S：
• 
• S最后的范围在−1≤S≤1。零均值归一化积相关去掉平均值的话就是归一化交叉相关，据说这比归一化交叉相关对变换更加敏感。

img = cv2.imread("123.jpg").astype(np.float32)
H, W, C = img.shape
mi = np.mean(img)
# Read templete image
temp = cv2.imread("4.jpg").astype(np.float32)
Ht, Wt, Ct = temp.shape
mt = np.mean(temp)
# Templete matching
i, j = -1, -1
v = -1
for y in range(H - Ht):
    for x in range(W - Wt):
        _v = np.sum((img[y:y + Ht, x:x + Wt] - mi) * (temp - mt))
        _v /= (np.sqrt(np.sum((img[y:y + Ht, x:x + Wt] - mi) ** 2)) * np.sqrt(np.sum((temp - mt) ** 2)))
        if _v > v:
            v = _v
            i, j = x, y
out = img.copy()
cv2.rectangle(out, pt1=(i, j), pt2=(i + Wt, j + Ht), color=(0, 0, 255), thickness=1)
out = out.astype(np.uint8)

无一例外，上述四种模式匹配方法对不同尺度不同角度匹配性极差