孟亞州，馬 瑜，白 冰，高林爽

（寧夏大學(xué)研究生院，寧夏銀川750021）

基于粒子群優(yōu)化的Otsu肺組織分割算法

孟亞州，馬 瑜?，白 冰，高林爽

（寧夏大學(xué)研究生院，寧夏銀川750021）

為減少肺組織分割算法的運算時間，提出了一種基于粒子群優(yōu)化的Otsu肺組織改進自動分割算法.針對傳統(tǒng)粒子群優(yōu)化的二維Otsu算法中二維直方圖計算量大、粒子搜索容易陷入局部最優(yōu)解的缺陷，使用灰度級-梯度二維直方圖減少二維直方圖的計算量，并減小粒子搜索范圍，采用基于粒子空間對稱分布的改進粒子群獲取最佳閾值.算法實現(xiàn)過程中利用孔洞填充算法去除背景，基于形態(tài)學(xué)操作去除噪聲、修補病變區(qū)域產(chǎn)生的孔洞.仿真實驗結(jié)果顯示，本文算法對圖像尺寸為512像素×512像素CT圖像的閾值分割時間約為0.2 s，比基于灰度級-鄰域均值二維直方圖的粒子群優(yōu)化的Otsu算法的閾值分割速度提高了約16%.較好地實現(xiàn)了胸腔CT圖像的肺組織自動分割，與傳統(tǒng)算法相比較，本算法在保證分割精度的基礎(chǔ)上分割速度明顯提升.

二維Otsu；改進粒子群；孔洞填充；形態(tài)學(xué)操作；肺組織自動分割

1　引 言

肺組織分割是計算機肺部疾病輔助診斷系統(tǒng)的關(guān)鍵技術(shù)之一.隨著計算機輔助醫(yī)療診斷技術(shù)的快速發(fā)展，肺組織圖像分割算法對分割的精度和速度提出更高要求.

近年來，肺組織分割算法的研究日益得到關(guān)注.2009年，孟琭等人提出了基于Snake模型的病變CT肺部圖像分割算法，無論肺內(nèi)有無病變，分割效果均比較理想，但算法運行時間相對較長［1］.2012年，Tetyana Ivanovska等人先初步分離出肺和氣管，然后將肺和氣管分離開［2］. 2013年，Ying Wei等人利用三維區(qū)域連通標(biāo)記、三維區(qū)域生長法對肺組織進行分割，分割精度較高，但算法復(fù)雜度相對較高［3］.Shiloah Elizabeth Darmanayagam等人利用多層前饋神經(jīng)網(wǎng)絡(luò)判斷肺組織分割是否完全，利用閾值法、形態(tài)學(xué)處理修補肺組織.雖然對病變區(qū)域分割效果理想，但是算法處理時間較長［4］.

傳統(tǒng)閾值法實現(xiàn)簡單、快速，但分割精度較低，對有病變的胸部CT圖像分割效果較差.區(qū)域生長法屬半自動分割方法，而且對種子點及生長合并規(guī)則的選取比較敏感.基于活動輪廓模型的分割法，效果較好，但是分割需花費大量時間.基于模式分類的胸部CT分割方法，訓(xùn)練樣本需要人為選取，而且由于要提取多個特征，處理時間較長.

針對肺部疾病計算機輔助診斷技術(shù)對全自動性、實時性要求較高，因此肺組織分割算法不僅僅要求分割精度，還要求算法必須全自動、快速分割.

綜上考慮，本文提出了一種基于改進粒子群優(yōu)化Otsu的胸腔CT圖像快速自動分割算法，使用灰度級-梯度二維直方圖，大大減少了直方圖的計算量，同時減少了粒子的搜索范圍.使用改進粒子群算法來搜索最優(yōu)分割閾值，不僅加快了傳統(tǒng)OTSU算法的運算速度，也避免了過早收斂陷入局部最優(yōu)解的現(xiàn)象.

2　基于粒子群優(yōu)化改進的二維Otsu分割算法

2.1二維Otsu分割算法

