基于MSA 特征和模擬退火優(yōu)化的遙感圖像多目標(biāo)關(guān)聯(lián)算法

李暉暉，滑 立，楊 寧，劉 坤

（1.西北工業(yè)大學(xué) 自動化學(xué)院，西安710072；2.上海海事大學(xué) 信息工程學(xué)院，上海200135）

0 引 言

多源遙感圖像融合［1］能夠綜合利用多源互補的圖像信息以提高信息的準(zhǔn)確性與可靠性，因此在諸多領(lǐng)域得到廣泛應(yīng)用，包括軍事、測繪、地質(zhì)、農(nóng)業(yè)及災(zāi)情監(jiān)測等。而目標(biāo)關(guān)聯(lián)是融合的先決條件，概括來說就是在兩幅（或多幅）不同時間（或空間）獲取的遙感圖像中，將來自同一目標(biāo)的信息進行匹配。然后才能進行融合檢測、識別、跟蹤等一系列處理。

以往的目標(biāo)關(guān)聯(lián)方法主要指狀態(tài)濾波類方法，將目標(biāo)視為點對象，利用雷達型數(shù)據(jù)提供的目標(biāo)位置、速度、方位等運動特征進行關(guān)聯(lián)，適合密集采樣的序列圖像。如文獻［2］提出了基于目標(biāo)質(zhì)心及質(zhì)心偏移量的聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)（Joint probabilistic data association，JPDA）方法，首先將目標(biāo)與背景分割，然后計算目標(biāo)區(qū)域的質(zhì)心，以估計目標(biāo)的運動信息，最后利用JPDA 方法［3］實現(xiàn)關(guān)聯(lián)與跟蹤。文獻［4］提出了在紅外系統(tǒng)中將目標(biāo)檢測和跟蹤聯(lián)合設(shè)計的方法，利用多假設(shè)跟蹤（Multiple hypothesis tracking，MHT）算法進行目標(biāo)圖像特征點的匹配跟蹤。但由于當(dāng)前遙感成像技術(shù)一般只能獲取采樣稀疏的遙感圖像，很難預(yù)測目標(biāo)的狀態(tài)量，因此信息融合領(lǐng)域中傳統(tǒng)的利用狀態(tài)特征進行關(guān)聯(lián)的方法并不適合遙感圖像的目標(biāo)關(guān)聯(lián)。需要利用目標(biāo)圖像自身特征進行匹配，來建立新的目標(biāo)關(guān)聯(lián)準(zhǔn)則。文獻［5］結(jié)合Gabor小波提取特征以及迭代最小平方和的方法，實現(xiàn)目標(biāo)尺度變化、旋轉(zhuǎn)及平移等幾何變形時的跟蹤。文獻［6］首先提取目標(biāo)圖像的8個不變矩特征，然后通過訓(xùn)練神經(jīng)網(wǎng)絡(luò)實現(xiàn)目標(biāo)的匹配和定位。

首先需要解決圖像特征的提取問題。不變矩方法是解決圖像特征不變性的常用方法，它能夠克服視點變化對特征量的干擾，最具代表性的就是Hu 矩 特 征［7］。2005 年Rahtu 等［8］結(jié) 合 多 尺度幾何分析方法，在Hu矩特征的基礎(chǔ)上，研究了可以同時捕獲空間特性和圖像強度的多維不變描述子，構(gòu)造了多尺度自卷積矩（Multi scale autoconvolution，MSA）特征，實踐證明這是目前最穩(wěn)健的不變矩特征之一［8］。然后采用距離度量法進行特征匹配，但由于遙感信息的不確定性和特征提取算法的不精確性導(dǎo)致特征匹配結(jié)果存在誤差，因此需要進行關(guān)聯(lián)修正來消除多目標(biāo)對應(yīng)關(guān)系的模糊性。文獻［9］對上述問題提供了一種解決思路，首先利用目標(biāo)特征匹配結(jié)果構(gòu)造一個多目標(biāo)關(guān)聯(lián)代價矩陣（Association cost matrix，ACM），然后采用模擬退火算法求解使整體關(guān)聯(lián)代價最小的關(guān)聯(lián)代價矩陣，即為最終多目標(biāo)關(guān)聯(lián)結(jié)果。

