基于二叉樹結(jié)構(gòu)的支氣管解剖結(jié)構(gòu)識別技術(shù)

王曦，李巖芳

（長春理工大學(xué)　計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春　130022）

基于二叉樹結(jié)構(gòu)的支氣管解剖結(jié)構(gòu)識別技術(shù)

王曦，李巖芳

（長春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春130022）

針對支氣管圖像匹配精度較差、效率過低問題，提出了一種解剖識別支氣管的方法。該方法包含對胸部CT圖像中支氣管的提取、支氣管的細(xì)化和支氣管的識別。通過對支氣管圖像細(xì)化得到單像素、連通的支氣管骨架圖，根據(jù)支氣管骨架圖的分支點(diǎn)建立二叉樹模型，并將其與匹配模板進(jìn)行匹配，最后標(biāo)記支氣管分支名稱信息。實(shí)驗(yàn)表明提出的方法在匹配效率和精度上有明顯的改進(jìn)，可以在1-4級分支很好地標(biāo)記出結(jié)果。

識別；細(xì)化；二叉樹

在最近幾年里，醫(yī)學(xué)圖像處理技術(shù)已經(jīng)有了非常顯著的提升。現(xiàn)在醫(yī)生可以使用多層螺旋CT來獲得高精度的CT斷層掃描，很大程度上提高了醫(yī)生對疾病的正確診斷率［1］。這使得醫(yī)學(xué)圖像處理技術(shù)成為了人們目前研究和關(guān)注的熱點(diǎn)。人們可以通過高精度的CT斷層掃描來幫助分割肺部支氣管，減少支氣管的斷裂等誤差。這些先進(jìn)的計(jì)算機(jī)輔助診斷技術(shù)對于肺部疾病的輔助診斷來說是十分關(guān)鍵的，在高精度的CT斷層掃描圖像上分割出支氣管樹，然后對提取的支氣管樹進(jìn)行細(xì)化處理，得到單像素寬的、連通的支氣管樹骨架，這對于肺部支氣管的解剖標(biāo)記有十分重要的指導(dǎo)意義［2］。

通常醫(yī)生使用已知的解剖學(xué)知識來診斷醫(yī)學(xué)圖像，診斷的規(guī)則是由目標(biāo)區(qū)域的解剖學(xué)名稱所構(gòu)成的，如果想要通過計(jì)算機(jī)來進(jìn)行輔助診斷，那么應(yīng)該識別從CT圖像中提取部位的解剖名稱。若能夠分配正確的解剖名稱到目標(biāo)區(qū)域，那么就能夠通過使用解剖名稱所描述的診斷規(guī)則來幫助醫(yī)生診斷［3］。

在支氣管匹配標(biāo)記方面，Mori K提出一種基于知識庫標(biāo)記的算法［4］，這個算法的優(yōu)點(diǎn)是能夠自動進(jìn)行支氣管的匹配標(biāo)記，但是并沒有包含解剖變化，僅能處理每個支氣管樹中的部分分支，此外這個方法對于丟失分支和假陽性分支很敏感。Park提出一種基于聯(lián)合圖的樹的匹配方法［5］，但是這種方法僅適用于部分?jǐn)?shù)據(jù)，并且不能容忍支氣管中出現(xiàn)假陽性分支。Pisupati提出一種基于動態(tài)規(guī)劃的分支點(diǎn)匹配算法［6］，然而這種方法也有不可避免的缺陷，僅適用于非常相似的兩者之間的匹配。Kitaoka提出一種使用數(shù)學(xué)虛位作為參照的標(biāo)記算法［7］，通過匹配目標(biāo)樹與虛位來標(biāo)記支氣管樹，這個算法的缺陷在于不能自動處理錯誤分支，需要通過手動進(jìn)行剪枝處理錯誤的支氣管分支。Juerg Tschirren在基于知識庫匹配算法的基礎(chǔ)上做出了改進(jìn)［8］，引進(jìn)了平行邊來進(jìn)行支氣管分支的剪枝處理，消除了錯誤的分支，并且通過剛性配準(zhǔn)減少了問題的規(guī)模，提高了計(jì)算速度，但是這中方法在支氣管的細(xì)小分支上的處理效果并不理想。Sinya Ema提出一種使用模板的標(biāo)記方法［9］，把支氣管分成右上肺葉、右中下肺葉、左上肺葉和左下肺葉（RU、RL、LU、LL）四個部分，并且為每個部分都準(zhǔn)備了大量的分支模型，這個方法在每個分支點(diǎn)選擇最適合的候選模型，并且對于肺的右上部分提出了一個特別的標(biāo)記步驟。右上肺葉RU部分的標(biāo)記分三個步驟：（1）進(jìn)行臨時的標(biāo)記；（2）選擇匹配合適的分支模型；（3）進(jìn)行RU部分的最終標(biāo)記；其它三個部分，通過計(jì)算適宜的評估值來選擇合適分支模型然后執(zhí)行標(biāo)記，這種方法很依賴于模板的準(zhǔn)確性。

