基于ISSA和積分圖的二維熵圖像多閾值分割快速算法

吳圳樺，唐文艷，呂文閣，陳汝杰，侯夢(mèng)華，李德源

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

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

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

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

1 麻雀搜索算法

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

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

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

跟隨者位置更新公式為

偵查者的位置更新公式為

2 改進(jìn)麻雀搜索算法

2.1 方差線性遞減的高斯擾動(dòng)

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

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

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

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

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

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

2.2 隨機(jī)步長(zhǎng)移動(dòng)策略

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

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

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

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

改進(jìn)的麻雀搜索算法流程為：

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

步驟2：計(jì)算每只麻雀的適應(yīng)度f(wàn)i，得到當(dāng)前最優(yōu)適應(yīng)度和最優(yōu)位置。

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

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

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

3 基于改進(jìn)麻雀搜索算法的多閾值圖像分割

3.1 二維熵多閾值分割方法

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

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

如此得到了一個(gè)關(guān)于pij的二維直方圖，如圖2所示。設(shè)分割閾值為(t,s),則二維直方圖被分割為4個(gè)區(qū)域，其中區(qū)域1和區(qū)域3代表目標(biāo)區(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 積分圖

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

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

運(yùn)用積分圖，可將式(17)和式(18)的計(jì)算簡(jiǎn)化為：

4 基于改進(jìn)麻雀搜索算法的多閾值圖像分割算法

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

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

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

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

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

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

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

流程圖如圖5所示。

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

5 實(shí)驗(yàn)結(jié)果與分析

5.1 基準(zhǔn)函數(shù)對(duì)比實(shí)驗(yàn)

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

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

表1 基準(zhǔn)測(cè)試函數(shù)Table 1 Benchmark functions

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

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

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

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

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

5.2 基于改進(jìn)麻雀搜索算法的二維熵多閾值圖像分割方法實(shí)驗(yàn)

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

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

5.3 對(duì)比實(shí)驗(yàn)

為驗(yàn)證本文方法的優(yōu)越性，將其與基于粒子群優(yōu)化算法(Particle Swarm optimization，PSO) 的二維熵分割方法進(jìn)行對(duì)比實(shí)驗(yàn)。基于粒子群優(yōu)化算法(PSO) 的二維熵分割方法是直接利用粒子群優(yōu)化算法對(duì)圖像的二維熵最優(yōu)閾值進(jìn)行尋優(yōu)的方法。

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

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

6 結(jié)論

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