基于改進(jìn)凸包算法的肺區(qū)域分割

張圣璞

摘 要 當(dāng)存在邊緣型肺結(jié)節(jié)的時候，常規(guī)的肺區(qū)域分割方法難以準(zhǔn)確地完成分割。本文針對這一問題進(jìn)行了研究，提出了基于改進(jìn)凸包算法的肺區(qū)域分割方法，實驗結(jié)果證明本文方法能夠較好地分割肺區(qū)域。

關(guān)鍵詞 肺區(qū)域分割 邊界修補 凸包算法

0 序言

現(xiàn)有針對肺部疾病的CAD系統(tǒng)的主要功能包括：肺區(qū)域分割、肺部氣腫的檢測、肺部血管及血管的分割、肺結(jié)節(jié)的檢測與分割及肺結(jié)節(jié)良惡性的判別等。[1]在有限的計算資源內(nèi)如何提高計算速度及準(zhǔn)確度，確定肺區(qū)域并精確地分割提取就顯得十分重要，所以肺部區(qū)域的分割是所有的肺部CAD系統(tǒng)的必要步驟。作為后續(xù)檢測的基礎(chǔ)，肺區(qū)域分割的速度及準(zhǔn)確度對于整個CAD系統(tǒng)的運行速度以及檢測準(zhǔn)確度具有十分重要的影響。[2]以肺結(jié)節(jié)檢測為例，Armato和Sensakovic[3]研究了肺區(qū)域分割對于整個CAD系統(tǒng)的重要性，實驗結(jié)果顯示錯誤的肺區(qū)域分割結(jié)果將會引起5%到17%的肺結(jié)節(jié)漏檢測。

針對這一問題，研究者們提出了一些邊界修補方法。如Armato等[4]提出的滾球法，但是修補結(jié)果對于圓球半徑十分敏感，降低了算法的通用性；王晶[5]利用端點檢測的方法，但是對于過大或者過小的結(jié)節(jié)的修補結(jié)果不好；袁克虹等[6]提出的基于局部凸包的修補方法，但是需要較多的參數(shù)設(shè)置。本文針對以上方法的不足之處，提出了改進(jìn)的二維凸包算法進(jìn)行肺區(qū)域邊界修補，能夠取得較好的分割結(jié)果。

1 二維凸包算法

最早的凸包算法由Graham[7]在1972年提出，主要通過計算點集中各個點之間的夾角以及斜率的大小來判斷各個點是否是凸包上的點。如圖1所示，存在一組二維點集，包含了所有點的最小凸多邊形就是這個點集的凸包。

Graham算法主要包含3個主要步驟：

步驟1：預(yù)處理。如圖2所示，圖（a）是原始點集，處理的第一步就是將其中的n個點進(jìn)行排序，排序規(guī)則為：首先選擇橫坐標(biāo)最小的點（如果有多個，則選取縱坐標(biāo)最小的那個）記為，該點一定會在凸包上，連接該點與其他所有點組成n-1個向量。我們只需要分別計算每個向量與y軸的負(fù)方向之間的夾角，按照夾角的大小由小到大對所對應(yīng)的點進(jìn)行排序并標(biāo)記，排序結(jié)果如圖（b）所示。同時當(dāng)存在方向相同的向量（即兩個點與在同一條直線上）的情況時，根據(jù)模的大小由小到大進(jìn)行排序，最終n個點分別記為，……，，如圖2（b）所示。

步驟2：建立邊緣堆棧。由幾何學(xué)知識可以知道步驟1中得到的點和最后一個點一定在凸包上。所以首先將一定在凸包上的三點、和依次壓入棧re，然后考慮下一個點，首先把點入棧，構(gòu)成棧的棧頂top處為，top-1處為，此時需要利用到下一個點即的信息。利用以上信息判斷和在處旋轉(zhuǎn)關(guān)系，判斷左轉(zhuǎn)還是右轉(zhuǎn)的公式如下：

（1）

如果構(gòu)成左轉(zhuǎn)關(guān)系，則棧頂?shù)狞c也在凸包上，此時入棧，接著判斷下一個元素；如果不構(gòu)成左轉(zhuǎn)關(guān)系，則說明棧頂元素不是凸包內(nèi)的點，此時棧頂元素出棧，入棧，繼續(xù)判斷是否是凸包內(nèi)的點，直到最后一個元素點。

步驟3：根據(jù)以上步驟得到的凸包邊緣堆棧，按照順序連接線段，即可組成點集的二維凸包，如圖2（c）所示。

圖3是肺區(qū)域初分割的結(jié)果示意圖，可以看出當(dāng)存在邊緣型肺結(jié)節(jié)的時候分割出的結(jié)果并不準(zhǔn)確。本文在初步分割的基礎(chǔ)上，使用二維凸包算法對初分割結(jié)果進(jìn)行肺輪廓細(xì)化修補，最終得到完整的肺區(qū)域圖像?？梢灾庇^地發(fā)現(xiàn)圖4（d）所示的結(jié)果與圖3（c）的結(jié)果相比，右上角的病灶區(qū)域也被正確的分割出。

