吳圳樺，唐文艷，呂文閣，陳汝杰，侯夢華，李德源

（1.廣東工業(yè)大學(xué) 機電工程學(xué)院，廣東 廣州 510006；2.深圳市啟靈圖像科技有限公司，廣東 深圳 518114）

智能制造在全球范圍內(nèi)快速發(fā)展，已成為制造業(yè)重要發(fā)展趨勢[1]。機器視覺技術(shù)因其作為實現(xiàn)智能制造的重要技術(shù)[2]，成為了工業(yè)自動化領(lǐng)域的關(guān)注重點。在機器視覺技術(shù)中，圖像分割是關(guān)鍵的預(yù)處理操作，被廣泛應(yīng)用于工業(yè)自動化、在線產(chǎn)品檢測、文檔圖像處理等方面。圖像分割的作用是提取出具有獨特性質(zhì)的區(qū)域，供后續(xù)圖像分析、特征提取與模式識別所用。圖像閾值化分割是一種傳統(tǒng)的最常用的圖像分割方法，因其實現(xiàn)簡單、性能較穩(wěn)定而成為圖像分割中最基本和應(yīng)用最廣泛的分割方法[3-4]，主要包括大津法、最小誤差法以及最大Kapur熵法等分割方法[5]。但是當圖像中存在多個目標或多個灰度不同的區(qū)域時，使用傳統(tǒng)的單閾值分割方法并不能把圖像中的目標有效地分割出來，而常見的多閾值分割方法是通過窮舉所有閾值來獲得圖像分割的最佳閾值，隨著閾值數(shù)的增多，分割算法的計算時間大大增加，不能滿足工業(yè)使用當中的實時性要求[6]。因此，如何快速且準確地獲得最佳閾值成為圖像多閾值分割問題的研究重點。

近年來，眾多學(xué)者把圖像多閾值分割問題作為參數(shù)最優(yōu)化問題，將群體智能優(yōu)化算法或群體智能優(yōu)化算法的改進算法應(yīng)用于圖像多閾值分割問題的最佳閾值搜索上，降低了最佳閾值的搜索時間。吳亮等[7]使用改進蝴蝶優(yōu)化算法對Otsu多閾值分割方法進行快速尋優(yōu)；于洋等[8]提出了一種自適應(yīng)粒子群優(yōu)化二維Otsu的閾值分割算法，利用圖像的灰度級和鄰域灰度級構(gòu)成二元組，建立二維最大類間方差模型，結(jié)合自適應(yīng)粒子群算法估計出圖像最佳閾值；陳愷等[9]分析了二維熵分割原理，將二維熵擴展至多閾值形式，并引入螢火蟲算法，提高了最佳閾值的搜索速度。但以上方法對多閾值圖像的分割處理時間仍需數(shù)秒。

為進一步提升圖像二維熵多閾值分割的分割效率，本文嘗試引入麻雀搜索算法(Sparrow Search Algorithm, SSA)[10]并對標準麻雀搜索算法進行分析研究，針對其存在的缺陷提出了一種改進麻雀搜索算法(Improved Sparrow Search Algorithm, ISSA)。接著，通過引入積分圖方法，降低二維熵多閾值圖像分割中總信息熵的運算量，并將總信息熵作為ISSA的適應(yīng)度函數(shù)進行最佳閾值尋優(yōu)，提出了基于ISSA并結(jié)合積分圖的二維熵圖像多閾值分割快速算法，最后將該算法與窮舉法以及基于粒子群優(yōu)化算法(Particle Swarm Optimization, PSO) 的二維熵方法進行圖像分割對比實驗。實驗結(jié)果表明相較于窮舉法，本文方法在圖像雙閾值分割和三閾值分割的速度上分別提升了1 077.76倍和1 317 635.53倍；相較于基于PSO的二維熵方法，本文方法仍取得了6.47倍和4.48倍的速度優(yōu)勢，極大地提升了圖像二維熵多閾值分割的分割效率，同時在工業(yè)應(yīng)用場景仍能夠獲得相同的效果。

1 麻雀搜索算法

