基于二叉树结构的支气管解剖结构识别技术

王曦，李岩芳

（长春理工大学　计算机科学技术学院，长春　130022）

基于二叉树结构的支气管解剖结构识别技术

王曦，李岩芳

（长春理工大学计算机科学技术学院，长春130022）

针对支气管图像匹配精度较差、效率过低问题，提出了一种解剖识别支气管的方法。该方法包含对胸部CT图像中支气管的提取、支气管的细化和支气管的识别。通过对支气管图像细化得到单像素、连通的支气管骨架图，根据支气管骨架图的分支点建立二叉树模型，并将其与匹配模板进行匹配，最后标记支气管分支名称信息。实验表明提出的方法在匹配效率和精度上有明显的改进，可以在1-4级分支很好地标记出结果。

识别；细化；二叉树

在最近几年里，医学图像处理技术已经有了非常显著的提升。现在医生可以使用多层螺旋CT来获得高精度的CT断层扫描，很大程度上提高了医生对疾病的正确诊断率［1］。这使得医学图像处理技术成为了人们目前研究和关注的热点。人们可以通过高精度的CT断层扫描来帮助分割肺部支气管，减少支气管的断裂等误差。这些先进的计算机辅助诊断技术对于肺部疾病的辅助诊断来说是十分关键的，在高精度的CT断层扫描图像上分割出支气管树，然后对提取的支气管树进行细化处理，得到单像素宽的、连通的支气管树骨架，这对于肺部支气管的解剖标记有十分重要的指导意义［2］。

通常医生使用已知的解剖学知识来诊断医学图像，诊断的规则是由目标区域的解剖学名称所构成的，如果想要通过计算机来进行辅助诊断，那么应该识别从CT图像中提取部位的解剖名称。若能够分配正确的解剖名称到目标区域，那么就能够通过使用解剖名称所描述的诊断规则来帮助医生诊断［3］。

在支气管匹配标记方面，Mori K提出一种基于知识库标记的算法［4］，这个算法的优点是能够自动进行支气管的匹配标记，但是并没有包含解剖变化，仅能处理每个支气管树中的部分分支，此外这个方法对于丢失分支和假阳性分支很敏感。Park提出一种基于联合图的树的匹配方法［5］，但是这种方法仅适用于部分数据，并且不能容忍支气管中出现假阳性分支。Pisupati提出一种基于动态规划的分支点匹配算法［6］，然而这种方法也有不可避免的缺陷，仅适用于非常相似的两者之间的匹配。Kitaoka提出一种使用数学虚位作为参照的标记算法［7］，通过匹配目标树与虚位来标记支气管树，这个算法的缺陷在于不能自动处理错误分支，需要通过手动进行剪枝处理错误的支气管分支。Juerg Tschirren在基于知识库匹配算法的基础上做出了改进［8］，引进了平行边来进行支气管分支的剪枝处理，消除了错误的分支，并且通过刚性配准减少了问题的规模，提高了计算速度，但是这中方法在支气管的细小分支上的处理效果并不理想。Sinya Ema提出一种使用模板的标记方法［9］，把支气管分成右上肺叶、右中下肺叶、左上肺叶和左下肺叶（RU、RL、LU、LL）四个部分，并且为每个部分都准备了大量的分支模型，这个方法在每个分支点选择最适合的候选模型，并且对于肺的右上部分提出了一个特别的标记步骤。右上肺叶RU部分的标记分三个步骤：（1）进行临时的标记；（2）选择匹配合适的分支模型；（3）进行RU部分的最终标记；其它三个部分，通过计算适宜的评估值来选择合适分支模型然后执行标记，这种方法很依赖于模板的准确性。

传统的树型匹配方法，由于不知道一个节点有多少子树，在构造过程中，每当增加节点时都要重新分配内存空间，导致效率低，使用指针时，每个节点又会分配指针空间同样造成内存浪费。针对上述方法中存在的缺陷，本文提出了一种通过把分割后的支气管转换为二叉树结构进行匹配的方法，重点解决了匹配精度不高、算法效率过低的问题。本文统一使用了公开的胸部CT数据进行实验，并对支气管的匹配结果进行了量化评估。

1　实验方法

如图1所示，支气管的解剖结构识别过程主要分为三个步骤：（1）在胸部CT数据中分割出支气管；（2）对提取到的支气管进行细化处理；（3）对细化后的结果转化为二叉树结构进行匹配标记。

在本文中使用区域增长算法对支气管进行分割，区域增长算法以3D种子区域增长为基础，这是一种简单、方便的图像分割算法，通过在CT图像中的支气管上选取种子点出发，创建一系列不断迭代加入进来的相似的体素，直到处理过每一个体素，最终形成一个区域［10］。

图1　支气管解剖结构识别过程

