东北大学学报:自然科学版  2018, Vol. 39 Issue (7): 942-948  
0

引用本文 [复制中英文]

赵海, 杨婷婷, 朱宏博, 窦圣昶. 一种基于ARG的肺结节良恶性度判定方法[J]. 东北大学学报:自然科学版, 2018, 39(7): 942-948.
[复制中文]
ZHAO Hai, YANG Ting-ting, ZHU Hong-bo, DOU Sheng-chang. Method of Measuring the Benign and Malignancy of Pulmonary Nodules Based on ARG[J]. Journal of Northeastern University Nature Science, 2018, 39(7): 942-948. DOI: 10.12068/j.issn.1005-3026.2018.07.007.
[复制英文]

基金项目

辽宁省科学技术计划项目(2015401039);辽宁省教育厅重点实验室基金资助项目(LZ2014015)

作者简介

赵海(1959-),男,辽宁沈阳人,东北大学教授,博士生导师。

文章历史

收稿日期:2017-02-27
一种基于ARG的肺结节良恶性度判定方法
赵海, 杨婷婷, 朱宏博, 窦圣昶    
东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
摘要:基于CT影像的肺结节的良恶性识别是肺癌诊断的重要环节, 针对这一问题, 提出一种基于属性关系图(attributed relational graph, ARG)的肺结节良恶性度判定方法.该方法以肺结节CT图像块作为输入, 利用ARG构建其特征结构, 并从大量ARGs中挖掘与或图(and-or graph, AoG)作为肺结节类别识别模板, 即肺结节良恶性度判定的依据.此外, 为提高模板挖掘效率, 该方法利用马尔可夫毯(Markov blanket, MB)发现算法去除图像中的冗余特征, 降低ARG节点数量.实验结果表明, 该方法对恶性肺结节的识别率达到90.12%, 能够帮助正确、快速辨识与分析肺结节良恶性, 具有一定的实用价值.
关键词ARG    与或图    马尔可夫毯    肺结节    良恶性    
Method of Measuring the Benign and Malignancy of Pulmonary Nodules Based on ARG
ZHAO Hai, YANG Ting-ting, ZHU Hong-bo, DOU Sheng-chang    
School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: YANG Ting-ting, E-mail: ytt_mili@163.com
Abstract: Identification of benign and malignant pulmonary nodules is an important task during the diagnosis of lung cancer. Aimed for solving this problem, a method of measuring the malignancy of pulmonary nodules based on the attributed relational graph (ARG) was proposed. Feature structures of input lung nodule CT image patches were constructed with ARGs and the nodule category template was built by mining and-or graph (AoG) from ARGs in the proposed method. Moreover, Markov blanket discovering algorithm was applied for discriminative features selection to reduce the node number of ARGs, so the computational complexity of the graph matching for AoG mining was greatly reduced. Experimental results show that the recognition rate of malignant pulmonary nodules is up to 90.12%, thus the proposed method can help identify the benign and malignant pulmonary nodules accurately and rapidly.
Key Words: ARG (attributed relational graph)    and-or graph    Markov blanket    pulmonary nodule    benign and malignant    

肺癌是引起死亡的重要威胁之一.肺癌起病隐匿, 早期肺癌仅表现为一角硬币(新版兰花硬币)大小的肺结节, 给临床检测带来极大困难[1].肺结节有良恶性之分, 如何在肺癌早期对肺结节进行快速准确地筛查具有十分重要的意义.一种可行的方法是实现肺部计算机辅助诊断(computer-aided diagnosis, CAD)系统, 通过对大量CT图像进行自动分析处理, 输出肺部病变的计算机识别结果.