麻雀搜索算法是根據(jù)麻雀覓食并逃避捕食者的行為而提出的群體智能優(yōu)化算法[10]。麻雀搜索算法主要模擬了麻雀群覓食的過程。麻雀群覓食過程也是發(fā)現(xiàn)者-跟隨者模型的一種，同時還疊加了偵查預(yù)警機制。在麻雀搜索算法中，每只麻雀的位置代表一個可行解。麻雀種群中的個體被劃分為3類，分別肩負不同的覓食職責(zé)，其中包括：(1) 發(fā)現(xiàn)較好食物的個體作為發(fā)現(xiàn)者；(2) 跟隨發(fā)現(xiàn)者進行覓食活動的跟隨者；(3) 在覓食過程中遇到危險進行反捕食行為的偵查者。麻雀種群中的發(fā)現(xiàn)者、跟隨者以及偵查者的個體數(shù)量保持恒定的比例。麻雀種群中的發(fā)現(xiàn)者是種群中適應(yīng)度較高的個體，擁有更廣的搜索范圍，為跟隨者提供覓食方向。跟隨者能夠發(fā)現(xiàn)適應(yīng)度最高的發(fā)現(xiàn)者，跟隨發(fā)現(xiàn)者的引導(dǎo)，不斷更新自身位置以獲得更高的適應(yīng)度。而發(fā)現(xiàn)者與跟隨者之間的身份是動態(tài)變化的，只要跟隨者獲得更高的適應(yīng)度，就有機會成為發(fā)現(xiàn)者。在覓食過程中，麻雀種群中一定比例的個體作為偵查者，在意識到危險時，會移向安全區(qū)作出反捕食行為，以獲得更高的適應(yīng)度。

發(fā)現(xiàn)者的位置更新公式為

式中：i termax為算法的最大迭代次數(shù)；α 為 ( 0,1]之間的均勻隨機數(shù)；Q為一個服從標準正態(tài)分布的隨機數(shù)；R2為 預(yù)警值，是[0,1]之間的一個均勻隨機數(shù)；T為安全閾值，取值范圍為[0.5,1.0]。

跟隨者位置更新公式為

偵查者的位置更新公式為

2 改進麻雀搜索算法

2.1 方差線性遞減的高斯擾動

由式(1)可知在SSA中，當R2

圖1 發(fā)現(xiàn)者位置變化趨勢Fig.1 Change trend of discoverer's position

為解決麻雀搜索算法在迭代過程之中，因發(fā)現(xiàn)者所有維度有向原點靠攏或跳躍的趨勢所造成的全局搜索能力不高的問題，本文采用方差線性遞減的高斯擾動策略，即去除式(1)中R2T時的更新策略修改為方差線性遞減的高斯擾動策略，使得該算法在迭代初期發(fā)現(xiàn)者群體具有一定的個體多樣性，并且在算法迭代的后期具備較強的局部搜索能力。改進后的發(fā)現(xiàn)者位置更新公式為

式中：n ormrnd(0,sigma)為 期望值為0，方差為s igma 的高斯分布。 s igma 值在迭代過程中線性地減小，其表達式為

式中：tmax為最大允許迭代次數(shù)，t為當前迭代次數(shù)；sstart和send分別為初始的方差取值和迭代到最大迭代次數(shù)的方差取值。設(shè)待優(yōu)化問題目標函數(shù)的定義域為 [a,b]，為使算法在迭代初期具有一定的個體多樣性，根據(jù)正態(tài)分布的 3σ 原則，sstart的取值為

send應(yīng)取一個較小的值，使得算法在迭代后期具備較強的局部搜索能力。由于該優(yōu)化算法針對最佳閾值搜索任務(wù)進行改進，并且考慮到閾值的取值為整數(shù)，因此將種群個體位置進行四舍五入取整，得到當前種群個體位置所對應(yīng)的閾值取值，且根據(jù)正態(tài)分布的 σ 原則令send=1，使得算法在迭代的后期，發(fā)現(xiàn)者在一定的概率下仍然具有跳出當前位置的能力。

2.2 隨機步長移動策略

