基于混沌布谷鳥優(yōu)化的二維Tsallis交叉熵建筑物遙感圖像分割

吳一全 周建偉

（1.南京航空航天大學(xué)電子信息工程學(xué)院，南京，211106；2.城市空間信息工程北京市重點(diǎn)實(shí)驗(yàn)室，北京，100038；3.數(shù)字出版技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京，100871）

引 言

近年來遙感成像技術(shù)的迅速發(fā)展，使得獲取的遙感圖像質(zhì)量越來越高。利用遙感圖像進(jìn)行人工地物信息的自動(dòng)提取，可以有效地提升工作效率，避免繁瑣的人工調(diào)查。建筑物作為一類重要的人工地物目標(biāo)，利用遙感圖像對(duì)其進(jìn)行自動(dòng)提取和識(shí)別在數(shù)字化城市的創(chuàng)建、地理信息更新及軍事目標(biāo)監(jiān)測(cè)等方面有著重要意義和實(shí)際應(yīng)用價(jià)值[1-3]。建筑物遙感圖像分割是建筑物目標(biāo)提取的首要且關(guān)鍵的一步，圖像的分割效果對(duì)提取的準(zhǔn)確性有著重要的影響[4]。

閾值分割作為一類有效的遙感圖像分割方法，其最關(guān)鍵的是快速地選擇一個(gè)特定閾值，最終實(shí)現(xiàn)分割[5-7]。其中關(guān)注最多的是基于熵的方法，Kapur等人[8]最早提出了基于一維最大熵法，這種方法簡單有效，能得到較好的結(jié)果，然而因?yàn)闊o法反映圖像的局部信息，對(duì)于有噪圖像的分割不是很準(zhǔn)確。Brink[9]將最大熵法推廣到二維直方圖，改善了圖像的分割結(jié)果，但是增加了計(jì)算復(fù)雜度，難以滿足實(shí)時(shí)處理的要求。Sahoo等人[10]在上述基礎(chǔ)上運(yùn)用了Tsallis熵，導(dǎo)出了基于二維Tsallis熵的分割方法，減少了運(yùn)算時(shí)間，但是分割效果不理想。為了利用內(nèi)部灰度的均勻性，文獻(xiàn)[11]導(dǎo)出了基于二維Tsallis灰度熵法，提升了圖像的分割效果，但在分割復(fù)雜背景的圖像時(shí)結(jié)果不如意。Li等人[12]給出了基于二維最小交叉熵的方法，分割的結(jié)果較準(zhǔn)確，然而與最大熵同樣存在在零點(diǎn)處無定義值的問題。針對(duì)這一問題，文獻(xiàn)[13]提出基于二維倒數(shù)交叉熵方法，避免了對(duì)數(shù)運(yùn)算，在一定程度上加快了速度，但分割結(jié)果的準(zhǔn)確性仍需提高。文獻(xiàn)[14]則結(jié)合了最小交叉熵與Tsallis熵，給出了基于二維最小Tsallis交叉熵法，使得分割結(jié)果更加精確，然而該方法的運(yùn)行時(shí)間仍舊較長，有待進(jìn)一步縮短。

為了進(jìn)一步加快閾值選取的運(yùn)算速度，人們將群智能優(yōu)化算法引入圖像閾值分割領(lǐng)域。文獻(xiàn)[15]利用遺傳算法來搜尋最大模糊熵下的最佳閾值，進(jìn)一步加快了方法的運(yùn)行速度。文獻(xiàn)[16]在二維閾值選取過程中引入粒子群優(yōu)化算法，在一定程度上減少了運(yùn)行的時(shí)間。文獻(xiàn)[17]則利用人工蜂群優(yōu)化閾值選取過程，有效地提升了方法的運(yùn)行速度。近幾年出現(xiàn)的布谷鳥搜索算法(Cuckoo search,CS)[18]相較于上述的智能優(yōu)化算法，具有算法簡便、需設(shè)置參數(shù)較少、實(shí)現(xiàn)容易、可沿較優(yōu)路徑搜索、可收斂到全局最優(yōu)且收斂速度快等優(yōu)點(diǎn)，目前已被應(yīng)用于函數(shù)優(yōu)化[19]、預(yù)測(cè)問題[20]等應(yīng)用領(lǐng)域。然而CS算法可能會(huì)陷入局部最優(yōu)點(diǎn)，為了解決這一問題，本文將混沌理論引入CS算法，利用混沌映射的偽隨機(jī)性使算法避免陷入局部最優(yōu)。

