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

朱必熙，張艷紅

（福建幼兒師范高等專科學校 人文科學系，福建 福州 350013）

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

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

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

1 研究方法

1.1 多尺度圖像分割方法

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

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

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

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

1.2 差分進化算法

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

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

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

1.2.1 種群初始化

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

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

1.2.2 變異算子

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

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

1.2.3 修補算子

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

1.2.4 雜交算子

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

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

1.2.5 選擇算子

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

1.3 分割對象的評價方法

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

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

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

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

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

1.4.1 分割參數種群初始化與分割評價

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

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

1.4.2 算法控制參數

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

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

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

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

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

表1 差分策略Table 1 Differential strategy

2 原型系統設計與實驗

2.1 原型系統設計

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

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

圖4 軟件原型系統界面Figure 4 Software prototype system interface

2.2 實驗數據

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

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

圖6 參考對象Figure 6 Reference objects

2.3 實驗設計

2.3.1 試驗的計算機環境

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

2.3.2 試驗的控制參數設計

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

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

3 結果與分析

3.1 實驗結果

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

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

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

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

3.2 分析與討論

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

4 結論

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

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