從式(2)中可以看出，在迭代過程中，當i>n/2時，跟隨者各維度位置的值為一個標準正態(tài)分布隨機數(shù)與一個以自然常數(shù)e為底數(shù)的指數(shù)函數(shù)的乘積。即此時跟隨者總是在原點周邊區(qū)域進行搜索。當i≤n/2時，跟隨者的迭代公式可簡化為

式中：r andi([0,1])表 示[0,1]中的隨機整數(shù)。顯然，在迭代過程中，跟隨者在全維度地向最優(yōu)位置移動，種群多樣性較低，算法容易陷入局部最優(yōu)。

為解決以上問題，本文提出隨機步長移動策略，將算法中發(fā)現(xiàn)者的位置更新公式改進為

式中：r and 表示0到1之間的均勻隨機數(shù)；u和l分別為最大步長因子和最小步長因子。由式(8)可知，跟隨者位置的每一維度以(l,u)之間的隨機步長向最優(yōu)位置移動，可通過設(shè)置步長因子的值調(diào)節(jié)跟隨者的移動速度。

改進的麻雀搜索算法流程為：

步驟1：初始化，包括初始化種群的規(guī)模N，發(fā)現(xiàn)者的個數(shù)PNum，跟隨者的個數(shù)FNum，最大步長因子u，最小步長因子l，最大迭代次數(shù)tmax，并按均勻分布初始化各麻雀個體的位置。

步驟2：計算每只麻雀的適應(yīng)度fi，得到當前最優(yōu)適應(yīng)度和最優(yōu)位置。

步驟3：選取適應(yīng)度最優(yōu)的前PNum個麻雀個體作為發(fā)現(xiàn)者，選取適應(yīng)度最優(yōu)的前FNum個麻雀個體，并排除前PNum個麻雀個體作為跟隨者，最后剩余的作為偵察者，并分別根據(jù)式(4)、(8)以及式(3)更新發(fā)現(xiàn)者、跟隨者以及偵察者的位置。

步驟4：根據(jù)各麻雀個體所處的位置重新計算適應(yīng)度值finew。當finew>fi時，表明迭代后的個體優(yōu)于上一代的個體，則用迭代后的個體替代上一代的個體，否則保持原個體不變。

步驟5:若算法的迭代次數(shù)達到最大迭代次數(shù)，則算法結(jié)束，否則跳轉(zhuǎn)到步驟3。

3 基于改進麻雀搜索算法的多閾值圖像分割

3.1 二維熵多閾值分割方法

基于一維直方圖可分離判據(jù)的閾值分割方法在圖像信噪比下降時，圖像的分割質(zhì)量急劇下降[11]。因此出現(xiàn)了一些利用圖像的二維直方圖進行閾值分割的方法[12-13]，其中就包括二維熵的閾值分割方法?？蓪⒍S熵閾值分割方法擴展為二維熵多閾值分割方法。

二維熵多閾值分割方法的原理為：假設(shè)一幅尺寸為M×N的待分割圖像f(x,y)(1 ≤x≤M,1 ≤y≤N)，利用尺寸為n×m的濾波核對其進行均值濾波獲得鄰域平均圖像g(x,y) ，兩圖像的灰度級均為0 ,1,···,L，L的取值一般為255。設(shè)r(i,j)為 圖像f(x,y)中灰度級為i且 圖像g(x,y) 中 灰度級為j的像素對數(shù)。定義r(i,j)所對應(yīng)的聯(lián)合概率密度為

如此得到了一個關(guān)于pij的二維直方圖，如圖2所示。設(shè)分割閾值為(t,s),則二維直方圖被分割為4個區(qū)域，其中區(qū)域1和區(qū)域3代表目標區(qū)域和背景區(qū)域，區(qū)域2和區(qū)域4代表邊緣和噪聲。

圖2 二維直方圖Fig.2 Two-dimensional histogram

圖3 多閾值二維直方圖Fig.3 Two-dimensional multi-threshold histogram

區(qū)域1和區(qū)域3的概率分別為

區(qū)域1與區(qū)域3的總信息熵為[14]

式中：

最大二維熵則是要獲得最佳閾值(t?,s?)，使得

令

式中：k=1,2,···,n+1 且定 義t0+1=s0+1=0 ，tn+1=sn+1=L。

