基于Delaunay三角网的骨架提取算法研究

第28卷第4期2006年8月舰 船 科 学 技 术

SH I P SC I E NCE AND TEC HNOLOGY Vo.l 28,No .4

Aug .,2006

文章编号:1672-7649(2006)04-0106-03

基于Delaunay 三角网的骨架提取算法研究

倪 健1

,董 强

2

(1.河北工程大学,河北邯郸056038;

2.中国船舶重工集团公司第七一八研究所,河北邯郸056027)

摘 要: 对目标图像提取其骨架,在目标检测、图像编码等计算机视觉、图像处理与模式识别领域有着广泛的

应用。本文提出了一种基于D elaunay 三角网的骨架提取改进算法,给出了实验效果。

关键词: 图像处理;Delaunay 三角网;骨架;中图分类号: TP391 文献标识码: A

The research of skeletonization algorith m based on D elaunay triangulation

N I Jian 1

,DONG Q iang

2

(1.H ebeiUn i v ersity of Eng i n eer i n g ,H andan 056038,Ch i n a ;

2.The 718Research Institute of CSI C ,H andan 056027,China)

Abst ract : The ske leton o f ob ject i m age is ex tracted have been app lied to co m puter v ision ,i m age pro

cessi n g and patter n recogn iti o n inc l u cling ob j e ct detection ,i m age code et a1.Th is paper presents a ne w ske l eton ization algo rithm based on de launay triangulati o n ,an experi m ent is g iven to de m onstrate t h e effecti v eness of t h e a l g orit h m here .

K ey w ords : i m age processi n g ;De launay triangu lation ;ske leton

收稿日期:2006-06-21

基金项目:邯郸市科技攻关项目(200510301-3)

0 引 言

骨架是图像几何形态的一种重要的拓扑描述,由一些表明物体大致形状的细线组成。利用骨架表示原始图像,可以在保持图像重要拓扑特征的前提下,减少图像中的冗余信息。因此,骨架提取算法被广泛应用于生物形状描述、模式识别、视觉检测以及图像

压缩编码等领域。骨架一般应具有以下性质[1]

:

(1)骨架宽度应为一个像素;

(2)骨架要尽可能穿过物体的 中部 ;

(3)骨架应保持物体的拓扑架构。

近年来人们提出了很多骨架化算法,本文根据Delaunay 三角网思想改进了骨架线提取算法,即采用较为简单的三角形切割方法得到运动人体骨架线,有效地区分了轮廓内部和外部,压缩了信息,更利于后期处理。

1 基于数学形态学的骨架提取方法

数学形态学以图像的形态特征为研究对象,它的主要内容是设计一整套概念、变换和算法,用来描述图像的基本特征和基本结构,也就是描述图像中的元素与元素、部分与部分间的关系。数学形态学的数学基础和所用语言是集合论,它把图像看成是点的集合。数学形态学的长处在于能定量地描述几何结构,应用数学形态学可以简化图像的数据,但仍保持他们

的基本形状特征[2]

。

生成图像中一个物体骨架的一种方法可通过沿某方向反复删除物体内、外轮廓线上的像素来完成。这里假定处理的图像为二值图像,称轮廓线上的点为 边缘点 ,在下面的讨论中假设背景为黑色(0),前景(人体)为白色(1),物体表现为图像平面上第一个8连通区域。被处理点及其相邻像素构成一个3!3

第4期倪 健,等:基于Delaunay 三角网的骨架提取算法研究的区域。若一个位置的值为1则称其为白色,否则称黑点。若从一个位置出发到达另一位置所经过的路径均为白点,则称2个位置是连通的。

骨架抽取的算法思想虽然较为简单,即反复地沿着某一方向删除物体的内、外轮廓上的边缘点,直到满足骨架性质为止,但实现起来却有许多细节要特别注意。算法的任何不完备都将直接导致抽取的失败。

2 通过De launay 三角网得出骨架

多边形骨架线提取的关键在于探测多边形内部到边界线上的等距离点集,在几何特征上属于空间邻近关系的探测问题,而计算几何中的De launay 三角网是一种较成熟的支持模型[3]

,具有其他算法模型

无可比拟的优势。

2.1 多边形内部约束Delaunay 三角网构架

[4]

计算几何研究的Delaunay 三角网从数学理论出发,严格符合Delaunay 三角网的性质定义。当应用到实际领域时,需针对其特殊性对算法进行改进。当多边形目标以群点角色直接构建三角网时,在多边形覆盖区域以边界离散点为运算对象建立约束Delaunay 三角网,约束条件为三角形不能穿越多边形的边界。

对多边形内部的三角形,根据邻接三角形的数目,进一步细分为三类:?类三角形是三角网中的边界节点,其3个顶点中有一个顶点作为骨架线的端点;#类三角形是三角网中的跨接三角形,是骨架线的骨干结构,描述了骨架线的延展方向;?类三角形作为骨架分支的交汇处,是向3方向伸展的出发点。2.2 三角网条件序贯遍历及骨架线树结构的建立

对于骨架线的提取,可仿照栅格结构中的扩张算子来设计三角网结构中的扩张算子。由于De launay 三角网在几何特征上具有最邻近连接的特点,三角形的边可以看作是多边形边界上的一点到其他边界点的邻近跨接,三角形跨接边的中点可以认为是多边形在该局部区域的片断中心。将邻接的1批三角形跨接边的中点顺序连接起来,便可以反映多边形在一维特征上的延展趋势,即骨架线。其具体的算法思想如下:首先,建立2个集合,即遍历三角形集{TR I}和分支三角形集{BRANC H },分别用来顺序记录遍历的所有三角形和顺序记录遍历的所有分支三角形(即?类三角形)。由任意一个?类三角形出发,将这个三角形放入{BRANC H }集合中,同时沿三角形三边方向进入邻接的三角形[5]

。

(1)如果当前考察的三角形是#类三角形,则继

续行进的方向就是惟一的,只需将该三角形放入{TR I}集合中;

(2)如果当前考察的三角形是?类三角形,则继续行进的方向就有2个,这样的分支三角形既要放入{TR I}集合中,同时也要放入{BRANC H }栈结构中,然后继续遍历;

(3)如果当前考察的三角形是?类三角形,那么表示这个三角网的一个分支已经遍历完成,将该三角形放入{TRI}集合中。

