基于图像配准的混合遗传FCM算法研究

李玉峰，李景芳

(1.沈阳航空航天大学 电子信息工程学院，辽宁 沈阳 110136；2.东南大学 移动通信国家重点实验室，江苏 南京 210096)

基于图像配准的混合遗传FCM算法研究

李玉峰1，2，李景芳1

(1.沈阳航空航天大学 电子信息工程学院，辽宁 沈阳 110136；2.东南大学 移动通信国家重点实验室，江苏 南京 210096)

摘要:针对目前图像变化检测的相关研究，提出一种新的算法：基于SAR图像配准的混合遗传FCM算法。算法主要分为4个步骤。第一步，利用Harris算法和SIFT算法对两幅图像进行匹配，证明它们是同源不同时相的图像。第二步，利用两种不同变化检测方法提取初步差异图像。第三步，利用PCA方法对差异图像进行降维处理。第四步，利用混合遗传FCM算法对特征矢量空间进行分类，并将分类结果与参考差异图像进行比较，获得变换信息。采用渥太华地区的部分图像作为检测算法的性能的数据库。获得的结果与FCM算法相比较，结果表明，提出的算法具有最高的全局正确率98.10%，算法效果更佳。

关键词:图像配准；变化检测；PCA ；混合遗传；FCM分割

SAR相对于可见光而言，由于其全天候、全天时的独特的特点，应用范围非常广泛，可以检测地震、洪灾等的变化，能够在第一时间获得灾区的公路、建筑物以及水利设备发生的受损情况，为灾区居民转移以及救助方式提供战略支持[1]。而可见光是一种非主动式成像，所以在夜晚或者光照不足的条件下就无法获得令人满意的光学遥感图像。所以，相比较而言，SAR越来越受到广大研究人员的关注。

SAR图像变化检测方法可以分为两大类：一是基于像素的变化检测方式，目前比较常用的是图像差值法和图像比值法；二是基于区域的变化检测方法，首先将SAR图像进行分割，得到区域图像，然后再在区域的基础上进行分割[2]。

1图像配准

通常意义上理解的图像配准是指对同一地区的不同时间拍摄的图像或者不同角度拍摄的图像进行匹配，找出不同图像的相同点或者相同区域，从而得到图像间最佳的几何变换关系[3-4]。通常在对图像进行变化检测之前，需要先对图像进行配准处理。

本文中用到的两幅图像，从视觉上看是来源于同一地区，然后利用图像配准技术验证一下这两幅图像是否来源于同一地区。令其中一幅图像为基准图像，另外一幅图像为待配准图像。两幅图像之间的相似度越高，那么匹配程度也越高。本文中，图像配准的作用主要是为了减少由于图像失配等外界因素导致的不良影响。

本文图像配准主要是基于特征点的图像匹配。图像特征点是指在水平、垂直方向上都发生极大变化的图像像素点。Harris算子[5]提取角点的基本原理是：定义一个局部检测窗口，当该窗口沿着不同方向移动时，观察被局部窗口覆盖区域的平均能量变化，如果该能量变化值超过设定的阈值，则将该窗口的中心像素点提取为角点。

SIFT算法[6]的基本思想为：根据高斯卷积核实现尺度空间的构建，然后在已完成的尺度空间内寻找极值点，并为极值点建立特征描述符。SIFT算法是一种局部特征描述子，它在图像发生缩放、尺度变化以及角度旋转时都具有不变性。

虽然SIFT算法的稳定性很好，但是它的运算量大，复杂度高。所以，本文采用将基于Harris角点的匹配方法和基于SIFT特征的匹配方法相结合。首先，利用Harris提取特征点，然后利用SIFT算法为每个特征点定义主方向保持旋转不变性，最后生成特征向量的描述子。这样，降低了匹配的复杂度，并且提高了算法的实时性和图像的正确匹配率。

Harris-SIFT算法的流程图如图1所示。

图1　Harris-SIFT算法的流程图

其中，相似度判断主要利用特征点之间的欧氏距离。假设与匹配点最小的欧氏距离差值为Dmin，次小值为Dmi_amin，如果这两者的比值在规定的范围内，则可以判定最小欧氏距离差值对应的点则是待匹配点。计算公式如下

(1)

式中：Threshold表示根据经验求得的阈值。

2初步变化检测

针对SAR图像，目前比较通用的方法主要有差值法、相关系数法、图像熵方法、直方图比较法来对SAR图像进行变化检测[7]。利用3种算法来提取SAR图像变化信息。

1)绝对值差分法：把两幅不同时相的图像相对像素作差，并取绝对值，就可以得到绝对值差分图像Id,1。绝对值差分公式如下

(2)

式中：XT,1表示第一幅图像某一点的像素值；XT,2表示第二幅图像对应点的像素值。

