基于改进模拟退火遗传算法的INSAR相位解缠算法

于向明　孙学宏　刘丽萍　张　成

(宁夏大学物理电气信息学院　宁夏 银川 750021) 宁夏沙漠信息智能感知重点实验室　宁夏 银川 750021)



基于改进模拟退火遗传算法的INSAR相位解缠算法

于向明孙学宏刘丽萍张成

(宁夏大学物理电气信息学院宁夏 银川 750021) 宁夏沙漠信息智能感知重点实验室宁夏 银川 750021)

为了解决经典的Goldstein枝切线法容易生成过长的枝切线和较多封闭区域的问题，提出一种基于改进模拟退火遗传算法的INSAR(Interferometric Synthetic Aperture Radar)相位解缠算法。该算法首先对部分残差点进行预处理，生成极性平衡的小段枝切线，然后使用改进模拟退火遗传算法求解剩余残差点的优化组合。经这两步处理后，所得到的枝切线的总长度和封闭区域的数量都明显减少。对真实INSAR数据的实验结果表明，该算法在运行时间和解缠精度上均有一定的优越性。

干涉合成孔径雷达相位解缠枝切线遗传算法模拟退火

0　引　言

干涉合成孔径雷达INSAR是一种用于获取地面高程信息的微波遥感测量技术，它通过对同一地区的两幅SAR图像进行相干处理，从而获得与高程相关的相位信息，以此反演出地面目标的高程。由于系统的原因，所提取到的相位的取值范围在(-π,π]之间，一般称其为缠绕相位。然而，真正与地面高程相关的是真实相位，因此，只有对缠绕相位进行相位解缠处理，恢复真实相位，才能得到地面上每个点准确的高度。在实际测量过程中，由于噪声、欠采样和地物不连续等因素的存在，导致干涉相位场出现不一致的现象，在相位数据中的表现均称为残差点，如何有效避免或降低残差点对解缠精度造成的影响，成为了国内外学者研究的热点。目前提出的解缠算法主要分为三类：路径跟踪法、最小范数法和网络流法。其中，以路径跟踪法中的Goldstein枝切线法[1]最为经典和有效，作为一种局部算法，它具有流程简单、速度快和精度高的优点。因此，在得不到实际DEM(Digital Elevation Model)数据校准的情况下，它常作为首先被尝试的算法。但当残差点较为密集时，Goldstein法设置的枝切线很难达到最短，而且容易围成大量封闭区域，对后期顺利解缠带来很大影响。针对枝切线的设置问题，混合遗传算法[2]、粒子群算法[3]、遗传算法[4]、蚁群算法[5]等智能算法被用于求解正负残差点的优化组合，使枝切线总长度逼近最短。但当残差点较多时，直接使用智能优化算法会导致算法的时间和空间复杂度急剧增加，在短时间内很难得到较优的结果，影响后期的解缠精度。因此，提出了一种基于改进模拟退火遗传算法的INSAR相位解缠算法。该算法首先对由噪声引起的偶极子进行配对，并对靠近边界的残差点采取统一“接地”处理，之后对剩余的残差点采用改进模拟退火遗传算法求解其优化组合。对真实的INSAR数据处理结果表明，该算法较好地实现了枝切线的优化设置，提高了解缠精度。

1　残差点与枝切线法

(1)

2　算法描述

2.1部分残差点预处理

在干涉相位图中，残差点主要分为两种形式：偶极子残差点和单极子残差点。其中，偶极子残差点在干涉相位图中以一对正负残差点的形式出现，而单极子残差点则以一个单一极性的残差点的形式出现，且没有与其配对的异性残差点。其中，由噪声引起的偶极子距离很近，相应的正负残差点通常紧紧相邻或相隔一个像素，在干涉相位图中较好识别。因此，对此类偶极子可先进行识别并连接，同时，对靠近边界的点可采取与边界相连的“接地”处理，实现电量平衡。经过上述处理后，可有效减少后期需要优化的残差点的数量，降低优化算法的压力。算法具体步骤如下：

Step1识别干涉相位图中的残差点，将正负残差点分别标记为+1、-1极性，并均标记为不平衡。

