改進(jìn)HD距離和遺傳算法的圖像匹配研究

劉晉勝，彭志平，周 靖

（廣東石油化工學(xué)院 計(jì)算機(jī)與電子信息學(xué)院，廣東 茂名 525000）

0 引言

圖像匹配是圖像理解和計(jì)算機(jī)視覺(jué)中的關(guān)鍵技術(shù)之一，在運(yùn)動(dòng)目標(biāo)跟蹤和識(shí)別、視頻運(yùn)動(dòng)估計(jì)和圖像檢索等領(lǐng)域有廣闊的應(yīng)用前景。隨著圖像清晰度的提高，圖像的微小細(xì)節(jié)變得清晰，對(duì)圖像匹配的要求進(jìn)一步提高，目前主要采用特征點(diǎn)匹配和模塊匹配等方法。在特征點(diǎn)匹配方面，Lowe提出的尺度不變特征變換（SIFT）方法匹配精度高[1]，對(duì)角度、尺度變化以及亮度變化都有較強(qiáng)的穩(wěn)健性[2]，但該方法需對(duì)圖像進(jìn)行高斯函數(shù)的多尺度變換及獲取圖像的極值點(diǎn)等復(fù)雜運(yùn)算，無(wú)法滿足高分辨力圖像及復(fù)雜場(chǎng)合的匹配精度要求，從而限制了SIFT算子應(yīng)用[3]。在模板匹配方法中，圖像匹配測(cè)度Hausdorff（HD）距離，能有效進(jìn)行圖像搜索，因具有計(jì)算快捷、不需點(diǎn)對(duì)點(diǎn)精確匹配和對(duì)局部非相似變形不敏感等優(yōu)點(diǎn)而得到廣泛應(yīng)用，但經(jīng)典HD距離采用的最大最小距離對(duì)出格噪聲和遮擋非常敏感，將導(dǎo)致距離計(jì)算的嚴(yán)重錯(cuò)誤[4]。許多研究者對(duì)其理論形式進(jìn)行了改進(jìn)，文獻(xiàn)[5-6]提出了部分HD距離、加權(quán)HD距離以及穩(wěn)健統(tǒng)計(jì)量LTS-HD等方法處理含有嚴(yán)重遮擋或退化問(wèn)題的圖像，能提高匹配的抗干擾能力，增強(qiáng)其在圖像匹配中的應(yīng)用，本文采用概率加權(quán)HD距離（Probability weighted Hausdoff，PWHD）作為算子，能準(zhǔn)確找到HD距離的中心，實(shí)現(xiàn)圖像精確匹配。

改進(jìn)HD距離實(shí)現(xiàn)圖像匹配取得了很好的效果，但該方法仍存在匹配計(jì)算量大等問(wèn)題，許多學(xué)者提出采用PSO算法[7]及遺傳算法等智能算法對(duì)其進(jìn)行優(yōu)化，以加快圖像匹配的速度。冷雪飛等人[8]采用遺傳算法的導(dǎo)航實(shí)時(shí)圖像匹配算法，能夠提高算法的抗干擾能力等性能，文獻(xiàn)[9-10]應(yīng)用改進(jìn)的遺傳算法提高圖像匹配的收斂速度，適用各種不同的圖像匹配場(chǎng)合，取得了較好的效果，但算法使用時(shí)，必須對(duì)不同的圖像設(shè)置特殊的參數(shù)，參數(shù)選擇對(duì)結(jié)果影響大，算法穩(wěn)健性較差。本文提出一種多策略的并行遺傳算法（Multi-strategy Parallel Genetic Al?gorithm，MSPGA），在并行遺傳算法上采用不同的算法策略，以增加群體的多樣性及算法的穩(wěn)健性，對(duì)概率加權(quán)HD距離進(jìn)行尋優(yōu)，實(shí)現(xiàn)圖像匹配。實(shí)驗(yàn)結(jié)果表明該算法有效，能滿足高分辨力圖像匹配要求。

1 改進(jìn)HD距離

