基于差分進化算法的圖像分割參數(shù)選擇方法研究

朱必熙，張艷紅

（福建幼兒師范高等?？茖W校 人文科學系，福建 福州 350013）

隨著衛(wèi)星發(fā)射技術(shù)、傳感器技術(shù)與數(shù)據(jù)傳輸技術(shù)的發(fā)展，遙感圖像的空間分辨率得到了很大的提高。高分辨率遙感圖像的紋理、幾何形狀更加清晰、細致，但也使地物對應的圖像更加復雜。對于如何從這些高分辨率圖像提取有意義的信息存在不少挑戰(zhàn)。基于對象的圖像分析方法 （Object-Based Image Analysis，OBIA），是以圖像對象作為分析單元，可充分利用地物光譜、紋理、幾何和拓撲關(guān)系等多種特征的圖像分析方法[1]。該方法近年在圖像分析中得到快速的發(fā)展。圖像分割獲取的對象單元是OBIA的首要和關(guān)鍵步驟，直接影響后續(xù)基于圖像對象分析與信息提取的精度。

鑒于圖像分割對基于對象的圖像分析方法的重要性，眾多學者對圖像分割進行了深入而廣泛的研究，許多適用于遙感圖像分割的算法被相繼提出[2]。其中，基于區(qū)域生長的多尺度圖像分割方法可以結(jié)合多種特征，進行多尺度的圖像分割，被廣泛應用于遙感圖像的分割[3-6]。由于地物結(jié)構(gòu)的復雜性、對地物本征尺度認識的不足、遙感圖像量測尺度的不變性及圖像分割算法中尺度參數(shù)與實際地物尺度之間聯(lián)系的物理含義不確定性等原因，在實際應用中如何選擇一個或多個合適的尺度進行圖像的分割還是一個亟待深入研究和解決的問題。

本文通過將差分進化算法（Differential Evolution，簡稱DE）引入圖像多尺度分割參數(shù)的選擇，根據(jù)參考圖與差異度準則選擇最佳的分割參數(shù)，可在一定程度上減少分割參數(shù)選擇的盲目性，這對于提高OBIA圖像分類精度及其該方法的推廣應用具有重要的意義。

1 研究方法

1.1 多尺度圖像分割方法

本研究采用Baatz和 Sch?pe 2000年提出的基于區(qū)域生長的多尺度圖像分割算法作圖像分割算法[4]。該算法根據(jù)區(qū)域虛擬合并前后的灰度特征標準差ΔStd、緊湊度ΔComp與光滑度ΔSmooth變化量，通過加權(quán)得到綜合異質(zhì)性測度HC，作為最終的合并準則測度，定義如式（1）。w1為灰度標準差變化量的權(quán)重，w2為形狀因子中緊湊度的權(quán)重[6]。

標準差變化量ΔStd根據(jù)式（2）進行計算。其中，n為通道（波段）數(shù)，pi為第i通道的權(quán)重，am和Stdmi為合并后的區(qū)域大小和第i通道的標準差，a1和a2為合并的兩個區(qū)域的大小，Std1i和Std2i為合并前兩個區(qū)域第i通道的標準差。

合并前后區(qū)域的緊湊度變化量ΔComp定義如式（3）。am、a1和 a2為合并的兩個區(qū)域的大小，lm、l1和 l2的為合并后及合并前的區(qū)域邊界長度。如果緊湊度變化量小，兩區(qū)域合并的可能性大。

合并前后區(qū)域的光滑度變化量定義如式（4），和的含義同式（2），和的為合并后及合并前的區(qū)域邊界長度，和的為合并后及合并前的區(qū)域外接矩形的周長。如果光滑度變化量小，兩區(qū)域合并的可能性大。

1.2 差分進化算法

差分進化算法是一種基于隨機并行搜索策略的啟發(fā)式優(yōu)化方法[7]。它對非線性不可微連續(xù)空間函數(shù)進行優(yōu)化、具有向種群個體學習的能力，其比遺傳算法、微粒群算法等其它進化算法更優(yōu)越的性能[8]。差分進化算法保留了基于種群的全局搜索策略，采用實數(shù)編碼、基于差分的簡單變異操作和一對一的競爭生存策略，降低了進化操作的復雜性。其特有的進化操作，使得其具有較強的全局收斂能力和魯棒性，非常適合于求解一些復雜環(huán)境中的優(yōu)化問題[9]。

