基于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—),女,硕士,主要研究方向为图像匹配、图像融合等。