2)对数比例法： 将两幅不同时相的SAR图像矩阵作比，并取绝对值，最后再取对数，形成对数比例图像Id,2。对数比例法公式如下

(3)

式中：log表示自然对数。对数比例图像用来改善低强度的像素。

3PCA处理

PCA方法主要应用于特征提取和降维处理[8-9]。从上述3个公式中获得的图像变化信息，用一个列矩阵Id(x,y)表示为

(4)

这3幅变化图像的尺寸均为H×W，那么总共有HW个向量组成图像中的像素。简而言之，Id,k表示矢量Id(x,y)，而k表示范围为1≤k≤N的指数，其中N=H×W。平均向量χ可以表示为

(5)

每个向量与平均向量的差为Δk=Id,k-χ。协方差矩阵CI的特征矢量为ei，相应的特征值为λi。协方差矩阵CI近似表示为

(6)

式中：利用N-1代替N，从而得到CI的无偏估计。假设，根据特征值的大小，即λi≥λi+1，将CI产生的特征向量按照降序排列。

将Id(x,y)投影于空间位置(i,j)处的每个像素的特征向量空间，从而得到特征矢量空间，即

(7)

协方差矩阵CI的特征向量按照矩阵A的行排列。矩阵的第一行是特征向量的最大特征值，以此类推。从而生成一个特征矢量空间，方便后续处理。

4遗传算法和FCM算法

4.1遗传算法

遗传算法(GA)[10-11]的原理类似于生物界的适者生存，优胜劣汰机制。遗传算法是一种随即搜索方法，不依赖函数的连续性，能够自适应地改变搜索方向，具有很好的并行性和全局搜索能力。遗传算法最重要的就是控制参数的选择。

控制参数的选择方法如下：

1)基因串长度

本文主要是针对灰度图像进行处理，并且采用二进制编码，所以相关范围保持在0～255之间即可。因此，本文选择基因串的长度为8。

2)迭代次数

迭代次数T用来制定终止条件。本文采用迭代次数范围为10～20。

3)种群大小

种群大小n即种群中染色体的多少。n太大会影响算法的效率，n太小会减少种群的多样性。根据经验，本文选择的种群大小为30。

4)交叉概率

交叉概率pc是指pc×n个染色体进行了交换基因。pc的取值范围为[0.6,0.9]。

5)变异概率

变异概率pm是指pm×n个染色体进行了基因取反操作。pc的取值范围为[0.03,0.08]。

4.2FCM算法

FCM算法[12-13]的数学理论基础已经很完善。近些年来，被引用到图像处理领域中。它的实质是求解非凸优化问题的迭代算法。FCM算法的大致思想是：划分到同一类别的对象的相似性尽可能得大；相反地，被划分到不同类的对象之间的相似性尽可能地接近于0。

FCM算法通过多次迭代运算，反复校正聚类中心和隶属度函数，所以FCM聚类又被叫做动态聚类。

FCM算法有一个很重要的函数，即隶属度函数。隶属度函数是用来确定每个数据点属于某一类的程度的一种度量方法。

FCM算法的步骤如下：

1)初始化。即设置目标函数的精度，模糊指数，最大迭代次数等；

2)初始化模糊聚类中心；

3)更新隶属度函数；

4)计算聚类中心；

假设集合X={x1,x2,…,xn}为特征空间Rn上的一个有限数据集合，并且把X划分为c类，用V={v1,v2,…,vc}表示个数为c的聚类中心。FCM算法的目标函数可以表示为

(8)

FCM算法从初始化聚类中心开始，通过每次迭代运算收敛到目标函数的局部极小值点。

隶属度函数uij的表示为

(9)

聚类中心zi的计算公式为

(10)

FCM算法通过对目标函数迭代计算，求出其最小值，从而获得对数据集合的模糊分类。

5混合遗传FCM算法

根据由遗传算法改进的模糊c均值聚类算法，把差异图像聚类成两种类型：变化类型和未发生变化类型，得到最终的变化矩阵。

因为模糊c均值聚类算法是一种局部自适应迭代算法，聚类中心的初始化问题对其十分重要。如果聚类中心初始化不恰当，容易造成目标函数极小值局部收敛，导致聚类效果不佳，影响图像分割，所以选择遗传算法对提取的初步信息进行聚类分析，获得初始聚类中心。

为了克服这种影响，得到更好的聚类结果，本文提出了一种混合遗传FCM算法[14]。

混合遗传FCM算法的步骤如下：

1)计算初始值

通过遗传算法获得k类的聚类中心{z1,z2,…,zk}。

2)适应度的计算

在这一步骤中，通过求FCM的目标函数JFCM的极小值计算N条染色体的适应度f。适应度的计算如下

(11)

3)选择

在这一步骤中，选择具有最佳适应度fi的染色体作为下一代的父本。染色体选择的概率pi为

(12)

4)交叉