在CAD系统实现过程中, 对肺结节进行良恶性度判定是目前相关研究人员主要关心的问题.Zinovev等[2]使用LIDC-IDRI(lung image database consortium and image database resource initiative)图像集中的注释特征和纹理特征作为分类指标, 采用信念决策树的方法来预测结节属性, 但在实际医疗工作中可能缺乏充分的注释特征.Chen等[3]在纹理特征上使用神经网络来区分良恶性肺结节, 相较于更为直观的形状特征和便于理解的语义特征, 纹理特征作为一种较低层次上的特征, 与人体感官对图像的描述理解具有一定差距, 并且纹理特征大多使用特征直方图进行量化计算, 更高维度的直方图能够更为详尽地描述图像, 但可能造成计算负担较大.Kumar等[4]利用自动编码器所提取的深度特征作为分类器输入, 使用二叉决策树进行肺结节良恶性分类, 但该方法更倾向于关注模型训练和分类器构造, 缺乏对底层特征空间结构的构造.Han等[5]则使用基于3D图像的纹理特征分析来进行结节诊断, 在一定程度上弥补了纹理特征的单一性.然而, 所有这些方法都依赖于结节提取作为先决条件, 可能存在不准确分割引起的错误分类结果.Shen等[6]直接对原始结节的图像块进行建模, 提取卷积特征用于分类, 避免了这一问题.

通过以上分析, 结合当前大数据医疗的背景下提高海量数据处理效率的需求, 本文提出基于ARG的肺结节良恶性度判定方法.该方法的主要创新包括两方面:1)首次将图模型用于肺结节良恶性鉴别工作.该方法无需依赖于肺结节提取, 以单个肺结节图像块作为输入构建ARG, 保留特征的空间特性, 然后通过对大量ARGs进行与或图(and-or graph, AoG)挖掘作为类别识别模板.2)运用马尔可夫毯(Markov blanket, MB)发现算法对ARG降维, 得到具有高度鉴别性的完备特征集, 在保证肺结节良恶性识别准确度的条件下减少了算法计算复杂度.

1 数据源

肺癌图片数据来源于LIDC-IDRI图像集、上海胸腔医院和沈阳盛京医院.目前LIDC-IDRI数据库包括1 010个病例的244 527张全肺CT扫描图像(扫描层厚1.25~3 mm, 512×512像素).LIDC-IDRI数据库中对肺结节良恶性等级评定为5级, 1为良性, 2为疑似良性, 3为未知, 4为疑似恶性, 5为恶性.本文将3, 4, 5等级判定为恶性, 1, 2等级判定为良性.对于上海胸腔医院和沈阳盛京医院共346个病例的21 803张肺部CT图像, 根据病患的影像学诊断报告从图像中分割出相应的肺结节图像块作为实验输入图像,并进行良恶性评定.表 1列举了5个样例的肺结节诊断信息统计.

表 1 肺部结节诊断信息统计 Table 1 Diagnostic information of pulmonary nodules

依据灰度信息, 肺结节可分为实质结节、部分实质结节和非实质或称为磨玻璃影(ground-glass opacity, GGO)结节, 三者的恶性病变率由低到高[7].实质结节数量多, 密度大, 边界较清晰, 因此检测容易; 非实质性肺结节边缘模糊, 其灰度值与周围区域对比不明显; 部分实质结节介于其余二者之间.依据位置信息, 肺结节可分为:孤立性肺结节(solitary pulmonary nodule single, SPNs)、血管粘连型肺结节(juxta-vascular pulmonary nodule, JVPN)、胸膜粘连型肺结节(juxta-pleural pulmonary nodule, JPPN)和胸膜尾肺结节(pleural tail pulmonary nodule, PTPN)[8].其中, SPNs较易检测和分类, 其余三者较难.表 1中列举了所用数据中部分肺结节的位置信息和灰度信息.

2 技术基础

1) 图模型.基于图模型的图像特征表示是指由图像局部特征形成相互联系的图G0=(V, E), 图节点为V, 边集E表示节点间的联系, 则图像之间的相似度度量或匹配等操作转化为图模型计算.目前, 图模型在场景模拟[9]、目标跟踪[10]、人脸识别[11]、物体检测[12]等图像识别工作中取得较好的成绩.常用的图有结构图、加权图、ARG, 相较于其他两种, ARG在描绘图像特征信息和全局结构时更具优势.