差分進化算法根據(jù)需要求解的參數(shù)及問題求解空間隨機產(chǎn)生初始種群，接著通過差分變異、修補與雜交等操作，產(chǎn)生中間個體（或稱試驗個體），然后通過選擇操作生成下一代個體。算法通過不斷迭代進化，引導收索向最優(yōu)解逼近。算法的主要步驟如圖1所示。

圖1 差分進化算法的主要步驟Figure 1 Main steps of differential evolution algorithm

1.2.1 種群初始化

設NP代表種群數(shù)目，D為問題求解的維度，xi,j（0）表示初始種群（第0代）中第i個個體的第j維分量；與為第j維分量的最小與最大取值范圍。則種群初始算子用式5和6進行。

式中 i=1,2,…,NP；j=1,2,…,D;rand（0,1）表示生成[0,1]的隨機函數(shù)。

1.2.2 變異算子

差分進化算法通過將基向量加上因子縮放后的差分向量得到變異向量實現(xiàn)個體的變異。不同的基向量選擇方式與不同的差分向量個數(shù)構(gòu)成不同的差分變異算子?；蛄康倪x擇方式一般有隨機選擇和選擇當代種群中最佳個體作為基向量兩種方式；差分向量的個數(shù)一般為1或2。如式（7）的差分變異算子采取最佳個體作為基向量加上對一個差分向量進行縮放得到變異個體。

其中，xbest（g）為當前群體的最優(yōu)個體向量；xi（g）為目標（父）向量；r1≠r2≠i為集合{1，2，…，NP}中隨機選擇的2互不相同的整數(shù)；xi（g）是變異向量；F為縮放因子或稱變異概率，取值范圍為[0,1+]差分算子是差分進化算法最重要的算子。目前的DE研究者設計了一些常用的變異算子，為了區(qū)分這些算子，采用“DE/a/b”來表示，DE表示差分進化算法；a代表基向量的選擇方式 （用rand表示隨機選擇；best表示選擇當代種群中最佳個體）；b表示差分向量的個數(shù)。比較常用的有變異算子可以參考文獻[8]。

1.2.3 修補算子

變異后的個體可能落在解的搜索空間外，需采取修補手段，修補算子描述如式（8）。

1.2.4 雜交算子

DE算法通過雜交操作生成試驗向量，雜交操作通過基準向量和變異向量進行，并采用離散雜交算子提高種群的多樣性，常用的雜交算子有指數(shù)雜交算子和二項式雜交算子。指數(shù)雜交算子的交叉操作按式（9）進行。二項式雜交算子的操作可以參考文獻十一[11]。

其中，〈l〉D表示對 D 取模運算，l是[1，D]之間的一個隨機整數(shù)，整數(shù)L在1和D之間。

1.2.5 選擇算子

DE算法根據(jù)目標向量和試驗向量的適應度f（·）來選擇最優(yōu)個體，如果試驗向量的適應度 f（ui（g））好于目標向量的適應度 f（xi（g）），保留試驗向量，否則保留目標向量。選擇算子可按式（10）進行描述。

1.3 分割對象的評價方法

基于參考對象的圖像分割結(jié)果評價，通過計算分割結(jié)果與參考圖對應區(qū)域的符合度來評價分割結(jié)果的優(yōu)劣。符合度評價指標的設計直接影響分割結(jié)果優(yōu)劣的選擇。本研究采用Pont-Tuset和Marques提出的Precision and Recall （F）差異度指數(shù)作為評價指標[11]。該指標根據(jù)對參考對象和分割對象重疊情況的不同，將分割圖像的像素分為四種區(qū)域，并據(jù)此定義分割對象與參考對象的差異度度量指標F。這四種區(qū)域的定義如圖2所示，其中綠色線條包圍的區(qū)域表示參考圖班R的范圍，紅色線條包含的區(qū)域表示分割區(qū)域S的范圍，tp表示正確分割的區(qū)域 （即tp=R∩S的部分），fp 表示過分割區(qū)域（即 fp=S-（R∩S）的部分），fn表示欠分割區(qū)域（即fn=R-（R∩S）的部分），剩余的部分表示不相關(guān)區(qū)域用tn表示，即tn=I-（R∪S），I表示整個圖像?；诜指顖D班的正確分割率Rsk和基于參考圖的正確分割率RRk，按式（11）計算，并根據(jù)式（12）計算差異度度量指標Fk。所有參考圖的對應分割結(jié)果的差異度度量指標F按式（13）計算。該指標取值范圍為[0,1]：數(shù)值越小，符合度越好；等于0表示分割對象與參考對象完全一致；等于1則表示完全不一致。

圖2 圖像的像素四種區(qū)域劃分Figure 2 Pixels of images divided into four regions

