基于Contourlet域Hausdorff距離和粒子群的多源遙感圖像匹配

陳 颯,吳一全

南京航空航天大學信息科學與技術學院,江蘇南京210016

基于Contourlet域Hausdorff距離和粒子群的多源遙感圖像匹配

陳 颯,吳一全

南京航空航天大學信息科學與技術學院,江蘇南京210016

為進一步提高多源遙感圖像的匹配精度和運算效率,提出一種利用Contourlet變換、Hausdorff距離和改進粒子群的遙感圖像匹配算法。在分別對目標圖像和參考圖像進行Contourlet分解的基礎上,采用小波模極大值法提取低頻圖像的邊緣信息,以LTS-HD作為圖像匹配的相似性度量準則,并利用一種帶極值擾動的簡化粒子群優化算法對低頻邊緣圖像進行匹配操作,得到粗匹配點;然后根據粗匹配點的位置反演計算到原始圖像,進行精匹配,最終實現全分辨率情況下遙感圖像的匹配。試驗結果表明,該算法與目前常用的遙感圖像匹配算法相比,不僅具有更高的匹配精度和運算效率,同時該算法對噪聲、不同程度的遮擋具有較強的穩健性。

多源遙感圖像匹配;Contourlet變換;Hausdorff距離;粒子群優化

1 引 言

圖像匹配是信息處理領域中一項非常重要的技術,它可以代替作業人員實現地面模型數據采集的自動化,并在計算機視覺、航空攝影測量、飛行器巡航制導等領域得到了廣泛的應用。在遙感圖像處理方面,圖像匹配技術可以應用于遙感圖像的定位和配準[1-3],它通過比較目標圖像和參考圖像之間的相似性來確定目標圖像在參考圖像中的位置。目前,圖像匹配算法大致可分為兩類:基于灰度的匹配和基于特征的匹配。由于遙感圖像往往是不同時間、不同波段或者不同傳感器拍攝的圖像,這種差異導致圖像的成像條件發生改變,從而使得圖像間灰度相差很大,因此基于灰度的匹配方法經常失效。而基于特征的匹配方法在提取特征的過程中,可以減少噪聲的影響,對灰度變化、圖像形變等都有較好的適應能力,所以適合多源遙感圖像間的匹配。常見的特征匹配方法通常是尋找特征之間的一一對應關系,計算對應特征之間的相似度量以得到圖像之間的變換關系。這些方法中特征對的建立較為復雜,當特征數目超過一定數量時,計算時間將成倍地增加,并且當特征的抽取過程中產生虛假特征或者丟失特征時,基于一一對應關系的匹配算法往往很難得到正確的結果。

Hausdorff距離是點特征匹配的一種有效方法,它不需要建立點與點之間的一一對應關系,只是計算兩個點集之間的相似程度,所以可以有效地處理很多特征點的情況。其中,基于 Hausdorff距離的邊緣圖像匹配算法因其計算的簡便性而得到廣泛的應用[4-5],如部分 Hausdorff距離算法,平均 Hausdorff距離算法等。文獻[6]結合部分和平均Hausdorff距離兩種方法提出了一種基于穩健統計量L TS的 Hausdorff距離(leasttrimmed-squares Hausdorff distance,L TS-HD)。這種方法將由噪聲干擾或遮擋而產生大距離剔除,從而很大程度上減小了噪聲和孤立點對精度和穩定性的影響,且在實際匹配過程中,使用這種距離作為相似度準則能夠很好地保證圖像匹配的精度。

另一方面,采用基于 Hausdorff距離的圖像特征匹配算法時,必須通過窮盡搜索的方法,逐一比較每個可能匹配點上的 Hausdorff距離值。因此當目標圖像為較大區域時,計算量就急劇增大。近年來陸續有人提出改進的匹配算法。這些算法或者通過縮小搜索空間來減少計算量,如借助小波變換的多分辨率特性,由粗到細逐層匹配[7-8];或者采用各種優化算法,其中最典型的是遺傳算法[9-11],通過非遍歷尋優搜索策略來加快匹配速度。然而前者常用的小波變換在方向性和各向異性上存在缺陷,不能很好地表示二維圖像中的方向信息。近年提出的Contourlet變換[12]具有多分辨率、局部定位、多方向性、近鄰界采樣和各向異性等性質,比小波變換更適合分析二維圖像中的邊緣特征。因此在圖像匹配中可以考慮利用Contourlet變換的有關特性。各種優化算法中,常用的遺傳算法局部尋優能力較差,參數選擇對結果影響大。而粒子群優化算法(particle swarm optimization,PSO)[13]通過群體中粒子的學習與更新實現群體智能優化搜索。與遺傳算法相比,簡單、易實現,需調整的參數少,是一種高效的并行搜索算法。利用PSO來搜索最佳匹配點,可望大大減少運算時間。

