基于分割模板加權Hausdorff 距離矩陣的特征匹配算法

徐一鳴，劉曉利，劉怡昕，3

(1.南京理工大學 瞬態物理國家重點實驗室，江蘇 南京210094;2.南通大學 電氣工程學院，江蘇 南通226000;3.南京炮兵學院，江蘇 南京211132)

基于Hausdorff 距離(HD)的特征匹配算法因其較小的運算量以及對目標一定程度幾何失真的適應性而得到了較為廣泛的應用。然而由于HD 本身對于噪聲和孤立點較為敏感，在實際運用時，常會因目標被遮擋或存在背景噪聲，導致無法實現圖像配準。針對這種情況，近年來已經提出了多種改進Hausdorff 算法，如部分HD(PHD)、平均HD(MHD)、去出格點HD(M-HD、LST-HD)等。上述算法可以克服一定程度多點、少點或出格點的影響，但在目標存在大比例遮擋或較嚴重非高斯噪聲干擾下的效果仍然欠佳［1］，因此要在電視制導武器系統上應用基于HD 的特征匹配算法，勢必需要對算法的抗干擾性能進行增強。

為了增強特征匹配算法的魯棒性，本文通過構造合適的角點響應函數(CRF)對部分平均HD 進行加權修正;同時采用模板分割的方法，根據子模板信息量來評價其對全局匹配的貢獻程度，構造加權修正的相似性度量矩陣。實驗證明，通過對相似性度量與特征空間分別進行加權修正，可以有效抑制出格點的干擾，從而弱化局部區域錯誤特征對全局匹配產生的影響。

1 基于加權HD 的角點匹配

1.1 角點檢測

角點作為圖像興趣點的一種特例，可以描述為圖像上灰度變換劇烈且和周圍的鄰點有著顯著差異的像素點，通常定義為一階導數為局部最大時所對應的像素點。角點包含了圖像至關重要的信息，且數量相對較少，比較適合用于實時匹配計算。

目前常用的角點檢測算子有多種，如Movarac算子、Harris 算子、F?rstner 算子、Plessey 算子、Susan算子等。本文采用了最小核相似區檢測角點(SUSAN)算法，該算法由Smith 首先提出，通常采用一個包含37 個像元的近似圓形模板，并基于該模板領域的圖像灰度計算角點響應函數的數值，如果大于某閾值且為局部極大值，則認為該點為角點。SUSAN 檢測算法具有方法簡單、特征定位比較準確、抗噪能力強等特點［2-3］。

1.2 HD 定義

給定2 個點集A={a1，a2，…，ap}和B={b1，b2，…，bq}，h(A，B)和h(B，A)稱為集合A 與B 之間的有向距離，定義為:

則A 和B 之間的HD 定義為:

HD 表征了2 點集間的最不相似程度［4］，由于無須知道點與點之間的一一對應關系，可以容忍一定程度下點位置的不準確以及多點、少點的誤差，因此非常適合應用于圖像配準。

1.3 基于角點響應函數的加權HD

為增強算法的魯棒性，結合部分平均HD 與CRF，提出了一種基于CRF 的加權部分平均HD.

首先去除零均值高斯噪聲的影響，采用部分平均HD，如下式［5-9］:

式中:th 表示按由小到大的順序排序，即把點集A中所有點到點集B 的距離按由小到大的順序排序，再對1 到k 的k 個距離求均值。

進一步考慮因非零均值噪聲和目標遮擋造成的影響。由此類干擾產生的角點，即使距離匹配中心的角點距離較近，但是通過構造合適的CRF，可以得到不同的CRF 數值。因此可以由二者CRF 的差值來構造加權函數，對部分平均HD 公式進行修正，從而抑制噪聲或遮擋產生的影響。

定義

稱為A 到B 的有向加權HD，Na為點集A 中選取的特征點的總數，d(a，B)為點集中特征點a 到點集B 的距離，w(a)為該距離上的權值。

模板圖像與搜索圖像的角點集分別定義為A{a［i］}，i∈［1，2，…，p］和B{b［j］}，j∈［1，2，…，q］，其中a［i］和b［j］包括了角點的位置以及該角點的CRF 值，定義為a［i］.POS，a［i］.CRF 以及b［j］.POS，b［j］.CRF.

角點檢測算法中的CRF 通常采用可以反映角點突出性，即角點處各方向灰度差變化趨勢的響應函數。而構造加權函數的目的為衡量該角點包含信息量的多少，通過估算該角點的不等“價值”來增強對于出格點的區分能力。由對特征點的分析可知，角點是在微小鄰域中灰度急劇變化的點，即在該局部區域中含有較大的信息量，因此將CRF 定義為角點像元與平均信息量之差的平方和。根據SUSAN算法中的37 像元模板，可得如下公式:

對于模板角點集A 中任一點a［i］，計算d(a［i］.POS，B{b［j］.POS})，a［i］必然對應于a［i］.POS-b［j］.POS|的點集B 中的m 個點b［jm］(通常情況下m=1，只有個別情況下才會存在多個對應點)，有權重公式如下:

經過加權的模板圖像到搜索圖像的有向HD 公式如下:

式中:Na=f1p，f1∈(0，1).

同理可得搜索圖像到模板圖像的有向HD 公式

式中:Nb=f2q，f2∈(0，1).

2 基于加權HD 矩陣的圖像匹配算法

2.1 分割模板圖像HD 矩陣

基于局部熵差的圖像匹配思想，可以將模板分割引入匹配過程，從而進一步抑制大比例目標遮擋或嚴重噪聲的影響。

將模板圖像分割成M ×N 個子模板，對各子模板與搜索圖像進行HD 計算，得到一個M ×N 維的HD 矩陣:

這個距離矩陣中每個元素的數值即該子模板與對應區域的相似程度;距離矩陣的范數則反映了整個模板與對應區域的相似程度。利用這個特性，可以根據各子模板對于整個匹配過程貢獻度的大小進行加權，從而較好地抑制受遮擋或噪聲等不利因素影響嚴重的局部區域對全圖像匹配造成的干擾。

2.2 HD 矩陣的加權修正

為了增加匹配的可靠性，對各子模板的重要性進行分析。由于角點在局部區域中含有較大的信息量，因此對于子模板來說，含有的角點越多，說明該子模板含有的信息量越大，對于圖像匹配的重要性就越高;反之，則說明該子模板的重要性越低。

由此采用了信息融合的方法來增強算法的可靠性，引入了角點密度矩陣對HD 矩陣進行修正，將經過加權修正的HD 矩陣作為相似性度量。

定義Ci，j=1-pij/NT，pij表示第i 行第j 列的子模板含有的角點數目，NT表示整個模板含有的角點總數。有角點密度矩陣

經過修正的加權HD 矩陣為

(11)式的意義在于，在子模板角點密度很小的情況下，即使該子塊與對應區域HD 很小，亦不足以說明兩者相似性高的可信度高;反之，當子模板角點密度很高，如果該子塊與對應區域的HD 很小，可以相信這二者相似性較高。

該加權HD 矩陣可以有效調整重要性不等的子模板對整體匹配產生的影響，從而將圖像匹配最后轉化為矩陣之間的比較。

2.3 HD 矩陣的比較

對于2 個含有大小各異元素的HD 矩陣，其大小的比較通常可以通過矩陣范數的計算來實現。

Frobenius 范數(F 范數)在工程上應用較為廣泛，其計算公式為

對于所求得的HD 矩陣，分別求出其F 范數，其中最小的F 范數對應的矩陣測度即對應搜索圖像上與模板圖像整體相似度最高的區域。

2.4 算法具體實現步驟

1)采用SUSAN 算子分別提取模板圖和搜索圖的角點，得到子模板特征二值圖Ti和搜索特征二值圖S，i∈［1，N］.

2)根據(10)式求解子模板角點密度矩陣CHD.

3)根據(5)式計算子模板Ti與搜索圖像S 各角點的CRF 值，得到T_CRFi［x，y］及S_CRF［x，y］.

4)采用3-4DT 算法在二維空間中對特征點集進行距離轉換［10］，得到圖像距離轉換矩陣JTi和JS.

5)根據(7)式、(8)式，結合JTi、JS、T_CRFi［x，y］及S_CRF［x，y］來求取每個子模板與搜索圖像之間的加權HD，得到距離矩陣JHD.

6)根據(11)式，結合CHD、JHD求取修正后的加權HD 矩陣JWHD.

7)根據(12)式，求取JWHD的Frobenius 范數D=‖JWHD‖F，以具有最小范數度量值的匹配點作為最終匹配點。

算法流程圖如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flowchart

3 實驗結果及分析

為證明本文算法的有效性，進行了大比例目標遮擋及斑點噪聲干擾下的目標跟蹤實驗，測試匹配效果及實時性能。計算機配置為INTEL P-IV 1.8 G處理器，512 M DDR 內存。在進行圖像匹配時，部分HD 中的參數f1，f2均設為0.8，模板圖像大小為64×64，搜索圖像大小為320 ×240.

圖2為模板圖像及其角點檢測結果，模板被分割為4 ×4 共16 個子模板。圖3為搜索圖像角點檢測結果。表1記錄了實時跟蹤圖像序列中的一些中間狀態幀。整個圖像序列共125 幀圖像，其中約90幀圖像存在不同程度的目標遮擋。為了驗證大比例遮擋情況下的匹配性能，未對模板進行更新。整個跟蹤過程中，模板對應區域角點數量因遮擋導致的少點比率最高達到43.75%.將目標實時跟蹤軌跡分解為x 軸方向與y 軸方向進行軌跡連續性分析，如圖4所示。目標在第25 幀～115 幀之間處于不同程度的局部遮擋狀態，軌跡分布連續而穩定，沒有出現明顯的誤匹配點。

