基于自適應(yīng)粒子群優(yōu)化的三維OTSU圖像分割算法

曾業(yè)戰(zhàn)，王潤民

（1.湖南理工學(xué)院 物理與電子學(xué)院，湖南 岳陽 414000；2.湖南科技大學(xué) 信息與電氣工程學(xué)院，湖南 湘潭 411201）

圖像分割是圖像處理和計(jì)算機(jī)視覺的關(guān)鍵環(huán)節(jié)，是進(jìn)行圖像識(shí)別、分析和理解的基礎(chǔ)。近幾年來隨著電子技術(shù)和計(jì)算機(jī)的飛速發(fā)展，應(yīng)用計(jì)算機(jī)技術(shù)進(jìn)行圖像分割廣泛應(yīng)用于軍事、遙感、氣象等方面。在常用的圖像分割算法中，基于灰度直方圖的閾值分割方法以其簡單實(shí)用的特點(diǎn)引起了研究者普遍重視。1979年日本學(xué)者大津展之提出了一維OTSU算法[1],該方法依據(jù)一維直方圖,以目標(biāo)和背景的類間方差最大為閾值選取準(zhǔn)則，在一般情況下能夠取得好的效果，但一維OTSU算法在分割含有噪聲的圖像時(shí)，分割效果并不理想。在一維OTSU的基礎(chǔ)上，二維OTSU分割算法利用了圖像象素與其鄰域空間的相關(guān)信息因而具有更強(qiáng)的抗噪性能[2]，并且由于該算法直觀、簡便、運(yùn)行速度快等特點(diǎn)而受到廣大學(xué)者的關(guān)注，但二維OTSU算法假設(shè)對(duì)象區(qū)域和背景區(qū)域上的概率和近似為1普遍性不夠。文獻(xiàn)[3]引入鄰域中值作為第三個(gè)特征構(gòu)造了三維灰度直方圖，提出了一種三維OTSU的圖像分割算法，該算法對(duì)低對(duì)比度、低信噪比的圖像獲得了更好的分割效果，特別對(duì)高斯噪聲或椒鹽噪聲和疊加了混合噪聲（高斯噪聲加椒鹽噪聲）的圖像有很好的抗噪性能，但三維OTSU運(yùn)算時(shí)間長，占用內(nèi)存空間大。文獻(xiàn)[4]對(duì)三維OTSU分割算法的遞推公式進(jìn)行了改進(jìn)，使得算法的運(yùn)算時(shí)間得到減少。為進(jìn)一步減少運(yùn)算時(shí)間，本文結(jié)合分割圖像的具體信息，綜合利用圖像的分割閾值與目標(biāo)區(qū)域的關(guān)系，提出了一種基于自適應(yīng)粒子群優(yōu)化的三維OTSU圖像分割算法，并進(jìn)行了仿真和分析。

1 基本理論

1.1 粒子群算法

粒子群算法的基本思想是通過群體中個(gè)體之間的協(xié)作和信息共享來尋找最優(yōu)解，是一種基于群集智能方法的演化計(jì)算技術(shù)。由于算法設(shè)置參數(shù)少、實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的高度重視，目前已廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。類似于其他進(jìn)化算法，粒子群算法對(duì)每個(gè)優(yōu)化問題的解設(shè)為搜索空間中的一個(gè)粒子，每個(gè)粒子根據(jù)求解問題參數(shù)用一個(gè)相應(yīng)的適應(yīng)度進(jìn)行匹配，粒子飛行的速度決定飛行的距離和方向，通過迭代追尋當(dāng)前的最優(yōu)粒子。

設(shè)D為搜索空間的維數(shù)，粒子i的位置和速度分別用Xi=（xi1，xi2，…,xiD）、Vi=（vi1，vi2，…，viD）表示，pid=（pi1，pi2，…，piD）為粒子i曾經(jīng)到達(dá)的最好位置，pg表示種群的最好位置。在每一次迭代中，粒子根據(jù)本身的最優(yōu)解pi和整個(gè)種群的最優(yōu)解pg修正自己的速度和位置最后找到最優(yōu)解[5]。速度和位置根據(jù)如下方程進(jìn)行更新

1.2 三維OTSU分割算法