重复上述过程,考察{BRANCH }栈是否为空,如果栈非空,则取出栈顶的三角形,直至{BRANCH }栈中元素为空,三角网遍历结束,得到三角网中所有三角形元素之间的二叉树结构。图1(a)表达了三角网内的遍历过程;图1(b)为记录对应的二叉树结构。二叉树的叶子节点对应着多边形骨架线的一个端点,其他节点对应着多边形骨架线的分支节点,节点之间的层次关系则描述了骨架线的主干与分支间的嵌套结构。

图1 记录三角网遍历过程的二叉树结构

2.3 主骨架线的提取

上述方法得到的骨架线是二叉树结构,而主骨架线是沿着主延伸方向的线性结构。为此,还需要对按照上述方法提取的骨架线做出取舍,以提取惟一确定的主骨架线。图2描述了骨架线某个分支处的情况。从图2(a)可以看到,多边形的骨架线在 P 1P 2P 3处产生分叉,是典型的二叉树结构。根据Gesta lt 连续性原则,为了保持人们视觉上的连续性和完整性,较为粗壮的R 分支应作为主延展方向。这样,L 分支被裁减,得到图2(b)中惟一确定的多边形延展方向。

基于上述的分析,对主骨架线的提取方法如下。在骨架线分支处,以分支部分的面积作为选取标准,舍弃面积较小的分支,保留面积较大的分支,直至终止于多边形的2个节点,得到主骨架线。对于图1

%

107%

舰 船 科 学 技 术第28

卷

图2 消减分支示意图

（ａ）中的多边形而言,主骨架线上的节点依次为L& A&B&C&H(即被虚线圈住的部分),得到的多边形主骨架线即为图1(b)中加粗的线段。从图1可以看到,得到的主骨架线可以反映出该多边形的形态特征和主延伸方向。

多边形的形状分析是属于空间认知的问题,也是一个不确定性问题。这里选取图2中R分支的依据是因为R分支更加粗壮,即R分支的面积比L分支的面积要大。换言之,是将分支部分的面积作为选取标准。这是因为在视觉认知中,吸引注意力的是图形的主体。选取标准要根据具体需求来确定,并不是惟一的。同时,如果各部分面积势均力敌,也会难以做出确定的选择,这说明,主骨架线只能针对线性结构延展十分明显的多边形,对于像圆形、五角星形等均匀分布的多边形,谈论主骨架线是没有意义的。

3 本文采用的骨架线提取方法

由于De launay三角形方法无法区分轮廓内部还是外部,因此本文在此思想的基础上采用了一种按逆时针遍历轮廓,找到最小的夹角,取对应两边的中线点,切割三角形,删除这个夹角点,继续递归,直到多边形为三角形为止的方法。对于中线点的连接,是采用记录被切割的三角形,在回复骨架时按照递归的方法寻找邻边三角形。其中,依据点与三角形内角和为360?来判断某点是否在被切割三角形内。 用本文提出的骨架线算法,可得到各关键帧的骨架,其效果如图3所示。说明本算法简单、高效,具有

很强的实用性和优越性。

图3 提取骨架线效果

4 结 语

数学形态学在国外已被实际应用于机器视觉、模式识别、图像处理等领域。目前国内也有不少学者研究了基于经典形态学的骨架提取算法,获得了较好的结果。本文研究的骨架提取算法,是经典数学形态学骨架提取方法的拓广和改进,因此有着广泛的应用前景。

参考文献:

[1] 严涛.基于图像的树木造型方法的研究[D].中国科学

院软件研究所,2000.

[2] BLO C H I.M a itre Fuzzy m athe m atical m orpholog i es:a

comparati ve study[J].P attem R ecogn iti on,1995,28(9):

1341-1387.

[3] 闵卫东,唐泽圣.二维任意内点集的D elaunay三角划分

生成算法[J].计算机学报,1995,18(5):365-371. [4] 艾廷华,郭仁忠,陈晓东.D elaunay三角网支持下的多边

形化简与合并[J].中国图象图形学报,2001,6(7):703

-709.

[5] 艾廷华.城市地图数据库综合的支撑数据模型与方法的

研究[D].武汉大学,2000.

作者简介: 倪健(1975-),女,讲师,硕士,从事图像处理与识别的研究。

% 108 %

不规则三角网的算法设计与实现10页word文档

1 引言 地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已经被普遍广泛采用。数字高程模型即DEM （Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。 由于地理信息系统的普及，DEM作为数字地形模拟的重要成果已经成为国家空间数据基础设施（NSDI）的基本内容之一，并被纳入数字化空间框架（DGDF）进行规模化生产，已经成为独立的标准基础产品[5]。DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。

基于三角形的表面建模可适合所有的数据结构，且三角形在形状和大小方面有很大灵活性，能很容易地融合断裂线，生成线或其他任何数据，因此基于三角形的方法在地形表面建模中得到了越来越多的注意，已经成为表面建模的主要方法之一。VB语言简洁易学，对于学习GIS的学生来说无疑是接受很容易而且较快的一门计算机编程和开发语言，也是大多数学生最熟悉和了解的语言。正是基于对生成不规则三角网算法的研究和满足学GIS的学生对VB语言的喜爱和熟悉的情况下，本文就主要介绍用三角网生长算法生成不规则三角网及其在VB6.0环境下的实现。 2 TIN的算法种类及各算法特点 在介绍构成TIN各种算法之前我们要来了解认识一下一个重要法则——Delaunay三角网法则。通常构建三角网并不考虑地性线（山脊线，山谷线）的骨架作用，但是，由于用等高线数据构建三角网时，由于地形的复杂多样，有的地区存在因地形突变而形成的断裂线等特殊地貌。另外一些地区存在大面积水域等内部不需要构网的区域，因此，在精度要求较高的TIN中，必须考虑以上问题。因此此时应顾及地性线，断裂线，水域线等特殊情况，也就是应构建约束—Delaunay三角网。约束法是基于约束图计算约束D—三角剖分[1,9]（简称CDT，即Constrained Delaunay Triangulation）构造算法[8]，这种Delaunay三角网满足这样的法则：Delaunay三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包含其他点。Delaunay三角网由对应Voronoi多边形的点连接而成。Delaunay三角形有三个相邻点连接而成，这三个相邻顶点对应的

一种提取物体线形骨架的新方法