但是在實際的實驗中我們發(fā)現(xiàn)，在利用常規(guī)的二維凸包算法進(jìn)行肺區(qū)域邊界修補的時候，雖然對于肺葉外邊緣的凹陷情況有了較大改善，但是會對肺葉內(nèi)邊緣的輪廓造成一定的破壞，如圖5中箭頭所指的位置，利用本方法邊界修補處理對與肺葉內(nèi)邊緣輪廓正常的凹陷進(jìn)行了錯誤的修補，這不是希望看到的結(jié)果。

2 改進(jìn)的二維凸包算法

統(tǒng)計結(jié)果表明，邊緣型肺結(jié)節(jié)多數(shù)存在于肺葉外側(cè)。針對這一特點本文改進(jìn)二維凸包算法，對肺葉外側(cè)邊界進(jìn)行修補。具體步驟如下：

步驟一：與常規(guī)凸包算法類似，為了減少邊界修補的計算量，首先對得到的二值掩模圖進(jìn)行邊緣檢測得到其邊緣輪廓，以橫坐標(biāo)最小的點為開始掃描，得到了肺區(qū)域邊界點集。如圖6（a）所示。

步驟二：利用常規(guī)二維凸包算法Graham算法步驟一對得到的邊緣輪廓進(jìn)行一次修補過程。首先把步驟一得到的肺區(qū)域邊界點集作為凸包算法處理的點集，然后按照節(jié)中步驟二中相關(guān)規(guī)則求出這組點集合的邊緣堆棧{，……，}，最后同樣根據(jù)左轉(zhuǎn)規(guī)則公式（2）逐一判斷出邊緣堆棧中的點是否是凸包點。

（p3-p1）？p2-p1）=（x3-x1）*（y2-y1）-（x2-x1）*（y3-y1） （2）

步驟三：經(jīng)過以上兩個步驟，我們得到了兩組邊緣點集S1和S3，且S3∈S1，分別是初分割結(jié)果的肺區(qū)域邊界點集和凸包算法計算出的凸包點集。找出集合S3中縱坐標(biāo)最大和最小的兩個點qmax和qmin，且qmax，qmin∈S1。

以右肺為例，我們按照一定的規(guī)則合并點集S1和S3就可以得到一個全新的點集，其中和是凸包點，而是未修補的邊界點。這樣按順序連接新的點集就得到了如圖6（c）所示的修補結(jié)果，其中肺葉外邊緣是凸包計算修補之后的結(jié)果，而肺葉內(nèi)邊界則是未修補的肺區(qū)域邊界。這樣在一定程度上既修補了肺葉外邊界上的凹陷，又避免了因為修補而對肺葉內(nèi)邊界的過度修補。

3 實驗結(jié)果分析

本文在公開的LIDC數(shù)據(jù)集上進(jìn)行實驗，選擇了其中存在邊緣型肺結(jié)節(jié)的圖像進(jìn)行具體對比實驗。結(jié)果如圖7所示。

圖7（a）是原圖像，肺部邊緣存在肺結(jié)節(jié)，圖7（b）是醫(yī)生手工分割的金標(biāo)準(zhǔn)結(jié)果，圖7（c）是經(jīng)過閾值法分割后的肺區(qū)域結(jié)果，可以發(fā)現(xiàn)由于存在邊緣型肺結(jié)節(jié)，僅利用閾值法分割出的肺部邊緣上存在明顯的凹陷，把肺結(jié)節(jié)分割到了肺區(qū)域以外，不利于后續(xù)的疾病診斷。圖7（d）是本文方法分割結(jié)果。實驗結(jié)果顯示本文方法對于邊緣型肺結(jié)節(jié)引起的肺區(qū)域邊界凹陷具有較好的修補效果。

4 總結(jié)

本文針對因邊緣型肺結(jié)節(jié)造成的肺區(qū)域邊界分割不準(zhǔn)確的情況，使用改進(jìn)的二維凸包算法進(jìn)行肺區(qū)域邊界修補，在傳統(tǒng)的二維凸包算法的基礎(chǔ)上，根據(jù)人體肺部生理解剖結(jié)構(gòu)對凸包算法進(jìn)行約束，避免了傳統(tǒng)二維凸包修補方法造成過度修補的情況。

參考文獻(xiàn)

[1] Armato Iii S G， Giger M L， Macmahon H. Method and system for the segmentation of lung regions in lateral chest radiographs： US， US6335980[P].2002.

[2] 聶生東，李雯，許建榮，等.自動分割CT圖像中肺實質(zhì)的方法[J].中國醫(yī)學(xué)影像技術(shù)，2006.22（9）：1428-1431.

[3] 楊聃.三維肺部CT圖像中的結(jié)節(jié)自動識別[D].華中科技大學(xué)，2007.

[4] 3Rd A S， Sensakovic W F. Automated lung segmentation for thoracic CT impact on computer-aided diagnosis[J]. Academic Radiology，2004.11（9）：1011-21.

[5] 王晶.基于CT圖像的肺實質(zhì)分割算法研究[D].沈陽大學(xué)，2010.

[6] 袁克虹，向蘭茜.用于計算機(jī)輔助診斷的肺實質(zhì)自動分割方法[J].清華大學(xué)學(xué)報（自然科學(xué)版），2011（1）：90-95.

[7] Graham R L. An efficient algorith for determining the convex hull of a finite planar set[J]. Information Processing Letters，1972.1（4）：132-133.