基于改進(jìn)模擬退火遺傳算法的INSAR相位解纏算法

于向明　孫學(xué)宏　劉麗萍　張　成

(寧夏大學(xué)物理電氣信息學(xué)院　寧夏 銀川 750021) 寧夏沙漠信息智能感知重點(diǎn)實(shí)驗(yàn)室　寧夏 銀川 750021)

?

基于改進(jìn)模擬退火遺傳算法的INSAR相位解纏算法

于向明孫學(xué)宏劉麗萍張成

(寧夏大學(xué)物理電氣信息學(xué)院寧夏 銀川 750021) 寧夏沙漠信息智能感知重點(diǎn)實(shí)驗(yàn)室寧夏 銀川 750021)

為了解決經(jīng)典的Goldstein枝切線法容易生成過長的枝切線和較多封閉區(qū)域的問題，提出一種基于改進(jìn)模擬退火遺傳算法的INSAR(Interferometric Synthetic Aperture Radar)相位解纏算法。該算法首先對(duì)部分殘差點(diǎn)進(jìn)行預(yù)處理，生成極性平衡的小段枝切線，然后使用改進(jìn)模擬退火遺傳算法求解剩余殘差點(diǎn)的優(yōu)化組合。經(jīng)這兩步處理后，所得到的枝切線的總長度和封閉區(qū)域的數(shù)量都明顯減少。對(duì)真實(shí)INSAR數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明，該算法在運(yùn)行時(shí)間和解纏精度上均有一定的優(yōu)越性。

干涉合成孔徑雷達(dá)相位解纏枝切線遺傳算法模擬退火

0　引　言

干涉合成孔徑雷達(dá)INSAR是一種用于獲取地面高程信息的微波遙感測量技術(shù)，它通過對(duì)同一地區(qū)的兩幅SAR圖像進(jìn)行相干處理，從而獲得與高程相關(guān)的相位信息，以此反演出地面目標(biāo)的高程。由于系統(tǒng)的原因，所提取到的相位的取值范圍在(-π,π]之間，一般稱其為纏繞相位。然而，真正與地面高程相關(guān)的是真實(shí)相位，因此，只有對(duì)纏繞相位進(jìn)行相位解纏處理，恢復(fù)真實(shí)相位，才能得到地面上每個(gè)點(diǎn)準(zhǔn)確的高度。在實(shí)際測量過程中，由于噪聲、欠采樣和地物不連續(xù)等因素的存在，導(dǎo)致干涉相位場出現(xiàn)不一致的現(xiàn)象，在相位數(shù)據(jù)中的表現(xiàn)均稱為殘差點(diǎn)，如何有效避免或降低殘差點(diǎn)對(duì)解纏精度造成的影響，成為了國內(nèi)外學(xué)者研究的熱點(diǎn)。目前提出的解纏算法主要分為三類：路徑跟蹤法、最小范數(shù)法和網(wǎng)絡(luò)流法。其中，以路徑跟蹤法中的Goldstein枝切線法[1]最為經(jīng)典和有效，作為一種局部算法，它具有流程簡單、速度快和精度高的優(yōu)點(diǎn)。因此，在得不到實(shí)際DEM(Digital Elevation Model)數(shù)據(jù)校準(zhǔn)的情況下，它常作為首先被嘗試的算法。但當(dāng)殘差點(diǎn)較為密集時(shí)，Goldstein法設(shè)置的枝切線很難達(dá)到最短，而且容易圍成大量封閉區(qū)域，對(duì)后期順利解纏帶來很大影響。針對(duì)枝切線的設(shè)置問題，混合遺傳算法[2]、粒子群算法[3]、遺傳算法[4]、蟻群算法[5]等智能算法被用于求解正負(fù)殘差點(diǎn)的優(yōu)化組合，使枝切線總長度逼近最短。但當(dāng)殘差點(diǎn)較多時(shí)，直接使用智能優(yōu)化算法會(huì)導(dǎo)致算法的時(shí)間和空間復(fù)雜度急劇增加，在短時(shí)間內(nèi)很難得到較優(yōu)的結(jié)果，影響后期的解纏精度。因此，提出了一種基于改進(jìn)模擬退火遺傳算法的INSAR相位解纏算法。該算法首先對(duì)由噪聲引起的偶極子進(jìn)行配對(duì)，并對(duì)靠近邊界的殘差點(diǎn)采取統(tǒng)一“接地”處理，之后對(duì)剩余的殘差點(diǎn)采用改進(jìn)模擬退火遺傳算法求解其優(yōu)化組合。對(duì)真實(shí)的INSAR數(shù)據(jù)處理結(jié)果表明，該算法較好地實(shí)現(xiàn)了枝切線的優(yōu)化設(shè)置，提高了解纏精度。