第XX卷第X期自动化学报Vol.XX,No.X 200X年X月ACTA AUTOMATICA SINICA Month,200X 一种提取物体线形骨架的新方法 刘俊涛1刘文予2吴彩华3原亮1 摘要本文提出了一种提取物体线形骨架的新方法。该方法首先计算物体距离变换的梯度，从而得到一个矢量场。距离变换的梯度对提取物体线形骨架具有重要意义，我们据此获得物体内部的关键点。其中，每一个关键点代表了物体的一个凸部分。之后，我们用搜索梯度最短路径的方法连接关键点，从而得到物体的线形骨架。本文方法得到的线形骨架能很好的反映物体拓扑和形状特征，并不易受边界噪声干扰。此外，本文的方法克服了基于距离变换的骨架提取算法固有缺点，获得了具有良好连通性的骨架。因此，基于本文方法得到的骨架能用于物体识别和匹配等领域。对大量二维、三维物体的实验取得了令人满意的效果。 关键词线形骨架,距离变换,梯度 中图分类号TP391.4 A New Method of Extracting the Objects’Curve-Skeleton LIU Jun-Tao1LIU Wen-Yu2WU Cai-Hua3YUAN Liang1 Abstract In this paper a new method of extracting the curve-skeleton of the objects is proposed.The gradient of the distance transform,which is a vector?eld and valuable for extracting curve-skeleton,is used to detect critical points inside the objects.Each critical point represents a convex segment of the object.Then,the critical points are connected through searching the shortest gradient path,and thus,the curve-skeleton of the object is obtained.The method proposed in this paper is insensitive to the boundary noise,and the topological and geometrical features of the object can be represented by the extracted curve-skeleton.Further more,compared with other methods based on distance transform,the method proposed in this paper guarantees the connectivity of the curve-skeleton.The extracted curve-skeleton can be applied to objects recognition and matching and so on.The results of experiments on large number of2D and3D objects are satis?ed. Key words Curve-skeleton,Distance Transform,Gradient 1引言 骨架（Skeleton）又称中轴（Medial Axis），通常使用烧草模型[1]和最大球（圆）[2]模型来描述。骨架有着与原物体相同的拓扑和形状信息，是一种性能优良的几何特征，能够有效的描述物体，因此，在物体识别、路径规划、医学工程[3]等领域多有应用。一般而言，由二值图像表示的二维物体的骨架均由曲线连接而成，而由体素模型表示的三维物体的骨架则往往由一些曲面组成。由于曲面的表示比较复杂，描述其特征比较困难，因此，尚需设法直接得到三维物体的线形骨架（Curve Skeleton），以利 收稿日期XXXX-XX-XX收修改稿日期XXXX-XX-XX Received Month Date,Year;in revised form Month Date,Year 国家自然科学基金(60273099,60471022)资助 Supported by National Natural Science Foundation of China (60273099,60471022) 1.军械工程学院计算机工程系石家庄050003 2.华中科技大学电子与信息工程系武汉430074 3.军械工程学院装备指挥与管理系石家庄050003 1.Dept.of Computer Engineering,Mechanical Engineer-ing Institute,Shijiazhuang,050003 2.Dept.of Electronics &Information Engineering,Huazhong University of Science& Technology,Wuhan430074 3.Dept.of Equipment Command &Management Engineering,Mechanical Engineering Institute, Shijiazhuang,050003 DOI:10.1360/aas-007-xxxx 后续处理。 骨架提取算法大致可以分为两类。一类是基于细化（Thinning）的方法[4,5]，即在保持拓扑不变性的条件约束下，依据体素（像素）邻域信息设定准则，采用迭代的方法逐步剔除普通点，直到最后剩下骨架点。细化算法生成的骨架难以保证准确性和光滑性[11]，需要进一步调整。另一类是基于距离变换的算法[6-10]。这类方法先对物体进行距离变换，据此来寻找骨架点。一般说来，基于距离变换的骨架提取算法获得的骨架点位置比较准确，但难以保证整个骨架的连通性。文献[6]中提出了一种基于距离变换的方法，该方法除需要对物体进行距离变换外，还需要得到距每个体素点距离最近的边界点的坐标，据此建立标准确定骨架点。该方法能得到线形骨架，但当物体分支比较细小时难以保证骨架的连通性。文献[7]提出了一种新的基于距离变换的骨架提取方法。该方法取距离变换值最大且靠近物体重心的点作为骨架生长的起始点。之后按照覆盖、判断新分支数和生长新骨架点几个步骤进行迭代。该方法得到的二维物体线形骨架具有很好的连通性，但不能得到三维物体的线形骨架。广义势场方法[8,9]假定物体的边缘上聚集了均匀分布的同种电荷，这些

ArcGIS方法利用到路面提取道路中心线的方法

A r c G I S方法-利用到路面提取道路中心线的方法利用到路面提取道路中心线的方法在利用GIS制图时，需要经常跟数据打交道。很多初级的制图人员都存在一种惯性思路，以为数据精度越高，出图的效果就越好。这是错误的观点。假如现在需要制作1:1w的地图，但手头上却只有1:500的地形图，数据精度虽然很高，但却无法在小比例尺下显示出来。回到主题上，1:500的数据，大多数道路都是以面状显示。由于其精度高，有些数据甚至是不带线道路图层的，而在1w的地图下，道路以线状表达才是符合要求的。所以，这就需要涉及到地图制图的一个常规工作—地图缩编。本文主要介绍如何从到路面直接提取出道路中心线，从而辅助小比例尺地图的制作。 由于面状数据一般都是不规则的，所以很难从其提取中心线，一般的GIS软件也没提供直接提取的工具。ArcGIS里面虽然也有一些工具可以辅助一下处理，例如在制图工具箱里面有一个提取中心线的工具，但这个工具的作用是通过道路边线（双线）提取中心线。也有人说ArcGIS里面同样是提供面转线工具，先用工具转一道再提取不就行了吗？可是问题来了，面转线工具传出来的数据是封闭线，而不是道路边线，提取中心线工具依然是不可用，除非在每个路面图形打断两端的封闭，不然无法进行提取，恰好打断工作又是非常的巨大。因此，该方法还是不可用。 为了解决这个问题，那就是ArcScan扩展模块。提到ArcScan扩展，很多专业人员第一时间反应是这只是个栅格矢量化工具，跟当前讨论的中心线提取似乎没有任何关系。只要深入了解ArcScan扩展的具体细节，我们不难发现其自动矢量化里面可以提取面要素和中心线，利用这一特性，我们就可以曲线去完成该任务了。 先来说说总体思路：将路面（矢量面数据）转化为栅格数据，因为ArcScan只能对栅格数据进行处理，由于是从矢量转为栅格而非扫描，栅格质量一般会非常好；通过二值化栅格

