改進Hausdorff距離和粒子群的圖像配準算法

胡明娣, 張中茂, 許天倚, 楊 潔

(西安郵電大學 通信與信息工程學院, 陜西 西安 710121)

圖像配準[1]是指在同一視覺系統(tǒng)中尋找一個最優(yōu)變換，使得在不同環(huán)境下獲得的參考圖像和待配準圖像高度吻合，對應特征點一一映射，即對齊的空間位置達到最佳。圖像配準技術已廣泛應用于導航及遙感圖像處理等領域。

圖像配準方法主要分為基于特征和區(qū)域兩種類型?；谔卣鼽c的圖像配準方法對噪聲及遮擋等干擾具有適應性強和數(shù)據(jù)計算量少等優(yōu)點，應用較為廣泛[2]。Hausdorff距離(Hausdorff distance,HD)[3]作為目前較為常用的圖像特征匹配度量，對圖像畸變適應性強，已取得較好的效果。基于代價函數(shù)(least trimmed square-Hausdorff，LTS-HD)距離的圖像配準算法[3]通過設定距離閾值去除噪聲點及錯誤距離，將改進的Hausdorff距離作為匹配測度，雖然取得了較高的配準率，但其閾值設置依靠經(jīng)驗，且復雜度較高。文獻[4]實現(xiàn)了對遮擋圖像自適應遮擋系數(shù)調(diào)整的Hausdorff距離測度，但是只適用于圖像中能提取大量特征點的圖像配準，不具有通用性?；诜指钅０寮訖郒ausdorff 距離矩陣的特征匹配算法[5]，在圖像內(nèi)容分布對比較明顯時取得了較高配準率，但模板加權系數(shù)很難確定。文獻[6]綜合考慮了遮擋系數(shù)、代價函數(shù)和出格點，改進了Hausdorff距離，并結合量子遺傳算法實現(xiàn)異源遮擋圖像配準，但其只適合激光圖像的配準，應用領域狹窄。

本文針對異源遙感圖像部分遮擋情況，利用尺度不變特征變換(scale-invariant feature transform,SIFT)算子[7]提取圖像的SIFT特征點作為圖像匹配特征空間，通過融合標準方差及部分平均改進Hausdorff距離作為相似性測度。同時，在粒子群(particle swarm optimization,PSO)算法[8]基礎上引入自適應參數(shù)和擾動機制增強算法的尋優(yōu)性能，并將該算法作為圖像配準的搜索策略，以期達到更好的配準效果。

1 改進的Hausdorff距離測度

1.1 Hausdorff距離

Hausdorff距離是一種模糊距離測度，用來衡量兩個有限點集之間的相似度。在圖像匹配識別中，將圖像作為一個點集，圖像的匹配程度則用兩個點集的相似程度表示。當兩點集之間Hausdorff距離越小時，兩點集的相似程度就越大。點集A={a1,a2,…,ap}到點集B={b1,b2,…,bq}的Hausdorff距離[9]定義為

式中：h(A,B)和h(B,A)分別表示點集A到點集B和點集B到點集A單向的Hausdorff距離；‖·‖為距離二范數(shù)。

1.2 改進的Hausdorff距離測度

部分Hausdorff距離(partial Hausdorff distance,PHD)[9]和平均Hausdorff距離 (modified Hausdorff distance,MHD)[10]對圖像噪聲具有較好地適應性。結合部分平均及排序思想，并融合標準方差，對Hausdorff距離進行改進，得到改進的部分均值Hausdorff距離 (improved partial modified hausdorff distance,IPMHD)，可定義為

式中：hz(A,B)為點集A到點集B有向距離由小到大排序后第z個Hausdorff距離值；hz(B,A)同理；S(A,B)和S(B,A)分別為兩點集之間的標準方差；NA和NB分別為點集A和點集B中特征點數(shù)目；f為遮擋比例；修正系數(shù)e通常取0.9[4]；q和p分別為點集A和點集B中實際計算所用特征點個數(shù)。

改進的IPMHD距離測度取值既不是點到集合最小距離，也不是最小距離中最大值，集合中所有點并未全部用于計算，剔除由孤立點造成的大距離，對剩下部分點排序，再采用部分點取平均。IPMHD考慮了遮擋對圖像匹配效果的影響，因而對遮擋及異常值適應性較強。

2 擾動機制的自適應參數(shù)PSO算法

2.1 基本PSO算法