傳統(tǒng)的樹型匹配方法，由于不知道一個節(jié)點(diǎn)有多少子樹，在構(gòu)造過程中，每當(dāng)增加節(jié)點(diǎn)時都要重新分配內(nèi)存空間，導(dǎo)致效率低，使用指針時，每個節(jié)點(diǎn)又會分配指針空間同樣造成內(nèi)存浪費(fèi)。針對上述方法中存在的缺陷，本文提出了一種通過把分割后的支氣管轉(zhuǎn)換為二叉樹結(jié)構(gòu)進(jìn)行匹配的方法，重點(diǎn)解決了匹配精度不高、算法效率過低的問題。本文統(tǒng)一使用了公開的胸部CT數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，并對支氣管的匹配結(jié)果進(jìn)行了量化評估。

1　實(shí)驗(yàn)方法

如圖1所示，支氣管的解剖結(jié)構(gòu)識別過程主要分為三個步驟：（1）在胸部CT數(shù)據(jù)中分割出支氣管；（2）對提取到的支氣管進(jìn)行細(xì)化處理；（3）對細(xì)化后的結(jié)果轉(zhuǎn)化為二叉樹結(jié)構(gòu)進(jìn)行匹配標(biāo)記。

在本文中使用區(qū)域增長算法對支氣管進(jìn)行分割，區(qū)域增長算法以3D種子區(qū)域增長為基礎(chǔ)，這是一種簡單、方便的圖像分割算法，通過在CT圖像中的支氣管上選取種子點(diǎn)出發(fā)，創(chuàng)建一系列不斷迭代加入進(jìn)來的相似的體素，直到處理過每一個體素，最終形成一個區(qū)域［10］。

圖1　支氣管解剖結(jié)構(gòu)識別過程

細(xì)化算法是用來在一個合理的時間內(nèi)精確地計(jì)算支氣管的中心路徑。早期的細(xì)化算法有許多種，例如：剝皮法、拓?fù)浞?、查表法等，在這些方法中，表層的點(diǎn)不斷地被去掉直到中心線的獲得［11］。本文使用的是一種在三維圖像中獲取中心線的方法，使用查表法檢測支氣管內(nèi)某個體素的26領(lǐng)域來判斷這個體素是否保留，遍歷每一個體素，最終得到支氣管細(xì)化結(jié)果［12］。圖2為支氣管分割及細(xì)化的結(jié)果。

圖2　支氣管分割、細(xì)化結(jié)果圖

支氣管分支標(biāo)記相當(dāng)于把肺部分成與左肺和右肺對應(yīng)的LMB和RMB兩部分，其中LUL，RUL，LB4+5，RB4+5，LLB，RLL相當(dāng)于肺部中的支氣管分支，LB1—LB10和RB1—RB10相當(dāng)于肺部支氣管的分支點(diǎn)。我們需要做的是根據(jù)匹配方法把這些分支名稱和分支點(diǎn)名稱標(biāo)記到需要被匹配的支氣管上。

建立支氣管樹的二叉樹結(jié)構(gòu)，通過對比兩個二叉樹結(jié)構(gòu)實(shí)現(xiàn)匹配標(biāo)記的具體算法如下所述：

（1）對細(xì)化后的支氣管圖像進(jìn)行掃描，檢測到的第一個像素點(diǎn)是支氣管的根節(jié)點(diǎn)。