Delaunay三角形构网的分治扫描线算法

第36卷　第3期测　绘　学　报 Vol.36,No.3 　2007年8月 ACTA GEODAETICA et CARTO GRAPHICA SINICA Aug ,2007 文章编号:100121595(2007)0320358205中图分类号:P208 文献标识码:A Delaunay 三角形构网的分治扫描线算法 芮一康,王结臣 (南京大学地理信息科学系,江苏南京210093) A N e w Study of Compound Algorithm B ased on Sw eepline and Divide 2and 2conquer Algorithms for Constructing Delaunay T riangulation RU I Y i 2kang ,WAN G Jie 2chen (Depart ment of Geographic Inf ormation Science ,N anji ng U niversity ,N anji ng 210093,Chi na ) Abstract :As one of the most important DTM model ,Delaunay triangulation is widely applied in manifold fields.A wide variety of algorithms have been proposed to construct Delaunay triangulation ,such as divide 2and 2conquer ,in 2cremental insertion ,trangulation growth ,and so on.The compound algorithm is also researched to construct Delau 2nay triangulation ,and prevalently it is mainly based on divide 2and 2conquer and incremental insertion algorithms.This paper simply reviews and assesses sweepline and divide 2and 2conquer algorithms ,based on which a new com 2pound algorithm is provided after studying the sweepline algorithm seriously.To start with ,this new compound al 2gorithm divides a set of points into several grid tiles with different dividing methods by divide 2and 2conquer algo 2rithm ,and then constructs subnet in each grid tile by sweepline algorithm.Finally these subnets are recursively merged into a whole Delaunay triangulation with a simplified efficient LOP algorithm.For topological structure is im 2portant to temporal and spatial efficiency of this algorithm ,we only store data about vertex and triangle ,thus edge is impliedly expressed by two adjacent triangles.In order to fit two subnets merging better ,we optimize some data structure of sweepline algorithm.For instance ,frontline and baseline of triangulation are combined to one line ,and four pointers point to where maximum and minimum of x axis and y axis are in this outline.The test shows that this new compound algorithm has better efficiency ,stability and robustness than divide 2and 2conquer and sweepline algo 2rithms.Especially if we find the right dividing method reply to different circumstance ,its superiority is remarkable.K ey w ords :Delaunay triangulation ;compound algorithm ;sweepline algorithm ;divide 2and 2conquer algorithm 摘　要:Delaunay 三角网作为一种主要的DTM 表示法,具有极其广泛的用途。基于分治算法和逐点插入法的合成算法是目前研究较多的用于生成Delaunay 三角网的合成算法。简要介绍和评价扫描线算法和分治算法后,提出一种新的基于这两种算法的合成算法。该方法兼顾空间与时间性能,稳定性较高,分别较扫描线算法和分治算法,运行效率和鲁棒性更优。 收稿日期:2006206221;修回日期:2007202206 基金项目:国家自然科学基金(40401046) 作者简介:芮一康(19832),男,江苏溧阳人,研究生,主要从事地理信息系统理论与应用研究。 关键词:Delaunay 三角网;合成算法;扫描线算法;分治算法 1　引　言 2维平面域内任意离散点集的不规则三角网(TIN 2Triangular Irregular Network )的构建是GIS 数据表达、管理、集成和可视化的一项重要内 容,也是地学分析、计算机视觉、表面目标重构、有限元分析、道路CAD 等领域的一项重要的应用技 术。在所有生成TIN 的方法中,Delaunay 三角网 最优,它尽可能避免了病态三角形的出现,常常被用来生成TIN 。Delaunay 三角网是Voronoi 图的直线对偶图,即是连接所有相邻的Voronoi 多边形的生长中心所形成的三角网。它有以下两条重要性质[1]:空外接圆性质,即由点集所形成的三角网中,每个三角形的外接圆均不包含点集中的

一种基于脊线跟踪的冠状动脉中心线提取方法