1　殘差點(diǎn)與枝切線法

(1)

2　算法描述

2.1部分殘差點(diǎn)預(yù)處理

在干涉相位圖中，殘差點(diǎn)主要分為兩種形式：偶極子殘差點(diǎn)和單極子殘差點(diǎn)。其中，偶極子殘差點(diǎn)在干涉相位圖中以一對(duì)正負(fù)殘差點(diǎn)的形式出現(xiàn)，而單極子殘差點(diǎn)則以一個(gè)單一極性的殘差點(diǎn)的形式出現(xiàn)，且沒有與其配對(duì)的異性殘差點(diǎn)。其中，由噪聲引起的偶極子距離很近，相應(yīng)的正負(fù)殘差點(diǎn)通常緊緊相鄰或相隔一個(gè)像素，在干涉相位圖中較好識(shí)別。因此，對(duì)此類偶極子可先進(jìn)行識(shí)別并連接，同時(shí)，對(duì)靠近邊界的點(diǎn)可采取與邊界相連的“接地”處理，實(shí)現(xiàn)電量平衡。經(jīng)過上述處理后，可有效減少后期需要優(yōu)化的殘差點(diǎn)的數(shù)量，降低優(yōu)化算法的壓力。算法具體步驟如下：

Step1識(shí)別干涉相位圖中的殘差點(diǎn)，將正負(fù)殘差點(diǎn)分別標(biāo)記為+1、-1極性，并均標(biāo)記為不平衡。

Step2找到一個(gè)不平衡的殘差點(diǎn)，以該殘差點(diǎn)為中心，放置一個(gè)3×3的搜索窗，若該點(diǎn)為邊界點(diǎn)，轉(zhuǎn)Step3，否則轉(zhuǎn)Step4。

Step3將搜索窗內(nèi)所有的殘差點(diǎn)與中心殘差點(diǎn)用枝切線相連，由于進(jìn)行了“接地”處理，因此，搜索窗內(nèi)的所有殘差點(diǎn)均可標(biāo)記為平衡，轉(zhuǎn)Step2。若搜索窗內(nèi)無其他殘差點(diǎn)，則將中心殘差點(diǎn)標(biāo)記為枝切線，并標(biāo)記為平衡，轉(zhuǎn)Step2。

Step4在搜索窗內(nèi)搜索異性殘差點(diǎn)，若找到，則將其與中心殘差點(diǎn)相連，并將這兩個(gè)殘差點(diǎn)標(biāo)記為平衡，轉(zhuǎn)Step2；若未找到，則判斷當(dāng)前搜索窗是否已到達(dá)邊界，若到達(dá)，則將該點(diǎn)與邊界相連，并標(biāo)記為平衡，轉(zhuǎn)Step2，若未到達(dá)，則判斷搜索窗大小是否為5×5，若是，則放棄對(duì)該點(diǎn)的操作，轉(zhuǎn)Step2；若不是，則將搜索窗擴(kuò)大至5×5，轉(zhuǎn)Step4。

點(diǎn)評(píng)：基于汽車產(chǎn)業(yè)在國民經(jīng)濟(jì)中的重要支柱性地位，不少人建議，國家應(yīng)對(duì)車輛購置稅減半征收。對(duì)于這樣的呼吁，并不難理解。作為一個(gè)重要稅種，車輛購置稅曾在2009年和2015年兩次下調(diào)，對(duì)1.6升及以下排量的乘用車減半征收購置稅，確實(shí)較好地促進(jìn)了小排量乘用車的推廣和提振汽車消費(fèi)。然而，這也在一定程度上提前透支了車市消費(fèi)能力。

