16阶归一化互信息和改进PSO算法的快速图像匹配

安 如，王慧麟，王 盈，陈春烨，张 琴，徐晓峰

(1.河海大学地球科学与工程学院，南京210098;2.南京大学地理与海洋科学学院，南京210093;3.南京大学建筑与城市规划学院，南京210093)

相似性测度是衡量两幅待匹配图像特征或亮度接近程度的一种度量方法，对图像匹配成功与否起着关键作用，一直是人们研究的热点问题。常用的方法主要有基于像元灰度和基于特征的各种相似性测度方法［1－2］。由于互信息不需要对不同成像模式下图像灰度间的关系作任何假设，也不需要对图像进行分割或任何预处理，所以近年来在医学和遥感图像匹配中得到了较多应用［2－4］。

粒 子 群 优 化 算 法 (Particle Swarm Optimization，简称 PSO)由 Eberhart等［5］于1995年提出，它是一类新兴的基于群智能优化的算法。由于该算法概念简单，易于实现，所以受到各领域学者的关注，被广泛应用于电力系统优化、神经网络训练、数字电路优化、交通事故探测、参数辨识等方面，并且得到了不同的改进［6－8］，取得了一定的效果。在图像匹配中，利用互信息能够得到较高的匹配正确率，但是其运算量大，速度慢［9］，难以达到实时要求。利用粒子群优化算法能够大幅提高其运算速度，实现快速匹配。笔者利用不同传感器获得的多源遥感图像，对互信息及改进的粒子群优化算法进行验证，证明互信息相似性测度具有更高的鲁棒性。而改进的自组织分层粒子群优化算法，通过增大重新初始化粒子的数量和改进收敛机制较好地克服了易于陷入局部极值和全局过早收敛的现象，不仅提高了互信息测度的匹配速度，而且能够得到相对较高的匹配正确率。

1 互信息相似性测度准则

1.1 归一化互信息

互信息是信息论的一个重要内容，主要用于衡量两个独立的随机变量或者两个图像对象之间的统计相关性特征，例如概率密度、梯度或者图像直方图［10］。互信息主要由两个对象间的联合概率或者联合熵表示，可以描述对象的不确定性和复杂性。如果两个对象间的互信息值小，则说明这两个对象是独立的，反之则说明这两个对象是关联的。在这个过程中联合概率在决定对象间的关联性中起着重要的作用。当两幅图像达到最佳配准时，其对应像素的灰度互信息应达到最大，因而互信息可作为图像配准中的相似性测度。互信息用信息熵表示时公式为［11］

如果将互信息用概率密度表示，其具体形式为

其中pU(u)，pV(v)分别指随机变量U和V的边缘概率，pUV(u，v)指U和V的联合概率。

将互信息应用于图像匹配有着独特的特点，大多数的灰度统计量是将两幅图像间的灰度建立线性关系，这种方法对于图像噪声或者各种扰动特别敏感。当出现噪声或者扰动时，统计量往往会有较大的变化，即单个像素点与另一幅图像对应象素点灰度的线性关系将会产生较大的变化，影响对图像整体的判断。互信息主要通过统计图像的“灰度对”分布信息判断图像间的关系，即图像整体灰度与另一幅图像整体灰度信息间的关系，当某一幅图像的灰度局部出现较大变化时，另一幅图像与之相对应的整体“灰度对”信息并不会有特别明显的变化。

虽然基于最大互信息的匹配算法能够取得较高的图像匹配正确率，但是当两幅图像的重叠部分偏小或者图像的插值方法比较粗糙时，匹配的正确率将会降低。为解决该问题，Studholme等［12］提出了归一化互信息测度。

归一化互信息的表达式如下

如果用概率密度表示，其具体形式为

1.2 不同灰度阶互信息对匹配性能的影响

通常图像用256阶灰度表示，但图像灰度阶越高，用互信息匹配耗时将越长，且并不是用高灰度阶图像匹配其正确率就越高。如图1所示为用SPOT卫星图像作为参考图像，IRS－C卫星图像为实时图像时采用不同灰度阶得到的互信息测度值曲面。

从图1中可发现，用256阶灰度图像进行匹配(图1(a))，在正确匹配位置处相似度峰值不显著;16阶灰度图像进行匹配时(图1(b))，在正确匹配位置有尖锐的相似峰存在;而用4阶灰度图像进行匹配(图1(c))，存在多个峰值，而在正确匹配位置处没有匹配峰值。各灰度阶匹配用时和正确率如表1所示。

