引言

    圖象匹配是在計算機視覺和自動目標(biāo)識別領(lǐng)域中廣泛應(yīng)用的識別定位技術(shù)，主要是在給定初始目標(biāo)信息的情況下，能在后續(xù)圖象中自動找到目標(biāo)區(qū)域。目標(biāo)位置通常用相對于視場左上角的偏移、旋轉(zhuǎn)角度和放大比例等幾個參數(shù)來描述。

    當(dāng)前，圖象匹配主要方法有特征匹配方法、基于平移模型的相關(guān)匹配方法等。特征匹配方法一般應(yīng)用于待匹配圖象目標(biāo)有較明顯的幾何特征，例如亮度特征、區(qū)域特征、邊緣特征、點特征等請情況。首先按照相同的特征提取準(zhǔn)則在輸入圖象和模板圖象中提取特征，再根據(jù)兩者特征的對應(yīng)性得到一個超方程組，然后可以通過一些諸如最小二乘法、最小錯誤方程法等優(yōu)化解法得到位置參數(shù)。定位將相對容易一些。但是，當(dāng)目標(biāo)處于復(fù)雜背景中，或者沒有明顯幾何特征時，這種方法的應(yīng)用受到很大的限制。此外，當(dāng)出現(xiàn)新的特征或者部分特征丟失等情況下，特征之間的對應(yīng)性將難以確立。本文論述的基于區(qū)域的仿射模型定位方法能夠在復(fù)雜背景中獲得較高的匹配精度，可以作為互相關(guān)算法的改進型。

1 仿射變換定義及其性質(zhì)

    仿射變換是射影幾何中的一種基本變換，其定義是：若變換 ， ， 是非奇異線性變換，  ,則變換 稱為仿射變換。
二維歐氏空間上的仿射變換為：
                            (1)
其中，
 ， ， 
式中的 都是實數(shù)。

    仿射變換具有平行線轉(zhuǎn)換成平行線和有限點映射到有限點的一般特性。平移，旋轉(zhuǎn)，縮放，及錯位等都是二維仿射變換的特例。

2 誤差評價方法

    傳統(tǒng)的誤差評價方式往往容易受到極個別大誤差點的影響，而不能夠有效考慮整體的情況。降低個別較大誤差點的影響，必須考慮在映射函數(shù)上對其進行抑制?？疾旌瘮?shù)誤差映射函數(shù)：                                (2)

    函數(shù)曲線表示為：
 
圖1   曲線

    實線表示 對應(yīng)的曲線，虛線表示 對應(yīng)的曲線， 值控制該函數(shù)對誤差的抑制范圍， 值越小對誤差值抑制的程度就越大。再采用 函數(shù)計算上面圖1的例子得到，(b)相對于(a)的 值為0.988，而(c)相對于(a)的 值為1.241，大于真正的目標(biāo)圖象的誤差，這種評價方式是合理的。

3 迭代求解算法

    這種方法的突出優(yōu)點是在目標(biāo)真實位置附近能夠快速收斂，并且可以獲取非常高的定位精度。缺點是該方法是局部收斂的，必須要有目標(biāo)的先驗位置知識。

    以模板圖象中心為坐標(biāo)原點建立坐標(biāo)系，那么模板圖象表示為 。模板圖象中的點 經(jīng)仿射變換后，變?yōu)檩斎雸D象中的點 ，其中位置 和 之間存在仿射關(guān)系： 。 為 和仿射系數(shù) 的函數(shù)。 和 是相對于模板圖象中心的水平和垂直坐標(biāo)， 和 表示仿射變換后的圖象在水平和垂直方向的變化量。

    若用 來表示模板圖象 經(jīng)過仿射變換后在輸入圖象中的對應(yīng)區(qū)域，則在灰度不變性前提下有公式成立：
                         (3)

    至此，模板目標(biāo)圖象和輸入圖象之間的仿射關(guān)系就建立起來了。

    基于梯度下降的算法是一種局部收斂的算法，計算時需要一個參數(shù)的初始估計 。采用迭代遞歸方法來求解最優(yōu)的仿射參數(shù) ：

    設(shè) ，參數(shù) 為仿射參數(shù) 的兩次估計值之間的差，稱為仿射增量：
                         (4)     參數(shù) 仍然采用迭代過程來計算。采用公式(3.11)所示的誤差評價函數(shù)：
  
                         (5)

    對誤差評價函數(shù)表達式中 的各分量分別求偏導(dǎo)可得：
   (6)

    令  ，得到含有未知變量 的方程，

    再采用高斯牛頓迭代法求解 ：
                          (7) 其中 ， 的調(diào)整增量 ， 
  

    (8)其中 部分計算較繁瑣，可以用 來代替。

    總結(jié)上面各計算分項，得到總的計算公式：
 
      (9) 

    參數(shù) 的迭代計算收斂之后，就得到了第 次仿射參數(shù) 。繼續(xù)計算 ， ，……，直到 ，得到參數(shù) 的最優(yōu)值。

