基于粒子群優化的Otsu肺組織分割算法

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

（寧夏大學研究生院，寧夏銀川750021）

基于粒子群優化的Otsu肺組織分割算法

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

（寧夏大學研究生院，寧夏銀川750021）

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

二維Otsu；改進粒子群；孔洞填充；形態學操作；肺組織自動分割

1　引 言

肺組織分割是計算機肺部疾病輔助診斷系統的關鍵技術之一.隨著計算機輔助醫療診斷技術的快速發展，肺組織圖像分割算法對分割的精度和速度提出更高要求.

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

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

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

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

2　基于粒子群優化改進的二維Otsu分割算法

2.1二維Otsu分割算法

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

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

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

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

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

則背景類、目標類的均值向量uA、uB分別為:

圖像的總均值向量u為:

離散度矩陣為:

則離散度測度為:

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

2.2改進粒子群算法

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

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

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

迭代過程中出現當前全局最優解左右兩側的粒子個數不均衡時，則需調整粒子位置使粒子在當前全局最優解兩側的粒子個數均衡.如圖3所示，在j維上，出現粒子在當前最優解右側的個數為6，而在左側的粒子的個數為3的情況時，將右側的兩個粒子，對稱調整到左側.

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

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

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

Step 2.判斷是否滿足迭代條件，滿足則轉到Step 3，否則轉到Step 7.

Step 3.更新pi、pg，計算適應度函數.

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

其中:

其中，w是慣性權重，T是當前迭代次數，Tmax是最大迭代次數，j是粒子所在的維度，c1、c2為學習系數，cmax、cmin為c1、c2的最大值、最小值，r1、r2為介于［0，1］的兩個相互獨立的隨機數.

Step 6.判斷粒子的位置是否搜索過，若搜索過則粒子當前位置變為附近未搜索過的位置.轉到Step 2.

Step 7.終止操作，輸出全局最優解.

2.3基于改進粒子群優化的二維Otsu算法

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

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

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

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

Step 3.判斷是否滿足迭代條件，滿足則轉到Step 4，否則轉到Step 8.

Step 4.根據式（6）計算粒子中每個粒子的適應值.

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

Step 6.基于粒子空間分布對稱，根據式（13）對粒子進行位置調整.

Step 7.判斷粒子的位置是否搜索過，若搜索過，則粒子當前位置變為附近未搜索過的位置.轉到Step3.

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

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

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

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

算法具體步驟如下:

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

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

Step 3.形態學操作:經過閾值分割后，利用開操作去除噪聲，利用閉操作填補病變區域的孔洞，得到二值圖像，進而得到分割圖像.

4　實驗結果和分析

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

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

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

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

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

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

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

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

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

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

圖7　不同CT圖像的肺組織分割結果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圖片的閾值分割處理時間都較少，相比于使用灰度級-梯度直方圖的粒子群優化的OTSU算法，本文算法的處理速度平均提高了16%.

5　結 論

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

［1］ 孟琭，賈同，趙大哲，等.基于Snake模型的病變CT肺部圖像分割［J］.系統仿真學報，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］.自動化學報，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］ 黃崗，李俊，潘金貴.基于粒子群優化方法的2維Otsu快速圖像分割算法［J］.中國圖象圖形學報，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］ 孫越泓.基于粒子群優化算法的圖像分割研究［D］.南京:南京理工大學，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-），男，寧夏西吉人，工學博士，副教授，碩士生導師，主要從事三維醫學圖像可視化、模式識別等方面的研究.E-mail:mayu95@163.com

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

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

2014-12-04；

2015-01-06.

寧夏回族自治區2012年科技攻關計劃項目（No.2012ZYG011）

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

?通信聯系人，E-mail:xingqing_myz@163.com