在二維OTSU算法的基礎(chǔ)上，三維OTSU分割算法引入鄰域中值作為第3個(gè)特征構(gòu)造了三維灰度直方圖。對(duì)于尺寸為 M×N、灰度范圍為{0，1，…L－1}的數(shù)字圖像，設(shè)像素點(diǎn)（x，y）的灰度值為 f（x，y），定義 h（x，y）和 g（x，y）分別為像素點(diǎn)（x，y）處 r×r的鄰域均值和鄰域中值，g（x，y）、h（x，y）灰度變化范圍均為{0，1，…L－1}。 采用（f（x，y），g（x，y），h（x，y））表示三向量（i，j，k）組成的三維直方圖，3個(gè)坐標(biāo)分別代表像素的灰度值、鄰域均值和鄰域中值，三維直方圖構(gòu)成大小為L×L×L的正方體區(qū)域，如圖 1（a）所示。 向量（i，j，k）發(fā)生的頻率為:

圖1 圖像的三維直方圖Fig.1 Three-Dimension histogram image

采用 sB的跡作 trsB（i，j，k）為類間的離散度測度[3－4]，即：

2 三維OTSU圖像分割算法

由式（4）可知，在計(jì)算三維 OTSU的離散度測度時(shí) ui、uj、uk和Ps（0）只與背景區(qū)域相關(guān)，如果能確定背景區(qū)域的大概范圍，則可進(jìn)一步減少 ui、uj、uk、Ps（0）和 trsB（i，j，k）運(yùn)算量。 由于三維OTSU算法的最佳分割閾值（i*，j*，k*）小于目標(biāo)區(qū)域灰度均值（gm，gm，gm），本文提出一種基于自適應(yīng)粒子群優(yōu)化的三維OTSU圖像分割算法。首先采用最佳熵分割算法初步提取目標(biāo)區(qū)域，選取該目標(biāo)區(qū)域的平均灰度值gm作為背景區(qū)域，即三維 OTSU 背景區(qū)域范圍為（gm×gm×gm，gm＜L），在此基礎(chǔ)上再采用三維OTSU算法進(jìn)行分割。因?yàn)楸尘皡^(qū)域的搜索空間從（L×L×L）降到了（gm×gm×gm），相應(yīng)的 ui、uj、uk、Ps（0）和 trsB（i，j，k）的計(jì)算量也由 O（L3）降為 O（gm3），所以運(yùn)算量進(jìn)一步減少。

在求解 trsB（i，j，k）時(shí)需 7 次乘法和一次除法，運(yùn)算復(fù)雜、計(jì)算量大、占用的時(shí)間長，而粒子群算法具有搜索速度快、效率高，算法簡單等優(yōu)點(diǎn)，本文通過粒子群算法優(yōu)化trsB最大時(shí)三維OTSU的最佳分割閾值i*，j*，k*。由于三維OTSU求解分割閾值含有3個(gè)參數(shù)，因此粒子群初始化為3維向量（i*，j*，k*），每個(gè)向量分別代表像素的灰度值、鄰域均值和鄰域中值。初始化種群大小為80，最大迭代次數(shù)為500次，加速系數(shù)c1=1.49、c2=1.49，其適應(yīng)度函數(shù)fit設(shè)為:

該算法的實(shí)現(xiàn)步驟包括:

1）采用基于最佳熵的分割算法初步提取目標(biāo)區(qū)域并計(jì)算該目標(biāo)區(qū)域的平均灰度值gm。

2）根據(jù)gm自適應(yīng)地設(shè)置三維OTSU背景區(qū)域范圍為（gm×gm×gm，gm＜L），并計(jì)算參數(shù) ui、uj、uk、Ps（0）。

3）初始化粒子群算法的種群大小，迭代次數(shù)、加速系數(shù)c1與c2、慣性權(quán)重w及粒子的初始速度和位置。

4）根據(jù)式（6）計(jì)算粒子的適應(yīng)度值，更新粒子的速度和位置。

5）如果達(dá)到最大迭代次數(shù)，則輸出最佳分割閾值i*，j*，k*，否則轉(zhuǎn)步驟 4）。

3 結(jié)果與分析