图1 不同灰度阶互信息相似性测度曲面Fig.1 Sim ilarity criteria curved surfaces of mutual information w ith different histogram bins

表1 不同灰度阶的标准PSO匹配时间和正确率Tab.1 M atching time and seccess rate of standard PSO by imagesw ith different histogram bins

从表1中可见，图像的灰度阶数越高，参与统计的图像信息量越多，则匹配所用的时间就越长;反之，则所消耗的时间越短。其中从256阶到64阶的匹配时间几乎是成倍的减少，在64阶以后，随着阶数的降低，相隔阶数之间的匹配的时间差依次递减。匹配正确率16阶最高。

通过对互信息与匹配正确率和匹配时间的影响的分析得出，当图像选用16阶灰度时，PSO算法能够利用较少的匹配时间并得到较高的正确率。论文选用16阶灰度互信息作为匹配的相似性度量准则。

2 优化搜索策略

2.1 粒子群优化算法

粒子群算法(PSO)思想来源于人工生命和演化计算理论。PSO中，每个优化问题的解被看成是搜索空间中的一只鸟，称之为“粒子”，所有的粒子都有一个由优化函数决定的适应值，每个粒子还有一个速度决定它们飞翔的方向和距离。每次迭代中，粒子通过跟踪两个“极值”更新自己，第1个是粒子本身所找到的最优解，称为个体极值PPbest;另一个是整个种群目前找到的最优解，称为全局极值GGbest。在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和位置

其中v是粒子的速度，ppresent是当前粒子的位置。pbest和Gbest是前面定义的个体极值和全局极值，rrand()是介于(0，1)之间的随机数，c1，c2是学习因子。

由式(5)的速度修正公式可看出，v分为3个部分:第1部分是“惯性”部分，继承了上一次的速度;第2部分是“认知”部分，表示了粒子从自身学习的成分;第3部分是“社会”部分，是粒子从群体学习的成分［13］。

算法的终止条件是全局最优值不变次数大于阈值或全局最优变化值小于规定阈值。其中粒子解的好坏由适应度函数衡量，笔者选择16阶归一化互信息准则作为算法的适应度函数。

2.2 几种改进的PSO

自从PSO算法在1995年提出以后，引起了全世界学者的兴趣。2003年，Eberhart提出了目前7种最有研究价值的PSO算法［14］，包括全信息PSO算法(The Fully Informed Particle Swarm)［15］、实时变化加速因子的自组织分层 PSO算法［16］(Self－Organizing Hierarchical Particle Swarm Optimizer with Time－Varying Acceleration Coefficients，简称为HPSO)，CPSO算法［17］(Center particle swarm optimization，简 称 为 CPSO)，Variable neighborhood selection based particle swarm optimization(简称VNSPSO)［18］等，这些算法代表了PSO的发展方向。

笔者对这几种主要粒子群改进算法进行了分析比较研究，在此基础上提出改进的自组织分层PSO算法(IHPSO).

2.3 改进的自组织分层PSO算法

2.3.1 自组织分层PSO算法(HPSO)

Ratnaweera等［16］提出了自组织分层PSO算法，当某个粒子的速度变为本次循环中最小速度时，就重新初始化该粒子的最大速度Vmax，增强其全局搜索能力。在算法中，最大速度Vmax和加速因子c1、c2是实时变化的。其中Vmax根据循环的次数而逐次减少，c1的值从大到小递减，而c2的值从小到大递增。

2.3.2 改进的自组织分层PSO算法

自组织分层PSO中利用最大速度更新速度变化为零的粒子，能使粒子随着迭代次数的增加而实时的调整粒子的速度范围，保证在当次循环时能够有合适的搜索范围。但是通过研究发现，在算法进行的过程中速度变化为零的粒子较少，通常每次循环仅有1～2个粒子其速度变化为零，对这些极少量粒子重新初始化，粒子的多样性不可能有大幅度的增加，因而也不可能完全让粒子群跳出局部极值。论文对自组织分层PSO方法的改进如下:

初始化方法的改进:在全局极值不变后，重新初始化个体极值不变粒子的速度。通过这个方法能够适时的帮助粒子群跳出局部极值，最终寻找到全局最优。

收敛方法的改进:判断粒子是否全局最优值发生不变前循环次数已满60次并且全局最优值是否连续30次不变，若符合条件则算法结束。该方法的基本流程描述如下:

Step1:初始化粒子的速度和位置;

