一種改進(jìn)的蟻群算法在高光譜遙感圖象分類中的應(yīng)用

孫 可, 殷守林, 劉 杰

(沈陽師范大學(xué) 科信軟件學(xué)院, 沈陽 110034)

?

一種改進(jìn)的蟻群算法在高光譜遙感圖象分類中的應(yīng)用

孫 可, 殷守林, 劉 杰

(沈陽師范大學(xué) 科信軟件學(xué)院, 沈陽 110034)

針對原始蟻群算法在高光譜遙感圖象分類中收斂速度慢,結(jié)果不精確的缺點(diǎn),提出了一種改進(jìn)的蟻群算法,并把基于改進(jìn)蟻群算法的特征選擇應(yīng)用在高光譜遙感圖象分類中,從而建立一種新的高光譜遙感圖象分類模型。模型分為3部分:基于傳統(tǒng)蟻群算法原理,提出新的蟻群算法信息素更新方法;使用改進(jìn)后的蟻群算法,令螞蟻在平面上隨機(jī)選擇一個隨機(jī)投影到平面上的特征,在所有特征中,使用判別函數(shù)來確定哪條路徑最優(yōu),隨后形成特征組合;根據(jù)特征組合,使用極大似然分類器對遙感圖象進(jìn)行分類。實(shí)驗(yàn)結(jié)果表明,基于改進(jìn)的蟻群算法更能有效的對高光譜遙感圖象進(jìn)行分類。

蟻群算法; 特征選擇; 高光譜遙感圖象分類; 信息素; 極大似然分類器; 特征組合

0 引 言

近年來,模擬自然界動物行為產(chǎn)生了人工智能算法,如最新的智能算法:磁鐵優(yōu)化算法[1]、頭腦風(fēng)暴算法[2]、狼群算法、貓群算法以及蟻群算法[3]等,其快速發(fā)展已經(jīng)應(yīng)用在很多領(lǐng)域。這些智能算法在高光譜遙感圖象分類中也得到了廣泛的應(yīng)用[4-6],陳善靜等[7]提出了一種新的結(jié)合空-譜二維特征蟻群組合優(yōu)化和支持向量機(jī)方法對高光譜圖象進(jìn)行分類,該方法首先使用一類蟻群在樣本空間進(jìn)行搜索,然后使用另一類蟻群在光譜維空間進(jìn)行搜索,得到最大間距波段并對其進(jìn)行組合,提取最優(yōu)特征波段。王立國等[8]提出了結(jié)合擬態(tài)物理學(xué)優(yōu)化(APO)算法的高光譜圖象波段選擇方法,首先對圖象進(jìn)行自空間劃分,然后選取適應(yīng)度函數(shù)。文獻(xiàn)[9]提出了一種基于人工蜂群算法的高光譜圖象波段選擇方法,大大提高了圖象分類的精確度。

在地表覆蓋物中,為區(qū)分它們的細(xì)微差別,高光譜遙感提供了非常高的光譜分辨率圖象數(shù)據(jù)[10]。但是大量的圖象數(shù)據(jù)又給研究人員帶來了分析與解釋上的難題,先前的研究結(jié)果表明,高維數(shù)據(jù)空間大多是空的[11],這表明主要應(yīng)用的數(shù)據(jù)結(jié)構(gòu)存在于一個子空間中。因此,有必要降低數(shù)據(jù)維度而不失原始數(shù)據(jù)的準(zhǔn)確性。

特征選擇和特征提取[12]可以降低數(shù)據(jù)維度,但特征提取策略往往是復(fù)雜的。大多數(shù)情況下,針對高光譜圖象的分類,可能會產(chǎn)生輻射降低或者混響信息的現(xiàn)象,特征選擇策略可以儲備各種地面上的信息,但是大量的高光譜圖象波段以及波段之間的強(qiáng)關(guān)聯(lián)信息使得不能做出一些特征選擇的方法。假設(shè)每個特征是獨(dú)立的,則不能獲得理想的降維,高光譜圖象中包含的豐富信息也不能被充分挖掘。因此,有必要研究一種有效的特征選擇方法選取能夠在不損失有用信息的情況下,利用該特征代表圖象的多光譜特性。

已有高光譜特征選擇方法存在最優(yōu)和次優(yōu)的局限性,針對該提出了一種改進(jìn)的蟻群算法特征選擇。在此過程中,首先將所有的特征隨機(jī)地映射到平面上,每個螞蟻在平面上隨機(jī)地選擇一個特征,然后根據(jù)判定函數(shù)決定在特征中哪一條路最優(yōu)。其中,選擇2個判別函數(shù),使用極大似然分類器分類選擇特性,實(shí)驗(yàn)結(jié)果證明了本方案的有效性。

1 蟻群算法概述

