摘  要： Hausdorff距離在圖像匹配領(lǐng)域廣泛應(yīng)用。針對(duì)Hausdorff距離結(jié)合一些搜索策略的匹配算法實(shí)時(shí)性不高的問(wèn)題，提出了一種基于改進(jìn)Hausdorff距離和人工蜂群算法搜索策略的圖像快速匹配。首先提取模板圖像和匹配子圖的邊緣特征，然后計(jì)算的模板圖像和匹配子圖的Hausdorff距離作為兩者的相似度量標(biāo)準(zhǔn)，最后采用人工蜂群算法進(jìn)行搜索匹配。實(shí)驗(yàn)結(jié)果表明，該方法在不降低匹配率的情況下，縮短了匹配時(shí)間，能應(yīng)用到嵌入式領(lǐng)域。

　　關(guān)鍵詞： 圖像匹配；Hausdorff距離；人工蜂群算法

0 引言

　　圖像匹配[1]是指根據(jù)模板圖像的特征信息在新的圖像中搜索相同或者相似特征信息的子圖像過(guò)程。圖像匹配技術(shù)廣泛應(yīng)用于人臉識(shí)別[2]、運(yùn)動(dòng)目標(biāo)識(shí)別與跟蹤[3]、行人檢測(cè)[4]、圖像拼接和融合[5]等領(lǐng)域。圖像匹配方法可分為三類：（1）基于圖像灰度信息的匹配方法[6]。該類方法易實(shí)現(xiàn)，一方面計(jì)算量較大，另一方面是當(dāng)圖像信息缺乏時(shí)匹配容易失敗。（2）基于遺傳算法的圖像匹配[7]。該類方法完成匹配的概率比一般算法的概率要高，但可能會(huì)增加計(jì)算量。（3）基于圖像特征的匹配方法[8-9]。該類方法計(jì)算量小，速度較快，但是對(duì)特征信息較敏感。Hausdorff距離是一種常用作圖像匹配的相似度量距離參數(shù)，它不需要建立兩個(gè)點(diǎn)集中點(diǎn)的一一對(duì)應(yīng)關(guān)系，對(duì)圖像的噪聲和小幅度旋轉(zhuǎn)具有魯棒性。目前基于Hausdorff距離的圖像匹配[10]方法很多，都是以提高匹配速度和匹配率為目的，有些效果并不理想。本文根據(jù)人工蜂群算法比遺傳算法、差分差異算法在優(yōu)化問(wèn)題方面的優(yōu)越性，以及該算法操作簡(jiǎn)單、運(yùn)算快捷的優(yōu)勢(shì)來(lái)進(jìn)行圖片匹配的搜索，并以改進(jìn)的部分Hausdorff距離作為相似度量來(lái)進(jìn)行圖像匹配。實(shí)驗(yàn)結(jié)果表明，該算法在匹配率不降低的情況下，減少了圖像匹配時(shí)間。

1 改進(jìn)Hausdorff距離

　　Hausdorff距離[11]是定義在兩個(gè)點(diǎn)集上的最大最小距離。設(shè)兩個(gè)有限點(diǎn)集A={a1，a2，a3，…，ap}和B={b1，b2，b3，…，bp}。則集合A、B之間的Hausdorff距離定義為：

　　H（A，B）=max[h（A，B），h（B，A）]（1）

　　其中，‖a-b‖表示點(diǎn)a和b之間的距離范數(shù)；h（A，B）表示點(diǎn)集A中所有點(diǎn)到點(diǎn)集B的最小距離的最大值；h（B，A）為反向Hausdorff距離。兩者的最大值構(gòu)成了H（A，B）。

　　Hausdorff距離表示兩個(gè)點(diǎn)集之間的相異度。但是傳統(tǒng)的Hausdorff距離對(duì)集合中的噪聲點(diǎn)、異常點(diǎn)特別敏感。針對(duì)這種情況，Huttenlocher[11]提出了部分Hausdorff距離。

　　Hk，l（A，B）=max[hk（A，B），hl（B，A）]（2）

　　其中：

　　其中，1≤k≤p，1≤l≤q，p、q分別為點(diǎn)集A、B中元素的個(gè)數(shù)。表示集合A中所有點(diǎn)到集合B中最小距離按從小到大排序后的第K個(gè)值，即為hk（A，B）。K值由f和q的積向下取整獲取，其中f∈[0，1]。部分Hausdorff能消除噪聲和異常點(diǎn)。但是部分Hausdorff距離計(jì)算只考慮集合A到集合B的距離，而沒(méi)有考慮集合A中每一個(gè)點(diǎn)到集合B的距離的排序情況，因此部分Hausdorff距離的計(jì)算存在一定的誤差，可能存在匹配失敗的情況。本文根據(jù)部分Hausdorff距離提出了一種改進(jìn)的Hausdorff距離。