收稿日期:2006-11-26;修订日期:2007-07-06 基金项目:新世纪优秀人才支持计划资助项目(NCET 20420948) 作者简介:高飞(1968-),男,山东昌乐人,副教授,博士,主要研究方向:智能信息处理、图像图形学;　高新波(1972-),男,山东莱芜人,教授,博士,主要研究方向:智能信息处理、图像工程、视频信号处理. 文章编号:1001-9081(2007)S1-0380-02 一种基于脊线跟踪的冠状动脉中心线提取方法 高　飞1 ,高新波 2 (1.深圳大学信息工程学院,广东深圳518060;2.西安电子科技大学电子工程学院,陕西西安710071)(nels on_gao2010@yahoo .com;nels ongao2010@g mail .com ) 摘　要:冠脉血管中心线的提取是血管造影图像定量分析中的关键步骤。基于脊线跟踪法,提出了一种血管中心线自动提取方法。通过交互式地指定一个起始点和一个终止点,该算法能够自动获取两点间的血管中心线。实验结果表明了该方法的鲁棒性和可重复性。 关键词:中心线提取;定量冠脉分析;脊线跟踪中图分类号:TP391.41 文献标识码:A 0　引言 冠脉血管造影是临床诊断的重要手段。对冠脉血管进行 定量分析具有重要的实际意义。与传统定性诊断方法相比,它克服了医生判断的主观随意性,提供了更为客观准确的诊断依据。血管轮廓线和中心线的自动提取是血管定量分析的前提。在血管造影图像中,血管的提取可以采用基于区域或边缘的图像分割技术。文献[1]中指出血管的剖面灰度分布呈近似高斯型,因此利用二维高斯模板来提取血管,但该方法比较耗时。文献[2]中利用一维旋转高斯模板代替了二维高斯模板,降低了算法的复杂度。不过,从精确分析的角度看,在血管分析中准确提取血管边缘是更好的选择。在现有的许多血管轮廓提取算法中,血管中心线的检测是最为关键和困难的一步。最简单的方法是手工描绘[3],但该方法费时费力且可重复性差,所以逐渐为人机交互的半自动方法所取代。在这些交互式方法中,操作者只需指明待分析血管段的起始点和结束点,就可以自动获得两点间的中心线[4,6]。不过,现有的中心线提取算法大都基于动态规划方法的,搜索时间较长,难以满足临床上实时性的要求。因此急需研究实时性能好的血管中心线提取算法。 既然血管剖面呈近似高斯分布,那么可以将血管的中心线看作脊线。中心线提取问题就转化为脊线的检测。受文献[5]中指纹特征点提取的脊线跟踪法的启发,本文提出了一种基于脊线跟踪的血管中心线提取方法,在实际应用中也取得了比较好的效果。需要指出的是,这里所说的中心线并不是严格的血管的对称轴线,只要求它位于血管内部且与血管走向一致即可,文献[4]中对此有详细说明。 1　血管中心线提取算法 1.1　图像预处理 血管造影图像质量因拍摄条件的不同而参差不齐,一般都有较强的噪声干扰。既然本文方法主要依据的是血管的脊线特征,因此,首先需要降低噪声对脊线特征的破坏。这里采用二维高斯模板来平滑噪声,模板大小一般应大于所选血管段的最大直径。图1显示了滤波的效果:图1(a )是沿血管一个剖面(垂直中心线方向)的灰度分布曲线,可以看到它近似 的反高斯形状;图1(b )是相应位置的梯度强度;图1(c )(d )为对应的平滑处理结果,可以看到,虽然处理后目标与背景的对比度降低了,但目标灰度和梯度的真实结构得到了加强,这有利于后面准确的计算局部脊线方向 。 图1　预处理结果显示 1.2　中心线跟踪 跟踪过程可以分为两步:局部脊线方向计算和中心线上点的更新。局部脊线方向计算方法将在1.3节中详述,这里假设已经得到了这个方向。为了叙述方便,以下将正在处理的点称为当前点。如图2所示,P k -1是当前点,在P k -1处计算 得局部脊线方向为θk -1,由P k -1沿θk -1前进d 个像素到达P ′k ,通过点的更新操作更新到P k ,此时P k 成为当前点。重复以上过程直到停止条件满足。在P ′k 点的更新操作中利用了匹配滤波方法:在P ′k 点得到局部脊线的估计方向θ′k ,以P ′k 为中心,在θ′k +π 2 的方向上获得剖面灰度分布曲线g ′(i )(i =1,…,2l +1)。设f (k )(k =-m ,…,m )为一维高斯 滤波模板,长度为2m +1,满足 ∑k f (k ) =1。通过下式来得到 更新的灰度分布g (i )(i =1,…,2l +1): ∑m v =-m f (v ) g ′ (i +v ),i =m +1,…,2l -m g ′(i ), 其他 (1) 取g (i )的局部极小值点作为更新点P k (如图2所示)。其中,参数l 、m 、d 可以经验地选择,l 应至少大于最大血管直 第27卷2007年6月 　 计算机应用 Computer App licati ons 　 Vol .27June 2007

三角网算法

三角网算法 (2010-11-15 10:54:01) 原作：Paul Bourke / 1989.1 翻译：robter_x 原文出处： https://www.wendangku.net/doc/a27865694.html,.au/~pbourke/terrain/triangulate/ 这是一个适用于地形模型的三角网算法。 摘要（略） 介绍 有很多技术能够应用于表面插值，也就是说，已知一些采样点高度，求与这些采样点接近的某点的高度。一些常用的方法是邻接插值，表面补丁，二次曲面，多边形插值，样条插值和下面将要描述的丹尼三角网（Delauney Triangulation）。一些插值方法经常应用于经验数据的显示，例如，地形模型中的原始数据来源于调查，气象中心的气象分析数据，或有限元分析筛选出的数据等。 这篇文章讨论的技术不仅适用于地形模型，而且适用于其它方面，这个技术具有下列特点 有一些地方的采样点密度高，而另一些地方的采样点密度低。例如，在地形模型中，一般水边界的内部的采样点呈低密度分布，而在一些较复杂的地方，采样点呈高密度分布。 由于地形表面的不连续，导致采样平面上的采样点较密集。这些可能是自然情况，如，悬岩和河岸，也可能是人工制造的不连续，如围墙。很多平滑方法不能很好的处理这种情况，特别是那些基于多边形的函数将导致表面尖突，摆动和不稳定。 采样点经常沿着等值线分布，这是由于采样点的来源可能是等值线图或者地质调查组的实际勘探。这是导致采样点密度不一致的另一个原因。沿着采样点曲线有较高的采样点密度，而与采样点曲线垂直的路径，除非遇到另一条采样点曲线，否则，没有采样点。 经常需有处理大量的采样点。对一个适用的技术来说，随着采样点数量的增加，处理采样所需的时间应该适度的增加。典型的采样点数量一般是100～100000，对于一个自动化的取样方法来说，通常会有这么大数量的采样点。 获得的采样点一般是逐步增多的。最初获得的采样点被分析，对于感兴趣的地方可能会增加采样密度。很显然，在分析结果上增加一些新的采样点来进一步分析比对所有的采样点重新分析要有利。

三角剖分

Delaunay三角剖分算法 默认分类2009-12-16 11:41:23 阅读33 评论0 字号：大中小订阅 转载：https://www.wendangku.net/doc/a27865694.html,/renliqq/archive/2008/02/06/1065399.html 1. 三角剖分与Delaunay剖分的定义 如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术。该问题图示如下： 1.1.三角剖分定义 【定义】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件： 1.除了端点，平面图中的边不包含点集中的任何点。 2.没有相交边。 3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。 1.2. Delaunay三角剖分的定义 在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起： 【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。 【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。 1.3.Delaunay三角剖分的准则 要满足Delaunay三角剖分的定义，必须符合两个重要的准则：

山脊线山谷线提取实验报告