Step2:分别计算各个粒子的适应度函数值，并统计各个粒子的个体极值pbest，以及粒子群的最优值gbest;

Step3:判断gbest是否不变，如果有变化，则转到Step4;否则不变，则转到Step5;

Step4:利用式(7)、式(8)和式(9)，根据变加速因子法分别更新粒子的速度，如果粒子速度的变化量为零，则利用式(6)重新初始化粒子的速度，并设定初始化的最小速度为0.1 Vmax;

其中选取惯性权重ω=0.729，其他参数同式(5);

Step5:判断粒子的pbest是否不变，如果不变，则随机初始化粒子的速度;如果有改变，则利用式(7)、式(8)和式(9)更新粒子的速度;

Step6:更新粒子的位置，重新计算其适应度值并统计各个粒子的 pbest和粒子群的gbest;

Step7:判断粒子是否全局最优值发生不变前循环次数满60次并且全局最优值是否连续30次不变，若符合条件则算法结束;若不符合条件则算法转到Step3。

3 实验与讨论

3.1 实验数据

笔者分别选取了4组同一地区，不同传感器，不同时相的遥感图像作为匹配实验的基准图像和产生实时图像的源图像，包括radarSAT－1、SPOT5和IKONOS－2这几种传感器，所选区域较有代表性，能较好的说明实验中的各种地表景观情况。实验所选基准图像的大小均为256×256。产生实时图像的源图像大小亦为256×256。一幅源图像生成100幅64×64的实时图像。

第1组:SAR和SPOT图像(见图2)SAR数据的拍摄传感器为radarSAT－1，拍摄时间为2003年6月，拍摄时采用C波段，波长为0.0565646 m，极化方式为HH极化，最近点入射角为23.989°，空间分辨率为12.5 m。SPOT数据的拍摄传感器为SPOT4，拍摄时间为2003年7月27日2点47分，全色波段，图像空间分辨率为10 m。

图2 匹配实验图像-农田景观区域Fig.2 Test data for imagematching-crop landscape area

第2组:SPOT和IKONOS图像(见图3)。SPOT5数据的拍摄时间为2003年7月27日2点47分，波段为PAN全色波段，图像空间分辨率为2.5 m。IKONOS数据的拍摄传感器为IKONOS－2，拍摄时间为2000年3月26日2点29分，图像空间分辨率为1 m。

图3 匹配实验图像-城市景观区域Fig.3 Test data for imagematching-city landscape area

第3组:IRS－C和SPOT4图像(见图4)。IRS－C数据的拍摄时间为1996年6月，波段为PAN全色波段，图像空间分辨率为 5.8 m。SPOT4数据的拍摄时间为1999年12月21日，波段为PAN全色波段，图像空间分辨率为10 m。

图4 匹配实验图像-河流景观区域Fig.4 Test data for imagematching-river landscape area

第4组:不同时相的SPOT5图像(见图5)。这一组数据都是SPOT5分别在不同时间内拍摄的PAN图像，图5(a)的拍摄时间为2000年12月，图5(b)的拍摄时间为2001年3月，空间分辨率为2.5 m。

在实验之前分别对各组图像进行了预处理，在第一组图像中使用GAMMA滤波对SAR图像进行了滤波处理，并且对SAR图像进行了灰度拉伸和几何纠正。

图5 匹配实验图像-村镇景观区域Fig.5 Test data for imagematching-twon landscape area

以图6为例，笔者的匹配是指在图6(a)中找到图6(b)的位置。匹配得到的图6(b)左下角点坐标与已知的正确匹配位置坐标在3个像素内，认为是正确匹配。图6(c)为匹配结果(从源图像上割取实时图像时就已经确定了他们在基准图上的准确位置，这样可测试匹配算法的性能)。

图6 匹配概念Fig.6 M atching concept

笔者研究是以分辨率较高，大小为256×256的图像作为基准图像，将分辨率较低，大小为64 ×64，其区域包含在基准图像中的子图像作为实时图像。实验中，分别输入基准图像和实时图像，以改进的PSO算法为快速搜索策略，随机生成粒子群，然后以16阶归一化互信息为相似度度量准则，进行图像快速匹配，最后输出匹配结果。

该实验以VC++6.0和Matlab作为开发和实验平台，计算机配置为Intel1.8 GHz的CPU，256 MByts内存。所用的图像主要是不同传感器在不同时段拍摄的不同分辨率的同一地区的遥感图像，图像中包括了各种地物景观，有较强的代表性。