细化算法是用来在一个合理的时间内精确地计算支气管的中心路径。早期的细化算法有许多种，例如：剥皮法、拓扑法、查表法等，在这些方法中，表层的点不断地被去掉直到中心线的获得［11］。本文使用的是一种在三维图像中获取中心线的方法，使用查表法检测支气管内某个体素的26领域来判断这个体素是否保留，遍历每一个体素，最终得到支气管细化结果［12］。图2为支气管分割及细化的结果。

图2　支气管分割、细化结果图

支气管分支标记相当于把肺部分成与左肺和右肺对应的LMB和RMB两部分，其中LUL，RUL，LB4+5，RB4+5，LLB，RLL相当于肺部中的支气管分支，LB1—LB10和RB1—RB10相当于肺部支气管的分支点。我们需要做的是根据匹配方法把这些分支名称和分支点名称标记到需要被匹配的支气管上。

建立支气管树的二叉树结构，通过对比两个二叉树结构实现匹配标记的具体算法如下所述：

（1）对细化后的支气管图像进行扫描，检测到的第一个像素点是支气管的根节点。

（2）把根节点的像素值设置为0，表示已经处理过该节点，此时该点为背景点。

（3）继续搜索，检查根节点之后的像素点并搜索该点的邻域内所包含像素点的个数。当该点邻域内点的个数为1时，表示该点为连接点，需要把其像素值设为0。邻域内点的个数为2时，表示该点为分支点，把其像素值置为1，并保存在建立二叉树的属性表中。若邻域内点的个数大于2时，需要根据本文方法把其转化为分支等于2的情况，并把像素值设为1，保存在属性表中。若该点邻域内点的个数等于0，则该点为叶子节点，同需要把其像素值设为1，保存在属性表中。

（4）返回第三步，继续处理像素点直到图像中所有的点都被处理完。

（5）根据属性表内根节点、分支点、叶子节点信息建立二叉树。

（6）从二叉树根节点开始深度优先搜索，比较两个二叉树结构，具有相同节点信息的即为匹配一致，否则该点匹配失败。

三叉分支转化为二叉分枝的方法：遇到三叉分支时需要在该分支点插入两个分支点，在这两个的分支点的子树中分别保存三叉分支的子树。具体如图3（a）所示：d为三叉分支，在d点插入两个分支点d1和d2，然后在d1和d2的子树中分别保存d的子树e3、e4、e5，转化之后的二叉树结构如图3（b）所示。

图3　三叉分支转化为二叉分支

如图4所示，把医学解剖名称信息记录在二叉树结构中作为匹配的模板，类似地把需要被匹配的病人CT图像进行支气管的分割提取，建立二叉树结构。通过对比两个二叉树的分支结构就可以把匹配上的二叉树分支部分的信息给需要被匹配的二叉树。这样就可以识别病人支气管二叉树中的绝大多数特征点，实现支气管的匹配标记，得到最终的支气管解剖结构识别的结果。

图4　带有标记信息的二叉树图

2　实验结果及分析

本文算法使用C++语言编程实现，在VS2010平台下运行。在实验中所用到的电脑配置是Windows 7下的64位操作系统、CPU主频是3.10GHz、内存为8.00GB。实验的胸部CT数据来源于EXACT09网站，该网站提供了40组CT实验数据作为竞赛使用，其中CT数据均为DICOM格式，并且每层的图像都是512*512像素，共有267～675层切片。

表1　支气管匹配标记对比结果

表1为本文方法与Kensaku Mori所用方法的支气管匹配标记对比结果，其中方法一为KensakuMori方法的标记结果，方法二为本文方法的结果。实验结果表明，在肺部支气管的主要分支，即0到4级分支上，本文方法的匹配的结果很好，要优于方法一，但是在4级分支之后的匹配结果较以前方法略差，这主要是由于在支气管树转换为二叉树时，因为三叉分支的转换容易出错所导致。具体表现在RB9、RB10、LB8、LB9的后继分支上的匹配标记有错误，不能得到正确的标记结果。

3　结论

本文提出的支气管解剖结构识别技术，实验结果表明这个方法分割提取了胸部CT图像中63%的支气管分支，在支气管树1到4级分支内解剖标记方法分配正确名称到支气管树分支上的成功率达到93%。实现了对支气管进行骨架化处理、支气管树模型的建立以及支气管树分支点的匹配。结果表明此方法能够使解剖学名称标记在支气管分支的正确位置。但是本文的方法在支气管的4级以后支气管区域标记结果并不理想，不能很好的处理支气管的细小分支，这些是以后需要重点解决的问题。

［1］孟文齐，赵卫东.医学图像快速插值算法的设计与实现［J］.计算机仿真，2011，28（2）：325-327.

［2］梁肖，胡贞.基于自适应阈值的活体细胞图像分割改进方法［J］.长春理工大学学报：自然科学版，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