4 迭代求解算法分析

    本節(jié)的目的是在分析算法的基礎(chǔ)上，盡快提高算法的執(zhí)行速度。下面首先來具體分析迭代求解參數(shù) 公式中的各個部分，以及詳細(xì)求解方法。 

    1）   表示第 次計算得到的目標(biāo)圖象，是按照第 次仿射參數(shù)到輸入圖象中截取的目標(biāo)區(qū)域。根據(jù)已知仿射參數(shù)，模板圖象中任意點在輸入圖象中對應(yīng)點的坐標(biāo)可以由下式求出：
       （10）

    假設(shè)模板圖象中水平相鄰兩個象素點 和 ，則經(jīng)仿射變換之后在輸入圖象中有對應(yīng)的兩點 和 。不難推導(dǎo)，有如下關(guān)系式成立：  。同理假設(shè)模板圖象中豎直相鄰兩個象素點 和 ，則經(jīng)仿射變換之后在輸入圖象中有對應(yīng)的兩點 和 ，有如下關(guān)系式成立：  。因此，可以得到結(jié)論：輸入圖象中經(jīng)變換后的兩點坐標(biāo)差只與模板中對應(yīng)點的坐標(biāo)差有關(guān)系，而與對應(yīng)點所處位置無關(guān)。也就是說，只要計算一次仿射變換，得到目標(biāo)左上角象素點的在輸入圖象中的位置，其它象素點的精確位置就可以采用增量法來求出。因此，除了第一個點以外，只需要計算兩個浮點加法就可以完成一個仿射變換點的精確位置。
僅僅獲得了精確的位置還是不夠的，還需要利用雙線性差值法來獲取相對精確的灰度值。
 
圖2  雙線性插值示例圖
 
  (11)
 ， ， ， 分別表示圖2中1，2，3，4點的灰度值。

    因此，對一個目標(biāo)象素點，只需要計算3次乘法運算和6次加法運算就可以獲得基于雙線性插值的結(jié)果灰度值。試驗發(fā)現(xiàn)，算法對目標(biāo)圖象灰度值的精度要求較小，只取整數(shù)部分就可以基本上滿足算法的需要。

    利用雙線性插值來求解精確圖象，是整個算法中最耗時間的部分。究竟是采取雙線性插值法還是采用相對簡單的最近鄰法來計算，需要根據(jù)具體情況來分析。根據(jù)實驗情況來看，當(dāng)模板圖象較大時（3000個象素點以上），采用雙線性插值法來求解目標(biāo)圖象有較大的時延。雙線性插值法在對比度較低、圖象紋理不豐富、目標(biāo)變化幅度較劇烈的時候表現(xiàn)比較突出，比最近鄰法收斂要快得多，總的計算時間也要略少。但是采用大模板時，雙線性插值法耗費的時間將它所帶來的便利抵消掉了，整體上就比采用最近鄰法略慢。

    2）差分圖象 ，包括水平差分和豎直差分兩部分，即 ，為兩個列向量，分別表示水平和豎直方向差分圖象。利用下面水平和豎直算子來求解差分圖象：
  
(a)水平差分算子       (b)豎直差分算子
圖3 差分算子

    實驗發(fā)現(xiàn)這部分對于精度要求雖然要比上面求解目標(biāo)圖象時要高一些，如果去掉小數(shù)部分也基本上沒有太大的影響。注意，差分圖象的求解是在輸入圖象中求得的，而不是對目標(biāo)圖象施算子。也可以在目標(biāo)圖象上求差分圖象，但是需要做個適當(dāng)?shù)淖儞Q。

    3） 函數(shù)的求解。

    可以采用查找表的方式來完成。如果目標(biāo)圖象和模板圖象均采用了整數(shù)形式，那么可以得到兩個圖象的象素差的存在范圍： 。又因為 函數(shù)具有關(guān)于原點對稱的性質(zhì)，所以只需要建立 的查找表就可以了。

    4） 求解。 ，表示仿射參數(shù)對 各分量的偏導(dǎo)數(shù)，反映了 各分量對整體的影響。當(dāng) 分別取0到5不同的值時，可以求得 的結(jié)果向量。因此可以通過不同的 值而直接表現(xiàn)為一些確定的向量。如下所示：
 
    5） 項： 在算法實現(xiàn)時，可以考慮只使用一個固定的 經(jīng)驗值，在以前的試驗中，采用了112.8，也就是65 ，效果較好。

    6）向量 為已知模板圖象。