交叉是用于繁殖的遗传算子。交叉是一种交换信息的高效方式。这些信息来源于适应度高的染色体。如果没有进行交叉操作，说明用于繁殖的染色体和其父系染色体很相像。在本文中，使用具有固定的交叉速率kc的单点交叉方法。

5)变异

每条染色体具有固定的变异速率km。

6)结束条件

如果迭代计算达到它的最大值，或者是两个连续的迭代方案之间最小的改善值低于阈值，那么程序终止，输出最佳方案。否则，用新产生的染色体代替之前步骤中的一些染色体，重复步骤2)～5)。

6仿真与分析

本文采用Matlab软件作为实验环境来验证本文所提出算法的性能，程序中用到两幅SAR图像是关于渥太华城市的两幅不同时相的图像，是由加拿大渥太华防卫研究和发展中心提供的。

图2所示的这两幅图像的数据大小均为290×350，由Radarsat SAR传感器获得。第一幅图像是1997年7月在夏季洪水灾害时拍摄的图像。第二幅图像是1997年8月在夏季洪水灾害之后拍摄的图像。在这两幅图像中，主要分为两类区域，一类是水域，一类是土地。

a　1997年7月洪灾时　　b　1997年8月洪灾后

因为两幅图像是否是同源图像，单单从视觉上是无法判定的。所以需要做一些相关实验去证明这两幅图像是同源图像。图像配准是为了保证变化前后的两幅图像中的像素大小和地理位置是一致的。

通过观察图3可以发现，经过Harris算子处理，第一幅图像的特征点个数是264，第二幅图像的特征点个数为350。

a　1997年7月洪灾时　　b　1997年8月洪灾后

图4是经过SIFT算子检测后的结果，两幅图像的特征点个数减少，第一幅图像的特征点个数186，第二幅图像的特征点个数272。结果表明特征点数明显。减少的原因是：Harris算法对尺度等因素不稳定，SIFT算法对尺度具有很好的稳定性，所以结合两个算法，可以检测出稳定的准确的特征点。然后求出稳定的特征点的特征向量，利用特征向量之间的欧氏距离判断是否是匹配点对。距离最小的一对特征点就是本文要求的匹配点。

a　1997年7月洪灾时　　b　1997年8月洪灾后

图5是在提取出两幅不同图像的特征点之后，利用特征点独有的特征向量的欧氏距离进行判断，是否是匹配点对。从图5的匹配结果可以看出，这两幅图总共有3对精确的匹配点对。因为SAR图像配准考虑的因素很多，而且配准精度一般要求在1对像素点对以上，所以可以判定这两幅图像是同源图像，可以继续后续的图像变化检测处理。

图5　匹配结果

图6是由两幅不同时相的SAR图像作为先验信息合成的，利用绘图软件画出来的，用来作为参考图像。

图6　参考图像

图7的运行结果是根据图2所示的第一幅图由遗传算法和FCM算法分别求得的4个聚类中心值的对比。其中，实线表示遗传算法求得的聚类中心，虚线表示FCM算法求得的聚类中心。从表1上可以看出，两种算法最终得到的聚类中心值是一致的。

图7　GA和FCM获得的4个聚类中心值的比较

算法时间/s聚类中心1聚类中心2聚类中心3聚类中心4GA0.365791977127182FCMA12.83281877125181

但是从表1可以看出，遗传算法的运行时间要远小于FCM算法的运行时间。所以，由以上结果可以得出，首先利用遗传算法求得聚类中心，然后利用FCM算法求得分割结果，可以节省运算时间。

图8表示最终的分割结果。其中，图8a表示混合遗传FCM算法分割结果，图8b表示FCM算法分割结果。从图左上角可以明显的发现聚类的结果不同，通过与图7的参考图像对比，得出混合遗传FCM算法分割结果更好。

得到分割结果之后，再与参考图像作差，可以得到最终的变化检测结果。

最能真实反映变化检测结果的数据还需要用如下参数表示。本文图像总共有101 500个像素。

TP：正确检测出来的变化像素个数。

TN：正确检测出来的未发生变化的像素个数。

FN(漏检)：把发生变化的像素检测成未发生变化像素的个数。

FP(误检)：把未发生变化的像素检测成发生变化的像素个数。

从上述方程得到的一些矩阵可以用来评价算法的性能。在本文中，采用如下的一些矩阵：

全局正确率(OA)表明算法的正确率

OA=(TP+TN)/(FN+FP+TP+TN)

(13)

关于不同方法的上述矩阵均在表2中显示。结果表明，相对于其他算法，本文提出的算法具有最高的全局正确率98.10%，变化检测效果更佳。

表2仿真结果

算法TPTNFNFPFN+FPOA/%FCM144618489211461001214797.88本文算法14966846091284641192598.10

7总结

