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

(1.南京理工大學(xué) 瞬態(tài)物理國家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京210094;2.南通大學(xué) 電氣工程學(xué)院，江蘇 南通226000;3.南京炮兵學(xué)院，江蘇 南京211132)

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

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

1 基于加權(quán)HD 的角點(diǎn)匹配

1.1 角點(diǎn)檢測

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

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

1.2 HD 定義

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

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

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

1.3 基于角點(diǎn)響應(yīng)函數(shù)的加權(quán)HD

為增強(qiáng)算法的魯棒性，結(jié)合部分平均HD 與CRF，提出了一種基于CRF 的加權(quán)部分平均HD.

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

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

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

定義

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

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

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

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

經(jīng)過加權(quán)的模板圖像到搜索圖像的有向HD 公式如下:

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

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

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

2 基于加權(quán)HD 矩陣的圖像匹配算法

2.1 分割模板圖像HD 矩陣

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

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

這個距離矩陣中每個元素的數(shù)值即該子模板與對應(yīng)區(qū)域的相似程度;距離矩陣的范數(shù)則反映了整個模板與對應(yīng)區(qū)域的相似程度。利用這個特性，可以根據(jù)各子模板對于整個匹配過程貢獻(xiàn)度的大小進(jìn)行加權(quán)，從而較好地抑制受遮擋或噪聲等不利因素影響嚴(yán)重的局部區(qū)域?qū)θ珗D像匹配造成的干擾。

2.2 HD 矩陣的加權(quán)修正

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

由此采用了信息融合的方法來增強(qiáng)算法的可靠性，引入了角點(diǎn)密度矩陣對HD 矩陣進(jìn)行修正，將經(jīng)過加權(quán)修正的HD 矩陣作為相似性度量。

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

經(jīng)過修正的加權(quán)HD 矩陣為

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

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

2.3 HD 矩陣的比較

對于2 個含有大小各異元素的HD 矩陣，其大小的比較通常可以通過矩陣范數(shù)的計(jì)算來實(shí)現(xiàn)。

Frobenius 范數(shù)(F 范數(shù))在工程上應(yīng)用較為廣泛，其計(jì)算公式為

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

2.4 算法具體實(shí)現(xiàn)步驟

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

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

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

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

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

6)根據(jù)(11)式，結(jié)合CHD、JHD求取修正后的加權(quán)HD 矩陣JWHD.

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

算法流程圖如圖1所示。

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

圖3 搜索圖像角點(diǎn)檢測結(jié)果Fig.3 Searched corners in image

當(dāng)改用部分平均Hausdorff 算法時(shí)，當(dāng)目標(biāo)進(jìn)入遮擋區(qū)域，便無法進(jìn)行正確的匹配。

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

圖4 目標(biāo)跟蹤軌跡Fig.4 Tracking trajectory of target

當(dāng)改用部分平均HD 算法時(shí)，無法實(shí)現(xiàn)正確匹配。

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

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

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

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

4 結(jié)論

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

圖7 加入嚴(yán)重噪聲干擾后的匹配結(jié)果Fig.7 Tracking result with heavy spot noise

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

References)

［1］ 趙峰偉.景象匹配算法性能評估及其應(yīng)用［D］.北京:國防科學(xué)技術(shù)大學(xué)，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］ 劉博，仲思東.一種基于自適應(yīng)閾值的SUSAN 角點(diǎn)提取方法［J］.紅外技術(shù)，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.