蟻群算法是根據(jù)螞蟻的習(xí)性而設(shè)計的一種智能優(yōu)化算法,算法的迭代過程如下。

設(shè)n為空間中元素的個數(shù),且用1,2,…,n表示元素的序號,螞蟻數(shù)量為m,元素i與j之間的距離為dij(i,j=1,2,…,n),t時刻路徑(i,j)上的信息量為τij(t)。在算法運(yùn)行之初,每一條路徑都有相等的信息量τij(t),設(shè)τij(t)=C(C為常數(shù)) ,則在t時刻,在元素i上的螞蟻k(k= 1,2,…,m) 由公式(1) 選擇下一個元素j。

其中:ηij(t)為t時刻路徑(i,j)上的能見度,是一個局部啟發(fā)式函數(shù),表示由元素i轉(zhuǎn)移到元素j的啟發(fā)程度;β表示啟發(fā)信息的重要程度;allowedk={0,1,…,n-1}表示螞蟻k當(dāng)前能選擇的元素集合;tabuk為禁忌表,作用是記錄螞蟻k已經(jīng)走過的元素。

一只螞蟻對應(yīng)一個元素,螞蟻按照式(2)來更新該邊上的信息素:

式中,ξ∈[0,1]為隨機(jī)參數(shù),τ0為常數(shù)。

當(dāng)所有螞蟻遍歷完所有元素后,用式(3)(4)更新各路徑上的信息素:

其中,ρ為信息素?fù)]發(fā)系數(shù);1-ρ為信息素殘留因子;為防止信息的無限積累,通常設(shè)置0<ρ<1;Δτij表示本次循環(huán)中路徑(i,j) 上的信息素增量;Lgb為到目前為止找出的全局最優(yōu)路徑。

2 改進(jìn)的蟻群算法

在傳統(tǒng)蟻群算法中,由于使用隨機(jī)比例狀態(tài)轉(zhuǎn)移原則,螞蟻總是選擇當(dāng)前產(chǎn)生的最優(yōu)解,從而易于陷入局部最優(yōu)解而產(chǎn)生早熟。為了使螞蟻能夠去選擇其他解,須增大選擇概率范圍,采用式(5)的狀態(tài)轉(zhuǎn)移方程去實(shí)現(xiàn)該功能。

其中,q為[0,1]區(qū)間均勻分布的隨機(jī)數(shù),K=1,2,…,NC。如果q<1-e-1/K,按式(5)進(jìn)行計算,否則采用輪盤賭的方式進(jìn)行狀態(tài)轉(zhuǎn)移。輪盤賭具體執(zhí)行方式如下:

1)r=rand(0,1),s=0,i=1;

2) 如果s≥r,轉(zhuǎn)到步驟4),否則順序執(zhí)行下一步;

4) 元素j即為所選元素,結(jié)束

螞蟻的信息素作為最關(guān)鍵的因素,需要有效利用,本文采用全局信息素的更新方法,對其進(jìn)行必要的調(diào)整。其具體過程是當(dāng)算法完成了一次迭代后,用式(7)對上一條路徑進(jìn)行信息素更新。

3 基于改進(jìn)蟻群算法的高光譜遙感圖象分類

高光譜圖象數(shù)據(jù)的每個波譜段可以看作一個特性,因此在高光譜圖象中,特征選擇可以轉(zhuǎn)化為波段的選擇,被選擇的子集能夠丟棄冗余的信息來降低數(shù)據(jù)集的維數(shù),在特征集X中,從n個特征中選擇m(m

3.1 特征選擇

對于分類來說,有n個特征可用于對每個模式進(jìn)行分類,X={x1,x2,…,xn}。首先將n個特征隨機(jī)地投影到平面上,每只螞蟻在平面上隨機(jī)地選擇一個特征。假設(shè)在t時刻,τij是路徑(i,j)上的信息素,n是特征集大小,m是蟻群中的螞蟻數(shù)量。其中信息素由式(6)、式(7)計算,初始設(shè)置Δτij(0)=0,選擇概率由式(5)計算,參數(shù)α和β控制信息素和啟發(fā)信息ηij的相對重要性。其中:

式中Jij是特征之間的判別函數(shù)。

對于改進(jìn)蟻群算法的特征選擇,在每次迭代的初始時期,所用特征是隨機(jī)選擇的。隨著迭代次數(shù)的增加,螞蟻將會選擇相同的路徑走,最后,特征子集對應(yīng)的最優(yōu)判別函數(shù)就是最佳結(jié)果。

3.2 圖象分類

具體流程如下:

1) 初始化參數(shù):設(shè)置參數(shù)α、β,最大循環(huán)次數(shù)Nmax,初始時刻信息量Δτij(0)=0,訓(xùn)練樣本總數(shù)M。