實(shí)驗(yàn)是在Intel Dual 1.6 GHz、1 G內(nèi)存、編程環(huán)境為Matlab 7.0的筆記本電腦上進(jìn)行。選取加有均值為零、方差為20的高斯白噪聲的圖像Peppers、Barbara、Lena3幅圖像進(jìn)行測試，圖像大小為512×512像素，表1給出了二維OTSU算法、文獻(xiàn)[4]分割算法和本文分割算法的運(yùn)算時(shí)間，從仿真結(jié)果可以看出，在運(yùn)算時(shí)間方面，本文分割算法的運(yùn)算時(shí)間比二維OTSU算法要長，主要是由于搜索空間從二維擴(kuò)大到三維，再加上三維OTSU算法本身的復(fù)雜性，導(dǎo)致運(yùn)算量增加、計(jì)算時(shí)間長，但明顯優(yōu)于文獻(xiàn)[4]所采用的分割算法，主要是由于背景區(qū)域的搜索空間從（L×L×L）降到了（gm×gm×gm），相應(yīng)參數(shù)計(jì)算量也由O（L3）降為O（gm3），另外采用粒子群算法優(yōu)化最佳分割閾值，進(jìn)一步減少了運(yùn)算時(shí)間；在分割效果方面，從圖2可以看出，對(duì)零均值的高斯白噪聲圖像，本文算法分割效果與文獻(xiàn)[4]分割算法相似，但優(yōu)于二維OTSU算法分割，如在Barbara的臉部和桌子的陰影部分，能夠有效的抑制目標(biāo)和背景處的大部分噪聲。

表1 不同算法的運(yùn)算時(shí)間（s）Tab.1 Different algorithms for computing time（second）

圖2 噪聲方差為20時(shí)不同方法對(duì)圖像的分割結(jié)果Fig.2 Noise variance for 20 different algorithms for segmentation result

4 結(jié) 論

本文從分割圖像自身特點(diǎn)出發(fā)，提出了一種基于自適應(yīng)粒子群優(yōu)化的三維OTSU圖像分割算法。首先根據(jù)目標(biāo)區(qū)域的平均灰度值自適應(yīng)地設(shè)定三維OTSU圖像分割算法的背景區(qū)域搜索范圍，然后采用基于三維OTSU圖像分割算法和粒子群算法對(duì)圖像進(jìn)行分割。該方法綜合利用了圖像目標(biāo)區(qū)域平均灰度值與OTSU算法背景區(qū)域范圍的關(guān)系，減小了計(jì)算的運(yùn)算量。另外，引入粒子群算法優(yōu)化最佳分割閾值，進(jìn)一步提高了算法的運(yùn)行效率。

[1]Otsu N.A threshold selection method from gray-level histograms[J].IEEE Transactions on System Man and Cybernetic，1979，9（1）：62－66.

[2]邱麗君，侯德文，王依才.改進(jìn)的二維Otsu圖像分割方法的研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（33）：195－197.

QIU Li-jun，HOU De-wen，WANG Yi-cai.Research on modified two-dimensional Otsu of image segmentation algorithm[J].ComputerEngineeringandApplications，2010，46（33）：195－197.

[3]景曉軍，李劍峰，劉郁林.一種基于三維最大類間方差的圖像分割算法[J].電子學(xué)報(bào)，2003，31（9）：1281－1285.

JING Xiao jun，LI Jian feng，LIU Yu lin.Image segmentation based on 3-D maximum between-Cluster variance[J]，Acta Electronica Sinica，2003，31（9）：1281－1285.

[4]范九倫，趙鳳，張雪峰.三維OTSU閾值分割方法的遞推算法[J].電子學(xué)報(bào)，2007，35（7）：1398－1402.

FAN Jiu-lun，ZHAO Feng，ZHANG Xue-feng.Recursive algorithm for Three-Dimensional Otsu's thresholding segmentaion method[J].Acta Electronica Sinica，2007，35（7）：1398－1402.

[5]李娟，饒妮妮，廖瑞華，等.基于改進(jìn)粒子群算法的AdHoc網(wǎng)絡(luò)移動(dòng)模型研究[J].電子學(xué)報(bào)，2010，38（1）：222-227.

LI Juan，RAO Ni-ni，LIAO Rui-hua，et al.Mobility model based on the improved-PSO algorithm for ad hoc network[J].Acta Electronica Sinica，2010，38（1）：222-227.

[6]遲玉紅，孫富春，王維軍，等.基于空間縮放和吸引子的粒子群優(yōu)化算法[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（1）：115-130.

CHI Yu-hong,SUN Fu-chun，WANG Wei-jun，et al.An improved particle swarm optimization algorithm with search space zoomed factor and attractor[J].Chinese Journal of Computers，2011，34（1）：115-130.

[7]LV Yan，GONG Qu.Application of weighting 3D-Otsu method in image segmentation[J].Application research of computers，2011，28（4）：1576-1579.