（2）把根節(jié)點(diǎn)的像素值設(shè)置為0，表示已經(jīng)處理過該節(jié)點(diǎn)，此時該點(diǎn)為背景點(diǎn)。

（3）繼續(xù)搜索，檢查根節(jié)點(diǎn)之后的像素點(diǎn)并搜索該點(diǎn)的鄰域內(nèi)所包含像素點(diǎn)的個數(shù)。當(dāng)該點(diǎn)鄰域內(nèi)點(diǎn)的個數(shù)為1時，表示該點(diǎn)為連接點(diǎn)，需要把其像素值設(shè)為0。鄰域內(nèi)點(diǎn)的個數(shù)為2時，表示該點(diǎn)為分支點(diǎn)，把其像素值置為1，并保存在建立二叉樹的屬性表中。若鄰域內(nèi)點(diǎn)的個數(shù)大于2時，需要根據(jù)本文方法把其轉(zhuǎn)化為分支等于2的情況，并把像素值設(shè)為1，保存在屬性表中。若該點(diǎn)鄰域內(nèi)點(diǎn)的個數(shù)等于0，則該點(diǎn)為葉子節(jié)點(diǎn)，同需要把其像素值設(shè)為1，保存在屬性表中。

（4）返回第三步，繼續(xù)處理像素點(diǎn)直到圖像中所有的點(diǎn)都被處理完。

（5）根據(jù)屬性表內(nèi)根節(jié)點(diǎn)、分支點(diǎn)、葉子節(jié)點(diǎn)信息建立二叉樹。

（6）從二叉樹根節(jié)點(diǎn)開始深度優(yōu)先搜索，比較兩個二叉樹結(jié)構(gòu)，具有相同節(jié)點(diǎn)信息的即為匹配一致，否則該點(diǎn)匹配失敗。

三叉分支轉(zhuǎn)化為二叉分枝的方法：遇到三叉分支時需要在該分支點(diǎn)插入兩個分支點(diǎn)，在這兩個的分支點(diǎn)的子樹中分別保存三叉分支的子樹。具體如圖3（a）所示：d為三叉分支，在d點(diǎn)插入兩個分支點(diǎn)d1和d2，然后在d1和d2的子樹中分別保存d的子樹e3、e4、e5，轉(zhuǎn)化之后的二叉樹結(jié)構(gòu)如圖3（b）所示。

圖3　三叉分支轉(zhuǎn)化為二叉分支

如圖4所示，把醫(yī)學(xué)解剖名稱信息記錄在二叉樹結(jié)構(gòu)中作為匹配的模板，類似地把需要被匹配的病人CT圖像進(jìn)行支氣管的分割提取，建立二叉樹結(jié)構(gòu)。通過對比兩個二叉樹的分支結(jié)構(gòu)就可以把匹配上的二叉樹分支部分的信息給需要被匹配的二叉樹。這樣就可以識別病人支氣管二叉樹中的絕大多數(shù)特征點(diǎn)，實(shí)現(xiàn)支氣管的匹配標(biāo)記，得到最終的支氣管解剖結(jié)構(gòu)識別的結(jié)果。

圖4　帶有標(biāo)記信息的二叉樹圖

2　實(shí)驗(yàn)結(jié)果及分析

本文算法使用C++語言編程實(shí)現(xiàn)，在VS2010平臺下運(yùn)行。在實(shí)驗(yàn)中所用到的電腦配置是Windows 7下的64位操作系統(tǒng)、CPU主頻是3.10GHz、內(nèi)存為8.00GB。實(shí)驗(yàn)的胸部CT數(shù)據(jù)來源于EXACT09網(wǎng)站，該網(wǎng)站提供了40組CT實(shí)驗(yàn)數(shù)據(jù)作為競賽使用，其中CT數(shù)據(jù)均為DICOM格式，并且每層的圖像都是512*512像素，共有267～675層切片。

表1　支氣管匹配標(biāo)記對比結(jié)果