5 迭代算法實驗分析：

    首先給出輸入圖象，如圖4(a)所示，再將輸入圖象中的矩形框標(biāo)志的區(qū)域截取出來，作為模板圖象，如圖4(b)所示。
           
(a)輸入圖象                                  (b)選取模板圖象
圖4 輸入圖象及模板圖象

    以圖5中的虛線框為初始估計值，按照上面給出的迭代算法求解，收斂之后得到仿射變化參數(shù)，再將其以矩形框的形式顯示出來，得到下面結(jié)果：
          
(a)匹配結(jié)果圖象                        (b)定位區(qū)域的目標(biāo)圖象
圖5 匹配結(jié)果圖象和定位結(jié)果目標(biāo)圖象

    從匹配的結(jié)果來看，最終的匹配框相比初始估計發(fā)生了旋轉(zhuǎn)、位移和比例放大變化，與圖4(a)中的模板圖象截取框完全吻合。將框中的圖象截取出來，得到的目標(biāo)圖象（如圖5(b)所示）與模板圖象完全一致，效果理想。從運算時間上來看，在迭代收斂區(qū)間內(nèi)，對于30 30大小的模板，算法從開始狀態(tài)到收斂僅需要8毫秒的時間（PⅢ730處理器，256M內(nèi)存，VC6.0編譯），驗證了該算法的可實時性能。

6 總結(jié)

    在本文中，首先對傳統(tǒng)的誤差評價方式進行了改進，減小了少數(shù)大誤差點對誤差評價造成的過大影響，更全面的考慮整個誤差的總體分布情況。隨后論述了仿射變換的定義和性質(zhì)，然后給出了基于區(qū)域仿射模型的快速定位方法，迭代求解算法。對迭代求解方法，本文詳細(xì)討論了它的實現(xiàn)原理，細(xì)節(jié)，并對算法進行了詳細(xì)的分析，同時給出了算法流程圖，以及試驗部分?？傮w來說，具有較強的實際意義。

參考文獻：

[1] Q. Zheng, R.R. Chellappa. Automatic feature point extraction and tracking in image sequences for
arbitrary camera motion. Computer Visionm, 1995, Vol.15: pages 31-76

[2] G. Jacob, A. Noble, and A. Blake. Robust contour tracking in echographic sequences. In Proceedings of
6th International Conference on Computer Vision, Bombay (India), January 1998: pages 408-413

[3] Min C. Shin, Dmitry Goldgof, and Kevin W. Bowyer. Comparison of edge detectors using an object recognition task. Proceedings of the IEEE CVPR Conference, 1999: pages 360-365

[4] John C. McEachen and James S. Duncan. Shape-based tracking of naturally occurring annuli in image sequences. In Computer Vision and Pattern Recognition, IEEE Computer Society, New York City, June 1993:
pages 613-614

[5] R.J. Feriez and D.C. Lang. Gear-tooth fault detection and tracking using the wavelet transform. Proc. Prognosis of Residual Life of Machinery and Structures, MFPT, 1998

[6] 毛澎芬, 沈世明. 射影幾何.上海：上?？茖W(xué)技術(shù)文獻出版社, 1985

[7] Song-Ha Choi and Seong_whan Lee. Region tracking using perspective motion model. Pattern Recognition 33(2000) 2095-2098.

[8] Michael J.Black and Allan D.Jepson, Eigentracking: robust matching and tracking of articulated objects using a view-based representation, [A], International Journal of Computer Vision, 1998: 26(1) pages 63-84.

[9] Klbl O, Bach U, Gasior D and de Laporte K. Multi-template-matching for the automation of photogrammetric measurements. Archives of the 17 th Congress ISPPS, Washington 1992; 29(B3): 540-548