2) ARG模型构建.文献[13]中用ARG对物体进行建模并挖掘AoG进行类模型构建, 其基本的构建过程可参见图 1.ARG是一种添加了节点属性和边属性的有向完全图, 属性由特征向量表示, 体现了图像的特征信息, 不同的视觉数据可以采用不同的属性来表示局部特征和空间关系.AOG是一种特殊的ARG, 有三层结构, 顶层AND节点包含多个OR节点集, 每个OR节点包含一个终端(terminal)节点集, 每个终端节点包含多个节点属性.所有OR节点形成完全图, 每一条边有边属性集.与或图还包含一个匹配元素集, 表示属性间的匹配权重.图 1中将输入图像进行特征提取, 特征图像块作为节点构建有向完全图, 以特征作为节点属性形成ARG, 然后从大量ARGs中挖掘出AoG作为类别模板.

图 1 图模型构建过程 Fig.1 Graph model construction process

挖掘AoG的目的是为了从大量ARGs中挖掘出最优状态的AoG, 使其能够对阳性ARG(此指恶性肺结节属性关系图)和阴性ARG(此指良性肺结节属性关系图)的区别力度最大, 从而获得最好的分类效果.该目标可通过式(1)的损失函数进行描述:

(1)

其中:εs+εs-为每个OR节点的阳性边界匹配能量和阴性边界匹配能量; ∑sV(εs+-εs-)表示生成损失, 描述了与或图G对阳性ARG和阴性ARG的区分能力; ∑sVλ(|Ωs|+β)为复杂度损失, 可避免发生过拟合.对于给定的初始图像模板和图像ARG集合, 与或图挖掘的流程如算法1所示, 具体流程可参见文献[13].

算法1    与或图挖掘算法

输入:初始图模板G; 阳性图Gk+集合; 阴性图Gl-集合; 迭代次数T; 阈值τ.

输出:类别模板G*.

1 while迭代次数≤T

2 图匹配, 分别计算GGk+Gl-集合中ARG的边界匹配能量, 进行图匹配.

3 OR节点属性修正.

4 寻找最坏OR节点作为冗余OR节点删除, 同时删除其所有终端节点.

5 发现新OR节点, 进行匹配估计和属性修正.

6 更新终端节点, 修正终端节点s的数量|Ωs|, 同时修正终端匹配.

7 OR节点属性修正, 同步骤3.

8 使用线性SVM训练匹配元素W.

9 end while

通过以上对AoG类别模型构建过程的描述可以发现, ARG采用完全图的方式构造, 并且图匹配求解涉及到二次分配问题(quadratic assignment problem, QAP)问题, 计算复杂度仍然较高.CT图像包含信息丰富, 其中也包含大量冗余信息, 因此, 可以考虑在利用目标物体的特征构建ARG前先进行特征选择, 挑选出最具区分力的图像块, 减少属性关系图的节点数量, 减少图匹配过程复杂度.

3 基于STMB特征选择的肺结节ARG模型构建

在随机变量的全集U中, 对于给定的变量XU和变量集MB⊂U(X∉MB), 若有X⊥{U-MB-{X}}|MB,则称能满足上述条件的最小变量集MB为X的马尔可夫毯[14].从图论的角度看, 变量的马尔可夫毯为变量的近邻, 如图 2中, 目标节点T的马尔可夫毯MBT={B, D, P, S, C}.

图 2 贝叶斯网络 Fig.2 Bayesian network

马尔可夫毯发现算法是降低数据冗余的有效手段.文献[14]指出, 在真实数据选择实验中, 同步马尔可夫毯(simultaneous Markov blanket, STMB)发现算法优于目前最先进的联合互信息(joint mutual information, JMI)过滤方法, 尤其在肺癌数据的特征提取实验中表现出优良的性能.基于这一点, 本文结合分治的思想, 使用STMB对ARG图进行节点降维(算法2).

