改進SOA算法在焊縫圖像分割中的應用

余勝威,丁建明,曹中清

(1.西南交通大學 機械工程學院， 四川 成都 610031;

2.西南交通大學 牽引動力國家重點實驗室，四川 成都 610031)

?

改進SOA算法在焊縫圖像分割中的應用

余勝威1,丁建明2,曹中清1

(1.西南交通大學 機械工程學院， 四川 成都 610031;

2.西南交通大學 牽引動力國家重點實驗室，四川 成都 610031)

摘要:提出一種基于改進的自適應人群搜索算法(ISOA)的焊縫圖像分割方法，該算法通過對基本人群搜索算法的高斯隸屬度函數以及隸屬度參數計算的改進，自適應確定搜索步長，實現對n尺度圖像進行n-1個閾值尋優計算。實驗結果表明：對比PSO，GA和SA算法，ISOA算法具有收斂速度快、穩定性強、精度高、全局尋優等特點，有效地克服了傳統SOA算法易陷入局部最優和收斂速度慢等缺陷，可滿足實際工程需求。

關鍵詞：多尺度分割;ISOA;類方差;PSO;GA;SA

一種閾值尋優的最感性的方法是采用窮舉法，基于Otsu的窮舉法較簡潔，但是計算量大[8]，采用窮舉法對本文“car測試圖像”進行閾值尋優，當閾值個數為2時，CPU耗時15.41 s，當閾值個數為3時，CPU耗時為4 095.01 s，計算量成千倍增加，采用窮舉法對n-1個閾值進行計算，有n(L-n+1)n-1種[7]可能，因此從算法執行效率上考慮，窮舉法不適合用于閾值優化分析。然而n-1閾值尋優可轉換為一個多尺度的函數優化問題。

本文采用生物智能算法進行圖像分割。生物智能算法能夠解決傳統算法不能解決的問題，如當尋優目標函數是離散的、不可微或者含有一些非線性相關參量時，傳統算法根本無法解決。粒子群算法在搜索域內，粒子以一定的速度更新當前最優粒子和最優種群。PSO簡單易實現，然而易出現早熟等現象，以致不能全局尋優[10]。遺傳算法是一種采用適者生存，優勝劣汰的隨機搜索方法，GA直接對結構對象進行操作，不存在求導和函數連續性的限定，但GA存在收斂性差、耗時長等缺點[11]，給圖像分割閾值全局尋優帶來困難。模擬退火算法(SA)是一種啟發式隨機搜索算法，通過模擬固體物質的退火過程，克服了窮舉法計算量過大的缺點，然而計算量大，Hammouche等研究表明[12]，PSO圖像分割在CPU執行時間，結果穩定性及精確度等方面都優于GA，DE，ACO，SA和TS。人群搜索算法(SOA)[13]，通過隨機挑選一定數量的志愿者，基于一定的啟發式信息、搜索規則和策略等，模擬人群搜索/覓食行為。目前該算法已用于函數優化、IIR數字濾波器設計、電力系統無功優化等領域[14]，與DE，APSO，CFPSO和CLPSO算法比較，SOA算法具有較好的全局尋優能力、較快的收斂速度和算法魯棒性[15]。本文提出一種改進的自適應SOA算法(ISOA)，并將該算法應用于圖像分割中，分割效果較滿意。本文主要研究性能相對較好的SOA，PSO，GA和SA算法，同時也為了驗證ISOA能用于多尺度圖像分割。

1N尺度閾值分割模型

多尺度圖像分割是一種有效的圖像分割方法，而n尺度閾值尋優的魯棒性對于圖像分割則是一個難點。本節提供一種更精確的解決方法，下面介紹一些基本的表達式[9]。

給定一個最大灰度值L(本文直接設為256)，對于一副灰度圖像而言，閾值取值為{0,1,2，…，L-1}，定義

其中i表示具體的灰度值，0≤i≤L-1，N表示圖像的像素個數，hi表示i灰度值的個數，pi表示概率值，則灰度的平均值為：

