一種基于改進(jìn)Hausdorff距離的圖像匹配方法*

甘新勝

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

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

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

1 Hausdorff距離及其改進(jìn)形式

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

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

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

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

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

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

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

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

圖1 合成圖像

2 基于HD的圖像匹配過程

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

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

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

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

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

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

圖3 匹配圖像

圖4 邊緣及匹配結(jié)果

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

表1 各個(gè)算法的實(shí)驗(yàn)結(jié)果

4 結(jié)束語

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

[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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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].北京:清華大學(xué)出版社,2007:63.