算法2    利用STMB进行特征选择

输入:LBP+HOG特征集D; 目标节点类别C; 子特征集合数目d.

输出:目标节点的马尔可夫毯MB.

1 将特征集D等分为d个子特征集Di, i=1, …, d.

2 以图像类别C作为目标节点, 利用STMB发现算法分别在子特征集Di中求得其马尔可夫毯MBi.

3 .

4 for XiD\MB

5     if XiC|MB不成立

6       MB=MB∪Xi

7     end

8 end

依据算法2, 将特征图像块集合D分为d个子特征集, 并在每一子特征集中分别求出马尔可夫毯MBi, 然后合并MBi初步得到MB集合.利用分治思想, 将大规模图像数据在小集合上进行并行运算, 可减少算法运行时间复杂度.算法中第4行D\MB表示集合D与集合MB的差集,由于马尔可夫毯是基于互信息(式(2))判断特征间的依赖程度, 子集合的划分有可能导致一些重要特征丢失, 因此需要从全集中对剩余的特征Xi进行判断, 若符合依赖性条件, 则将其加入MB中, 得到最终的马尔可夫毯MB.图 3为STMB降维实验效果图, 可以发现特征数量大大减少.

(2)
图 3 肺结节特征选择 Fig.3 Feature selection of pulmonary nodules (a)—原始图像特征;(b)—STMB降维后图像特征.

其中:p(x)和p(y)分别为样本x和样本y发生的概率; p(y, x)为yx之间的联合概率.

使用STMB特征选择的ARG肺结节良恶性度判定的方法思路可以参见图 4.首先从肺部CT图像中分割肺结节图像块, 然后进行特征提取.本文选用局部二值模式(local binary pattern, LBP)和方向梯度直方图(histogram of oriented gradient, HOG)[15]对肺结节CT图像进行特征描述, 然后应用算法2对得到的特征进行选择, 将选择后的特征图像块作为ARG节点, 将得到的LBP+HoG特征向量作为ARG节点的单元属性, 此外, 为了保留特征间的空间关系, 将HoG窗口尺度比及其中心线的长度和方向作为ARG的边属性(见图 5)构建ARG.接下来, 运用算法1挖掘AoG.图 6显示了肺结节的与或图挖掘过程, 其中, 图 6a中粗线矩形框为从肺结节图像中标定的初始模板节点, 图 6b中矩形框为从肺结节图像集中挖掘得到的最终AoG节点.

图 4 肺结节良恶性鉴别的思路 Fig.4 Differentiation of benign and malignant pulmonary nodules
图 5 ARG特征属性 Fig.5 ARG attributes
图 6 肺结节AoG挖掘过程 Fig.6 AoG mining process of pulmonary nodules (a)—初始AoG模板节点;(b)—最终形成的肺结节AoG节点.
4 实验结果及讨论

从LIDC-IDRI数据库中选取200份资料, 并从沈阳盛京医院和上海胸腔医院所提供的CT图像资料中选取100份, 将这300份影像学资料作为实验数据, 按7:3的数量比将肺结节分为训练集和测试集, 从中找出恶性肺结节.具体地说, LIDC-IDRI训练集样本中包含肺结节1 017个, 其中恶性肺结节292个, 分别为孤立性肺结节134个, 血管粘连型肺结节47个, 胸膜粘连型肺结节62个, 磨玻璃影结节49个.测试集中包括肺结节431个, 其中恶性肺结节132个, 以上四种类型肺结节的数量分别为66, 24, 22和20.医院数据集的训练集包括肺结节568个, 其中恶性肺结节153个;测试集包括肺结节209个, 其中恶性肺结节72个.从数据集中分割出肺结节图像块并构建ARG, 然后从ARG训练集中挖掘类别图模型AoG(算法1), 依据式(1)将测试集中的ARG分别与得到的AoG进行图匹配, 若匹配能量低于阈值, 则认为是目标类别, 阈值的设定由经验值确定.本文实验指标采用准确度(accuracy, ACC)、敏感度(sensitivity, SEN)和特异度(specificity, SPE)进行衡量, ACC代表整体检测效果, SEN又称真阳性率, 表示正确检测出恶性肺结节的能力, SPE又称真阴性率, 表示正确检测出良性肺结节的能力.三者值越大代表分类实验准确性能越好, 计算公式见式(3)~式(8), 其中索引下标c=1~4, 分别为孤立型肺结节、血管粘连型肺结节、胸膜粘连性肺结节、磨玻璃影结节.总计结果由式(6)~式(8)得到, 表示各类别统计结果的加权平均.式中,TP(true positive)表示将良性肺结节分类为良性的概率,FN(false negative)表示将良性肺结节分类为恶性的概率,FP(false positive)表示将恶性肺结节分类为良性的概率,TN(true negative)表示将恶性肺结节分类为恶性的概率.