山脊线山谷线提取实验报告 实验内容描述： 山脊线和山谷线构成了地形起伏变化的分界线（骨架线），因此它对于地形地貌研究具有重要意义；另一方面，对于水文物理过程研究而言，由于山脊、山谷分别代表示分水性与汇水性，山脊线和山谷线的提取实质上也是分水线与汇水线的提取。 本次实验通过某区域栅格DEM掌握山脊线和山谷线这两个基本地形特征信息的理论及其基于DEM的提取方法与原理；同时，熟练掌握利用ArcGIS软件对这两个地形特征信息的提取方法。 实验原理： 1.本实验基于规则格网DEM数据使用平面曲率与坡形组合法提取山脊线和山谷线，首先利用DEM数据提取地面的平面曲率及地面的正负地形，取正地形上平面曲率的大值即为山脊，负地形上平面曲率的大值为山谷。实际应用中，由于平面曲率的提取比较繁琐，而坡向变率（SOA）在一定程度上可以很好地表征平面曲率。因此，提取过程中可以SOA代替平面曲率。 2.主要用到以下理论知识： 1）坡向变率：是指在提取坡向基础上，提取坡向的变化率，亦即坡向之坡度（Slope of Aspect，SOA）。它可以很好地反应等高线弯曲程度； 2）反地形DEM数据：求取原始DEM数据层的最大高程值，记为H，通过公式（H-DEM），得到与原来地形相反的DEM数据层，即反地形DEM数据； 3）地面坡向变率SOA：地面坡向变率在所提取的地表坡向矩阵的基础上沿袭坡度的求算原理，提取地表局部微小范围内坡向的最大变化情况。但是SOA在提取过程中在北面坡将会有误差产生，所以要将北坡坡向的坡向变率误差进行纠正，其公式为： SOA=(( [SOA1]+[ SOA2] )-Abs( [SOA1]-[ SOA2] ))/2 其中：SOA1为原始DEM数据层坡向变率，SOA2为反地形DEM数据层坡向变率。 4）焦点统计 5）ArcScan自动矢量化 流程图

基于MATLAB的骨架提取算法的研究实现

毕业设计（论文）题目：基于MATLAB的骨架提取算法的研究实现 系别信息工程系 专业名称通信工程 班级学号 098204232 学生姓名俞浩然 指导教师欧巧凤 二O一三年五月

毕业设计（论文）任务书 I、毕业设计(论文)题目： 基于MATLAB的骨架提取算法的研究实现 II、毕业设计(论文)使用的原始资料(数据)及设计技术要求： 学习数字图像处理技术，深入研究中轴变换的各种算法原理，采用MATLAB编程，完成中轴变换，要求算法效率较高，且能较好的抑制噪声。 具体要求如下： 1﹑充分了解数字图像处理原理 2、熟悉MATLAB开发环境，图像转换、骨架提取等相关算法 3、采用Matlab实现图像二值化和中轴变换 3、比较各种算法的处理效果；并进行算法性能分析 III、毕业设计(论文)工作内容及完成时间： 第1周-第3周：查找资料，翻译英文文献，撰写开题报告。 第4周-第8周：程序流程框图编制、源程序设计，系统软件设计及调试。 第9周-第13周：实验数据分析。 第14周-第16周：撰写毕业论文，准备答辩。

Ⅳ、主要参考资料： [1].[美]恩格尔 W K. Digital Signal Processing Using MATLAB [M]. 西安:西安交通大学出版社，2002 [2].[美] Nakamura S. Numerical Analysis and Graphic Visualization with MATLAB(Second Edition) [M].北京:电子工业出版社，2002 [3]. [美]冈萨雷斯.数字图像处理（MATLAB版）[M]. 北京：电子工业出版社，2005 [4]. [美]冈萨雷斯.数字图像处理（第二版）[M]. 北京：电子工业出版社，2007 2007 [5]. 张化光,刘鑫蕊,孙秋野.MATLAB/SIMULINK实用教程[M].北京:人民邮电出版社, 2011 [6].秦筱威一种有效的骨架毛刺去除算法[J].华中科技大学学报,2004,(12): 28-31 [7]. 杨承磊, 孟祥旭等. 带状图像交叉区域的骨架求解算法[J]. 计算机辅助设计与图形学学报, 2000, (9): 677-681. 信息工程系通信工程专业类 0982042 班 学生（签名）： 填写日期：自2013年2月21日至2013年 5 月 28 日 指导教师（签名）： 助理指导教师(并指出所负责的部分)： 通信工程系主任（签名）：

delaunay算法简介

三角剖分原理： 很多时候我们获取的信息信号都是很离散的信号，比如大地高程测量时的成果测网，纸质各种参数曲线的数字化数据等等，靠大量增加采样点的方法不现实而且会超乎想象的增加处理的计算量，通过趋势分析插值的方法可以使得数字化的模型更逼近原始模型，但是终归于这些离散数据是要通过一种方式在电脑中成为一种整体数据，不管是2d还是3d。 三角剖分最终是要将离散的数据通过连接成很多三角形来达到面化或体化的目的（四面体其实就是四个三角形）。那么我们是不是可以随便来连三角形呢？当然不行了，咱们连成的面或体要与离散化前的原始模型越接近越好。 怎么样才能使咱们连成的面或体要与离散化前的原始模型越接近越好呢？一般来说每个离散点都有一定的作用范围，那么我们在连三角形是不是就要想到，尽量让每个三角形内的三个点相对来说隔得近一点。 首先有两个原则： 1 产生的三角形不相重叠。（如果重叠，那么其中的一个三角形岂不是多余了） 2 不产生新的顶点。（如果产生新的顶点了，那么这个顶点的值我们可以确认它符合于原始模型吗？），不过这条原则很难完全保证不产生。 然后有两个问题要解决：

1 面化或体化时是否要考虑到边界的问题？也就是是否考虑边界离散点的凹凸判断，如果要考虑的话，所有边界点依次相连就行，如果不用考虑的话，所有凸点边界点依次相连就行。一般来说是要考虑的。 2 面化或体化时是否要考虑到面内或体内空洞的问题？也就是是否考虑内部空白区的判断，如果要考虑的话，内部空白区的边界点要跟问题1同等考虑。 再次我们看一下经典的三角剖分方法： 谈到三角剖分，这个名字你不得不熟悉，这就是经典---Delaunay 三角剖分。 Delaunay三角剖分具有四个特有的性质： （1）保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外圆性质。这个特征已经作为创建Delaunay三角网的一项判别标准； （2）它的另一个性质最大最小角性质：在由点集中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形，从这个意义上讲，Delaunay三角网是“最接近于规则化的”的三角网。 （3）Delaunay三角网是唯一的。 （4）三角网的外边界构成了点集的凸多边形“外壳”； 大概的道理我们是懂了，但是给你任意一些点，你采用什么思路