二維閾值尺度問題能夠拓展到n維閾值尺度，考慮n-1個不同閾值尺度tj，j=1,2,3,…,n-1，具體的表達式如下：

(1)

其中：x表示H×W圖像的寬度坐標值；y表示H×W圖像的高度坐標值，其像素二維函數為f(x,y)，待分割圖像將被分成D1，D2，…，Dn類，組成F(x,y)。

最簡單并且最快速的閾值尋優方法是，直接找出不同類之間最大方差對應的灰度值，一般定義如下：

(2)

其中：j代表一個具體的類；wj表示第j類的概率；μj為第j類的均值；具體的D1，D2，…，Dn類的wj和μj表示如下：

(3)

(4)

從而一個n尺度閾值問題降維為一個函數尋優問題，尋找閾值tj，使不同類間方差目標函數最大，目標函數如下：

(5)

相應的算法核心代碼如下：

fitR(j)=sum(probR(1:xR(j,1)))*(sum((1:xR(j,1)).*probR(1:xR(j,1))/sum(probR(1:xR(j,1)))) - sum((1:Lmax).*probR(1:Lmax)) )^2;

forjlevel=2:level-1

fitR(j)=fitR(j)+sum(probR(xR(j,jlevel-1)+1:xR(j,jlevel)))*(sum((xR(j,jlevel-1)+1:xR(j,jlevel)).*probR(xR(j,jlevel-1)+1:xR(j,jlevel))/sum(probR(xR(j,jlevel-1)+1:xR(j,jlevel))))- sum((1:Lmax).*probR(1:Lmax)))^2;

end

fitR(j)=fitR(j)+sum(probR(xR(j,level-1)+1:Lmax))*(sum((xR(j,level-1)+1:Lmax).*probR(xR(j,level-1)+1:Lmax)/sum(probR(xR(j,level-1)+1:Lmax)))-sum((1:Lmax).*probR(1:Lmax)))^2;

fitBestR(j)=fitR(j);

%xR為種群個體，level為分割尺度，Lmax=256；

% probR為Pi概率值。

隨著灰度級的增加，目標函數尋優將變得更復雜，計算量大大增加；因此，選取哪種算法進行優化模型分析，成為我們需要考慮的問題。

最近生物智能算法被廣泛應用于目標優化分析，它是一種高效的智能算法。

2算法分析

隨著智能算法的日新月異，算法的改進顯得越來越重要，其計算速度、穩定性、全局尋優能力是當前研究的熱點問題，改進的自適應人群搜索算法(ISOA)立足簡化SOA算法[15]，通過對隸屬度函數以及慣性權值的改進，簡化了算法結構，縮短了算法執行時間，提高了算法穩定性以及全局尋優能力等。

2.1　搜索步長的確定

基本SOA算法，采用個體在當前種群中的相對位置排序，進行隸屬度計算，增大了計算復雜度；而ISOA不確定推理行為的隸屬度隨迭代次數線性遞增：

(6)

uij=ui+rand·(1-ui)，j=1,…,D

(7)

其中，ui為第i代個體對應目標函數值φ的隸屬度，本文采用線性隸屬函數，在最佳位置有最大隸屬度值umax=1.0，最差位置有最小隸屬度umin=0.011 1；iter和itermax分別為當前迭代次數和最大迭代次數；uij為j維搜索空間第i代個體對應目標函數值φ的隸屬度；D為搜索空間維數。

由不確定推理可得步長：

(8)

其中，αij為j維搜索空間的搜索步長；δij為高斯隸屬函數參數，計算如下：

(9)

(10)

式中：pg(t)為種群全局最優值；rands(·)為[-1, 1]隨機變量；ω是慣性權值，Wmin和Wmax分別為相應的最小最大權值。

2.2　搜索方向的確定

采用第i代個體的利己方向、利他方向以及預動方向隨機加權平均，確定搜索方向如式(11)：

(11)