Otsu算法是日本學(xué)者Otsu提出的一種自動閾值分割算法［5］.該算法在圖像的灰度直方圖基礎(chǔ)上，將目標(biāo)和背景的類間方差最大化作為自動確定分割閾值的依據(jù).一維Otsu算法在信噪比低的圖像中分割效果不理想，而二維Otsu利用了圖像的局部信息，有效地避免了噪聲的影響［6］.考慮到胸腔CT圖像也存在噪聲，因此本文采用二維Otsu算法.

圖1　兩種二維直方圖的比較Fig.1　Comparison of two different two-dimensional histogram

如圖1所示，給定一個分割閾值（s，t），二維直方圖分成0、1、2、3四個區(qū)域，0、1區(qū)域?qū)?yīng)圖像的背景類、目標(biāo)類，2、3區(qū)域?qū)?yīng)圖像的邊界和噪聲.在圖（a）中，灰度級-鄰域均值二維直方圖存在錯分的情況:對應(yīng)圖像背景類、目標(biāo)類的0、1區(qū)域的左上角、右下角可能存在邊界和噪聲，對應(yīng)邊界和噪聲的2區(qū)域的右下角處、3區(qū)域的左上角處可能存在目標(biāo)或背景點.計算二維直方圖需要對整個二維直方圖計算；而灰度級-梯度二維直方圖如圖（b）所示，信息主要分布在直方圖的下方，不存在錯分情況，計算二維直方圖時，只需計算0、1區(qū)域，并且粒子群的粒子搜索范圍為0、1區(qū)域，有效減少了粒子的搜索范圍，進而縮短算法運算時間［7］.基于以上考慮，本文采用灰度級-梯度二維直方圖.

二維Otsu具體算法概述如下:設(shè)一幅大小為M×N的圖像有L個灰度級，灰度值為i、其梯度為j的像素點個數(shù)為nij，則其概率pij為:

以閾值變量（s，t）將灰度圖像的像素分為背景類A、目標(biāo)類B，則背景類A、目標(biāo)類B出現(xiàn)的概率PA、PB分別為:

則背景類、目標(biāo)類的均值向量uA、uB分別為:

圖像的總均值向量u為:

離散度矩陣為:

則離散度測度為:

由于離散度測度越大代表兩類間的差別越大，因此選取離散度測度達到最大值時對應(yīng)的分割閾值作為最佳閾值（s?，t?）［8］，即

2.2改進粒子群算法

粒子群算法是Kennedy和Eberhart受到飛鳥集群活動的規(guī)律性啟發(fā)提出的一種基于群智能的隨機優(yōu)化算法［9］.傳統(tǒng)粒子群算法存在收斂速度慢、容易陷入局部最優(yōu)解的問題［10］，改進算法則有效解決了這兩類問題.本文中粒子群算法選用基于粒子空間分布的粒子群算法，利用胸腔CT圖像的灰度級-梯度直方圖分布特性，減少粒子的搜索范圍，慣性權(quán)重、學(xué)習(xí)系數(shù)采用線性變化策略.粒子在運動初期，提高全局搜索能力，更多向群體學(xué)習(xí)；粒子在運動后期，提高局部搜索能力，加強自我學(xué)習(xí)能力［11］.

圖2　粒子空間位置分布Fig.2　Space distribution of particles

粒子搜索在迭代過程中，會出現(xiàn)粒子位置在局部最優(yōu)解一側(cè)的情況（如圖2（a）所示），這樣會導(dǎo)致粒子容易陷入局部最優(yōu)解.為避免此類情況，迭代過程中需要調(diào)整粒子位置提高種群的多樣性，使粒子的位置盡量在局部最優(yōu)解的周圍（如圖2（b）所示）［11-12］.

迭代過程中出現(xiàn)當(dāng)前全局最優(yōu)解左右兩側(cè)的粒子個數(shù)不均衡時，則需調(diào)整粒子位置使粒子在當(dāng)前全局最優(yōu)解兩側(cè)的粒子個數(shù)均衡.如圖3所示，在j維上，出現(xiàn)粒子在當(dāng)前最優(yōu)解右側(cè)的個數(shù)為6，而在左側(cè)的粒子的個數(shù)為3的情況時，將右側(cè)的兩個粒子，對稱調(diào)整到左側(cè).

圖3　粒子基于空間對稱分布調(diào)整示意圖Fig.3　The sketch map of adjusting particle's position based on symmetrical distribution