1.4 基于差分進化算法的多尺度圖像分割參數(shù)選擇方法

多尺度圖像分割最優(yōu)分割參數(shù)解的求解采用差分進化算法進行優(yōu)化時，選擇分割算法的尺度參數(shù)、光譜特征權(quán)重與緊湊度權(quán)重參數(shù)作為差分進化算法的問題求解空間，將分割算法、分割評價方法及差分進化算法進行有效集成，具體集成流程如圖3所示。

圖3 基于差分進化算法的多尺度圖像分割參數(shù)選擇流程Figure 3 Selection process of multiscale image segmentation parameters based on differential evolution algorithm

1.4.1 分割參數(shù)種群初始化與分割評價

基于DE算法的多尺度圖像分割參數(shù)選擇涉及到尺度、光譜權(quán)重、緊致度權(quán)重等3個參數(shù)的優(yōu)化，其問題的求解空間為這三個參數(shù)設置的最小與最大值。根據(jù)設置的種群大小NP，采用式（6）進行分割參數(shù)種群的初始化。

根據(jù)初始化種群個體的分割參數(shù)，利用多尺度分割算法對每個個體進行分割，并利用差異度指數(shù)F對每個個體的分割結(jié)果進行評價。

1.4.2 算法控制參數(shù)

DE算法涉及種群大小NP、差分進化最大代數(shù)G、差分策略、縮放因子F、雜交概率CR、差異度終止閾值的5個控制參數(shù)。其中NP、F和CR為控制參數(shù)，其設置的數(shù)值會影響搜索最優(yōu)分割尺度參數(shù)和收斂速度；最大代數(shù)G與差異度終止閾值用于控制進化終止的條件，如果滿足條件則終止進化，將得到最佳個體的分割參數(shù)作為最優(yōu)分割參數(shù)輸出；若否，繼續(xù)差分進化。

種群大小NP：較大的群體會增加個體的多樣性，加大搜索到最優(yōu)解的可能性，但會降低收斂速度；較小的群體會加快收斂速度，但容易導致局部收斂或停止進化。

縮放因子F：用于控制搜索步長，較小的F會加快收斂，但容易導致局部收斂，出現(xiàn)“早熟”現(xiàn)象；較大的F值會增加算法跳出局部最優(yōu)解的可能性，但F＞1會降低收斂速度，根據(jù)Storn和Prince的建議F的合理取值在[0.4，1.0]范圍內(nèi)[7]，較好的初始值 F=0.5[12]。

雜交概率CR：該參數(shù)的設置主要取決于所求解的問題，對于自變量相互獨立的問題，CR可設置較小的值，而對于自變量相互依賴的問題，CR應設置較大一些。趙艷麗[9]指出，一般初始取值為0.3。

差分進化策略：依據(jù)變異和雜交算子的不同，可設計不同的差分進化策略。按“DE/a/b/c”來表示不同的差分策略。其中DE表示差分進化算法；a表示基向量的選擇方式 （用rand表示隨機選擇；best表示選擇當代種群中最佳個體）；b表示差分向量的個數(shù)，一般為1或2；c表示不同的雜交算子，分別用bin和exp表示二項式雜交和指數(shù)雜交。表1為常見的一些組合策略[6]。

表1 差分策略Table 1 Differential strategy

2 原型系統(tǒng)設計與實驗

2.1 原型系統(tǒng)設計

根據(jù)設計的基于DE算法的多尺度圖像分割參數(shù)選擇模型，在Matlab中進行原型系統(tǒng)的設計。軟件原型系統(tǒng)的圖形用戶界面如圖4所示，左側(cè)提供打開分割圖像與參考對象、設置多尺度圖像分割參數(shù)搜索空間與差分進化算法控制參數(shù)等用戶交互接口，右側(cè)提供圖像顯示，用于顯示打開圖像、參考對象及分割結(jié)果等數(shù)據(jù)。其中為了降低使用的復雜度，原型系統(tǒng)中將縮放因子F固定為0.5、雜交概率CR固定為0.3。

在利用該原型系統(tǒng)進行多尺度分割參數(shù)選擇時，用戶需要打開待分割圖像及分割圖斑的參考對象。設置完多尺度圖像分割參數(shù)搜索空間與差分進化算法控制參數(shù)及輸出結(jié)果的名稱后，單擊運行即可進行基于DE算法的多尺度圖像分割參數(shù)選擇，得到最佳的分割參數(shù)及其對應的分割結(jié)果。

圖4 軟件原型系統(tǒng)界面Figure 4 Software prototype system interface

2.2 實驗數(shù)據(jù)