基于以上分析，本文提出了基于混沌布谷鳥搜索(Chaotic cuckoo search，CCS)的二維Tsallis交叉熵建筑物遙感圖像分割方法。首先給出了二維Tsallis交叉熵的選取公式，然后使用Logistic映射，將混沌擾動(dòng)引入布谷鳥搜索算法以加快算法的運(yùn)算速度，最后利用該混沌布谷鳥搜索算法優(yōu)化閾值的尋找過程，并以此分割建筑物遙感圖像。針對(duì)大量建筑物遙感圖像進(jìn)行實(shí)驗(yàn)，并與二維倒數(shù)交叉熵法[13]、二維Tsallis熵法[10]、基于混沌粒子群優(yōu)化(Chaotic particle swarm optimization，CPSO)的二維Tsallis灰度熵法[11]等方法進(jìn)行比較，驗(yàn)證了本文的方法分割建筑物遙感圖像時(shí)擁有明顯的優(yōu)勢(shì)。

1 二維Tsallis交叉熵閾值選取公式

設(shè)圖像f(m,n)的尺寸為M×N，灰度級(jí)總數(shù)為L，定義圖像像素點(diǎn)(m,n)的8-鄰域平均灰度f(x,y)，D一般取像素點(diǎn)的8-鄰域，W表示鄰域D中像素的個(gè)數(shù)。用h(i,j)代表二元對(duì)(f=i,g=j)在該圖像中出現(xiàn)的個(gè)數(shù)(0≤h(i,j)≤M×N)，則二元對(duì)(i,j)的聯(lián)合p(i,j)=1，由p(i,j)構(gòu)成該圖像的二維直方圖，其區(qū)域劃分如圖1所示。假設(shè)i=t,j=s兩條直線把直方圖分割為4塊區(qū)域，將圖像中亮（暗）的區(qū)域設(shè)成目標(biāo)（背景），則0，1分別表示目標(biāo)及背景區(qū)域，2，3分別表示邊界及噪聲區(qū)域。在邊界和噪聲區(qū)域，其像素點(diǎn)與整幅圖像的像素總數(shù)相比，數(shù)量很小，可以忽略不計(jì)，其p(i,j)≈ 0。

因此，目標(biāo)類和背景類的先驗(yàn)概率分別為

對(duì)應(yīng)的灰度均值向量分別為

圖1 二維直方圖區(qū)域劃分Fig.1 Division of 2-D histogram region

則圖像的二維Tsallis交叉熵為

2 混沌布谷鳥優(yōu)化的二維Tsallis交叉熵分割方法

2.1 布谷鳥搜索算法

CS算法由Yang Xinshe仿照自然界中布谷鳥的寄巢產(chǎn)卵特點(diǎn)和部分生物的萊維(Levy)飛行模式，于2009年提出。其主要思想是通過隨機(jī)游走方式產(chǎn)生候選鳥巢以及采用貪婪策略更新鳥巢位置，最終使鳥巢位置達(dá)到或者接近全局最優(yōu)解。CS算法假定了以下3個(gè)條件：

(1)布谷鳥每次僅僅產(chǎn)一只卵，孵化時(shí)鳥巢的選擇是隨機(jī)的；

(2)對(duì)于每組鳥巢，最好的可以留至下一代；