HD距離是描述兩組點(diǎn)集之間相似程度的一種量度，它是兩個(gè)點(diǎn)集之間距離的一種定義形式：假設(shè)有兩組集合A=｛a1，a2，…，ap｝，B=｛b1，b2，…，bq｝，則這兩個(gè)點(diǎn)集合之間的HD距離[11]定義為

式中：‖·‖是點(diǎn)集A和點(diǎn)集B間的距離范式。式（1）稱為雙向HD距離的最基本形式，h（A，B）和h（B，A）分別稱為從A集合到B集合和從B集合到A集合的單向HD距離，取兩者中的較大者為兩集合的雙向HD距離H（A，B），度量了兩個(gè)點(diǎn)集間的最大不匹配程度。

HD距離對(duì)變形不敏感，對(duì)噪聲和圖像遮擋退化等比較敏感，文獻(xiàn)[8]采用加權(quán)平均的方式實(shí)現(xiàn)，取得了較好效果，但算法的權(quán)值由圖像的邊沿特征二值化分布情況來(lái)決定。本文提出PWHD，是針對(duì)兩張圖片的h（A，B）距離出現(xiàn)的概率來(lái)進(jìn)行加權(quán)處理。具體公式為

式中：加權(quán)函數(shù)w（a）是此距離的權(quán)值，由該距離出現(xiàn)的概率決定，概率越大，最后為該值的可能性越大，公式為

式中：na是點(diǎn)集A中特征點(diǎn)的總數(shù)，h（a，B）是點(diǎn)集A中的特征點(diǎn)a到點(diǎn)集B的距離，hi（a，b）是點(diǎn)集A中的特征點(diǎn)ai到點(diǎn)集B的特征點(diǎn)b距離，w（a）是此距離的權(quán)值，c是歸一化分段后進(jìn)行分段的參數(shù)，參數(shù)由模版大小確定。h（B，A）的公式同上。

PWHD能夠根據(jù)HD距離出現(xiàn)的概率來(lái)自適應(yīng)選擇加權(quán)參數(shù)w（a），通過(guò)對(duì)圖像匹配時(shí)距離數(shù)值的分析發(fā)現(xiàn)，此時(shí)的數(shù)值基本成單峰形式，采用概率加權(quán)將更加突出峰值數(shù)據(jù)，使PWHD距離不僅能改善噪聲點(diǎn)、漏檢點(diǎn)的影響，也克服了遮擋對(duì)圖像的影響。PWHD較平均HD距離（MHD）更能夠突出距離的相對(duì)值并有效去除干擾、突變等情況；較文獻(xiàn)[8]加權(quán)HD距離的獲取不用進(jìn)行圖像邊緣的預(yù)處理，實(shí)現(xiàn)方式簡(jiǎn)單，因此PWHD距離測(cè)度較原HD測(cè)度更具優(yōu)越性。但是不論是傳統(tǒng)的HD還是改進(jìn)的HD，在對(duì)高分辨力圖像進(jìn)行處理時(shí)計(jì)算量仍然較大，匹配速度有待提高，因此采用多策略并行的改進(jìn)遺傳算法進(jìn)行搜索，以期加快匹配速度。

2MSPGA實(shí)現(xiàn)

目前，多核處理器的廣泛適用使得算法的并行性研究不斷增多，并行遺傳算法的研究及實(shí)現(xiàn)越來(lái)越多，為提高遺傳算法在圖像匹配中不用根據(jù)每一幅圖片進(jìn)行修改算法參數(shù)，本文提出了一種穩(wěn)健性強(qiáng)、收斂性速度快的多策略并行遺傳算法（MSPGA）。

MSPGA采用并行算法的結(jié)構(gòu)，采用8個(gè)并行分支，并構(gòu)建8個(gè)不同的選擇、交叉、變異的遺傳操作為并行策略，采用是遺傳算法中較常見(jiàn)及經(jīng)典的操作方法，進(jìn)行圖像匹配，對(duì)應(yīng)如表1所示。

表1 算法策略配置