本文借鑒文獻［9］的思想，將基于MSA 特征匹配和關(guān)聯(lián)代價矩陣最優(yōu)化的多目標(biāo)關(guān)聯(lián)算法應(yīng)用于海地機場飛機多目標(biāo)關(guān)聯(lián)問題上，在組合優(yōu)化過程中，著重對模擬退火算法進行了改進：在原始算法的搜索過程中設(shè)定內(nèi)、外循環(huán)迭代次數(shù)，并設(shè)計了一種新的溫度更新函數(shù)，它具有一定的自適應(yīng)性，改進了溫度控制方式，提高了搜索效率。通過海地機場6類飛機灰度圖像進行多組實驗，結(jié)果證明了本文算法具有很好的多目標(biāo)關(guān)聯(lián)效果。

1 多尺度自卷積矩（MSA）

多尺度自卷積矩（MSA）是迄今為止最為有效的不變矩。MSA 變換的基本原理：圖像中任意一點的坐標(biāo)可以用其他隨機不共線三點的坐標(biāo)線性表示，對圖像進行仿射變換時，這四個點線性表示的系數(shù)不會發(fā)生變化，因此可利用系數(shù)不變性質(zhì)構(gòu)造仿射不變量，具有較好的穩(wěn)定性。

定義圖像的仿射變換為A＝A（T，t），設(shè)圖像仿射變換前后的坐標(biāo)分別為x 和x′，即x′＝A（x）＝Tx＋t。設(shè)f 為圖像的灰度函數(shù)，仿射變換后的圖像為f′（x′）＝f（Tx＋t）。

設(shè)x0，x1，x2∈R2是f（x）定義域中的3個點，則點μα，β 可線性表示為：

μ′α，β可表示為：

式中：x′0，x′1，x′2分別 對應(yīng)于x0，x1，x2的仿射變換。可見隨機變量f（μα，β）和f′（μ′α，β）有著相同的分布，因此其數(shù)學(xué)期望也相等，這種相等關(guān)系獨立于仿射變換。MSA 方法即為變量f（μα，β）的數(shù)學(xué)期望值：

單純從數(shù)學(xué)上考慮積分元素在積分域內(nèi)的任意性，可知F（α，β）就是仿射變換的不變特征。設(shè)γ＝1－α－β，則μα，β ＝αx1＋βx2＋γx0。概率密度函數(shù)pUα，β（u）＝（pα×pβ×pγ）（u），可將式（3）改寫為：

2 關(guān)聯(lián)代價矩陣（ACM）

2.1 構(gòu)造ACM

研究兩幅遙感圖像中的目標(biāo)關(guān)聯(lián)問題，可將其看作2維分配問題［10］。假設(shè)前一圖像中有M個目標(biāo)，后一圖像中有N 個目標(biāo)?，F(xiàn)在定義一個二值分配變量：

于是可用此形成整體關(guān)聯(lián)矩陣：a ＝｛a（m，n）；m＝0，1，…，M；n ＝0，1，…，N｝，關(guān)聯(lián)的目的是找到最優(yōu)關(guān)聯(lián)矩陣使得下面的全局關(guān)聯(lián)代價最?。?/p>

提取出各目標(biāo)的MSA 特征后，通過計算目標(biāo)特征之間的歐氏距離可獲得任意兩目標(biāo)的MSA 特征匹配代價m ＝0，1，…，M；n＝0，1，…，N，其中為前一幅圖像中目標(biāo)m 的k 維MSA 特征，為后一幅圖像中的k 維MSA 特征。C ＝｛a（m，n）c（m，n）；（m ＝0，1，…，M）；（n ＝0，1，…，N）｝為關(guān)聯(lián)代價矩陣。當(dāng)m ＝n＝0時，表示兩幅圖像之間沒有發(fā)生匹配，c（0，0）可設(shè)為較大的正數(shù)。當(dāng)m或n 有一個為0時，表示存在漏檢或虛警等問題，此時令