(3)可以用來放卵的鳥巢數(shù)目一定，鳥巢主人察覺布谷鳥卵的概率為Pα。

CS算法的鳥巢坐標(biāo)位置與解空間中的解一一對(duì)應(yīng)，在以上3個(gè)假定基礎(chǔ)上，CS算法利用Levy飛行隨機(jī)行走方式和偏好隨機(jī)行走方式更新鳥巢位置。

(1)Levy飛行隨機(jī)行走。主要利用式(5)產(chǎn)生新解

由于對(duì)Levy分布積分比較困難，文獻(xiàn)[21]證明了可以采用Mantegana算法實(shí)現(xiàn)等價(jià)計(jì)算，即

式中：σv=1，β=1.5。 σu求解公式為

式中Γ()表示伽馬函數(shù)。
(2)偏好隨機(jī)行走。仿照寄主察覺布谷鳥的卵后將其丟棄的想法和原理。具體操作如下：任意得到一個(gè)滿足[0,1]均勻分布的隨機(jī)數(shù)r，并與發(fā)現(xiàn)概率Pα∈[0,1]進(jìn)行比較，若r＞Pa，則按式(9)得到新解

通過上述兩種方式所得的新解均采用貪婪選擇操作，即得到新解后，將新解和原解的適應(yīng)度函數(shù)值進(jìn)行比較，與原解相比，若新解較優(yōu)，那么將新解取代原解，反之保留原解。

2.2 混沌CS算法

在標(biāo)準(zhǔn)CS算法中，隨機(jī)游走模式的單一導(dǎo)致其搜索時(shí)針對(duì)性不強(qiáng)?；煦缇哂袀坞S機(jī)性、規(guī)律性、對(duì)初值敏感等優(yōu)點(diǎn)，在可行域內(nèi)能夠搜尋到所有狀態(tài)。因此在CS算法中融入混沌序列，可以使算法更容易跳出局部最優(yōu)點(diǎn)，提升算法在后期的收斂速度，提高算法解的質(zhì)量。因此，本文使用Logistic映射的混沌擾動(dòng)算子對(duì)CS算法進(jìn)行改善，以期減少分割方法的求解時(shí)間。

Logistic映射的表達(dá)式如下

式中μ為控制變量。

為了提升算法的準(zhǔn)確性，對(duì)每一次更新的最佳鳥巢位置添加混沌擾動(dòng)，擾動(dòng)方法可由式(11)確定

式中：γ為比例系數(shù)；Xbest,d為當(dāng)代最佳位置的第d維向量；Xnewbest,d表示新的最佳位置的第d維向量；xd為當(dāng)代由式(10)產(chǎn)生的混沌序列。

2.3 方法流程圖與步驟

本文方法的基本思路為：根據(jù)建筑物遙感圖像的二維直方圖計(jì)算二維Tsallis交叉熵，采用混沌映射改進(jìn)CS算法并優(yōu)化閾值的選取過程，最終完成對(duì)建筑物遙感圖像的分割。圖2為本文方法流程圖。

本文方法具體步驟如下：

步驟1 初始化算法的基本參數(shù)：鳥巢數(shù)目n=20，發(fā)現(xiàn)概率Pa=0.25，搜索精度ε，最大迭代次數(shù)Tmax=100；

步驟2 用鳥巢位置代表圖像的二維閾值(t*,s*)，并且以隨機(jī)方式生成n個(gè)鳥巢的初始位置，根據(jù)式(3)計(jì)算初始鳥巢位置的二維Tsallis交叉熵，求得初始最小的值；

步驟3 利用式(5—8)更新當(dāng)前的所有鳥巢，求出當(dāng)前所有鳥巢的二維Tsallis交叉熵，若新鳥巢的二維Tsallis交叉熵小于原鳥巢的二維Tsallis交叉熵，則替換鳥巢位置；