Step2找到一个不平衡的残差点，以该残差点为中心，放置一个3×3的搜索窗，若该点为边界点，转Step3，否则转Step4。

Step3将搜索窗内所有的残差点与中心残差点用枝切线相连，由于进行了“接地”处理，因此，搜索窗内的所有残差点均可标记为平衡，转Step2。若搜索窗内无其他残差点，则将中心残差点标记为枝切线，并标记为平衡，转Step2。

Step4在搜索窗内搜索异性残差点，若找到，则将其与中心残差点相连，并将这两个残差点标记为平衡，转Step2；若未找到，则判断当前搜索窗是否已到达边界，若到达，则将该点与边界相连，并标记为平衡，转Step2，若未到达，则判断搜索窗大小是否为5×5，若是，则放弃对该点的操作，转Step2；若不是，则将搜索窗扩大至5×5，转Step4。

点评：基于汽车产业在国民经济中的重要支柱性地位，不少人建议，国家应对车辆购置税减半征收。对于这样的呼吁，并不难理解。作为一个重要税种，车辆购置税曾在2009年和2015年两次下调，对1.6升及以下排量的乘用车减半征收购置税，确实较好地促进了小排量乘用车的推广和提振汽车消费。然而，这也在一定程度上提前透支了车市消费能力。

按照Step1至Step4遍历所有残差点后，由噪声引起的邻近偶极子残差点和靠近边界的残差点均实现了电量平衡，剩余极性不平衡的残差点则使用改进模拟退火遗传算法计算其优化组合。

2.2改进模拟退火遗传算法

遗传算法GA(Genetic Algorithm)是一种借鉴生物界的进化规律演化而来的智能优化方法[8]，其特点是不需要求导和其他辅助信息，具有隐含的并行性，全局搜索能力较强。但在实际应用中，标准遗传算法容易出现过早收敛和陷入局部最优解等问题，其局部搜索能力较差。模拟退火算法SA(Stimulated Annealing)是一种根据自然界中固体物质的退火降温过程与一般组合优化问题之间的相似性所提出来的一种优化算法。该算法采用Metropolis准则来接受产生的最优问题解[9]，确保了算法在接受优解外，还能以一定的概率接受恶化解，并随着温度的降低使接受恶化解的概率趋向于0，从而使算法能跳离局部最优的“陷阱”，得到全局最优解。因此，模拟退火算法具有较强的“爬山”能力，即局部搜索能力较强，但该算法对整个搜索空间的情况了解不多，不能很快地使搜索过程进入最有希望的搜索区域，全局搜索能力较差。

针对这两种算法存在的优势和不足，本文提出一种改进模拟退火遗传算法，该算法将模拟退火算法融入遗传算法的交叉和变异操作中，提高遗传算法的局部搜索能力，防止长时间陷入局部最优解。同时，使用所有残差点及其最小相关边编码[10]，生成一条适应度较高的染色体，并根据该条染色体，采用最近邻与随机2-opt初始化方法生成整体适应度值较高的初始种群，用以加快算法的收敛速度。算法的具体步骤如下：

Step1控制参数设置。主要有最大遗传代数、种群大小、交叉和变异概率、初始温度、降温速率等。

Step2编码。采用所有残差点及其最小相关边编码，该编码方式首先将所有正负残差点进行编号，之后逐个遍历所有残差点，若当前残差点到边界的最短距离小于其到最邻近异性残差点的距离的2倍，则将该残差点与边界相连，同时将对应的边界点定义为一个虚拟的残差点；若当前残差点不满足上述要求，则将其与最邻近的异性残差点相连。遍历完所有残差点后，将所配对的正负残差点的排列分别建模为两条染色体，在算法执行过程中，正残差点对应的染色体作为参考染色体，其排列顺序始终固定不变，将负残差点对应染色体作为初始染色体。图1左侧表示对5个正残差点和4个负残差点的编号结果，数字的上标代表该点的极性，右侧为使用所有残差点及其最小相关边编码得到的结果，正残差点对应的染色体可表示为{1B,1+,2+,3+,4B,4+,5+}，其相应的负残差点染色体编码为{1-,2B,2-,3B,3-,5B, 4-}，枝切线的总长度则通过计算同一基因座上所对应的正负残差点的距离之和求出。可以看出，经过该方法编码，所得到的染色体对应的枝切线总长度较小。

