2.2.4 模板匹配

模板匹配（Template Matching）是图像识别中最具代表性的方法之一，其具有算法实现容易，匹配速度快的特点。

1.模板匹配概念

模板匹配是将从待识别的图像提取的若干特征量与模板对应的特征量进行比较，计算图像和模板特征量之间的距离，用最小距离法判定所属类。用模板匹配法进行模式识别时通常需要先建立标准模板库。Hausdorff距离（HD）又称最大最小距离，是描述两组点集之间相似程度的一种量度，它是集合与集合之间距离的一种定义形式。假设有两组集合A={a1,a2,…,aN }A，B={b1,b2,…,bN }B，则这两组集合之间的Hausdorff距离可以定义为

2.Hausdorff距离

式中，称为A集合和B集合之间的直接Hausdorff距离，‖.‖是某种距离范数。如果定义一个点a到一个点集B的距离d(a,B)为该点到该点集中每一个点的距离的最小值，即

则dh(A,B)是点集A中每个点到点集B中的最小距离集合d(a,B)中的最大值。Hausdorff距离dH取dH(A,B)和dH(B,A)的最大值。从而可获得两个点集A和B之间的匹配程度。

3.改进的Hausdorff距离

为了抵抗噪声的干扰，对Hausdorff距离进行改进，把距离公式由

变为

即把求最大最小距离变为求最小距离的累加和，这样做可以有效地抵抗随机噪声的干扰，从整体上计算两个点集之间的距离，而不是只靠最大距离，从而增加了两个点集之间距离的稳定性，从理论上更加合理。

4.基于改进的Hausdorff距离的模板匹配算法

基于改进的Hausdorff距离的模板匹配算法如下。

先生成各个模板的模板库，然后逐个计算待识别的样本图像与各个样本的模板库之间的改进的Hausdorff距离Di(i=1,2,…,N)，N为模板个数。步骤如下：

（a）初始化D(X,Ti)，令D(X,Ti)=0。

（b）从上到下，从左至右，逐个像素扫描待识别样本图像，如果是1（黑色像素），记录下该点Px,y的位置；否则继续扫描。

（c）模板图像上，在以Px,y点为中心的k × k邻域内，搜索1（黑色像素），寻找与Px,y最近的点，并且计算Px,y和该点之间的距离，此距离是待识别图像和模板图像在该点的最小距离。如果k×k邻域内没有找到1，就认为距离为较大者。

（d）把所有计算的距离进行累加到待识别样本到模板的距离D(X,Ti)中。

（e）判断是否扫描待识别图像结束，如没有结束，转到步骤b，否则继续计算，直至得到待识别样本到模板的距离D(X,Ti)。

（f）按照同样的步骤可计算模板到待识别样本的改进的Hausdorff距离D(Ti,X)。

（g）取Di =Max(D(X,Ti),D(Ti,X))。

当Di最小时，对应的模板就是识别的结果。

5.模板匹配的C语言实现

下面给出基本的模板匹配算法的C语言实现，如代码2-8所示。

代码2-8模板匹配算法的代码

        #define N  10;   //样品类别
        #define K  25;   //特征维数
        double LeastDistance()
        {
            double min=10000000000;
            number_no number_no;
            for(int n=0;n<N;n++)
            {
                for(int i=0;i<pattern[n].number;i++)
                {
                    if(match(pattern[n].feature[i],testsample)<min)
                    {
                          //匹配的最小值
                          min=match(pattern[n].feature[i],testsample);
                          number_no.number=n;//模板类别
                          number_no.no=i;//模板序号
                    }
                }
            }
            return number_no;//返回样本的类别和序号
        }
        double match(double a[], double b[])
        {
            double count=0.0;
            for(int i=0;i<K;i++)
            {
                count+=(a[i]-b[i])＊(a[i]-b[i]);
            }
            return count;
        }