(1)

(2)

2.2 Levy飛行機制

Levy飛行機制[11]使運動的軌跡具有隨機性，飛行中頻繁的短距離搜索可在當前最優(yōu)解周圍仔細搜尋，以此提高局部搜索能力；利用偶爾長距離的跳躍式搜索可擴增搜索范圍增強粒子全局搜索,防止粒子陷入局部最優(yōu)解。引入Levy飛行機制后，粒子的位置可更新[11]為

(3)

其中：?為步長控制量；L(β)為萊維隨機搜索路徑的隨機數(shù)。?和L(β)需滿足條件[11]為

其中：?0為常數(shù)，通常取0.01[11]；β取值范圍為[0，2]；xb為所有粒子中位置最優(yōu)處;μ和ν為服從標準正態(tài)分布隨機數(shù);Γ為標準Gamma函數(shù)。

2.3 Logistic混沌機制

Logistic混沌機制[12]使粒子處于混沌狀態(tài)，因而能擴大粒子的活動范圍。當粒子陷入局部最優(yōu)時，將Logistic混沌機制引入PSO算法，可增加粒子種群多樣性，從而避免算法過早收斂，達到尋優(yōu)目的。更新后的粒子位置表示式[12]為

(4)

其中：zk表示混沌域，且zk?(0.25,0.50,0.75)時系統(tǒng)處于混沌區(qū)域；α為Logistic參數(shù)，取值范圍為(0,4]，當α∈(3.569 945 6, 4)時，系統(tǒng)處于混沌狀態(tài)[12]；λ為擾動系數(shù)，一般取值為常數(shù)2[12]。

2.4 擾動機制的自適應參數(shù)PSO算法

改進的粒子群算法(improved particle swarm optimization,IPSO)通過動態(tài)改變PSO算法中慣性因子和學習因子，添加Levy飛行和Logistic混沌兩種擾動機制，擴展種群多樣性，避免陷入局部最優(yōu)。

慣性權重因子采用余弦變化[13]，可表示為

(5)

加速因子采用正弦函數(shù)變化[14]，可表示為

(6)

其中：ωmax=0.95,ωmin=0.40；g為總迭代次數(shù);r1和r2為0～1之間的隨機數(shù);c=1.5為基準值。PSO算法搜索前期，ω取值較大，加速因子c1大、c2小，有助于個體對全局學習；后期ω取值較小，加速因子c1小、c2大，有助于局部搜索時群體的學習。將式(5)和式(6)分別代入式(1),得到粒子更新速度為

(7)

3 基于IPMHD測度的IPSO圖像配準

將IPSO算法用于特征點匹配搜索策略，以IPMHD距離測度作為IPSO適應度函數(shù)，根據(jù)基準圖規(guī)格確定粒子活動邊界范圍。使粒子群在基準圖上隨機搜索，每次動態(tài)記錄粒子所在位置，并以該點位置為左上角截取尺寸大小與模板圖相同矩形區(qū)域，每次截取的矩形塊與模板圖之間的IPMHD距離為本文算法可行解，所有可行解中的最小的IPMHD即為最優(yōu)解，輸出最優(yōu)解值并結束算法?；贗PMHD測度的IPSO圖像配準算法的具體步驟如下。

步驟1設置初始參數(shù)，以IPMHD距離測度為IPSO算法適應度函數(shù)。

步驟2初始化粒子，計算粒子適應度函數(shù)值f(xi)，記錄個體最優(yōu)值pb及種群全局最優(yōu)值pg。

步驟3利用式(7)和式(2)更新粒子。

步驟5引入Logistic混沌擾動,利用式(4)對粒子位置更新。

步驟7引入Levy飛行擾動，利用式(3)更新粒子位置。

步驟8記錄粒子適應度值，并更新個體最優(yōu)值以及全局最優(yōu)值。

步驟9判斷是否達到最大迭代次數(shù)，若是，則輸出pg，停止迭代，算法結束；否則轉入步驟3，重復迭代。

4 實驗及結果分析

實驗在Win10環(huán)境下，CPU為Intel Core i7-8 700 K,主頻為3.7 GHz,內(nèi)存為16 GB的仿真平臺上，使用Matlab R2016a軟件進行仿真，驗證IPMHD距離的有效性和IPSO算法的配準性能。以IPMHD距離測度為IPSO搜索算法適應度函數(shù)，適應度函數(shù)值越小，粒子適應性更優(yōu)。