图1　所有残差点及其最小相关边编码

Step3初始化种群。经过Step2产生一条枝切线总长度较短的初始染色体后，对该条染色体采用最近邻与随机2-opt方法产生初始种群。即随机选择初始染色体中的两个基因，交换其位置产生一条新的染色体，若新的染色体所对应的枝切线总长度小于初始染色体对应的枝切线总长度，则将新的染色体放入种群中，否则在初始染色体中重新选择两个基因，重复上述步骤。最终产生枝切线整体长度较短的初始种群。

Step4适应度函数。使用枝切线总长度的倒数作为适应度函数，即该条染色体所对应的枝切线长度越短，其适应度越高。

Step5选择操作。使用随机遍历选择，相比与轮盘赌，该方法可进一步提高选择的公平性。

Step6交叉和模拟退火操作。将父代种群两两随机分组，使用部分匹配交叉对每组中的染色体P1和P2执行交叉操作，得到子代染色体C1和C2，计算父代和子代对应的枝切线总长度分别为f(Pi)和f(Ci)，其中i=1,2，使用Metropolis准则接受新解，如式(2)所示。

(2)

即如果f(Ci)-f(Pi)<0，则以概率1接受新的染色体Ci，否则以概率exp[-(f(Ci)-f(Pi))/T0]接受Ci。

Step7变异和模拟退火操作。随机选择染色体中的两个基因进行交换，交换前和交换后的染色体分别为S1和S2，之后采用Metropolis准则接受新解S2，方法步骤同Step6。

Step8执行降温操作，并判断是否达到最大遗传代数，若是，则输出当前适应度最高的染色体；若不是，则转Step5继续执行。

得到输出的染色体后，将其与参考染色体中同一基因座的基因一一对应，即可确定残差点组合方式，之后在干涉相位图中用枝切线连接对应正负残差点，最后使用洪泛法绕开枝切线进行相位解缠。

3　实验结果与分析

实验中使用的是伊朗BAM地区的两幅SAR图像，在Matlab中(计算机配置：CPU i5-4200M 内存4 GB)经配准、干涉图生成、去平和滤波之后得到如图2所示的700×700干涉相位图，图3为经四点环路积分法检测出的残差点，其中正残差点(白色)2914个，负残差点(黑色)2913个。

Goldstein法设置的枝切线如图4所示，从图5所示的局部放大图可以看出在残差点密集处，枝切线不仅较长，而且由于残差点的重复连接，导致形成了许多封闭区域，这在后期将形成解缠“孤岛”。

图2　干涉相位图　　　　　图3　残差点图

图4　Goldstein法设置的枝切线　　　图5　枝切线局部放大图

表1中给出了Goldstein法和本算法设置枝切线的量化对比。可以看出，相比于Goldstein法，本算法所设置的枝切线长度缩短36.95%， 封闭区域数量减少了98.64%，在运算时间上也得到了一定的改善。

表1　枝切线设置结果对比

本算法所设置的枝切线如图6所示。由于本算法是将正负残差点进行配对连接，或是将残差点与边界相连，因此，最终所设置的都是一些小段的枝切线，没有围成大面积的封闭区域。

为了进一步验证算法在解缠精度上的有效性，将本算法和Goldstein法、质量图引导法的解缠结果进行对比，图7至图9分别为这三种算法的解缠结果。

图6　本算法设置的枝切线　　图7　本算法的解缠结果

图8　Goldstein法解缠结果　图9　质量图引导法解缠结果

同时，使用解缠误差ε和总运算时间作为量化对比指标。其中，解缠误差ε[11]一般采用式(3)定义。

(3)

表2　不同算法的解缠结果对比