2) 計算各特征之間的相關(guān)系數(shù)rij;初始化異質(zhì)樣本比例系數(shù)為υ,數(shù)量為0;初始循環(huán)次數(shù)N=1。

3) 執(zhí)行改進(jìn)的蟻群算法。

Step 1 設(shè)定螞蟻數(shù)目k=1;

Step 2 螞蟻隨機(jī)選擇一個特征yi開始出發(fā);

Step 3 第k只螞蟻根據(jù)式(5)計算特征yi到y(tǒng)j的狀態(tài)轉(zhuǎn)移概率;

Step 4 根據(jù)狀態(tài)轉(zhuǎn)移概率選擇候選特征,如果候選特征與該訓(xùn)練樣本之間的判別函數(shù)值大于設(shè)定的閾值,則保留此特征并存于樣本子空間中,否則選擇下一個樣本;

Step 5 若樣本子空間中的樣本數(shù)小于異質(zhì)樣本數(shù)K(K=υM),螞蟻繼續(xù)搜索否則向下執(zhí)行;如果當(dāng)前樣本子空間判別函數(shù)達(dá)到最大值,設(shè)定k=k+1,根據(jù)式(6)和式(7)更新螞蟻信息素,螞蟻移動到y(tǒng)j,設(shè)置i=j,否則,轉(zhuǎn)到2)。

Step6 如果判別函數(shù)大于最大值,則保留螞蟻異質(zhì)樣本。

4) 循環(huán)次數(shù)增加1,即N=N+1。

5) 如果循環(huán)次數(shù)超過最大值,迭代停止,輸出此時的判別函數(shù)值的特征。否則轉(zhuǎn)到3)。

3.3 判別函數(shù)

在高光譜成像技術(shù)的具體應(yīng)用中,采用的判別函數(shù)分別是Bhattacharya距離和Jeffries-Matusita距離。

3.3.1 Bhattacharya距離

其中,n是類別的個數(shù);Jij(B)是第i個類與第j個類之間的Bhattacharya距離;μi是第i個類的平均向量;∑i第i個類的協(xié)方差矩陣。

3.3.2 Jeffries-Matusita距離

其中,n是類的個數(shù);JM是第i個類與第j個類之間的Jeffries-Matusita距離。

假設(shè)在以上2種距離計算中有類高斯分布,Bhattacharya 距離和Jeffries-Matusita距離作為距離測量法,獲得的距離越大,蟻群預(yù)期值越大,那么得到的解最優(yōu)。

4 實(shí)驗(yàn)仿真及分析

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

為了說明提出算法的可行性和高效性,在Pentium(R) Dual-Core 2.6 GHz,內(nèi)存為2.0 G的硬件系統(tǒng)和Windows XP,MATLAB2014a軟件平臺環(huán)境下將本文提出的算法用于遙感圖象分類實(shí)驗(yàn)。對比本文基于改進(jìn)的蟻群算法高光譜遙感圖象分類(IAC-HRS)、傳統(tǒng)蟻群算法高光譜遙感圖象分類(AC-HRS)[4]。研究數(shù)據(jù)來自某地區(qū)的遙感圖象,其中分為6大類數(shù)據(jù):居住地、荒地、植被、道路、湖泊和河流,總訓(xùn)練數(shù)為2 000,測試數(shù)為500,表1是各類樣本具體的數(shù)量。

表1 樣本數(shù)值Tab.1 Samples values

4.2 實(shí)驗(yàn)結(jié)果及分析

圖1是基于傳統(tǒng)蟻群算法高光譜遙感圖象分類結(jié)果,圖2是基于改進(jìn)的蟻群算法高光譜遙感圖象分類結(jié)果。分類樣本的準(zhǔn)確率如表2所示。

表2 各類樣本分類的準(zhǔn)確率Tab. 2 Accuracy of classification of various types of samples %

由圖1和圖2所知,基本蟻群高光譜遙感圖象分類方法和改進(jìn)的高光譜遙感圖象分類對遙感圖象分類都有很準(zhǔn)確的結(jié)果,但是改進(jìn)的蟻群算法對其影響更大,因?yàn)樵谙伻悍椒ㄖ懈滦畔⑺乜梢苑乐刮浵佅萑刖植拷?從而增大其灰色關(guān)聯(lián),從表2即可得知,在這6類數(shù)據(jù)中,新的算法比采用基本蟻群算法的圖象分類結(jié)果分別高1.7%、0.8%、0.4%、0.5%、1.9%、1.1%。從實(shí)驗(yàn)結(jié)果可以說明采用本文算法能較好的實(shí)現(xiàn)高光譜遙感圖象分類。

圖1 AC-HRS結(jié)果Fig.1 Result of AC-HRS

圖2 IAC-HRS結(jié)果Fig.2 Result of IAC-HRS

5 結(jié) 語