(3)
(4)
(5)
(6)
(7)
(8)

表 2表明所提方法在LIDC-IDRI数据集上对恶性肺结节识别的准确率为90.12%.接下来在医院数据集上进行同样实验, 该数据集的训练集包括肺结节568个, 其中恶性肺结节153个;测试集包括肺结节209个, 其中恶性肺结节72个.实验结果见表 3, 本文方法在医院数据集上对恶性肺结节识别的准确率为87.5%, 略低于在LIDC-IDRI数据集上的结果.这主要是由于对磨玻璃影结节的识别准确率比较低, 由于磨玻璃影结节早期较小, 因此对其进行观察识别难度较大, 可能会影响实验结果.而对其余三类肺结节良好的识别率说明该方法具有广泛的适用性, 具有一定的实际应用价值.

表 2 本文算法在LIDC-IDRI数据集上对不同类别恶性肺结节的检测结果 Table 2 Detection results of different types of malignant lung nodules by ARG method with LIDC-IDRI dataset
表 3 本文算法在医院数据集上对不同类别恶性肺结节的检测结果 Table 3 Detection results of different types of malignant lung nodules by ARG method with hospital dataset

将基于ARG的肺结节良恶性度量方法与相关工作中提到的同类方法进行相同条件下的实验性能比较, 比较结果见表 4.进一步地, 对几种方法绘制ROC曲线(图 7)来动态呈现不同方法对结节的识别能力.图中越靠近左上角的曲线说明该方法对于肺结节的分类能力越强, 通过计算ROC曲线下面积(AUC)可以进行准确衡量.

表 4 不同肺结节分类方法性能比较 Table 4 Performance comparison of different methods for pulmonary nodules classification
图 7 ROC曲线 Fig.7 ROC curves

从实验结果来看, 本文方法对恶性肺结节敏感度为90.12%, 次优, 特异度和准确度最优, AUC=0.84次优.所提方法对肺结节的识别力较高, 能避免因未能准确识别恶性结节而使患者错过最佳的诊疗时期.相较于MC-CNN方法, 本文方法的准确度和AUC得分略低, 这是由于卷积神经网络在训练3D结节切片特征时能够通过卷积核保留一定空间信息, 但卷积神经网络中卷积核计算量大, 复杂的卷积网络并不会对肺癌检测率有很大提高, 反而会带来高昂的时间代价, 3D结节切片的使用也引起了模型训练时间的延长.类似地, 基于3D纹理特征的方法具有最高的敏感度, 但该方法需要提前分割结节轮廓构建3D特征, 可能丢失部分轮廓特征.本文方法将感兴趣区域的图像块以图模型的方式进行结构构建, 从实验结果来看, 图模型的应用不仅避免了单独的肺结节提取过程, 还能保留表观特征的空间信息.从一系列图像的属性关系图中挖掘出与或图, 抽象出类内共性的同时也保持了类内个体的多样性, 而挖掘过程中阴性ARG的存在, 使得模型能够排斥非目标图像的差异性,得到较好的识别结果.