2.2 ACM 最優(yōu)化

假設(shè)同一幅圖像中目標(biāo)種類各不相同，根據(jù)多目標(biāo)關(guān)聯(lián)的具體應(yīng)用，優(yōu)化建模需要滿足如下條件：兩幅圖像最多只能分配給對方一個目標(biāo)。數(shù)學(xué)表述即為“關(guān)聯(lián)矩陣a 中每一行和每一列只有一個值為1”，以此構(gòu)造可行的關(guān)聯(lián)矩陣。設(shè)C＝｛C1，C2，…，Ck｝為所有可行的關(guān)聯(lián)代價矩陣的集合，E（Ci）為對應(yīng)于Ci的目標(biāo)函數(shù)值。構(gòu)造關(guān)聯(lián)代價矩陣最優(yōu)化的數(shù)學(xué)模型為：E（C＊）＝minE（Ci），C＊∈C，?Ci∈C。目標(biāo)函數(shù)的最小值對應(yīng)關(guān)聯(lián)代價矩陣的最優(yōu)解，即關(guān)聯(lián)代價矩陣的能量最?。?1］。為方便表述，記a （m ，n） 為amn，考慮到實際的約束條件，進一步將目標(biāo)函數(shù)定義如下：

式中：前兩項為懲罰項，對應(yīng)具體的約束條件，只有當(dāng)前兩項均為零時，第三項才是多目標(biāo)關(guān)聯(lián)的實際代價。不考慮關(guān)聯(lián)為空的情況，設(shè)定A、B 為較大的正數(shù)，只有當(dāng)關(guān)聯(lián)矩陣a 中每一行和每一列有且只有一個元素為1、其余元素均為零時，求得的目標(biāo)函數(shù)值才會最小，對應(yīng)的關(guān)聯(lián)矩陣即為最優(yōu)關(guān)聯(lián)結(jié)果。

3 模擬退火算法

3.1 傳統(tǒng)模擬退火算法

在實際優(yōu)化問題中，有些目標(biāo)函數(shù)具有非凸性，存在局部最優(yōu)解，尤其是當(dāng)優(yōu)化問題規(guī)模增大時，迅速增加的局部最優(yōu)解數(shù)目將會導(dǎo)致全局優(yōu)化結(jié)果不夠準(zhǔn)確，同時又增加了計算量。模擬退火 算 法［12］（Simulated annealing，SA）是 基 于Monte－Carlo迭代求解策略的一種隨機尋優(yōu)算法，它來源于對固體退火過程的模擬，挖掘物理工程中固體物質(zhì)的退火降溫過程與組合優(yōu)化問題的相似性，從理論上來說，它是一種近似全局最優(yōu)算法。1983年，Krickpatric等人將模擬退火算法成功應(yīng)用于大規(guī)模組合優(yōu)化問題的求解［12］。

模擬退火過程大致分為以下三個階段：

（1）升溫階段：加熱時，固體內(nèi)部粒子隨著溫度的升高，運動增強，當(dāng)溫度足夠高，固體變?yōu)闊o序狀，內(nèi)能增大。升溫階段對應(yīng)算法的設(shè)定初始溫度（充分大）。

（2）平衡階段：退火過程中，根據(jù)熱力學(xué)定律可知在每一溫度下，系統(tǒng)自由能逐步減到最小時，即達到平衡態(tài)。等溫下熱平衡過程可用Monte Carlo方法模擬，為使結(jié)果精確，需要大量采樣，導(dǎo)致計算量很大。為提高搜索效率，1953 年，Metropolis等人提出重要性采樣法，粒子在當(dāng)前溫度T 趨于平衡態(tài)的概率為χ ＝exp（－ΔE／kT），其 中 ΔE 為 內(nèi) 能 改 變 量，k 為Boltzmann常數(shù)。依據(jù)概率χ ＞r＝random［0，1］接受該狀態(tài)為重要狀態(tài)。上述接受新狀態(tài)的準(zhǔn)則稱Metropolis準(zhǔn)則［13］，相對Monte Carlo方法來說，計算量明顯減少。

