（控制科学与工程专业论文）医学图像序列分割方法研究.pdf

国防科学技术大学研究牛院学位论文 摘要 随着医学影像的发展，医学图像处理技术越来越重要。医学图像分割作为医学图像处 理和分析中的关键技术，在医学研究和临床应用中起作重要的作用。图像分割的质量将直 接影响着对图像的后续处理，图像分割被视为图像处理的瓶颈。 本文主要针对医学图像序列的分割进行重点研究，对于图像序列的分割一般采用两种 方式：一种是直接在三维数据空间中分割，提取出感兴趣对象包含的体素；另一种是对每 张二维切片独立进行分割，再将每张切片中提取的对象组合起来。 本文首先研究了医学图像分割中一些有代表性的方法，分析了各类方法的特点及存在 的问题；其次，针对瞳孔图像序列存在的问题，本文选取基于梯度矢量流的主动轮廓模型 作为基本模型，将其应用于图像序列的分割，取得了较好的效果；对于骨骼等c t 图像序 列，将其作为三维数据，使用基于图论的最小割最大流的方法对三维数据进行直接分割， 实验结果表明该方法实时性较高，对于c t 图像序列有较好的分割效果。 最后，在对基于图论的权值聚类方法进行深入分析研究的基础上，结合分水岭算法， 针对图像序列的分割问题，提出了一种快速分割方法。该方法利用分水岭方法的初始分割 速度快，运算复杂度低的优点，将分水岭方法视为权值聚类方法的预处理过程，解决了权 值聚类方法处理较大图像速度变慢的问题。同时，该方法利用权值聚类方法的统计特性， 得出各相邻切片层间的区域相关性，极大地提高了图像序列分割的准确性。 【关键词】医学图像处理 最小割最大流图切分图像序列主动轮廓模型权值聚 类算法 第1 页 国防科学技术大学研究牛院学位论文 a b s t r a c t w i t ht h ed e v e l o p r n e n to ft h em e d i c a l i i m g i n g ，m e d i c a l i m a g ep r o c e s s i n gb e c o m e sm o r ea n d m o r ei m p o r t a m a sm ek e yt e c h n i q u eo fm e d i c a l i m a g ep r o c e s s i n g ，m e d i c a li m a g es e g m e n t a t i o n p l a y sa ni i i l p o i r t a n tr o l ei nc l i n i ca i l dp a t h o l o g yr e s e a r c h q u a l i t ) ，o fi m a g es e g m e n 诅t i o nd i r e c t l y 斫r e c t sm ef o l l o w i n gr e s u l to fi m a g ep r o c e s s i n ga n di i l l a g es e g m e n t a t i o ni s r e g a r d e d 嬲m e b o t t l e n e c ko fm e d i c a li m a g ep r o c e s s i n g t h i sp a p e ri sm a i l l l ya b o u tm em e t h o d o l o g i e so fs e q u e n c ei m a g es e g r n e n t a t i o n t h e r ea r e 咖、v a y sf o rs e q u e n c eh a g es e g m e n t a t i o n ：o n ei sd i r e c t l ys e g m e n t i n gi i l3 dd a t as p a c ea n d e x t r a c t i n gt h ei n t e r e s t e do b j e c tr e g i o n ；m eo t h e ri ss e g m e n t a t i o nf o re a c hs l i c e 锄dc o m p o s i n g m eo b j e c tr e g i o no fa l ls l i c e s f i r s t l y ，t h ep a p e rb e n yi r i t r o d u c e dm er e p r e s e n tm e t h o d so fm e d i c a li m a g es e g m e n t a t i o n a n da n a l y s e dt h e i rc h a r a c t e r i s t i c sa n dp r o b l e m s s e c o n d l y ad e t a i l e dd i s c u s s i o ni sg i v e na _ b o u t t h ea c t i v ec o m o u rm o d e l s t 1 1 e nw es e l e c t e dt h eg v fs n a l ( em o d e lf o rs e g m e n t a t i o no fp u p i l s e q u e n c ei m a g e s t h i r d l y t h ep 印e rf o c u s e do nt h em e t h o d so fg r a p hc u t s ，i n t r o i i u c e dt i l eb a s i c t h e o 巧a i l dt h es t u d y i n gs i t u a t i o no f 舒印hc u t s t h e nt h ep a p e rf i n i s h e dt l l em i n c u t m a x f l o w a l g o r i m ma n du s e di tf o rs e g m e n t a t i o no fc ts e q u e n c ei m a g e s l a s t l y ，t 1 1 ep a p e rs t u d i e dt h ew e i g h t e da g g r e g a t i o na l g o r i t h mb a s e do ng r a p h c o m b i n i n gt h e w a t e r s h e da l g o r i t l l mm l d t h e 、e i g h t e da g g r e g a t i o na l g o r i t ，af a s ta l g o r i t t l mf o rs e g m e n t a t i o n o fs e q u e n c ei m a g e sb a s e do nr e g i o nr e l a t i v i t ) ri sp r o p o s e d a st h ef a s t s e g m e m a t i o na n dl o w c o m p u t a t i o m lc o m p l e x i 够o fw a t e r s h e dm e t l l o d ，、m a d ei t 嬲t h ep r e 仃e a t m e n to ft ：h e 、e i g h t e d a g g r e g a t i o na l g o r i t l l m t h en e wm e t h o ds o l v e dt h el o w e rs p e e dp r o b l e mf o rs e g m e n t a t i o no fb i g i m a g e s u s i n gm es 诅t i s t i c a l i n f o 肌a t i o na i l dr e g i o nr e l a t i v i 吼m ea c c u r a c yo fs e g m e i n a t i o ni s i m p r o v e d 【k e y w o r d s 】m e d i c a l i m a g ep m c e s s i n g ；m i n c u t m a x - n o w ；g r a p hc u t ；s e q u e n c ei m a g e s ； a c t i v ec o t o u rm o d e i s ；w e i g h t e da g g r e g a t i o na l g o r i t h m 第1 i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说- 明并表示谢意 学位论文题目：匡堂鱼篮度列佥割虚造珏塞 一一 学位论文作者签名： 童；l 丑s 日期：为1 年1 1 月巧日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使月j 学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：匡堂圈鱼庄列佥劐左塞珏盔 学位论文作者签名： ：刍：j 叠k 日期：2 口屯7 年1 1 月巧日 一-。 作者指导教师签名：器虹日期：翻7 年，月“日 | 阖防科学技术大学研究牛院学位论文 第l 章绪论 医学图像处理的主要方向有图像分割、图像配准、结构分析等，而其中医学图像分割 的研究鬃有更重要的意义。结构分析、运动分析、三维可视化等后续操作，以及豳像弓| 导 手术、肿瘤放射治疗、治疗评估等应用研究都假设已对图像做了准确分割，或者说是以图 像分割为基础的，这与计算机视觉中出现的情况类似。医学图像分割是正常组织和病变组 织的三维重建、定量分析等藤续操作的基础，也是临床医学应用研究的瓶颈，分割的准确 性对医生判断疾病的真实情况并做出正确的诊断计划至关重要。 由于医学图像具有的极其繁杂的多样性和复杂性，加上目前医学影像设备成像技术上 的特点，使得医学图像存在一定的噪声，图像中目标物体部分边缘也有可能局部不清晰， 这使得医学甏像的分割更加困难。因此，善前在医学图像分割方西仍然没有可以通用的理 论和方法。从指导思想上看，图像分割方法可以分为两种体系：以计算机为单一执行者的 自动分割方法和人机结合的交互式分割方法。自动分割方法的指导思想追求完全由计算机 自主完成的分割任务，而不需要入工参与。但是，目前计算机自主分割的结采不熊令人满 意，准确性不能满足医学图像的应用要求；露对入机交互过于依赖又是实际应雳不能接受 的。因而，自动分割方法的研究继续受到关注的同时，交互式分割方法的研究也成了医学 图像分割的研究重点。 1 1 医学图像分割的意义 图像分割在医学应用领域中具有特殊的意义和十分重要的应用价值。医学图像分割是 医学图像处理和分析的关键技术。医学图像囱于成像原理和设备的不同，存在多种成像模 式，包括c t ( 计算机断层扫描) 、m 附( 磁共振成像) 、u l 椭u n d ( 超声成像) 、p e t ( 正 电子放射断层成像) 、s p e c t ( 单光子辐射断层扫描) 、纵( 功熊磁共振影像) 及其它医 学影像设备所获得的图像。随着成像技术的发展和影像医学在临床上的成功应用，医学图 像分割在临床诊断、病理分析以及治疗等方面正发挥着越来越大的作用。分割的图像正被 广泛应用于许多场合，具体如下： 1 ) 人体组织体积的定量测量和分析，病变组织的定位和测量，医学诊断解剖结构的 学习，治疗计划的制定和计算机指导手术等。 2 ) 医学图像的三维重建和医学图像可视化。使于外科手术方案的制定和仿真，药物 疗效的评估以及放疗计划中的3 d 定位等。 3 ) 图像分割结果可用于在不丢失有用信息前提下进行数据的压缩和传输。这对于提 高在p a c s 、远程放射学和i n t e m e t 中的图像传输速度是至关重要的。 因此，医学图像分割对医学图像的处理和应用有着非常重要的作鬻。 图像分割是一个经典的难题，至今尚无通用的自身理论，医学图像分割也没有通用和 第l 页 国防科学技术大学研究生院学位论文 圆满的解决方法，原因之一就是医学图像的复杂性和多样性：一方面，医学图像的形成会 受到噪声、场偏移效应、局部体效应和组织运动等因素的影响，这就使医学图像与普通图 像相比，本质上具有模糊和不均匀的特点；另一方面，人体的组织解剖结构和形状复杂， 个体差异又较大，这些都给医学图像的分割带来困难，而图像分割的结果和准确度又直接 关系到临床应用的效果。因此，很有必要对医学图像分割方法进行深入研究。 1 2 医学图像分割的特点 由于医学图像实际获取条件变化不定，如场成像设备的场偏移效应、患者体位的移动、 剪床的运动以及采样伪影、局部体效应、空间混叠等因素使图像中存在许多不确定性干扰； 同时，医学图像具有采样数据量大，感兴趣区域解剖结构复杂、易变，微细结构( 血管、 神经) 分布错综复杂等特点：医学图像还具有对比度低、组织特性的可变性大，不同软组 织之间或软组织与病区之间的边界模糊、不明确和不连续等特点；而且人与人之间有相当 大的差别，不同模态图像因成像原理彳 。三个力福 互作用，从而改变s n a k e 曲线的形状，使能量函数达到最小。 主动轮廓模型的轮廓线可以魇一条参数曲线e 0 ) = x ( s ，y ( s ) ) 表示，其中sg 【0 ，l 】。 s n a k e 的能量函数定义为： 露= f 寺( ( ( s ) ) + k ( c f s ) ) ) 丞 ( 2 1 ) 其中，互m 定义为： c ( s ) ) 拦岱矽( s ) 1 2 + 声lc ”( 掌) 1 2 ( 2 2 ) 是s n a k e 模型的内部能量与参数曲线的特性相关，其中联、夕为控制参数，分别控制参数 曲线的弹性和刚性( 或说是连续性和光滑性) 。 在式( 2 2 ) 中，一阶导数项c ( s ) 是曲线c ( s ) 的切向量，而掰ic 。( s ) 1 2 代表参数曲线的 弹性能量，用以反抗曲线的掇伸：弹性麓越大，睡线越不易被拉伸，所以晓是弹性系数。 二阶导数项c ”( s ) 是曲线c ( s ) 的曲率，而ic ”( s ) 1 2 代表曲线的弯曲能量，用以抵抗曲线的 弯曲变形；弯魏能量越大，滴线越不容易变弯，所以厣是刚性系数。可冤s n a l ( e 轮廓的灵 第l o 页 因防科学技术大学研究生院学位论文 活性完全由这两个系数决定。 在式( 2 1 ) 中的巨盯是外部能量，与图像特征密切相关，反映了图像的某些本质特征， 如边缘、线条等，它使得s n a k e 向感兴趣的目标方向移动。由于这些方向只能根据特定的 问题而定义，所以外部能量不易确定。因此，巨。没有统一的数学表达式，必须从问题本 身的特征出发，利用灵活的图像处理技术来得到。对于灰度图像，( 而y ) ，一般采用以下几 种图像能量函数： 砭= 一iv ，( x ，j ，) 1 2 ( 2 3 ) 砭= 一lv ( q ( x ，y ) 木，( 五y ) ) 1 2 ( 2 4 ) 吃= v 【q ( x ，y ) 掌，( z ，y ) 】 ( 2 5 ) 吃= ，( x ，少) ( 2 6 ) 其中，q ( x ，y ) 是方差为仃二维高斯函数，v 是梯度算子。瓯的实质是对原图像，( 石，y ) 的 边缘取反，也称作高斯势能。由上述几种图像能量函数可以看出，图像边缘点的能量取得 最小值。 s n a k e 曲线的运动过程就是寻找能量函数最小点的过程，将式( 2 1 ) 取极小值，满足 欧拉方程的具有最小能量的s n a k e 模型的一价偏微分方程为【7 1 ： 口c 。( j ) 一c 。( s ) 一v e 乙= o ( 2 7 ) 能量平衡方程还可以认为是力的平衡方程： + 瓦= o ( 2 8 ) 其中，= 口c 。( s ) 一c 。( s ) ，它控制曲线的特性；l = 一v ，它将主动轮廓吸引到真 实的轮廓。 也就是说，s n a l 【e 在外力匕的作用下不停的向着真实轮廓移动，而内力在保持s n a l ( e 拓扑性的同时随着s m k e 曲线的移动而变化，最终达到内外力之和等于零。这时，s n a k e 就停留在真实的轮廓上。 由于传统s n a l ( e 中匕= 一v ，其作用范围局限于图像边缘附近，外力场捕获区很小。 这样就出现了初始化和凹陷区两个问题：第一，分割结果与初始位置有关，当初始s i l a k e 远离外力场的捕获区时，s n a k e 就有可能不会停留在图像的真实轮廓上；第二，由于该方 法基于梯度寻找边缘，所以不易逼近曲率高的部分，即进入凹陷区域很难。 图2 1 是一个u 形物的经典外力图，从图中可以看到在u 形开口处，外力基本处于水 平方向，缺乏向下的引力，因此传统s n a k e 很难跟踪到目标凹陷轮廓边缘( 如图2 2 和图 2 3 ) 。 为此，研究人员多次对这一算法进行改进。如：d t e 勉o p o u l o s 和m k a s s 使用不同尺度 的高斯势能场以扩大捕获区域【8 1 ；l d c o h e n 将压力场和高斯势能场相叠加，将其作为新 的外力场1 9 】，这就是有名的气球理论；后来，还有l d c o h e n 和i c o h e n 提出的距离力场； c h e n y 锄gx u 和j e n yl p r i n c e 提出了用梯度矢量流( g v f ) 代替外力场的方法【1 1 1 。 第l l 页 围防科学技术大学研究牛院学位论文 图2 1 经典s n a k e 模型外力场 图2 2s n a k e 曲线初始位置 图2 3s n a k e 曲线最终位置 2 2 梯度矢量流 g v f ( ( h d i e n tv e c t o rf l o w ) 理论是h o p 垃_ l s 大学的c h e n y 锄gx u 和j e n yl p 血c e 两 位科学家在1 9 9 8 年提出来的【1 1 】。它的目的是要解决经典s n a k e 模型中初始化和凹陷区两个 问题。此理论引入新的外力定义方式g v f 以扩大外力作用范围，并加强目标凹陷轮廓边缘 的吸引力。 g v f 理论定义了灰度图像，( z ，j ，) 的一个边缘图厂( x ，y ) = 一( x ，y ) ，和一个g v f 向量场 圪陌( x ，y ) = ( 甜( x ，y ) ，v ( z ，y ) ) 。甜、1 ，是向量场陌的水平向量和垂直方向的分量。 这个向量场陌根据h o m 和s c h u n c k 的经典光流公式【1 2 】，可使能量函数最小化： = j j ( 正+ + 口+ 嵋) + i 夥1 2 i 圪陌一耵1 2 出咖 ( 2 9 ) 其中，段、，屹、y ，是、y 分别对x 、y 的一阶偏导数；是被处理图像，的边缘图， 第1 2 页 国防科学技术大学研究生院学位论文 厂的实质是经典s i 址e 外力场的取反，w 是的梯度场，在完全一致区域，是恒定 的，此时盯为零；是控制参数，根据图像的噪声来设定，噪声变大，值增加。由公 式( 2 9 ) 可知，当i 夥f 较大，较小时，s n a k e 曲线受经典外力的影响较大；而iw i 较小， 较大时，s n a k e 曲线受g v f 向量场圪陌的影响较大。 根据如下欧拉方程求解，可以得到梯度向量即： 胛2 州材一z ) ( 七) ( 2 1 0 ) 2 v 一( v 一工) ( 刀+ ) = o 其中，v 2 是梯度算子，六、 是边缘图对x 、y 的偏导。 对方程式( 2 1 0 ) 进行迭代求解，可以得到g v f 向量场的两个分量“( x ，j ，) 、v ( x ，j ，) ： 2 胛2 坼七，一六! 刀)( 2 h + 。= 胛2 v 一( _ 一) ( + ) 其中，f 表示迭代次数。 由上可知，经典s n a k e 模型的外力向量场直接由六、六这两个分量构成。根据g v f 理论将六、工进行多次迭代，可以求得新的向量场陌的两个分量和y 。在g v f 场的 图2 4u 形图的g v f 向量场 作用下，不但经典s n a k e 中的初始化问题和凹陷区问题可以得到解决，气球理论中外突的 第1 3 页 国防科学技术大学研究生院学位论文 现象也能够被克服。由上方法求得u 形图的g f v 向量场如图2 4 所示。 由图可知，对于u 形轮廓外部，外力向内指向轮廓线，而在u 形图内部，外力向外指 向轮廓线，这就使得s n a l ( e 曲线总是向着轮廓方向运动，最终收敛于轮廓线( 如图2 4 、 图2 5 所示) 。 图2 5 基于g v f 场的s n a k e 模型最终曲线 2 3 瞳孔图像序列分割 利用g v f 的s n a k e 模型解决经典s n a k e 模型进入深度凹陷区困难及弱边界渗透等弱 点。观察瞳孔图像序列的特点，随机选取瞳孔序列的一层( 如图2 6 所示) 。该帧图像中 瞳孔部分与周围背景的灰度值相差较大。根据这一特征，我们采取先对图像进行二值化， 再用g v f 主动轮廓模型得到瞳孔边界。 i 襄 图2 6 瞳孔序列图像中的一层 运用阈值分割方法，将目标从背景中提取出来。在本算法中，采取先对图像进行归一 化处理，再使用单阈值分割法( 选取阈值为0 5 ) ，将得到如图2 7 所示结果，最后利用数 学形态学方法对涧孔进行填充( 图2 8 ) 。 因在瞳孔序列图像中，瞳孔目标与周围背景区别较大，且目标内部存在洞孔，根 据瞳孔图像序列的这一特点，本文采取先对图像序列进行二值化，再进行洞孑l 填充操作， 第1 4 页 国防科学技术大学研究生院学位论文 最后运用g v f 主动轮廓模型求取目标轮廓。 针对瞳孔序列图像，本算法有如下优点：图像二值化后，可以去除背景中较明显的噪 声，从而加快收敛速度；图像二值化可使目标与背景的边界更加明显，使得最终分割结果 更加准确( 图2 9 ) 。 图2 7 瞳孔图像阈值分割图2 8 瞳孔图像进行洞孔填充结果 ( a ) ( b ) 图2 9 基于g v fs n a l ( e 的瞳孔图像分割 图a 为原始图像最终分割结果，图b 为进行二值化、洞孔填充操作图像的最终分割结果 本文采取该算法对瞳孔的收缩变化图像序列进行分割。算法的具体步骤如下： ( 1 ) 对图像序列各层图像进行二值化，并进行洞孔填充操作； ( 2 ) 求取图像序列各层图像的梯度矢量流( g v f ) ； ( 3 ) 手动选取初始层图像的轮廓； ( 4 ) 将当前切片的分割结果投影到下一张切片作为初始轮廓，然后用g v fs n a l 【e 模型 自动分割下一张切片； ( 5 ) 重复第3 步直到完成所有图像层的分割。 在m a t l a b 环境下对瞳孔图像序列进行分割，因图像序列各切片层间变化不大，每隔四 第1 5 页 国防科学技术大学研究牛院学位论文 层进行分割( 1 ，5 ，1 0 ，) ，分割结果如图2 1 0 所示。其它基于主动轮廓模型的序列分 割方法可参看如下文献【1 3 】。 l a jlb ) 【c ) 图2 1 0 基于g v fs n a k e 模型的瞳孔图像序列分割 图a 为第4 0 层图像手动选取轮廓，图b 为第4 0 层图像对应分割结果，图c 为第1 1 0 层图像分割结果 第1 6 页 慝隧戮露黟孵 国防科学技术大学研究生院学位论文 第3 章c t 图像序列分割 c t 成像的主要特点是具有高密度分辨率，比普通x 射线照片高1 毗0 倍，能准确测 出某一平面各种不同组织之间的放射衰减特性的微小差异，以图像或数字将差异显示，极 其精细地分辨出各种软组织的不同密度，从而形成对比。 由于c t 图像成像的高分辨率特点，对于骨骼、肝脏和肺等c t 图像，目标与周围背 景很好的区分出来。对于这一类图像，我们采用基于图论的最小割最大流方法，将图像序 列作为三维数据直接对其进行分割。 3 1 基于图论的分割方法 在图论中，设图g = ( y ，e ) ，其中，矿代表节点的集合，e 代表边的集合。对g 的每 一条边( m ，1 ，) 赋以权值，g 连同它边上的权值称为赋权图。其基本理论如下： ( 1 ) 图的最优划分准则1 4 】 对于图g = ( y ，e ) ，图g 的节点y 被划分为彳、占两部分，且有彳ub = y ，彳厂、曰= o ， 节点之间的边的连接权为w ，则将图g 划分为彳、b 两部分的代价函数( c u ts i z c ) 为： 例( 彳，b ) = 嘞 ( 3 1 ) 使得上述切割值最小的划分( 彳，b ) 即为图g 的最优二元划分，这种划分准则称为最小 割集( m i n i m l 蛐c u t ) 准则。 ( 2 ) 图像的最佳分割 对于无向权值图g = ( y ，e ) ，像素集被看作节点集矿，边缘集被视为边的集合e ，设 像素之间的权值为m ，则将图像二值划分为两个集合( 区域) 彳、召的代价函数为 c 斫( 彳，b ) = 嘞 对于一幅图像，使得上述代价函数最小的划分即为图像的最佳分割。 ( 3 ) 权函数 权函数一般定义为两个节点之间的相似度，在基于图论的图像分割方法中，常见的权 函数有如下形式【1 5 1 = e x p ( 一oc 一巧1 1 2 砰) e x “_ l i 置：一“砖) e 篓e “置一一”2 0 。 “砒 阶段： 这一阶段，主动节点从自由节点中吸收节点成为它的子节点。 帆i l e 彳o p i c k 锺a e l i v e f l o d ep 芒么 f o re v e 哆n e i g h b o r 口s u c h m a t 护卯一“矽( p q ) o 薹f 豫磁( 譬) = 彩也铋蒯q 论娠眦h 波e 豁缀数l i v e 豹d e ： 豫舾( g ) 澎豫髓( p ) ，剐艇胛( g ) p ，么澎彳u 幻 l f 豫驻锄彩硼豫髓事豫磁( p ) 羚咖夕= 黝观喇 e n df o r 黜m o v ep 如m 么 e n d w k l e r e t u n lp = g “a u 擎粼嫩豉i o 珏”阶段 这一阶段是有从s 到f 的一条有效路径p 为输入，在这一阶段的开始时刻，孤立节点集 是空集，但在这一阶段的最后，因有效路径p 使得至少条边是饱和的，这就会产生一些 孤立节点。 f i n dt h eb 0 砌e n e c kc 印a c i 够厶o np u 脚爨持s 主( 1 喊孚滋盐姆p 溅魏g 羹o wa 珏g hp f o re a c he d g e ( p ，9 ) i l lpt i l a tb e c o l n e ss a t l 腿t e d i f 豫髓( 夕) = 豫髓( g ) = s 妞ns c t 以只删r ( 窖) - ga n do ：= d u 铆 i f 豫磁( p ) = 豫髓( g ) = rt l l e ns e t 黝琵册( p ) ：= 彩跹dd 譬d u p e n df o r “鲥印t i o ns 堍g e 阶段 在这一阶段将处理所有的孤立节点直到孤立节点集d 为o ，对每一个孤立节点将试图 在网一搜索树中找到个有效的父节点，若成功找到这鸯的父节点，则将矽从孤立节点集 d 中移除并认为它在同一树中；否则，将p 变为自由节点而p 的所有子节点加入到孤立节 点集中。 、确i l ed 喾圆 第2 3 页 国防科学技术大学研究生院学位论文 p i c ka no r p h a j ln o d ep oa j l dr e i n o v ei t 仔o mo p r o c e s sp e n dw h i l e 在上述流程中，“p r o c e s sp ”包含以下几个步骤，首先在p 的所有邻点找寻找有效的 父节点，有效父节点将满足几个条件：豫脚( g ) = 豫脚( p ) ，驴卯一唧( g p ) o ，且节 点g 的根节点必须为s 或，。最后一个条件将保证g 的根节点不是来源于孤立节点集。 如果p 找到一个有效的父节点，则设定朋r 删丁( p ) = g ，这样p 仍然在同一搜索树中 且p 是主动节点还是被动节点的状态没改变；如果p 没有找到一个