从解缠结果中可以看出，Goldstein枝切线法形成了大量的解缠孤岛，如图8中的黑色区域所示，同时，其解缠误差也高于其他两种算法。质量图引导法的解缠精度和本文算法相当，但由于该方法需要不断对纳入邻接表中的元素进行排序，所以其运行时间很长。而本文算法将部分残差点预处理与优化算法结合，不仅在运行时间上具有一定的优势，同时，解缠精度也得到了一定的提高，此外，所围成的封闭区域数量也大幅减少，这将为后期高程的反演工作带来极大的便利。

4　结　语

针对Goldstein枝切线法存在的问题，本文提出了一种新的INSAR相位解缠算法。该算法根据残差点的分布特点，将部分残差点预处理与改进模拟退火遗传算法相结合，用以实现对枝切线的优化设置。对真实INSAR数据的处理结果表明，本文提出的算法不仅在较短的时间内得到了整体长度较短的枝切线，而且使封闭区域的数量大幅降低，提高了解缠精度，相比与常用的局部解缠算法，有一定的优越性。

[1] Goldstein R M,Zebker H A,Werner C L.Satellite radar interferometry:Two-dimensional phase unwrapping[J].Radio Science,1988,23(4):713-720.

[2] Karout S A,Gdeisat M A,Burton D R,et al.Two-dimensional phase unwrapping using a hybrid genetic algorithm[J].Applied Optics,2007,46(5):730-743.

[3] 张妍,冯大政,曲小宁.基于改进粒子群算法的二维相位解缠方法[J].电波科学学报,2012,27(6):1116-1123.

[4] 曲小宁,张妍,冯大政.TSP理论在二维相位解缠的应用[J].系统工程与电子技术,2011,33(4):742-745.

[5] 魏志强,金亚秋.基于蚁群算法的InSAR相位解缠算法[J].电子与信息学报,2008,30(3):518-523.

[6] 李平湘,杨杰.雷达干涉测量原理与应用[M].北京:测绘出版社,2006:79-80.

[7] Huntley J M,Buckland J R.Characterization of sources of 2π phase discontinuity in speckle interferograms[J].Journal of the Optical Society of America A,1995,15(9):1990-1996.

[8] 于海璁,陆锋.一种基于遗传算法的多模式多标准路径规划方法[J].测绘学报,2014,43(1):89-96.

[9] 傅文渊,凌朝东.布朗运动模拟退火算法[J].计算机学报,2014,37(6):1301-1308.

[10] Gutmann B,Weber H.Phase unwrapping with the branch-cut method: clustering of discontinuity sources and reverse simulated annealing[J].Applied Optics,1999,38(26):5577-5593.

[11] Ghiglia D C,Pritt M D.Two-Dimensional Phase unwrapping:Theory,Algorithms,and Software[M].New York:Wiley,1998:293-294.

A PHASE UNWRAPPING ALGORITHM BASED ON IMPROVED STIMULATED ANNEALING GENETIC ALGORITHM FOR INTERFEROMETRIC SAR

Yu XiangmingSun XuehongLiu LipingZhang Cheng

(SchoolofPhysicsElectricalInformationEngineering,NingxiaUniversity,Yinchuan750021,Ningxia,China) (NingxiaKeyLaboratoryofIntelligentSensingforDesertInformation,Yinchuan750021,Ningxia,China)

In order to solve the problems that classical Goldstein’s branch-cuts method easily generates excessively long branch-cuts and more enclosed areas, we proposed a phase unwrapping algorithm for interferometric SAR, which is based on improved stimulated annealing genetic algorithm. First, the algorithm pre-processes part of residues to generate small piece branch-cuts with balanced polarity. Then it uses improved stimulated annealing genetic algorithm to calculate the optimised combination of remaining residues. After these two processing steps, the total length of branch-cuts derived and the number of enclosed areas decrease significantly. Results of experiment on real INSAR data proved that the proposed algorithm has certain advantage in run time and phase unwrapping precision.

Interferometric synthetic aperture radar (INSAR)Phase unwrappingBranch-cutGenetic algorithmStimulated Annealing

2015-07-16。国家自然科学基金项目(61461044)；宁夏高等学校科学技术研究项目(NGY2014007)。于向明，硕士生，主研领域：INSAR信号处理。孙学宏，副教授。刘丽萍，教授。张成，教授。

TP701

A

10.3969/j.issn.1000-386x.2016.10.051