2.2.4 模板匹配

模板匹配（Template Matching）是圖像識(shí)別中最具代表性的方法之一，其具有算法實(shí)現(xiàn)容易，匹配速度快的特點(diǎn)。

1.模板匹配概念

模板匹配是將從待識(shí)別的圖像提取的若干特征量與模板對(duì)應(yīng)的特征量進(jìn)行比較，計(jì)算圖像和模板特征量之間的距離，用最小距離法判定所屬類。用模板匹配法進(jìn)行模式識(shí)別時(shí)通常需要先建立標(biāo)準(zhǔn)模板庫。Hausdorff距離（HD）又稱最大最小距離，是描述兩組點(diǎn)集之間相似程度的一種量度，它是集合與集合之間距離的一種定義形式。假設(shè)有兩組集合A={a1,a2,…,aN }A，B={b1,b2,…,bN }B，則這兩組集合之間的Hausdorff距離可以定義為

2.Hausdorff距離

式中，稱為A集合和B集合之間的直接Hausdorff距離，‖.‖是某種距離范數(shù)。如果定義一個(gè)點(diǎn)a到一個(gè)點(diǎn)集B的距離d(a,B)為該點(diǎn)到該點(diǎn)集中每一個(gè)點(diǎn)的距離的最小值，即

則dh(A,B)是點(diǎn)集A中每個(gè)點(diǎn)到點(diǎn)集B中的最小距離集合d(a,B)中的最大值。Hausdorff距離dH取dH(A,B)和dH(B,A)的最大值。從而可獲得兩個(gè)點(diǎn)集A和B之間的匹配程度。

3.改進(jìn)的Hausdorff距離

為了抵抗噪聲的干擾，對(duì)Hausdorff距離進(jìn)行改進(jìn)，把距離公式由

變?yōu)?/p>

即把求最大最小距離變?yōu)榍笞钚【嚯x的累加和，這樣做可以有效地抵抗隨機(jī)噪聲的干擾，從整體上計(jì)算兩個(gè)點(diǎn)集之間的距離，而不是只靠最大距離，從而增加了兩個(gè)點(diǎn)集之間距離的穩(wěn)定性，從理論上更加合理。

4.基于改進(jìn)的Hausdorff距離的模板匹配算法

基于改進(jìn)的Hausdorff距離的模板匹配算法如下。

先生成各個(gè)模板的模板庫，然后逐個(gè)計(jì)算待識(shí)別的樣本圖像與各個(gè)樣本的模板庫之間的改進(jìn)的Hausdorff距離Di(i=1,2,…,N)，N為模板個(gè)數(shù)。步驟如下：

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

（b）從上到下，從左至右，逐個(gè)像素掃描待識(shí)別樣本圖像，如果是1（黑色像素），記錄下該點(diǎn)Px,y的位置；否則繼續(xù)掃描。

（c）模板圖像上，在以Px,y點(diǎn)為中心的k × k鄰域內(nèi)，搜索1（黑色像素），尋找與Px,y最近的點(diǎn)，并且計(jì)算Px,y和該點(diǎn)之間的距離，此距離是待識(shí)別圖像和模板圖像在該點(diǎn)的最小距離。如果k×k鄰域內(nèi)沒有找到1，就認(rèn)為距離為較大者。

（d）把所有計(jì)算的距離進(jìn)行累加到待識(shí)別樣本到模板的距離D(X,Ti)中。

（e）判斷是否掃描待識(shí)別圖像結(jié)束，如沒有結(jié)束，轉(zhuǎn)到步驟b，否則繼續(xù)計(jì)算，直至得到待識(shí)別樣本到模板的距離D(X,Ti)。

（f）按照同樣的步驟可計(jì)算模板到待識(shí)別樣本的改進(jìn)的Hausdorff距離D(Ti,X)。

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

當(dāng)Di最小時(shí)，對(duì)應(yīng)的模板就是識(shí)別的結(jié)果。

5.模板匹配的C語言實(shí)現(xiàn)

下面給出基本的模板匹配算法的C語言實(shí)現(xiàn)，如代碼2-8所示。

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

        #define N  10;   //樣品類別
        #define K  25;   //特征維數(shù)
        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;//模板序號(hào)
                    }
                }
            }
            return number_no;//返回樣本的類別和序號(hào)
        }
        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;
        }