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

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

0 引言

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

1 改進Hausdorff距離

　　Hausdorff距離[11]是定義在兩個點集上的最大最小距離。設(shè)兩個有限點集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‖表示點a和b之間的距離范數(shù)；h（A，B）表示點集A中所有點到點集B的最小距離的最大值；h（B，A）為反向Hausdorff距離。兩者的最大值構(gòu)成了H（A，B）。

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

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

　　其中：

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

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

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

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

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

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

　　2.1 人工蜂群算法簡介

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

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

　　其中，id為新的蜜源位置，ij為蜜源的第j維位置，kj為隨機選擇的不等于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ù)，若某個蜜源i經(jīng)過t次迭代搜索后沒有找到更優(yōu)質(zhì)的蜜源，該蜜源被遺棄，同時引領(lǐng)蜂就變?yōu)閭刹旆?，在整個搜索空間中根據(jù)式（9）隨機產(chǎn)生一個新解?茲j代替?茲i：

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

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

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

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

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

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

　　（4）根據(jù)pro（i）的概率來進行領(lǐng)域搜索，并根據(jù)式（8）產(chǎn)生新解?茲id，根據(jù)式（7）計算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)過t次迭代搜索而沒有被優(yōu)化，則根據(jù)式（9）在S圖中隨機產(chǎn)生一個新解?茲j代替?茲i。

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

　　2.3 匹配成功與失敗判斷

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

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

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

3 實驗結(jié)果與分析

　　3.1 實驗結(jié)果

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

　　3.2 實驗結(jié)果分析

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

4 結(jié)論

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

　　參考文獻

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

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

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

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

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

　　[6] 王振江，吳健，林方全.一種結(jié)合快速灰度投影與SSDA的圖像匹配方法[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)平，王雯，等.基于改進SIFT算法的圖像匹配[J].儀器儀表學(xué)報，2013；34（5）：1117-1111.

　　[10] 高晶，孫繼銀，劉婧.基于鄰域灰度信息的Hausdorff距離圖像匹配方法[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.