5 结论

本文基于属性关系图提出一种肺结节良恶性评估的CAD分类系统, 该系统使用ARG对CT图像进行特征建模, 利用马尔可夫毯发现算法进行特征降维, 最终生成AoG类别模板并用于目标分类.实验结果表明,该方法用于肺结节良恶性识别能够取得良好的效果, 可广泛应用于实际医疗数据处理.尽管本文方法的有效性已得到初步验证, 但在挖掘与或图时如何选择高效的图匹配方法还需进一步研究.

参考文献
[1]
Zhang F, Song Y, Cai W, et al. Lung nodule classification with multilevel patch-based context analysis[J]. IEEE Transactions on Biomedical Engineering, 2014, 61(4): 1155–1166. DOI:10.1109/TBME.2013.2295593
[2]
Zinovev D, Feigenbaum J, Furst J, et al. Probabilistic lung nodule classification with belief decision trees[C]//International Conference of the IEEE Engineering in Medicine & Biology Society. Boston, 2011: 4493-4498.
[3]
Chen H, Wu W, Xia H, et al. Classification of pulmonary nodules using neural network ensemble[C]//International Conference on Advances in Neural Networks. Berlin: Springer, 2011: 460-466.
[4]
Kumar D, Wong A, Clausi D A. Lung nodule classification using deep features in CT images[C]//Conference on Computer and Robot Vision. Santiago: IEEE Computer Society, 2015: 133-138.
[5]
Han F, Wang H, Zhang G, et al. Texture feature analysis for computer-aided diagnosis on pulmonary nodules[J]. Journal of Digital Imaging, 2015, 28(1): 99–115. DOI:10.1007/s10278-014-9718-8
[6]
Shen W, Zhou M, Yang F, et al. Multi-crop convolutional neural networks for lung nodule malignancy suspiciousness classification[J]. Pattern Recognition, 2017, 61(61): 663–673.
[7]
Brandman S, Ko J P. Pulmonary nodule detection, characterization, and management with multidetector computed tomography[J]. Journal of Thoracic Imaging, 2011, 26(2): 90–105. DOI:10.1097/RTI.0b013e31821639a9
[8]
Kostis W J, Reeves A P, Yankelevitz D F, et al. Three-dimensional segmentation and growth-rate estimation of small pulmonary nodules in helical CT images[J]. IEEE Transactions on Medical Imaging, 2003, 22(10): 1259–1274. DOI:10.1109/TMI.2003.817785
[9]
Aksoy S. Modeling of remote sensing image content using attributed relational graphs[C]//Joint Iapr International Conference on Structural, Syntactic, and Statistical Pattern Recognition. Berlin: Springer-Verlag, 2006: 475-483.
[10]
Lu Y, Wu T, Zhu S C. Online object tracking, learning, and parsing with and-or graphs[C]//Computer Vision and Pattern Recognition. Columbus: IEEE, 2014: 3462-3469.
[11]
Bengoetxea E, Bloch I. Inexact graph matching for model-based recognition:evaluation and comparison of optimization algorithms[J]. Pattern Recognition, 2005, 38(11): 2099–2113. DOI:10.1016/j.patcog.2005.05.007
[12]
Zhang Q, Wu Y N, Zhu S C. Mining and-or graphs for graph matching and object discovery[C]//IEEE International Conference on Computer Vision. Santiago: IEEE Computer Society, 2015: 55-63.
[13]
Zhang Y, Zhang Z, Liu K, et al. An improved IAMB algorithm for Markov blanket discovery[J]. Journal of Computers, 2010, 5(11): 1755–1761.
[14]
Tian G, Qiang J. Efficient Markov blanket discovery and its application[J]. IEEE Transactions on Cybernetics, 2016, 47(5): 1169–1179.
[15]
Singh S, Gupta A, Efros A A. Unsupervised discovery of mid-level discriminative patches[C]//Computer Vision. Berlin: Springer-Verlag, 2012: 73-86.