吳浩然
(合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院,安徽 合肥 230601)
圖像分割就是把圖像分成若干個(gè)特定的、具有獨(dú)特性質(zhì)的區(qū)域并提出人們感興趣目標(biāo)的技術(shù)和過程?,F(xiàn)有的圖像分割方法主要分以下幾類:基于閾值的分割方法、基于區(qū)域的分割方法以及基于邊緣的分割方法。其中基于閾值的分割方法是最常見的方法,該方法根據(jù)圖像中目標(biāo)與背景的灰度值的差異,通過設(shè)置一個(gè)或幾個(gè)閾值來將圖像分割成多個(gè)區(qū)域。目前比較成功的閾值方法有聚類方差法、熵方法等[1]。在這之中熵閾值分割方法又因?yàn)閷?shí)現(xiàn)簡單且性能穩(wěn)定而得到了廣泛的應(yīng)用。20世紀(jì)80年代,學(xué)者們就開始將熵的概念應(yīng)用在閾值選擇上。Pun首先將熵的概念引入圖像的閾值分割,提出了最大后驗(yàn)熵法[2],Kapur等人提出了一維最大Shannon熵閾值法[3],Li和Lee提出了最小交叉熵閾值法[4]。
上述基于熵的閾值分割法中一般采用的都是一維Shannon熵,但Shannon熵具有廣延性,其會忽略兩個(gè)子系統(tǒng)之間的相互作用,放在圖像分割中就是忽略了目標(biāo)和背景之間的相關(guān)性[1]。為了解決這個(gè)問題,Tsallis擴(kuò)展了Shannon熵并提出了Tsallis熵[5],Tsallis熵具有非廣延性,使用Tsallis熵進(jìn)行圖像分割可以取得更好的結(jié)果。除此之外,由于一維熵閾值分割法是利用圖像的一維直方圖進(jìn)行計(jì)算的,這在得到最佳分割閾值的過程中沒有利用到圖像的空間信息,因此圖像分割結(jié)果容易受到噪聲的干擾,而利用圖像的局部空間信息可以在一定程度上改善分割結(jié)果[6],有學(xué)者據(jù)此引入了像素的鄰域灰度信息,提出了多種基于圖像二維直方圖的熵閾值分割方法,如二維Renyi熵閾值法[7]、二維Tsallis熵閾值法[8]等。擴(kuò)展的二維方法能較好地抵抗高斯噪聲的干擾,但卻無法抵抗椒鹽噪聲的干擾[9],因此有學(xué)者引入了鄰域中值提出了三維分割算法,如三維Otsu法[10]、三維Tsallis熵法[11]等。上述三維閾值分割方法都是利用圖像的原始灰度,鄰域平均灰度,以及鄰域中值組成圖像的三維直方圖,并未利用到圖像的梯度信息,這存在著一定的局限性[9]。受文獻(xiàn)[9]啟發(fā),該文引入了梯度信息,將其與圖像像素的鄰域均值、鄰域中值結(jié)合構(gòu)成圖像的三維直方圖,并結(jié)合Tsallis熵理論提出了三維Tsallis熵閾值分割方法。將提出的新的三維Tsallis熵閾值分割法與該文提出的一種新的改進(jìn)粒子群優(yōu)化算法結(jié)合進(jìn)行圖像閾值選擇,取得了較好的分割結(jié)果。由上所述,相對于一維熵閾值分割法,二維熵閾值法進(jìn)行分割可以取得更好的結(jié)果,但同時(shí)分割步驟也變得更加繁瑣,計(jì)算量也變得更大,從而運(yùn)算時(shí)間也變得更長。因此為了提高分割效率,有學(xué)者提出了利用元啟發(fā)式算法結(jié)合二維熵來進(jìn)行閾值選擇。與二維熵閾值分割法相比,三維熵閾值分割法的計(jì)算量更大,因此該文同樣使用元啟發(fā)式算法對三維熵閾值分割法進(jìn)行優(yōu)化以提高分割效率。
啟發(fā)式算法(heuristic algorithm)是一種基于人的主觀經(jīng)驗(yàn)或自然規(guī)律所構(gòu)造的算法,能夠在可接受的計(jì)算花費(fèi)(如計(jì)算時(shí)間)下給出待解決組合優(yōu)化問題的一個(gè)較優(yōu)的可行解,但該可行解與目標(biāo)問題的最優(yōu)解之間的誤差一般無法預(yù)計(jì)。元啟發(fā)式算法(meta-heuristic algorithm)是啟發(fā)式算法的改進(jìn),由于元啟發(fā)式算法較少依賴算法本身組織結(jié)構(gòu),因此其通用性強(qiáng)、泛化性更好[12]。遺傳算法[13]是(genetic algorithm,GA)較早提出來的一種元啟發(fā)式算法,文獻(xiàn)[14]就將遺傳算法與二維最大熵法結(jié)合進(jìn)行圖像分割,在分割精度明顯優(yōu)于一維最大熵法的情況下分割速度與一維最大熵法基本相同。除此之外,文獻(xiàn)[15-16]也都將遺傳算法應(yīng)用于圖像分割領(lǐng)域。鯨魚優(yōu)化算法[17](whale optimization algorithm,WOA)是一種受鯨魚社會行為啟發(fā)的元啟發(fā)式算法,文獻(xiàn)[18]將鯨魚優(yōu)化算法與多閾值Otsu法結(jié)合進(jìn)行圖像分割,實(shí)現(xiàn)了更高的分割精度。除此之外,文獻(xiàn)[19-20]也將改進(jìn)的鯨魚優(yōu)化算法與熵閾值法結(jié)合進(jìn)行圖像分割。
粒子群優(yōu)化算法[21](particle swarm optimization,PSO)是由Kennedy和Eberhart于1995年提出的一種基于群體智能的元啟發(fā)式優(yōu)化算法,由于操作簡單、收斂速度快而得到了廣泛的應(yīng)用,文獻(xiàn)[22]就將PSO與二維最大Tsallis熵結(jié)合進(jìn)行閾值選擇,取得了較好的結(jié)果。雖然PSO算法收斂速度快,但仍存在早熟收斂的問題,并且具有種群多樣性隨迭代數(shù)增加下降過快、有可能不收斂到全局最優(yōu)解等缺點(diǎn),這將會導(dǎo)致分割閾值選取不夠精確,從而圖像分割精度較低。因此有學(xué)者通過不斷改進(jìn)這些元啟發(fā)式算法以獲得更好的效果。該文通過修改粒子群優(yōu)化算法的粒子迭代方式,得到了一種在低維環(huán)境下可以有效避免局部最優(yōu)的改進(jìn)粒子群優(yōu)化算法,然后將其與三維Tsallis熵結(jié)合對圖像進(jìn)行分割,取得了更好的分割精度。
取圖像自身的灰度值以及對應(yīng)的鄰域平均灰度值構(gòu)造二維直方圖,如圖1所示。
圖1 二維直方圖
在圖1中,(s,t)為假設(shè)的閾值向量,可以看出,向量(s,t)將上圖分割為四個(gè)部分,其中區(qū)域A和B表示目標(biāo)或背景,區(qū)域C和E表示邊界點(diǎn)或噪聲。
則目標(biāo)和背景兩類的二維Tsallis熵分別為:
(1)
(2)
式中,L為圖像灰度級,q為待定系數(shù),其代表了Tsallis熵的非廣延性,文中q取0.8。由此可得圖像總的二維Tsallis熵為:
(3)
以上公式為文獻(xiàn)[8]和文獻(xiàn)[23]的工作。
假設(shè)f為大小M×N、灰度級為L的一幅圖像,用f(x,y)表示位于圖像(x,y)處的像素點(diǎn)的灰度值,g(x,y)表示以(x,y)為中心的3×3的像素鄰域的平均灰度值。在此基礎(chǔ)上再設(shè)h(x,y)為以(x,y)為中心的3×3鄰域灰度中值,z(x,y)為以(x,y)為中心的3×3鄰域的梯度值。其中梯度的計(jì)算如下所示:
z(x,y)=9|f(x,y)-g(x,y)|
(4)
該文則將g(x,y)、h(x,y)與z(x,y)三個(gè)元素作為三維Tsallis熵的組成部分構(gòu)成三維直方圖,如圖2所示。
圖2 三維直方圖
由圖2可以看出,假設(shè)的三個(gè)閾值(s,t,q)將圖中像素劃分為8個(gè)部分。其中區(qū)域0,1,2,3位于梯度閾值q的下方,即位于該區(qū)域的灰度值梯度較小,這表示該區(qū)域的像素之間灰度值變化不大,所以一般認(rèn)為目標(biāo)與背景位于該區(qū)域。反之區(qū)域4,5,6,7的梯度值則較大,這表示該區(qū)域像素之間灰度值變化較大,一般認(rèn)為邊緣和噪聲位于該區(qū)域。因?yàn)槲挥谀繕?biāo)或背景的灰度值比較相似,因此位于目標(biāo)或背景的像素點(diǎn)處的鄰域平均灰度值與中值則會非常接近,從而在區(qū)域0,1,2,3中,位于對角線處的區(qū)域0,1便代表背景和目標(biāo)(假設(shè)區(qū)域0為背景,區(qū)域1為目標(biāo)),區(qū)域2,3則因?yàn)橄袼攸c(diǎn)很少而可以忽略不計(jì)。與之同理,邊緣和噪聲點(diǎn)主要出于區(qū)域4,5之中,區(qū)域6,7則可以忽略不計(jì)。其中區(qū)域4中的邊緣信息為背景區(qū)域向目標(biāo)區(qū)域過度的邊緣信息,區(qū)域5為目標(biāo)區(qū)域向背景區(qū)域過度的邊緣信息[9]。
每個(gè)像素對(i,j,k)出現(xiàn)的聯(lián)合概率為:
(5)
式中,rijk表示像素對(i,j,k)出現(xiàn)的次數(shù)。則區(qū)域0,1,4,5的聯(lián)合密度分別為:
(6)
(7)
(8)
(9)
則根據(jù)上述公式以及上節(jié)的Tsallis熵公式可得區(qū)域0,1,4,5的三維Tsallis熵分別為:
(10)
(11)
(12)
(13)
據(jù)上所述,該文將區(qū)域0,4作為背景,1,5作為目標(biāo),根據(jù)Tsallis熵的定義,提出了以下圖像總的熵的公式:
(14)
只需求出式(14)最大值即可得到最優(yōu)閾值,在求得最優(yōu)閾值(s*,t*,q*)之后按以下公式對圖像進(jìn)行分割:
(15)
由上文所述,圖像的背景與目標(biāo)均處于閾值q*以下,所以公式(15)未利用到閾值q*。
(16)
(17)
式中,d為粒子的某一個(gè)維度。c1和c2為加速度系數(shù),二者通常情況下都取2,R1(t)與R2(t)為[0,1]之間的隨機(jī)數(shù)。ω為慣性權(quán)重,通常是隨著迭代次數(shù)的增加而線性減小,最大值一般取ωmax=0.9,最小值一般取ωmin=0.4,ω的公式如下:
(18)
式中,Max_iter為最大迭代次數(shù)。
如式(16)、(17)所示,在粒子群優(yōu)化算法中,每次迭代每個(gè)粒子都只向當(dāng)前位置,自身的歷史最優(yōu)位置pbesti以及所有粒子所發(fā)現(xiàn)的全局歷史最優(yōu)位置gbest進(jìn)行學(xué)習(xí),這導(dǎo)致粒子在更新時(shí)其余粒子信息使用不足[25]。且每當(dāng)有粒子陷入局部最優(yōu)時(shí),由于gbest的存在,其他粒子都會向該粒子學(xué)習(xí),這將會導(dǎo)致算法陷入局部最優(yōu)。因此為了避免算法陷入局部最優(yōu),該文引入了綜合學(xué)習(xí)策略[26]并同時(shí)修改PSO中粒子的學(xué)習(xí)方式,使粒子在更新時(shí)盡量減少其對gbest的依賴并增加對其他粒子信息的使用。
不失一般性,考慮以下最小化問題:
minf=f(x)
(19)
在綜合學(xué)習(xí)策略中,粒子在更新時(shí),每個(gè)維度都會向不同的粒子學(xué)習(xí)。具體規(guī)則如下所述:在粒子更新時(shí),粒子的每個(gè)維度都會對應(yīng)生成一個(gè)隨機(jī)數(shù),然后將隨機(jī)數(shù)與學(xué)習(xí)概率Pc進(jìn)行比較,若隨機(jī)數(shù)較大,則粒子該維度將之從自身pbest的對應(yīng)維度進(jìn)行學(xué)習(xí)。若學(xué)習(xí)概率Pc更大,粒子該維度則向其他粒子對應(yīng)的維度進(jìn)行學(xué)習(xí),而學(xué)習(xí)的對象則通過競爭選擇而來。競爭選擇的具體規(guī)則如下所述:首先隨機(jī)選擇兩個(gè)粒子,然后比較這兩個(gè)粒子的歷史最優(yōu)值(將兩個(gè)粒子的pbest帶入評價(jià)函數(shù)求得的適應(yīng)值),選擇適應(yīng)值較好的一個(gè)將其pbest對應(yīng)的維度當(dāng)成粒子更新時(shí)某個(gè)維度的學(xué)習(xí)對象。
受綜合學(xué)習(xí)策略的啟發(fā),該文提出了綜合學(xué)習(xí)改進(jìn)粒子群優(yōu)化算法(comprehensive learning improved particle swarm optimization,CLIPSO),具體原理如下:首先,將粒子按行組為一個(gè)矩陣,每個(gè)粒子為一行,行順序隨機(jī)確定,然后將所有粒子按標(biāo)準(zhǔn)PSO的迭代規(guī)則迭代一次。這之后位于矩陣第一行的粒子先按照PSO的迭代法則更新自身位置,即該粒子的學(xué)習(xí)對象為自身歷史最優(yōu)位置pbesti與全局歷史最優(yōu)位置gbest,然后剩下的粒子按照矩陣的行順序從上往下依次更新位置,但這些粒子的學(xué)習(xí)對象與第一個(gè)粒子不同,它們在更新位置之前會生成一個(gè)隨機(jī)數(shù),然后將該隨機(jī)數(shù)與事先設(shè)定的學(xué)習(xí)概率Pc(文中Pc取0.8)進(jìn)行比較,若學(xué)習(xí)概率較大,則粒子只向自身的歷史最優(yōu)值pbesti進(jìn)行學(xué)習(xí)。反之若隨機(jī)數(shù)較大,則在該粒子上方隨機(jī)挑選兩個(gè)粒子,再對這兩個(gè)粒子的當(dāng)前適應(yīng)值進(jìn)行對比,選擇較優(yōu)的粒子作為當(dāng)前更新位置的粒子的學(xué)習(xí)對象,其中i={2,3,…,N}。
在上述CLIPSO的迭代步驟中,除了位于矩陣第一行的粒子會向全局歷史最優(yōu)值gbest學(xué)習(xí)外,其余粒子均不會向gbest學(xué)習(xí),雖然這會避免粒子被gbest吸引而輕易地陷入局部最優(yōu),但由于粒子是隨機(jī)分布的且在算法開始的時(shí)候粒子矩陣的行順序也是隨機(jī)確定的,因此粒子在迭代過程中可能會缺少全局信息,從而導(dǎo)致算法收斂速度變慢。該文將所有粒子都更新過一次位置之后迭代一次,然后每隔一定的迭代次數(shù)(設(shè)為m代),就對所有的粒子整體進(jìn)行一次PSO迭代以獲取全局最優(yōu)信息,文中m取15。
CLIPSO具體的迭代公式如下:
(20)
(21)
(22)
式中,2≤i≤N,1≤j3 CLIPSO實(shí)驗(yàn)與分析
3.1 實(shí)驗(yàn)準(zhǔn)備
為了驗(yàn)證綜合學(xué)習(xí)改進(jìn)粒子群優(yōu)化算法的尋優(yōu)能力以及跳出局部最優(yōu)的能力,使用了5個(gè)經(jīng)典的測試函數(shù)來驗(yàn)證CLIPSO的性能。這5個(gè)測試函數(shù)中,f1為單峰函數(shù),其余為多峰函數(shù),所有函數(shù)解空間均設(shè)為2維,各函數(shù)參數(shù)如表1所示。
表1 函數(shù)參數(shù)
續(xù)表1
在這一部分,將CLISPO與PSO本體以及量子粒子群優(yōu)化算法(quantum-inspired particle swarm optimization,QPSO)[27]、遺傳算法、鯨魚優(yōu)化算法在五個(gè)測試函數(shù)上的測試結(jié)果進(jìn)行比較。所有算法均使用相同的種群大小40和最大迭代次數(shù)7 500。每個(gè)算法都在測試函數(shù)上運(yùn)行30次,然后取平均值。實(shí)驗(yàn)環(huán)境為:Intel(R) Core(TM)i7-6700HQ CPU @2.60 GHz。RAM 8.00 GB,Windows10操作系統(tǒng),MatlabR2016a。運(yùn)行結(jié)果見表2。
表2 各算法在測試函數(shù)上的比較
表2中,mean表示算法運(yùn)行30次所得結(jié)果的平均值,min表示這30次結(jié)果中的最優(yōu)值,max表示這30次結(jié)果中的最差值,std表示這30次結(jié)果的標(biāo)準(zhǔn)差,time表示算法運(yùn)行的時(shí)間。由表2數(shù)據(jù)可以發(fā)現(xiàn),CLIPSO在這5個(gè)基準(zhǔn)函數(shù)上的平均表現(xiàn)比較優(yōu)異。在單峰函數(shù)f1上,CLIPSO、QPSO、WOA每次都可以發(fā)現(xiàn)函數(shù)的最優(yōu)值,同時(shí)PSO與GA則多次陷入了局部最優(yōu)。在函數(shù)f2上,CLIPSO多次陷入了局部最優(yōu),但在該函數(shù)上只有WOA算法每次都達(dá)到了全局最優(yōu)。在函數(shù)f3上,只有CLIPSO每次都能收斂到全局最優(yōu)值,其余算法均不同程度地陷入了局部最優(yōu)。在函數(shù)f4上,CLIPSO與QPSO、WOA均能次次達(dá)到全局最優(yōu),PSO與GA算法則多次陷入了局部最優(yōu)。在函數(shù)f5上,所有算法均陷入了局部最優(yōu),但CLIPSO所能達(dá)到的效果最接近全局最優(yōu)值。由此可以得知,CLIPSO可以在一定程度上避免局部最優(yōu)。但從表中也可以看出,CLIPSO的運(yùn)行時(shí)間要長于其他算法,這也是未來需要改進(jìn)的方向。
為了驗(yàn)證CLIPSO結(jié)合三維Tsallis熵的分割精度,對Lena、Camera這兩張圖片進(jìn)行了加噪處理,然后將CLIPSO結(jié)合三維Tsallis熵對這些圖片進(jìn)行分割并將分割結(jié)果與CLIPSO結(jié)合二維Tsallis熵對這些圖片的分割結(jié)果進(jìn)行對比。實(shí)驗(yàn)中CLIPSO種群數(shù)設(shè)置為20,最大迭代次數(shù)設(shè)置為100。實(shí)驗(yàn)環(huán)境為:Intel(R) Core(TM)i7-6700HQ CPU @2.60 GHz,RAM 8.00 GB,Windows10操作系統(tǒng),MatlabR2016a。分割用的圖片如圖3所示。
圖3 分割用圖像
本節(jié)將CLIPSO分別結(jié)合二維Tsallis熵與三維Tsallis熵對Lena、Camera兩張圖片以及它們的加噪圖片進(jìn)行分割,操作環(huán)境如上所述,圖片的分割結(jié)果如圖4和圖5所示。
圖4 Lena分割結(jié)果對比
在圖4、圖5中,位于每張圖片下方的是圖片分割的時(shí)間與閾值,圖(a)是原圖的分割結(jié)果,圖(b)是添加了高斯噪聲的分割結(jié)果,圖(c)是添加了椒鹽噪聲的分割結(jié)果,圖(d)是添加了混合噪聲的分割結(jié)果。
由圖4可以看出,在圖4(a)上,CLIPSO結(jié)合三維Tsallis熵的方法清晰地將人臉分割了出來,但CLIPSO結(jié)合二維Tsallis熵的方法卻無法完全將人臉與背景分離。在圖4(b)上,二者表現(xiàn)相同但效果較差。在圖4(c)上,二維Tsallis熵方法的分割結(jié)果存在著大量的噪聲點(diǎn),而三維Tsallis熵的分割結(jié)果則只有少量的噪聲點(diǎn)。在圖4(d)上,二維Tsallis熵與三維Tsallis熵的分割結(jié)果均存在著噪聲點(diǎn),但三維Tsallis熵的分割圖片上的噪聲點(diǎn)要明顯少于二維Tsallis熵分割圖片上的噪聲點(diǎn)。
在圖5中,二維Tsallis熵與三維Tsallis熵均清晰的分割出了目標(biāo)與背景,但二維Tsallis熵在添加了圖5(b)上的分割結(jié)果中存在著少量的噪聲點(diǎn),在圖5(c)上的分割結(jié)果中存在著大量的噪聲點(diǎn),在圖5(d)上的分割結(jié)果中則幾乎整張圖片都布滿了噪聲點(diǎn)。與此相反,三維Tsallis熵的所有分割結(jié)果幾乎沒有區(qū)別,僅在添加了混合噪聲的圖片上存在著極少的噪聲點(diǎn)。
圖5 Camera分割結(jié)果對比
雖然總體來說三維Tsallis熵閾值分割法可以有效地避免噪聲干擾,但其分割時(shí)間卻遠(yuǎn)遠(yuǎn)大于二維Tsallis熵。這是因?yàn)槿STsallis熵閾值分割法代碼的時(shí)間復(fù)雜度要遠(yuǎn)遠(yuǎn)大于二維Tsallis熵閾值分割法代碼的時(shí)間復(fù)雜度。為了解決三維熵閾值分割法的時(shí)間復(fù)雜度過大的問題,文獻(xiàn)[9-10]都提出了三維熵的遞推公式以減小算法的時(shí)間復(fù)雜度。而該文選擇采用元啟發(fā)式算法來優(yōu)化三維Tsallis熵閾值分割法,雖然最終分割時(shí)間仍遠(yuǎn)大于二維Tsallis熵閾值分割法,但與文[9]提到的三維OTSU法相比,分割時(shí)間約為其一半。與同樣是文獻(xiàn)[9]提出的利用遞推公式的三維Renyi熵閾值分割法相比,分割時(shí)間則與之相近。
由于二維Tsallis熵閾值分割法難以抵抗部分噪聲的干擾,通過引入圖像的鄰域均值、鄰域中值以及梯度信息構(gòu)建了三維直方圖,并將其與Tsallis熵理論結(jié)合提出了一種三維Tsallis熵閾值分割方法。實(shí)驗(yàn)表明,與二維Tsallis熵閾值分割方法相比,三維Tsallis熵閾值分割法可以有效地抵抗各種噪聲的干擾。
為了更精確地進(jìn)行圖像分割,提出了一種新的改進(jìn)粒子群優(yōu)化算法:綜合學(xué)習(xí)改進(jìn)粒子群優(yōu)化算法,將其與前面提出的三維Tsallis熵結(jié)合進(jìn)行圖像分割。實(shí)驗(yàn)表明,綜合學(xué)習(xí)改進(jìn)粒子群優(yōu)化算法可以在低維環(huán)境下有效地避免陷入局部最優(yōu),且其與三維Tsallis熵結(jié)合可以更精確地進(jìn)行圖像分割。
雖然綜合學(xué)習(xí)改進(jìn)粒子群優(yōu)化算法與三維Tsallis熵結(jié)合可以更精確地分割圖像,三維熵閾值分割方法的時(shí)間仍然要遠(yuǎn)遠(yuǎn)高于二維熵閾值分割方法,因此在后續(xù)的改進(jìn)中,可以嘗試將綜合學(xué)習(xí)改進(jìn)粒子群優(yōu)化算法中穿插的PSO替換成其他更快的PSO變體,或引入如文獻(xiàn)[10]所述的三維熵遞推公式,也許可以加快圖像的分割速度。