在2D的机器视觉应用中，模板匹配比较常见，

常见的匹配算法有基于灰度的匹配，基于边缘的匹配，基于形状的匹配等。推荐《机器视觉算法与应用》这本书，这本书是halcon开发人员撰写，对于模板匹配介绍的比较详细。下面介绍基于形状的模板匹配。

在pcl和opencv中都有关于linemod的实现。本算法是基于linemod的2D版本，主要从opencv的源码修改。

1 算法的基本流程如下：

(1). 计算方向梯度，并进行方向扩展

以彩色梯度为例，Opencv源码先进行了7*7的高斯模糊，然后利用Sobel算子计算了梯度，继而在每个像素点求解出了梯度方向以及幅值，只有超过一定阈值的梯度才会被保留；接着在3*3的领域内统计梯度的方向，数量超过5的梯度方向才会被采用。值得注意的是，这里的方向都是无符号的，也就是只取上一半，Opencv实现的代码里分为了8个方向。如图所示，这种提取特征的方式对于梯度起到了主成分提取和放大的效果。

为了使得匹配有一定的容错度，对图像（非模板）提取完方向后得到了特征图，在一定领域里让这个特征进行扩散，继而利用模板进行滑窗匹配时就有了一定的容错度。下图展示了扩散的过程以及对方向离散化的过程，扩散的范围是T=3个像素，方向的个数n=5。

（图像提取完）

（扩展后）

(2). 预处理响应图

针对8个方向和1里得到的扩散图逐个像素进行匹配，匹配的结果是距离最近方向角度的余弦值。值得注意的是，虽然这里有八个方向，但是夹角只有五种情况（算的直线夹角而非射线），故而匹配的结果只有五种，OpenCV里用0,1,2,3,4表示。

这里有8个方向，故而就有8张预处理的图，在利用模板进行匹配的时候就可以直接调用对应方向在对应像素的结果，避免了滑窗时重复的计算。

这样就用了一点内存空间换取处理上的速度。

(3). 线性存储

在进行滑窗匹配计算匹配度时调用响应图中的数据都是有规律的，每隔滑窗的步长T采取一次数据，故而文章提出直接将响应图中的数据拉成N*N个“长条”，这样就可以将多个数据融合在一起进行加的操作从而减少算法的运行时间。

上文也提及到了匹配的结果只有0-4四种结果，一个char的长度是8位，最多能融合63个特征相加而不溢出，故而OpenCV实现的代码里最多只支持63个特征（这一点在修改的源码中已经改进）。

这一步是整个算法的关键，也是提高速度的关键。以下图为例进行详细说明：

将响应图按照步长T, 分为T*T个线性存储。这样对于一个模板在滑窗比对的时候，模板中的同一个像素在不同位置所对应的比对值，都在同一个线性存储里。模板中的所有像素都对应一个匹配结果的线性存储，如下图2中右边。这样就可以用SSE进行整体相加计算。而不必在每一个模板滑窗地方单独相加计算。

                                                    （1）

                                                     （2）

上面遍历过程的示例代码：

2 总结

（1）模板问题。算法因为只对模板进行滑窗计算，针对模板的旋转和缩放问题，需要首先将模板根据角度精度和缩放因子进行旋转和缩放生成不同的模板，对所有模板进行梯度计算以及离散化处理。由于此算法的特点，此算法对上千张模板进行匹配对速度影响不大。

（2）此算法结合的是边缘的梯度大小和方向，速度上用了金字塔，sse以及openMP进行加速。所以在效果上，稳定性和速度都很好，比一些商业软件的匹配工具差不了太多。下图是一些检测实例，速度方面，500万像素找出目标，大约200ms左右。