基于自適應粒子群優化的三維OTSU圖像分割算法

曾業戰，王潤民

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

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

1 基本理論

1.1 粒子群算法

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

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

1.2 三維OTSU分割算法

在二維OTSU算法的基礎上，三維OTSU分割算法引入鄰域中值作為第3個特征構造了三維灰度直方圖。對于尺寸為 M×N、灰度范圍為{0，1，…L－1}的數字圖像，設像素點（x，y）的灰度值為 f（x，y），定義 h（x，y）和 g（x，y）分別為像素點（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個坐標分別代表像素的灰度值、鄰域均值和鄰域中值，三維直方圖構成大小為L×L×L的正方體區域，如圖 1（a）所示。 向量（i，j，k）發生的頻率為:

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

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

2 三維OTSU圖像分割算法

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

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

該算法的實現步驟包括:

1）采用基于最佳熵的分割算法初步提取目標區域并計算該目標區域的平均灰度值gm。

2）根據gm自適應地設置三維OTSU背景區域范圍為（gm×gm×gm，gm＜L），并計算參數 ui、uj、uk、Ps（0）。

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

4）根據式（6）計算粒子的適應度值，更新粒子的速度和位置。

5）如果達到最大迭代次數，則輸出最佳分割閾值i*，j*，k*，否則轉步驟 4）。

3 結果與分析

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

表1 不同算法的運算時間（s）Tab.1 Different algorithms for computing time（second）

圖2 噪聲方差為20時不同方法對圖像的分割結果Fig.2 Noise variance for 20 different algorithms for segmentation result

4 結 論

本文從分割圖像自身特點出發，提出了一種基于自適應粒子群優化的三維OTSU圖像分割算法。首先根據目標區域的平均灰度值自適應地設定三維OTSU圖像分割算法的背景區域搜索范圍，然后采用基于三維OTSU圖像分割算法和粒子群算法對圖像進行分割。該方法綜合利用了圖像目標區域平均灰度值與OTSU算法背景區域范圍的關系，減小了計算的運算量。另外，引入粒子群算法優化最佳分割閾值，進一步提高了算法的運行效率。

[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]邱麗君，侯德文，王依才.改進的二維Otsu圖像分割方法的研究[J].計算機工程與應用，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].電子學報，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].電子學報，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]李娟，饒妮妮，廖瑞華，等.基于改進粒子群算法的AdHoc網絡移動模型研究[J].電子學報，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]遲玉紅，孫富春，王維軍，等.基于空間縮放和吸引子的粒子群優化算法[J].計算機學報，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.