（计算数学专业论文）一种基于点云的曲面匹配的八叉树算法.pdf

大连理工大学硕士学位论文 摘要 三维形状的匹配，在逆向工程、虚拟现实、医学图像配准、机器人、自动控制、以 及药物分子结构设计等领域有着广泛应用，是计算机图形学中的重要研究课题。 三维形状匹配的关键是曲面的匹配，其基本问题是定义和计算两个曲面( 通常是三 维几何体的表面) 的差异。这一差异完全由曲面的内蕴性质决定，与其它因素无关。例 如，将一个曲面与其经过刚体运动( x f 移和旋转) 后的像相比较，其差异应该为零。曲 面匹配可分为刚性曲面( 无形变) 匹配和弹性曲面( 有形变) 匹配两大类。二者的区别 在于：刚性曲面匹配仅仅将一个曲面与其在刚体运动作用下的像视为相同；弹性曲面匹 配则将曲面在一个包括刚体运动在内的更大的运动群作用下的像视为相同。刚性匹配是 弹性匹配的特例；研究刚性匹配的有效算法，是实现更一般的弹性曲面匹配的基础。曲 面匹配的算法在很大程度上依赖于曲面表示的方法。在计算机图形学中，最为常用的离 散曲面表示，有点云和三角网格两种。三维激光扫描仪获取的原始测量数据就是点云， 它具有结构简单、处理手段灵活多样等优点。 本文的主要工作，是针对基于点云的刚性曲面匹配问题，提出了一种通用的匹配算 法。该算法不需要在被测物体上附加任何参考点或标签点，对待匹配点云的相对位置没 有要求，可以处在空间任意位置上，仅利用曲率估计创建八叉树，再结合s e p m a p 实现点 云的部分匹配和整体匹配。本算法不需要提取特征点，因而也不依赖于曲率的极值。 本文具体结构如下：第一章综述国内外有关曲面匹配的工作，主要是有关特征的研 究；第二章介绍有关点云的基本概念，包括常用的处理方法；第三章是关于八叉树的简 要介绍，这是本文下面提出的新算法中使用的重要工具；第四章提出了新的曲面匹配八 叉树算法并从实验和理论上分析了算法的可行性；在本文的结论中对我们的研究进行 了总结和展望。 关键词：曲面匹配；点云；八叉树；特征 一种基于点云的曲面匹配的 a no c t r e ea l g o r i t h mf o rp o i n t - b a s e ds u r f a c em a t c h i n g a b s t r a c t t h r e ed i m e n s i o n a ls u l f b t ：em a t c h i n gi so fg r e a ti m p o r t a n c ei na v a r i e t yo fa r e a s ，s u c ha s t h e 嘲e n g i n e e r i n g ，t h ev i r t u a lr e a l i t y ，t h em e d i c a li m a g er e g i s t r a t i o n , t h er o b o t , t h e a u t o m a t i cc o n t r o lf i e l d s , a n dm o l e c u l e ss l z u c t u r ed e s i g no fd r u ga n ds oo n , w h i e l ai s 弛 i m p o r t a n tt a s ki nc o m p u t a t i o n a lg e o m e t r y t h ek e yo f t h e3 do b j e c t s m a t c h i n gi st h es u r f a c e sm a t c h i n g w h o s eb a s i cp r o b l e mi st o d e f i n ea n dc o m p u t et h ed i f f e r e n c eo ft h et w os u r f a c e s ( w h i c ha r ea l w a y ss u r f a c e so f3 d g e o m e t r i co b j e c t s ) 1 1 1 ed i f f e r e n c ei sc o m p l e t e l yd e c i d e db yt h ei n h e r e n tq u a l i t y w h i c hi s i n d e p e n d e n to fo t h e rf a c t o r s f o re x a m p l e ，as u r f a c es h o u l db et h es a m ea st h ei m a g et h e s u r f a c ef o r m sb yt r a n s l a t i o na n dr e v o l u t i o n t h es u r f a c em a t c h i n gi n c l u d e st h er i g i ds u r f a c e m a t c h i n ga n dt h ef l e x i b l es u r f a c em a t c h i n g t h e i rd i f f e r e n c ei st h a tt h er i g i ds u r f a l c ei so n l y t h es a m e 越i t si m a g l ei nt h er i g i dm o v e m e n t , b u tt h ef l e x i n es u r f a c ei nl a r g e rm o v e m e n t g r o u p n er i g i di s a i le s p e c i a le x a m p l et ot h ef l e x i b l e t or e s e a r c ht h er i g i ds u r f a c e s m a t c h i n gi st h eb a s i c 勰t h ef l e x i b l es u r f a c e s t h es u r f a c em a t c h i n ga l g o r i t h m sd e p e n do nt h e s u r f a c e se x p r e s s i o nm e t h o d si nal a r g ed e g r e e i nc o m p u t e rg r a p h i c s t h em o s tc o m m o n d i s c r e t es u l f a c e se x p r e s s i o ni n c l u d e st h ep o i n t sc l o u da n dt h ei r i a n g u l a rm e s h n eo r i g i n a l d a t ag o t t e nb yt h e3 ds l ：a n n c ri st h ep o i n t sc l o u d , w h o s es l l u c t u r ei se a s ya n dw h i c hc f l l 3 b e t r e a t e di nk i n d so f m e a m t h em a i nw o r ko ft h ea r t i c l eb r i n g sf o r w a r dau n i v e r s a lm a t c h i n gm e t h o dt dt h er i g i d s u r f a c eb a s e d0 1 1t h ep o i n t sc l o u d 1 1 1 ca l g o r i t h md o n tn e e da n yr e f e r e n c ep o i n t sa n dl a b e l p o i n t si nm e a s u r e do b j e c t sa n di si n d e p e n d e n t0 1 1t h ep o s i t i o n i nt h ea l g o r i t h mt h ep o i n t s c l o u dr e a l i z e sp a r t i a la n dw h o l em a t c h i n gb yt h eo c 1 e eb u i l tb yt h ee s t i m a t i n gt h ec u r v a t t u e a n ds e p m a p n l ea l g o r i t h md o e s n tn e e dt h ec h a r a c t e r , a n ds oi si n d e p e n d e n to ft h e c t n v a t u r ee x t r e m u m j u s tb e c a u s eo f t h e s e ，t h eb o d yo f t h ea r t i c l ei sa sf o l l o w s ： i nt h ef i r s tc h a p t e r , t h ep o p u l a rw o r ki nt h ew o r l di ss u n m a a r i z e d ，m a i n l ya b o u tt h e c h a 瑚l c t c r sr e s e a r c h ； i nt h es e c o n dc h a p t e f ，t h ep o i n t sc l o u dr e s e a r c hi ss u m m a r i z e d , i n c l u d i n gc o m m o n m e t h o d sd e a l i n gw i t ht h ep o i n t s ； i nt h et h i r dc h a p t e r ，t h ei n f o r m a t i o na b o u tt h eo c l a - e ei ss u m m a r i z e d , w h i c hi st h e i m p o r t a n tt o o li no u ra l g o r i t h m ； 一1 ir 大连理工大学硕士学位论文 i nt h ef o u r t hc h a p t e r w eb r i n gf o r w a r da l lo a 慨a l g o r i t h mo ft h es u r f a c em a t c h i n g b a s e do nt h ep o i n t sc l o u d a n dw ea n a l y z et h ea l g o r i t h m sf e a s i b i l i t yf t o mt h ep o i n to ft h e e x p e r i m e n ta n d t h et h e o r y i nt h ef m a l ，t h er e s u l ta n dt h ef u t u r ew o r ka b o u tt h ea l g o r i t h mb r i n g i n gf o r w a r di nt h i s a r t i c l ei sg i v e n k e yw o r d s ：t h es u r f a c em a t c h i n g ；t h ep o i n t sc l o u d ；t h eo c t r e e ；c h a r a c t e r 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：丝堕曰期：兰塑：! ：垒 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作一：至煎 导师签名：盘琏i 筮缝堡芝 年月日 大连理工大学硕士学位论文 1绪论 1 1 曲面匹配问题 本文研究的曲面匹配( s u r f a c em a t c h i n g ) i m 7 题，属于计算几何领域。计算几何是- - f 3 重要的数学学科，与函数逼近、微分方程数值解、算法与数据结构、微分几何、代数几 何、组合数学等紧密相关，其理论成果在c a d c a m c a e ，图像处理，计算机图形学， 科学可视化等许多科学和工程领域都有重要应用。 曲面匹配的基本问题是定义和计算两个曲面( 通常是三维几何体的表面) 的差异。 这一差异完全由曲面的内蕴性质决定，与其它因素无关。该问题的数学模型可以表述如 下：设g 是一个给定的三维欧氏空间的变换群，d 表示集合问的某种距离f 一般是 h a u s d o r f f 距离或m i n k o w s k y 距离) ，则曲面丘占之间的差异占定义为 占( 丘固= m i n 以丘及磅) l ，g ) 这是一个优化问题。依据变换群g 的不同，曲面匹配可分为刚性曲面( 无形变) 匹配和 弹性曲面( 有形交) 匹配两大类。刚性曲面匹配问题中，g 为刚体运动群；而在弹性曲 面匹配问题中，g 是一个包括刚体运动在内的更大的运动群。刚性匹配是弹性匹配的特 例；研究刚性匹配的有效算法，是实现更一般的弹性曲面匹配的基础。 依据对结果的不同形式要求，曲面匹配又可以分为以下几类问题。 ( 1 ) 曲面校准( s u r f a c ea l i g m n e n t ) 。该问题要求找到一个变换。使得经过该变换之 后，曲面与曲面口之间的距离最小。 ( 2 ) 曲面比较( s u r f a c ec o m p a r i s o n ) 。该问题要求判定两个曲面的差异是否大于某一 给定的阈值。 ( 3 1 曲面检索( s u r f a c er e t r i e v a l ) 。该问题是给定一个模型曲面彳和一个由多个曲面 组成的曲面数据库，要求从该数据库中找出最接近4 的曲面数据成员。 ( 4 ) 曲面注册( s u r f a r c e r e g i s 捌o n ) 。该问题要求判定曲面么是否与曲面县有能够重 合的公共部分；如果有公共部分，求出使得公共部分能够重合的变换。 由以上曲面匹配闯题的表述可以看出，求解以上四类问题的基础是曲面校准，即在 运动群g 中，找出变换乃使得以丘“甸) 达到最小值。这方面早期的研究工作，以 h e a d - i n - h a t 和i c p 方法为代表，依靠交互手段，为变换，人为指定一个初值，然后 用迭代方法近似地求出最优值。这两种方法最早用于三维医学成像，其中i c p 方法取得 了巨大的成功，目前已经发展出多种改进形式，仍然广泛应用于解决各种实际问题。但 是，依赖人工干预，不能实现整个过程的自动处理，是i c p 方法的根本缺陷。而且由于 一种基于点云的曲面匹配的 所涉及的优化问题具有非线性，如果初值选取得不够好，使用i c p 方法就无法得出正确 的结果。 针对i c p 方法的局限，近年来产生了各种解决方案。其中多数研究认为，将曲面作 为三维空间中的( 连续或离散的) 点集直接进行比较，其计算复杂度太高。必须寻求其 它形式的描述曲面部分性质的、运动群g 作用下的不变量，用比较这些不变量之间的差 异，取代对完整的曲面表示进行比较。这类曲面的不变量统称为描述符( d e s c r i p t o r ) 。 已经提出的描述符不下几十种，可以大致分为几何的、拓扑的、分析的、视图的和统计 的等类型。 ( 1 ) 几何描述符是提取曲面的一些运动群g 作用下的几何不变量，通过比较这些运 动不变量的差异，来进行曲面的比较。常用的有基于曲率的描述符( c u r v a t u r eb a s e d d e s c r i p t o r ) 、基于壳的描述符( h u l lb a s e dd e s c r i p t o r ) 、旋转图像( s p i ni m a g e s ) 、 形状上下文( s h a p ec o n t e x t ) 等。 ( 2 ) 拓扑描述符是引入一些拓扑工具，得到曲面的运动不变量，如阿尔法形状( a - s h a p e ) 、r e e b 图( r e e bg r a p h ) 、骨架图( s k e l e t o ng r a p h ) 等。 ( 3 ) 分析描述符是利用时一频变换等分析工具，提取曲面的不变量，如球面调和 ( s p h e r i c a lh a r m o n i c s ) 、f o u r i e r 系数、小波系数( w a v e l e tc o e f f i c i e n t s ) 等。 ( 4 ) 视图描述符是采集曲面在不同平面上的投影，利用图像处理中的一些工具提取 曲面的不变量，如光照场( l i g h tf i e l d ) 、震动匹配( s h o c km a t c h i n g ) 、二维查询界面( 2 d q u e r yi n t e r f a c e ) 等。 ( 5 ) 统计描述符是采用概率分布、矩等统计量作为比较曲面差异的基础，如曲面随 机点概率分布( p r o b a b i l i t yd i s t r i b u t i o no fr a n d o ms u r f a c ep o i n t s ) 、z e r n i k e 描述 符( z e r n i k ed e s c r i p t o r ) 等。 描述符的引入，极大地丰富了解决曲面匹配问题的技术手段，实质性提高了曲面匹 配计算机算法的智能化水平。在曲面检索、曲面分类与识别等领域中，问题本身往往不 要求精确计算出曲面间的差异量，而只是要对这些量进行大致的估计或者排序。通过选 择适当的描述符，可以使这些问题得到显著的简化。 对于需要精确计算两个曲面差异量的情形，如前所见，问题的关键在于找出相应的 最优变换。在初值良好的条件下，i c p 方法对求解这一问题是有效的。因此，近年来国 际上围绕初值的自动计算，进行了大量的研究。基于曲面整体信息的拓扑、分析、视图、 统计以及部分几何描述符，对确定具体的变换基本上没有用处。但是，另一部分基于局 部信息的几何描述符，可以有效地用于确定两个曲面上少数点之间的对应关系，进而给 一2 一 大连理工大学硕士学位论文 出所求交换的良好估计，作为i c p 算法的初值。目前，通过局部曲面描述符寻找初始变 换的方法，已经成为研究曲面校准、比较和注册问题的主要途径。 不周曲面匹配方法的评价。主要考察计算效率，区分能力，以及是否可以用于部分 匹配等三个方面。这主要取决于采用的描述符。就原理相同或相似的描述符而言，描述 符越复杂，信息量越大，则区分能力越强，相应地，计算效率越低；反之，计算效率较 高的描述符，通常都比较简单，区分不同曲面的能力较弱。就信息量相近的描述符而言， 基于整体信息的描述符，区分能力较强，计算效率较高，但不具备部分匹配的能力：反 之，基于局部信息的描述符，能够用于部分匹配，但计算效率和区分能力较差。就基于 不同原理的描述符丽言，基于统计的和分析的描述符计算效率较高，但区分能力较差， 且一般不适用于部分匹配；基于拓扑的描述符，与适当的分割算法配合使用，能够用于 部分匹配，但计算效率不高，区分能力也有限：基于视图的描述符能够达到很高的区分 能力，但计算复杂度高，也难以用于部分匹配；基于几何的描述符比较灵活，以上各种 优缺点的组合都有出现。 1 2 基于局部信息的几何描述符与曲面的特征 基于局部信息的几何描述符，因为具有计算效率高又可用于部分匹配的优点，受到 普遍重视和广泛研究。这类描述符在计算几何的其它分支，如网格生成，曲面分割，曲 面重建等问题中都有应用，般称为曲面的几何特征。 在曲面重建中，特征的检测和重建是一个很重要的预处理步骤，通过这些特征的重 建可以将原阆题分解为一些光滑子区域的重建问题另外特征的重建可以保证在特征线 附近有足够的采样密度，从而保证重建后的物体不会丢失一些重要的几何特征 在网格处理中，特征部分标识了要被处理的目标区域或者是需要在处理过程中保持 的区域如在网格编辑中，被编辑的通常是曲面的特征在网格变形中，两个相邻网格 之间的特征需要对应起来在网格简化1 1 和网格压缩中，一个主要的目标就是使用尽 可能少的数据来表示霹格的特征在对一个菲规则网格进行重网格化5 8 ，从丽使其具 有细分连接关系时，原网格的特征也要尽量保持在曲面分割川中，希望分割线沿着 尖锐的褶皱和尖点，从而得到的每片子曲面上的点的曲率变化不大另外沿着特征割开 还可以获得物体的一些有意义的部分，以便应用在变形和动画制作上在曲面降噪嗍中， 通常在滤掉噪声的同时不可避免的会使得该曲面丢失一些尖锐特征因此如何准确地识 别特征，就显得非常重要 特征在许多方面都有应用，但是具体什么是特征，仍然没有一个广为接受的定义这 主要是由于：特征的定义是与具体应用相关的，使用的目的不同，相应的特征定义也就 一种基于点云的曲面匹配的 不同对于不封闭曲面，其边界可以视为特征。对封闭曲面而言，曲面内部三维区域的 体积可以视为一个特征。对于任何曲面，它的表面积都可以视为特征。三维离散曲面的 边界曲率，顶点曲率，网格面曲率，顶点数量、网格面面积等都可作为特征。另外还有 三维曲面的轮廓特征，它主要是指顶点和网格的分布特征。 还有一些拓扑特征，如分支，连通性等。此外，根据曲面是否可定向，可以将曲面 分为可定向曲面和非可定向曲面对于闭曲面又可以根据曲面的亏格数来分类因此， 曲面是否可定向和闭曲面的亏格都是曲面的特征在三维检索中，曲面的r e e b 图“”和中 轴( m e d i a la x i s ) 都可以使用一些二维曲线来揭示三维曲面的拓扑结构，并被应用在曲 面匹配和检索”中，它们也是曲面的特征这些都是曲面的拓扑特征 拓扑特征虽然揭示了曲面的一些重要性质，但是这些性质一般都属于曲面的整体性 质。而在实际应用中使用更多的还是曲面的局部性质，即几何特征同样几何特征也没 有一个统一的定义因为同其它特征( 比如纹理特征) 一样，使用入眼来判断几何特征很 容易，但是它们的自动提取却不是很简单的事一方面特征的刻画要比识别困难得多： 即使特征很模糊，人眼仍然可以很容易识别出它们，然而在使用计算机对它们进行识别 之前必须给它们一个数学上的精确定义；另一方面由于人为噪声的引入，很容易把噪声 错误地识别为特征，或者相反，这对比较稀疏的网格尤其明显h u b e l i 和g r o s s 在l l 川中 给出了网格特征( m e s hf e a t u r e ) 的定义如下：网格特征是能够描述网格的重要性质的分 段光滑的曲线该定义除了限定特征是一些曲线以外没有给出任何其它信息 几何特征是与连续性密切相关的。一般不满足c o 连续的区域只有边界，因此边界 是一种特征不满足c 1 连续的区域形成褶皱或角点对于离散表示的曲面，比如常用的三 角网格曲面，需要通过取阈值的方法确定褶皱或角点。目前使用的曲线特征，绝大多数 指的都是褶皱。根据局部的凸凹性又可以分为脊线( r i d g e ) 和谷线( v a l l e y ) 最近l a i 等 人在1 中又给出了其它两类特征：桥( b r i d g e ) 和隧道( t u n n e l ) ，不过它们的应用不多， 该论文也没有对它们进行更多的讨论 j i a o 等人在”习中通过与特征点相连的特征曲线条数，将特征点分为四类：尖点 ( t i p ) ，终点( t e r m i n u s ) ，转点( t u r n ) 和交叉点( j u n c t i o n ) 与它们相连的特征曲线条 数分别为：0 ，1 ，2 ，2 条以上，如图1 1 此外m l ，1 1 3 1 4 1 中则简单地将曲率较大的点，边或三角形作为特征 大连理工大学硕士学位论文 全分胁畚 图1 1 特征点的类型 f i g i 1t h et y p e so ft h ec h a r a c t e rp o i n t s 一5 一种基于点云的曲面匹配的 2 点云概述 随着三维扫描设备的广泛应用，点几何元素受到越来越多的重视。对于复杂结构的 模型，使用点集表示比三角网格更能有效地表示和显示该几何形体f 1 6 】。本文以没有任何 拓扑信息的散乱点集为处理对象来匹配曲面。要想很好的利用点云来进行匹配等需要对 点云的相关概念和点云的梗关计算等进彳亍了解，本章从这些角度对点云进行了综述和研 究。 2 1 点云相关概念 1 ) 采样密度【”】： 假定p 是曲面集s 上一个离散点集，如果以曲面集s 上任一点x 为球心，占为半径 的球面内至少有一个采样点，并且6 q ，则r t l + + ，若肌厂 ) ( ，p ) 为s 的函数) ，则说b o x 中包含的曲面点在同一个球上。 大连理工丈学硕士学位论文 4 1 3 节点： 我们让一个b o x 对应个节点，当b o x 包含有点云中的点时，这个节点记为黑色， 否则记为白色。节点包含信息：从该b o x 中取的n 个点的平均曲率和重心坐标，该节点 是否有子节点的标志( 下文节点分解问题将解释有无子节点的问题) ，是否会找到匹配 节点的标记f l a g ，初始值f l a g = 0 ，找到匹配对象时f l a g = l 。这个节点也就包含了它对应 的b o x 所含的曲面的信息。 树节点的数据结构描述： s t r u c tt r 捌妯d c n o a t x ，y ，z ； 包围盒中所含点云中点的重心 f l o a t l ：边长 s t r u c tt r e e n o d e f 矾磁： 父节点指针 s t r u c tt r a n c e + c h i l d 【8 】；予节点指针 s t r u c t p o i n 烈o d e + p o i n t ； 包含的数据点的指针 s t r i n gc o d e ； ，本节点编码，八进制 i n t m d e g本节点在兄弟节点中的序号 b o o ll e a 是否叶子节点 b o o l 丑a g ；，黾否能找到匹配对象 4 1 4 节点的分解： 若节点对应的b o x 中随机取出的n 个点不在同一个球面上时，我们把该节点对应的 b o x 分解成八个大小相同的子立方体，八分后所褥的小盒子对应节点我们记为该节点的 子节点，注意子节点我们给它们如下排序。我们从这八个小b o x 中每个b o x 都进行下列 操作：随机取出n 个点，计算这n 个点的平均曲率，以平均曲率的大小来将这些子节点 从左到右进行排序，没点云中点的小盒子都放到最后，按原位置从上到下从前到后从左 到右的顺序排列无点的小盒子。 一种基于点云的曲面匹配的 图4 2包围盒空间分割 f i 9 4 2 t h ed i v i s i o i lt ot h es p a c 2b yb o x 4 2 三维模型八叉树的建立 对三维模型进行从整体到局部的匹配是一个渐进匹配过程，八叉树是三维模型从整 体到局部的分解，根部节点是八叉树的第1 层，用于三维模型整体相似性比较，层次高 的节点的比较表示局部细节的比较，这样通过八叉树可以对三维模型从整体到局部进行 匹配；此外，最终八叉树匹配结果与坐标系无关。 八叉树的建立包括三维模型预处理，节点信息值的计算，包围盒最小边长的确定和 建树四部分。 4 2 。1 三维模型预处理 三维模型b o x 大小的统一化 将两个匹配曲面a ，b 的点云分别放入它们各自的b o x ，b o x a 的边长记为d 。，b o x b 的边长记为d 。不妨设d 。d 。，向四面八方同时延伸放大b o x b 的边长，延伸过程中保 持b o x b 的中心不变t 使d = d b 。 4 2 2 节点信息值的计算 曲率我们采用文献f 1 8 】中采用的方法计算。重心坐标等的计算很显然。 4 2 3 包围盒最小边长的确定 为了确定包围盒分割结束的一个条件，我们需要计算包围盒的最小边长厶。 在此我们采用【3 l 】中讲述的方法，设数据集共有n 个点，l 为上面确定的包围盒的 边长。设定每m 个点划分为一个子域，边长为z 。 藉精露紫 大连理工大学硕士学位论文 对于每个子域，构造一个m x m 的距离矩阵d ，元素d ( i ，) 代表第i 个点到第j 个点 的距离，则矩阵d 是个对角线为0 的对称矩阵。这样仅仅需要计算c 三个距离求得上 ( 或下) 三角矩阵，就可以求得此子域的最小间距t 。 考虑到域分割后的边界属性，我们给每个子域补充一个盯，令0 - = l 。，使得子域的 边长变成z + 盯。 4 2 4 改进的八叉树的构建步骤 本算法与一般的八叉树楣比，多了一个约束条件，将八叉树的节点数大大减少，且 对八叉树子节点间进行了排序，从这两方面提高了曲面的匹配效率。 步骤一将预处理后的点云放到它们所属的b o x 中。 步骤二分割节点 随机的从c ( c 为预处理后阿焦云a 或b ) 的b o x 中取n 个点，看这n 个点是否在同、 一球面上，同时计算这n 个点的重心坐标，根节点上记录这n 个点的平均越率，这n 个 点的重心坐标。若这n 个点在同一球面上，则点云c 表示的是一个球面，树只有一个根 节点；若不在同一球面上将根节点分解，将节点依次分解下去，一直分解到节点对应b o x 包含曲面都是球面或b o x 边长小于l ；。为止，这样我们就构成了如下图所示的八叉树。 1 21 5髓 图4 3 八叉树 f i 9 4 3o c t r e e 步骤三采用论文【3 s 1 中方法给节点编码 对于一个2 ”x 2 “x 2 “的正方体包围盒空间进行如上所示的八等分的划分，则可以利 用0 到7 八进制编码序号的特点，将任一个节点的位置与一个八进制数唯一对应，即 q = g n 1 8 ”- 1 + 目0 2 8 ”一2 + + 吼8 + q 0 8 0 其中，q j 为八进制，吼e i o ，7 】，f o ，l ，n - i 。吼表示该节点在其兄弟节点之间 的序号：一而g 。表示吼节点的父节点在其同胞兄弟间的序号。这样，从g 。到g ，完整地 一种基于点云的曲面匹配的 表示出八叉树中的每个叶子节点到树根的路径。对于如图三中的八叉树，最低层“黑体” 节点的编码为：( 1 2 ，1 5 ，6 0 ，6 1 ，6 6 ) 。 这样构建出八叉树，实际上用平面和球面逼近出原曲面。 4 3 八叉树的匹配 4 3 1 s e p m a p 类似于文献p 7 】中方法我们建立s e p m a p 。对于一个节点的八个子节点构成的集合找 们记为g = k 。= ( 弘r t ，) ，i = 1 8 j ，( 其中。p 为各个子节点对应的b o x 中随机取的n 个 点的重心坐标，疗。为p 点法线) 点集g 中第一个子节点g l 的s e p m a p 为 m = h = p ，妒，r ) j ，j = l 7 其中r a 用下面的计算： f o r g j g ，岛2 ( g ，) ，_ ，1 1 d e f i n ev - - t h ev e c t o rp q ， 2 c a l c u l a t e ( 0 ，r ) a sf o l l o w s ，s f i g 4 ( a ) 目硝e a n g l e b e t w e e nt i p a n d v ( b )矿= t h e a n g l e b e t w e e n a n d v ( c ) f - - t h el e n g t ho f v ( t h ed i s t a n c eb e t w e e npa n dq ) 3 r e c o r dr a = p ，) i n m 大连理工大学硕士学位论文 图4 4 点p ，q 的d e p m a p 的计算 f i 9 4 4t h e c a l c u l a t i o n o f a s e p m a p m p l em = 够，丸r ) o f t w o o r l c n w a p o i n t s ( p , n p ) a n d ( q ，拧q ) 4 3 2 s e p g a p 匹配 假设m ，m 7 两个节点的八个子节点问的关系( 这儿指的节点都在本文建的八叉树 上) 已由上面说的s e p g a p 表示出， m = 研，= ( 口，妒，r ) ，= 2 8 m 7 = 坍j = ( 矽7 ，7 ，r7 ) ，= 2 - - 8 ) 现在来匹配肘m 7 两个节点： f o r ( 1 = 2 ；i 审8 ；l + 矿( 巧一吒，f f ) & l ，6 9 ，) f | 6 b u m + + ： i f ( n u m 一7 1 p r i n t f ( ”m ，m 7 是匹配的”) 4 3 3 八叉树的匹配 构建三维模型的八叉树后，根据八叉树的比较来匹配三维模型。八叉树从根节点到 叶子节点代表了三维模型从整体到局部的特征，因此八叉树的匹配体现了三维模型从整 体到局部的匹配。八叉树的匹配包括父节点间曲率的比较，子节点问曲率的比较，子节 点问s e p m a p 的比较。 从两个根节点间的比较开始，依次比较到两个节点相匹配或到叶节点为止。 当两个父节点曲率相同时进行步骤l ，不同时进行步骤2 一种基于点云的曲面匹配的 步骤1 ：当两个父节点曲率差小于最，即进行这两个节点下的八个子节点间的比较 ( 由上面建树过程我们知这时八个子节点已按曲率由大到小将子节点排列好) ，两棵树 的比较已相等的父节点的八个子节点曲率值分别记为a i , a ：，a g ； 6 l ，6 2 ，6 8 时，计算 t0 l a , - b , i 若| 口l 一包l 6 1 ，再对这两组子节点用s e p m a p 匹配的方法看其是否匹配，若 f 。lt - i 在s e p m a p 影射下仍是匹配的，则说两个父节点对应的b o x 中所含点表示的曲面是匹配 的，f l a g = l 。 步骤2 ：当曲率不等时仍旧进行两个节点的子节点间的比较，若子节点间节点出现 相等的，进行步骤1 ，若仍不等，继续执行步骤2 。 这样比较到最后f l a g = l 的节点对应的b o x 都找到了匹配对象。 4 3 4 数值实验 下面采用对应于二维情形的四叉树方法，进行曲线匹配。 实验一匹配 o ，万2 】上的由十个点构成的s i n ( x ) 和c o s ( x ) 图像。如图4 5 。 图4 5 【o ，z r 2 】上的由十个点构成的正弦和余弦函数图像 f i 9 4 5t h ei m a g eo fs i n e a n dc o s i n ei n 0 ，石2 】b y1 0p o i n t s 大连理工大学硕士学位论文 经实验匹配这十个点，实验结果，这两个图像是完全匹配的。当点数较少时我们将 所有点参加匹配即可。 实验二匹配 0 3 万4 】上的由十个点构成的s i n ( x ) 弄 d r r 4 , 3 1 r 4 1 上的由十个点构成的 c o s ( x ) 图像。如图六。 图4 6 由十个点构成的 o ，3 y r 4 f _ i e 弦和p 4 ，3 万4 】上的余弦函数图像 f i 9 4 6 t h es i n e i 眦g e i n 【o , 3 ，r 4 】a n d t h e c o s i n e i m a g e i np 4 ，3 万4 】b y1 0 p o i n t s 最后实验结果得p 4 ，万2 】与p 2 ，3 石4 】上的余弦函数图像均与【o ，万4 】部分的正 弦函数图像相同。 一种基于点云的曲面匹配的 结论与展望 对三维模型从整体到局部进行匹配可以较好的匹配曲面，本文基于这种思想，通过 对三维模型进行递归分解：同时计算分解部分的平均曲率，获得八又树。理论上来讲， 这样生成的八叉树可以很好的从整体到局部地匹配曲面，匹配同坐标轴的选取无关，是 平移和旋转不变量，不是放缩不变量。本匹配算法理论上只要是相同部分就能匹配出来， 相匹配的部分可能是曲面的几个局部相匹配。 我们在m a t l a b 环境下用本算法实现了对 o ，筇2 上的正余弦函数的匹配和 【0 ，3 万4 】上的s i n ( x ) 与防4 ，3 z 4 】的c o x ) 图像间的匹配。 实验结果表明，本文提出的八叉树存储和匹配算法能够较好地匹配曲线和曲面。概括 起来。本文提出的算法具有以下特点： ( 1 ) 在三维匹配过程中使用八叉树算法存储和匹配图形顶点。 ( 2 ) 本文算法扩大了匹配算法的使用范围，使匹配不再受曲面特征的限制，不再受 曲率极值限制，既能进行整体匹配也能进行局部匹配。 ( 3 ) 算法的局限性是：算法复杂度较高，八叉树的所有节点数记为n 的话，复杂度 是0 ( n ! ) ；并且匹配成功的概率跟极大似然估计有关；八叉树的表示精度取决于空间分 辨率，它只能是近似地表示空间物体，从而只是近似的匹配曲面；占用的存储空间较大， 模型生成依赖其它表示法( 如三维数组) 。 综上所述，如何实质性地改进本文提出算法的计算效率，建立次数较低的多项式时 间算法，是今后的研究课题。 蕉里三查堂堕主兰垡堡塞 参考文献 i k o u k iw a t a n a b e a l e x a n d e rg b e l y a e v d e t e c t i o no fs a l i e n tc u r v a t u r ef e a t u r e s o n p o l y g o n a ls u r f a c e s c o m p u t e rg r a p h i c sf o r u m2 0 0 1 ，2 0 ( 3 ) ：3 8 5 3 9 2 一一 2 s y o s h i z a w a ，a b e l y a e v ，h p s e i d e l f a s ta n dr o b u s td e t e c t i o no fc r e s tl i n e so n m e s h e s i n ：p r o c o f 榭s y m p o s i u mo ns o l i da n dp b y s i c a lm o d e l i n g 。2 0 0 5 ：2 2 7 屹3 2 c 3 a l l i e z 。p ，m e y e r ，l l ，d e s b r u n ，m i n t e r a c t i v eg e o m e t r yr e m e s h i n g i n ：p r o c e e d i n g so f a c ms i g g r a p l l2 0 0 2 腰t r a n s g r a p h 2 0 0 2 ，2 1 ( 3 ) ：3 4 7 3 5 4 【4 a 1l i e z ，p ，d ev e r d i 6 r e ，e c ，d e v i l l e r s ，0 e ta 1 i s o t r o p i cs u r f a c er e m e s h i n g i n ： p r o c e e d i n g so fs h a p em o d e l i n gi n t e r n a t i o n a l ，2 0 0 3 ：4 9 5 8 e 5 s d o n g ，s k i r c h e r ，m g a r l a n d h a r m o n i cf u n c t i o n sf o rq u a d r i l a t e r a lr e m e s h i n go f a r b i t r a r ym a n i f o i d s c o m p u t e ra i d e dg e o m e t r i cd e s i g n 2 0 0 5 2 2 ：3 9 2 4 2 3 6 s g e o r g i o sa n d f g e r a l d c r e s tl i n e sf o rs u r f a c es e g m e n t a t i o na n df l a t t e n i n g i e e e t r a n s a c t i o n so nv i s u a 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 4 ，1 0 ( 5 ) ： 5 3 6 - 5 4 4 e 7 h y a m a u c h i ，s g u m h o l d ，兄z a y e re ta 1 m e s hs e g m e n t a t i o nd r