基于Halton序列改進蝠鲼算法的K-means圖像分割

董躍華，李 俊，朱東林

(江西理工大學信息工程學院，江西 贛州 341000)

0 引言

近年來，圖像分割備受研究者關注，其對未知世界具有重要意義，作為圖像處理的關鍵步驟，其目的是從圖像中提取感興趣的目標信息，如今在醫(yī)學、農業(yè)、海洋等領域有重要研究價值。聚類圖像分割也已經得到成功的研究。其中，K-means是最常見且最簡單的聚類方法[1]，但K-means存在隨機性較大且易陷入局部最優(yōu)的缺陷，無法合理地控制聚類中心。隨著研究的不斷深入，智能優(yōu)化算法在數據挖掘、路徑優(yōu)化、圖像處理等領域被廣泛應用，由于其在優(yōu)化方面表現卓越，很多學者將其應用到圖像處理領域，該類算法已成為科研領域的研究重點。文獻[2]采用螢火蟲算法對K-means聚類算法進行優(yōu)化，使得其在醫(yī)學圖像分割問題中具有更好的性能指標；文獻[3]提出了一種新型的動態(tài)粒子群優(yōu)化算法，用于優(yōu)化K-means圖像分割的質量，較傳統(tǒng)的K-means聚類分割算法具有更好的直觀效果，解決了傳統(tǒng)K-means聚類在圖像分割中分割質量和效率方面的問題； 文獻[4]對灰狼優(yōu)化(Grey Wolf Optimizer，GWO)算法進行改進，用于衛(wèi)星圖像的聚類分割；文獻[5]采用正余弦算法(Sine Cosine Algo-rithm,SCA)解決傳統(tǒng)聚類方法存在的聚類中心不合理和收斂速度慢等問題；文獻[6]為解決K-means聚類效果的缺陷，提出了一種新型改進麻雀搜索算法(Modified Sparrow Search Algorithm,MSSA)，采用Logistic的自適應因子及小孔成像反向學習提升了麻雀搜索算法的尋優(yōu)能力，使得優(yōu)化后的K-means圖像分割的質量更佳。上述研究證實了智能優(yōu)化算法對傳統(tǒng)的K-means 聚類算法進行優(yōu)化，能取得較好的聚類及圖像分割結果。

蝠鲼覓食優(yōu)化(Manta Ray Foraging Optimization,MRFO)算法是最近流行的一種群智能優(yōu)化算法，具有靈活的搜索能力，全局搜索能力強，但是缺乏局部開發(fā)能力[7]。例如個體之間順序搜索，依賴性較大，缺乏主動性，導致整體搜索范圍較好，但局部搜索性能較差。當前，研究者們已經注意到這一點，陸續(xù)開展研究，例如文獻[8]將分數微積分(fractional calculus)與MRFO進行結合，來修正蝠鲼運動的方向，通過CEC 2017測試函數驗證了該算法的可行性，將其應用于圖像分割問題中具有良好的效果；文獻[9]提出一種基于圖的并行分割算法，該算法采用并行結構,將圖像分為多個區(qū)域,充分利用不相鄰區(qū)域的處理具有并行性的特點,對多個區(qū)域進行并行處理；文獻[10]將梯度優(yōu)化器與MRFO結合，以此來降低算法陷入局部最優(yōu)的概率，在單目標及多目標的經濟排放調度中，具有較好的效果；文獻[11]采用自適應加權及混沌思想改進MRFO，從而高效地處理熱力學中的問題；文獻[12]采用反向學習初始化種群，增大種群的多樣性，將其應用于閾值圖像分割問題中，具有較好的分割質量；文獻[13]在MRFO中加入了一種攻擊能力，使其跳出局部最優(yōu)找到全局最優(yōu)解，進而應用于3D Tsallis的圖像分割問題中；文獻[14]將SA融合MRFO，并應用于PID控制器中，融合之后的算法明顯優(yōu)于其他算法的控制;此外，文獻[15]采用反向學習及融合模擬退火算法，提高了算法的收斂速度，將其應用于分數階比例積分導數(FOPID)控制器中，具有較好的控制性能。雖然這些工作能夠取得一定的成效，但不能完全平衡算法的局部搜索和全局搜索，當面對高維復雜問題時，解的質量存在不可靠性。