　　設(shè)ai是集合A中的一個(gè)元素，則ai到集合B的距離為：

　　其中：k=f·N」，N表示集合A或者B中的個(gè)數(shù)，f∈[0.6，0.8]。通過(guò)平均值來(lái)計(jì)算dB（a）和dA（b），dB（a）可以有效地避免集合A中ai到集合B的最小距離的計(jì)算誤差，得到更加符合實(shí)際的最小距離，dA（b）同理。則h（A，B）、h（B，A）定義為：

　　其中，λ是最小距離閾值。當(dāng)d（x）的值大于λ時(shí)，E（x）的值為0。h（A，B）表示集合A到集合B中距離的平均值，h（B，A）同理；T（A）、T（B）分別表示集合A和B中的d（x）≤λ時(shí)點(diǎn)的個(gè)數(shù)。通過(guò)平均距離來(lái)計(jì)算h（A，B）、h（B，A）可以有效地消除樣本集中的異常點(diǎn)的影響和抑制樣本集中高斯噪聲。為了避免集合中僅僅少量點(diǎn)滿足最小距離原則，大多數(shù)的點(diǎn)被閾值剔除，而Hausdorff距離計(jì)算依然滿足匹配條件，但是匹配結(jié)果是不正確的，因此新的Hausdorff距離計(jì)算公式定義為：

　　式（10）中考慮了兩個(gè)集合中有效點(diǎn)的數(shù)量，這樣當(dāng)兩個(gè)集合中的有效點(diǎn)很少或者有不符合常理的相異度時(shí)，由于Hausdorff距離的值太多而不再考慮兩個(gè)集合的相似度的計(jì)算。這樣可以克服匹配過(guò)程中因?yàn)樵肼?、異常點(diǎn)、遮擋和陰影產(chǎn)生的影響。

2 人工蜂群算法搜索策略的圖像匹配

　　2.1 人工蜂群算法簡(jiǎn)介

　　ABC[12]是一種群體智能算法，該算法根據(jù)蜜蜂采蜜機(jī)制來(lái)求解最優(yōu)問(wèn)題?？蓪⒚鄯浞譃閭刹旆?、引領(lǐng)蜂、跟隨蜂三類。引領(lǐng)蜂和偵察蜂搜尋蜜源，跟隨蜂優(yōu)化蜜源。一只引領(lǐng)蜂對(duì)應(yīng)一個(gè)蜜源，尋找到蜜源后釋放并標(biāo)記蜜源信息，跟隨蜂根據(jù)式（7）選擇最大概率處的蜜源為標(biāo)記蜜源，并根據(jù)式（8）在標(biāo)記蜜源周圍搜索新蜜源。新蜜源與標(biāo)記蜜源進(jìn)行比較，選取較優(yōu)異的蜜源反復(fù)尋找更優(yōu)蜜源。若該蜜源經(jīng)過(guò)若干次優(yōu)化而不能再提高，引領(lǐng)蜂變成偵察蜂，根據(jù)式（9）隨機(jī)搜索新蜜源，直到在該區(qū)域中尋找到最優(yōu)蜜源或者放棄該區(qū)域。

　　設(shè)D為優(yōu)化問(wèn)題解的維數(shù)，蜜源i的隨機(jī)初始位置為做領(lǐng)域搜索并產(chǎn)生新解。

　　其中，id為新的蜜源位置，ij為蜜源的第j維位置，kj為隨機(jī)選擇的不等于i處蜜源的第j維，rand∈[-1，1]。

　　設(shè)蜂群數(shù)量為N，在t次迭代后蜜源位置信息為{xi（t）}，i=1，2，…，N。在該次搜索后，得到蜜源的適應(yīng)為fit（xi（t）），它被選擇的概率為：

　　其中，fit（xi（t））就是模板圖和待匹配子圖的Haursdorff距離的倒數(shù)。

　　設(shè)t為?茲i處蜜源最大迭代次數(shù)，若某個(gè)蜜源i經(jīng)過(guò)t次迭代搜索后沒(méi)有找到更優(yōu)質(zhì)的蜜源，該蜜源被遺棄，同時(shí)引領(lǐng)蜂就變?yōu)閭刹旆?，在整個(gè)搜索空間中根據(jù)式（9）隨機(jī)產(chǎn)生一個(gè)新解?茲j代替?茲i：

　　其中，j為新產(chǎn)生的蜜源位置，i為原蜜源位置，?茲k為隨機(jī)蜜源位置，i不等于k，rand∈[-1，1]。

　　為更直觀地描述ABC算法，圖1為算法的流程圖。