圖2 模板圖像及分割模板角點檢測圖像Fig.2 Template image and corners of template partition image

圖3 搜索圖像角點檢測結果Fig.3 Searched corners in image

當改用部分平均Hausdorff 算法時，當目標進入遮擋區域，便無法進行正確的匹配。

為了驗證算法在嚴重非高斯噪聲干擾下的性能，對搜索圖像加入了較嚴重的斑點噪聲(n=10)，并進行匹配分析。圖5、圖6分別為加入噪聲前后的角點檢測結果，可見加入斑點噪聲后，搜索圖像中增加了大量因噪聲引起的角點。圖7為噪聲干擾下的匹配結果示意圖，圖7(b)與圖7(c)為搜索圖像角點與模板匹配情況，可以看到存在一個錯配點。圖7(a)為匹配區域扣除正確匹配點外的出格點，共計12 個。對于僅有16 個角點的模板，出格點比例高達42.9%，錯配率為3.57%.

圖4 目標跟蹤軌跡Fig.4 Tracking trajectory of target

當改用部分平均HD 算法時，無法實現正確匹配。

將基于分割模板加權HD 矩陣算法(TPWHDM)與部分平均HD 算法(PMHD)進行比較，測試最大、最小以及平均匹配時間(tmax，tmix，)和目標匹配效果，如表2所示。

表1 實時跟蹤圖像序列Tab.1 Real-time tracking image sequence

圖5 加入斑點噪聲前的角點檢測圖像Fig.5 Corner detection without noise

圖6 加入斑點噪聲后的角點檢測圖像Fig.6 Corner detection with noise

4 結論

由于HD 對出格點比較敏感，導致基于HD 的特征匹配算法較區域相關匹配算法更易受目標遮擋及噪聲干擾的影響。本文利用特征點信息量的不等性，通過構造角點響應函數，提出了一種基于CRF的加權部分平均HD;同時通過模板分割后子模板對于全局匹配貢獻度的不等性進行相似性度量矩陣加權修正，從而在相似性度量與特征空間上對因遮擋或噪聲引起的局部錯誤特征進行了雙重抑制。目標跟蹤實驗證明該算法具有較強的魯棒性，對于可靠性要求較高的電視制導武器系統具有一定的可行性。

圖7 加入嚴重噪聲干擾后的匹配結果Fig.7 Tracking result with heavy spot noise

表2 2 種算法的性能比較Tab.2 Performance comparison of two algorithms

References)

［1］ 趙峰偉.景象匹配算法性能評估及其應用［D］.北京:國防科學技術大學，2002.ZHAO Feng-wei.Performance evaluation and application of image matching algorithms［D］.Beijing:National University of Defense Technology，2002.(in Chinese)

［2］ Smith S M，Brad Y M.SUSAN-a new approach to low level image processing［J］.International Journal of Computer Vision，1997，231，23(1):4578.

［3］ 劉博，仲思東.一種基于自適應閾值的SUSAN 角點提取方法［J］.紅外技術，2006，28(6):331-333.LIU Bo，ZHONG Si-dong.A SUSAN corner detector based on adaptive threshold［J］.Infrared Technology，2006，28(6):331-333.(in Chinese)

［4］ Huttenlocher D P，Klanderman G A，Rucklidge W J.Comparing images using the Hausdorff distance［J］.IEEE Trans Pattern Analysis and Machine Intelligence，1993，15(10):850-863.

［5］ Dubuisson M P，Jain A K.A modified Hausdorff distance for object matching［C］∥Proceedings of 12th International Conference on Pattern Recognition.Jerusalem:IEEE Computer Society，1994:566-568.

［6］ William J，Rucklidge.Efficiently location objects using the Hausdorff distance［J］.International Journal of Computer Vision，1997，24(3):251-270.

［7］ Shen F，Wang H.Real time gray level corner detector［J］.Pattern Recognition Letters，2002，23(8):1-6.

［8］ Sim D G，Kwon O K，Park R H.Object matching algorithm using robust Hausdorff distance measures［J］.IEEE Trans Image Process，1999，8(2):425-429.

［9］ Arturo P，Victor A R，Raul Enrique S Y，et al.Monte Carlo evaluation of the Hausdorff distance for shape matching［J］.LNCS，2006，4225:686-695.

［10］ Borgrfore G.Distance transformations in digital images ［J］.Computer Vision Graphics and Image Processing，1986，34:344-371.