式中：pi(t)為種群個體最優值；xi(t-1)為上一代個體；sign(·)為符號函數；?1和?2為[0，1]隨機數。

2.3　個體位置的更新

確定搜索方向和步長后，進行位置更新：

Δxij(t+1)=αij(t)dij(t)

(12)

xij(t+1)=xij(t)+Δxij(t+1)

(13)

相應的算法核心代碼如下：

% maxgen=itermax,t=iter迭代次數

% 慣性權值,Wmax=0.9,Wmin=0.1

W=Wmax-t*(Wmax-Wmin)/maxgen;

% 隸屬度值Umax=1.0,Umin=0.011 1

u=Umin+t*(Umax-Umin)/maxgen;

U=u+(1-u)*rand; % 隸屬度

T= sqrt(-log(U)); % 搜索步長

% 確定利己方向，gbest為pi(t)

Diego(i,:) = (gbest(i,:) - pop(i,:));

% 確定利他方向，zbest為pg(t)

Dialt(i,:) = (zbest - pop(i,:));

% 確定預動方向，pop_1為上一代個體

Dipro(i,:) = (pop(i,:) - pop_1(i,:));

% 確定經驗梯度方向

Di(i,:) = sign(W* Dipro(i,:) +rand*Diego(i,:) +rand*Dialt(i,:));

% 確定高斯函數的參數，N_PAR=D

C(i,:) =W*abs(zbest.*rands(1,N_PAR));

Bc(i,:) =C(i,:)*T;% 確定搜索步長

pop(i,:)=pop(i,:)+Di(i,:).*Bc(i,:); % 更新位置

3實驗結果及分析

電腦配置為AMD A8-4500M(1.9 GHz)，2 GB可用內存，軟件MATLAB(2014a)。圖像大小均為200×400，圖1為不同圖像及其直方圖。

圖1　不同的圖形及對應的直方圖Fig.1 Histogram of different image

初始化粒子速度均設定為0，粒子的位置在可行域內隨機產生，搜索空間取決于圖像灰度值的范圍，也就是說如果圖像是8位色圖，那么粒子的尋值空間為0~255。ISOA，PSO，GA和SA都是參數化的算法，為了增強對比效果，選取迭代次數為50，種群數為30(等效于SA迭代次數(鏈長)為30)。其中，PSO算法粒子速度滿足[vmin,vmax]=[-5, 5]，GA算法交叉概率為pc=0.8，變異概率為pm=0.2，SA初始溫度T=1 000，降溫速率q=0.5，本文中閾值尺度2≤n≤5，選取適應度估計值、CPU計算時間以及算法穩定性3個指標進行算法對比研究。

3.1　適應度值估計

因為算法是隨機產生個體的，對于每一個尺度n，分別采用ISOA，PSO，GA和SA算法運行20次，統計各算法得到的適應度均值和標準偏差值，如表1所示。

如表1所示，閾值個數分別為2，3，4和5，尺度對應為3，4，5和6。盡管對于每一尺度，各算法計算的最優適應度值是相近的，然而隨著閾值個數的增加，相對標準偏差值也增大。相比較，ISOA算法穩定且不易陷入局部最優。

表1　不同圖像分割算法得到的適應度平均值±STD

3.2　CPU處理時間

衡量算法有效性的一個重要指標，就是CPU計算時間[9]，CPU計算時間越小，算法越能夠被考慮來應用于實際控制器，算法執行時間過長，則算法本身有待改進。表2為不同算法的處理時間對比。

表2　不同圖像分割算法的CPU處理時間

如表2所示，ISOA算法表現更好的性能，用時最短，其次是PSO，再次是GA，最后是SA算法。Hammouche等研究表明[12]，PSO圖像分割是在CPU執行時間，結果穩定性、結果精確度等方面優于GA和SA。

為了直觀的觀察ISOA算法的分割結果，圖2為不同尺度下的ISOA算法分割結果。

圖2　圖像分割結果(從左到右表示閾值個數為2，3，4，5)Fig.2 Image segmentation results(n=2,3,4,5 for image from left to right)