1 標準蝠鲼覓食優(yōu)化算法

MRFO算法模擬蝠鲼在海洋中不同的捕食策略，通過不同的合作方式進行覓食，從而實現對一定空間內解的搜索。該算法主要分為鏈式覓食、 螺旋覓食和空翻覓食3個階段。

1.1 鏈式覓食(Chain foraging)

蝠鲼群體覓食時，第一個蝠鲼向最好的食物源挪動，而其他蝠鲼則向最好的食物源和它前方的蝠鲼移動，依次形成一條鏈狀的捕食鏈。具體數學模型可表示為

(1)

1.2 螺旋覓食(Cyclone foraging)

在一定空間內，蝠鲼群體中的每一個蝠鲼發(fā)現優(yōu)質食物源時，會首尾相接，呈螺旋形狀向食物源匯聚。蝠鲼種群在匯聚的過程中，其運動方式逐漸從單一的鏈條狀轉變成螺旋狀，圍繞最佳的食物源開展搜索。螺旋覓食過程的數學模型可表示為

(2)

(3)

1.3 空翻覓食(Somersault foraging)

當某個蝠鲼發(fā)現食物源后，將食物源視作一個支點并繞其旋轉、空翻至另一個新位置，以引起其他蝠鲼的注意。對蝠鲼群體而言，空翻覓食是圍繞食物源展開多樣的搜索，它可以有效改善下一次蝠鲼群體的搜索方式。其數學模型為

(4)

式中:S為空翻因子，決定空翻的距離;r2和r3是服從[0,1] 均勻分布的兩個隨機數。隨著S取值不同，蝠鲼個體會空翻至搜索空間中與當前位置關于最優(yōu)解對稱的位置。

2 基于Halton序列改進蝠鲼覓食優(yōu)化算法

2.1 Halton序列初始化種群

原始蝠鲼覓食優(yōu)化算法采用隨機函數初始化種群,該方法得到的種群分布具有較大的隨機性，能夠覆蓋到一定的空間范圍，但是它的不確定性也同樣存在，不能保證每次隨機初始化種群后的分布都是均勻的，甚至密集性較大，從而導致種群搜索速度慢,種群多樣性不足。針對上述問題,本文引入Halton序列產生偽隨機數來初始化種群,該方法充分考慮了個體分布的均勻性，偽隨機數的遍歷性能夠使個體均勻地分布在空間內的不同位置，這樣能夠提升初始種群的質量，為后續(xù)算法的搜索提供有效的條件，加快了算法的收斂速度[16]。

對于二維的Halton序列,其實現過程為:選取兩個質數作為基礎量,通過對兩個基礎量不斷展開,從而組合成一系列均勻分布且不重復的點,其展開過程數學模型描述為[17]

(5)

σ(n)=c0x-1+c1x-2+…+cmx-m-1

(6)

H(n)=[σ1(n),σ2(n)]

(7)

式中:n∈N;x為大于等于2的質數，表示Halton序列基礎量；ci∈{0,1,2,…,p-1}，為常數；σ(n)為定義的序列函數；H(n)為最后得到的二維均勻Halton序列。為清晰地描述Halton初始化種群的優(yōu)勢，給出算法采用Halton的個體分布圖。初始種群分布如圖1所示。兩個基礎量分別為2和3。

圖1 初始種群分布圖Fig.1 Initial population distribution map

從圖1中可以清晰地看出，Halton生成的種群位置非常均勻，而隨機初始化的部分個體位置相對集中，Halton序列能夠使算法更好地開發(fā)出不同位置的解，提升算法的全局性搜索能力。

