甘新勝

(江蘇自動化研究所,江蘇 連云港 222006)

圖像匹配技術是計算機視覺領域的一項關鍵技術在圖像配準、模式識別、目標跟蹤等方面都有應用。圖像匹配通常提取兩幅圖像的特征點形成特征點集,再通過相似性準則描述兩個點集的相似度。特征點可以是邊緣點、角點等。通常特征點選取在噪聲、光照、成像角度等變化下均能檢測到的特征,具有較強的穩(wěn)定性。圖像匹配考慮的是兩幅圖像特征點集的相似性,如果不考慮特征點的提取過程,影響兩個圖像點集匹配的主要原因是遮擋、局部變化等因素。選擇正確的相似性準則是圖像匹配過程中一個重要的步驟。

Hausdorff距離(HD)的原始定義噪聲敏感,很難在實際的圖像匹配中應用。通過對HD的改進能夠消除其本身存在的局限性,Huttenlocher等人[1]提出了部分HD,將最小距離排序再取其中的一個,該改進消除了噪聲的干擾,但在實際應用中,部分比例設置的精確程度影響匹配的效果。Dubuisson等人[2]提出了均值HD(MHD),計算過程中把噪聲也用于計算,在實際應用效果不如部分HD。Azencott等人[3]提出了一種Censord HD(CHD),該改進需要兩次排序,計算復雜度較高。Sim 等人[4]基于M-估計和最小截取二乘法提出了M-HD和LTS-HD,兩者均是屏除噪聲點進行計算,與 PHD一樣存在參數的設置問題。汪亞明[5]在 LTS-HD和 M-HD基礎上提出了魯棒性HD(RHD),RHD依賴于兩個參數的設置,而且在計算過程進行偽邊緣去除,這個操作復雜度較高,在實際匹配中無法準確判定哪些是偽邊緣。改進的一種形式是加權 HD(WHD)[6～9],這種方法通常用于面部識別、文字識別等能夠預先知道物體的各個部分的空間分布。HD不要求匹配雙方建立一對一的點對應的,而是關注兩個匹配點集的最大不匹配程度。本文在分析傳統(tǒng)HD方式的缺陷,并提出了基于核函數的HD測度,該HD是通過對各個最小距離值進行核函數計算,并將函數值的和均值作為單向 HD 值,無向的HD值取兩個單向值的最小值。

1 Hausdorff距離及其改進形式

給定兩個有限點集 A={a1,a2,…,ap}和 B={b1,b2,…,bq},它們之間的Hausdorff距離定義如下:

在上兩式中,范數||?||可取不同形式,如 L1,L∞和 L2等。h(A,B)稱為集合A與集合B的有向Haudorff距離(前向HD),描述了點a∈A到點集B中任意點的最大距離;同樣,函數h(B,A) 稱為從集合B與集合A的有向Haudorff距離(逆向HD),描述了點b∈B到點集A中任意點的最大距離。由于h(A,B) h(B,A)不對稱,所以一般取它們兩者之間的最大值作為兩個點集的Haudorff距離。如果兩個點集的HD為0,就說明這兩個點集是重合的。從定義可以看出,如果兩個點集的大部分點都一樣,但只有很少甚至一個點不一致,得到Hausdorff距離就會較大。說明Hausdorff距離對外點很敏感,針對這個問題,人們提出了很多的改進方法[1-9]。

影響兩個點集的匹配的主要原因是遮擋和兩點集間的局部變化。如果預先能夠知道模板物體在圖像中的被遮擋的比例,那么通過設定 PHD的比例即可能夠實現正確的匹配,但在實際情況中很難知道精確的比例,有時知道大致的比例也不能得到正確的結果。如圖1所示,當比例f為0.395時能夠得到正確的匹配,但取 0.39和 0.4均不能得到正確的結果。同樣的實驗,MHD不能得到正確的匹配,而且M-HD、LTS-HD在參數設置稍大時不能得到正確的匹配。局部變化影響 HD匹配的結果是在第一階段的最小距離集合中存在大量分布在0點附近的值。典型的例子如不同季節(jié)的航拍圖像匹配,道路或者其它物體被植被的遮擋情況不同,從而出現原來直線的道路被扭曲了。

遮擋、局部變化使得最小距離的分布集中在 0值附近,從而出現在某個閾值下,該部分占據的比例達到最大。為了克服遮擋、局部變化對匹配的影響,計算單向 HD值時引用核密度函數的方式,集合A?B的單向HD值計算如下:

式中,ai為集合A的成員,NA是模板A的點數目,dB(ai)表示點 ai到集合 B的最小距離,Kσ是核函數,σ為帶寬。B?A的單向HD值為

其中,N’B為在模板 A覆蓋下的點數目,要求 N’B＞0。通過對最小距離值的分布分析知道,在匹配位置的分布通常接近于高斯分布, Kσ可以取高斯函數:

其中,σ2表示方差,d為最小距離。H(A,B)通過式(7)得到:

當兩幅圖像越相似,H(A,B)越大;反之越小,而匹配點就是函數值的極大值點。通過參數σ2的設置從而決定最小距離在零附近的值起到的作用,當局部變化較大時,σ2取大一些,相反就小一些,通常來說σ2取1～5。從式子可以看出,當核函數取不同的函數得到不同的結果,如取恒指值就是MHD,而M-HD是一種分段函數。使用高斯能夠較好的考慮最小距離集合中的低頻部分,低頻部分的距離值越大,最終取值越大,消除簡單的單一閾值的劃分導致的匹配錯誤。