3.2 参数设置

1)遍历互信息。

遍历互信息主要是利用16阶归一化互信息来进行遍历搜索。将实时图在匹配基准图中逐像元依次移动并计算其与大小相同的基准图子图的互信息值，出现最大互信息值的位置即认为是匹配正确的位置。

2)标准PSO算法。

标准PSO算法主要用式(5)更新粒子的速度，用式(5)第2式更新粒子的位置。选取惯性权重ω =0.729，加速因子c1=2.0，c2=2.0，最大速度Vmax为最大允许飞行范围，取值为192(即256－64=192)。

3)FIPSO算法。

实验中，选取粒子间的距离作为判断粒子拓扑关系的标准，计算所有两个粒子间的距离，并计算出其平均值，即为粒子间的平均距离。当粒子与其它粒子的距离小于平均距离，则那个粒子即为该粒子的邻域粒子，参与该粒子的拓扑计算和速度更新。用平均距离统计出邻域粒子后，用式(12)计算出各个粒子的个体加速因子，然后用式(11)计算出记录粒子邻域信息的参数Pm，最后用式(10)更新粒子的速度。选取压缩因子χ=0. 729，加速因子c=4.1。

4)HPSO算法。

HPSO算法用式(7)和式(8)计算出每次循环中的加速因子的值，然后用式(5)计算其中的认知部分与社会部分之和，即速度的变化量，如果变化量为0，则用式(6)重新初始化粒子的速度。随着循环数的增加，c1的取值从2.5到0.5递减，而c2的取值从0.5到2.5递增，Vmax的取值从192到19.2(0.1×192)递减，最大循环次数iitermax为120。

5)CPSO算法。

CPSO算法中，所有的参数设置与标准PSO算法的参数设置相同。

6)VNSPSO算法。

当全局极值连续20次不变时，需要以最优粒子的位置为圆心依次作30个圆，为了增大搜索范围，尽量使这30个圆能覆盖到大部分的图像，通过实验取r=4。

7)改进HPSO(50)。

实验中，改进HPSO使用50个粒子，控制算法循环到60次后判断连续30次不变则算法收敛。

8)改进HPSO(90)。

改进HPSO(90)表示使用90个粒子进行实验，算法收敛条件和改进HPSO相同。

3.3 匹配实验与讨论

首先将每幅图像都用互信息的遍历算法统计出各组图像的匹配正确率和匹配时间，作为PSO算法匹配结果的参照。然后运行各种PSO算法，以期最后的结果能接近遍历互信息的匹配正确率，但能够大幅度的减少匹配运行时间。

将这4组遥感图像数据分别进行遍历互信息、标准PSO、FIPSO、CPSO、HPSO和改进HPSO算法的实验，结果如表2所示。

表2 几种方法匹配结果Tab le 2 M atching Results of severalmethods

从表2可看出，16阶遍历互信息算法的匹配正确率最高，但是耗时也最多，其平均匹配时间约为4 s，总体匹配性能并不高。使用90个粒子的改进的HPSO算法是所有PSO算法中匹配正确率最高的，整体匹配正确率于互信息算法相比最为接近，降低的幅度很少，但是时间只有遍历互信息的40%左右。如果用50个粒子的改进HPSO算法，比90个粒子的HPSO算法的匹配正确率略低，比其他PSO算法的正确率都要高，但是匹配的时间最少，匹配的整体性能最高。其他PSO算法大多比标准PSO算法的匹配性能要高，其中HPSO算法的性能总体要更高一些，但是比不上改进的HPSO。

对于各组图像，第1组SAR和SPOT匹配的正确率较低，这主要是由于SAR图像的噪声太多，图像整体质量不高。在匹配过程中，由于噪声的影响，出现较多突出的互信息峰值，甚至很多峰值都超出了正确位置的峰值，使粒子在飞翔过程中找不到正确位置，造成误匹配。对于其他各组图像，图上地物较多，信息较为丰富的区域匹配正确率整体较高，即使有微小的峰值差异，只要是正确位置的峰值最突出，通过调整PSO算法，总能找到正确的位置。而有的图像整体信息较为贫乏，错误峰值较多，这就是有的图像匹配正确率能在不同的PSO算法下提高较大，而有的图像无论使用何种PSO算法始终不能得到较高匹配正确率的原因。

4 结论