通過(guò)改變遺傳算子共可產(chǎn)生8個(gè)遺傳策略，算法結(jié)構(gòu)框圖如圖1所示。

在圖1中數(shù)據(jù)的遷移產(chǎn)生下一代群體，數(shù)據(jù)交換采用自適應(yīng)遷移。自適應(yīng)遷移策略中，各分支需要轉(zhuǎn)出的數(shù)據(jù)跟該分支中第t代個(gè)體的適應(yīng)度及前面未遷移代的個(gè)體適應(yīng)度之和成比例關(guān)系

式中：fi為個(gè)體的適應(yīng)度；fj為分支的適應(yīng)度；M為分支群體規(guī)模；Kj為第j個(gè)策略分支轉(zhuǎn)出數(shù)據(jù)數(shù)量；T為第j分支未遷移代數(shù)值，若當(dāng)代進(jìn)行了數(shù)據(jù)遷移設(shè)置T值為1，若未產(chǎn)生遷移T=T+1，k為遷移系數(shù)。k為針對(duì)轉(zhuǎn)移數(shù)據(jù)量、交換時(shí)間、群體多樣性等方面綜合考慮，再由數(shù)據(jù)遷移加速度比關(guān)系及系統(tǒng)采用的串行傳輸速率關(guān)系，取k值為4將得到較好的加速比。

由自適應(yīng)遷移策略計(jì)算可知，在算法策略針對(duì)該函數(shù)尋優(yōu)的過(guò)程中，分支適應(yīng)度大的群體轉(zhuǎn)出的最優(yōu)個(gè)體數(shù)量較多，實(shí)現(xiàn)不同分支、不同策略最優(yōu)個(gè)體的共享。在移民操作中完成自適應(yīng)遷移的移出操作后，在數(shù)據(jù)轉(zhuǎn)移空間將其他分支轉(zhuǎn)出的數(shù)據(jù)移入到各個(gè)分支，重新構(gòu)成新一代的子群體，作為下代父代群體，各子群體再次分別進(jìn)行算法選擇的操作。

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

3.1 圖像匹配步驟

在進(jìn)行多策略并行遺傳算法的PWHD實(shí)現(xiàn)時(shí)，由于PWHD不需對(duì)圖像進(jìn)行預(yù)處理，只需把H（A，B）放入適應(yīng)度函數(shù)計(jì)算過(guò)程，實(shí)現(xiàn)步驟：

1）對(duì)圖像進(jìn)行編碼，采用二進(jìn)制編碼形式，對(duì)匹配點(diǎn)的坐標(biāo)（x，y）進(jìn)行編碼，染色體的長(zhǎng)度可隨模板長(zhǎng)度的變化而變化，如一幅2592×1944像素的圖像，x用12位，y用11位二進(jìn)制碼表示，產(chǎn)生一個(gè)23位長(zhǎng)度的染色體。

2）隨機(jī)產(chǎn)生初始種群，每個(gè)分支各50個(gè)，共隨機(jī)產(chǎn)生400個(gè)位置（x，y）并把其轉(zhuǎn)化為基因串，作為初始種群。

3）對(duì)個(gè)體進(jìn)行適應(yīng)度函數(shù)值計(jì)算，適應(yīng)度是遺傳算法中個(gè)體進(jìn)化的驅(qū)動(dòng)力，是進(jìn)行自然選擇的唯一依據(jù)。因此設(shè)計(jì)如下適應(yīng)度函數(shù)

式中：Hx,y(A,B)是在坐標(biāo)（x，y）處模板和待匹配圖像兩點(diǎn)集的PWHD距離，加權(quán)分段參數(shù)c設(shè)為10。由該式可見(jiàn)，當(dāng)兩點(diǎn)集越匹配時(shí)，PWHD越小，適應(yīng)度值越大，表明個(gè)體越優(yōu)越。由于在完全匹配的理想情況下，PWHD的H（A，B）有可能等于0，為了避免分母為零，給數(shù)值進(jìn)行加1處理。

