（计算数学专业论文）基于拉普拉斯算子的点云骨架提取.pdf

大连理工大学硕士学位论文 摘要 曲线骨架的提取在计算机图形学和可视化领域的许多应用中是一个比较基本的问 题曲线骨架是三维模型的一维表示它广泛地应用在计算机动画、虚拟导航、分割、 形状匹配等领域现有的曲线骨架提取算法使用的三维模型大多是以离散体素或者网格 曲面形式表示的，而直接在点云上提取其曲线骨架的文献比较罕见 本文中我们提出了一种有效且鲁棒的点云骨架提取算法首先我们在散乱点云上建 立邻域关系，进而构建拉普拉斯矩阵将点云上的所有顶点当作位置约束引入方程通 过迭代地更新并且解离散拉普拉斯方程，将点云进行收缩，直到点云收缩到我们需要的 程度然后利用主成分分析方法将节点和分支区分开来分别进行聚类简化，从而得到一 些关键点然后通过本文的连接手术连接这些关键点得到初步曲线骨架最后建立图， 计算这个图的最小生成树，修复最小生成树而得到最终的曲线骨架 通常用三维扫描仪等点云获取设备得到的点云带有不同程度的噪声我们对曲面上 的采样点施加不同程度的高斯噪声，然后利用我们的算法提取曲线骨架实验结果表明 该方法能够较好应用于带有一定程度噪声的点云，即具有较强的抗噪能力该算法对于 任意拓扑结构的点云也能适用实验中我们对于不同亏格的点云提取其曲线骨架，得到 的结果令人满意 树 关键词：曲线骨架；曲线骨架提取；点云；拉普拉斯算子；主成分分析；最小生成 基于拉普拉斯算子的点云骨架提取 a l a p l a c i a nb a s e dm e t h o df o re x t r a c t i o nc u r v e s k e l e t o nf r o m p o i n tc l o u d a b s 仃a c t e x t r a c t i o no fc u r v e s k e l e t o n si saf u n d a m e n t a lp r o b l e mw i t hm a n ya p p l i c a t i o n si n c o m p u t e rg r a p h i c sa n dv i s u a l i z a t i o n c u r v e s k e l e t o n sa l e1 dr e p r e s e n t a t i o no f3 do b j e c t s ， w h i c ha leu s e f u lc o m m o n l yf o rm a n yv i s u a l i z a t i o nt a s k si n c l u d i n ga n i m a t i o n , v i r t u a l n a v i g a t i o n , s e g m e n t a t i o n ，s h a p em a t c h , e t c m o s te x i s t i n gc u r v e - s k e l e t o ne x t r a c t i o nm e t h o d s m a k eu s eo fav o l u m e t r i cd i s c r e t er e p r e s e n t a t i o no rm e s hs u r f a c er e p r e s e n t a t i o n b u tm e t h o d s f o re x t r a c t i o nc u l w e s k e l e t o n sf r o mp o i n tc l o u d sa l es e l d o mr e l a t i v e l y i nt h i sp a p e r ，w ep r o p o s e da ne f f e c t i v ea n dr o b u s ta l g o r i t h mf o re x t r a c t i o n c u r v e - s k e l e t o n sf r o mp o i n tc l o u d s f i r s t l y ，w es e t u pn e i g h b o r h o o d so fs c a t t e r e dp o i n t s ，a n d c o n s t r u c t e dal a p l a c em a t r i x w ct r e a t e da l lp o i n t sa sp o s i t i o n a lc o n s t r a i n t s w es o l v e da n d u p d a t e dt h ed i s c r e t el a p l a c es y s t e mi t e r a t i v e l y ，u n t i la l lp o i n t sc o n t r a c t e dt ot h ep o s i t i o n sw e n e e d e d t h e nw ee m p l o y e dt h ep r i n c i p l ec o m p o n e n ta n a l y s i s ( p c a ) t od i f f e r e n t i a t eb e t w e e n j o i n t sa n d b r a n c h e so ft h ec o n t r a c t e dp o i n t s w ec l u s t e r e dt h et w ok i n d so f r e g i o n ss e p a r a t e l y t og e tt h ek e yn o d e s t h e nw ec o n n e c t e dt h e s ek e yn o d e sb yt h ec o n n e c t i o ns u r g e r yw e p r o p o s e dt og e tar a wc u r v e - s k e l e t o no ft h eg i v e np o i l l tc l o u d w ec o n s t r u c t e dag r a p ho nt h e c u r v e - s k e l e t o n , a n dc o m p u t e dt h em i n i m u ms p a n n i n gt r e e ( m s t ) f i n a l l y ，w er e f i n e dt h e m s ta n dg a i n e dt h ef i n a lc u r v e - s k e l e t o n t h ep o i n tc l o u d sw h i c ha c q u i r e db yt h e3 ds c a n n e ra l eu s u a l l yn o i s y w ea d d e dg a u s s n o i s eo nt h es a m p l e dp o i n t so f m a n i f o l ds u r f a c e s ，a n de x t r a c t e dt h ec u r v e - s k e l e t o nu s i n go u r a l g o r i t h m t h er e s u l t ss h o w e dt h a to u ra l g o r i t h mc a nb ca p p l i e do nn o i s yp o i n tc l o u d s t h a ti s t h ea l g o r i t h mh a sg o o dr o b u s t n e s s t h ea l g o r i t h mc a na l s ob ea p p l i e do i lp o i n tc l o u d so f a r b i t r a r yt o p o l o g y t h ee x p e r i m e n t ss h o w e dt h a tw ec a ne x t r a c tc b r v e - s k e l e t o n so fd i f f e r e n t g e n u sp o i n tc l o u dm o d e l s m s t k 呵w o r d s ：c u r v e s k e l e t o n ；c u r v e - s k e l e t o ne x t r a c t i o n ；p o i n tc l o u d ；l a p l a c i a n ；p c a ； 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意 若有不实之处，本人愿意承担相关法律责任 学位论文题目： 作者签名： 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学硕士学位论文 1绪论 1 1曲线骨架提取的相关背景 曲线骨架作为三维模型的一维表示，在计算机动画、虚拟导航、分割、形状匹配等 领域被广泛采用b l u m1 9 6 7 年给出了骨架的最初定义：三维模型的中轴是由模型最大 欧氏内切球球心构成的点的集合因为模型的骨架很好的保留了模型的拓扑连接性及其 形态，所以经常被用于碰撞检测、三维动画、模型渲染、模型表面重建、模型检索等应 用中 曲线骨架提取的问题在近十年来获得了研究人员的极大关注不过设计一个有效地 骨架提取方法仍然瑟临着极大的挑战曲线骨架提取的困难之一是它没有严格的定义 但是很难决定使用那种算法更好，这是因为对曲线骨架的好坏评价目前还没有一个标准 c o r n e a 等人根据不同的应用提出了曲线骨架需要满足的若干性质 1 9 ，如拓扑一致性、 等距变换不变性、居中性、细性等等，并且对现今骨架提取方法做了大致的归类在不 同的应用领域，对曲线骨架的这些性质有不同的要求 对三维模型骨架的研究很早就开始了骨架提取的方法可以归为两大类，体方法和 几何方法它们的区别在于前者利用模型的内部空间的信息，后者只用到模型的曲面信 息( 1 ) 细化，该方法通过迭代地去掉体素边暴上那些所谓的“简单点”来提取体数据模 型的骨架因为模型的体表示数据量巨大，所以整个过程比较耗时( 2 ) 距离场方法该 方法在模型空间定义了一个距离函数给定一个阈值，通过抽取大于该阈值的点作为候 选体素，然后逐步去掉候选体素边界上的点得到离散点，最后连接成曲线( 3 ) v o r o n o i 图方法利用三维网格模型的顶点或者三维散乱点集可以直接产生v o r o n o i 图，v o r o n o i 图的边和面可以用来提取模型的近似中轴对中轴可以用修剪的办法来生成曲线骨架 ( 4 ) 基于r e e b 的方法，该类算法首先在模型上定义一个连续函数，计算每个模型顶点的 函数值，将具有相同函数值的顶点聚合成一个顶点，得到模型的骨架此外，还有一些 其他方法如s h a f t 等人2 0 0 7 年提出了一种基于可变模型演化的骨架提取方法，可以用于 点云和多边形网格上的骨架提取 拉普拉斯算子是一个局部微分算子它广泛地用于曲面逼近，压缩和水印，还有交 互式的阏格处理和插值等与传统的笛卡尔坐标( 绝对坐标) 只能表示点的全局的空闻 位置不同，微分坐标能表示曲面局部的信息如曲面局部的方向、弯曲程度等因此在曲 面上定义保持这些性质的算子，可以用于一些保持细节的变形等操作s o r k i n e 等人首次 提出了基于拉普拉颠算子的网格变形框架f 3 4 利用该框架变形的优点有( 】) 在约束作 基于拉普拉斯算子的点云骨架提取 用下，能够尽可能地保持曲面局部的细节( 2 ) 解最小平方问题将误差分散，重建的效果 比较好( 3 1 解稀疏线性方程组有高效的算法工具包的支持本文的点云收缩是该框架 应用的延伸 目前在三维网格模型或者体素化模型上提取骨架的方法比较多，而直接在点云上提 取骨架的方法较为罕见利用激光扫描仪、接触式探测器等设备来获取原始点云，是一 种十分重要的模型来源从点云提取出的骨架，可以应用于点云分割，点云动画等领域， 还可以用于点云上的一些后续处理，因此有一定的实用价值在这样的背景下，本文提 出了一个有效并且鲁棒的点云骨架提取方法该方法的特点是仅利用了点云的几何空间 位置信息来提取曲线骨架它避免了事先对点云做网格重建或者体素化等预处理过程 该算法有较强的抗噪能力，对模型的拓扑没有过多的要求，能提较好地取任意亏格点云 的曲线骨架尽管该方法有这些优点，但也有一些问题有待解决( 1 ) 没有找到一个统一 普适的权值来收缩点云不同的权值在点云的收缩过程中有较大的影响取得不好，收 缩的点云容易走出模型甚至发散( 2 ) 对于点云中出现平面或接近平面形状的部分，用 本算法的效果不理想这是因为在这些部分收缩的点云不能很好地呈线性分布，用p c a 方法会将该部分识别为节点从而对曲线骨架的拓扑一致性产生影响 1 2 本文的主要工作 在点云上提取曲线骨架的文献相对较少本文中我们提出了一种有效雨鲁棒的点云 曲线骨架提取算法文中对带有不同程度噪声的点云和不同亏格的点云做了若干实验 我们对点云施加不同程度的噪声，实验结果表明该方法具有较强的抗噪能力，能够较好 地提取带有一定程度噪声的点云对于不同亏格的点云，该算法提取的曲线骨架也令人 满意 本文的结构安排如下： 第二章讨论了基于点云表示的必要性基于点的几何作为高度复杂的三维物体的表 面表达形式，已受到计算机图形学研究者的广泛关注，相对于三角网格模型，点模型表 面既不用存放也不用维护全局一致的拓扑结构，在处理高度复杂或动态变化的物体形状 时，显得特别灵活和方便，产生了很多简单、有效的曲面几何处理和绘制算法 第三章给出了中轴、骨架和曲线骨架的若干概念以及曲线骨架的性质的描述曲线 骨架的性质不是所有的都必须满足，在不同的应用背景下，对于骨架性质要求也各有不 同目前提取骨架的绝大多数算法都是使曲线骨架满足部分的性质 大连理工大学硕士学位论文 第四章是对目前体模型、网格模型上的曲线骨架提取方法的综述曲线骨架提取的 方法可以大致归为两大类，体方法和几何方法它们的区别在于前者利用模型的内部信 息，后者只用到模型的曲面信息 第五章介绍了基于拉普拉斯算子的网格编辑框架的基本知识本文的后续的点云收 缩方面的工作是从该框架引申而来 第六章对本文提出的点云曲线骨架提取的步骤做了详细的描述该算法在点云上建 立了的种邻域关系，从而将拉普拉斯算子在网格编辑方面的框架推广到了点云上点 云上的曲线骨架提取少有人研究，而点云是一种三维模型获取的重要途径，在一些领域 因其简单灵活，比三角网格有着先天的优势直接在点云上提取骨架，对于点云的一些 应用和后续的处理有一定的意义 基于拉普拉斯算子的点云骨架提取 2 点的图形学 近几年来的研究表明，基于点的建模、处理和绘制在计算机图形学领域内正受到越 来越多的关注基于点的几何表示可以看成是对连续曲面的进行采样，得到三维点的空 间位置p ，也可以附带点的法向量n ，或者辅助性的曲面属性，例如颜色或材质等 2 1三角网格与点基元 三角网格仍然是当前计算机图形学应用领域中最常用的曲面表示方法三角网格由 于其简单灵活，在许多注重处理性能的领域取代了传统的c a d ( c o m p u t e ra i d e dd e s i g n ) 曲面表示，如m 瓜b s 曲面 三角网格具有灵活的曲面表达能力，任意拓扑和形状的模型曲面都能用三角网格进 行表达，而且这种表达方式不需要满足复杂的内片光滑条件三角片的简单性使得生成 几何模型和对模型几何处理的算法更有效这个优势在交互式的应用中更加明显因为 对三角片的几何处理和绘制己得到高速图形硬件的支持，这些图形硬件每秒可以处理数 以百万计的三角片和n u r b s 曲面片相比，三角片有更简单的数学表达形式要表示 同样精度的曲面，n u r b s 曲面片表示方式需要更多的片元光滑曲面用三角网格( 分片 线性曲面) 来表示时，对三角形边长减半可以减小4 倍的误差，这意味着三角形的数量与 逼近误差成反比因此，根据曲面曲率( 或形状复杂度) 调整三角网格的顶点的密度可以 更好地逼近模型的外曲面 尽管三角网格比n u r b s 更灵活，但是在有些应用领域也有其限制和不足大多数 三角网格的算法需要维持二维流形曲面前后的拓扑一致性在网格处理过程中，维持拓 扑一致性有时候使得算法复杂度大大增加例如，在动态网格连接中，在极端变形后为 了避免过度拉伸或者在感兴趣区域提供更多自由度，拓扑关系经常需要改变在这种情 况下，基于点的表示更加灵活例如在模型绘制中，曲面的拓扑关系是不需要的因此， 今后在表面几何复杂的模型中，采用基于点云( 它不需要存储和维护全局一致的拓扑关 系) 的表示是一种更简单更灵活的几何处理图元的发展方向 从绘制角度来看，由于三角网格正变得越来越复杂而可能不适合绘制c p u 和g p u 处理能力的稳定增长，廉价的内存和三维扫描仪设备的广泛使用使得获取和处理大量高 精度数据，如包含百万数量级三角片的网格，成为可能当三角片数目超过屏幕像素的 数目时，要绘制这样的三角模型，三角片投影在屏幕上将不足一个像素大小这种情况 大连理工大学硕士学位论文 下，传统增量式光栅化方法的效率大大降低因此，绘制高度复杂模型时点似乎更胜一 筹 ( a ) 蘑i 蘩管 l b jl c j 图21 曲网格绘制b ) c ) ，d ) 点云绘制 f i 口la ) m e s hr e n d e r i n gb ) ，c ) ，d ) p o i n tc o u d sr e n d e r i n g 超 ( d ) 2 2 点的邻域 在点模型几何处理和编辑造型中，采样点邻域的选取是至关重要的一步，无论在点 模型法向和曲率估算、局部几何重建、参数化及光顺去噪中，还是在点模型的编辑造型 甚至点模型的绘制中，邻域的选取都有着非常明显的影响点模型采样点邻域究竟取多 大，如何选取最为适宜，这一问题一直是点模型数字几何处理中的关键问题 在三角网格模型中，利用顶点之间的拓扑连接关系，每一个顶点邻域的确定比较简 单和直观可以取顶点的1 - 环邻域( o n e - x l n g n e i g h b o r h o o d ) ，对某些特定应用，还可以取 顶点的2 环邻域( t w o - r i n g n e i g h t ，o r h o o d ) 等等而对于离散点模型来说整个模型通常由 成千上万的离散采样点组成，每个采样点仅包含几何信息和睦面属性信息，由于采样点 之间无任何拓扑连接信息，采样点邻域的选取要困难得多 ( 1 ) 球形邻域( b m ln e i 窨h b o r h o o d ) 采样点的球形邻域是根据采样点问的欧氏距离构造出的邻域它将在以采样点p 为 中心，半径为e 球内的所有采样点定义为该采样点的邻域点虬= 只| j i p 一只 这 种方式适合于规则点采样曲面，这是因为对于不规则点采样曲面，在一球内可能包含 过多或过少的点除此之外，球形邻域对于即使均匀规则采样但其局部特征尺寸小于 的采样点分布的邻域估算也会不可靠，如：对于两个非常接近且又是分开的曲面在其局 部特征尺寸小于时，邻域估算会不可靠图2 2 中显示的是球形邻域的例子在我们的 数值试验中，取f 为常数的获得了较好的结果 基于拉普拉斯算子的点云骨架提取 图2 2 球形邻域 f i 9 2 2 ab a l ln e i g h b o r h o o d ( 2 ) “近邻 对于欧氏距离不能处理的不规则采样曲面，“近邻提供了一种自适应邻域估算的方 法对于每个采样点p ，将与采样点距离最近的k 个采样点定义为该采样点的邻域点 a m e n t a 等人和a n d e r s s o n 等人指出：如果采样点满足一定的采样规则( 如对局部特征尺 寸的自适应) ，则能保证邻域估算的可靠性 然而，缸近邻仅仅从跟扫描曲面内在几何特性无关的采样点之间的欧氏距离来确定 邻域点，无法反映各个采样点的采样密度改进的肛近邻考虑了采样点处的不同的采样 密度，数目k 的确定使得各采样点的局部采样密度保持不变p = k r 2 ，其中，_ 是采样点 如近邻的包围球的半径 图2 3 肛近邻 f i g2 3k - n e i g h b o r h o o d 大连理工大学硕士学位论文 3曲线骨架的相关概念及性质 三维模型在计算机辅助设计、医学成像、计算机图形学、科学可视化、计算流体力 学等学科中是很常见的而许多应用需要这些模型的一个更“紧凑”的表示曲线骨架 就是这样一种表示在计算机图形学和可视化领域，三维模型的曲线骨架提取是一个 基本的问题曲线骨架是与其三维模型的拓扑一致的一种直观的、易于理解的表示形式 它在很多领域都有应用，如虚拟导航、动画、统计分析、形状匹配和形状恢复等 近十年来，这个问题获得了极大的关注但是设计一个有效而鲁棒的曲线骨架提取 的方法仍然面临着极大的挑战骨架提取的困难之一是它没有严格的定义以至于不同 文献对骨架有不同的定义，他们的算法也只适用于有限的一些模型因为对骨架的评价 没有一个标准，所以很难决定使用那种算法更好c o r n e a 等人根据不同的应用提出了曲 线骨架需要满足的若干性质，如拓扑一致性( h o m o t o p i c ) 、等距变换不变性( i n v a r i a n t u n d e ri s o m e t r i cw a n s f o r m a t i o n s ) 、居中性( c e n t e r e d n e s s ) 、细性( t h i n n e s s ) 等等，并且对现 今骨架提取方法做了大致的归类 3 1中轴( m e d i a la x i s ) 骨架( s k e l e t o n ) 和曲线骨架( c u r v e s k e l e t o n ) 三维模型的中轴是由模型最大欧氏内切球球心构成的点的集合也就是这些内切 球至少和模型的边界交于两个点通常中轴含有面元，所以也可以叫做中轴面打个比 方，一个模型完全由干燥的草组成，在模型边界点燃，如果两个火苗相遇，它们会将对方 扑灭这个模型的中轴就是由火被扑灭的位置组成的模型的中轴如图3 。1 所示 图3 1红色部分表示该模型的中轴 f j 够1 r e dp a r ti st h em e d i a la x i so f t h em o d e l 骨架是模型的极大开球的球心的集合用数学公式表示如下设xc 酞3 是三维模 型球心为x x ，半径为厂的开球定义为s r ( x ) = y r 3id ( x ，少) ，其中d ( x ，y ) 是 基于拉普拉斯算子的点云骨架提取 酞3 中的点x 和y 的距离一个球曲 ) ex 是极大的，如果它不被任何x 中的开球完全 包含 尽管中轴和骨架有密切联系，但是它们严格来说是不同的中轴是骨架的子集如 图3 2 所示该二维模型的中轴和骨架都是一条线段，但是线段的端点属于骨架而不属 于中轴不过有些作者也将中轴和骨架不予区分，交替使用 图3 2红色端点属于骨架而不属于中轴面 f i 荫2 e n dp o i n t so f t h es e g m e n tn o tb e l o n gt ot h em e d i a la x i sb u t1 h es k e l e t o no f t h em o d e l 中轴或骨架的一个主要的缺点就是它们对模型边界的扰动十分敏感图3 - 3 中展示 了边界的一个小扰动对中轴的影响程度 图3 3中轴或骨架对边界扰动敏感 f i 9 3 3s e n s i t i v i t yt os m a l lc h a n g e si nt h eo b j e 盯sb o u n d a r y 在许多应用中，我们需要对模型有一个简明的表示，这个表示或者是曲线，或者是 直线段例如，传统的逆向关节链( i n v e r s e - k i n e m a t i c s ) 动画中的关节链就是由一些表示 模型的躯干、手、脚等部位的线段相互连接而成另外还有一些应用领域如虚拟导航， 需要一组穿过模型的曲线路径三维模型的线状表示通常叫做模型的曲线骨架它是 由一些一维曲线构成的图3 4 给出了一些三维模型的曲线骨架 一8 一 大连理工大学硕士学位论文 尽管曲线骨架看起来很简单，可是到目前为止还没有一个严格的定义2 0 0 6 年d e y 和s u n 提出了一种曲线骨架可能的定义他们通过引人中轴测地函数将曲线骨架定义为 中轴面的子集然而这样的定义过于严格，会限制骨架的一些应用 麓。知弋誉飞 滁 圈34一些三维模型的曲线骨架的例于 f 1 9 34e x 鲫m 嚣o f c l m , e - s k e l e t m l so f d i f f e r e n t3 d o b j e c t s 荐 3 2 曲线骨架性质 三维模型0 的曲线骨架记为s 鲥d 】我们将讨论曲线骨架的如下性质同伦性 ( h o m o t o p i c ) 、等距变换不变性恤v a r i a m t u n d e r i s o m e t r i c t r a l x 商o l i 1 1 a d 0 1 1 5 ) 、可重建性 f r o m t r u c f i o n ) 、细性( t h i r m e s s ) 、中心性( e * n t e r e d n e s s ) 、可靠性( 障l i a b i l i t y ) 、光滑性 ( s m o o t h n e s s ) 、组份可区分性( c o m p o n e n t - w i s ed i f f e r e n t i a t i o n ) 、鲁棒性( r o b u s m , s s ) 和多层 次( h i e r a r c h i c ) 等 32 1 拓扑一致性 即曲线骨架保持拓扑的性质曲线骨架应该与原始模型拓扑等价保持拓扑的性质 可以简单叙述如下两个物体有相同的拓扑，如果它们有相同数量的连通分支、通道和 洞当然严格意义上来说一维曲线不能和有洞物体保持拓扑一致于是我们给出了一 个相对宽松的拓扑保持的定义：对模型的每个通道或者洞曲线骨架应该至少有一个环 当然如果模型没有通道或者洞，则曲线骨架没有环这样定义曲线骨架的性质对于检测 曲线骨架的拓扑保持性很有用 礼 _ 冷育 基于拉普拉斯算子的点云骨架提取 3 2 2 等距变换不变性 给定一个等距变换及保持点与点之间的距离的变换) ，变换之后的模型及d ) 的曲线 骨架，记作s k ( t ( o ) ) ，应该和对变换之前的曲线骨架做变换，后相同即：t ( s k ( o ) ) = 跚丌) 。该性质在形状识别方面的应用上很有用处在这类应用中，需要有一个能描 述物体形状的表示，例如曲线骨架尽管两个相似的物体的方向不同，但是他们的曲线 骨架忽略方向上的差异后的差别很小 3 2 3可重建性 如果将骨架定义为极大内切球中心的轨迹，并且给定曲线骨架和中轴或者骨架的关 系，那么一个很自然的重建模型的方法就是计算以曲线骨架上的点为球心的极大内切球 的并如果记重建操作为r e c ( s k e l e t o n ) ，那么完全的重建操作满足：r e c ( s k ( ) = 0 可以计算以三维模型的中轴或者骨架上的点为球心的极大内切球的并，来将三维模 型完全重建出来通常，因为曲线骨架只是中轴的子集，如果仅利用曲线骨架来做，不 可能将模型完全重建即：r e c ( s k ( o ) ) 0 通过计算0 一r e c ( s k ( o ) ) 的体积来量化重 建模型的误差 直觉上，曲线骨架重建模型的能力大概可以作为衡量曲线骨架好坏的一个标准毕 竟如果利用曲线骨架重建出来的误差很大，说明曲线骨架没有很好地捕捉到原始模型的 形状但是最近的研究表明事实上并不如此在文献 1 1 】中，一些很好的模型的抽象表 示根本不能用来重建另外，在 1 2 】中，利用曲线骨架从三维模型库中找出相似模型获 得了不错的结果 3 2 4 细性 曲线骨架应该是一维的，即在任何方向，曲线上的点，除了连接点( 曲线相交的地 方) ，都最多只有一个体素那么大我们可以将曲线骨架上的点分为三类：正常点只有两 个邻点、端点只有一个邻点、连接点可以有三个或者更多邻点细性和上面一节的可重 建性是有冲突的，二者不能兼顾 3 2 5 中心性 曲线骨架一个很重要的性质就是它保持在模型的中心位置要得到一个好的满足中 心性的曲线骨架，需要让它位于模型的中轴上，因为模型的中轴在它的中心单单让曲 线位于中轴上还不够，我们需要曲线在其对应的中轴部分的中心不过，在绝大多数情 况下，提取的曲线骨架不需要也不希望它严格满足中心性因为我们不希望曲线骨架像 大连理工大学硕士学位论文 中轴那样对模型边界的小扰动过于敏感满足近似的中心性质可能对于许多应用来说已 经足够了例如在虚拟结肠镜应用中，可靠性和光滑性比中心性更重要 3 2 6 可靠性 曲线骨架的可靠性是说模型的每个边界点，至少在曲线骨架的一个点上可见换句 话说，对任意边界点，至少存在一条直线和曲线骨架上的某个点相连，而且这条直线和 模型的边界不相交可靠性这个术语是从虚拟内窥镜而来的，即需要确保内部器官组织 的表面能够完全被内科医生观察到 图3 5曲线骨架的可靠性 f i g3 5t h er e l i a b i l i t yo fe u r v e - s k e l 豇o n 3 2 7 光滑性 曲线骨架满足光滑性不仅视觉上比较美观，而且在一些应用中很有用例如虚拟导 航，将曲线骨架作为照相机的运动路径，曲线需要足够光滑来保证显示的图像不出现剧 烈抖动我们可以将曲线段的光滑性定义为曲线切线方向的变化量要保证光滑地导航， 曲线切线方向角度的变化量需要尽可能地小 3 2 8 组份可区分性 曲线骨架要能够区分模型的不同组份，反映其结构。也就是说模型逻辑上的组份要 和曲线骨架上的组份( 一些弧线段) 能够一对应起来 模型逻辑上的组份没有一个严格的定义有的文献将有意义的组份定义为它能够直 观地和其他部分区分开只要曲线骨架有易于识别的关节和连接点，对原始模型的分割 就可以产出不同组份和曲线骨架的一一对应这个一一对应常常应用于动画和网格分解 中 基于拉普拉斯算予的点云骨架提取 图3 6曲线骨架的组份可区分性 f i 够6 t h ec o m p o n e n t - w i s ed i f f e r e n t i a t i o no fc u r v e s k e l e t o n 3 2 9 鲁棒性 如图3 3 所示，中轴对模型的边界的小扰动十分敏感曲线骨架需要对模型边界的 噪声保持较低的敏感度即有噪声的模型和无噪声的模型计算出的曲线骨架应该相似 因此一个鲁棒的算法不能有很好的中心性质 3 2 1 0 多层次 因为曲线骨架是原始模型的近似，提取的曲线骨架要能反映原始模型自然的层次， 也就是说曲线段有父子关系一个有层次曲线骨架在一些应用背景下很有用比如动画， 模型的躯干是父节点，四肢和头部是它的子节点父节点和子节点的变换相关联，当父 节点改变时，它的子节点要随着改变，当子节点需要变化时，可以通过改变其父节点实 现 一1 2 一 图37 曲线骨架的多层次性 f i 醇7t h e h l e r a j - e h i c o f h l m 3 21 1 曲线骨架的性质小结 除了上述的一些曲线骨架的性质之外，还有一些对算法上的要求，比如计算有效性 因为许多应用要求能够实时地获得骨架上述曲线骨架的性质不是所有的都必须瞒足， 而且有些性质是相互冲突的，如鲁棒性和中心性目前提取骨架的绝大多数算法都只是 使曲线骨架满足上述部分的性质这根据应用背景的不同而有所不同 基于拉普拉斯算于的点云骨架提取 4曲线骨架提取方法概述 对于二维和三维的曲线骨架提取有许多算法，有一些是从二维推广到三维上的，如 细化下面我们将讨论范围限制在三维情况 曲线骨架提取的方法可以归为两大类，体方法和几何方法它们的区别在于前者利 用模型的内部信息，后者只用到模型的曲面信息 4 1 体方法 现有的大多数曲线骨架提取方法利用模型的体素离散表示或者规则的体素化表示， 或者是定义在三维空间的离散场函数这些方法有两个共同的缺点：1 可能丢失细节2 不合适的离散解析度将导致数值计算不稳定 41 】体素细化( v o x e l - t l d n n i n g ) 该方法通过选代地去掉体煮边界上那些所谓的“简单点”( 不改变拓扑结构的点) 来 提取体数据模型的骨架简单点的一个重要性质是它们可以根据局部特征来判断，即 我们可以通过找体素的邻域体累来判断该体素是否是简单点细化算法从模型边界开始 迭代地去掉边界上的简单点来细化模型知道再也没有简单点可以删除为止圈41 显示 了细化二维模型的过程，边界点标记为b 每一步迭代，判断边界点是否是简单点，如 果是简单点，则删除迭代到最后，所有简单点都删除，得到骨架 ：) o 尹。* a 尹 珊 豳汹吗一 图41一个二维模型细化的例子 f i 9 4lt h e t h i n 丌i n gp r o c e s s o i la t le x a m p l e 2 ds h a p e 根据选择简单点的策略的不同和去点的优先规则，衍生出了一类细化的方法2 0 0 8 年台湾成功大学王昱舜、李同益提出了一种迭代的方法提取骨架该方法先将曲面模型 大连理工大学硕士学位论文 体素化，然后在得到的体数据上构造两个关于边界体囊的距离的能量，最小化该能量得 到收缩的体紊接着利用细化的方法生成骨架这样得到的骨架更加光滑，但仍还需要做 后期的修剪处理一般来说细化的方法鲁棒性不好，而且还要避免过量地删去体素 4 12 距离场 大多数基于距离场的方法分如下四步：( 1 ) 定义距离场( 2 ) 找到“脊点”( 3 ) 修剪 ( 4 ) 连接 首先在三维模型内部定义了一个距离函数对于模型内部每个点，其距离值为该点 到模型边界的最小距离即d ( 尸) = 恶恐，( d ( 尸q ) ) ，其中b ( o ) 是模型的边界点集台， 。 d ( 只d ) 是p 点和0 点的距离，比如选择欧氏距离如图4 2 是模型的一个切面，不同颜 色表示不同距离值然后通过检测距离场的“脊点”来获取预选体素即将距离大于给定 阈值的点选取出来作为预选体素连接这些预选体素得到近似的中轴曲面通常预选体 素的数量会很大，接下来是将这些预选体素进行修剪修剪后的体素通常是离散的，母 后将这些点重新连接起来得到曲线骨架连接的方法大多数都用的是最小生成树和最短 路径或者一些其他图论的方法来完成的 图4 2 用颜色表示的三维横型某十切面的距离场 开9 42 ac o l o 州c ds l i c e0 f m e d i s t a n c e f i e l do f a3 ds h a p e 还有其他一些距离场方法用斥力或者用径向基函数来代替距离变换这些距离场方 法利用大量的样本边界计算模型内点，因此对噪声的敏感度稍低然后连接局部极值点 来生成骨架 基于距离场的方法能够准确地提取模型的中轴然而它们在提取任意模型的曲线骨 架时不得不借助额外的技术来修剪中轴 4 2 几何方法 几何方法直接利用多边形网格或者散乱点集 基于拉普拉斯算子的点云骨架提取 4 2 1 v o r o n o i 图 三维网格模型的顶点或者三维散乱点集可以直接产生v o r o n o i 图v o r o n o i 图的边和 面可以用来提取模型的近似中轴对中轴可以用修剪的办法来生成曲线骨架 4 2 2r e e b 图 近十来基于r e e b 图的方法获得了很大的关注r e e b 图定义如下：给定一个定义在紧 致流形m 上的实值函数zf ：m _ r ，r e e b 图是m 酞的商空间定义的等价关系一为： ( x l ，厂( 毛) ) ( 屯，f ( x ：) ) 当且仅当厂( 五) = f ( x 2 ) ， 为和乇属于叫( 而) ) 或者厂- 1 ( 厂( 吃) ) 的同一个连通分支 换句话说，由定义的等价类是f 1 3 f 的水平集的连通分支构成r e e b 图的节点对应于 函数的关键点( 例如，厂梯度为o 的点) ，r e e b 图的边表示了关键点的连接关系 r e e b 图不是曲线骨架，甚至它和原始模型定义在不同的空间中然而可以将r e e b 图嵌入到三维空间中，最终得到曲线骨架如图4 3 图4 3r e e b 图在原始图像空间的嵌入 f i 9 4 3 a ne m b e d d i n go ft h er e e bg r a p hi n t ot h eo r i g i n a li m a g es p a c e 有些基于r e e b 图的方法使用多变量实值函数，如测地函数【h i l a g a 等2 0 0 1 或者调和 函数 a u j a y 等2 0 0 7 1 ，用于特定的应用为了得到曲线骨架，r e e b 图需要在曲面上重采样 来获得更加接近骨架的节点，然后嵌入到几何模型中a u j a y 等人提出了一种调和r e e b 大连理工大学硕士学位论文 图方法，通过解拉普拉斯方程得到调和函数但是他们的方法需要用户显示地指定边界 条件 4 2 3 其他几何方法 这些方法不依赖定义在流形上的函数来生成曲线骨架l i 等人通过边按长度顺序进 行坍塌来获取线段骨架该方法对模型网格的镶嵌( t e s s e l l a t i o n ) 很敏感k a t z 和t a l 通过 分解网格然后连接这些连通子网格来获取骨架 4 3 其他曲线骨架提取方法 还有一些其他的方法不能归于上述两大类方法如2 0 0 7 年s h a f t 等人提出了一种基 于可变模型演化的曲线骨架提取方法，可以用于点云和多边形网格上的曲线骨架提取 基于拉瞢拉斯算子的点云哥絮提取 5 基于拉普拉斯算子的网格处理方法 曲面表示和处理是计算机图形学中十分重要的课题简单地说三维模型的表示方 式很大程度决定了它能用到的技术和应用领域例如比较流行的逐片线性曲面表示( 三 角网格) ，如何显示三角网格，如何研究其拓扑性质等都有直接的方法另一方面三角 网格表示在许多造型需求上显得不够好而且，通常扫描得到的曲面十分复杂经常带 有噪声，这需要如滤踱重采样和压缩等几何处理手段来处理，使得其方便存储和传输 害； 图51 基于拉昔拉斯算于的同格变形例子 f i 9 5 1 s o m ee x a l n p b o f m e s hc i e f o n n m i o nu s i n 9 1 a p a c i a n m “ 5 1拉普拉斯算子和曲面微分表示 在大多数应用中，不可能对一个全矩阵一r 做存储和其他操作，因此我们通常 在网格上定义一个局部算子厂r “这样就可以用稀疏矩阵来表示这个算子( 稀疏矩阵 可以降低存储空间) 拉普拉斯算于也是这样的一个局部微分算子它广泛地用于曲面 逼近，压缩和水印还有交互式的网格处理和插值等与传统的笛卡尔坐标( 绝对坐标) 只能表示点的全局空间位置不同，微分坐标能表示曲面局部的信息如曲面局部的方向、 弯曲程度等因此在曲面上定义保持这些性质的算子，可以用于一些保持细节等的变形 操作 5 1 1 拉普拉斯算子定义 假设。“= ( v f ) 是一个有h 个顶点的三角网格其中r 表示顶点集台表示边 的集合，表示面的纂台对于每个顶点，饿我们用传统笛卡尔坐标表示，记为 v ，= ( ，卫鼻) 首先定义微分坐标( 也叫5 一坐标) 如下： 大连理工大学硕士学位论文 4 。( 班聊，v ，一虿1 ，蒹，v ，= 石1 a i l a ，善，v a 。；而，# ，r n 其中( f ) = ，i ( f ，_ ) 目，d i - - - i ( 圳，叫做顶点i 的度或阶 从笛卡尔坐标到6 一坐标的变换可以写成矩阵形式，即所谓的网格拉普拉斯算子 ( l a p l a c i a no f t h e m e s h ) ，记它为l 将网格看作是一个图g = ( 矿，e ) ，设彳为这个图的邻 接矩阵 = 巍e ， d 是对角矩阵满足d i i = 谚，那么将绝对坐标转为6 一坐标的变换矩阵为 工= i d a 为方便起见，根据矩阵上得到一种对称矩阵形式厶= d l = d - a ， fz i = y ( 厶l = 一1 ，) e 【0 其他 即t v ，= d 4 图5 2 是一个图和它的拉普拉斯矩阵 4q - 1 - 13 1 q q5 - 1 - 1 1 - 1- 1 - 1 一q _ qq 一 4- 11 3 1q 4 - 1 - - 1 q一6 _ 1 _