山脊线山谷线提取实验报告

山脊线山谷线提取实验报告 实验容描述： 山脊线和山谷线构成了地形起伏变化的分界线（骨架线），因此它对于地形地貌研究具有重要意义；另一方面，对于水文物理过程研究而言，由于山脊、山谷分别代表示分水性与汇水性，山脊线和山谷线的提取实质上也是分水线与汇水线的提取。 本次实验通过某区域栅格DEM掌握山脊线和山谷线这两个基本地形特征信息的理论及其基于DEM的提取方法与原理；同时，熟练掌握利用ArcGIS软件对这两个地形特征信息的提取方法。 实验原理： 1.本实验基于规则格网DEM数据使用平面曲率与坡形组合法提取山脊线和山谷线，首先利用DEM数据提取地面的平面曲率及地面的正负地形，取正地形上平面曲率的大值即为山脊，负地形上平面曲率的大值为山谷。实际应用中，由于平面曲率的提取比较繁琐，而坡向变率（SOA）在一定程度上可以很好地表征平面曲率。因此，提取过程中可以SOA代替平面曲率。 2.主要用到以下理论知识： 1）坡向变率：是指在提取坡向基础上，提取坡向的变化率，亦即坡向之坡度（Slope of Aspect，SOA）。它可以很好地反应等高线弯曲程度； 2）反地形DEM数据：求取原始DEM数据层的最大高程值，记为H，通过公式（H-DEM），得到与原来地形相反的DEM数据层，即反地形DEM数据； 3）地面坡向变率SOA：地面坡向变率在所提取的地表坡向矩阵的基础上沿袭坡度的求算原理，提取地表局部微小围坡向的最大变化情况。但是SOA在提取过程中在北面坡将会有误差产生，所以要将北坡坡向的坡向变率误差进行纠正，其公式为： SOA=(( [SOA1]+[ SOA2] )-Abs( [SOA1]-[ SOA2] ))/2 其中：SOA1为原始DEM数据层坡向变率，SOA2为反地形DEM数据层坡向变率。 4）焦点统计 5）ArcScan自动矢量化 流程图

【CN109949360A】一种道路中心线的提取方法、装置、电子设备及存储介质【专利】

(19)中华人民共和国国家知识产权局 (12)发明专利申请 (10)申请公布号 (43)申请公布日 (21)申请号 201910204580.9 (22)申请日 2019.03.18 (71)申请人 北京百度网讯科技有限公司 地址 100085 北京市海淀区上地十街10号 百度大厦2层 (72)发明人 高建虎　 (74)专利代理机构 北京品源专利代理有限公司 11332 代理人 孟金喆 (51)Int.Cl. G06T 7/66(2017.01) G06T 7/77(2017.01) G06T 7/13(2017.01) (54)发明名称 一种道路中心线的提取方法、装置、电子设 备及存储介质 (57)摘要 本发明实施例公开了一种道路中心线的提 取方法、装置、电子设备及存储介质。所述方法包 括：根据预先获取的当前导航区域中的各个像素 点的位置和像素值，确定所述当前导航区域对应 的初始道路图像；其中，所述初始道路图像中包 括至少一个初始道路轮廓；将所述初始道路图像 中的各个初始道路轮廓切分为与其对应的至少 两个道路子轮廓；其中，各个道路子轮廓中包括 一个重心位置；根据各个初始道路轮廓对应的各 个道路子轮廓的重心位置，确定出各个初始道路 轮廓的道路中心线。不仅可以准确地提取出道路 中心线，而且还可以节省提取时间，提高提取效 率。权利要求书3页 说明书16页 附图9页CN 109949360 A 2019.06.28 C N 109949360 A

权　利　要　求　书1/3页CN 109949360 A 1.一种道路中心线的提取方法，其特征在于，所述方法包括： 根据预先获取的当前导航区域中的各个像素点的位置和像素值，确定所述当前导航区域对应的初始道路图像；其中，所述初始道路图像中包括至少一个初始道路轮廓； 将所述初始道路图像中的各个初始道路轮廓切分为与其对应的至少两个道路子轮廓；其中，各个道路子轮廓中包括一个重心位置； 根据各个初始道路轮廓对应的各个道路子轮廓的重心位置，提取出各个初始道路轮廓的道路中心线。 2.根据权利要求1所述的方法，其特征在于，所述将所述初始道路图像中的各个初始道路轮廓切分为与其对应的至少两个道路子轮廓，包括： 将所述初始道路图像中的各个初始道路轮廓作为各个当前道路轮廓，根据各个当前道路轮廓中的各个像素点的位置，计算各个当前道路轮廓的覆盖范围； 若各个当前道路轮廓的覆盖范围满足预先设置的第一切分条件，根据各个当前道路轮廓中的各个像素点的位置和像素值，计算各个当前道路轮廓的重心位置； 根据各个当前道路轮廓的覆盖范围和各个当前道路轮廓的重心位置，将各个当前道路轮廓切分为两个当前道路子轮廓，将各个当前道路子轮廓作为各个当前道路轮廓，重复执行上述操作，直到各个当前道路轮廓的覆盖范围不满足所述预先设置的第一切分条件。 3.根据权利要求2所述的方法，其特征在于，所述方法还包括： 若各个当前道路轮廓的覆盖范围不满足所述预先设置的第一切分条件，根据各个当前道路轮廓中的各个像素点的位置，计算各个当前道路轮廓的重心位置到各个当前道路轮廓的距离； 若各个当前道路轮廓的重心位置到各个当前道路轮廓的距离满足预先设置的第二切分条件，将各个当前道路轮廓切分为两个当前道路子轮廓，将各个当前道路子轮廓作为各个当前道路轮廓，重复执行上述操作，直到各个当前道路轮廓的重心位置到各个当前道路轮廓的距离不满足所述预先设置的第二切分条件。 4.根据权利要求1所述的方法，其特征在于，所述根据预先获取的当前导航区域中的各个像素点的位置和像素值，确定所述当前导航区域对应的初始道路图像，包括：根据预先获取的当前导航区域中的各个像素点的位置和像素值，确定出所述当前导航区域对应的预处理前的初始道路图像； 按照预先确定的预处理方式对所述当前导航区域对应的预处理前的初始道路图像进行预处理，获取到所述当前导航区域对应的预处理后的初始道路图像。 5.根据权利要求1所述的方法，其特征在于，所述根据各个初始道路轮廓对应的各个道路子轮廓的重心位置，提取出各个初始道路轮廓的道路中心线，包括： 根据各个初始道路轮廓对应的各个道路子轮廓的重心位置，确定各个道路子轮廓的重心位置的连接规则； 按照各个道路子轮廓的重心位置的连接规则，将各个道路子轮廓的重心位置进行连接，提取出各个初始道路轮廓的道路中心线。 6.一种道路中心线的提取装置，其特征在于，所述装置包括：确定模块、切分模块和提取模块；其中， 所述确定模块，用于根据预先获取的当前导航区域中的各个像素点的位置和像素值， 2