2.2 基于折射原理的反向學習

反向學習(Oppposite-Based Learning,OBL)是一種常用的改進智能優(yōu)化算法的方法，這種計算當前位置的反向解的學習方式能很好地提升算法的搜索范圍，使得算法的尋優(yōu)性能在前期得到提升[18]。雖然優(yōu)化性能有所提升，但方法單一，缺乏靈活性，在后續(xù)優(yōu)化中存在陷入局部優(yōu)化的可能。為了解決上述問題，本文采用折射反向學習(Refracted Oppposite-Based Learning, ROBL)[19-20]來更新發(fā)現者的位置。原理是把光的折射定律引入到反向學習中，利用折射定律開發(fā)更深層次的解。具體原理如圖2所示。

圖2 折射反向學習原理圖Fig.2 Schematic diagram of refracted oppposite-based learning

在圖2中，X軸上的解的搜索區(qū)間為[a,b],Y軸表示法線，l與l′表示入射光線與折射光線的長度，α和β分別為入射角和折射角,O為[a,b]的中點，由圖中的幾何關系及折射率的定義可知

(8)

令p=l/l′,代入上式可得

(9)

將公式進行變形，得到折射反向解為

(10)

顯然，p=m=1時，可轉換為一般的反向學習，由此看出，一般的OBL得到的解比較固定，手段單一。而ROBL則可以通過調整參數動態(tài)獲取新解，降低算法陷入局部最優(yōu)的概率。當優(yōu)化的問題維度上升，折射反向學習算式為

(11)

2.3 新型高斯變異

變異是群智能優(yōu)化算法常用的手段，主要是用來擺脫算法原有機制的束縛，開拓出新的搜索方式[21]。MRFO算法在前期具有較好的搜索能力，但后期個體尋優(yōu)接近最優(yōu)解，個體之間相互靠攏，這樣就可能陷入局部最優(yōu)。因此，本文引入一種新型的高變異函數GMFi(t)[22]，能夠有效改善此類情況，通過指數函數改變后期個體搜索范圍，跳出局部最優(yōu)狀態(tài)。GMFi(t)具體算式為

(12)

xi(t+1)=GMFi(t)xi(t)

(13)

2.4 改進的蝠鲼覓食優(yōu)化算法

為提升蝠鲼覓食優(yōu)化算法的尋優(yōu)能力，本文提出了一種Halton序列蝠鲼覓食優(yōu)化(HMRFO)算法，該算法采用Halton初始化種群，使得個體分布均勻，為尋優(yōu)做好充分的準備；再采用折射反向學習增大個體的搜索能力，最后采用新型高斯變異來降低算法陷入最優(yōu)的概率,綜合提升算法的尋優(yōu)能力。具體偽代碼流程如下。

Algorithm:The framework of the HMRFO

Input

M：最大迭代次數

N：種群數量

Output：Xbest,fg

采用Halton序列初始化種群

t=1;

While(t

Fori=1 toNdo

If rand<0.5 then

Ift/M

根據式(3)更新個體位置

Else

根據式(2)更新個體位置

End if

Else

根據式(1)更新個體位置

End if

根據式(11)更新個體位置

Compute the fitness of each individual,getXbest,fg,Xworst

Fori=1 toNdo

根據式(4)更新個體位置

End for

根據式(13)更新個體位置

Compute the fitness of each individual;

Get a newXbest,fg;

End while

Get the finalXbest,fg。

2.5 基于HMRFO的K-means圖像分割

傳統(tǒng)K-means算法的原理是隨機選擇K個聚類中心，這樣選取的方式具有不確定性，導致最后的結果存在較大的差異，且容易陷入局部最優(yōu)。因此需要選擇合適的初始聚類中心。智能優(yōu)化算法已經成功地應用于K-means中，改善了其隨機性與陷入局部最優(yōu)的缺陷。本文采取改進的蝠鲼覓食優(yōu)化算法對K-means進行優(yōu)化，使得初始聚類中心得到良好的控制。其目標函數為

(14)

式中:Xi為圖像的一個像素灰度值；Yj為第j個聚類中心。利用HMRFO得到最佳初始聚類中心數使其目標函數的適應度值最小。具體分割流程主要包括以下兩部分：

1) 通過HMRFO的全局搜索能力對初始聚類中心進行優(yōu)化，找到圖像點集中合理且最佳的初始聚類中心位置；