鑒于上述原因,本文提出一種基于Contourlet變換、Hausdorff距離和改進粒子群的遙感圖像匹配算法。該算法主要包含以下三個方面:①將目標圖像和參考圖像進行Contourlet分解,對低分辨率圖像進行粗匹配,根據粗匹配點的位置反演計算到原始圖像,進行精匹配;②在匹配時利用一種改進的帶極值擾動的簡化粒子群算法來搜索最佳匹配位置,進一步提高運算速度;③采用小波模極大值法提取圖像邊緣信息,以LTS-HD作為圖像匹配的相似性度量準則,從而提高算法穩健性。

2 Contourlet變換、粒子群和 H ausdorff距離的基本原理

2.1 Contourlet變換

離散Contourlet變換也稱塔形方向濾波器組(pyramidal direction filter bank,PDFB),它由子帶分解和方向變換兩個步驟實現。首先用拉普拉斯塔形濾波器對圖像進行多尺度分解,以“捕獲”奇異點;然后由方向濾波器組將奇異點連成線形結構,從而捕捉圖像中的輪廓。圖1給出了Contourlet變換的濾波器組結構,原始圖像經Contourlet分解,得到一個低通圖像和分布于多尺度多方向上的高頻分量。

圖1 Contourlet變換的濾波器組Fig.1 Contourlet filter bank

2.2 基本粒子群優化算法(bPSO)

設在n維搜索空間中,每個粒子i有位置Xi= (Xi1,Xi2,…,Xin)和速度Vi=(Vi1,Vi2,…,Vin),前者表示問題的解,對應的目標函數值作為評價該粒子優劣程度的適應度;后者表示粒子從當前位置移動到下一個位置的速度大小。首先初始化一個具有隨機位置和速度的粒子群,然后通過迭代的方式在解空間中尋找最優解。假設在第t次迭代時刻,粒子i所找到的最優解為pbesti(t),稱為個體極值;整個粒子群當前所找到的最優解為gbest(t),稱為全局極值。在t+1次迭代時刻,粒子i按下式更新其速度和位置

其中,t表示當前迭代次數;學習因子c1=c2=2; r1、r2是均勻分布在(0,1)上的隨機數;w是慣性因子,一般將w設為隨迭代次數t線性遞減,即

其中,wmax和wmin分別表示最大和最小慣性因子, tmax表示總的迭代次數。在迭代更新過程中,粒子每一維的速率限制成Vi∈[Vmin,Vmax],粒子的位置限制在允許范圍之內,最后輸出的 gbest為全局最優解。

2.3 H ausdorff距離

Hausdorff距離主要用于衡量兩個點集之間的不匹配程度。給定兩個有限點集 A={a1,a2,…,ap}和B={b1,b2,…,bq},兩者之間的 Hausdorff距離定義為

3 基于Contourlet域 H ausdorff距離和改進粒子群的遙感圖像匹配算法實現過程

3.1 改進的帶極值擾動的簡化粒子群優化算法(mtsPSO)

通過群體中粒子的學習與更新產生的群體智能優化搜索,采用位置-速度模型動態跟蹤當前的搜索情況以調整搜索策略。然而基本粒子群優化算法搜索過程中容易陷入局部極值束縛,難以保證收斂到全局最優解。此外還存在后期收斂速度慢和精度低等缺點。為此對上述基本粒子群算法進行改進[14],采用一種改進的帶極值擾動簡化粒子群優化算法(mtsPSO)。

mtsPSO算法去掉了bPSO進化方程的粒子速度項而使原來的二階微分方程簡化為一階微分方程,僅由粒子位置控制更新過程,避免了由粒子速度項引起的粒子發散而導致后期收斂速度變慢和精度低的問題,同時通過增加極值擾動算子加快粒子跳出局部極值點而繼續優化,從而使粒子群優化算法更為實用。mtsPSO算法中粒子的更新過程為

U(0,1)表示均勻分布在(0,1)上的隨機數。

考慮到較大的慣性權重因子有利于提高算法的全局搜索能力,較小的慣性權值可增強算法的局部能力,本文的mtsPSO算法對帶極值擾動簡化粒子群優化算法作了修改,采用下列慣性權值遞減策略[15],使其自適應達到最佳平衡慣性因子,如式(6)所示

