【计算机视觉（五）】模板匹配
前请提要
前三期（【计算机视觉（二）】常用颜色空间及其转换）、【计算机视觉（三）】形态学处理、【计算机视觉（四）】轮廓检测）在介绍基本知识的同时穿插了一个很naive的检测车牌位置的方法，对参数设置有很强的依赖。后续会慢慢涉及到高级的方法。
本期内容
本期作为一个引子介绍模板匹配法，引出后来的Cascade检测算法。
一、全等模板
car_test.jpg
假如我们要在上面这张固定的图上找出左边这辆车的位置，一个很简单的方法就是我们可以先人工把左边这辆车用“截图”工具裁剪出来。
template.jpg
然后拿着这张图在大图上找，一开始，我们把模板图放到大图的左上角，看它们是不是所有像素值都相等，然后往右移一个像素，再看是不是所有值相等，如此遍历整幅图，直到找到全等的位置。
sw1.jpg
sw2.jpg
这样的搜寻策略叫做滑动窗口。
template_match_result.jpg
实现代码如下：
# coding: utf-8
import cv2
import numpy as np
'''
函数名：template_match
输入：
template 模板
img 原图
输出：
(x,y) 匹配位置的左上角坐标，找不到返回None
'''
def template_match(template, img):
tpl_h, tpl_w = template.shape[:2]
img_h, img_w = img.shape[:2]
for i in xrange(img_h - tpl_h):
for j in xrange(img_w - tpl_w):
roi = img[i:i+tpl_h, j:j+tpl_w]
if (template == roi).all():
return (j,i)
return None
# 程序入口
def main():
# 整图
cars = cv2.imread('car_test.jpg')
# 车模板
car_tpl = cars[117:199, 24:246].copy()
pos = template_match(car_tpl, cars)
tpl_h, tpl_w = car_tpl.shape[:2]
if pos is not None:
x,y = pos
cv2.rectangle(cars, (x,y), (x+tpl_w,y+tpl_h), (0,255,0), 2)
cv2.imshow('template', car_tpl)
cv2.imshow('result', cars)
cv2.imwrite('template_match_result.jpg', cars)
cv2.waitKey(0)
if __name__ == '__main__':
main()
这样做的缺点很明显，只要有一个像素点跟模板不相等就找不到了，如果只是要找些非常固定的东西那用这种方法是可以的，比如以前做游戏脚本的时候要实现鼠标点到某个固定的技能或道具上。
二、相关系数
这时候要用更靠谱的测度——例如相关系数（除此之外还有平方差等）。
图像的相关系数的计算方法参考这个公式，是从Matlab的文档截下来的。
相关系数公式
分子是图像与模板的协方差，分母是它们的标准差的乘积。
具体原理参考知乎的这个回答。
它会返回一个数值表示图像的相关程度，越相关，值越靠近1，实现代码如下：
# 输入灰度图
def norm_corr(template, img):
tpl_h, tpl_w = template.shape[:2]
img_h, img_w = img.shape[:2]
expand_img = np.zeros((tpl_h+img_h, tpl_w+img_w), dtype=np.uint8)
expand_img[:img_h, :img_w] = img
img_h, img_w = expand_img.shape[:2]
# 图像均值
tpl_mean = np.mean(template)
# 减均值
tpl_sub_mean = template - tpl_mean
# 标准差
sigma_tpl = np.sum(tpl_sub_mean**2)
# 相关系数图
corr = np.zeros(img.shape, dtype=np.float32)
for i in xrange(img_h - tpl_h):
for j in xrange(img_w - tpl_w):
roi = expand_img[i:i+tpl_h, j:j+tpl_w]
# 图像均值
roi_mean = np.mean(roi)
# 减均值
roi_sub_mean = roi - roi_mean
# 标准差
sigma_roi = np.sum(roi_sub_mean**2)
# 协方差
cov = np.sum(tpl_sub_mean * roi_sub_mean)
# 相关系数
corr[i,j] = cov / np.sqrt(sigma_tpl * sigma_roi)
# 归一化到0-255
corr_max = corr.max()
corr_min = corr.min()
print 'max = ', corr_max
print 'min = ', corr_min
if corr_max != corr_min:
corr = 255 * (corr - corr_min) / (corr_max - corr_min)
return corr.astype(np.uint8)
要注意输入是灰度图，最后输出是一张表示每一个位置上的相关系数的图，归一化到0-255就可以显示出来了。再次使用上面的模板图和大图，得到的相关系数图如下：
相关系数图
图中越亮的地方表示把模板的左上角在大图的对应位置的可能性越大。
我们可以把相关图上值超过127（最大255，可以自行设置这个阈值）的地方用矩形框标出来。
代码如下：
idx = np.where(corr > 0.5 * 255)
rows = idx[0]
cols = idx[1]
rects = []
for r,c in zip(rows, cols):
if c+tpl_w < img_w and r+tpl_h < img_h:
rects.append((c,r,c+tpl_w,r+tpl_h))
for rect in rects:
tx,ty,bx,by = rect
cv2.rectangle(cars, (tx,ty), (bx,by), (0,255,0), 2)
效果如下：
所有框
可以看到虽然用的模板是左边的车，但由于两台车很相似，所以右边的车也被检出来了，但是框非常的多，我们可以想办法做去重，把顶点靠近的矩形框当作一个子集，最后分别给出各个矩形集的平均位置，代码如下，可以根据需要子集改进：
def group_rects(rects, diff=20):
groups = [[rects[0]]]
for rect in rects[1:]:
tx,ty,bx,by = rect
found = False
for gr in groups:
for gre in gr:
if abs(gre[0]-tx) < diff and abs(gre[1]-ty) < diff and abs(gre[2]-bx) < diff and abs(gre[3]-by) < diff:
gr.append(rect)
found = True
break
if found:
break
if not found:
groups.append([rect])
result = []
for group in groups:
result.append(np.array(group).mean(axis=0).astype(np.int32).tolist())
return result
这样就得到了很好的两个框。
框融合结果
总结
即使改变了使用的距离函数，我们也只使用了一个数据（图像）就希望能检测到其他的同类物体，的确是很以偏概全的想法。以检测车子的例子来说，我们是把一台特定的车当作模板，而没有从更接近本质的角度去解构这个问题，假设我们能人为的定义车子该长什么样也许就能很好的解决这个问题，比如说车有轮子、车窗、车灯、整体是流线型的，等等。这些性质可以称为车子的特征（feature）。计算机视觉有很大部分研究的问题都在围绕着如何更好的描述物体，也就是如何得到物体更好的特征。特征可能是级联的，意思是说有轮子是车子的特征，轮子也有自己的特征（圆的，黑的），特征总是从低层的只包含结构、形状等信息往高层的更不可描述的信息走。发展到现在，特征可以分为人为设计和通过机器学习的方法学习出来两种，人为设计的特征如HOG、Haar等，有着固定的计算过程，可以手工计算出来，在深度学习大热的当今已经慢慢被新晋行业的人视为“传统的技术”，但在我看来这两者并没有那么大的不同，没有必要放弃这些“old-school”的技术，这样只会造成“拿起锤子，看什么都是钉子”的想法。
