（生物医学工程专业论文）三维脑血管中轴提取算法研究.pdf

三维脑血管中轴提取算法研究 a b s t r a c t i nt h ec l i n i c a ld i a g n o s i sa n dt h e r a p yo fc e r e b r o v a s c u l a rd i s e a s e ，c o m p u t e rp r o c e s s i n go n3 d c e r e b r o v a s c u l a ri m a g e ss u p p l y sd o c t o r sat o o lt oo b s e r v e3 dc e r e b r o v a s c u l a rs t r u c t u r e sa ta n y a n g l e ，a n dc a nb eu s e f u li nt h ed i a g o s i sa n dt h e r a p y b e c a u s eb l o o dv e s s s e l sb r a n c e si sc o m p l e xa n d i t ss h a p ei st h i n ，h o wt og e tt h e t h ee x a c td e s c r i p t i o no fe e r e b r o v a s c u l a rs t r u c t u r e sh a sb e e n i n t r a c t a b i l i t y ：t h ef r a m eo f3 de e r e b r o v a s c u l a rs t r u c t u r e sd e p a n do nt h ei t sc e n t e r l i n e ，w h i c hh a s t h es a m et o p o l o g ya n dg e o m e t r ys h a p ew i t ht h ec e r e b m v a s c u l a ri m a g e s b a s eo nm e t h o d sf o r3 d c e n t e d i n ee x t r a c t i o no f o b j e c t sw h i c hh a v eb e e ni n t r o d u c e di nr e c e n ty e a r s ，i nt h i sp a p e r , a l g o r i t h m r e s e a c ho n3 dc e r e b r o v a s e u l a ri m a g e s c e n t e r l i n ee x t r a c t i o ni sp r e s e n t e d t h em a i np a r t so ft h e s t u d yo f t h i st h e s i sa l ea sf o l l o w i n g ： 1 ) f i r s lw em a k eas u m m a r yo ft h em e t h o d sf o r3 de e n t e r l i n ee x t r a c t i o no fo b j e c t sw h i c hh a v e b e e ni n t r o d u c e di nr e c e n ty e a r s 2 ) i nt h i sp a r t , ae e n t e r l i n e e x t r a c t i o nb a s e do n3 de u c l i d e a nd i s t a n c et r a n s f o r mi sp r e s e n t e d t h i s m e t h o di n c l u d et h e3 dl o c a lm a x i m as e l e c t i o n , n e i g h b o u rm a x i m as e l e c t i o na n ds a d d l ep o i n t s s e l e c t i o n 1 1 1 i sm e t h o di sa u t o m a t i c 3 ) i nt h i sp a r t ，ac e n t e r l i n ee x t r a c t i o nb a s e do nh e s s i a nm a t r i xi sp r e s e n t e d t h i sm e t h o di n c l u d e 3 de u c l i d e a nd i s t a n c et r a n s f o r m , c o m p u m rt h eh e s s i a nm a t r i xi ne v e r yv o x e l ，a n dv i s i b i l i t y t e s t t h i sm e t h o di sa l s oa u t o m a t i c 4 1m o s tm e t h o d sf o r3 dc e n t e r l i n ee x t r a c t i o no fo b j e c t sw h i c hh a v eb e e ni n t r o d u c e di nr e c e n t y e a r sg e to n l yt h ec e n t e d i n ep o i n t s o u ro b j e c t i v ei s t h a tw ec a ng e t3 dc e r e b r o v a s c u l a r s t r u c t u r e sc l e a r l y , s oh o wt og e tt h ep a t ho f c e n t e r l i n ei sv e r yi m p o r t a n t w eg e tt h ep a t hw i t ha l l t h ep o i n t sb yd i j k s t r a ss h o r t e s tp a t ha l g o r i t h m k e yw o r d s ：c e r e b r o v a s c u l a ri m a g e s ，c e n t e r l i n ee x t r a c t i o n ，e u c l i d e a nd i s t a n c et r a n s f o r m ， h e s s i a nm a t r i x , d i j k s t r a 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 颦趔 e t期：塑墨：壹 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：幽导师签名：毪蛰 期：二坐 东南人学硕士学位论文 第一章绪论 1 i 课题的背景和研究意义 脑血管疾病是神经科最常见的疾病，特别是脑中风( 脑梗塞，脑出血) 是当前严重威胁人 类生命和健康的疾病之一【1 】。在发达国家，脑中风是导致死亡的第三常见疾病。我国脑中 风发病率较高，现患病例约有5 0 8 7 0 0 万。年发病率1 5 0 i o 万，病死率为1 2 0 1 0 万， 每年有1 9 5 万新发病例，约有1 5 6 万人死于脑中风。我国的脑血管病有两大特点： i ) 欧美等发达国家的发病率逐渐降低，但我国还在持续上升； 2 ) 复发率高、病死率高。每年直接治疗支出就达到9 7 亿元人民币，如果加上出院之 后预防和康复的费用，估计将达到3 0 0 亿元。 由此可见，我们对脑血管疾病的治疗已经刻不容缓。同时，脑血管疚病的治疗水平的高低也 是衡量一个国家和城市医疗水平的重要标准。 目前已有的诊疗方法大致可分为介入式和基于图像两种方法 2 。随着科学技术的发展， 对医学也提出了更高的要求。现代医学更注重无损诊断、无损治疗，更加注重治疗的准确性。 相对于介入式方法，基于图像的方法是将计算机技术与医学相结合，它不会给病人带来生理 和心理上的痛苦，同时能够为医生提供更加客观、准确的信息。目前，无论是外科手术还是 放射性治疗，通常需要血管的量化和可视化。然而在医学可视化的研究中，对血管、神经等 细微组织的绘制一直是个十分棘手的问题。由于血管分枝众多，形态细小，并且随着人们对 血管形态绘制的要求越来越精细，例如，外科手术模拟中对主要的血管、神经的形态，位置 必须有准确的描述。因此，当描述精细结构时，管状组织成为必不可少的一个组成部分。 三维血管结构的整体框架很大程度上依赖于图像中血管的有效检测和结构关系描述。由 于血管中轴和原图像具有相同拓扑性和相似的几何形状，因此能够较好的反映血管的结构信 息，使医生能够选择自己感兴趣的观察方向和角度，从而得出正确的诊断结果。这对于血管 疾病的诊断( 如血管狭窄、血管瘤) 具有很重要的意义。 迄今为止，大多数的血管中轴提取算法是在二维情况下提出来的，三维的方法并不是二 维情况下的简单推广。 本课题就是研究三维脑血管中轴提取的算法，由于血管中轴提取的好坏将直接影响到图 像信息的表达，并最终影响到诊疗的结果，因此如何能够比较精确的提取三维脑血管的中轴 致关重要，这也是本课题研究的意义所在。 3 三维肭1 6 l 管中轴提取算法研究 1 2 研究现状 中轴提取在很多领域都有很重要的应用，如物体表达，数据压缩，计算机视觉和计算机 动画。利用中轴表示原始的图像，可以在保留原始图像的拓扑结构和形状特征的前提下，减 少图像的冗余信息。 中轴是表示物体的一种很自然的形式，三维模型的中轴可以看成是由物体中所有最大内 接球中心所在位置点构成【3 】。三维模型的中轴在如计算机视觉、医学图像可视化、特征 提取与表示、模型匹配跟踪等诸多领域有着广泛应用。通常的中轴提取算法有人工指定的 方法，拓扑细化和距离变换。人工指定算法要求用户一张张地在切片上直接指定中心点，然 后再将点连成线。这种方法耗时费力，已很少采用；拓扑细化方法【4 5 】的主要思想是重复地 一层层剥开物体，每一步只删除不会影响模型拓扑结构的点。这种方法多采用模板方式来实 现。抽取的中轴可以保留物体的拓扑结构，但是计算量往往很大，而且短的分枝易被抹掉； 距离变换的方法 6 - 8 主要基于这样的事实：物体的中轴应该是物体内到边界具有最大距离 的点集。将二值数字图像转化成距离图，其上的每一点到最近的边界点距离最小。距离变换 的方法速度较快，易于实现。但由此方法得到的中轴点离散分布可能不连通，会出现中轴线 断裂的情况。此外还有基于形态学的方法 9 b 基于区域增眭的方法 1 0 b 以及基于三维几何 矩【1 l 一1 2 】等中抽提取算法。 下面我们对上述方法当中的细化的方法，基于形态学的方法，基于区域增长的方法和基 于三维几何矩的中轴提取方法进行介绍。它们都是中轴提取这一研究课题中非常具有代表性 的方法。 1 2 1 细化算法 我们重点介绍p a l a g y ia n dk u b a ( 以下简称p k ) 细化算法 1 3 】，首先我们应当了解三维 空间上的一点和它邻域点的位置关系，如图1 1 所示： h w hn e w p 巨 s w瘩 s 彗洲聃b n 蘸 删 b 嚣芒 b 鞠髓噶e 图1 i p 和它的邻域点 4 东南人学硕l 二学位论文 我们用，0 ) 米表示p 邻域点，j = 6 ，1 8 ，2 6 。p 点的，邻域点的集合x = x o ，x 1 ，x 2 x 。 如果x 为空，或者说 = 0 ，则p 点为孤立点。6 0 ) 定义为p 点的面点，包括点t ，n e ，s ，w和b 。8 0 ) 定义为p 点的角点， 包括点 t n w ，t s w ，t n e ，t s e ，b n w ，b s w ，b n e ，b s e 。n l s 0 ) 定义为p 点的边点，包括6 0 ) 和 t n ，t s ，t w ，t e ，n w ，n e ，s w ，s e ，b n ，b s ，b w ，b e 。n 2 6 0 ) 包括1 8 0 ) 和8 0 ) 。 我们可以把一幅三维图像表示成( z 3 ，m ，月，口) ，将背景像素称为“黑点”，特征像素称为“白 点”；黑点的集合用b 来表示，m 表示黑点的最大邻域点属于b 的个数，n 表示白点的最 大邻域点属于b 的个数。我们以下的操作皆对( z 3 , 2 6 ，6 ，b ) 有效。 在图像( z , 2 6 , 6 ，口) 中，当黑点p 同时满足下面两个条件时为单点 1 5 1 6 ： 1 ) 集合b n n 2 6 ( p ) 仅包含一个2 6 _ 成员点； 2 ) 集合z 3 n 6 ( p ) 非空，且它的6 邻域点包含在集合z 3 n 1 8 ( p ) 中。 下面我们说明当黑点删除时，拓扑结构是如何保持的。 三维平行删除操作对( 2 6 ，6 ) 图像保持拓扑不变当且仅当同时满足下面条件【1 7 】 1 8 】： 1 ) 只有单点被删除 2 ) 如果一个被删除的单位格中包含两个黑点p ，q ，那么p ，q 都是单点。 3 ) 如果一个被删除的单位格中包含三个黑点p ，q ，那么p ，q ，r 都是单点。 4 ) 如果一个被删除的单位格中包含四个黑点p ，q ，r ，s ，那么p ，q ，j 都是单点。 5 ) 一个单元格不包含黑点，那么这个单元格将被删除。 三维细化算法一般包含6 个子迭代分别从6 个方向删除t 角点，b 角点，n 角点，e 角 点，s 角点，w 角点。而p k 细化算法分别从t n w ，t s w , t n e ，t s e ，b n w , b s w ，b n e ，b s e 8 个方向来删除图1 1 的点。 1 2 2 基于形态学的方法 形态学以图像形态分析为基础，用具有一定形态结构的“结构元素”去度量图像的形 态，以解决图像理解问题。形态学的基础是腐蚀和膨胀运算，设原始图像为4 ，结构元素 为b ，下面给山两种运算的定义及几何意义 1 4 1 5 。 1 ) 腐蚀的运算符为0 ，a 用b 米腐蚀写作a o b ， 5 三维脑m 管中轴提取箅j 土研究 2 ) 膨胀的运算符为0 ，a 用口来膨胀写作4 0 b 基于形态学的中轴提取方法的实质是击中与击不中变换( 也称塞拉变换) ，它是数学形 态学的一种基本变换，该变换在一次运算中同时可以捕获到内外标记。击中击不中变换需要 两个结构基元e 和f ，( e n f = ) ，这两个基元被称为一个结构元素对b = ，f ) ，一个 探测图像内部，另一个探测图像外部。当且仅当e 平移到某一点时可填入a 的内部，f 平移 到该点时可填入4 的外部时，该点才在击中击不中变换的输出中。利用该变换可以进行物 体的识别，击中击不中的定义为 1 6 ： a f f b = ( 爿 e ) n 0 。f ) ，一f f 曰= p i e + x c a ；f + x c a 。) 中轴提取的实质就是将一个物体化为一条单象素宽的线，从而图像化显示出拓扑性质， 这个过程可分为两步： 1 ) 一个正常的腐蚀，但它是有条件的，也就是说，那些被标为可除去的像素点并不立 即消去： 2 ) 在第二步中。只将那些消除后并不破坏连通性的点消除，否则保留。 l - 2 3 基于区域增长的方法 w o o d 等人提出了一种借助区域生长算法实现自动提取树状空腔中轴的方法 1 7 。此 后，b l e z e k 和r o b b 也提出了一种借助区域生长算法提取体数据中轴的算法 1 8 ，且给不 同方向的体素分配了更为准确的切削距离，并且利用这个算法生成两个已知点之间的最短路 径。 该算法的基本原理是：假定根节点已确定，则中轴可以定义为具有如下特征的体数据子 集： 1 ) 保持体数据的拓扑结构； 2 ) 2 6 邻域连通； 3 ) 单体素宽； 4 ) 近似位于分支的中心轴上； 5 ) 尽可能的平滑。 该方法的基本思想基于“树”的每个分支都存在惟一的一个结束节点。且这个育点剑“树” 的根节点有局部的最大距离。 6 东南大学硕士学位论文 1 2 4 基于三维几何矩的算法 我们通常可以将血管的局部结构用一段小圆柱来近似，_ 【 l 米描述血管的各个参数可以用 某个球形邻域中的几何矩来表示，因而对血管的中轴提取可归结为对幽象局部几何矩的计 算。将某一段血管用一段直径为d 的圆柱来近似，其方向有其轴线方向( 图1 2 中的口，) 定义，在某个球形窗e l 中，为简化问题的处理，将圆杆绕z 轴和x 轴旋转t 2 和角度，以 至其与z 轴重合。旋转前后各阶矩的变换关系见 1 1 】。 zz 图i 2 血管的局部结构 在血管内部图象灰度和背景灰度分布相对比较均匀的情况下，血管的中轴点的位置可通 过是血管的重心来估测，有关血管重心。旋转角度和二 径的计算方法见 1l 】。该方法的大体 步骤如下： 1 ) 首先，人工估计一些血管中的“关键”点，例如血管中的分叉点、拐点； 2 )以上述关键点为起点进行血管跟踪检测。在当前点计算出血管参数，由血管直径自 适应的确定下一点的最佳窗口尺寸，并沿血管方向确定下一个窗口的位置； 3 ) 计算窗口的重心，如果它不落在窗口的中心附近，则对窗口进行调整； 4 ) 重复( 2 ) ，( 3 ) 的计算过程，存储所跟踪的血管参数，如果计算出来的血管直径小 于体元的边长或者通过决策窗口内无血管就停止跟踪，再重新从下一个“关键”点 开始跟踪另一条血管。 7 三维脑m 管中轴提取算法研究 最后需要指出的是：对血管的中轴提取与 一般意义上的表面骨架抽取有些相似，但并不相 同。图1 3 以多边形为例，简单给出了它们的区 别 6 。图1 3 ( a ) 的虚线部分为表面骨架，图 1 3 ( b ) 的虚线部分为中轴。表面骨架抽取要求保 持模型的拓扑结构，并尽量保持模型的细节信 息，如一些小的分支等；而中轴提取的目的在于 观察模型的内部及表面结构，它要求的是表面细 节能够被中轴上的点所看到，同时要尽量避免尖锐 图1 3 提取表面骨架与提取中轴的区别 的突起。本文的主要目的就在于针对脑血管提出了几种较为新颖的中轴提取算法，这些方法 计算简单，没有或者只有较少的人工干预，而且从实验结果上看，效果也非常的理想。 1 3 本文组织结构 本文的结构安排如下： 第一章绪论：介绍了本课题一三维脑血管中轴提取算法的研究背景和研究意义并给 出了目前这一研究方向的现状。在这里，重点介绍了细化的方法和基于三维几 何矩的方法。 第二章基于三维距离变换的中轴提取算法：首先采用快速三维距离变换的算法将原图 像转换成距离图，然后在此基础上采用一种完全面向三维图像的中轴提取算 法，主要步骤包括：选取模板，确定局部值最大点，确定邻域值最大点和确定 “鞍点”。该算法是完全自动化的算法，不需要人工干预。 第三章基于h e s s i a n 矩阵的中轴提取算法：在对单纯的基于h e s s i a n 矩阵的算法改 进后，提出了改进后的基于h e s s i a n 矩阵 | 句中辅提取算法，主要步骤包括： 三维欧几里德距离变换，求h e s s i a n 矩阵，可视化检测几个步骤。该算法同 基于三维距离变换的中轴提取算法一样，也是完全自动化的。 第四章实验结果及分析：分别通过对人工模拟图像和对实际医学图像的实验结果来验 证前面两章提出的中轴提取算法。其中对人工模拟图像的实验是为了验证准确 度；而对实际医学图像的实验则是为了验证算法的有效性，这主要包招晟终提 取山的中轴的效果和计算时间。在这里，我们将对磁共振脑血管造影图像( m r a ) 8 东南大学碗e 学位论文 和数字减影造影脑血管图像( d s a ) 进行处理。在对图像进行二值化，血管分 割和图像插值等预处理之后。采用前面的算法进行中轴提取，在此之后应用 d i j k s t r a 最短路径生成算法将各个中轴点连接成线段。同时还介绍了一种三维 图像的可视化方法一最大密度投影法( m i p ) 。 第五章总结与展望：总结了本文完成的主要工作，并对未来的工作进行了展望。 参考文献 1 王拥军脑血管疾病与认知功能障碍 j 中华内科杂志，2 0 0 5 ，4 4 ( i i ) ：8 7 2 8 7 3 【2 舒中力基于l e v e ls e t 的心血管图像中轴提取【硕士学位论文】南京：东南大学生物医学工 程系2 0 0 5 3 b l u mh b i o l o g i c a ls h a p ea n dv i s u a ls c i e n c e ：p a r tl 【j 】j t h e o r e t i c a lb i o l o g y , 1 9 7 3 ，3 8 ( 2 ) ：2 0 5 2 8 7 4 h o n g l c ，m u r a k i s ，k a u f m a n a ，b a r t z d ，h e t s v i r t u a lv o y a g e ：i n t e r a c t i v e n a v i g a t i o n i n t h e h u m a nc o l o n i n ：t u r n e rw ：e d p r o c e e d i n g so f t h es i g g r a p h 9 7 l o sa n g e l e s ：a c mp r e s s ， 1 9 9 7 ：2 7 - 3 4 5 p a v l i d i s t a t h i n n i n g a l g o r i t h m f o r d i s c r e t eb i n a r y i m a g e s c o m p u t e r g r a p h i c sa n d i m a g e p r o c e s s i n g , 1 9 8 0 ，1 3 ( 2 ) ：1 4 2 1 5 7 6 h e t s ，h o n g l c ，c h e n d q ，l i a n g z i l r e l i a b l e p a t h f o r v i r t u a le n d o s c o p y ：e n s u r i n gc o m p l e t e e x a m i n a t i o no f h u m a no r g a n s i e e et r a n s a c t i o n so nv i s u a l i z a t i o na n dc o m p u t e rg r a p h i c s ， 2 0 0 1 ，7 ( 4 ) ：3 3 3 3 4 2 7 w a nm ，d a c h i l l ef k a u f m a na d i s t a n c e - f i e l db a s e ds k e l e t o n sf o rv i r t u a ln a v i g a t i o n i n ： p r o c e e d i n g so f t h ei e e ev i s u a l i z a t i o n2 0 0 1 ：2 3 9 - 2 4 6 8 b i t t e rl ，k a n f m a na e ，s a t om p e n m i z e d d i s t a n c ev o l u m e t r i cs k e l e t o na l g o r i t h m i e e e t r a n s a c t i o n so nv i s u a l i z a t i o na n dc o m p u t e rg r a p h i c s ，2 0 0 1 ，7 0 ) ：1 9 5 2 0 6 9 江萍基于形态学骨架提取算法的研究及其实现计算机应用，2 0 0 3 ，2 3 ( 6 ) ：1 3 6 1 3 7 1 0 王刚基于区域增长技术的树状器官的骨架提取算法西安电子科技大学学报2 0 0 3 ， 3 0 ( 5 ) ：5 9 4 5 9 7 1 i 罗立民谢筱华鲍旭东利用三维几何矩在核磁图象中定量检测血管科学通报1 9 9 4 ， 3 9 ( 4 ) ：3 7 2 - 3 7 5 9 三维脑m 管中轴提取算法研究 1 2 谢筱华罗立民韦钰基于矩的三维幽象边界检测计算机学报1 9 9 4 ；1 7 ( 1 ) ：1 - 8 1 3 k p a l a g y i ，a k n b a , d i r e c t i o n a l3 d t h i n n i n gu s i n g8s u b i t e m t i o n s ，p r o e d g c i 9 9 ，l n c s l 5 6 8 ， 1 9 9 9 ：3 2 5 3 2 6 1 4 s e r r a j i m a g e a n a l y s i sa n dm a t h e m a t i c a lm o p p h o l o g y m l o n d o n ，a c a d e m i cp r e s s ，1 9 8 2 1 5 崔屹数学形态学方法及应用 岫北京：科学出版社，2 0 0 0 1 6 余松煜数字图像处理 m 北京：电子工业出版社，1 9 9 8 1 7 范江波，周明全，耿国华虚拟内窥镜技术的研究与实现 j ，2 0 0 0 ：( 6 ) ：6 0 6 3 1 8 w o o ds ，z e r h o u n ie ，h o f o r dj ，e ta 1 m e a s u r e m e n to f t h r e e - d i m e n s i o n a ll u n gs t r u c t u r e sb y u s i n g c o m p u t e d t o m o g r a p h y j a p p l p h y s ，1 9 9 5 ；7 9 ( 2 ) ：1 6 8 7 1 6 9 7 1 0 东南人学顾1 学位论文 第二章基于三维欧几里德距离变换的中轴提取算法 2 1 引言 每个像素或体素的距离变换值是该点到图形边界的最短距离，任何基于距离变换的中轴 提取算法都要首先计算距离变换。 物体的中轴点是满足如下条件的点： 1 ) 在与同一边界点对应的所有点中，中轴点与边界的距离最大； 2 ) 这一点到所有边界的距离当中，应该能够找到展小的距离。 所有符合这些条件的点连接起来就成为物体的中轴，中轴点的这些特点构成了基于三维 距离变换算法的依据。 2 2 距离变换 距离变换的概念自r o s e n f i e l d 和p f a l t z 1 于1 9 6 6 年首次提出以来，己被广泛地应用 于图像分析、计算机视觉和模式识别领域。人们利用它来实现目标细化、中轴抽取、形状的 插值和匹配、粘连物体的分离等 2 8 。 距离变换是针对二值图像的一种变换，它的变换结果不是另一幅二值图像，而是一个灰 度级图像，即距离图像。图像中每个像素点的灰度值为该像素与距其最近的背景像素间的距 离。也有另外一种表述，图像中每个像素点的灰度值为该像素与距其最近的特征像素间的距 离。由于变换的对象是二值图像，所以两种表述方法是一致的。 2 2 1 距离的定义 图像中两像素之间的距离有多种定义方法 9 】，例如c i t y b l o c k 距离，c h e s s b o a r d 距离和 e u c l i d e a n 距离等。 1 ) c i t y b l o e k 距离即满足下面的公式： o = l a x l + l a y i 如图2 1 ( a ) 所示 2 ) c h e s s b o a r d 距离，即满足下面的公式： o = m a x o 缸i ，蚓) 如图2 1 ( b ) 所示 三维j i j | 舡管中轴提取算法研究 2 一 k ， ， ， 2 一 p l ( a ) c i t y b l o c k 距离 1 一 x ， 2 - 圈2 1 两种距离的定义 h 啼 1 ( b ) c h e s s b o a r d 距离 3 ) e u c l i d e a n 距离，欧几里德距离是最直观的距离定义方法，满足如下公式 如图2 2 所示 l ， 吖 ， 、 啼 l ( a ) 二维像素的距离 d ：k ) 2 + b ) 2 2 1 o ( b ) 三维体元的距离 闰2 2 欧几里德距离示意图 2 东南大学硕一i ：学位论文 2 2 2 距离变换相关背景 在二维空间，一个n x n 的二值图像可以认为仅包含特征和背景两种像素。我们将特 征像素称为“自点”背景像素称为“黑点”。在距离变换图像中，每个像素值表示该像素 到离它是近的一个黑点的距离。在实际计算中，常采用两种距离测度：非欧几里德距离和 欧几里德距离。前者常采用串行扫描实现距离变换b o ，主要步骤为： 1 ) 按从左到右，从上到下的光栅扫描，每碰到一个象素，判断是。 还是非o ，是o ，保留不变：如果是非o ，则原值 p = m i i l 0 4 + 5 ，p 3 + 7 ，p 2 + 5 ，p l + 7 ) 。 2 ) 逆程扫描，从右从下开始扫描。每碰到一个象素，判断是0 还是 非o ，是0 ，保留不变；如果是非0 ，则原值 p 3p 2p l p 4 pp o p sp 6p 7 图2 3 光栅扫描 p = p + m i l l b ，m i n ( p s + 7 ，p 6 + 5 ，p 7 + 7 ，p o + 5 ) 】，得到整个的距离图。 该算法扫描过程中传递最短距离信息，计算简单，但得到的仅是欧几里德距离的一种近似 值。在三维图象处理当中，我们往往要面对较大的数据量。此时，串行算法速度较慢，精确 度也不高。文献 1 1 提出一种欧几里德距离变换的最优算法，采用行列交叉处理的方法， 缩小搜索最近黑点的范围。 常见的三维距离变换算法大都是对二维近似欧几里德距离变换算法的三维扩 展，0 k a b e 9 等人将棋盘( c h e s s b o a r d ) 方法扩展到三维。b o r g e f o r s 1 2 设计了一个3 3 x 3 的局部操作器来实现距离变换，并将算法产生的距离与欧几里德距离的差值最小作为优化标 准。r a g n e m a l m 1 3 对此算法做了改进，然而这些算法得到的都是近似的欧几里德距离。而关 于三维欧几里德距离变换算法。文献中却很少提及。在有些应用领域，如三维医学图像处理 中，由于对精度有很高的要求，因此要求距离变换算法得到的必须是完全欧几里德距离。 本章在二维欧几里德距离变换算法的基础上，提出了一种三维欧几里德距离变换算法， 在三维空间中可以得到完全欧几里德距离。对一个n xn xn 的三维二值图像，我们将其 分解成个n n 的二维二值圈像，首先对个二值图像进行二维欧几里德距离变换， 然后利用二维欧几里德距离变换的结果，进行三维欧几里德距离变换，并且通过优化方法来 减少计算量。 1 3 三维脑皿管中轴提取算法研究 2 2 3 完全欧几里德距离变换 给定一幅幽像。图像中的像素被分成特征像素和非特征像素。特征像素可以是点、边， 或者物体。所谓图像上的距离变换，就是求图像中每一个像素到离它最近的特征像素的距 离。 对于一副n n 二维二值图像，我们把值等于1 的像素( 白点) 作为感兴趣的部分， 而把值等于0 的像素( 黑点) 作为背景。表示为a 0 = 0 或l ，i = 0 一l ，j 0 n - 1 。令b 2 。= 融，) ，托，= 1 为感兴趣部分的坐标。那么对于口f 的二维欧几里德距离 变换通过下面方法计算： d 2 0 = p m ，_ i n 吗。( f x ) 2 + ( ，一y ) 2 ， i = 0 n i ，_ ，= 0 n i 。 相对于二维图像中的像素，我们把构成三维图像的基本元素称为体素( v o x e l ) ，体素是 图形学中描述几何图元的最小基本单元，体索( v o x e z ) 可以理解为二维像素在三维空间的推 广，它们是一组分布在正交网格中心的立方体单元。基于体素的三维模型有诸多应用，例如医 学影像、流体力学、碰撞检测、地形造型、机械零件造型和制造等领域。圈2 4 所描述的是 三维图像中的体素和它的2 6 邻域。 o “，t o z o o o ；io 。 ：o 二 ，o ： o ：0 ：0 - - o o ；：0 ； tt oio ：- o ： 一o o ；o ro + ： t o o 一o 一；一o o 图2 4 中心体索和它相邻体索的位置关系 4 东南大学硕l 学位论文 ，相应的对于一副n x n x n 三维二值图像，我们把值等于1 的体黍( 自点) 作为感兴 趣的部分，而把值等于0 的体素( 黑点) 作为背景。表示为 a y k = 0 或l ，i 0 。 n i ，= o n 一1 ，k = o n - 1 。令b d = 缸，y ，z 】= 1 为感兴趣部分 的坐标。那么对于口m 的三维欧几里德距离变换通过下匠方法计算： d 2 舭2 i ，。r a ：i i n 毋。( f x ) 2 + o y y + ( k z ) 2 ， i = 0 n 一1 ，= 0 n 一1 ，k = 0 一1 。 2 2 3 1 二维欧几里德距离变换快速算法 文献 1 1 中有如下一些定义： 定义2 1 记f = 缸，j 1 = l 为图像中所有白点的集合。 定义2 2 对于给定( f ，力，记m ( f ，力为距离g ，) 最近的黑点：记 s 呒= f n 缸，y l x f ，) ， 为( f ，_ ，) 左上部分所有黑点的集合： n e o = f n 缸，y l x i ，) ， j 为o ，) 右上部分所有黑点的集合。 这4 个集合到( f ，) 最近的黑点分别记为s ( f ，l 舾( f ，) ( f ，j ) - 与n e ( i ，_ ，) ，它们 当中距离( f ，) 展近者即为 f ( f ，) 。 定义2 3 上( f ，) = m a x 2 ：( f ，) j ，其中m 表示第，列像素左边所有黑点的集合， 则( f ，( f ，) ) 为嵋中第f 行最右边的黑点；r ( f ，) = m i i l ：( f ，) 目j ，其 中e j 表示第，列像素右边所有黑点的集合，则( f ，r ( f ，) ) 为e j 中第f 行最 左边的黑点；p ( f ，j ) = m a x l ：( f ，) s ，) ，其中墨表示第f 行像素下边所有 黑点的集合，则p ( f ，n ，) 为s 中第列最上边的黑点： q ( f ，) = m i n l ：( i ，) 。其中，表示第f 行像素上边所有黑点的集合， 1 5 三维脑6 【管中轴提取算法研究 则( q ( f ，l ，) 为，中第j 列最下边的黑点。 有了这4 个数组，可简化对s w ( i ，j l s e ( i ，a n w ( f ，) 与e ( f ，) 的寻找。 以 s ( f ，j ) 为例，不必计算与比较( f ，j ) l i s w ( i ，) 中所有黑点的距离，而只需将( f ，) 与 ( 1 ，l o ，j 强( 2 ，l ( 2 ，强，( f ，l ( ) ) 作计算比较即可。 引理2 1 ：设q ，) ，0 ，) 为同一列上的两个像素， 且b c l ，若 s 形0 ，) = g ，y ) ，s w ( b ，) = ( z ，w ) ，则z x ；设( f ，口) ，( f ，6 ) 为同一行 上的两个像素，且b 口，若s 旷( f ，口) = 0 ，f ) ，s ( f ，6 ) = 0 ，v ) ，则 v t 。 证明详见文献 2 。对舾，n w 与i c e 也有同样的结论。 g ，r ) r () o ，口) 0 ，v ) - () ( f ，6 ) - ( ) 图2 5 引理2 1 中同一行中的两个像素 由引理2 1 ，可进一步缩小对最近黑点的搜索范围，如已知s 矿( f ，_ ，) = ( z ，w ) ，则对， 列上的其他像素 ，) ，若_ j j ，则 s ，) 只能在第z n 行的范围内。推而广之，设第，列像素已被r 等分且己知 1 6 东南人学硕i 学位论文 s f 堕， ；包，毗炽：】，一，) ，则数组三第列也被分成，部分，其中第i 部分为 lr 三g ，_ ，) g t ，) 。因此，第t 部分像素只需用数组工第，列的第_ i 部分元素去寻找最近 阳黑点。列样，如采一仃像系傲r 等分，也司米州吲样的方 去绢小对s w 僵的搜累予叵围。因 此，对s 矽值的计算可以在行、列方向上交叉进行。以便互相等分，减小计算量。 该算法主要分为三个步骤： 1 ) 对于图像中的某一行，设口u 为该行当中任意一个非0 ( 特征) 像素，p ，剀为该 行当中距离a t j , 最近的o ( 背景) 像素， 矿“表示p ，砂) 所在的列。这一步骤的目 的在于求出该行中每一个非0 ( 特征) 像素所对应的矿，具体方法见表2 1 。 2 ) 对于图像中的每一行，均进行步骤i ) ，这样我们就得到每一行中的非o ( 特征) 像 a i d , 所对应的p ，e ，p ，即) 的坐标为0 ，矿7 ) 。对于图像中的某一列，假设 a o , j , 口u ，4 一1 ，为该列上的所有像素，我们可以得到它们各自对应的 p 。崩， ，只，删p - l ，e 池。对于该列上任意一点口，j ，假设p 。为整副二维图像中 距离a t ， 最近的0 ( 背景) 像素，则由定义2 2 可知，p 。必然是 p 。露力，p l ，即旷p _ 1 ，只当中的一个。由引理2 1 ，假设0 ，) ，( 6 ，) 为同一列上的 两个像素，它们各自对应的p 。的坐标分别为g 。，y 。l k ，y 6 ) ，如果口b ，则 吒。由此我们可以对步骤2 ) 进行优化，假设该列中第警行上像素为鸭。， 苎 p 孟为整副二维图像中距离q 最近的0 ( 背景) 像素，此时该列上的像素己被 二等分，位于。学一l 行上像素所对应的p 。必然位于p 兰的“上方”，而位于 n + i - n - 1 行上像素所对应的p r o m 必然位于p 兰的“下方一。同理，我们可以 继续对歹。进行等分，再计算翌4 行和兰4 1 行，等分越来越细，则计算量越来越小， 直到所有像素全都计算山来为止。令= 2 “，为正整数。n ，表示距离非0 1 7 三维腑m l 管中轴提取算注研究 像素口已( 七x 距离展近的0 像素，在这里。 驰) = - 1 ) + 扣删啪z q 3 ) 撮后，对丁二图像中的任意一个像素口u ，很容易计算出它到0 像素( 背景) 的最短 j a j ， 距离，假设距离q 最近的0 像素的坐标为g ，y ) ，则这个最短的距离值为 图2 6 是对该算法的全部描述 表2 1 ：算法步骤l 的演示 01234567891 01 11 21 3 1 4 1 5 1l1001l0l01100 11 b ，n i l n i ln i l 34 “i 1n i l7 “i 19n i l “i 1 1 2n i ln i ln i l 工，j n i l “i 1 n i l3444779991 21 21 21 2 33334777991 21 21 2n i l n i ln i l 矿o ) 33 3 34 4 77 79 91 2 1 2 1 2 1 21 2 ，表示图像中的某一列o j s n 一1 ，在这里= 1 6 ；a u 。表示第，列中每一点的像 素值；如果d ，2 l ，则以_ = n i l ，否则6 ，。2 _ ， = b h = n i l 矿o ) ：三r ，当( ，一厶y ( ，一岛) 2 【r g 其他 8 = 6 j = n i l ，他 其 铲 当b l gm ，：【 = 足 = 他h 其 沪翔 m = 东南人学顾j 学位论文 0 123 4 567 001il1ll1 i101lll0l 2ll0ll0ll 3ili1 l 1ll 4lll 0l l ll 5li1ll0li 6ll1