為了試驗測試所使用的方法在圖像分割參數(shù)選擇的可行性，以2014年11月16日拍攝的福建省永安市燕西街道大煉村地區(qū)的部分航空彩色圖像（如圖5）為待分割圖像進行試驗。該航空圖像的大小為512×512像素、以空間分辨率為0.6 m，包含位深為8比特的紅、綠、藍三個波段（通道）。該圖像主要由耕地、房屋、道路和河流等主要地物構(gòu)成，通過在ArcMap軟件以該航空圖像為底圖，進行人工數(shù)字化，獲得20塊耕地地塊作為參考對象（如圖6所示）。

圖5 待分割航空圖像Figure 5 Aviation images to be split

圖6 參考對象Figure 6 Reference objects

2.3 實驗設計

2.3.1 試驗的計算機環(huán)境

試驗的原型系統(tǒng)軟件在64位版本的Win10操作系統(tǒng)的筆記本上運行。筆記本的CPU為Intel（R）Core（TM）i3-2310M 四核 CPU（2.10GHz）、內(nèi)存 10.0GB、顯存2GB的NVIDIA GeForce GT 550M顯卡。

2.3.2 試驗的控制參數(shù)設計

通過將分割參數(shù)的搜索空間設置為：尺度參數(shù)[10,100]、光譜權(quán)重[0.6,0.9]、緊致度權(quán)重[0.4,0.6]；將差分進化算法的參數(shù)設置為：種群數(shù)量10、進化代數(shù)10、最小誤差 1×10-16，差分策略選擇為 DE/best/1/exp。利用軟件原型系統(tǒng)進行尺度、光譜權(quán)重與緊致度權(quán)重參數(shù)的選擇實驗。

同時，為了評價差分進化算法選擇的分割參數(shù)的穩(wěn)定性，設計進行20次的最佳分割參數(shù)搜索選擇實驗，根據(jù)得到的實驗結(jié)果進行算法的穩(wěn)定性評價。

3 結(jié)果與分析

3.1 實驗結(jié)果

對20次實驗得到的的最佳分割參數(shù)按符合度從小到大排序，如表2所示。符合度最佳的分割結(jié)果如圖7所示，符合度最差的分割結(jié)果如圖8所示。

圖7 符合度最小分割結(jié)果（實驗12）Figure 7 Minimum compliance results（experiment 12）

圖8 符合度最大分割結(jié)果（實驗7）Figure 8 Maximum compliance segmentation results（experiment 7）

表2 多尺度圖像分割參數(shù)差分進化選擇結(jié)果Table 2 Differential evolution selection of multiscale image segmentation parameters

3.2 分析與討論

針對本實驗數(shù)據(jù)，從20次的實驗結(jié)果看，差分進化算法在度尺度圖像分割參數(shù)選擇時，相同的參數(shù)搜索空間范圍、相同的差分進化控制參數(shù)，得到的符合度值在[0.084,0.274]之間，均值為0.194，難以獲得統(tǒng)一的最優(yōu)分割結(jié)果，但都可以獲得相對較理想的分割結(jié)果。從20次實驗獲得的分割參數(shù)的尺度值介于[31,55]、光譜權(quán)重和緊致度權(quán)重的取值介于參數(shù)設置的搜索空間范圍之間，可以看出：不同的尺度參數(shù)、光譜和緊致度權(quán)重的組合，可以獲得相近的分割結(jié)果。從實驗數(shù)據(jù)的分析可以初步得出，多尺度圖像分割對于相同的分割結(jié)果，可以由不同的參數(shù)組合進行分割得到。

4 結(jié)論

本研究實現(xiàn)了基于差分進化方法的多尺度圖像分割參數(shù)的選擇，可根據(jù)參考圖與差異度準則選擇“最優(yōu)”的分割參數(shù)，相對于傳統(tǒng)的人工試錯的辦法選擇分割參數(shù)，減少分割參數(shù)選擇的盲目性，達到了多尺度圖像分割參數(shù)的客觀、定量化選擇的目標。

對于實驗的航空彩色圖像的“最優(yōu)”的分割參數(shù)選擇結(jié)果看，采用多尺度圖像分割方法對其進行圖像對象分割時，通過不同的尺度參數(shù)、光譜和緊致度權(quán)重的組合，可以獲得相近的分割結(jié)果。因此，鑒于分割參數(shù)的組合數(shù)量之多，僅通過人工試錯的方法，難以找到合適的分割參數(shù)。通過本文提出的方法可以獲得較理想的分割參數(shù)及分割結(jié)果。