按照Step1至Step4遍歷所有殘差點(diǎn)后，由噪聲引起的鄰近偶極子殘差點(diǎn)和靠近邊界的殘差點(diǎn)均實(shí)現(xiàn)了電量平衡，剩余極性不平衡的殘差點(diǎn)則使用改進(jìn)模擬退火遺傳算法計(jì)算其優(yōu)化組合。

2.2改進(jìn)模擬退火遺傳算法

遺傳算法GA(Genetic Algorithm)是一種借鑒生物界的進(jìn)化規(guī)律演化而來的智能優(yōu)化方法[8]，其特點(diǎn)是不需要求導(dǎo)和其他輔助信息，具有隱含的并行性，全局搜索能力較強(qiáng)。但在實(shí)際應(yīng)用中，標(biāo)準(zhǔn)遺傳算法容易出現(xiàn)過早收斂和陷入局部最優(yōu)解等問題，其局部搜索能力較差。模擬退火算法SA(Stimulated Annealing)是一種根據(jù)自然界中固體物質(zhì)的退火降溫過程與一般組合優(yōu)化問題之間的相似性所提出來的一種優(yōu)化算法。該算法采用Metropolis準(zhǔn)則來接受產(chǎn)生的最優(yōu)問題解[9]，確保了算法在接受優(yōu)解外，還能以一定的概率接受惡化解，并隨著溫度的降低使接受惡化解的概率趨向于0，從而使算法能跳離局部最優(yōu)的“陷阱”，得到全局最優(yōu)解。因此，模擬退火算法具有較強(qiáng)的“爬山”能力，即局部搜索能力較強(qiáng)，但該算法對(duì)整個(gè)搜索空間的情況了解不多，不能很快地使搜索過程進(jìn)入最有希望的搜索區(qū)域，全局搜索能力較差。

針對(duì)這兩種算法存在的優(yōu)勢和不足，本文提出一種改進(jìn)模擬退火遺傳算法，該算法將模擬退火算法融入遺傳算法的交叉和變異操作中，提高遺傳算法的局部搜索能力，防止長時(shí)間陷入局部最優(yōu)解。同時(shí)，使用所有殘差點(diǎn)及其最小相關(guān)邊編碼[10]，生成一條適應(yīng)度較高的染色體，并根據(jù)該條染色體，采用最近鄰與隨機(jī)2-opt初始化方法生成整體適應(yīng)度值較高的初始種群，用以加快算法的收斂速度。算法的具體步驟如下：

Step1控制參數(shù)設(shè)置。主要有最大遺傳代數(shù)、種群大小、交叉和變異概率、初始溫度、降溫速率等。

Step2編碼。采用所有殘差點(diǎn)及其最小相關(guān)邊編碼，該編碼方式首先將所有正負(fù)殘差點(diǎn)進(jìn)行編號(hào)，之后逐個(gè)遍歷所有殘差點(diǎn)，若當(dāng)前殘差點(diǎn)到邊界的最短距離小于其到最鄰近異性殘差點(diǎn)的距離的2倍，則將該殘差點(diǎn)與邊界相連，同時(shí)將對(duì)應(yīng)的邊界點(diǎn)定義為一個(gè)虛擬的殘差點(diǎn)；若當(dāng)前殘差點(diǎn)不滿足上述要求，則將其與最鄰近的異性殘差點(diǎn)相連。遍歷完所有殘差點(diǎn)后，將所配對(duì)的正負(fù)殘差點(diǎn)的排列分別建模為兩條染色體，在算法執(zhí)行過程中，正殘差點(diǎn)對(duì)應(yīng)的染色體作為參考染色體，其排列順序始終固定不變，將負(fù)殘差點(diǎn)對(duì)應(yīng)染色體作為初始染色體。圖1左側(cè)表示對(duì)5個(gè)正殘差點(diǎn)和4個(gè)負(fù)殘差點(diǎn)的編號(hào)結(jié)果，數(shù)字的上標(biāo)代表該點(diǎn)的極性，右側(cè)為使用所有殘差點(diǎn)及其最小相關(guān)邊編碼得到的結(jié)果，正殘差點(diǎn)對(duì)應(yīng)的染色體可表示為{1B,1+,2+,3+,4B,4+,5+}，其相應(yīng)的負(fù)殘差點(diǎn)染色體編碼為{1-,2B,2-,3B,3-,5B, 4-}，枝切線的總長度則通過計(jì)算同一基因座上所對(duì)應(yīng)的正負(fù)殘差點(diǎn)的距離之和求出?？梢钥闯?，經(jīng)過該方法編碼，所得到的染色體對(duì)應(yīng)的枝切線總長度較小。