改進粒子群算法概述如下:

Step 1.粒子群初始化.設(shè)種群共有N個粒子，其搜索空間為d維空間，則第i個微粒的位置可表示為xi=（xi1，xi2，...，xid），其飛行速度表示為vi=（vi1，vi2，...，vid）.每個粒子所經(jīng)歷過的最好適應(yīng)值的位置為pi=（pi1，pi2，...，pid），種群所有微粒所經(jīng)歷過的適應(yīng)值最好的位置為全局最好位置，記pg=（pg1，pg2，...，pgd）.

Step 2.判斷是否滿足迭代條件，滿足則轉(zhuǎn)到Step 3，否則轉(zhuǎn)到Step 7.

Step 3.更新pi、pg，計算適應(yīng)度函數(shù).

Step 4.速度、位置更新.對粒子群算法的每一次迭代，速度和位置的更新方程為:

其中:

其中，w是慣性權(quán)重，T是當(dāng)前迭代次數(shù)，Tmax是最大迭代次數(shù)，j是粒子所在的維度，c1、c2為學(xué)習(xí)系數(shù)，cmax、cmin為c1、c2的最大值、最小值，r1、r2為介于［0，1］的兩個相互獨立的隨機數(shù).

Step 6.判斷粒子的位置是否搜索過，若搜索過則粒子當(dāng)前位置變?yōu)楦浇此阉鬟^的位置.轉(zhuǎn)到Step 2.

Step 7.終止操作，輸出全局最優(yōu)解.

2.3基于改進粒子群優(yōu)化的二維Otsu算法

二維Otsu算法是通過搜索到能夠使背景類和目標(biāo)類差別最大的閾值，進行閾值分割.傳統(tǒng)Otsu算法采用窮舉的方式去搜索，計算量大、耗時多.利用粒子群算法優(yōu)化的Otsu分割算法，能夠大大減少傳統(tǒng)Otsu算法的計算量，但是傳統(tǒng)粒子群算法存在過早收斂陷入局部最優(yōu)解的缺點.二維直方圖選擇上，為節(jié)省算法運行時間，避免出現(xiàn)使用灰度級-鄰域均值二維直方圖出現(xiàn)目標(biāo)或背景與噪聲或邊界錯分的情況，本文算法采用灰度級-梯度二維直方圖；粒子群算法選擇上，采用基于粒子空間對稱分布的改進粒子群算法去優(yōu)化二維Otsu算法來避免陷入局部最優(yōu)解.利用圖像在灰度級-梯度二維直方圖的分布特性，不僅減少了直方圖的計算量，也縮小了粒子的搜索范圍，在保證了分割精度的同時，又有效提高了分割的速度.

具體算法的基本步驟如下:

Step 1.生成m個粒子，其搜索空間為二維空間，則第i個微粒的位置可表示為xi=（xi1，xi2），考慮到圖像在灰度級-梯度二維直方圖的分布特性，其搜索范圍為圖1（b）圖的0、1區(qū)域，即xi1在［Gmin，Gmax］隨機生成，xi2在［Gradmin，Gradmax］隨機生成，每個粒子的速度在［-Vmax，Vmax］隨機生成，設(shè)置最大迭代次數(shù)N，慣性權(quán)重最大值、最小值，學(xué)習(xí)系數(shù)最大值、最小值.其中，Gmin、Gmax為圖像的灰度級最小值、最大值，Gradmin、Gradmax為圖像的梯度最小值、最大值.

Step 2.計算圖像的灰度值-梯度二維直方圖.

Step 3.判斷是否滿足迭代條件，滿足則轉(zhuǎn)到Step 4，否則轉(zhuǎn)到Step 8.

Step 4.根據(jù)式（6）計算粒子中每個粒子的適應(yīng)值.

Step 5.根據(jù)式（8）、（9）更新第t+1次迭代后各個粒子的位置、速度.

Step 6.基于粒子空間分布對稱，根據(jù)式（13）對粒子進行位置調(diào)整.

Step 7.判斷粒子的位置是否搜索過，若搜索過，則粒子當(dāng)前位置變?yōu)楦浇此阉鬟^的位置.轉(zhuǎn)到Step3.

