.. _template_matching:

模板匹配
*****************

目标
====

在这节教程中您将学到:

.. container:: enumeratevisibleitemswithsquare

   * 使用OpenCV函数 :match_template:`matchTemplate <>` 在模板块和输入图像之间寻找匹配,获得匹配结果图像
   * 使用OpenCV函数 :min_max_loc:`minMaxLoc <>` 在给定的矩阵中寻找最大和最小值(包括它们的位置).

原理
======

什么是模板匹配?
--------------------------

.. container:: enumeratevisibleitemswithsquare

   模板匹配是一项在一幅图像中寻找与另一幅模板图像最匹配(相似)部分的技术.


它是怎么实现的?
------------------

.. container:: enumeratevisibleitemswithsquare

   * 我们需要2幅图像:

     a. **原图像 (I):** 在这幅图像里,我们希望找到一块和模板匹配的区域 
     b. **模板 (T):** 将和原图像比照的图像块 

     我们的目标是检测最匹配的区域:

     .. image:: images/Template_Matching_Template_Theory_Summary.jpg
              :align: center      

   * 为了确定匹配区域, 我们不得不滑动模板图像和原图像进行 *比较*  :

     .. image:: images/Template_Matching_Template_Theory_Sliding.jpg
              :align: center      

   *  通过 **滑动**, 我们的意思是图像块一次移动一个像素 (从左往右,从上往下). 在每一个位置, 都进行一次度量计算来表明它是 "好" 或 "坏" 地与那个位置匹配 (或者说块图像和原图像的特定区域有多么相似).

   *  对于 **T** 覆盖在 **I** 上的每个位置,你把度量值 *保存* 到 *结果图像矩阵* **(R)** 中. 在 **R** 中的每个位置 :math:`(x,y)` 都包含匹配度量值:

      .. image:: images/Template_Matching_Template_Theory_Result.jpg
               :align: center      

      上图就是 **TM_CCORR_NORMED** 方法处理后的结果图像 **R** . 最白的位置代表最高的匹配. 正如您所见, 红色椭圆框住的位置很可能是结果图像矩阵中的最大数值, 所以这个区域 (以这个点为顶点,长宽和模板图像一样大小的矩阵) 被认为是匹配的. 

   * 实际上, 我们使用函数 :min_max_loc:`minMaxLoc <>` 来定位在矩阵 *R* 中的最大值点 (或者最小值, 根据函数输入的匹配参数) .
   
OpenCV中支持哪些匹配算法?
----------------------------------------------------

问得好. OpenCV通过函数 :match_template:`matchTemplate <>` 实现了模板匹配算法. 可用的方法有6个:

a. **平方差匹配 method=CV\_TM\_SQDIFF**

这类方法利用平方差来进行匹配,最好匹配为0.匹配越差,匹配值越大.    
    
   .. math::
    
      R(x,y)= \sum _{x',y'} (T(x',y')-I(x+x',y+y'))^2  
    
    
b. **标准平方差匹配 method=CV\_TM\_SQDIFF\_NORMED**
		
   .. math::
    
      R(x,y)= \frac{\sum_{x',y'} (T(x',y')-I(x+x',y+y'))^2}{\sqrt{\sum_{x',y'}T(x',y')^2 \cdot \sum_{x',y'} I(x+x',y+y')^2}} 
       

c. **相关匹配 method=CV\_TM\_CCORR**

这类方法采用模板和图像间的乘法操作,所以较大的数表示匹配程度较高,0标识最坏的匹配效果.
    
   .. math::
    
      R(x,y)= \sum _{x',y'} (T(x',y')  \cdot I(x+x',y+y'))  
      