圖1　所有殘差點(diǎn)及其最小相關(guān)邊編碼

Step3初始化種群。經(jīng)過Step2產(chǎn)生一條枝切線總長度較短的初始染色體后，對(duì)該條染色體采用最近鄰與隨機(jī)2-opt方法產(chǎn)生初始種群。即隨機(jī)選擇初始染色體中的兩個(gè)基因，交換其位置產(chǎn)生一條新的染色體，若新的染色體所對(duì)應(yīng)的枝切線總長度小于初始染色體對(duì)應(yīng)的枝切線總長度，則將新的染色體放入種群中，否則在初始染色體中重新選擇兩個(gè)基因，重復(fù)上述步驟。最終產(chǎn)生枝切線整體長度較短的初始種群。

Step4適應(yīng)度函數(shù)。使用枝切線總長度的倒數(shù)作為適應(yīng)度函數(shù)，即該條染色體所對(duì)應(yīng)的枝切線長度越短，其適應(yīng)度越高。

Step5選擇操作。使用隨機(jī)遍歷選擇，相比與輪盤賭，該方法可進(jìn)一步提高選擇的公平性。

Step6交叉和模擬退火操作。將父代種群兩兩隨機(jī)分組，使用部分匹配交叉對(duì)每組中的染色體P1和P2執(zhí)行交叉操作，得到子代染色體C1和C2，計(jì)算父代和子代對(duì)應(yīng)的枝切線總長度分別為f(Pi)和f(Ci)，其中i=1,2，使用Metropolis準(zhǔn)則接受新解，如式(2)所示。

(2)

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

Step7變異和模擬退火操作。隨機(jī)選擇染色體中的兩個(gè)基因進(jìn)行交換，交換前和交換后的染色體分別為S1和S2，之后采用Metropolis準(zhǔn)則接受新解S2，方法步驟同Step6。

Step8執(zhí)行降溫操作，并判斷是否達(dá)到最大遺傳代數(shù)，若是，則輸出當(dāng)前適應(yīng)度最高的染色體；若不是，則轉(zhuǎn)Step5繼續(xù)執(zhí)行。

得到輸出的染色體后，將其與參考染色體中同一基因座的基因一一對(duì)應(yīng)，即可確定殘差點(diǎn)組合方式，之后在干涉相位圖中用枝切線連接對(duì)應(yīng)正負(fù)殘差點(diǎn)，最后使用洪泛法繞開枝切線進(jìn)行相位解纏。

3　實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)中使用的是伊朗BAM地區(qū)的兩幅SAR圖像，在Matlab中(計(jì)算機(jī)配置：CPU i5-4200M 內(nèi)存4 GB)經(jīng)配準(zhǔn)、干涉圖生成、去平和濾波之后得到如圖2所示的700×700干涉相位圖，圖3為經(jīng)四點(diǎn)環(huán)路積分法檢測出的殘差點(diǎn)，其中正殘差點(diǎn)(白色)2914個(gè)，負(fù)殘差點(diǎn)(黑色)2913個(gè)。

Goldstein法設(shè)置的枝切線如圖4所示，從圖5所示的局部放大圖可以看出在殘差點(diǎn)密集處，枝切線不僅較長，而且由于殘差點(diǎn)的重復(fù)連接，導(dǎo)致形成了許多封閉區(qū)域，這在后期將形成解纏“孤島”。

圖2　干涉相位圖　　　　　圖3　殘差點(diǎn)圖

圖4　Goldstein法設(shè)置的枝切線　　　圖5　枝切線局部放大圖