Step 8.將改進粒子群搜索到的全局最優(yōu)解作為分割閾值，對圖像進行閾值分割，輸出圖像.

圖4　基于改進粒子群的二維Otsu算法流程圖Fig.4　Flow chart of the two-dimensional Otsu based improved PSO

3　基于粒子群優(yōu)化Otsu的肺組織改進自動分割算法

針對傳統(tǒng)肺組織分割算法普遍存在分割速度慢的缺陷，本文基于胸腔CT圖像中心區(qū)域近似孔洞特性，利用2.3節(jié)中改進粒子群優(yōu)化的Otsu算法對胸腔CT圖像進行肺組織分割，以此來提高分割速度.

算法具體步驟如下:

Step 1.圖像預(yù)處理:利用胸腔CT圖像中心區(qū)域近似孔洞特性，進行孔洞填充操作后得到背景區(qū)域，與原圖像相減，得到去除背景的預(yù)處理圖像；

Step 2.閾值分割:采用基于改進粒子群優(yōu)化的Otsu算法，對胸腔CT圖像進行肺組織閾值分割；

Step 3.形態(tài)學(xué)操作:經(jīng)過閾值分割后，利用開操作去除噪聲，利用閉操作填補病變區(qū)域的孔洞，得到二值圖像，進而得到分割圖像.

4　實驗結(jié)果和分析

為驗證基于粒子群優(yōu)化的二維Otsu改進算法的分割精度和速度，比較本文算法和傳統(tǒng)Otsu算法、文獻［13］中基于灰度級-鄰域均值二維直方圖的粒子群優(yōu)化的Otsu算法的分割精度和速度.采用來自寧夏第四人民醫(yī)院的肺結(jié)核病臨床數(shù)據(jù).圖像尺寸為512像素×512像素，實驗硬件環(huán)境為Windows8.1系統(tǒng)、主頻2.6 GHz、內(nèi)存4 GB的PC筆記本，軟件開發(fā)平臺為MATLAB R2008a.

圖5　不同閾值算法分割結(jié)果對比Fig.5　Results of segmentation by different algorithm

表1　不同算法的最佳閾值、分割時間對比Tab.1　The best thresholds and processing time by different algorithm

圖5為使用傳統(tǒng)二維Otsu算法、使用文獻［13］中的基于灰度級-鄰域均值二維直方圖的粒子群優(yōu)化Otsu算法、使用本文的閾值分割算法對圖5（a）原圖像分割的結(jié)果對比.

由圖5可得:本文算法與傳統(tǒng)二維Otsu算法、文獻［13］中使用灰度級-鄰域均值二維直方圖的粒子群優(yōu)化的Otsu算法的閾值分割結(jié)果近似，均不影響后續(xù)的肺組織形態(tài)學(xué)分割.

圖6　肺組織分割算法Fig.6　Lung segmentation algorithm

表1為使用圖5中3種不同閾值分割算法獲取的最佳閾值、分割時間對比.由上可得:文獻［13］中，粒子群優(yōu)化的傳統(tǒng)二維Otsu算法處理時間為傳統(tǒng)二維Otsu算法處理時間的1/3左右，由于使用的灰度級-鄰域均值二維直方圖本身存在缺陷，而本文算法使用的是灰度級-梯度二維直方圖，無論在直方圖的計算，還是粒子群的搜索，都能減少算法的處理時間，因此本文算法處理時間又比文獻［13］算法節(jié)省16%.

圖6描述的是對胸腔CT圖像進行肺組織分割的過程圖.圖6（a）為胸腔CT原圖像，圖6（b）為對（a）圖填充孔洞操作后的圖像，圖6（c）為圖6（b）減圖6（a）得到的去除背景的圖像，圖6（d）對圖6（c）利用本文算法進行閾值分割后的圖像，圖6（e）對圖6（d）進行形態(tài)學(xué)操作去除噪聲、填充孔洞后的圖像，圖6（f）為最終分割結(jié)果.

圖7是對3幅不同的胸腔CT圖像進行肺組織分割的結(jié)果對比.圖7（a）、7（c）、7（e）為胸腔CT原圖像，圖7（b）、7（d）、7（f）分別為對圖7（a）、7（c）、7（e）的肺組織分割結(jié)果，圖7（f）、7（g）、7（h）為利用半徑分別為13、22、28的結(jié)構(gòu)元素對圖7（e）進行形態(tài)學(xué)操作后得到的分割結(jié)果.