　　2.2 圖像匹配實(shí)現(xiàn)步驟

　?。?）參數(shù)初始化。設(shè)置蜜源（初始化）個(gè)數(shù)N，蜜源位置i最大迭代次數(shù)t，優(yōu)化過(guò)程最大迭代次數(shù)Cycle，蜜源解的維數(shù)D，匹配精度的閾值Th等參數(shù)的設(shè)置。

　?。?）對(duì)模板圖像和待匹配圖像用中值濾波對(duì)圖像濾波和用Canny算子作邊緣檢測(cè)，并轉(zhuǎn)換為二值圖像，分T和S。二值圖像中每個(gè)邊緣點(diǎn)用坐標(biāo)位置表示。

　　（3）為提高匹配速度，將圖像S劃分為4×5的區(qū)域，在每個(gè)區(qū)域產(chǎn)生一個(gè)初始解?茲i，其中i=1，2，…，N。根據(jù)式（4）計(jì)算T集合和Si集合的HD距離，即fit（xi（t）），并根據(jù)HD計(jì)算每個(gè)解的pro（i）。

　　（4）根據(jù)pro（i）的概率來(lái)進(jìn)行領(lǐng)域搜索，并根據(jù)式（8）產(chǎn)生新解?茲id，根據(jù)式（7）計(jì)算T集合和集合Sid的fit（xid（t）），若fit（xid（t））大于fit（xi（t）），則用?茲id的位置代替?茲i位置，fit（xid（t））的值代替fit（xi（t））的值，否則i、fit（xi（t））保持不變。

　?。?）若?茲i的位置經(jīng)過(guò)t次迭代搜索而沒(méi)有被優(yōu)化，則根據(jù)式（9）在S圖中隨機(jī)產(chǎn)生一個(gè)新解?茲j代替?茲i。

　?。?）重復(fù)步驟（2）~（5），直到達(dá)到匹配的閾值Th或者最大迭代次數(shù)Cycle，檢測(cè)是否達(dá)到最優(yōu)的匹配位置。

　　2.3 匹配成功與失敗判斷

　　設(shè)模板圖像T在待匹配圖像中的起始位置為m（i，j），匹配后的匹配位置為m（i′，j′），根據(jù)式（14）計(jì)算橫坐標(biāo)和縱坐標(biāo)的坐標(biāo)偏差d。

　　d=‖i-i′‖+‖j-j′‖（14）

　　根據(jù)式（15）判斷是否匹配成功。

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

　　3.1 實(shí)驗(yàn)結(jié)果

　　為了驗(yàn)證本文的算法，在CPU為Intel（R）Pentium（R）CPU G630@ 2.70 GHz，內(nèi)存2 GB的硬件設(shè)備上用MATLAB2010軟件仿真測(cè)試。在實(shí)驗(yàn)中，f的值為0.65，初始化種群個(gè)數(shù)N為20，最大迭代次數(shù)t為30，最大循環(huán)次數(shù)Cycle為400，閾值Th為10 000。第一組實(shí)驗(yàn)是以ABC為搜索策略，以傳統(tǒng)Hausdorff距離（HD-ABC）、部分Hausdorff距離（PHD-ABC）和改進(jìn)部分Hausdorff距離（SPHD-ABC）作為相似度量進(jìn)行仿真來(lái)測(cè)試算法的匹配率；第二組實(shí)驗(yàn)是以PHD作為相似度量，分別用逐行搜索的方法（PHD-PS）、遺傳算法的搜索策略（PHD-GA）、人工蜂群算法的搜索策略（PHD-ABC）進(jìn)行仿真來(lái)測(cè)試算法的搜索策略，每種算法進(jìn)行30次仿真測(cè)試。

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