圖1 合成圖像

2 基于HD的圖像匹配過程

圖像匹配通常是模板和圖像的匹配,即一副圖像為模板,一副為圖像,模板在圖像中搜索物體存在的位置?；贖D的圖像匹配過程如圖2所示,主要包括三步:首先是特征提取,角點、邊緣點提取。角點提取可以采用Harris、SUSAN等算法。其次對提取的特征圖像進行距離變換,目的是為了減少HD的計算量,距離變換根據實際要求選取,兩次掃描就能得到距離圖[10]。然后利用距離圖進行搜索,移動模板在圖像上搜索,計算每一錨點上的 HD 值,選取極值為最佳匹配點。通常來說首先計算前向 HD,只有前向HD值小于或大于某個值才進行逆向 HD的計算,這樣可以減少不必要的計算。如果模板與圖像的存在形變,還需要對模板進行幾何變換,再重復前一過程的搜索。通常來,計算逆向HD時,不取全圖像的數據進行考慮,而只考慮被模板覆蓋的部分[1]。

圖2 基于HD距離的圖像匹配過程

3 實驗結果與分析

為了測試改進 HD的性能,將對 PHD、MHD、M-HD、LTS-HD、本文方法等進行實驗分析。首先設置處理的參數。距離變換算法為串行計算,相鄰距離為 3,對角距離為 4,具體實現見文獻[10]。其次是改進HD的算法設置。實現與原算法不一致的地方在于M-HD和LTS-HD在文獻[5]中并沒有給出逆向(B?A)的計算方法,這里增加了逆向計算,參數與正向(A?B)一致;各個改進HD的參數設置見表1。

實驗分為兩組,第一組實驗使用圖1的圖像進行匹配,圖像來源于文獻[4],模板的實際位置為(37,29)。實驗二是一副經典圖像并經過了涂抹,模板的實際位置為(37,60),效果如圖3,準確匹配的合成效果如圖4所示,與圖1(c)的合成思路一樣,在圖像上疊加模板邊緣圖像。疊加顯示可以直觀的反映出匹配的結果。匹配正確,對應位置的邊緣將保持圖像的邊緣,在圖像上沒有而模板有的邊緣將添加;如果匹配位置不正確,邊緣一致在合成圖上將出現重影,邊緣加重,如圖5是在(35,60)位置進行合成得到的效果圖,從中可以看出,在模板框內本應重疊的帽沿部分出現邊緣加重,原因是疊加圖本應是一條邊緣,但現在出現了兩條。

實驗結果見表1,從中可以看出,①均值HD在兩次實驗中都沒有得到正確的匹配;②部分HD依賴于比例參數f的設置,有時要求設置非常精確才能夠得到正確的匹配;③M-HD 取得正確結果也依賴于τ的設置,第一組實驗為5,第二組實驗為6,當取值較大時不能得到正確匹配,原因是,τ越大,用于計算HD值的點越多,噪聲點越多,偏差也就越大,同樣事情也發(fā)生在LTS-HD;④本文算法在兩組實驗中都能得到較好的匹配結果,都能找到正確的匹配位置。

圖3 匹配圖像

圖4 邊緣及匹配結果

圖5 錯誤匹配的合成效果,合成為位置為(35,60)

表1 各個算法的實驗結果

4 結束語

Hausdorff距離的應用十分廣泛,不同的應用領域都有自身的特點,也就有不同的改進方法。通過實驗分析得到,基于核函數的 Hausdorff距離在圖像匹配具有較強的魯棒性。HD距離經過了研究,但還有很多問題,如計算量大問題。未來的研究將結合變換參數進行匹配研究,并考慮在搜索策略進行改進。

[1]Huttenlocher D P, Klanderman G A, Rucklidge W J.Comparing images using the Haudorff distance[J].IEEE Transactions on Pattern Analysis and machine Intelligence,1993,15(9):850-863.

[2]Dubuisson G P, Jain A K. A modified Haudorff distance for object matching[C]. Proceedings of the 12thIAPR International Conference on Pattern Recognition, Jersusalem,Isr:IEEE press,1994:566-568.

[3]Azencott R, Durbin F, Paumard J. Multiscale indentification of building in compressed aerial scenes[C]. Proceedings of 13thInternional Conferences on Pattern Recognition, Vienna,Austria:[s,n.].1996:974-978.

[4]Sim D G, Kwon O K, Park R H. Object matching algorithm using robust Haudorff distance measures[J].IEEE Transactions on Image Processing, 1999,8(3):425- 429.

[5]汪亞明.圖像匹配的魯棒性Hausdorff方法[J].計算機輔助設計與圖形學學報,2002,14(2):1-4.

[6]Lu Y, Tan C. Chinese word searching in imaged documents[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2004,18(2):229-246.

[7]Lin K H, Lam K M, Siu W C. Spatially eigenweighted haudorff distances for human face recognition[J]. Pattern Recognition,2003,36(8):1827-1834.

[8]Guo B F, Lam K M,Siu W C, Yang S. Human face recognition using a spatially weighted Hausdorff distance[C].IEEE International Symposium on Circuits and Systems, Sydney, NSW:Institue of Electrical and Electronics Engineers Inc,2001:145-148.

[9]Lu Y, Tan C L, Huang W, Fan L Y. An approach to word image matching based on weighted hausdorff distance.[C],Seattle,USA ‘ 6thICDAR’,10-12,Sept,2001,

[10]章晉毓.圖像工程(中冊)[M].北京:清華大學出版社,2007:63.