OPENCV自学（二）——模板匹配

以下图为例简单说明一下，左边淡蓝色区域表示待搜索的图像，右上角的三角形表示目标，意思就是要在左边的图中找出右边的正三角形在左边图中位置。

    一般的算法思想：将搜索模板 T( m×n 个像素)叠放在被搜索图S( W×H 个像素)上平移，模板覆盖被搜索图的那块区域叫子图Sij。i，j为子图左上角在被搜索图S 上的坐标。搜索范围是： 
       1≤ i ≤ W–m 
       1≤ j ≤ H–n 
    通过比较T 和Sij 的相似性，完成模板匹配过程。 衡量模板T和子图Si,j的匹配程度,可用下列两种测度:

 或者 

    将上面第一个式子展开得到下面的：

    从展开的公式中可以看出，中间第二项是一个常数，也就是只跟模板有关系，而第一个和第三个是和原图有关的，随着模板在原图上的移动，这两个值也在发生变化。当D(i,j)的值最小时，说明找到了目标，通过这个关系，可以将展开的公式变形得到其他的公式，但是原理都是根据这个来的。在此不再一一列举。

    这个算法的效率是非常的地下的，每移动一个像元就要进行一次计算，计算量是相当的大，曾经试验过一个1000*1000的图，模板大小100*100，大概需要十分钟左右（机器性能也一般，但是这种真的是太慢了）。于是就有人提出下面的优化算法。主要有：

1 粗精匹配结合 
观察实际模板匹配运算结果可以发现,匹配点附近的匹配误差迅速下降,明显区别于其它位置。针对这一特点,采用粗精匹配结合的算法迅速锁定匹配点大致区域,可大大降低整体匹配次数。具体实现方法:先跳动着隔几个点进行一次粗匹配,大致框定匹配区域,然后在附近区域逐一检索获得最佳匹配点。运算量可减少到三分之一以下，且目标提取效果相当好。

2 限制最大匹配误差 
因为只需找到最小匹配误差的位置,不必完整计算每一位置的绝对匹配误差,而以已经计算的最小匹配误差作为最大允许误差。若计算误差大于该最大允许误差,就肯定不是最佳匹配点,可以提前结束计算,进入下一匹配位置的计算;如果匹配完成后仍小于最大允许误差,就用当前误差替换最大允许误差,并把该点作为潜在的匹配位置记录下来。匹配点和非匹配点的误差常常相差2~3个数量级。经过这种处理后,匹配点后剩余的计算量可以大大降低。

3 乱序匹配 
目标出现在匹配区域中的位置不确定。不固定顺序算法可以更快地检索到匹配区域,迅速降低最大匹配误差,减少剩余非匹配点的计算量,降低整体运算量。针对光电探测设备的实际工作情况,在跟踪状态下,目标位移角速度和角加速度有限,导致目标常处于匹配区域中心附近。选择由中心向周围辐射匹配的方式效果最理想。

CV_EXPORTS_W void cv::matchTemplate (const Mat & image,  
                                     const Mat & templ,  
                                     /*CV_OUT*/ Mat & result,  
                                     int  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 归一化相关系数匹配法

   关于OpenCV的匹配效果如下图所示：

（图片来源：http://www.cnblogs.com/xrwang/archive/2010/02/05/MatchTemplate.html ）

关于如何使用OpenCV的模板匹配可以参考网址http://www.cnblogs.com/xrwang/archive/2010/02/05/MatchTemplate.html 。OpenCV的目标匹配表面上使用的是前面分析的方式，其实实质上在内部做了很多的处理，比如建立金字塔从顶层粗略计算大概范围，然后再详细计算，以及使用傅里叶变换来进行比较等等（如果不进行这些处理，计算速度超级慢）。