摘 要： Hausdorff距離在圖像匹配領域廣泛應用。針對Hausdorff距離結合一些搜索策略的匹配算法實時性不高的問題，提出了一種基于改進Hausdorff距離和人工蜂群算法搜索策略的圖像快速匹配。首先提取模板圖像和匹配子圖的邊緣特征，然后計算的模板圖像和匹配子圖的Hausdorff距離作為兩者的相似度量標準，最后采用人工蜂群算法進行搜索匹配。實驗結果表明，該方法在不降低匹配率的情況下，縮短了匹配時間，能應用到嵌入式領域。
關鍵詞： 圖像匹配；Hausdorff距離；人工蜂群算法
0 引言
圖像匹配[1]是指根據模板圖像的特征信息在新的圖像中搜索相同或者相似特征信息的子圖像過程。圖像匹配技術廣泛應用于人臉識別[2]、運動目標識別與跟蹤[3]、行人檢測[4]、圖像拼接和融合[5]等領域。圖像匹配方法可分為三類：（1）基于圖像灰度信息的匹配方法[6]。該類方法易實現，一方面計算量較大，另一方面是當圖像信息缺乏時匹配容易失敗。（2）基于遺傳算法的圖像匹配[7]。該類方法完成匹配的概率比一般算法的概率要高，但可能會增加計算量。（3）基于圖像特征的匹配方法[8-9]。該類方法計算量小，速度較快，但是對特征信息較敏感。Hausdorff距離是一種常用作圖像匹配的相似度量距離參數，它不需要建立兩個點集中點的一一對應關系，對圖像的噪聲和小幅度旋轉具有魯棒性。目前基于Hausdorff距離的圖像匹配[10]方法很多，都是以提高匹配速度和匹配率為目的，有些效果并不理想。本文根據人工蜂群算法比遺傳算法、差分差異算法在優化問題方面的優越性，以及該算法操作簡單、運算快捷的優勢來進行圖片匹配的搜索，并以改進的部分Hausdorff距離作為相似度量來進行圖像匹配。實驗結果表明，該算法在匹配率不降低的情況下，減少了圖像匹配時間。
1 改進Hausdorff距離
Hausdorff距離[11]是定義在兩個點集上的最大最小距離。設兩個有限點集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之間的距離范數；h（A，B）表示點集A中所有點到點集B的最小距離的最大值；h（B，A）為反向Hausdorff距離。兩者的最大值構成了H（A，B）。
Hausdorff距離表示兩個點集之間的相異度。但是傳統的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中元素的個數。表示集合A中所有點到集合B中最小距離按從小到大排序后的第K個值，即為hk（A，B）。K值由f和q的積向下取整獲取，其中f∈[0，1]。部分Hausdorff能消除噪聲和異常點。但是部分Hausdorff距離計算只考慮集合A到集合B的距離，而沒有考慮集合A中每一個點到集合B的距離的排序情況，因此部分Hausdorff距離的計算存在一定的誤差，可能存在匹配失敗的情況。本文根據部分Hausdorff距離提出了一種改進的Hausdorff距離。
設ai是集合A中的一個元素，則ai到集合B的距離為：
其中：k=f·N」，N表示集合A或者B中的個數，f∈[0.6，0.8]。通過平均值來計算dB（a）和dA（b），dB（a）可以有效地避免集合A中ai到集合B的最小距離的計算誤差，得到更加符合實際的最小距離，dA（b）同理。則h（A，B）、h（B，A）定義為：
其中，λ是最小距離閾值。當d（x）的值大于λ時，E（x）的值為0。h（A，B）表示集合A到集合B中距離的平均值，h（B，A）同理；T（A）、T（B）分別表示集合A和B中的d（x）≤λ時點的個數。通過平均距離來計算h（A，B）、h（B，A）可以有效地消除樣本集中的異常點的影響和抑制樣本集中高斯噪聲。為了避免集合中僅僅少量點滿足最小距離原則，大多數的點被閾值剔除，而Hausdorff距離計算依然滿足匹配條件，但是匹配結果是不正確的，因此新的Hausdorff距離計算公式定義為：
式（10）中考慮了兩個集合中有效點的數量，這樣當兩個集合中的有效點很少或者有不符合常理的相異度時，由于Hausdorff距離的值太多而不再考慮兩個集合的相似度的計算。這樣可以克服匹配過程中因為噪聲、異常點、遮擋和陰影產生的影響。
2 人工蜂群算法搜索策略的圖像匹配
2.1 人工蜂群算法簡介
ABC[12]是一種群體智能算法，該算法根據蜜蜂采蜜機制來求解最優問題。可將蜜蜂分為偵察蜂、引領蜂、跟隨蜂三類。引領蜂和偵察蜂搜尋蜜源，跟隨蜂優化蜜源。一只引領蜂對應一個蜜源，尋找到蜜源后釋放并標記蜜源信息，跟隨蜂根據式（7）選擇最大概率處的蜜源為標記蜜源，并根據式（8）在標記蜜源周圍搜索新蜜源。新蜜源與標記蜜源進行比較，選取較優異的蜜源反復尋找更優蜜源。若該蜜源經過若干次優化而不能再提高，引領蜂變成偵察蜂，根據式（9）隨機搜索新蜜源，直到在該區域中尋找到最優蜜源或者放棄該區域。
設D為優化問題解的維數，蜜源i的隨機初始位置為做領域搜索并產生新解。
其中，id為新的蜜源位置，ij為蜜源的第j維位置，kj為隨機選擇的不等于i處蜜源的第j維，rand∈[-1，1]。
設蜂群數量為N，在t次迭代后蜜源位置信息為{xi（t）}，i=1，2，…，N。在該次搜索后，得到蜜源的適應為fit（xi（t）），它被選擇的概率為：
其中，fit（xi（t））就是模板圖和待匹配子圖的Haursdorff距離的倒數。
設t為?茲i處蜜源最大迭代次數，若某個蜜源i經過t次迭代搜索后沒有找到更優質的蜜源，該蜜源被遺棄，同時引領蜂就變為偵察蜂，在整個搜索空間中根據式（9）隨機產生一個新解?茲j代替?茲i：
其中，j為新產生的蜜源位置，i為原蜜源位置，?茲k為隨機蜜源位置，i不等于k，rand∈[-1，1]。
為更直觀地描述ABC算法，圖1為算法的流程圖。
2.2 圖像匹配實現步驟
（1）參數初始化。設置蜜源（初始化）個數N，蜜源位置i最大迭代次數t，優化過程最大迭代次數Cycle，蜜源解的維數D，匹配精度的閾值Th等參數的設置。
（2）對模板圖像和待匹配圖像用中值濾波對圖像濾波和用Canny算子作邊緣檢測，并轉換為二值圖像，分T和S。二值圖像中每個邊緣點用坐標位置表示。
（3）為提高匹配速度，將圖像S劃分為4×5的區域，在每個區域產生一個初始解?茲i，其中i=1，2，…，N。根據式（4）計算T集合和Si集合的HD距離，即fit（xi（t）），并根據HD計算每個解的pro（i）。
（4）根據pro（i）的概率來進行領域搜索，并根據式（8）產生新解?茲id，根據式（7）計算T集合和集合Sid的fit（xid（t）），若fit（xid（t））大于fit（xi（t）），則用?茲id的位置代替?茲i位置，fit（xid（t））的值代替fit（xi（t））的值，否則i、fit（xi（t））保持不變。
（5）若?茲i的位置經過t次迭代搜索而沒有被優化，則根據式（9）在S圖中隨機產生一個新解?茲j代替?茲i。
（6）重復步驟（2）~（5），直到達到匹配的閾值Th或者最大迭代次數Cycle，檢測是否達到最優的匹配位置。
2.3 匹配成功與失敗判斷
設模板圖像T在待匹配圖像中的起始位置為m（i，j），匹配后的匹配位置為m（i′，j′），根據式（14）計算橫坐標和縱坐標的坐標偏差d。
d=‖i-i′‖+‖j-j′‖（14）
根據式（15）判斷是否匹配成功。
3 實驗結果與分析
3.1 實驗結果
為了驗證本文的算法，在CPU為Intel（R）Pentium（R）CPU G630@ 2.70 GHz，內存2 GB的硬件設備上用MATLAB2010軟件仿真測試。在實驗中，f的值為0.65，初始化種群個數N為20，最大迭代次數t為30，最大循環次數Cycle為400，閾值Th為10 000。第一組實驗是以ABC為搜索策略，以傳統Hausdorff距離（HD-ABC）、部分Hausdorff距離（PHD-ABC）和改進部分Hausdorff距離（SPHD-ABC）作為相似度量進行仿真來測試算法的匹配率；第二組實驗是以PHD作為相似度量，分別用逐行搜索的方法（PHD-PS）、遺傳算法的搜索策略（PHD-GA）、人工蜂群算法的搜索策略（PHD-ABC）進行仿真來測試算法的搜索策略，每種算法進行30次仿真測試。
3.2 實驗結果分析
本文實現了兩組對比實驗。第一組實驗測試了在ABC搜索策略不變的情況下，分別以HD、PHD和SPHD作為相似度量進行仿真實驗。圖2中（a）到（f）圖分別為基準圖、加入高斯噪聲的基準圖、加入椒鹽噪聲的基準圖、縮放10%比例的基準圖、順時針旋轉10°的基準圖、g為匹配模板圖。算法匹配率如表1所示。由表1結果可看出，HD-ABC算法在圖像中加入高斯噪聲和椒鹽噪聲的情況下匹配率較低，其他情況下匹配度較高。但是該方法的平均匹配時間較長，無法滿足實時性要求。PHD-ABC算法和SPHD-ABC算法在圖像中存在各種變換的情況下的匹配率相當，但是SPHD-ABC算法平均匹配時間少于PHD-ABC算法的平均匹配時間。第二組實驗測試了以PHD作為相似度量標準，分別用逐行搜索的方法（PHD-PS）、遺傳算法的搜索策略（PHD-GA）和人工蜂群算法的搜索策略（PHD-ABC）進行仿真測試。圖3中（a）圖為旋轉的基準圖、（b）圖為部分遮擋和旋轉的基準圖、（c）圖為匹配模板圖。算法的搜索策略對比結果如表2所示。由表2可以看出，在相似度量準則相同的情況下，三種搜索策略的匹配率基本相同，但是以ABC為搜索策略平均匹配時間遠遠小于逐行搜索平均匹配時間和優于GA為搜索策略的平均匹配時間。
4 結論
部分Hausdorff距離在圖像匹配方面作為相似度量標準得到廣泛應用。同時，ABC在求解最優問題具有計算簡單，收斂時間短的優勢。本文提出的簡化部分Haursdorff距離的計算方法將簡化的部分Haursdorff距離作為相似度量準則并結合人工蜂群算法的搜索策略，實現了圖像匹配。實驗結果表明，在圖像存在高斯噪聲、椒鹽噪聲、部分遮擋、小幅度旋轉的情況下，本文算法的平均匹配率不低于其他算法平均匹配率，但是平均匹配時間小于其他算法的平均匹配時間，增加了實時性的需求。該算法可移植應用到嵌入式系統中。但是，人工蜂群算法在圖像匹配中也存在局部最優的問題，這需要進一步研究。
參考文獻
[1] 熊凌.計算機視覺中的圖像匹配技術[J].湖北工業大學學報，2003，21（3）：171-173.
[2] 劉福新，杜世培，陳益強.基于改進Hausdorff距離的人臉匹配方法[J].計算機工程與應用，2007，43（35）：169-171.
[3] 劉玉秋，王康平，刑玉梅.視頻流中的自適應閾值模板匹配車輛檢測算法[J].吉林大學學報，2007，45（5）：791-794.
[4] 萬力，武愛民.基于Hausdorff距離的行人跟蹤計數方法[J].信息技術，2007（8）：105-107.
[5] 莊志國，孫惠軍，董繼揚.基于角點檢測的圖像匹配算法及其在圖像拼接中的應用[J]. 廈門大學學報（自然科學版），2007，46（4）：501-505.
[6] 王振江，吳健，林方全.一種結合快速灰度投影與SSDA的圖像匹配方法[J].計算機工程與應用，2011，47（33）：195-197.
[7] 黃濤，楊華高，胡水才.遺傳算法在相關匹配中的應用研究[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] 劉佳，傅衛平，王雯，等.基于改進SIFT算法的圖像匹配[J].儀器儀表學報，2013；34（5）：1117-1111.
[10] 高晶，孫繼銀，劉婧.基于鄰域灰度信息的Hausdorff距離圖像匹配方法[J].計算機應用，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.