（3）冷卻階段：隨著溫度緩慢降低，固體內(nèi)部粒子運動漸趨有序，同時能量下降。本階段，采用合適的溫度衰減函數(shù)即退火策略來控制算法進程。最簡單也最常用的控制參數(shù)衰減函數(shù)為：Tk＝aTk－1＝akT0（k＝1，2，…），其中，a 是常值，取0.5～0.9。重復(fù)執(zhí)行新狀態(tài)產(chǎn)生及判斷是否接受新狀態(tài)的過程，逐漸降溫直到趨于零時，達到能量最小狀態(tài)，即求得全局最優(yōu)解。

3.2 改進模擬退火算法尋優(yōu)

模擬退火算法是一種啟發(fā)式搜索方法，它具有原理簡單、適合求解組合優(yōu)化問題中的全局（或近似）最優(yōu)解［14］、適用范圍廣等優(yōu)點，但也存在一些缺點：當(dāng)變量過多、構(gòu)造的目標(biāo)函數(shù)較復(fù)雜時，為獲得較精確的全局最優(yōu)解，初始溫度需要足夠高且降溫幅度要小，這將導(dǎo)致迭代搜索過程緩慢，求解時間太長，工業(yè)應(yīng)用較困難；在Metropolis準(zhǔn)則依概率接受新狀態(tài)環(huán)節(jié)中，有可能丟失當(dāng)前最優(yōu)解而陷入局部最優(yōu)解鄰域。

針對上述問題，為確保算法的優(yōu)化質(zhì)量，同時又提高算法的搜索效率（時間性能），本文研究了以下改進算法：選擇合適的初始溫度和終止溫度，并設(shè)計高效的退火策略，改進對溫度的控制方式，設(shè)計一個新的溫度更新函數(shù)，根據(jù)某一溫度下狀態(tài)被接受的次數(shù)來決定降溫幅度，保證溫度更新有一定的自適應(yīng)性。在搜索過程中設(shè)置雙閾值，即內(nèi)、外循環(huán)的迭代次數(shù)，若目標(biāo)函數(shù)值在當(dāng)前溫度下保持s＿max步不變，記為當(dāng)前最優(yōu)解；判斷在T （i ＋1） 溫度下求得的關(guān)聯(lián)矩陣與上一溫度 T （）i 下求得的關(guān)聯(lián)矩陣是否一致，若外循環(huán)連續(xù)iter＿max步降溫過程中搜索到的最優(yōu)關(guān)聯(lián)矩陣均保持不變，可認為得到了較高質(zhì)量的全局最優(yōu)解。具體步驟如下：

4 實驗結(jié)果及分析

為了檢驗所提方法的可行性，選用如圖1所示的海地機場6 類飛機目標(biāo)灰度圖像進行實驗（這些圖像來自于某些海地機場的IKONOS衛(wèi)星圖像，如圖2 所示，它的分辨率為1 m，大小為3000×3000像素），每幅圖像大小為128×128像素。考慮到實際圖像會受到噪聲干擾、遮擋、亮度變化等情況的影響，我們除了對圖像進行尺度縮放、旋轉(zhuǎn)、仿射變換外，還對圖像加入了不同等級的高斯白噪聲、遮擋以及亮度變化。構(gòu)成了多組6類待關(guān)聯(lián)的飛機目標(biāo)，下面給出了原始飛機目標(biāo)和其中6組仿真圖像，如圖3所示。

圖1 海地機場6類飛機目標(biāo)Fig.1 Six class aircraft targets of Haiti airport

圖2 IKONOS衛(wèi)星圖像（海地機場）Fig.2 IKONOS satellite image（Haiti airport）

圖3 6組仿真圖像Fig.3 Six group simulation image

以圖2中的飛機目標(biāo)和圖3中其仿真的待關(guān)聯(lián)目標(biāo)進行關(guān)聯(lián)為例：首先在集合｛－1，－0.75，－0.5，－0.25，0，0.25，0.5，0.75，1｝中取任意兩元素的組合構(gòu)成29對（α，β）值，進而計算各飛機目標(biāo)的29維MSA 特征向量，通過距離度量法獲得兩兩匹配概率；隨機初始化關(guān)聯(lián)矩陣a，并求得相應(yīng)的關(guān)聯(lián)代價矩陣C 如下：