由圖6、圖7可得:本文算法能夠有效地對類似圖7（a）、7（c）以及正常的胸腔CT圖像分割出肺組織，對類似圖7（e）進行分割的分割效果較差，通過增大形態(tài)學(xué)處理所用結(jié)構(gòu)元素的半徑，可以修補大部分孔洞（如圖6（f）、7（g）、7（h））.

圖7　不同CT圖像的肺組織分割結(jié)果Fig.7　Lung segmentation results of different CT image

表2為使用圖5中的3種Otsu算法分別對胸腔CT原圖像1、2、3進行閾值分割的處理時間對比.

表2　不同算法的閾值分割處理時間對比Tab.2　Processing time of different threshold segmentation algorithm

由表2可得，本文算法對于不同胸部CT圖片的閾值分割處理時間都較少，相比于使用灰度級-梯度直方圖的粒子群優(yōu)化的OTSU算法，本文算法的處理速度平均提高了16%.

5　結(jié) 論

提出了一種基于改進粒子群優(yōu)化Otsu的胸腔CT圖像快速自動分割算法.使用灰度級-梯度二維直方圖減少直方圖的計算量，減小粒子群的搜索范圍，達到了節(jié)省分割時間的目的.對圖像尺寸為512像素×512像素CT圖像的閾值分割時間約為0.2 s，相比于文獻［13］中使用灰度級-鄰域均值直方圖的粒子群優(yōu)化的Otsu算法，本文算法的處理速度平均提高了16%.而且在分割精度上，與傳統(tǒng)的二維Otsu算法以及文獻［13］粒子群優(yōu)化的Otsu算法相比，閾值分割精度幾乎一致，不影響肺組織分割結(jié)果.

［1］ 孟琭，賈同，趙大哲，等.基于Snake模型的病變CT肺部圖像分割［J］.系統(tǒng)仿真學(xué)報，2009，21（15）:4603-4606，4612.

Meng L，Jia T，Zhao D Z，et al.Pathological lung segmentation for CT images based on Snake model［J］.Journal of System Simulation，2009，21（15）:4603-4606，4612.（in Chinese）

［2］ Ivanovska T，Hegenscheid K，Laqua R，et al.A fast and accurate automatic lung segmentation and volumetry method for MR data used in epidemiological studies［J］.Computerized Medical Imaging and Graphics，2012，36（4）:281-293.

［3］ Wei Y，Shen G，Li J J.A fully automatic method for lung parenchyma segmentation and repairing［J］.Journal of Digital Imaging，2013，26（3）:483-495.

［4］ Darmanayagam S E，Harichandran K N，Cyril S R R，et al.A novel supervised approach for segmentation of lung parenchyma from chest CT for computer-aided diagnosis［J］.Journal of Digital Imaging，2013，26（3）:496-509.［5］ Otsu N.A threshold selection method from gray-level histograms［J］.IEEE Transactions on System，Man and Cy-bernetic，1979，9（1）:62-66.

［6］ 劉健莊，栗文青.灰度圖像的二維Otsu自動閾值分割法［J］.自動化學(xué)報，1993，19（1）:101-105.

Liu J Z，Li W Q.The automatic thresholding of gray-level pictures via two-dimensional OTSU method［J］.Acta Automatica Sinica，1993，19（1）:101-105.（in Chinese）

［7］ 吳成茂，田小平，譚鐵牛.二維Otsu法閾值法的分割快速迭代算法［J］.模式識別與人工智能，2008，21（6）:746-757.

Wu C M，Tian X P，Tan T N.Fast iterative algorithm for two-dimensional Otsu Thresholding method［J］.Pattern Recognition and Artificial Intelligence，2008，21（6）:746-757.（in Chinese）

［8］ 黃崗，李俊，潘金貴.基于粒子群優(yōu)化方法的2維Otsu快速圖像分割算法［J］.中國圖象圖形學(xué)報，2011，16（3）: 377-381.

Huang G，Li J，Pan J G.A fast 2D Otsu image segmentation algorithm based on particle swam optimization algorithm［J］.Journal of Image and Graphics，2011，16（3）:377-381.（in Chinese）