如圖2所示，隨著閾值個數增加，圖像分割更加細致；當閾值個數為5時，即將圖像分為6部分，圖像顯得更加平滑。

3.3　算法全局尋優分析

考慮到生物智能算法都具有隨機性特點，即每一次運行結果是不完全相同的，因此有必要進行算法的全局尋優能力分析。

為了定義算法的全局尋優能力，本文采用標準偏差來衡量，如式(14)所示。

(14)

式中：STD是標準偏方差；σi是第i次算法運行得到的適應度值；μ是σ的平均值；N是算法執行的次數，在此取N=20。STD值越小，則表示算法的穩定性越強。閾值取值分別為2,3,4,5，針對每一個閾值，算法均運行N次，統計數據得如表1所示結果。

為了提高表1的可讀性，圖3表示采用不同算法，對不同尺度下的不同圖像的適應度值標準偏差計算統計圖。

如圖3所示，GA是最不穩定的，ISOA是相對最穩定的，綜合各項指標，ISOA是一種性能最佳的圖像分割算法。

4結論

1)提出了一種ISOA算法的焊縫圖像分割算法，ISOA算法通過改進高斯隸屬函數以及自適應慣性權值，達到性能改進的目的，實驗結果表明，該算法具有快速收斂、全局尋優能力等特點。

圖3　不同的圖像不同的STD值(從左到右表示2，3，4，5個閾值)Fig.3 STD values for image segmentation results(n=2,3,4,5 for image from left to right)

2)將ISOA算法成功應用于焊縫圖像分割，實現了Otsu多級閾值下的焊縫圖像分割，對比于PSO,Ga和SA算法，基于適應度值，STD和CPU計算時間性能指標，試驗結果表明，采用ISOA算法性能更好，不易陷入局部最優，且隨著閾值個數的增加，分割效果越好。

3)一方面，焊縫圖像分割的自動化能夠很好地實現焊縫的定位，且快速檢測表面有明顯缺陷的焊縫，另一方面，能夠降低人工目測檢測周期長，操作困難等缺陷。由于焊縫圖像受外界干擾影響較大，就需要保證算法的適應性，ISOA算法根據用戶設定的分類數，自動進行圖像的閾值最大化分割，并且分割結果能夠很好的自動識別焊縫，因此基于ISOA算法在T型焊縫圖像分割的成功應用，具有廣泛的應用前景，例如PID參數整定、遙感圖像分割、視頻分析等領域。

參考文獻：

[1] 李娜，李元香.基于自適應粒子群算法和數據場的圖像二維閾值分割[J]．計算機輔助設計與圖形學學報,2014,24(5):628-635.

LI Na, LI Yuanxiang.Image segmentation with two-dimension threshold based on adaptive particle swarm optimization and data field[J]．Journal of Computer-Aided Design & Computer Graphics, 2014, 24(5):628-635.

[2] 余勝威,丁建明.轉向架構架焊縫表面質量檢測研究[J].鐵道科學與工程學報,2015,12(2):402-406.

YU Shengwei, DING Jianming.Quality detection reaearch on bogie frame welding surface[J].Journal of Railway Science and Engineering, 2015,12 (2):402-406.

[3] 梁硼.X射線焊縫圖像缺陷自動提取與識別技術研究[D].南京：南京航空航天大學,2012.

LIANG Peng.Research on technology of automatic extraction and identification for weld defects in X-Ray image[D].Nanjing: Nanjing University of Aeronautics and Astronautics, 2012.

[4] 余剛.鋼制對接焊縫缺陷超聲相控陣檢測圖像特征與識別[D].南昌：南昌航空大學,2012.

YU Gang.Defect image characterization and recognition of steel butt welds based on ultrasonic phased array[D].Nanchang：Nanchang Hangkong University, 2012.

[5] ZHANG Jing,JIN Yanxia.Genetic algorithm for weld image edge detection[J].IEEE,2010:511- 513.