其中,t表示當前迭代次數;tmax表示總迭代次數。

3.2 改進型H ausdorff距離(G-HD)

L TS-HD的有向 Hausdorff距離定義為

其中,dB(a)(i)表示序列(dB(a)(1)≤dB(a)(2)≤…≤dB(a)(NA))中的第 i個距離值。試驗中采用的代價函數ρ定義為

H=h×NA,NA為集合A中點的個數。τ是用來剔除外部點的閾值,這樣產生較大距離的外部點就被丟棄了。由于嵌入了求平均值的運算,該算法對于參數τ和h的變化不敏感,所以對于被遮掩或因噪聲而退化的目標配準效果也較好。

3.3 算法實現步驟

現利用改進的帶極值擾動粒子群優化算法在Contourlet域尋找匹配點,實現兩幅遙感圖像的匹配,具體過程如下:

1.對目標圖像和參考圖像分別進行 Contourlet變換,得到兩組Contourlet分解系數。分解層數L的選取由目標圖像決定,分解后低頻圖像不應太小,否則所含信息太少易造成誤匹配;

2.分別提取目標和參考圖像低頻部分的邊緣圖像,記為target_E和original_E。本文采用小波模極大值法提取邊緣信息;

3.在original_E上初始化粒子群:隨機生成m個粒子,位置偏移量Δx、Δy作為粒子的位置,設置 tmax、wstart、wend、T0、Tg,同時令 t=0,t0=0, T0=0;

4.以target_E和original_E的L TS-HD作為適應度函數,由式(4)、(7)、(8)求各粒子的適應度 f itp,即 Hausdorff距離;

5.更新個體極值 pbesti(t)、全局極值gbestL(t); 6.根據粒子群體狀態按照式(5)更新粒子;

7.迭代:令t=t+1,返回步驟4直至最大迭代次數或者滿足給定的精度;

8.根據迭代后最優解所在的位置 gbestL,輸出低頻部分的最佳偏移位置ΔxL、ΔyL,即粗匹配點;

9.將粗匹配點的位置返演計算到原始圖像,并在大小為10個像素的鄰域范圍內通過LTS-HD算法計算得到精匹配結果,即最終匹配結果。

4 試驗結果與分析

針對200組遙感圖像進行了試驗,現選取其中三組遙感圖像加以說明,分別是256×256的可見光圖像(圖2(a))與61×61的紅外圖像(圖2(b)); 256×256的SAR圖像(圖2(d))與72×92的可見光圖像(圖2(e));256×256的紅外圖像(圖2(g))與95×95的可見光圖像(圖2(h))。采用本文提出的基于Contourlet域 Krawtchouk矩和帶極值擾動的簡化粒子群匹配算法,在Intel Pentium4 2.78 GHz CPU、512 M內存、Matlab7.1環境中運行,匹配結果如圖2所示。其中,mtsPSO算法的主要參數: wstart=0.95,wend=0.4,m=100,tmax=500。

圖2 三組試驗圖像Fig.2 Images of the three experiments

4.1 取不同分解層L的試驗結果比較

分解層L的取值應由目標圖像的大小決定。分別對以上三組圖像進行試驗,程序運行1次,結果如表1所示。表中坐標均為匹配位置左上角坐標。

表1 取不同分解層時的匹配結果Tab.1 Matching results for different decomposition levels

可以看出,當L取值偏小時,耗時較長且有一定的匹配誤差;L越大耗時越短,當L=2時,匹配誤差為(0,0);但當L偏大時,分解層數變多,低頻部分信息量變少,也易造成匹配誤差或者不匹配。

4.2 不同方法的試驗結果比較

為了便于比較,采用了以下幾種常見的匹配算法對試驗圖像進行匹配:(a)基于灰度相關的圖像匹配算法;(b)基于 HD和遺傳算法的圖像匹配算法;(c)基于 HD和 PSO的圖像匹配算法; (d)本文提出的基于 Contourlet變換、L TS-HD和mtsPSO的圖像匹配算法。其中分解層數取L=2,每種算法重復運行100次,當且僅當匹配誤差為(0,0)時認為解正確,上述不同算法的匹配結果比較如表2所示。

表2 不同算法的匹配結果Tab.2 Matching results of different algorithms