4）遺傳算法策略進(jìn)化。每一分支采用該分支中的選擇、交叉及變異，產(chǎn)生下一代群體。算法策略如表1所示，其中交叉算子中由于一點(diǎn)交叉對(duì)算子的改變影響比兩點(diǎn)交叉小，因此算法在交叉概率pc的設(shè)置采用一點(diǎn)交叉分支取為0.9，兩點(diǎn)交叉分支選取為0.8，來(lái)平衡兩種交叉方式對(duì)算子的影響。變異算子變異概率的大小對(duì)算法的收斂性有較大影響，針對(duì)圖像特征算法的不固定性，取普通變異概率為0.01，大變異概率為0.1。

5）最優(yōu)個(gè)體遷移。最優(yōu)個(gè)體自適應(yīng)遷移根據(jù)自適應(yīng)遷移公式（式（5））計(jì)算分支群體需當(dāng)代遷出的個(gè)體數(shù)量，在數(shù)據(jù)轉(zhuǎn)移空間將其他分支轉(zhuǎn)出的數(shù)據(jù)移入到各個(gè)分支，重新構(gòu)成新一代的子群體，作為下代群體。

6）算法終止。對(duì)該算法的終止條件跟簡(jiǎn)單遺傳算法相同，一是采用最大循環(huán)次數(shù)本文設(shè)為100次，當(dāng)次數(shù)到達(dá)最大循環(huán)次數(shù)時(shí)停止；二是采用閾值判斷，在算法中的適應(yīng)度超過(guò)閾值時(shí)停止，算法采用了多種遺傳策略，因此對(duì)滿足條件的判斷上采用了對(duì)單一種群判斷的策略，當(dāng)其中某一分支種群的群體適應(yīng)度達(dá)到設(shè)定閾值或遺傳代數(shù)達(dá)到上限時(shí)退出算法操作，得到算法最優(yōu)解。若兩個(gè)終止條件都未滿足，則轉(zhuǎn)回3）繼續(xù)執(zhí)行。

3.2 試驗(yàn)結(jié)果及分析

為了驗(yàn)證本文算法的有效性，利用Sony相機(jī)拍攝的500萬(wàn)像素圖像在計(jì)算機(jī)上進(jìn)行匹配仿真實(shí)驗(yàn)，算法采用Matlab語(yǔ)言編寫，在主頻為Intel Core4 2.8 GHz、內(nèi)存2 Gbyte的PC機(jī)上進(jìn)行算法測(cè)試。首先從不同場(chǎng)景下對(duì)本文算法進(jìn)行定量性能評(píng)估，并給出匹配結(jié)果；然后用本文算法與文獻(xiàn)[8]的算法進(jìn)行分析比較。

由于遺傳算法具有隨機(jī)性，為驗(yàn)證算法穩(wěn)健性，采用100組圖像進(jìn)行試驗(yàn)。對(duì)圖像在噪聲、旋轉(zhuǎn)以及抗遮擋方面進(jìn)行算法收斂速度、正確匹配次數(shù)和平均收斂時(shí)間進(jìn)行分析，驗(yàn)證算法中PWHD的抗干擾能力及MSPGA的穩(wěn)健性。選取其中一幅圖像加以說(shuō)明，原圖（圖2a）為2592×1944，匹配圖（圖2b）為256×256，圖像進(jìn)行原始匹配結(jié)果為圖2c。分別進(jìn)行加入隨機(jī)噪聲、匹配圖像旋轉(zhuǎn)10°及加入1/4圖像匹配區(qū)域遮擋等實(shí)驗(yàn)，各組實(shí)驗(yàn)100次，遺傳算法的收斂過(guò)程如圖3所示。