表1為本文方法與Kensaku Mori所用方法的支氣管匹配標(biāo)記對比結(jié)果，其中方法一為KensakuMori方法的標(biāo)記結(jié)果，方法二為本文方法的結(jié)果。實(shí)驗(yàn)結(jié)果表明，在肺部支氣管的主要分支，即0到4級分支上，本文方法的匹配的結(jié)果很好，要優(yōu)于方法一，但是在4級分支之后的匹配結(jié)果較以前方法略差，這主要是由于在支氣管樹轉(zhuǎn)換為二叉樹時，因?yàn)槿娣种У霓D(zhuǎn)換容易出錯所導(dǎo)致。具體表現(xiàn)在RB9、RB10、LB8、LB9的后繼分支上的匹配標(biāo)記有錯誤，不能得到正確的標(biāo)記結(jié)果。

3　結(jié)論

本文提出的支氣管解剖結(jié)構(gòu)識別技術(shù)，實(shí)驗(yàn)結(jié)果表明這個方法分割提取了胸部CT圖像中63%的支氣管分支，在支氣管樹1到4級分支內(nèi)解剖標(biāo)記方法分配正確名稱到支氣管樹分支上的成功率達(dá)到93%。實(shí)現(xiàn)了對支氣管進(jìn)行骨架化處理、支氣管樹模型的建立以及支氣管樹分支點(diǎn)的匹配。結(jié)果表明此方法能夠使解剖學(xué)名稱標(biāo)記在支氣管分支的正確位置。但是本文的方法在支氣管的4級以后支氣管區(qū)域標(biāo)記結(jié)果并不理想，不能很好的處理支氣管的細(xì)小分支，這些是以后需要重點(diǎn)解決的問題。

［1］孟文齊，趙衛(wèi)東.醫(yī)學(xué)圖像快速插值算法的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)仿真，2011，28（2）：325-327.

［2］梁肖，胡貞.基于自適應(yīng)閾值的活體細(xì)胞圖像分割改進(jìn)方法［J］.長春理工大學(xué)學(xué)報：自然科學(xué)版，2013，36 （3-4）：138-141.

［3］Kitasaka T，Mori K，Hasegawa J，et al.A Method for Extraction of Bronchus Regions from 3D Chest X-ray CT Images by Analyzing Structural Features oftheBronchus［J］.FORMA，2002，12（17）：321-338.

［4］Mori K，Suenaga Y.Automated anatomical labeling of the bronchial branch and its application to the virtual bronchoscopy［J］.IEEE Trans Med Imaging，2000，19（2）：103-114.

［5］Yongsup Park.Registration of linear structures in 3-D medical images［C］.Japan，Osaka University，2013.

［6］Pisupati C，Wolff L，Mitzner W，et al.Tracking 3-D pulmonary tree structures［J］.Workshop MathematicalMethodsinBiomedicalImageAnalysis，1996（57）：160-169.

［7］Kitaoka H，Park Y，Tschirren J，et al.Automated NomenclatureLabelingoftheBronchialTreein 3D-CT Lung Images［J］.MICCAI，2002，9（6）：25-28.

［8］TschirrenJ，McLennan，Hoffman，etal.Matching and anatomical labeling of human airway tree［J］. IEEE Trans Med Imaging，2005（12）：1540-1547.

［9］Kenasku Mori，Sinya Ema.Automated Nomenclature of Bronchial Branches Extracted from CT Images and Its Application to Biopsy Path Planning in Virtual Bronchoscopy［J］.MICCAI，2005，12（1）：854-861.

［10］Pechin Lo，Bram van Ginneken，Joseph M，et al. ExtractionofAirwaysfromCT（EXACT’09）［C］.IEEETransMedImaging，2012，7（31）：2093-2107.

Recognition Technology Based on the Anatomy of the Bronchial Binary Tree

WANG Xi，LI Yanfang
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

In view of the low accuracy and efficiency of the bronchial image matching，a method of anatomic identification is proposed.The method includes the extraction of bronchus，the refinement of bronchus and the recognition of bronchus in the CT images of the chest.By thinning the bronchial images that a single pixel and connected bronchial skeleton map was obtained，then establishes a binary tree model according to the branch point of skeleton map and match with the matching template，finally，label the name information of the bronchial.Experiments show that this method can improve the matching efficiency and accuracy，and can be a good marker of 1-4 level.

identification；thinning；binary tree

TP3-05

A

1672-9870（2016）03-0128-04

2015-11-04

王曦（1991-），男，碩士研究生，E-mail：1207877345@qq.com

李巖芳（1965-），女，教授，E-mail：yziwangtian@163.com