然后構(gòu)造整體關(guān)聯(lián)代價矩陣目標(biāo)函數(shù)，利用改進的模擬退火算法尋優(yōu)，得到使得ACM 能量最小的關(guān)聯(lián)矩陣。此外，提取出MSA 特征后，利用最近鄰（NN）算法進行關(guān)聯(lián)實驗，與得到的最終關(guān)聯(lián)矩陣作比較。由于仿真圖像目標(biāo)組與原始目標(biāo)組的排列順序一樣，只對每個目標(biāo)圖像進行變換、加入干擾等，理論上求得的最終關(guān)聯(lián)矩陣應(yīng)該是單位矩陣。實驗結(jié)果與理論一致，可見利用關(guān)聯(lián)代價矩陣最優(yōu)化能夠克服多目標(biāo)特征匹配引起的關(guān)聯(lián)模糊性，關(guān)聯(lián)結(jié)果更加準(zhǔn)確。

引入關(guān)聯(lián)正確率指標(biāo)進行統(tǒng)計實驗分析，圖4給出了結(jié)合MSA 特征和ACM 最優(yōu)化的多目標(biāo)關(guān)聯(lián)結(jié)果，圖5 給出了結(jié)合MSA 特征和NN方法實現(xiàn)多目標(biāo)關(guān)聯(lián)的結(jié)果。可以看出，本文基于MSA 和ACM 最優(yōu)化的多目標(biāo)關(guān)聯(lián)算法結(jié)果明顯優(yōu)于利用最近鄰算法進行關(guān)聯(lián)的結(jié)果。當(dāng)圖像發(fā)生尺度縮放、旋轉(zhuǎn)、噪聲干擾、仿射變換、遮擋以及亮度變化等一系列變化時，最近鄰算法無法解決關(guān)聯(lián)模糊性，而ACM 考慮了整體關(guān)聯(lián)代價，具有一定的抗模糊性，可獲得更為有效的關(guān)聯(lián)結(jié)果。

圖4 MSA＋ACMFig.4 Association accurate ratio of MSA＋ACM

圖5 MSA＋NNFig.5 Association accurate ratio of MSA＋NN

［9］是用MSA 特征和ACM 最優(yōu)化算法解決艦船目標(biāo)的關(guān)聯(lián)問題，本文借鑒其思路，將該算法應(yīng)用于飛機圖像的多目標(biāo)關(guān)聯(lián)問題上，并著重對傳統(tǒng)模擬退火算法進行了改進。利用本文改進的模擬退火算法和傳統(tǒng)算法對每組目標(biāo)群圖像分別獨立運行50次，記錄每組運行時間（s）和目標(biāo)關(guān)聯(lián)結(jié)果數(shù)據(jù)，計算關(guān)聯(lián)正確率（%），進行統(tǒng)計分析，其對比結(jié)果如表1所示?？梢钥闯?，改進的模擬退火算法既保持了多目標(biāo)關(guān)聯(lián)結(jié)果的準(zhǔn)確性，又減少了計算量，在時間性能（搜索效率）上有了較大的提高。

表1 傳統(tǒng)SA和改進的SA實驗結(jié)果對比Table 1 Experiment comparison results of the traditional SA and improved SA

5 結(jié)束語

針對無法準(zhǔn)確估計采樣稀疏的遙感圖像中目標(biāo)的狀態(tài)信息，而利用圖像特征匹配的目標(biāo)關(guān)聯(lián)算法又無法處理大場景中多個目標(biāo)關(guān)聯(lián)引起的模糊性的問題。本文研究了基于MSA 特征和關(guān)聯(lián)代價矩陣最優(yōu)化的遙感圖像多目標(biāo)關(guān)聯(lián)算法，并著重改進了模擬退火算法尋優(yōu)過程。通過仿真實驗表明：MSA 特征可克服遙感成像中視點變化或目標(biāo)姿態(tài)變化等因素的影響，具有良好的仿射不變性和抗干擾性，是有效的關(guān)聯(lián)量；在關(guān)聯(lián)準(zhǔn)則的約束下構(gòu)造目標(biāo)函數(shù)對ACM 進行最優(yōu)化，得到的全局最優(yōu)解有效消除了多目標(biāo)之間特征關(guān)聯(lián)的模糊性；改進的模擬退火算法能夠改善執(zhí)行多次迭代搜索過程的時效性，可快速得到全局最優(yōu)解。