步驟4 根據(jù)式(9)采用偏好隨機(jī)行走方式更新鳥巢的位置，仍舊用二維Tsallis交叉熵較小的位置取代原位置，求得當(dāng)代最小的二維Tsallis交叉熵，且和前一代的值對(duì)比，記錄最佳的鳥巢位置；

步驟5 利用式(10)和式(11)對(duì)最佳的鳥巢位置進(jìn)行混沌擾動(dòng)，并與擾動(dòng)之前進(jìn)行對(duì)比，保留二維Tsallis交叉熵更小的一組鳥巢位置；

步驟6 若未滿足設(shè)定的搜索精度或未達(dá)到最大的迭代次數(shù)，重新回到步驟3，反之繼續(xù)；

步驟7 輸出最優(yōu)閾值(t*,s*)，并以此分割建筑物遙感圖像。

圖2 本文方法流程圖Fig.2 Flowchart of proposed method

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

對(duì)于多類建筑物遙感圖像，采用本文提出的基于CS及基于CCS的二維Tsallis交叉熵法進(jìn)行了大量實(shí)驗(yàn)，并與二維倒數(shù)交叉熵法、二維Tsallis熵法、基于CPSO的二維Tsallis灰度熵法進(jìn)行對(duì)比，給出了5種方法分割后建筑物遙感圖像結(jié)果及運(yùn)行時(shí)間。受篇幅限制，現(xiàn)以其中3幅不同種類建筑物遙感圖像的分割結(jié)果加以說明，分別為建筑物遙感圖像1（500像素×274像素）、建筑物遙感圖像2（543像素×366像素）、建筑物遙感圖像3（454像素×473像素）。圖3—5分別給出了3幅原始建筑物遙感圖像及二維倒數(shù)交叉熵法、二維Tsallis熵法、基于CPSO的二維Tsallis灰度熵法、基于CS的二維Tsallis交叉熵法、基于CCS的二維Tsallis交叉熵法處理后的圖像。其中，基于CPSO的二維Tsallis灰度熵法的粒子群數(shù)為20，最大迭代次數(shù)為100；基于CS的二維Tsallis交叉熵法和基于CCS的二維Tsallis交叉熵法的最大迭代次數(shù)為100，種群規(guī)模為20，概率Pa=0.25。本文實(shí)驗(yàn)的運(yùn)行環(huán)境為Intel(R)Core(TM)i5 CPU 2.50 GHz/4 GB,Matlab R2015b。

如圖3所示，建筑物遙感圖像1中包含建筑物、道路及河流等目標(biāo)，從分割結(jié)果中看出：二維倒數(shù)交叉熵法在分割時(shí)，部分建筑物和道路連在一起，因此誤分割率很高，特征不鮮明；二維Tsallis熵法分割結(jié)果較差，未準(zhǔn)確地分割出目標(biāo)；利用基于CPSO的二維Tsallis灰度熵法得到的效果不是很理想，大部分建筑物無法分辨；而本文提出的基于CS及基于CCS的二維Tsallis交叉熵法則對(duì)建筑物輪廓及細(xì)節(jié)有著精確分割，邊緣比較完整，且可以較好地將建筑物和河流及道路分開。

圖3 建筑物遙感圖像1及其分割結(jié)果Fig.3 Remote sensing image of Building 1 and its segmentation results

如圖4所示，建筑物遙感圖像2中建筑物聚集，且具有不同形狀，復(fù)雜度較高。二維倒數(shù)交叉熵法分割較為準(zhǔn)確，但仍有一部分背景誤劃分成了建筑物；二維Tsallis熵法誤分割部分較多；基于CPSO的二維Tsallis灰度熵法未完全分離目標(biāo)和背景，多數(shù)建筑物未被分割出來，效果不佳；而本文提出的基于CS及基于CCS的二維Tsallis交叉熵法效果較好，準(zhǔn)確地將建筑物及背景分離，提取出的建筑物邊界使得紋理細(xì)節(jié)更為豐富。