針對基本蟻群算法在高光譜遙感圖象分類中出現(xiàn)早熟,且易于陷入局部最優(yōu)的缺點(diǎn),提出了改進(jìn)的蟻群算法,在蟻群行動過程中改進(jìn)信息素,然后再進(jìn)行特征選擇,來決定哪條路徑最優(yōu),根據(jù)特征組合,使用極大似然分類器對遙感圖象進(jìn)行分類。經(jīng)過實(shí)驗(yàn)論證,本文算法在很大程度上提高了分類效果,在實(shí)際工程應(yīng)用中,也能夠發(fā)揮其價值。在以后的遙感圖象分類工作中,將會采用更為先進(jìn)的人工智能算法來提高分類準(zhǔn)確率。

[ 1 ]WOO D K, CHOI J H, ALI M, et al. A Novel Multimodal Optimization Algorithm Applied to Electromagnetic Optimization[J]. IEEE Trans Magn, 2011,47(6):1667-1673.

[ 2 ]楊玉婷,史玉回,夏順仁. 基于討論機(jī)制的頭腦風(fēng)暴優(yōu)化算法[J]. 浙江大學(xué)學(xué)報(工學(xué)版), 2013,47(10):1705-1711.

[ 3 ]夏浩東,薛云,鄧會娟,劉鳳姣. 基于蟻群算法的光譜分解方法剔除植被干擾信息[J]. 地質(zhì)力學(xué)學(xué)報, 2012,18(1):72-78.

[ 4 ]胡河山,覃亞麗. 基于蟻群算法的多光譜遙感圖像分類[J]. 杭州電子科技大學(xué)學(xué)報, 2012,32(4):88-91.

[ 5 ]吳孔江,曾永年,靳文憑,等. 改進(jìn)利用蟻群規(guī)則挖掘算法進(jìn)行遙感影像分類[J]. 測繪學(xué)報, 2013,42(1):59-66.

[ 6 ]王立國,魏芳潔. 結(jié)合遺傳算法和蟻群算法的高光譜圖像波段選擇[J]. 中國圖像圖形學(xué)報, 2013,18(2):235-242.

[ 7 ]陳善靜,胡以華,石亮,等. 空-譜二維蟻群組合優(yōu)化SVM的高光譜圖像分類[J]. 光譜學(xué)與光譜分析, 2013,33(8):2192-2197.

[ 8 ]王立國,魏芳潔. 結(jié)合APO算法的高光譜圖像波段選擇[J]. 哈爾濱工業(yè)大學(xué)學(xué)報, 2013,45(9):100-106.

[ 9 ]王立國,趙亮,劉丹鳳. 基于人工蜂群算法高光譜圖像波段選擇[J]. 哈爾濱工業(yè)大學(xué)學(xué)報, 2015,47(11):82-88.

[10]劉振林. 基于核空譜信息挖掘的高光譜圖像分類方法研究[D]. 哈爾濱:哈爾濱工業(yè)大學(xué), 2014.

[11]馮小東. 基于稀疏表示的高維數(shù)據(jù)無監(jiān)督挖掘研究[D]. 北京:北京科技大學(xué), 2015.

[12]蘇紅軍,杜培軍. 高光譜數(shù)據(jù)特征選擇與特征提取研究[J]. 遙感技術(shù)與應(yīng)用, 2006,21(4):288-293.

An improved ant colony algorithm used in Hyperspectral remote sensing image classification

SUN Ke, YIN Shoulin, LIU Jie

(Software College, Shenyang Normal University, Shenyang 110034, China)

When original ant colony algorithm is used in Hyperspectral remote sensing image classification, which has slow convergence speed and results inaccuracy. The author proposes an improved ant colony algorithm in this paper. And the feature selection based on new scheme is applied into Hyperspectral remote sensing image classification, so it builds a new Hyperspectral remote sensing image classification model. This model includes three parts: firstly, it presents new pheromone updating methods based on traditional ant colony algorithm; secondly, each ant stochastically selects a feature on the plane(features are randomly projected on a plane) based on new ant colony algorithm. In all features, it uses discrimination function to determine which road is the best; thirdly, according to the characteristics of combination, it uses the maximum likelihood classifier to classify remote sensing image. Finally, experimental results show that the new scheme based on improved ant colony algorithm is more effective to deal with Hyperspectral remote sensing image classification.

ant colony algorithm; feature selection; Hyperspectral remote sensing image classification; pheromone; maximum likelihood classifier; feature combination

2016-05-10。

國家自然科學(xué)基金資助項目(60970112)。

孫 可(1979-),男,山東滕州人,沈陽師范大學(xué)副編審,哈爾濱工業(yè)大學(xué)博士研究生。

1673-5862(2016)03-0354-05

TP391

A

10.3969/ j.issn.1673-5862.2016.03.020