本文主要根据FCM算法对初始值敏感的问题，提出了一种基于遗传算法的改进FCM分割方法。因为FCM分割容易因为聚类中心初始值取值不当，而陷入局部极小值。而遗传算法具有能够得到局部最优解的能力。所以本文提到将两种算法相结合求最佳聚类分割结果。并且在这之前，采用3种不同的初步变化检测方法，尽可能地包含更多的信息。然后，利用PCA方法对提取的初步信息降维处理。混合遗传FCM算法，相对于FCM算法有两个很明显的优势：一是运算时间大大减少，因为本算法利用遗传算法获得聚类中心，而遗传算法不存在求导等复杂运算；二是解决了FCM算法对初始聚类中心敏感的问题。

参考文献：

[1]YAHYA N，KAMEL N S，MALIK A S. Subspace-based technique for speckle noise reduction in SAR images[J]. IEEE transactions on geoscience and remote sensing，2014，52(10)：6257-6271.

[2]MARIN C，BOVOLO F，BRUZZONE L. Building change detection in multitemporal very high resolution SAR images[J]. IEEE transactions on geoscience and remote sensing，2015，53(5)：2664-2682.

[3]丁南南，朱明.基于特征点的图像配准技术研究[D].北京：中国科学院，2012.

[4]熊博莅. SAR图像配准及变化检测技术研究[D].长沙：国防科学技术大学，2012.

[5]聂兰苏，唐雁．基于角点检测的图像拼接方法研究[D]．重庆：西南大学，2013.

[6]汪松，王俊平，王世奎. 基于SIFT算法的图像匹配方法研究[D]. 西安：西安电子科技大学，2013.

[7]GONG M G，ZHOU Z Q，MA J J. Change detection in synthetic aperture radar images based on image fusion and fuzzy clustering[J]. IEEE transactions on image processing，2012，21(4)：2141-2151.

[8]刘瑛.基于主成分分析的遥感图像分割算法[D].乌鲁木齐：新疆大学，2011.

[9]莫德林，刘克江，曹彬才，等. 基于主成分分析的遥感图像变化检测[J].影像技术，2013(10)：53-56.

[10]乔阳，李恩，董凤服.基于改进遗传算法的图像分割方法[D]. 成都：电子科技大学，2013.

[11]王雪，李莉. 基于遗传算法的医学图像分割技术的研究[D]. 长春：长春理工大学，2013.

[12]张小峰，张彩明.基于模糊聚类算法的医学图像分割技术研究[D]. 济南：山东大学，2014.

[13]赵洪宋，潘地林.基于遗传算法和FCM的图像自动标注[J].计算机与数字工程，2015(3)：497-500.

[14]HUNG C C，KULKARNI S，KUO B C. A new weighted fuzzy c-means clustering algorithm for remotely sensed image classification[J]. IEEE journal of selected topics in signal processing，2011，5(3)：543-553.

Hybrid genetic FCM algorithm research based on image registration

LI Yufeng1，2，LI Jingfang1

(1.SchoolofElectronicsandEngineering，ShenyangAerospaceUniversity，Shenyang110136，China；2.NationalMobileCommunicationsResearchLaboratory，SoutheastUniversity，Nanjing210096，China)

Abstract:A hybrid genetic FCM algorithm based on SAR images registration is proposed in this paper in view of the present researches of the image change detection. This proposed method is divided into three steps. In the first step，Harris algorithm and SIFT algorithm are used to match different images，proved that they are the homologous images from same region achieved at different time. In the second step，with the using of two change detection methods，the primarily difference image is obtained. In the third step，PCA method is used for feature extraction and dimension reduction. In the fourth step，the feature vector space information is divided into two classes based on hybrid genetic FCM algorithm. The change information is achieved by comparing the classification results and reference difference image. This method takes the parts of image of Ottawa area as data set for the performance evaluation. Compared with other FCM method， the results show that the change detection accuracy of the proposed algorithm reaches 98.10%， so it is better than other algorithms.

Key words:image registration； change detection； PCA； hybrid genetic； FCM segmentation

中图分类号:TN915

文献标志码:A

DOI：10.16280/j.videoe.2016.03.002

基金项目：国家自然科学基金项目(61171081)；航空科学基金项目(20122654)；江苏省博士后基金项目(1101077c)

作者简介：

李玉峰(1969— )，教授，博士，主要研究方向为图像压缩与传输技术，无线通信理论及应用等；

李景芳(1989— )，女，硕士，主要研究方向为信号与信息处理，为本文通讯作者。

责任编辑：时雯

收稿日期：2015-07-26

文献引用格式：李玉峰，李景芳.基于图像配准的混合遗传FCM算法研究[J].电视技术,2016，40(3)：5-10.

LI Y F，LI J F.Hybrid genetic FCM algorithm research based on image registration[J].Video engineering,2016,40(3)：5-10.