3.2 積分圖

通過二維直方圖計算總信息熵H時運算量巨大，如式(17)及式(18)所示，對于每對閾值(tk,sk)均要做累加計算，且隨著閾值數(shù)量的增多，二維熵多閾值分割方法的計算復(fù)雜度呈指數(shù)級增長。為盡可能地提高最佳閾值的搜索速度，本文采用Viola等[15]提出的積分圖方法來降低總信息熵H的運算量。分別對pk及hk生成對應(yīng)的積分圖，如圖4所示，其中：

圖4 pk 及 hk對應(yīng)的積分圖Fig.4 Integral diagram corresponding to pk and hk

運用積分圖，可將式(17)和式(18)的計算簡化為：

4 基于改進麻雀搜索算法的多閾值圖像分割算法

設(shè)分割圖像的閾值向量T為[t1,t2,···,tn,s1,s2,···,sn]， 其中0

步驟1：讀取待分割灰度圖f。

步驟2：根據(jù)灰度圖f求得二維直方圖。

步驟3：根據(jù)步驟2中的二維直方圖求得pk和hk對應(yīng)的積分圖。

步驟4：初始化麻雀種群，其中每個麻雀個體的位置代表一個閾值向量，并利用積分圖及根據(jù)式(16)、式(21)和式(22)計算所有麻雀個體的適應(yīng)度值。

步驟5：利用改進麻雀搜索算法對閾值向量進行尋優(yōu)迭代，直至達到最大迭代次數(shù)。

步驟6：通過使用尋優(yōu)得到的最優(yōu)閾值對待分割圖像進行閾值分割，輸出分割后的圖像。

流程圖如圖5所示。

圖5 分割算法流程圖Fig.5 Flow chart of segmentation algorithm

5 實驗結(jié)果與分析

5.1 基準函數(shù)對比實驗

通過設(shè)計基準函數(shù)對比實驗來驗證改進算法的性能提升，設(shè)計二維熵圖像多閾值分割對比實驗來驗證基于改進麻雀搜索算法的二維熵多閾值分割方法在運行速度上的優(yōu)越性。本文實驗均基于Windows1064位操作系統(tǒng)，CPU為Intel(R)Core(TM)i5-4210 M和16 GB內(nèi)存的PC機，實驗軟件為Matlab R2018a。

為測試改進麻雀搜索算法的搜索能力，本文采用4個不同特征的基準測試函數(shù)作為實驗對象，如表1所示。表1中特征“U”代表該函數(shù)是單峰函數(shù)，函數(shù)在定義域內(nèi)沒有局部極值，只有全局最優(yōu)解；特征“M”代表函數(shù)是多峰函數(shù)，多峰函數(shù)相對于單峰函數(shù)具有多個局部極值，用于檢驗算法的全局搜索能力；特征“S”代表函數(shù)是可分離的，即該函數(shù)可由N個單變量函數(shù)之和表示；特征“N”代表函數(shù)是不可分離的，與可分離函數(shù)相對，不可分離函數(shù)變量之間存在復(fù)雜的關(guān)系，因此此類函數(shù)的尋優(yōu)較為困難[16]。實驗中算法的通用參數(shù)分別設(shè)置為：種群的規(guī)模N=50， 最大迭代次數(shù)tmax=100，發(fā)現(xiàn)者、跟隨者及偵查者的比例為2:7:1。

表1 基準測試函數(shù)Table 1 Benchmark functions

標準麻雀搜索算法和改進麻雀搜索算法在4個基準測試函數(shù)上的收斂曲線如圖6所示,從圖中可以看出改進后的麻雀搜索算法在F1上表現(xiàn)出了更優(yōu)的收斂精度；在F2上表現(xiàn)出了更優(yōu)的全局搜索能力；在F3上表現(xiàn)出更優(yōu)的收斂速度；在F4上表現(xiàn)出與標準麻雀搜索算法相似的尋優(yōu)能力。

圖6 基準函數(shù)收斂圖Fig.6 Convergence graph of benchmark function