圖3為在各種情況下多策略并行遺傳算法的收斂分析，結(jié)果說(shuō)明算法對(duì)圖像中的噪聲、旋轉(zhuǎn)以及抗遮擋有效。在MSPGA收斂過(guò)程和結(jié)果進(jìn)行數(shù)據(jù)追蹤，8個(gè)分支中收斂速度和適應(yīng)度的值在不同圖像的情況下數(shù)值各異，在原圖匹配中，策略3的收斂速度快，在第60代即滿足收斂要求；加入隨機(jī)噪聲匹配中，分支5的收斂速度快，在第80代即滿足收斂要求；在匹配圖像旋轉(zhuǎn)的匹配中，策略4的收斂速度快，在第90代即滿足收斂要求；而區(qū)域遮擋匹配中，分支1的收斂速度快，在第90代即滿足收斂要求。

為了驗(yàn)證算法的匹配精度及速度，用相近的文獻(xiàn)[8]和[10]匹配算法對(duì)實(shí)驗(yàn)圖像進(jìn)行匹配，圖像匹配算法各進(jìn)行100次實(shí)驗(yàn)，匹配誤差為（0，0）時(shí)認(rèn)為解正確。匹配結(jié)果比較如表2所示。

表2 不同算法的匹配結(jié)果

由表2可見(jiàn)，本文算法在各種情況下收斂速度均較文獻(xiàn)[8]和[10]的算法快，正確率只在圖像旋轉(zhuǎn)時(shí)較文獻(xiàn)[8]算法低，表明本文算法在圖像匹配的速度及精度均較高。

4 結(jié)論

在對(duì)高分辨力圖像進(jìn)行匹配的過(guò)程中，本文提出了采用概率加權(quán)HD距離及多策略并行遺傳算法的方法，充分考慮了圖像匹配中噪聲干擾、旋轉(zhuǎn)及遮擋的情況，因此對(duì)HD距離進(jìn)行了研究和改進(jìn)，并考慮圖像匹配中數(shù)據(jù)容易陷入局部最優(yōu)，采用多策略并行遺傳算法加快匹配速度。實(shí)驗(yàn)結(jié)果表明提出的算法是有效、可行的。

[1] LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[2] 宋海華，邵志一.基于改進(jìn)型特征匹配的圖像拼接方案設(shè)計(jì)[J].電視技術(shù)，2008，32（2）：19-20.

[3] 楊濤，張艷寧，張秀偉，等.基于場(chǎng)景復(fù)雜度與不變特征的航拍視頻實(shí)時(shí)配準(zhǔn)算法[J].電子學(xué)報(bào)，2010，38（5）：1069-1077.

[4] Jordi Inglada，Alain Giros.On the possibility of automatic multisensor image registration[J].IEEE Transactions on Geoscience and Remote Sensing，2004，42（10）：2104-2120.

[5] 王靖，朱夢(mèng)宇，趙保軍，等.基于小波和改進(jìn)型Hausdorff距離的遙感圖像配準(zhǔn)方法[J].電子學(xué)報(bào)，2006，34（12）：2167-2169.

[6] 楊猛，潘泉，張紹武，等.基于定量定性互信息的多層次特征圖像匹配算法[J].中國(guó)圖象圖形學(xué)報(bào)，2010，15（9）：1376-1383.

[7] 陳颯，吳一全.基于Contourlet域Hausdorff距離和粒子群的多源遙感圖像匹配[J].測(cè)繪學(xué)報(bào)，2010，39（6）：599-604.

[8] 冷雪飛，劉建業(yè)，熊智.基于遺傳算法的導(dǎo)航實(shí)時(shí)圖像匹配算法[J].通信學(xué)報(bào)，2008，29（2）：17-21.

[9] 楊延西，劉丁，辛菁.模糊遺傳圖像相關(guān)匹配算法[J].儀器儀表學(xué)報(bào)，2005，26（11）：1166-1169.

[10] 龔志輝，張春美，孫雷，等.一種改進(jìn)Hausdorff距離和自適應(yīng)遺傳搜索的遙感目標(biāo)匹配方法[J].測(cè)繪學(xué)報(bào)，2009，34（5）：190-193.

[11] 孫曉路，丁曉青.基于邊緣特征的異質(zhì)圖像目標(biāo)配準(zhǔn)方法[J].電視技術(shù)，2010，34（12）：130-134.