［9］ Kennedy J，Eberthart R C.Particle Swarm Optimization［C］.Proc.IEEE Int.Conf.on Neural Networks，Piscataway:IEEE，1995:1942-1948.

［10］ 王洪濤，李丹.基于改進粒子群算法的圖像邊緣檢測研究［J］.液晶與顯示，2014，29（5）:800-804.

Wang H T，Li D.Image edge detection research based on improved particle swarm optimization algorithm［J］. Chinese Journal of Liquid Crystals and Displays，2014，29（5）:800-804.（in Chinese）

［11］ 孫越泓.基于粒子群優(yōu)化算法的圖像分割研究［D］.南京:南京理工大學(xué)，2011.

Sun Y H.Image segmentation research based on particle swarm optimization algorithm［D］.Nanjing:Nanjing University of Science&Technology，2011.（in Chinese）

［12］ 孫越泓，魏建香，夏德深.一種基于粒子對稱分布多樣性的PSO算法［J］.模式識別與人工智能，2010，23（2）: 137-143.

Sun Y H，Wei J X，Xia D S.An improved PSO based on diversity of particle symmetrical distribution［J］.Pattern Recognition and Artificial Intelligence，2010，23（2）:137-143.（in Chinese）

［13］ Helen R，Kamaraj N，Selvi K，et al.Segmentation of pulmonary parenchyma in CT lung images based on 2D Otsu optimized by PSO［C］.Proceedings of 2011 International Conference on Emerging Trends in Electrical and Computer Technology（ICETECT），Tamil Nadu:IEEE，2011:536-541.

Improved lung segmentation algorithm based on 2D Otsu optimized by PSO

MENG Ya-zhou，MA Yu?，BAI Bing，GAO Lin-shuang

（School of Graduate，Ningxia University，Yinchuan 750021，China）

This paper develops an automatic segmentation method of lung image using two dimensional Otsu method based on particle swarm optimization in order to reduce operation time.Aiming at the shortage of the traditional two dimensional Otsu based on particle swarm optimization，which the calculating quantity is large and standard particle swarm algorithm is easy to fall into local optimum，an improved lung segmentation based on 2D Otsu optimized by PSO is proposed in this paper.Using the grayscale-gradient two-dimensional histogram，not only reduces the amount of histogram's calculation，but also narrows the searching area of particles.The algorithm uses the improved PSO which based on diversity of particle symmetrical distribution to search optimal threshold.In the process of algorithm，the region filling algorithm is used to remove background in order to make the threshold segmentation of lung better，and the morphology operations to remove noise and repair holes which in the target image.The threshold segmenting time in this algorithm is about 0.2 s，increased about 16%than the speed of the traditional Otsu threshold segmentation optimized by PSO，the size of the CT images is 512×512 pixels in this experiment.The segmentation algorithm in this paper can seg-ment the lung in CT image automatically，not only ensures the accuracy of the segmentation，but also improves the speed of the segmentation in comparison with conventional algorithms.

two-dimensional Otsu；improved PSO；region filling；morphological operations；automatic lung segmentation

TP394.1

A doi:10.3788/YJYXS20153006.1000

1007-2780（2015）06-1000-08

孟亞州（1991-），男，山東鄒城人，碩士研究生，主要從事圖像處理、模式識別方面的研究.E-mail:xingqing_ myz@163.com

馬瑜（1974-），男，寧夏西吉人，工學(xué)博士，副教授，碩士生導(dǎo)師，主要從事三維醫(yī)學(xué)圖像可視化、模式識別等方面的研究.E-mail:mayu95@163.com

白冰（1990-），男，碩士研究生，主要研究方向為圖像處理.E-mail:fengfubaibing@163.com

高林爽（1990-），女，碩士研究生，主要研究方向為圖像處理.E-mail:1046935271@qq.com

2014-12-04；

2015-01-06.

寧夏回族自治區(qū)2012年科技攻關(guān)計劃項目（No.2012ZYG011）

Supported by Key Science and Technology Program of Ningxia Hui Autonomous Region，China（No. 2012ZYG011）

?通信聯(lián)系人，E-mail:xingqing_myz@163.com