為避免實驗結(jié)果的隨機性，定量分析改進后算法的尋優(yōu)性能，標準麻雀搜索算法(SSA)和改進麻雀搜索算法(ISSA) 對表1中的4個基準函數(shù)各獨立運行30次，選取運行結(jié)果中的最差值、最優(yōu)值、平均值和標準差作為對比指標進行比較，如表2所示。

表2 算法性能比較Table 2 Comparison of performance among different algorithms

從尋優(yōu)結(jié)果的比較中可發(fā)現(xiàn)，在F1上，ISSA極大地提高了尋優(yōu)精度；在F2上SSA沒有能夠搜尋到最優(yōu)解，體現(xiàn)了ISSA相較于SSA在全局搜索能力上的提升；在F3和F4上，ISSA相較于SSA,其尋優(yōu)結(jié)果的標準差更低，表現(xiàn)出了更好的尋優(yōu)穩(wěn)定性，具有更高的尋優(yōu)能力。

5.2 基于改進麻雀搜索算法的二維熵多閾值圖像分割方法實驗

本文實驗選取了Lenna圖、Camera man圖、Rice圖以及工業(yè)生產(chǎn)當中的齒輪圖和剎車盤圖分別進行基于改進麻雀搜索算法的二維熵多閾值圖像分割方法的單閾值分割、雙閾值分割以及三閾值分割。算法的參數(shù)設(shè)置為：種群的規(guī)模N=50，最大迭代次數(shù)tmax=30 ，最大步長因子u=1.7，最小步長因子l=0.3，發(fā)現(xiàn)者、跟隨者及偵查者的比例為1:8:1。分割后的圖像如圖7所示。圖7中，齒輪圖包含多個待分割的齒輪目標，在單個剎車盤工件上同時存在多個灰度不同的區(qū)域，對此類圖像進行單閾值分割往往不能得到理想的分割結(jié)果。利用本文方法對齒輪圖像進行雙閾值分割，可正確分割出所有的齒輪目標。而剎車盤圖像灰度不同的區(qū)域較多，采用三閾值分割方可獲得理想的分割結(jié)果。

圖7 分割結(jié)果Fig.7 Segmentation results

5.3 對比實驗

為驗證本文方法的優(yōu)越性，將其與基于粒子群優(yōu)化算法(Particle Swarm optimization，PSO) 的二維熵分割方法進行對比實驗?；诹Ｗ尤簝?yōu)化算法(PSO) 的二維熵分割方法是直接利用粒子群優(yōu)化算法對圖像的二維熵最優(yōu)閾值進行尋優(yōu)的方法。

以上2種算法對前述5幅原始圖像進行分割實驗，分割后的閾值與計算時間如表3所示。由表3可知，相較于基于PSO的二維熵方法，本文方法在雙閾值分割及三閾值分割中取得了6.47倍及4.48倍的速度優(yōu)勢。將改進麻雀搜索算法應(yīng)用在二維熵圖像多閾值分割上，提高了圖像分割的速度。

表3 兩種算法的結(jié)果對比Table 3 Comparison of the results between two algorithms

6 結(jié)論

本文針對圖像二維熵多閾值分割時存在的計算量過大，計算時間過長的問題，提出了基于ISSA并結(jié)合積分圖的二維熵圖像多閾值分割快速算法。首先，引入麻雀搜索算法(SSA)并對該算法的算法性能進行分析研究，針對SSA存在的全局搜索能力差、容易陷入局部最優(yōu)解的缺點，提出了基于方差線性遞減的高斯擾動策略和隨機步長移動策略的ISSA。相較于SSA，ISSA在4種不同類型的基準函數(shù)上表現(xiàn)出更優(yōu)的尋優(yōu)能力。接著，通過引入積分圖方法，降低總信息熵的運算量，最終提出了基于改進麻雀搜索算法并結(jié)合積分圖的二維熵圖像多閾值分割快速算法。最后，使用該方法與基于PSO的二維熵方法進行圖像分割對比實驗，實驗結(jié)果表明，相較于基于PSO的二維熵方法，本文方法仍取得了6.47倍和4.48倍的速度優(yōu)勢，提升了圖像二維熵多閾值分割的分割效率。