表1中給出了Goldstein法和本算法設(shè)置枝切線的量化對(duì)比?？梢钥闯觯啾扔贕oldstein法，本算法所設(shè)置的枝切線長度縮短36.95%， 封閉區(qū)域數(shù)量減少了98.64%，在運(yùn)算時(shí)間上也得到了一定的改善。

表1　枝切線設(shè)置結(jié)果對(duì)比

本算法所設(shè)置的枝切線如圖6所示。由于本算法是將正負(fù)殘差點(diǎn)進(jìn)行配對(duì)連接，或是將殘差點(diǎn)與邊界相連，因此，最終所設(shè)置的都是一些小段的枝切線，沒有圍成大面積的封閉區(qū)域。

為了進(jìn)一步驗(yàn)證算法在解纏精度上的有效性，將本算法和Goldstein法、質(zhì)量圖引導(dǎo)法的解纏結(jié)果進(jìn)行對(duì)比，圖7至圖9分別為這三種算法的解纏結(jié)果。

圖6　本算法設(shè)置的枝切線　　圖7　本算法的解纏結(jié)果

圖8　Goldstein法解纏結(jié)果　圖9　質(zhì)量圖引導(dǎo)法解纏結(jié)果

同時(shí)，使用解纏誤差ε和總運(yùn)算時(shí)間作為量化對(duì)比指標(biāo)。其中，解纏誤差ε[11]一般采用式(3)定義。

(3)

表2　不同算法的解纏結(jié)果對(duì)比

從解纏結(jié)果中可以看出，Goldstein枝切線法形成了大量的解纏孤島，如圖8中的黑色區(qū)域所示，同時(shí)，其解纏誤差也高于其他兩種算法。質(zhì)量圖引導(dǎo)法的解纏精度和本文算法相當(dāng)，但由于該方法需要不斷對(duì)納入鄰接表中的元素進(jìn)行排序，所以其運(yùn)行時(shí)間很長。而本文算法將部分殘差點(diǎn)預(yù)處理與優(yōu)化算法結(jié)合，不僅在運(yùn)行時(shí)間上具有一定的優(yōu)勢，同時(shí)，解纏精度也得到了一定的提高，此外，所圍成的封閉區(qū)域數(shù)量也大幅減少，這將為后期高程的反演工作帶來極大的便利。

4　結(jié)　語

針對(duì)Goldstein枝切線法存在的問題，本文提出了一種新的INSAR相位解纏算法。該算法根據(jù)殘差點(diǎn)的分布特點(diǎn)，將部分殘差點(diǎn)預(yù)處理與改進(jìn)模擬退火遺傳算法相結(jié)合，用以實(shí)現(xiàn)對(duì)枝切線的優(yōu)化設(shè)置。對(duì)真實(shí)INSAR數(shù)據(jù)的處理結(jié)果表明，本文提出的算法不僅在較短的時(shí)間內(nèi)得到了整體長度較短的枝切線，而且使封閉區(qū)域的數(shù)量大幅降低，提高了解纏精度，相比與常用的局部解纏算法，有一定的優(yōu)越性。

[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ìn)粒子群算法的二維相位解纏方法[J].電波科學(xué)學(xué)報(bào),2012,27(6):1116-1123.

[4] 曲小寧,張妍,馮大政.TSP理論在二維相位解纏的應(yīng)用[J].系統(tǒng)工程與電子技術(shù),2011,33(4):742-745.

[5] 魏志強(qiáng),金亞秋.基于蟻群算法的InSAR相位解纏算法[J].電子與信息學(xué)報(bào),2008,30(3):518-523.

[6] 李平湘,楊杰.雷達(dá)干涉測量原理與應(yīng)用[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] 于海璁,陸鋒.一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法[J].測繪學(xué)報(bào),2014,43(1):89-96.

[9] 傅文淵,凌朝東.布朗運(yùn)動(dòng)模擬退火算法[J].計(jì)算機(jī)學(xué)報(bào),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。國家自然科學(xué)基金項(xiàng)目(61461044)；寧夏高等學(xué)校科學(xué)技術(shù)研究項(xiàng)目(NGY2014007)。于向明，碩士生，主研領(lǐng)域：INSAR信號(hào)處理。孫學(xué)宏，副教授。劉麗萍，教授。張成，教授。

TP701

A

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