d. **标准相关匹配 method=CV\_TM\_CCORR\_NORMED**    
    
   .. math::
    
      R(x,y)= \frac{\sum_{x',y'} (T(x',y') \cdot I'(x+x',y+y'))}{\sqrt{\sum_{x',y'}T(x',y')^2 \cdot \sum_{x',y'} I(x+x',y+y')^2}} 
    

e. **相关匹配 method=CV\_TM\_CCOEFF**

这类方法将模版对其均值的相对值与图像对其均值的相关值进行匹配,1表示完美匹配,-1表示糟糕的匹配,0表示没有任何相关性(随机序列).
    
   .. math::
    
      R(x,y)= \sum _{x',y'} (T'(x',y')  \cdot I(x+x',y+y'))  
   
   在这里
     
   .. math::
    
      \begin{array}{l} T'(x',y')=T(x',y') - 1/(w  \cdot h)  \cdot \sum _{x'',y''} T(x'',y'') \\ I'(x+x',y+y')=I(x+x',y+y') - 1/(w  \cdot h)  \cdot \sum _{x'',y''} I(x+x'',y+y'') \end{array} 
    
    
f. **标准相关匹配 method=CV\_TM\_CCOEFF\_NORMED**
    
   .. math::
    
      R(x,y)= \frac{ \sum_{x',y'} (T'(x',y') \cdot I'(x+x',y+y')) }{ \sqrt{\sum_{x',y'}T'(x',y')^2 \cdot \sum_{x',y'} I'(x+x',y+y')^2} } 

通常,随着从简单的测量(平方差)到更复杂的测量(相关系数),我们可获得越来越准确的匹配(同时也意味着越来越大的计算代价). 最好的办法是对所有这些设置多做一些测试实验,以便为自己的应用选择同时兼顾速度和精度的最佳方案.	  
	  

代码
====


.. container:: enumeratevisibleitemswithsquare

   * **在这程序实现了什么?**
 
     .. container:: enumeratevisibleitemswithsquare

        * 载入一幅输入图像和一幅模板图像块 (*template*)
        * 通过使用函数 :match_template:`matchTemplate <>` 实现之前所述的6种匹配方法的任一个. 用户可以通过滑动条选取任何一种方法.
        * 归一化匹配后的输出结果
        * 定位最匹配的区域
        * 用矩形标注最匹配的区域

   * **下载代码**:
     单击 `这里 <https://code.ros.org/svn/opencv/trunk/opencv/samples/cpp/tutorial_code/Histograms_Matching/MatchTemplate_Demo.cpp>`_

   * **看一下代码:**

.. code-block:: cpp

   #include "opencv2/highgui/highgui.hpp" 
   #include "opencv2/imgproc/imgproc.hpp"
   #include <iostream>
   #include <stdio.h>

   using namespace std;
   using namespace cv;

   /// 全局变量
   Mat img; Mat templ; Mat result;
   char* image_window = "Source Image";
   char* result_window = "Result window";

   int match_method;
   int max_Trackbar = 5;

   /// 函数声明
   void MatchingMethod( int, void* );

   /** @主函数 */
   int main( int argc, char** argv )
   {
     /// 载入原图像和模板块
     img = imread( argv[1], 1 );
     templ = imread( argv[2], 1 );

     /// 创建窗口
     namedWindow( image_window, CV_WINDOW_AUTOSIZE );
     namedWindow( result_window, CV_WINDOW_AUTOSIZE );
  
     /// 创建滑动条
     char* trackbar_label = "Method: \n 0: SQDIFF \n 1: SQDIFF NORMED \n 2: TM CCORR \n 3: TM CCORR NORMED \n 4: TM COEFF \n 5: TM COEFF NORMED";
     createTrackbar( trackbar_label, image_window, &match_method, max_Trackbar, MatchingMethod );

     MatchingMethod( 0, 0 );

     waitKey(0);
     return 0;
   }

   /**
    * @函数 MatchingMethod
    * @简单的滑动条回调函数
    */
   void MatchingMethod( int, void* )
   {
     /// 将被显示的原图像
     Mat img_display;
     img.copyTo( img_display );
 
     /// 创建输出结果的矩阵
     int result_cols =  img.cols - templ.cols + 1;
     int result_rows = img.rows - templ.rows + 1;   
  
     result.create( result_cols, result_rows, CV_32FC1 );

     /// 进行匹配和标准化
     matchTemplate( img, templ, result, match_method );
     normalize( result, result, 0, 1, NORM_MINMAX, -1, Mat() );

     /// 通过函数 minMaxLoc 定位最匹配的位置
     double minVal; double maxVal; Point minLoc; Point maxLoc;
     Point matchLoc;
 
     minMaxLoc( result, &minVal, &maxVal, &minLoc, &maxLoc, Mat() );

     /// 对于方法 SQDIFF 和 SQDIFF_NORMED, 越小的数值代表更高的匹配结果. 而对于其他方法, 数值越大匹配越好
     if( match_method  == CV_TM_SQDIFF || match_method == CV_TM_SQDIFF_NORMED )
       { matchLoc = minLoc; }
     else  
       { matchLoc = maxLoc; }

     /// 让我看看您的最终结果
     rectangle( img_display, matchLoc, Point( matchLoc.x + templ.cols , matchLoc.y + templ.rows ), Scalar::all(0), 2, 8, 0 ); 
     rectangle( result, matchLoc, Point( matchLoc.x + templ.cols , matchLoc.y + templ.rows ), Scalar::all(0), 2, 8, 0 ); 

     imshow( image_window, img_display );
     imshow( result_window, result );

     return;
   }

代码说明
===========

#. 定义一些全局变量, 例如原图像(img), 模板图像(templ) 和结果图像(result) , 还有匹配方法以及窗口名称:

   .. code-block:: cpp

      Mat img; Mat templ; Mat result;
      char* image_window = "Source Image";
      char* result_window = "Result window";

      int match_method;
      int max_Trackbar = 5;


#. 载入原图像和匹配块:

   .. code-block:: cpp

      img = imread( argv[1], 1 );
      templ = imread( argv[2], 1 );

#. 创建窗口,显示原图像和结果图像:

   .. code-block:: cpp

      namedWindow( image_window, CV_WINDOW_AUTOSIZE );
      namedWindow( result_window, CV_WINDOW_AUTOSIZE );
  
#. 创建滑动条并输入将被使用的匹配方法. 一旦滑动条发生改变,回调函数 **MatchingMethod** 就会被调用.

   .. code-block:: cpp

      char* trackbar_label = "Method: \n 0: SQDIFF \n 1: SQDIFF NORMED \n 2: TM CCORR \n 3: TM CCORR NORMED \n 4: TM COEFF \n 5: TM COEFF NORMED";
      createTrackbar( trackbar_label, image_window, &match_method, max_Trackbar, MatchingMethod );

#. 一直等待,直到用户退出这个程序.

   .. code-block:: cpp

      waitKey(0);
      return 0;
  
#. 让我们先看看回调函数. 首先, 它对原图像进行了一份复制:

   .. code-block:: cpp

     Mat img_display;
     img.copyTo( img_display );


#. 然后, 它创建了一幅用来存放匹配结果的输出图像矩阵. 仔细看看输出矩阵的大小(它包含了所有可能的匹配位置)

   .. code-block:: cpp
 
      int result_cols =  img.cols - templ.cols + 1;
      int result_rows = img.rows - templ.rows + 1;   
  
      result.create( result_cols, result_rows, CV_32FC1 );
 
#. 执行模板匹配操作:

   .. code-block:: cpp

     matchTemplate( img, templ, result, match_method );

   很自然地,参数是输入图像 **I**, 模板图像 **T**, 结果图像 **R** 还有匹配方法 (通过滑动条给出)

#. 我们对结果进行归一化:

   .. code-block:: cpp

      normalize( result, result, 0, 1, NORM_MINMAX, -1, Mat() );

#. 通过使用函数 :min_max_loc:`minMaxLoc <>` ,我们确定结果矩阵 **R** 的最大值和最小值的位置. 

   .. code-block:: cpp

      double minVal; double maxVal; Point minLoc; Point maxLoc;
      Point matchLoc;
 
      minMaxLoc( result, &minVal, &maxVal, &minLoc, &maxLoc, Mat() );
   
   函数中的参数有:

   .. container:: enumeratevisibleitemswithsquare   

      + **result:** 匹配结果矩阵
      + **&minVal** 和 **&maxVal:** 在矩阵 **result** 中存储的最小值和最大值
      + **&minLoc** 和 **&maxLoc:** 在结果矩阵中最小值和最大值的坐标.
      + **Mat():** 可选的掩模


#. 对于前二种方法 ( CV\_SQDIFF 和 CV\_SQDIFF\_NORMED ) 最低的数值标识最好的匹配. 对于其他的, 越大的数值代表越好的匹配. 所以, 我们在 **matchLoc** 中存放相符的变量值:

   .. code-block:: cpp
     
     if( match_method  == CV_TM_SQDIFF || match_method == CV_TM_SQDIFF_NORMED )
       { matchLoc = minLoc; }
     else  
       { matchLoc = maxLoc; }

#. 显示原图像和结果图像. 再用矩形框标注最符合的区域:

   .. code-block:: cpp

      rectangle( img_display, matchLoc, Point( matchLoc.x + templ.cols , matchLoc.y + templ.rows ), Scalar::all(0), 2, 8, 0 ); 
      rectangle( result, matchLoc, Point( matchLoc.x + templ.cols , matchLoc.y + templ.rows ), Scalar::all(0), 2, 8, 0 ); 

      imshow( image_window, img_display );
      imshow( result_window, result );


结果
=======

#. 开始测试我们的程序,一幅输入图像:

   .. image:: images/Template_Matching_Original_Image.jpg
            :align: center
 
   还有一幅模版图像:

   .. image:: images/Template_Matching_Template_Image.jpg
            :align: center  

#. 产生了一下结果图像矩阵 (第一行是标准的方法 SQDIFF, CCORR 和 CCOEFF, 第二行是相同的方法在进行标准化后的图像). 在第1列, 最黑的部分代表最好的匹配, 对于其它2列, 越白的区域代表越好的匹配.

   ============  ============  ============ 
    |Result_0|    |Result_2|    |Result_4|
   ============  ============  ============ 
    |Result_1|    |Result_3|    |Result_5|
   ============  ============  ============ 

   .. |Result_0| image:: images/Template_Matching_Correl_Result_0.jpg
                      :align: middle

   .. |Result_1| image:: images/Template_Matching_Correl_Result_1.jpg
                      :align: middle

   .. |Result_2| image:: images/Template_Matching_Correl_Result_2.jpg
                      :align: middle

   .. |Result_3| image:: images/Template_Matching_Correl_Result_3.jpg
                      :align: middle

   .. |Result_4| image:: images/Template_Matching_Correl_Result_4.jpg
                      :align: middle

   .. |Result_5| image:: images/Template_Matching_Correl_Result_5.jpg
                      :align: middle

#. 正确的匹配在下面显示 (右侧被矩形标注的人脸). 需要注意的是方法 CCORR 和 CCOEFF 给出了错误的匹配结果, 但是它们的归一化版本给出了正确的结果, 这或许是由于我们实际上仅仅考虑 "最匹配" 而没考虑其他可能的高匹配位置.

   .. image:: images/Template_Matching_Image_Result.jpg
            :align: center

翻译者
=================
guoming0000@ `OpenCV中文网站 <http://www.opencv.org.cn>`_ <guoming0000@sina.com>