2) 將HMRFO輸出的初始聚類中心在K-means算法中進行圖像分割。

具體流程圖如圖3所示。

圖3 基于HMRFO的K-means圖像分割流程圖Fig.3 Flow chart of K-means image segmentationbased on HMRFO

3 性能測試與分析

3.1 時間復雜度分析

時間復雜度是衡量一個算法的重要指標，因此需要平衡算法的尋優(yōu)能力與時間復雜度，才能說明得到有效的提升?；镜腗RFO僅分為鏈式覓食、螺旋覓食及空翻覓食3個階段，其中鏈式覓食與螺旋覓食在同一個循環(huán)內。設種群數量為N，最大迭代次數為T,維度為D，因此MRFO的時間復雜度可以歸納為

O(MRFO)=O(T(O(cyclone foraging+chain foraging)+
O(somersault foraging)))=
O(T(ND+ND))=O(TND)。

(15)

設引入折射反向學習的計算時間為t1，引入新型高斯變異的計算時間為t2，原算法與改進后算法的初始化階段可忽略不計。

因此HMRFO可以歸納為

O(HMRFO)=O(T(O(cyclone foraging+
chain foraging)+O(t1))+O(somersault foraging)+
O(t2))=O(TND)。

(16)

可以看出，HMRFO的時間復雜度沒有發(fā)生根本的變化。對于迭代次數較大的情況,小幅度的增加可以忽略不計。若能有效地提升算法的尋優(yōu)能力，這些增加會具有重大意義。

3.2 基準函數測試

為了驗證HMRFO算法的有效性及可行性，本文選取了6個基準測試函數來驗證其函數優(yōu)化能力。具體測試函數信息如表1所示。為了證明HMRFO具有競爭性，將其與MRFO,GWO,Particle Swarm Optimization(PSO)[23],Whale Optimization Algorithm (WOA)[24]這4種算法進行對比。各算法的迭代次數與種群數量分別為500，100。實驗環(huán)境為Window10 64bit，軟件為Matlab2019b，內存為16 GiB，處理器為Intel?CoreTMi5-10200H CPU@2.40 GHz。各算法的尋優(yōu)結果如表2所示，分別計算了各算法30次運行結果的平均值、最優(yōu)值和標準差。

表1 測試函數信息Table 1 Test function information

表2 各算法尋優(yōu)結果Table 2 Optimization results of each algorithm

為了能清晰地看出各算法在各函數中的尋優(yōu)情況及收斂效果，給出了各算法的平均收斂圖，如圖4所示。

從圖4中可看出，HMRFO的收斂效果較好，基本都能最快找到精度最高的解，尤其在F4(x)～F6(x)這些函數中，收斂效果具有較大的優(yōu)勢。可見，靈活的搜索機制使得算法在尋優(yōu)過程中迅速找到最優(yōu)解，從而證明了HMRFO的有效性。

圖4 各算法收斂效果Fig.4 Convergence effect of each algorithm

4 圖像分割實驗