笔者对不同灰度阶归一化互信息相似性测度的匹配性能进行了研究，认为16阶归一化互信息具有较好的匹配性能。通过增大重新初始化粒子的数量和改进收敛机制，增加了粒子的多样性，降低了粒子陷入局部极值的概率，基于此提出了一种改进的自组织分层PSO算法(IHPSO)。与标准PSO、全信息PSO和自组织分层PSO算法相比，改进的自组织分层PSO算法加快了匹配速度，有效提高了匹配的正确率，取得了较为理想的结果。但与遍历搜索相比，采用改进的自组织分层PSO算法，在匹配速度有显著提高的基础上，匹配正确率有所下降。今后还应进一步研究各种粒子群优化思想，在大幅度提高匹配速度的前提下，保持匹配正确率。

［1］Zitova B，Flusser J.Image registrationmethods:a survey［J］.Image and Vision Computing，2003，21:977－1000.

［2］安如，王慧麟，陶晓勋，等.景象匹配相似性测度准则研究［J］.河海大学学报:自然科学版，2009，37(2): 147－152.

An Ru，Wang Hui－lin，Tao Xiao－xun，et al.Scenematching similartymeasure criteria［J］.Journal of Hohai U－niversity(Natural Sciences)，2009，37(2):147－152.

［3］Studholme C，Hill DLG，Hawkes D J.An overlap invariant entropymeasure of3Dmedical Imagealignment［J］. PatternRecognition，1999，32(1)，71－86.

［4］Chen H M，Varshney P K，Arora M K.Performance of mutual information similarity measure for registration of multitemporal remote sensing images［J］.IEEETransactions on Geoscience and Remote Sensing，2003，41 (11):2445－2454.

［5］Eberhart R C，Kennedy J.A new optimizer using particles swarm theory［C］//Proc 6th Int'l Symp on Micro Machine and Human Science.1995:39－43.

［6］Eberhart R C.Fuzzy adaptive particle swarm optimization［C］//Proceedings of the IEEE Conference on Evolutionary Computation.Seoul，Korea，2001:101－106.

［7］Carlos A Gregorio Toscano Pulido，Maximino Salazar Lechuga.Handlingmultiple objectives with particle swarm optimization［J］.IEEE Transactions Evolutionary Computation，2004，8(3):138－142.

［8］Chunming Yang，Dan Simon.A new particle swarm optimization technique［C］//Proceedings of the 18th International Conference on Systems Engineering，IEEE. 2005.

［9］张见威，韩国强.基于互信息的医学图像配准中的互信息的计算［J］.生物医学工程学杂志，2008，25(1):12－17.

Zhang Jian－wei，Han Guo－qiang.Calculation of mutual information based on mutual information image regislration［J］.Journal of Biomedical Engineering，2008，25(1):12－17.

［10］Van Den Bergh F，Engelbrecht A P.A Cooperative approach to particle swarm optimization［J］.IEEE Transactions on Evolutionary Computation，2004，8(3):225－239.

［11］Cover TM，Thomas JA.Elements of information theory［C］//Proceedings of the 18th International Conference on Systems Engineering IEEE.New York:John Wiley＆Sons，2009.

［12］Studholme C，Hill d LG，Hawkes D J.An overlap invar－iant entropy measure of 3D medical image alignment［J］.Pattern Recognition，1999，32(1):71－86.

［13］An Ru，Gong Peng，Wang Hui－lin，etal.Amodified PSO algorithm for remote sensing image template matching［J］.Photogrammetric Engineering＆Remote Sensing，2010，76(4):379－389.

［14］Hu Xiao－hui，Shi Yu－hui，Russ Eberhart.Recent advances in particle swarm［C］//Proceedings of the 2004 Congress on Evolutionary Computation，2011:90－97.

［15］Mendes R，Kennedy J，Neves J.The fully informed particle swarm:simpler，maybe better［J］.IEEE Transactions on Evolutionary Computation，2004，8(3):204－210.

［16］Ratnaweera A，Halgamure SK，Watson H C.Self－organizing hierarchical particle swarm optimizerwith time－varying acceleration coefficients［J］.Evolutionary Computation，IEEE Transactions，2004，(8):240－255.

［17］Liu Yu，Qin Zheng，Shi Zhe－wen，et al.Center particle swarm optimization［C］//Preprint submitted to Elsevier Science，2006:12－19.

［18］Jin Jing，Wang Qiang，Shen Yi.High－performancemedical image registration using improving particle swarm optimization［C］//IEEE International Instrumentation and Measurement Techonlogy Conference，2008:12－15.