（生物医学工程专业论文）基于Level+Set方法的脑血管三维中轴提取.pdf

a b s t r a c t t i t l e ：t h et h r e e - d i m e n s i o n a l ( 3 d ) i m a g e sc e n t e r l i n ee x t r a c t i o no f c e r e b r o v a s c u l a rb a s e do nl e v e l s e t s a u t h o r ：b a oz h e n g y e t h e s i ss u p e r v i s o r ：p r o f e s s o rs h uh u a z h o n g ；a s s o c i a t ep r o f e s s o rz h o uw e i p i n g u n i v e r s i t y ：s o u t h e a s tu n i v e r s i t y i nt o d a y sw o r l d , t h ec e r e h r o v a s c u l a rd i s e a s eh a sb e e no n eo ft h ed i s e a s e st h a tg r a v e l y t h r e a t e nt h eh e a l t ha n dt h el i f eo f t h eh u m a nb e i n g s i nt e r m so f t h ec l i n i c a ld i a g n o s i sa n dt h e r a p y o fc e r e b r o v a s c u l a rd i s e a s e t h eu s eo fc o m p u t e ro fp r o c e s s i n go f3 dc e r e b r o v a s c u l a ri m a g e s s u p p l i e sd o c t o r sat o o l t oo b s e r v e3 dc e r e b r o v a a c u l a rs n u c t 惴f r o ma n ya n g l ea n dh e l p st h e d o c t o r st om a k em o r ea e c u r a t e j u d g e sa n dd i a g n o s e s b e c a u s eo f t h eg r e a tn u m b e ro f b l o o dv e s s e l b r a n c h e sa n dt h e i rt h i ns h a p e ，a n da l o n gw i t hp e o p l e si n c r e a s i n gr e q u i r e m e n t so np r e c i s e l y d e s c r i b i n gt h es h a p eo fb l o o dv e s s e l s ，h o wt og e tt h ee x a l c td e s c f i p t i o no fc e r e b r o v a a c u l a f s t r u c t u r e sh a sb e e na l li n t r a c t a b l eq u e s t i o n t h eo v e r a l lf r a m eo f3 dc e r e b r o v a s c u l a rs t r u c t u r e s l a r g e l yd e p e n d so nt h ee f f e c t i v et e s t i n ga sw e l la ss t n j c t u r er e l a t i o n s h i pd e s c r i p t i o no f b l o o dv e s s e l i m a g e s t h ec e n t e r l i n ee x t r a c t i o ni st h eb a s i so f t h e3 dc 2 r e b r o v a s c o l a rr e c o n s t r u c t i o n , a n di sa l s o t h ek e yp o i n to ft h ew h o l er e s e a r c h i nt h i st h e s i s ，a l g o r i t h mn s e a r c ho fc e n t e r l i n ee x t r a c t i o ni s m a i n l yc o n c e r n e d ；t h ea u t h o rp r o p o s e sa n dc o m p l e t e st h ec e n t e r l i n ee x t r a c t i o no f3 d e e r e b r o v a s e u l a ri m a g eb a s e do nl e v e ls e t s ，t h e r e f o r e ，f u l f i l lt h er e s e a r c hw o r k t h em a i np a r t so f t h er e s e a r c ho f t h i st h e s i sa r ea sf o l l o w e d ： j ) f i r s t ，t h ea u t h o rm a d eas u m m a r yo ft h em e t h o d sf o rc e n t e r l i n ee x t r a c t i o no fo b j e c t s w h i c hh a v eb e e ni n t r e d u e e di nr e c a n ty e a s 2 ) t h ea u t h o ri n t r o d u c e dt h ef u n d a m e n t a lc o n c e p ta n dd e f i n i t i o no f d i s t a n c et r a n s f o r m a t i o n a n dp r e s e n t e dt h ea l g o r i t h m so fc e n t e r l i n ee x t r a c t i o nb a s e do n3 dd i s t a n c et r a n s f o r m t h ea u t h o ra l s or e s e a r c h e do nt h ea l g o r i t h e mo f3 de u c l i d e a nd i s t a n c et r a n s f o r mb a s e d 0 1 1t h e2 de u c l i d i a nd i s t a n c et r a n s f o r mt of i n do u tt h er u l eo ft h e2 da l g o r i t h e m e x p a n d i n gt o3 da l g o r i t h e m 3 ) t h ea u t h o rs u m m a r i z e dt h ep r i n c i p l eo f t h el e v e ls e t sa n dt h ed a t aa l g o r i t h e ma p p l i e dt o c o m p u t e ra n dp r e s e n t e dt h ef a s tc o m p u t i n gm e t h o do fl e v e ls e t s ：f a s tm a r c h i n gm e t h o d r f m m ) b a s e do l li t , t h ea u t h o rp u tf o r w a r da ni m p r o v e df a s tm a r c h i n gm e t h o df o rt h e c e n t e r l i n ee x t r a c t i o na n dt h e nc o m p a r e da n da n a l y z e dt h er e s u l t sw i t ho t h e ra l g o r i t h m s , w h i c hy i e l d ss a r i s f y i n gr e s u l t s 4 ) i n t h i ss e c t i o n , t h ea u t h o rf u r t h e ra p p l i e dt h em e t h o dt o3 di m a g e s ，a n da l s og o tf r u i t f u l r e s u l t s t h ea l g o f i t h e mt h a tt h ea u t h o rp r o p o s e dh a sf u l f i l l e dt h et a s ko f3 dc e n t e r l i n e e x t r a c t i o n t h ew h o l er e s e a r c hh a sb e e ns u c c e s s f u l l yc o m p l e t e d k e yw o r d s ：l e v e ls e t s ，c e r e b r o v a s c u l a r , d i s t a n c et r a n s f o r m , c e n t e r l i n ee x t r a c t i o n , f a s t m a r c h i n gm e t h o d ( f m m ) i i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：导师签名：j 习垦垂鳕瞄期：硎衫 第一章绪论 第一章绪论 1 1 课题的背景和研究意义 脑血管疾病是一种严重危害人类健康的常见病、多发病。脑血管病世界平均发病率约为 2 0 0 l o 万年，最高为日本每年每l o 万人中就有2 9 0 人发生脑血管病。我国各地年均发病 率为21 9 1 0 0 万。据报道，我国每年有2 0 0 多万人发生脑血管病。该病土要发生于中老年人， 其发病率从5 0 岁开始有随年龄增高趁贽。随着我国人口老龄化程度不断增高，老年人比例逐 渐增长，脑血管病发病率会越米越高。 目前已有的诊疗方法人致可分为介入式和基于图像两种方法，介入式的诊疗方法虽然直 接有效但是往往会给患者带来极人的痛苦。而现有的基于图像的诊疗方法例如x 光帆和超 声仪还仅仅只能提供- 二维的幽像信息，这就需要医生在头脑中进行血管二维结构的重建，这 不仅带来了额外的凼难，在某些情况f 也不尽可靠。于是，在诊断和治疗脑血管疾病的临床 实践中。借助计算机对二维的脑血管造影图序列的三维重建处理，为医生提供了一个在任意 角度观察血管的二维结构，从而帮助医生进行诊断和治疗。 二维血管结构的帮体框架很人程度上依赖丁图像中血管的有效检测和结构关系描述。由 于血管中轴币i 原图像凡有相同拓扑性年| i 相似的儿何形状，因此能够较好的反映血管的结构信 息，使医生能够选择自己感兴趣的观察方向和角度，从而得出止确的诊断结果【1 】。j 乞今为 止，人多数的血管中轴提取算法是在二维情况f 提出来的，三维的方法并不是二维情况下的简 单推广。 本课题就是研究三维脑血管中轴提取的算法由于血管中轴提取的好坏将直接影响到图 像信息的表达，| 晟终影响剑诊疗的结果，田此如何能够比较精确的提取三维脑血管的中轴 致关重要，这也是本课题研究的意义所在。距离变换与中轴变换是图像分析当中重要的研究 方法，它们对对像的结构特征、拓扑控制、形状表示等方面简单而有效。 1 2 研究现状 骨架( 或中轴) 在很多领域都有很重要的应用，如物体表达，数据压缩，计算机视觉和 东南人学硕士学位论文 计算机动画。利州骨架表示原始图像，可以在保留原始图像的拓扑结构和形状特征的前 提f ，减少幽像的冗余信息。 骨架提取的算法很多，大致可以分为二种： 1 拓扑细化的算法，这是基丁形态学的方法基本思想是逐层均匀的剥掉图形的边界点， 剩f 晟里层的不能再剥掉( 否则会影响连通性) 的部分就得到了图形的骨架。通常的实现手 段是给山一种简单点( s i m p l ep o i n t ) 的定义，此种简单点的移除不会影响原始图形的连通 关系简单点的判断通过考察某点与其领域点的连通关系实现每次迭代过程去除本轮的简 单点，循环执行迭代过程直至去除所有的简单点，剩余的点集构成骨架点集。 细化法的不足在丁计算复杂度高和骨架位置不精确。复杂度高是因为细化法通常需要进 行迭代运算；位置不精确是因为细化法只是考虑局部连通关系，无法对图形特征迸行全局的 把握。 车武军和杨勋年提出一种改进的细化算法解决骨架位置不精确的问题。该算法首先用 传统细化法求出连通的骨架，然后引入s n a k e 模型调整骨架的位置 2 ，这虽然可以在一定 程度上解决精准度问题但仍不如距离变换方法精确。 2 为把中轴看作计算儿何学中的等分线，利用v o r o n o i 图进行计算。但是计算相当复杂 3 。v o r o n o i 图是计算儿何领域里的一项重要i ：具。给出空间里由h 个点组成的点集s 。对 丁点集s 中的点j p f ，v o r o n o i 多面体表示到点厅距离小于到点集s 内任何其它点距离的空 间区域。v o r o n o i 幽是所有这些v o r o n o i 多面体的集合。 根据骨架的定义，最人圆( 球) 与图形边界是相切的，骨架点与至少两个边界点的距 离相等且取展小值。因此，图形边界点集的v o m n o i 倒能够给出部分的骨架。不完备之处在 于v o r o n o i 图计算的是空间内剑给定点集距离最小的区域，因而不区分幽形内外部分，在遇 到有凹点的图形时与精确骨架有差别，可知骨架是v o r o n o i 图的子集。 v o r o n o i 幽方法只适合计算简单多面体的骨架。不适用于离散模型。对于复杂的三维实 体，理论上可以先_ l i 表面网格模型表达然后计算v o n r o n o i 图，但是若原始物体表面太光 滑，则表面多边形太小，v o n r o n o i 图的计算晕将十分庞人，因此v o n r o n o i 图方法的适用范 围目前还比较狭窄。此类方法也便r 生成多尺度骨架描述，但是需要剪支的过程而且规则 很复杂。 o g n i e w i c z 给出了利刚v o r o n o i 图计算二维骨架的方法【4 】，a e d d y 和t u r k i y y a h 利用 v o r o n o i 到的反变换d e l a u n a y 二角化计算了三维骨架【5 】。 3 为计算物体边界的距离变换。 距离变换记录了| 玺| 形内每个点到边界的摄短距离，以任一点为圆心，该点的距离变换值 为二# 径作的圆就是以该点为圆心的图形内切圆。因此距离变换这一图形分析里的基本手段被 2 第一章绪论 引入进了骨架算法的研究中，利刚距离变换可以生成任一点的内切圆，然后比较所有内切圆 的包含关系就能判断哪些是最人圆。基下距离变换的方法在骨架点的准确度上有明显的优 势，且由此类方法求出的骨架具有完全重建原始图形的能力，并具备平移、旋转、比例变化 的不变性 6 】。但是这类方法很难保证骨架的连通性，这将影响骨架拓扑特性的表达。此类 方法也不保证骨架结果的单像素特性，这点与骨架定义是不符的，并且会影响匹配算法的进 行。 n i b l a c k 和g i b b o n 引入了鞍点( s a d d l ep o i n t s ) 的概念【7 】，鞍点不是严格的最大圆的圆心， 是将标准拓宽寻找剑的一类点，这些点能将不连通的骨架部分连通起来。鞍点虽然在二维里 较好的解决了骨架连通性问题但是却不容易推“到三维。 距离变换也可以f h s e t h i a n 8 介绍的f a s tm a r c h i n gm e t h o d ( f m m ) 来计算，f m m 以同定 的速度沿着边界法线方向的演化满足距离变换【9 】。然后视中轴为距离变换的奇点，检测出 距离变换的奇点。 s i d d i q i 1 0 等人是在演化界面跟踪做记号的点，骨架点即为能量守恒定律被破坏的点 虽然这种方法比直接奇点检测要稳定，但是计算量很大。m a r t i n 1i 】等人在f m m 得到的距离 变换上利用矩分析方法检测骨架，同样运算繁琐。 由 1 2 】知，骨架点就是由丁紧致的边界线段，在f m m 界面传播过程中消失的点。也就是 说，所有在界面传播的点都来白丁边界点，边界里面的点在边界上都有一个源点。所以我们 只需确定演化曲线上的每一点来自下边界线上的哪一点【1 3 】。 基丁上述认知，本文提出了一种基 f m m 的增广骨架提取方法。该方法计算简单，不 必进行导数，梯度和差分的计算因此更稳定。而且从实验结果看，效果相当的好。 1 3 本文组织结构 本文的结构安排如下： 第一章绪论：介绍了本课题三维脑血管中轴提取算法的研究背景和研究意义， 并给出了目前这一研究方向的现状，在这里，介绍了细化，骨架和中轴变换的 不同处，同时介纠了目前己知的各种骨架提取的算法。 第二章距离变换：介绍了距离变换的基本概念和定义，提出了一种基于三维距离变换 的中轴提取算法，该算法以分割后的二值体数据作为输入，进行距离变换，在 这里我们在_ 二维欧儿里德距离变换算法的基础上，对三维欧儿里德距离变换进 行了研究，从而对距离变换在中轴提取上的应用有了大概了解，为下一步基于 l e v e ls e t 方法进行中轴提取打好了基础。 第三章水平集基本理论及实现：介绍了l e v e ls e t 方法的原理以及应用于计算机的数值 3 东陌人学硕j ：学位论文 解法讨论了l e v e ls e t 的快速算法：快速行进法( f a s tm a r c h i n gm e t h o d ) 。接 着本章提出了一种改进的f m m 算法来计算脑血管图像的中轴，然后我们把该 方法提取应_ l j 于中轴提取，并且和其他算法进行了比较和分析。 第四章基丁l e v e ls e t 方法的二维骨架提取：把本文算法扩展到三维脑血管中轴提取 井实现，通过对实验结果的比较和分析得出了结论，总结了l e v e ls e t 方法的 优势和待改进之处，基本完成了课题研究的要求。 第五章总结与展望：总结了上述算法的优点，以及算法中些缺憾和需要改进的地方， 展望了一些朱来可以做的一些_ l 作。 4 第一章绪论 参考文献 【j 】冒非罗立民鲍旭东血管数字减影图像中的结构特征提取【j 】电子学报1 9 9 5 ， 2 3 ( 1 5 ) ：2 2 3 - 2 3 8 【2 l e e t c ，k a s h y a p ，r ，l b u i l d i n gs k e l e t o nm o d e l sv i a3 - dm e d i a ls u r f a c e a x i st h i n n i n g a l g o r i t h m s j c v g i p ：g r a p h i c a lm o d e l sa n di m a g ep r o c e s s i n g , 1 9 9 4 ，5 6 ( 6 ) ：4 6 2 - 4 7 8 【3 】乍武军杨勋年，汪国昭动态骨架算法f j 】，软t i ：学报，2 0 0 31 4 ( 4 ) ：8 1 8 - 8 2 3 【4 o g n i e w i c z l 艮a u t o m a t i cm e d i a la x i sp r u n i n gb ym a p p i n gc h a r a c t e r i s t i c so fb o u n d a r i e s e v o l v i n gu n d e rt h ee u c l i d e a ng e o m e t r i ch e a tf l o wo n t ov o r o n o is k e l e t o n s j ，h a r v a r d r o b o t i c sl a b o r a t o r y ，t e c h n i c a lr e p o r t 9 5 - 4 ，1 9 9 5 5 r e d d y j m ，t u r k i y y a h g m c o m p u t a t i o no f 3 ds k e l e t o n su s i n gag e n e r a l i z e dd e l a u n a y t r i a n g n l a t i o nt e c h n i q u e j c o m p u t a i d e dd e s i g n ，1 9 9 5 ，2 7 ( 9 ) ：6 7 7 6 9 4 【6 l o b r e g t s ，v e r b e e k p w ，g r o e n f c at h r e e - d i m e n s i o n a ls k e l e t o n i z a t i o n ：州n c i p l ea n d a l g o r i t h m j i e e et r a n s a c t i o n so np a t t e r na n a l y s i sa n dm a c h i n ei n t e l l i g e n c e ， 1 9 8 0 ，2 ( 1 ) ：7 5 - 7 7 【7 n i b l a c k c w ，g i b b o n s b p ，c a p s o n w d ，g e n e r a t i n gs k e l e t o n sa n dc e n t e f l i n e sf r o m l ：l l e d i s t a n c et r a n s f o r m ，c v g i p ：g r a p h i c a lm o d e l sa n di m a g ep r o c c s s i n g , n r 5 4 ，1 9 9 2 ，p p 4 2 0 4 3 7 【8 s e t h i o n j af a s tm a r c h i n gl e v e ls e tm e t h o df o rm o n o t o n i c a l l ya d v a n c i n gf r o n t s j ， p r o e n a t a c a d s c i 1 9 9 69 3 ( 4 ) ：1 5 9 1 1 5 9 5 s l o b r e g t ，p w v e r b e e k , f c a g r o e o 9 】杨新图像偏微分方程的原理与麻刚【m 】，上海交通人学出版社，2 0 0 3 年第一版 f 1 0 s i d d i q i l k ，b o u i x s ，t a n n e n b a u m a ，w z u c k e r s ，t h eh a m i l t o n - j a e o b i s k e l e t o n j ，i n t l c o n lo nc o m p u t e rv i s i o ni c c v 9 9 ，p 8 2 8 - 8 3 4 ，1 9 9 9 【1 1 】m a r t i n r u m p ca l e x a n d r u t e l e aac o n t i n u o u ss k e l a t o n i z a t i o nm e t h o db a s e do l ll e v e l s e t s c 】i e e et c v gs y m p o s i u mo nv i s u a l i z a t i o n ( 2 0 0 2 ) f 1 2 k i m m e l r ，s h a k e d d ，k i r y a t l rb r u c k s t e i n m a ，s k e l e ! o n i z a t i o nv i sd i s t a n c e m a p sa n dl e v e ls e t s ，【j 】c o m p u t e rv i s i o na n di m a g eu n d e r s t a n d i n g , v 0 1 6 2 ，n o 3 ， p p 3 8 2 3 9 1 ，1 9 9 5 【1 3 】舒中力基丁l e v e ls e t 方法的心血管图像中轴提取【r 】硕士学位论文2 0 0 5 年6 月 5 东南大学硕上学位论文 2 1 引言 第二章距离变换 距离变换( d t d i s t a n c et r a n s f o r m ) 是图形分析领域的一种基本研究手段，它的实质 是一种i ! i 像变换方法，被广泛应_ 【l j 于图像形态处理( 如细化、粗化、骨架化) ，模式匹配( 如 物体检测和s t e r e of e a t u r e 匹配) ，机器人碰撞检测，计算图像两点之问的最短距离，虽短路 径检测，形状田子的计算，数据压缩，离散v o r o n o i 图等方面。本章主要介绍了距离变换的 基本理论利三维距离快速变换的中轴提取方法，为后面对水平集理论进行阐述做个铺垫。 2 2 距离变换的基本概念 给定一幅离散二值图，它由一些特征像素点和非特征像素点组成，这里所谓的特征点可 以是点、边或物体等感兴趣的对像。尽管对这个二值图作任何的处理并不会给我们提供更多 的额外信息但合适的处理能给我们提供灵活的处理方式，距离变换就是这么一种手段。通 过距离变换，一幅_ 二值幽就可以转换成相麻的灰度图其中每个像素对应它到最近特征点的 距离值：这样，原来的二值图( 可以看成是只有两个灰度的灰度图) 就成为灰度更为丰富的 灰度豳。 距离变换首先是由r o s e n f e l d 和p f a l t z 在1 9 6 6 年引入的。在提出这个概念的同时，他们 给山了一种4 d m e t r i c 的快速算法随后在1 9 6 8 年改进为“伪”并行算法。出于计算效率 考虑，由这些方法计算得剑的并不是真止的欧氏距离，与坐标的选取有人的关系，但奠定了 后来各类快速距离变换的基本思想。为了提高这些算法的准确性，在随后的十多年时间里， 一些学者，包括r o s e n f e l d 和p f a l t z 在山，作了改进性工作但进展不鲥1 】【2 】。在1 9 8 0 年， 情况山现了转机d a n i e l s s o n 基丁i 前述思想提出了一个当时最好的按序的距离变换算法；尽 管在少数特殊例子f 会山现计算误差，不过误差总小于一个像素，因此这是一个具有实用意 义的欧氏距离变换算法；四年斤，h y a r n a d a 于1 9 8 4 年正式发表了没有误差的并行欧氏距 离算法。从这时起，在上述两个i ：作的推动下，距离变换的研究进入一个黄金时期。 6 第二章距离变换 2 2 1 离散图像的基本概念 为了便于理解i 墨| 像描述的具体方法，有必要了解离散图像的几个几何方面的概念例如 图像的连通性、边界和距离筲。它们有些是显而易见的，有的则要繁复的证明。这些证明不 在本文讨论。一幅数字幽像可以看作是像素点集合。分割后的图像一股由几个部分组成，每 个部分具有一定的灰度值。若全幽所有部分只含有两个灰度值则为二值图。设图像由m 个 非空子集s ，是，s m 组成，即为u t _ l 墨。且s n s j = o ，i j 。当m = 2 时全图 a n s 和组成，为二值图。为方便起见，主要讨论二值图像的情况井约定s 中的点值为 l ，s c 为s 的补集，其中的值为0 。 2 2 1 1 邻接与连通 邻接与连通是像素之间的基本关系，是研究图像描述的基础。邻接和连通 l 1 i - 1 j l - 1 j 1j - i l 卜 1 】 l1 l l 一1 i + 1ji l j - 1 i 一1 图2 1 ( a ) 邻域和邻点 ( b ) 四连通和八连通【5 】 的概念可以直观地叙述如。f 。 除了l 璺 像的边缘点以外，所有像素都有8 个邻点如图2 1 ( a ) 所示。图像处理技术 中常采川两种邻接方式：一种是4 邻接，即指水平和垂直方向的四个邻点( f - i ，d ，( f ， 一1 ) ，( i + 1 ，d ( i , j + 1 ) ，由它们组成的邻域称i f , j 3 的四邻域：第二种为8 邻接，( f ，力与 包括对角元素在内的所有8 个邻点为8 邻接，相应的域称为8 邻域。若两个像素p 和9 是4 邻接的则称它们为4 连通，如果它们是8 邻接的，则称为8 连通。由于连通的定义不同， 同一幽像的迕通性含有差别。例如，i 玺| 2 1 ( b ) 是一个简单的2 值图，如果按4 连通定义来理 解，则l 所表示的部分是根本不连通的线段；若按8 连通来理解，则是一个闭合的环。 卜j 面再对邻接，连通作进一步的讨论。我们说图像中两点j 、q 2 _ 间存在长度为n 的通 路，意思是指存在一系列点昂= 只暑，嚣= q ，其中只是晕。的邻点，1 f s , 。如果 这些邻点的定义是4 邻接的，则称4 通路，如果是8 邻接的则称8 通路。 定义2 1 设s 是图像中的一个子集，p 、q 是s 中的点。如果从，到q 存在一个全部点 都在s 中的通路，则称p 、q 在s 中是迮通的。若这个通路是4 通路，则称4 连通；若是8 通 7 0 0 0 0 0 0 0 0 0 0 0 l l l 0 0 0 o，ooo0 0 ololo 1 0 o o l 0 晖o l o o o o 01 0 0 o o o 0 0 0 o o 譬口0 0 0 0 0 0 0 0 o o o o o o o o o o l l 0 0 o o o o o o 0 0 i 0 0 0 1 0 0 o 1 0 0 0 9 o o 0 i l l o o o 0 o 0 0 0 o o o 0 0 0 0 0 o 0 东南人学硕i ：学位论文 路，则称8 连通。对于s 中任意点p ，s 中所有的与p 连通的点的集合称为s 的连通分 量( c o m p o n e n t ) ，即一个连通的区域。 连通性具有如卜 的性质： ( 1 ) p 与尸是连通的； ( 2 ) 若_ p 与q 吐通，则q 与j p 也迕通； ( 3 ) 若p 与q 连通，q 与r 连通，则p 与r 连通。 由此可见，幽像中的两个点，当且仅当它们属于同一连通分蟹时，它们才是相互连通的。 2 2 1 2 曲线和边界 弧和曲线可以这样定义：它们是集合s 的子集r 。这个子集是s 的连通分量，子集中除 两个端点以外的每一个点都有而且只有两个邻点( 端点仅有一个邻点) 。 设是s 的补集，且图像的边缘包含在中。我们称包含幽像边缘的的连通分 量为背景。而s 的其它连通分颦，如果存在的话，则一定处于s 的某个连通分量之中称 之为孔。例如幽2 1 ( b ) 中矸为背景，鹾为孔。s 中有孔的连通分量称为复连通，没有 孔的称为单连通。 通常对s 和应采用不同的连通定义。设l 所表示的为s ，0 为。若对s 采用8 连 通，则它是个闭合的环，环中间的0 形成了一个孔它与环外的酽是不连通的。如果对 也用8 连通，则的环外部分莆j 环p j 部分是连通的都是背景，这就与环是闭合的这一点 产生矛盾。因此应该h j 4 连通定义，反之亦然。s 中与邻接的点的集合s 称为s 的 边界集合中的点称边界点：按前述的曲线定义可知，边界一般是一条闭曲线。s 中除去f 的点，即s f 称为s 的内部。 以上讲述的就是曲线和边界的基本定义，下面我们看看距离的概念。 2 2 2 距离 距离是构成距离变换的一个基本概念不同的距离定义也对应不同的距离变换，因此在 详细介纠距离变换之前首先要知道几个常t 【 ；| 的距离定义。 2 2 2 1 距离的定义 距离是| 垄i 像，中像素之间重要的儿何特征。一般地说，任意两点问的距离可以有多种规 定方式。但是，各种规定都应满足下面定义： 定义2 2 设，为一非空集合，如果对于，中的任何两个元素j p ，q ，均有一个确定的 8 第二章距离变换 实数记为p ( p ，q ) 与它f f j 对应且满足r 面三个条件： i 非负性：p ( e ，q ) 2 0 ，而且p ( p ，q ) = o 的充分必要条件是p = q ； n 对称性：p ( p ，q ) = p ( o ，p ) ； i i i 三角不等式：p ( p ，q ) p ( r ，p ) + 厦q ，r ) ，这里胄也是，中任意一个元素；则 称p 是，上的一个距离，而称，是以p 为距离的空间。条件1 i t i 称为距离公理。距离空间 中的元素义称为点。 在数字图像处理中，图像，中各元素是离散的像素点，我们称这样的距离空间是离散的。 一般用r 计算距离变换的距离空间包括l ，2 l 和一l ，其中2 模最为理想，具有旋转 不变性等良好性质。 2 2 2 2 数字化图像中常用的距离 f 面，我们将列举出对于数字化l 兰| 像常用的几种距离定义。 现在假设尸，q 是一数字化图像中的两个像素点，它们的坐标或行、列号分别是( 而，m ) ， ( ，儿) ，则可以定义以| 卜几种常用距离公式： 1 欧氏距离 和连续情形f 相同，规定为： 吃( p ，q ) = ( 五一而) 2 + ( ，i 一儿) 2 如图2 2 所示： 1 - - = ， 、，v 一 啼 i ( a ) 二维像索的距离 ( b ) 三维体元的距离 图2 2 欧几里德距离示意图 9 东南大学硕上学位论文 2 街区距离 规定为：面( j p ，9 ) 爿而一x 2i + l y l 一儿i 街区距离义称为绝对值距离。显而易见，这种定义的背景是像北京或长安这类只有纵横 交错的街巷的城市。卜标中的4 表示，从任一点出发只能向上、下，左、右四个方向之一前 进。街区距离是简单、运算速度最快的一种实用定义，但与欧氏距离相比误差最大。 3 棋盘距离 规定： 以( p ，9 = m a x ( i x i 一而i , i y r 一儿j ) z 1 _ ， 1o1 l z l z 2 2 2 22l2 2 图2 3 ( a ) 街区距离( b ) 棋盘距离 ( c ) 八边形距离【3 】 4 m i n k o w s g y 距离 以上二种距离都是m i n k o w s k y 距离的特例。这种距离可以用下式表示为： d ( 口，6 ) = n 一而) ，+ ( m 一儿) ，r ；劬= 2 时，就是欧几里得距离：当归= l 时，则成了街区距离以；当p - - - h 时t 则成了 棋盘距离以。街区距离和棋盘距离是欧几里得距离的近似。由于在数字图像的处理和分析 中，距离常常是作为某种特征出现的，关心的不是它的绝对精度；而这两种近似计算方便， 结果义都是正整数，冈此经常采h j 这两种近似的度量而不采用欧氏距离。 显然，与p 点冉勺街区距离不人于，的点组成的区域是菱形，而与j p 点的棋盘距离不大于 f 的点组成的区域是直立的止方形。如幽2 3 ( a x b ) 所示，其中，= 2 。而以( 尸，9 ) 为p 到q 的最短4 通路的欧度。以( j p ，q ) 为尸到q 的晟短8 通路的长度( 设任意方向两邻点的距离为1 ) 5 八边形距离 顾名思义，八边形距离的特征圆是一个八边形( 如图2 3 ( c ) ) 。八边形距离就是这样一 种距离，其根本思想是将棋盘平街区距离交替地进行以图消除两者的负面影响；由于这样 得到的“特征圆”是一个八边形而被称为“八边形距离”。 卜标8 表示从每点出发可向八个方向前进。 6 豪斯道夫( h a u s d o r l t ) 距离 h a u s d o r f f 距离是广泛_ j 丁衡量两个集合之问差别的度量：对每个一c i 和r 0 。定义 一个彳的一个开邻域为辑( 一) = y l j r a ，矗( y ) 0 ( p r o ) ，则 3 q ed ( 只e ) - 使得p 和旦啊相同的晟近特征点 5 。 证明：设月是离p 最近的一个特征点令q 是，_ 与c ( p ，e ) 的交点，我们证明q i 蔫足性质 2 1 。 h j 反证法。 若彳不是9 的最近特征点，不妨另设为君，如图2 4 所示： 令4 爿p a l 丁| 是 ， c ( 于。) 图2 4 连续点说明 ，畋爿刨i ，如刊p b i ，出爿q b d i = d 二+ 占1 d ；( d 二 = ，d ， - 4 q a i 但这与，口的定义矛盾故有i r e 一，i - r e 证毕 上述引理说明，距离变换的确可以看成是一个局部化过程，但引理2 1 同时指出。完全 的局部化可能会造成一定的误差，因为在离散条件下，只根据邻域无法判断最近的特征点。 2 4 距离变换算法 2 4 1c h a m f e r 距离变换算法 g b o r g e f o r s 在1 9 8 3 年总结了前人的t 作提出了c h a m f e r 算法【1 5 】，它是已有t 作的推 厂：模板的人小可以根据需要选取，模板局部掩码值也可为任意正实数。在c h a m f e r 距离变 换意义f ，每一类人小相同的模板都可以找剑相应一组局部距离晟优值，使得求解的距离与 实际欧氏距离的最人误差最小化。例如对于3 x 3 的模板，最优局部距离为a = 1 ， c 2 = 西1 + 丙靴该组数骶晟大误捌、机击一瓦卜但这组值荆# 局部意义f 的欧氏距离；相反，具有局部意义下的欧氏距离的解即c 1 = 1 ，c 2 = 2 在最大 误差晟，j 、化意义却不是最优的，这时的最大误差为4 7 4 芝- 2 一1 ) * s i z e ，l 百1 一瓦l 显然小3 - 1 4 2 , 2 2 1 i ，因此有人称 iic = ，22c = 时取得的距离变换为伪欧氏距离，但也有的学者将c h a m f e r 算 法得剑的距离统称为伪欧氏距离。 第一二章距离变换 2 4 2 向量法 c h a m f e r 方法的计算结果精度不高，例如m o n t a n a r i 的2 阶伪欧氏距离在( 掰+ 1 ) ( 掰 + 1 ) 区域内的最人可能误差限为0 0 9 m 1 4 。因此吸引不少学者努力寻找更为准确有效的快 速变换算法。首个精度上( 与欧氏距离相比) 具有突破性意义的f ：作是d a n i e l s s o n 于1 9 8 0 年作山的 d a n i e l s s o n1 9 8 0 1 。该算法的重要特点是用两个与输入图像大小相同的二维数组作 为i ：作空间，分别保存沿坐标轴剑最近特征点的坐标分量。要得到实际的距离值，须要计算 各分龄平方和的平方根，例如向量化力，其距离值就是+ y 2 该方法的计算过程与八边形算法很相似：向前向后扫描过程各有一对模板计算更新模 板所覆薷的像素对麻的向量值，井将( o ，o ) f 的像素的向量值重置为新向量中模长最小的向 量；但在计算颦增加不多的情况f 达到很要的精度效果：几乎没有误差，且晟大误差与图像 的尺寸无关，总小丁r 一个像素。尽管没有直接给出距离值，但在需要时可随时转换为距离， 当然计算鼙也相应增加，但反之不成立它可以提供更多的额外信息，因此