[6] Xianghua Hou,Honghai Liu.Welding image edge detection and identification research based on canny operator[J].IEEE,2012:250-253.

[7] Brink A D.Minimum spatial entropy threshold selection[J].IEE Proceedings on Vision Image and Signal Processing, 1995, 142(3)：128-132.

[8] Kulkarni R V, Venayagamoorthy G K.Bio-inspired algorithms for autonomous deployment and localization of sensor nodes[J].IEEE Transactions, 2010, 40(6)：663-675.

[9] Pedram Ghamisi, Micael S Couceiro, Jón Atli Benediktsson, et al.An efficient method for segmentation of images based on fractional calculus and natural selection[J].Expert Systems with Applications, 2012, 39(16): 12407-12417.

[10] 胡衛東,曹文貴.基于粒子群BP網絡混合算法的邊坡穩定性評價[J].鐵道科學與工程學報,2015,2(1):66-71.

HU Weidong, CAO Wengui.Slope stablitity evaluation based on hybrid algorithm of particle swarm optimization and BP neural network[J].Journal of Railway Science and Engineering, 2015,2(1):66-71.

[11] 鄧連波,史峰,莫輝輝.物流配送車輛路徑問題多代競爭遺傳算法[J].鐵道科學與工程學報,2015,2(5):75-79.

DENG Lianbo, SHI Feng, MO Huihui.Muilt-generation compete genetic algorithm for logistics distribution vehicle routing problem[J].Journal of Railway Science and Engineering, 2015,2(5):75-79.

[12] Hammouche K, Diaf M, Siarry P.A comparative study of various meta-heuristic techniques applied to the multilevel thresholding problem[J].Engineering Applications of Artificial Intelligence, 2010, 23(5)：676-688.

[13] 戴朝華,陳維榮,朱云芳,等.IIR數字濾波器設計的搜尋者優化算法[J].西南交通大學學報, 2009, 44(6): 871-876.

DAI ChaoHua, CHEN Weirong, ZHU Yunfang, et al.IIR digital filter design via seeker optimization algorithm[J].Journal of Southwest Jiaotong University, 2009, 44(6): 871-876.

[14] Dai Chaohua, Chen Weirong, Zhu Yunfang, et al.Reactive power dispatch considering voltage stability with seeker optimization algorithm[J].Electric Power System Research, 2009, 79(10): 1462-1471.

[15] 余勝威,曹中清.基于人群搜索算法的PID控制器參數優化[J].計算機仿真,2014,31(9): 347-350.

YU Shengwei, CAO Zhongqing.Optimization parameters of PID controller paraters based on seeker optimization algorithm[J].Computer Simulation，2014,31(9): 347-350.

(編輯陽麗霞)

Improved seeker optimization algorithm application in weld image segmentation

YU Shengwei1, DING Jianming2, CAO Zhongqing1

(1.College of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China;

2.State Key Laboratory of Traction Power, Southwest Jiaotong University, Chengdu 610031, China)

Abstract：This paper present's a new novel method which is called improved seeker optimization algorithm .Gaussian membership function and its parameters of traditional SOA algorithm are optimized, and the step length is determined by uncertainty reasoning based on adaptive principle.Besides, improved SOA is able to decide the n-1 optimal for n-level threshold on a given image.Compared with PSO, GA and SA algorithm, testing results show that improved SOA enhances the performance in terms of convergence speed, stability, solution accuracy and global optimality.ISOA could also greatly overcome the shortcomings of traditional methods, such as local optima and slow convergence speed.Hence, improved SOA can be widely employed in practical engineering.

Key words：multi-scale segmentation; ISOA; class variance; PSO; GA; SA

通訊作者：丁建明(1981-)，男，四川巴中人，博士，從事機械設計、故障診斷研究；E-mail:fdingjianming@126.com

基金項目：國家自然科學基金重點資助項目(61134002)

收稿日期：2015-06-11

中圖分類號：TP391.4

文獻標志碼：A

文章編號：1672-7029(2015)06-1471-07