4.1 無遮擋條件下Hausdorff距離匹配性能對比

為了驗證IPMHD測度的有效性，分別使用兩組數(shù)據(jù)進行驗證。第1組數(shù)據(jù)為通過GoogleEarth下載的兩幅615×600像素的青海湖鳥瞰圖，如圖1所示；第2組數(shù)據(jù)為地理空間數(shù)據(jù)云下載的Landsat TM不同單波段異源圖像，其規(guī)格為620×600像素，并截取子圖150×150像素，如圖2所示。將IPMHD、HD、PHD 、MHD和LTS-HD等5種測度分別進行仿真匹配，比較其無遮擋條件下圖像配準成功率，結果如表1所示。

圖1 同源未遮擋遙感圖像配準結果

圖2 異源遙感圖像配準結果

距離測度實驗次數(shù)成功次數(shù)成功率/% HD503876 PHD504080 MHD504182 LTS-HD504188 IPMHD504590

由表1可以看出，HD距離測度匹配效果最差；PHD和MHD距離測度性能接近，較HD距離有一定提高；LTS-HD距離測度優(yōu)于HD、PHD和MHD距離測度；IPMHD距離測度匹配性能相較LTS-HD距離測度有小幅提升，性能最優(yōu)。

4.2 遮擋條件下各Hausdorff距離匹配性能對比

為驗證IPMHD算法對遮擋適應性及魯棒性，選取Landsat4-5 MSS多波段衛(wèi)星圖作為異源圖像對，圖像規(guī)格為761×748像素，如圖3所示，其中圖3(b)為圖3(a)中截取200×200像素子圖；圖3(d)為圖4(c)的遮擋40%，圖3(e)為圖3(b)和圖3(d)之間的配準。分別將IPMHD、HD、PHD 、MHD和LTS-HD等5種測度根據(jù)圖3中的配準圖進行不同比例遮擋實驗，5種Hausdorff距離測度在遮擋條件下的圖像匹配成功率如圖4所示。

圖3 異源遮擋遙感圖像配準結果

圖4 各距離測度在遮擋條件下的圖像匹配成功率

從圖4可以看出，各Hausdorff距離測度隨遮擋比例提高配準成功率呈下降趨勢。 HD、PHD和MHD在遮擋比例超過20%時，性能急劇下降；LTS-HD考慮了遮擋和異常值的影響，但遮擋適應性略低于IPMHD；IPMHD距離測度對遮擋的抗干擾性最強，當遮擋比例不超過20%時，仍有高達近80%成功匹配率，且對于排序靠前的前z個特征點，前40%的點對配準有用，因此可取IPMHD距離從小到大排序前40%特征點，以減少運算量。

4.3 配準算法比較分析

以IPMHD距離為相似性測度，分別將IPSO算法、文獻[13]、文獻[14]和文獻[15]中的改進PSO算法作為搜索策略進行配準實驗，尋優(yōu)結果如表2所示。

表2 不同搜索算法尋優(yōu)性能對比

由表2可以得出，文獻[13]和文獻[14]算法在性能及時間上比較接近，在耗時上優(yōu)于文獻[15]算法及IPSO算法，但尋優(yōu)結果穩(wěn)定性較差；IPSO耗時比文獻[15]算法長，可能是因為兩次擾動的隨機性耗時較長，但成功匹配次數(shù)最高，尋優(yōu)準確率高于其他3種算法，具有較強的實時性。

上述3組實驗均證明了在圖像受干擾時，IPMHD距離測度比其他改進的Hausdorff距離測度適應性更強，同時IPSO算法相比其他改進PSO算法尋優(yōu)性能更佳。

5 結語

以異源遙感圖像為背景，分別改進了Hausdorff距離測度和粒子群算法的圖像配準算法，將圖像的SIFT特征作為特征空間，融合部分平均和標準方差改進hausdorff距離，改善了Hausdorff距離易受干擾等缺點；選擇粒子群算法作為搜索策略，引入自適應變換參數(shù)改變慣性因子和學習因子，同時加入擾動機制改變粒子位置，防止了粒子陷于局部最優(yōu)。實驗結果表明，IPMHD距離測度比其他改進的Hausdorff距離測度適應性更強，IPSO算法相比其他改進PSO算法，尋優(yōu)性能更佳。該圖像配準算法具有較好地圖像配準效果。