目前，圖像處理已經應用于多個領域，陸地上的圖像已經得到了良好的發(fā)展，但在水下圖像中仍具有研究價值。因此,為了展現研究價值，本文選取了4幅水下圖像作為測試圖像，數據來源于文獻[25]。選取 PSO,MSSA,MRFO,HMRFO 這4種算法對K-means 進行優(yōu)化，并實現圖像分割，同時也將傳統(tǒng)K-means 的圖像分割效果一起進行對比。由于聚類中心個數K值對K-means 聚類效果的影響較大，K值選擇不當會對結果產生很大的影響，因此本文將K值統(tǒng)一設為3，避免K值的干擾。算法的參數進行統(tǒng)一設置：種群數量為30，最大迭代次數為100。各算法分割效果見圖5。

單純從人的視覺無法判斷分割圖像的細節(jié)差異，因此本文引入了3種常見的圖像分割的度量指標PSNR，SSIM及FSIM，用于衡量各算法的分割質量及優(yōu)化能力。

PSNR主要用于測量分割后的圖像與原始圖像之間的差值，具體算式為

(17)

(18)

式中:ERMSE為像素的均方根誤差；M×Q為圖像的大小；I(i,j)為原始圖像的像素灰度值；Seg(i,j)為分割圖像的像素灰度值。PSNR值越大，代表圖像分割質量越好。

圖5 各算法分割效果Fig.5 Segmentation effect of each algorithm

SSIM是處理圖像中邊緣信息內容的度量。它是通過評估處理圖像與原始圖像的高頻內容(邊緣信息)的相似性來測量的。SSIM值越高，說明圖像質量與算法優(yōu)化的性能越好。SSIM的算式為

(19)

式中:μI與μseg分別為原始圖像與分割圖像的平均值；σI與σseg分別為原始圖像與分割圖像的標準差；σI,seg為原始圖像與分割圖像的協(xié)方差；c1,c2是用來確保穩(wěn)定性的常量。

FSIM是反映原始圖像和分割圖像之間特征相似性的度量指標，用于評價圖像的局部結構和提供對比度信息。FSIM的取值范圍一般為[0,1]，其值越接近于1，代表分割效果越好。FSIM的定義如下

(20)

SL(C)=SPC(C)SG(C)

(21)

(22)

(23)

(24)

(25)

其中：Ω為原始圖像的所有像素區(qū)域；SL(C)為相似性得分，C為像素點；PCm(C)為相位一致性度量；T1和T2為常量；G為梯度下降；E(C)為在位置C上的響應矢量大小，并且尺度為n；ε為一個極小的數值；An(C)為尺度為n的局部大小。具體分割度量指標如表3所示。

表3 各算法分割性能Table 3 Segmentation performance of each algorithm

在圖5中，單純從肉眼來看，HMRFO優(yōu)化后的圖像更加清晰，尤其是在Test 02～03中，圖像整體性較好，其他算法優(yōu)化后的圖像相對過于粗糙。通過表3可直觀地看出，HMRFO在4個圖像中的最優(yōu)指標是最多的，尤其在Test 03中，HMRFO優(yōu)化后的指標均是最好的，K-means的效果最差，其他算法的最佳指標比較少。因此，可以看出HMRFO優(yōu)化后的K-means圖像分割具有較好的普適性，且分割質量較好;同時，也說明了多策略的引入進一步提升了算法的尋優(yōu)能力。

5 結論

K-means聚類算法的初始聚類中心隨機性較大且容易陷入局部最優(yōu)，導致圖像分割質量較差，為此，本文提出了一種基于HMRFO的K-means圖像分割，HMRFO采用Halton序列初始化種群，使得個體分布更加均勻，進一步提升了種群的多樣性，再引入一種折射反向學習，提高算法的全局視野，最后采用高斯變異防止算法出現早熟現象，平衡算法的局部與全局性搜索。通過6個標準測試函數驗證了HMRFO的有效性及可行性。由其優(yōu)化K-means的圖像分割中可以看出，HMRFO優(yōu)化后的圖像分割質量比其他算法更佳，且普適性較好。但從表3中可看出，同一幅圖像中，不一定能保證3個性能指標均是最佳的，因此下一步的工作重點是平衡所提算法在同一幅圖像中的所有性能指標。