　　本文實(shí)現(xiàn)了兩組對(duì)比實(shí)驗(yàn)。第一組實(shí)驗(yàn)測(cè)試了在ABC搜索策略不變的情況下，分別以HD、PHD和SPHD作為相似度量進(jìn)行仿真實(shí)驗(yàn)。圖2中（a）到（f）圖分別為基準(zhǔn)圖、加入高斯噪聲的基準(zhǔn)圖、加入椒鹽噪聲的基準(zhǔn)圖、縮放10%比例的基準(zhǔn)圖、順時(shí)針旋轉(zhuǎn)10°的基準(zhǔn)圖、g為匹配模板圖。算法匹配率如表1所示。由表1結(jié)果可看出，HD-ABC算法在圖像中加入高斯噪聲和椒鹽噪聲的情況下匹配率較低，其他情況下匹配度較高。但是該方法的平均匹配時(shí)間較長(zhǎng)，無(wú)法滿足實(shí)時(shí)性要求。PHD-ABC算法和SPHD-ABC算法在圖像中存在各種變換的情況下的匹配率相當(dāng)，但是SPHD-ABC算法平均匹配時(shí)間少于PHD-ABC算法的平均匹配時(shí)間。第二組實(shí)驗(yàn)測(cè)試了以PHD作為相似度量標(biāo)準(zhǔn)，分別用逐行搜索的方法（PHD-PS）、遺傳算法的搜索策略（PHD-GA）和人工蜂群算法的搜索策略（PHD-ABC）進(jìn)行仿真測(cè)試。圖3中（a）圖為旋轉(zhuǎn)的基準(zhǔn)圖、（b）圖為部分遮擋和旋轉(zhuǎn)的基準(zhǔn)圖、（c）圖為匹配模板圖。算法的搜索策略對(duì)比結(jié)果如表2所示。由表2可以看出，在相似度量準(zhǔn)則相同的情況下，三種搜索策略的匹配率基本相同，但是以ABC為搜索策略平均匹配時(shí)間遠(yuǎn)遠(yuǎn)小于逐行搜索平均匹配時(shí)間和優(yōu)于GA為搜索策略的平均匹配時(shí)間。

4 結(jié)論

　　部分Hausdorff距離在圖像匹配方面作為相似度量標(biāo)準(zhǔn)得到廣泛應(yīng)用。同時(shí)，ABC在求解最優(yōu)問(wèn)題具有計(jì)算簡(jiǎn)單，收斂時(shí)間短的優(yōu)勢(shì)。本文提出的簡(jiǎn)化部分Haursdorff距離的計(jì)算方法將簡(jiǎn)化的部分Haursdorff距離作為相似度量準(zhǔn)則并結(jié)合人工蜂群算法的搜索策略，實(shí)現(xiàn)了圖像匹配。實(shí)驗(yàn)結(jié)果表明，在圖像存在高斯噪聲、椒鹽噪聲、部分遮擋、小幅度旋轉(zhuǎn)的情況下，本文算法的平均匹配率不低于其他算法平均匹配率，但是平均匹配時(shí)間小于其他算法的平均匹配時(shí)間，增加了實(shí)時(shí)性的需求。該算法可移植應(yīng)用到嵌入式系統(tǒng)中。但是，人工蜂群算法在圖像匹配中也存在局部最優(yōu)的問(wèn)題，這需要進(jìn)一步研究。

　　參考文獻(xiàn)

　　[1] 熊凌.計(jì)算機(jī)視覺(jué)中的圖像匹配技術(shù)[J].湖北工業(yè)大學(xué)學(xué)報(bào)，2003，21（3）：171-173.

　　[2] 劉福新，杜世培，陳益強(qiáng).基于改進(jìn)Hausdorff距離的人臉匹配方法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（35）：169-171.

　　[3] 劉玉秋，王康平，刑玉梅.視頻流中的自適應(yīng)閾值模板匹配車輛檢測(cè)算法[J].吉林大學(xué)學(xué)報(bào)，2007，45（5）：791-794.

　　[4] 萬(wàn)力，武愛(ài)民.基于Hausdorff距離的行人跟蹤計(jì)數(shù)方法[J].信息技術(shù)，2007（8）：105-107.

　　[5] 莊志國(guó)，孫惠軍，董繼揚(yáng).基于角點(diǎn)檢測(cè)的圖像匹配算法及其在圖像拼接中的應(yīng)用[J]. 廈門(mén)大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，46（4）：501-505.

　　[6] 王振江，吳健，林方全.一種結(jié)合快速灰度投影與SSDA的圖像匹配方法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（33）：195-197.

　　[7] 黃濤，楊華高，胡水才.遺傳算法在相關(guān)匹配中的應(yīng)用研究[J].艦船電子工程，2010（3）：70-72.

　　[8] Zhou Ji， Shi Jiaoying. A robust algorithm for feature point matching[J] .Computers &Graphics， 2002；26（3）：429- 436.

　　[9] 劉佳，傅衛(wèi)平，王雯，等.基于改進(jìn)SIFT算法的圖像匹配[J].儀器儀表學(xué)報(bào)，2013；34（5）：1117-1111.

　　[10] 高晶，孫繼銀，劉婧.基于鄰域灰度信息的Hausdorff距離圖像匹配方法[J].計(jì)算機(jī)應(yīng)用，2011；31（3）：741-744.

　　[11] HUTTENLOCHER D P， KLANDERMAN G A， RUCKLIDGE W J.  Comparing images using the Hausdorff distance[J]. IEEE Transactions on Pattern Analysis and machine Intelligence，1993，15（9）：850-863.

　　[12] KARABOGA D， BASTURK B. On the performance of artificial bee colony algorithm[J]. Applied Soft Computing， 2008，8（1）：687-697.