基于改進凸包算法的肺區域分割

張圣璞

摘 要 當存在邊緣型肺結節的時候，常規的肺區域分割方法難以準確地完成分割。本文針對這一問題進行了研究，提出了基于改進凸包算法的肺區域分割方法，實驗結果證明本文方法能夠較好地分割肺區域。

關鍵詞 肺區域分割 邊界修補 凸包算法

0 序言

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

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

1 二維凸包算法

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

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

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

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

（1）

如果構成左轉關系，則棧頂的點也在凸包上，此時入棧，接著判斷下一個元素；如果不構成左轉關系，則說明棧頂元素不是凸包內的點，此時棧頂元素出棧，入棧，繼續判斷是否是凸包內的點，直到最后一個元素點。

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

圖3是肺區域初分割的結果示意圖，可以看出當存在邊緣型肺結節的時候分割出的結果并不準確。本文在初步分割的基礎上，使用二維凸包算法對初分割結果進行肺輪廓細化修補，最終得到完整的肺區域圖像。可以直觀地發現圖4（d）所示的結果與圖3（c）的結果相比，右上角的病灶區域也被正確的分割出。

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

2 改進的二維凸包算法

統計結果表明，邊緣型肺結節多數存在于肺葉外側。針對這一特點本文改進二維凸包算法，對肺葉外側邊界進行修補。具體步驟如下：

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

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

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

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

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

3 實驗結果分析

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

圖7（a）是原圖像，肺部邊緣存在肺結節，圖7（b）是醫生手工分割的金標準結果，圖7（c）是經過閾值法分割后的肺區域結果，可以發現由于存在邊緣型肺結節，僅利用閾值法分割出的肺部邊緣上存在明顯的凹陷，把肺結節分割到了肺區域以外，不利于后續的疾病診斷。圖7（d）是本文方法分割結果。實驗結果顯示本文方法對于邊緣型肺結節引起的肺區域邊界凹陷具有較好的修補效果。

4 總結

本文針對因邊緣型肺結節造成的肺區域邊界分割不準確的情況，使用改進的二維凸包算法進行肺區域邊界修補，在傳統的二維凸包算法的基礎上，根據人體肺部生理解剖結構對凸包算法進行約束，避免了傳統二維凸包修補方法造成過度修補的情況。

參考文獻

[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圖像中肺實質的方法[J].中國醫學影像技術，2006.22（9）：1428-1431.

[3] 楊聃.三維肺部CT圖像中的結節自動識別[D].華中科技大學，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圖像的肺實質分割算法研究[D].沈陽大學，2010.

[6] 袁克虹，向蘭茜.用于計算機輔助診斷的肺實質自動分割方法[J].清華大學學報（自然科學版），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.