word版本hslogic_Delaunay三角剖分算法应用

本课题的研究方法 三角网格化主要有两种准则:一种称为Delaunay三角剖分,即在生成的三角形网格中,各三角形的最小内角和为最大;另一种是在生成的三角网格中,所有三角形的边长和最小.其中, Delaunay三角剖分是目前研究应用最广的一种剖分方法.本课题的研究方法主要是以Delaunay三角网的两个重要性质（空外接圆性质和最大最小角度性质）以及Delaunay三角网的基本原理为基础，参照传统算法思路，在构建三角网的过程中，改进算法的实现方法，数据结构，以达到提高效率的目的。 Delaunay的重要性质 空外接圆性质：在由点集V生成的Delaunay三角网中,每个三角形的外接圆均不包含该点集的其他任意点。λ 最大最小角度性质：在由点集V生成的Delaunay三角网中，所有三角形中的最小角度是最大的，即在生成的三角形网格中,各三角形的最小内角和为最大。λ唯一性：不论从区域何处开始构网，最终都将得到一致的结果。λ 由于以上特性,决定了Delaunay三角网具有极大的应用价值。Miles证明了Delaunay三角网是“好的”三角网；Lingas进一步论证了“在一般情况下，Delauany三角网是最优的。”同时以上特性也成为建立Delaunay三角网的重要算法依据。 3.3 详细算法描述 算法基于上述的传统构建算法，但仅有两步： 第一步： （1）在离散点集中寻找一纵坐标最小的点A。 （2）以点A为起点，寻找两个点B、D，使得向量AB与横坐标轴夹角最小，向量AD与横坐标轴夹角最大。若点A、B、D共线，将原B点标记为A，寻找点D，使得向量AD与直线AB夹角最大；寻找点C使得向量BC与线段AB夹角最小。否则，若A、B、D不共线，则寻找点C使得向量BC与线段AB夹角最小。这样，所有点都在逆时针旋转的折线DABC的左侧。 （3）上面一步生成的点C、D如果为同一点，则△ABC（或△ABD）即为包含所有不规则点的Delaunay三角形，生成凸包的过程结束跳过一下各步；否

冠状动脉中心线提取

冠状动脉中心线提取 2018.12.5 1简介 1.1步骤和实现方式 本次任务是从冠状动脉增强图像提取血管中心线。步骤和实现方式大致如下： ?图像二值化：读入.mha格式CT图像，阈值处理； ?空洞填充 ?图像细化：类似腐蚀，取最大内切球心的集合 ?端点分叉点检测：考虑26邻域内像素个数，卷积实现 ?断裂分支重连：寻找连接点，条件判断，Dijkstra最小代价连接 ?构建中心线：在分叉点集基础上追踪，数组存储在Cell中 1.2运行说明 coronary_refine.m是主要的运行函数。其他函数和脚本：branchReconnect输入细化后的图像和权重（原始CT volume的像素值为可能性），其中调用了三维的Dijkstra函数；directConnect脚本很简短地实现在三维图像中两点连直线，但因为用了最短路径所以没有采用；其余函数都是由比较冗长的小功能封装成的。两张图片运行时间小于一分钟。 2实现方法 2.1阈值 为了不让阈值化后丢失的成分过多，对后续分支重连的步骤造成困难，这里选择了较小的阈值0.1*原图最大值(2^16)。这也导致最后结果中分支会显得比0.5的阈值下丰富很多，但算法能够原图(mha)保证最终中心线和真实血管走向的一致性。 2.2空洞填充 一开始使用的是imfill函数，通过查看源代码可见这个函数调用了imcomplement和imreconstruct对二值图像进行填充。imfill对三维图像的处理速度较慢，最终使用形态学库函数bwmorph3中的fill功能进行处理。

图1:Skeleton of a rectangle defined in terms of bi-tangent circles. 2.3图像细化 程序中调用了bwskel来实现。Thinning在文献中有两种最为常见的方法，一种被称为“Onion peeling”1，顾名思义用不断的腐蚀操作来一层一层地剥开血管，难点是设置一定的条件来保证原有拓扑结构。这个方法也是bwskel的参考文献中使用的方法。2还有一种细化方法也和腐蚀有些类似，基本思路是求连通域内部的内切圆心（三维为球心）集合，如图一。 2.4基于卷积的端点分叉点检测 虽然形态学库函数中同样有branch和endpoint的功能，但这两个功能的feature都导致它们并不适合直接使用。比如bwmorph3中branch会返回所有分叉点以及分叉点各自的相邻点。面对如此古怪的feature，不如构造简单的卷积核来求端点分叉点。 ?分叉点检测 首先考虑3*3*3全1的卷积核。在二值、细化图像非分叉部分，其响应应该为3。如果将响应大于3的视为分叉，其结果中会有很多处于真正的分叉点附近、实际却为原图空白部分的点被误判成分叉。原因就是分叉附近往往点较为密集，空白点的26邻域内也容易出现多个1，导致超出阈值。解决方法很简单，要让卷积能区分出原中心线上的点和空白格，只要在kernel的中心加大权重，这样空白格的响应和值为1的点差距会变得很大，从而被排除在外。代码如下（因为convolution包含padding，最终结果还需删除padding部分）： 1A Sequential3D Thinning Algorithm and Its Medical Applications 2Ta-Chih Lee,Rangasami L.Kashyap and Chong-Nam Chu Building skeleton models via3-D medial surface/axis thinning algorithms. Computer Vision,Graphics,and Image Processing,56(6):462-478,1994.