孫 可, 殷守林, 劉 杰

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

?

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

孫 可, 殷守林, 劉 杰

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

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

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

0 引 言

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

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

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

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

1 蟻群算法概述

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

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

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

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

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

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

其中,ρ為信息素?fù)]發(fā)系數(shù);1-ρ為信息素殘留因子;為防止信息的無(wú)限積累,通常設(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ì)算,否則采用輪盤(pán)賭的方式進(jìn)行狀態(tài)轉(zhuǎn)移。輪盤(pán)賭具體執(zhí)行方式如下:

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

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

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

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

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

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

3.1 特征選擇

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

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

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

3.2 圖象分類(lèi)

具體流程如下:

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

2) 計(jì)算各特征之間的相關(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ī)選擇一個(gè)特征yi開(kāi)始出發(fā);

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

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

Step 5 若樣本子空間中的樣本數(shù)小于異質(zhì)樣本數(shù)K(K=υM),螞蟻繼續(xù)搜索否則向下執(zhí)行;如果當(dāng)前樣本子空間判別函數(shù)達(dá)到最大值,設(shè)定k=k+1,根據(jù)式(6)和式(7)更新螞蟻信息素,螞蟻移動(dòng)到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ù)超過(guò)最大值,迭代停止,輸出此時(shí)的判別函數(shù)值的特征。否則轉(zhuǎn)到3)。

3.3 判別函數(shù)

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

3.3.1 Bhattacharya距離

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

3.3.2 Jeffries-Matusita距離

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語(yǔ)

針對(duì)基本蟻群算法在高光譜遙感圖象分類(lèi)中出現(xiàn)早熟,且易于陷入局部最優(yōu)的缺點(diǎn),提出了改進(jìn)的蟻群算法,在蟻群行動(dòng)過(guò)程中改進(jìn)信息素,然后再進(jìn)行特征選擇,來(lái)決定哪條路徑最優(yōu),根據(jù)特征組合,使用極大似然分類(lèi)器對(duì)遙感圖象進(jìn)行分類(lèi)。經(jīng)過(guò)實(shí)驗(yàn)論證,本文算法在很大程度上提高了分類(lèi)效果,在實(shí)際工程應(yīng)用中,也能夠發(fā)揮其價(jià)值。在以后的遙感圖象分類(lèi)工作中,將會(huì)采用更為先進(jìn)的人工智能算法來(lái)提高分類(lèi)準(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é)報(bào)(工學(xué)版), 2013,47(10):1705-1711.

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

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

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

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

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

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

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

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

[11]馮小東. 基于稀疏表示的高維數(shù)據(jù)無(wú)監(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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(60970112)。

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

1673-5862(2016)03-0354-05

TP391

A

10.3969/ j.issn.1673-5862.2016.03.020