如圖5所示，建筑物遙感圖像3中建筑物周圍有著植被和道路，干擾較多，分割結(jié)果顯示：二維倒數(shù)交叉熵法和二維Tsallis熵法未能準(zhǔn)確地分開建筑物與地面區(qū)域，勢(shì)必會(huì)影響之后的檢測(cè)識(shí)別效果；基于CPSO的二維Tsallis灰度熵法仍有部分道路誤分割，且部分建筑物邊緣模糊殘缺，紋理特征不太豐富；本文提出的基于CS及基于CCS的二維Tsallis交叉熵法可以很好地將建筑物和道路分開，同時(shí)在有噪聲干擾狀況下，仍然能將建筑物準(zhǔn)確地分割出來，說明抗噪性能強(qiáng)。綜合所有結(jié)果，采用本文提出的方法對(duì)建筑物遙感圖像進(jìn)行分割，能得到明顯良好的效果。

表1列出了5種分割方法的最佳分割閾值及運(yùn)行時(shí)間。從表1能夠看出，二維倒數(shù)交叉熵法和二維Tsallis熵法由于窮舉了所有像素值，因此所需的運(yùn)行時(shí)間較長；基于CPSO二維Tsallis灰度熵法因?yàn)槭褂昧巳褐悄芩惴?，相?duì)縮短了時(shí)間；而本文提出的基于CS及基于CCS的二維Tsallis交叉熵法方法進(jìn)一步縮短了時(shí)間，且基于CCS比基于CS的方法平均節(jié)省了50%。

為了進(jìn)一步分析CS算法及混沌CS算法的收斂特性，選取實(shí)驗(yàn)中的一幅圖像，分別用兩種方法進(jìn)行50次獨(dú)立實(shí)驗(yàn)并取平均，繪出迭代次數(shù)與目標(biāo)函數(shù)的關(guān)系圖如圖6所示。從圖中能夠得到，CS算法會(huì)在迭代的過程中落入局部極值點(diǎn)，迭代更新的后期收斂速度變得緩慢，平均需要40次迭代達(dá)到收斂，影響算法的運(yùn)行速度；而混沌CS算法卻并沒有陷入局部最優(yōu)，收斂速度快，在16次迭代左右就已經(jīng)收斂，大大減少了算法運(yùn)行時(shí)間。

圖4 建筑物遙感圖像2及其分割結(jié)果Fig.4 Remote sensing image of Building 2 and its segmentation results

圖5 建筑物遙感圖像3及其分割結(jié)果Fig.5 Remote sensing image of Building 3 and its segmentation results

圖6 CS算法和CCS算法的迭代過程圖Fig.6 Iterative process of CS algorithm and CCS algorithm

表1 5種方法的最佳分割閾值及運(yùn)行時(shí)間比較Tab.1 Comparison of five methods in optimal thresholds and running time

4 結(jié)束語

針對(duì)建筑物遙感圖像，本文提出了基于混沌布谷鳥優(yōu)化的二維Tsallis交叉熵分割方法。Tsallis交叉熵綜合考慮了分割前及分割后圖像信息的差異性和關(guān)聯(lián)性，可以提高遙感圖像的分割效果。首先給出了二維Tsallis交叉熵的閾值選取公式，然后采用布谷鳥搜索算法優(yōu)化閾值搜索過程，同時(shí)為了進(jìn)一步提升方法的收斂速度，利用Logistic映射生成的混沌序列來改進(jìn)布谷鳥搜索算法，有效地減少了方法的運(yùn)行時(shí)間。針對(duì)建筑物遙感圖像進(jìn)行了大量實(shí)驗(yàn)，并與二維倒數(shù)交叉熵法、二維Tsallis熵法、基于CPSO的二維Tsallis灰度熵法等方法相比，本文方法能夠更準(zhǔn)確地分割建筑物遙感圖像，運(yùn)算時(shí)間更短，可認(rèn)為是一種行之有效的建筑物遙感圖像分割方法。