參考文獻：

［1］雷琳.多源遙感圖像艦船目標(biāo)特征提取和融合技術(shù)研究［D］.長沙：國防科技大學(xué)電子科學(xué)與工程學(xué)院，2008.Lei Lin.Ship feature extraction and fusion in multiple remote sensing images［D］.Changsha：School of Electronic Science and Engineering，National University of Defense Technology，2008.

［2］Bar－shalom Y，Sherlukde H M，Pattipati K R.Use of measurements from an image sensor for precision target tracking［J］.IEEE Trans AES，1989，25（6）：863－871.

［3］Bar Shalom Y.Extension of the probabilistic data association filter in multi－target tracking［C］∥Proceedings of the 5th symposium on nonlinear estimation，1974：16－21.

［4］Blackman S，Dempster R J，Broida T J.Multiple hypothesis track confirmation for infrared surveillance systems［J］.IEEE Trans AES，1993，29（3）：810－823.

［5］董學(xué)志，宋建中，韓廣良.一種利用Gabor小波特征的目標(biāo)跟蹤方法［J］.光學(xué)技術(shù)，2003，29（4）：484－486.Dong Xue－zhi，Song Jian－zhong，Han Guang－liang.Target tracking method using wavelet feature［J］.Optical Technique，2003，29（4）：484－486.

［6］姚劍，劉其真，張斌.模糊技術(shù)與神經(jīng)網(wǎng)絡(luò)的混合算法在運動目標(biāo)識別與跟蹤中的應(yīng)用［J］.計算機工程與應(yīng)用，2000，1：62－64.Yao Jian，Liu Qi－zhen，Zhang Bin.The application of combination of fuzzy algorithms and neural network in tracking moving object［J］.Computer Engineering and Applications，2000，1：62－64.

［7］Hu M K.Pattern recognition by moment invariant［C］∥Proc IRE，1961，49：1428－1436.

［8］Rahtu E，Salo M，Heikkila J.Affine invariant pattern recognition using multi－scale auto convolution［J］.IEEE Transactions on Pattern analysis and Machine Intelligence，2005，27（6）：908－918.

［9］雷琳，蔡紅蘋，唐濤，等.基于MSA 特征的遙感圖像多目標(biāo)關(guān)聯(lián)算法［J］.遙感學(xué)報，2008，12（4）：586－592.Lei Lin，Cai Hong－ping，Tang Tao，et al.A MSA feature－based multiple targets association algorithm in remote sensing images［J］.Journal of Remote Sensing，2008，12（4）：586－592.

［10］Bar－Shalom Y，Kirubarajan T，Gokberk C.Tracking with classification aided multiframe data assoeiation［J］.IEEE Transactions on Aerospace and Electronic Systems，2005，41（3）：868－878.

［11］Mandal A K，Pal S，De A K，et al.Novel approach to identify good tracer clouds from a sequence of satellite images［J］.IEEE Transactions on Geoscience and Remote Sensing，2005，43（4）：813－818.

［12］Krickpatric S，Gelett J C D，Vecchi M P.Optimization by simulated annealing［J］.Science，1983，220（4598）：671－680.

［13］Winkler G.Image Analysis，Random Fields and Dynamic Monte Carlo Methods［M］.Berlin：Springer－Verlag，1999.

［14］高尚.模擬退火算法中的退火策略研究［J］.航空計算技術(shù)，2002，32（4）：20－26.Gao Shang.Research on annealing strategy in simulated annealing algorithm［J］.Aeronautical Computer Technique，2002，32（4）：20－26.