由于遺傳算法、粒子群算法等這些尋優算法所求得的解具有一定的不確定性,多次運行程序可以發現:算法(a)除試驗1(灰度相差不大)外,正確率都為零。這是因為SAR、紅外和可見光等遙感圖像的成像原理不同,使得圖像之間灰度相差很大,在這種情況下,圖像的灰度線性關系不成立,利用傳統的互相關不能搜索到精確的匹配點。相比算法(a),算法(b)、(c)采用 HD作為相似性度量準則,分別以遺傳、PSO加快搜索速度,一定程度上克服了灰度引起的誤匹配。其中(b)的耗時相對較長,這是因為遺傳算法較粒子群算法多了交叉、變異等步驟,因此運行速度較(c)慢。然而算法(c)采用傳統的 Hausdorff距離作為相似性測度,因此算法存在對斑點噪聲干擾敏感、匹配精度低等問題;且由于搜索范圍較大,PSO參數相對設置較高,計算量仍然偏大。算法(d)采用基于Contourlet域L TS-HD和mtsPSO的匹配算法,一方面加快了匹配速度,另一方面也提高了匹配精度,正確率大于其他三種方法,穩定性最好,計算速度最快。

4.3 算法的抗噪性能

在給出的三組試驗圖像中加入均值為0,方差為0.01的高斯噪聲,利用本文提出的算法進行匹配,結果如圖3所示。

圖3 三組加噪的試驗圖像Fig.3 Noisy images of the three experiments

進行了多次試驗,匹配結果分別為(167, 150)、(126,12)、(115,46),匹配誤差都為(0,0)。可以看出,采用本文提出的算法對帶噪聲的圖像進行匹配時,仍能得到精確的匹配結果,且目標圖像越大,其對噪聲的抑制能力越強。原因是圖像越大,參與匹配運算的圖像信息量越大,從而增強了算法對噪聲的抑制能力。

4.4 算法的抗遮擋能力

在給出的三組試驗圖像中分別進行不同程度的遮擋,利用本文提出的算法進行匹配,結果如圖4所示。

圖4 三組遮擋的試驗圖像Fig.4 Partially occluded images of the three experiments

匹配結果分別為(167,150)、(126,12)、(115, 38),僅最后一組試驗有(0,-8)的匹配誤差,因此,本文提出的算法具有一定的抗遮擋能力。

5 結 論

本文提出了一種利用 Contourlet變換、Hausdorff距離和改進粒子群的遙感圖像匹配算法。在對目標圖像和參考圖像進行 Contourlet分解的基礎上,采用小波模極大值法提取低頻圖像的邊緣信息,以L TS-HD作為圖像匹配的相似性度量準則,并利用一種帶極值擾動的簡化粒子群優化算法對低頻邊緣圖像進行匹配操作,得到粗匹配點,然后根據粗匹配點的位置反演計算到原始圖像,進行精匹配。試驗選取了不同分解層數、不同方法對結果進行比較。結果表明,該算法與目前常用的匹配算法相比,不僅具有更高的匹配精度和運算效率,同時該算法對噪聲、不同程度的遮擋具有一定的穩健性。

[1] BENTOUTOU Y,TALEB N,KPALMA K,RONSIN J. An Automatic Image Registration forApplications in Remote Sensing[J]. Geoscience and Remote Sensing, 2005,43(9):2127-2137.

[2] ZHANG Shaoming,CHEN Yingying,LIN Yi.A Robust Matching Algorithm for SAR Image with Multiple Subareas[J].Acta Geodaetica et Cartographica Sinica,2007, 36(4):406-413.(張紹明,陳映鷹,林怡.用于末制導的SAR圖像多子區實時匹配算法[J].測繪學報,2007,36 (4):406-413.)

[3] INGLADA J,MURON V,PICHARD D,FEUVRIER T. Analysis of Artifacts in Subpixel Remote Sensing Image Registration[J].Geoscience and Remote Sensing,2007,45 (1):254-264.

[4] SUN Jin,GU Hongbin,Qin Xiaolin,ZHOU Na.An Image Matching Algorithm Using Robust Hausdorff Distance[J]. Journal of Image and Graphic,2008,13(4):761-767.(孫瑾,顧宏斌,秦小麟,周娜.一種魯棒型 Hausdorff距離圖像匹配方法[J].中國圖象圖形學報,2008,13(4): 761-767.)

[5] ZHOU Zhiqiang,WANG Bo.Object Matching Algorithm Based on RobustHausdorffDistance[J].Journal of Computer Applications,2009,29(1):86-89.(周志強,汪渤.一種基于魯棒Hausdorff距離的目標匹配算法[J].計算機應用,2009,29(1):86-89.)

[6] SIM D G,KWON O K,PARK R H.Object Matching Algorithms Using RobustHausdorff Distance Measures [J].IEEE Transactions on Image Processing,1999, 8(3):425-429.

[7] TENG Yichen,TSENG Dinchang.Remote-sensing Image Recognition Based on Wavelet Transform and Hausdorff Distance[C]∥Proceedings of International Geoscience and Remote Sensing Symposium.Toulouse:[s.n.],2003: 3528-3530.

[8] MAO Xia,HUANG Kang,LIANG Yaoming.Template Coarse Matching of SAR and Optical Images Based on Wavelet Subbands and Hausdorff Distance[C]∥Proceedings of SPIE,the International Society for Optical Engineering.Washington:SPIE,2007,6786(2):1-6.

[9] ZANG Tiefei,SHEN Tingzhi,CHEN Jianjun,GU Jianjun. The Application ofImproved HausdorffDistanceand Genetic Algorithm in Image Matching[J].Journal of Beijing Institute of Technology,2000,20(6):733-737. (臧鐵飛,沈庭芝,陳建軍,顧建軍.改進的 Hausdorff距離和遺傳算法在圖像匹配中的應用[J].北京理工大學學報,2000,20(6):733-737.)

[10] YU Qiuze,CHENG Hui,LIU Jian,et al.Matching SAR Image to Optical Image Using Modified Hausdorff Distance and Genetic Algorithms[J].Journal of Astronautics,2006,27(1):130-134.(于秋則,程輝,柳健,等.基于改進Hausdorff測度和遺傳算法的SAR圖像與光學圖像匹配[J].宇航學報,2006,27(1):130-134.)

[11] LENG Xuefei,LIU Jianye,XIONG Zhi.Real-time Image Matching for Navigation System Based on Genetic Algorithm[J].Journal on Communications,2008,29(2):17-21.(冷雪飛,劉建業,熊智.基于遺傳算法的導航實時圖像匹配算法[J].通信學報,2008,29(2):17-21.)

[12] DONOHO M N,VETTERLI M.The Contourlet Transform:an EfficientDirectionalMultiresolution Image Representation[J].Image Processing,2005,14(12): 2091-2106.

[13] KENNEDYJ,EBERHART R.Particle Swarm Optimization[C]∥Proceedings of IEEE International Conference on Neural Networks,IV Piscataway,NJ,USA,1995: 1942-1948.

[14] HU Wang,LI Zhishu.A Simpler and More Effective Particle Swarm Optimization Algorithm[J].Journal of Software, 2007,18(4):861-868.(胡望,李志蜀.一種更簡化而高效的粒子群優化算法[J].軟件學報,2007,18(4): 861-868.)

[15] CHEN Guimin,JIA Jianyuan,HAN Qi.Study on the Strategy of Decreasing Inertia Weight in Particle Swarm Optimization Algorithm[J].Journal of Xi’an Jiaotong University,2006,40(1):53-56.(陳貴敏,賈建援,韓琪.粒子群優化算法的慣性權值遞減策略研究[J].西安交通大學學報,2006,40(1):53-56.)

(責任編輯:雷秀麗)

Multi-source Remote Sensing Image Matching Based on Contourlet-domain Hausdorff Distance and Particle Swarm Optimization

CHEN Sa,WU Yiquan
School of Information Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China

To further improve the accuracy and efficiency of multi-source remote sensing image matching,an algorithm based on contourlet transform,Hausdorff distance and improved particle swarm optimization was proposed in this paper.Firstly,the target image and reference image were decomposed to the low resolution image using contourlet transform.Then,wavelet modulus maxima algorithm was employed to extract the edges in the low-frequency subbands,and least-trimmed-squares Hausdorff distance(LTS-HD)was used as similarity measure for image matching.Meanwhile,the extremum disturbed and simple particle swarm optimization was introduced to get the rough matching results.The position of rough matching results was corresponded to the original image and then the matching between the higher resolution images could be implemented stepwise up to the full resolution images.The experimental results show that,compared with those of other common sensing image matching methods,the proposed algorithm has the high accuracy,efficiency and strong robustness.

multi-source remote sensing image matching;contourlet transform;Hausdorff distance;particle swarm optimization

CHEN Sa(1985—),female,Master,majors in image matching and image fusion.

E-mail:sasha85@163.com

1001-1595(2010)06-0599-06

P237

A

國家自然科學基金 (60872065)

2009-07-27

2010-02-12

陳颯(1985—),女,碩士,主要研究方向為圖像匹配、圖像融合等。