（交通信息工程及控制专业论文）点模型的降噪与三维重建算法研究.pdf

西南交通大学博士研究生学位论文第1 页 摘要 由于工业设计、航天模拟、医学辅助诊断、影视娱乐等应用需求的推动， 关于三维数据获取和数字几何处理技术的研究越来越受到学者们的关注。近 几年来，随着三维模型获取的软硬件技术迅速发展，人们可以通过多种数据 采样方法来获取现实物体的计算机表示。这种通过逆向工程来获取的三维数 据主要包括c t ( 计算机断层成像) 数据、m r i ( 核磁共振成像) 数据以及三 维非规则点模型和网格模型数据等。和网格模型相比，点元不仅结构简单， 易于操作，并且不用存储点与点之间的拓扑连接关系，适合表示如雕像、头 发等几何形状和表面特征复杂且不规则的物体。然而即便是高保真的三维扫 描设备，获取的点云数据也会受到噪声的污染，所以在对点模型进一步操作 之前必须进行降噪处理。点云数据的隐式曲面重建由于不需要考虑采样点之 间的拓扑关系，并能方便地重建出复杂的模型，使其成为求反工程和科学可 视化领域的一种重要方法，因此，如何快速、准确地计算出点云数据的隐式 曲面成为了研究的热点问题。隐式曲面的可视化已得到广泛研究，但至今没 有一种有效的方法，绝大多数都采用多边形网格化采样的绘制方法，这又重 新引入了大量的拓扑约束。 本文以点模型为研究对象，在点模型的降噪、隐式曲面重建和隐式曲面 绘制三个方面进行了深入研究并提出了一些新的算法，主要内容包括： 1 ) 为了更好地去除噪声并保持模型的突出特征，提出了点模型多边滤 波器降噪算法，该算法充分考虑了模型表面的法向量、曲率等内蕴 几何量和噪声之间的关系。首先通过自适应选取最优邻域控制函数， 将滤波窗口限制在采样点法向量相近的区域，以防止滤波后模型的 收缩和过光顾；然后运用协方差矩阵分析的方法，在最优邻域内计 算出各采样点的法向量和曲率；最后以采样点滤波参考平面为基准， 分别平滑采样点法向量和空间位置，即先对采样点法向量进行多边 平滑，然后根据新的法向量多边平滑输出各采样点的位置偏移量， 最后在法向方向上移动该采样点，以达到降噪的目的。实验结果表 明，多边滤波器不仅能有效地去除噪声，同时还能较好地保持点模 型表面的几何特征。 2 1 针对噪声点云数据提出了一种基于b a y e s i a n 统计理论的降噪算法。 算法的主要思想是在可能的重建概率空间上寻找最大后验概率。首 第1 | 页西南交通大学博士研究生学位论文 先，分别计算测量过程数学模型和曲面先验概率模型；其次，通过 共轭梯度优化算法确定每一个点的最大后验位置；最后，应用s u r f a c e s p l a t t i n g 算法绘制点模型。本文的先验概率模型不仅能去除扫描点 云数据的噪声，同时还能增强曲面的细节特征。 3 ) 针对三维扫描获取的带噪声和离群点的点云数据，提出了一种隐式 曲面重建算法。首先，引入一种基于均值漂移的聚类优化算子，通 过移动每一个采样点到核密度函数的局部最大值点来限制各种幅度 的噪声并剔除离群点噪声；其次，用自适应的八叉树空间划分方法 将聚类优化后的采样点数据分成小的子域；最后，在每个子域内计 算径向基局部形状函数，并用单位分解法将每个局部函数进行加权 混合来逼近模型的全局函数。 4 ) 提出了一种点云数据隐式曲面重建的快速算法。通过改进再生核粒 子逼近法，提出了最小二乘再生核法，并与单位分解法有机结合， 应用到点模型的隐式曲面重建算法中，改善了重建效率。此外，为 了进一步减小计算开销，还用另外三种方法加快重建速度：一是v s 树分层的空间划分方法将全局域划分为小的子域，二是根据每个采 样点的重要性评价函数值迭代简化输入的点云数据，三是利用g p u 上的稀疏矩阵求解器将局部形状函数的求解过程移植到g p u 上完 成。 5 ) 提出了一种新的基于粒子系统和s u r f a c es p l a t t i n g 的隐式曲面可视化 算法。首先，基于平行线束的初始化方法在隐式模型表面找到均匀 分布的采样点，避免了原来粒子系统中的分割一死亡过程；第二，用 共轭梯度法替代原来粒子系统中的梯度下降法作为优化算法，将每 一个椭圆粒子累进移动到低能量状态，避免了较长的收敛时间和围 绕最小值的摆动现象；第三，用贪婪选择法选择能够覆盖整个曲面 的且不产生空洞的活动子集；最后，松弛过程进一步改善依赖曲率 的各向异性粒子采样。本文的粒子专门为基于s p l a t s 的表示法而设 计，可以直接转换为椭圆s p l a t s 而不需要任何改动。因此，本算法 可以快速地、高质量地绘制出复杂隐式曲面模型。 关键词：点模型，降噪，多边滤波器，隐式曲面重建，s u r f a c es p l a t t i n g 西南交通大学博士研究生学位论文第l | l 页 a b s t r a c t w i t ht h ed e m a n d so fv a r i o u sa p p l i c a t i o nf i e l d ss u c ha si n d u s t r i a l d e s i g n ， a v i a t i o ns i m u l a t i o n ，c o m p u t e r a i d e dm e d i c a ld i a g n o s i s ，e n t e r t a i n m e n ta n ds oo n ， s t u d i e so n3 dd a t aa c q u i s i t i o n ，p r o c e s s i n ga n dv i s u a l i z a t i o na r eb e c o m i n gm o r e a n dm o r ei m p o r t a n ta n da t t r a c t i v ea m o n gt h ec o m p u t e rg r a p h i c sr e s e a r c h e r s i n r e c e n ty e a r s ，w i t hr a p i dd e v e l o p m e n ta n dg r e a ti m p r o v e m e n ti nt h eh a r d w a r ea n d s o f t w a r ef o ra c q u i r i n g3 dd a t a ，p e o p l em a yo b t a i nr a wd a t ar e p r e s e n t a t i o n so f r e a lo b j e c t sw i t hc o m p l e xs h a p ev i aav a r i e t yo fw a y s t h e3 dd a t ao b t a i n e db y r e v e r s e e n g i n e e r i n g a r e m a i n l y c l a s s i f i e di n t oc td a t a ，m r i d a t a ，a n d u n o r g a n i z e d 3 dp o i n t b a s e do rm e s h b a s e d d a t a c o m p a r e dt o m e s h b a s e d m o d e l s ，p o i n tp r i m i t i v e sa r en o to n l ys i m p l ea n de a s yt oo p e r a t e ，b u ta l s on o t n e e dt os t o r ea n yt o p o l o g i c a lc o n n e c t i v i t yi n f o r m a t i o nb e t w e e np o i n t s p o i n t p r i m i t i v e sa r ea l s os u i t a b l ef o rr e p r e s e n t i n gi r r e g u l a rr e a lo b j e c t ss u c ha ss t a t u e a n dh a i re t c ，w h i c hm a yh a v ec o m p l e xg e o m e t r ya n da p p e a r a n c e h o w e v e r , e v e n w i t h3 dh i g hf i d e l i t ys c a n n e r s ，t h eo b t a i n e dp o i n tc l o u dd a t am a yb ep o l l u t e db y v a r i o u sk i n d so fn o i s e t h u s ，d e n o i s i n gi sn e c e s s a r yf o rp o i n t b a s e dm o d e l s b e f o r ef u r t h e rp r o c e s s i n g d u et ot h ec o n v e n i e n c et or e c o n s t r u c t c o m p l e x g e o m e t r ya n dn on e e dt om a n a g et h et o p o l o g yi n f o r m a t i o no fp o i n t s ，i m p l i c i t s u r f a c er e c o n s t r u c t i o nh a sb e c o m ea l li m p o r t a n tt e c h n i q u ei nr e v e r s ee n g i n e e r i n g a n ds c i e n t i f i cv i s u a l i z a t i o n s o ，h o wt o c o m p u t et h ei m p l i c i t f u n c t i o nf r o m s c a t t e r e dp o i n t se f f i c i e n t l ya n da c c u r a t e l yh a sa l s ob e c o m ea ni m p o r t a n tp r o b l e m t h ev i s u a l i z a t i o no fi m p l i c i ts u r f a c eh a sb e e ns t u d i e dw i d e l y , b u tt h e r ea r en o e f f i c i e n tv i s u a l i z a t i o nm e t h o d sb yn o w m o s tr e s e a r c h e r sc o n v e r t i m p l i c i t s u r f a c e si n t op o l y g o n a lm e s h e s ，w h i c hi n h e r e n t l yr e i n t r o d u c e dh e a v yt o p o l o g i c a l c o n s t r a i n t s f o c u s e do np o i n t b a s e dm o d e l s ，t h e d e n o i s i n g f o r p o i n t b a s e dm o d e l s ， i m p l i c i ts u r f a c e sr e c o n s t r u c t i o nf r o mp o i n tc l o u d sa n dv i s u a l i z a t i o no fi m p l i c i t s u r f a c e sa r es t u d i e da n dan u m b e ro fn o v e la l g o r i t h m sa r ep r o p o s e di nt h i s d i s s e r t a t i o n t h em a i nc o n t r i b u t i o n si n c l u d e ： 1 ) i no r d e rt od e n o i s ee f f i c i e n t l ya n dp r e s e r v et h es h a r pf e a t u r e so ft h e 第lv 页西南交通大学博士研究生学位论文 m o d e l s ，ad e n o i s i n ga l g o r i t h mo fam u l t i l a t e r a lf i l t e rf o rp o i n t s a m p l e d m o d e l si sp r e s e n t e d t h ea l g o r i t h mt a k e si n t oa c c o u n tt h er e l a t i o n s h i p b e t w e e nn o i s ea n du n d e r l y i n gg e o m e t r i ci n f o r m a t i o n s u c ha sn o r m a l a n dc u r v a t u r e f i r s t ，b yc h o o s i n gac o n t r o lf u n c t i o nf o ral o c a la d a p t i v e o p t i m a ln e i g h b o r h o o d ，t h ef i l t e rw i n d o wi ss e ti nt h er e g i o nw i t hs i m i l a r n o r m a l st oa v o i dt h ep r o b l e mo fs h r i n k a g ea n do v e r - s m o o t h i n g s e c o n d ， n o r m a l sa n dc u r v a t u r e so fs a m p l i n gp o i n t si nt h eo p t i m a ln e i g h b o r h o o d a r ee s t i m a t e db yu s i n gc o v a r i a n c em a t r i xa n a l y s i s t h i r d ，b a s e do nt h e f i l t e rr e f e r e n c e p l a n e ，n o r m a l sa n dp o s i t i o n s o fs u r f a c e p o i n t s a r e s m o o t h e dr e s p e c t i v e l y , i e ，t h en o r m a l so fs u r f a c ep o i n t sa r ec a l c u l a t e d f i r s t l yb yu s i n gm u l t i l a t e r a lf i l t e r , t h e n ，b ya p p l y i n gm u l t i l a t e r a lf i l t e r a g a i n ，t h ep o s i t i o no f f s e t so fs a m p l i n gp o i n t sa r eo b t a i n e d ，f i n a l l y , e a c h p o i n ti sm o v e di nt h ed i r e c t i o no fn o r m a l sb e i n gs m o o t h e d e x p e r i m e n t s s h o wt h a tt h em u l t i l a t e r a lf i l t e rc a l ln o to n l yd e n o i s ee f f i c i e n t l yb u ta l s o p r e s e r v et h eg e o m e t r i cf e a t u r e so ft h es u r f a c es u c c e s s f u l l y 2 、ad e n o i s i n g a l g o r i t h m f o rn o i s y p o i n t c l o u d sb a s e do nb a y e s i a n s t a t i s t i c si s p r e s e n t e d t h em a i ni d e ai s t op e r f o r mas e a r c hf o ra m a x i m u mo f p o s t e r i o rp r o b a b i l i t y ( m a p ) i n t h e s p a c e o fp o s s i b l e p o s i t i o n s f i r s t ，am a t h e m a t i c a lm o d e lo fn o i s ym e a s u r e m e n tp r o c e s s a n da p r i o ro v e rs u r f a c es h a p e sa r ec o m p u t e dr e s p e c t i v e l y s e c o n d ，a l l a p p r o x i m a t em a p p o s i t i o n f o re a c h p o i n t i sf o u n d b yu s i n g a c o n j u g a t e dg r a d i e n to p t i m i z a t i o nm e t h o d f i n a l l y , t h es u r f a c es p l a t t i n g a l g o r i t h mi sa p p l i e dt or e n d e rt h ed e n o i s e dp o m t b a s e dm o d e l s t h e p r o p o s e dp r i o rc a ns m o o t ha w a yn o i s eo ft h es c a n n e dp o i n tc l o u d sw h i l e e n h a n c i n gv i s i b l es u r f a c ef e a t u r e s 3 ) a na l g o r i t h mf o rr e c o n s t r u c t i n gi m p l i c i ts u r f a c ef r o mp o i n tc l o u d sw i t h n o i s ea n do u t l i e r s a c q u i r e db y3 ds c a n n e r si sp r e s e n t e d i nt h i s d i s s e r t a t i o n f i r s t ，ac l u s t e r i n go p t i m i z a t i o no p e r a t o rb a s e do nm e a n s h i f ts c h e m ei si n t r o d u c e d w h i c hs h i f t se a c hp o i n tt ol o c a lm a x i m u mo f k e r n e ld e n s i t yf u n c t i o n r e s u l t i n gi ns u p p r e s s i o no fn o i s ew i t hd i f f e r e n t a m p l i t u d e sa n dr e m o v a lo fo u t l i e r s s e c o n d ，t h ec l u s t e r e dd a t ap o i n t sa r e 西南交通大学博士研究生学位论文第v 页 d i v i d e di n t os u b d o m a i n su s i n ga l la d a p t i v eo c t r e es u b d i v i s i o nm e t h o d t h i r d ，al o c a lr a d i a lb a s i sf u n c t i o ni sc o n s t r u c t e da te a c ho c t r e el e a fc e l l ， a n dt h e s el o c a ls h a p ef u n c t i o n sa r eb l e n tt o g e t h e rw i t ht h e i ra s s o c i a t e d w e i g h tf u n c t i o n sb yu s i n gap a r t i t i o no fu n i t yt oa p p r o x i m a t et h ee n t i r e g l o b a lf u n c t i o n 4 1af a s t i m p l i c i ts u r f a c er e c o n s t r u c t i o na l g o r i t h mf r o mp o i n tc l o u d si s p r e s e n t e di nt h i sd i s s e r t a t i o n an e wl e a s ts q u a r er e p r o d u c i n gk e r n e l m e t h o di sp r o p o s e db a s e do nr e p r o d u c i n gk e r n e lp a r t i c l ea p p r o x i m a t i o n a n da p p l i e dt oi m p l i c i ts u r f a c er e c o n s t r u c t i o nf r o mp o i n tc l o u d s i tc a n i m p r o v et h er e c o n s t r u c t i o ne f f i c i e n c yb yc o m b i n i n gt h ep a r t i t i o no f u n i t y m o r e o v e r ，i no r d e rt o f u r t h e rd e c r e a s et h ec o m p u t a t i o n a lc o s t ， t h r e em e t h o d sa r eu s e dt os p e e dt h er e c o n s t r u c t i o n f i r s t ，v st r e e s c h e m ei su s e dt os u b d i v i d et h eg l o b a ld o m a i ni n t os u b d o m a i n s s e c o n d ， ac o s tf u n c t i o nd e f i n e df o re a c hp o i n ti su s e dt oi t e r a t i v e l ys i m p l i f yt h e i n p u t p o i n tc l o u d sa c c o r d i n gt o i t sv a l u e s t h i r d ，t h ec o m p u t a t i o no f l o c a ls h a p ef u n c t i o n si st r a n s p l a n t e do nt h eg p ub yas p a r s em a t r i x s o l v e r 5 ) an o v e lv i s u a l i z a t i o na l g o r i t h mf o ri m p l i c i ts u r f a c e sb a s e do np a r t i c l e s y s t e ma n ds u r f a c es p l a t f i n gi sp r e s e n t e d f i r s t ，a na l t e r n a t i v ei n i t i a l t e c h n i q u eb a s e do nb u n d l e so fp a r a l l e ll i n e si su s e dt of i n di n i t i a lp o i n t s t h a ta r ee v e n l yd i s t r i b u t e do nt h es u r f a c e b e c a u s eo fi t sc h a r a c t e r i s t i c s ， t h eu s u a l s p l i t a n d d e a t h c r i t e r i o no fp a r t i c l e s y s t e mi sn o tn e e d e d s e c o n d ，e a c he l l i p t i c a lp a r t i c l ei sm o v e dt o w a r d sap r o g r e s s i v e l yl o w e r e n e r g ys t a t eu s i n gac o n j u g a t eg r a d i e n tm e t h o d ，w h i c hr e p l a c e st h e g r a d i e n t d e s c e n t a sa n o p t i m i z a t i o n m e t h o dt oa v o i dv e r y l o n g c o n v e r g e n c et i m e sa n di r r e c o n c i l a b l eo s c i l l a t i o na r o u n dt h em i n i m u m t h i r d ，ag r e e d ys e l e c t i o ns t r a t e g yi su s e dt oc h o o s eas u b s e to fa c t i v e p a r t i c l e s w h i c hg u a r a n t e eah o l e f r e e a p p r o x i m a t i o n f i n a l l y , a r e l a x a t i o np r o c e s sf u r t h e ri m p r o v e st h ec u r v a t u r ed r i v e na n i s o t r o p i c p a r t i c l es a m p l i n g t h ep r o p o s e de l l i p t i c a lp a r t i c l e s a r e e s p e c i a l l y d e s i g n e df o rs p l a t b a s e dr e p r e s e n t a t i o na n dc a nb ed i r e c t l yc o n v e r t e d 第v l 页西南交通大学博士研究生学位论文 i n t o e l l i p t i c a l s u r f a c e s p l a t s a s r e n d e r i n gp r i m i t i v e s w i t h o u t a n y m o d i f i c a t i o n ，t h u sh i g h p e r f o r m a n c er e n d e r i n go fc o m p l e xi m p l i c i t s u e f a c e sc a l lb eo b t a i n e d k e yw o r d s ：p o i n t b a s e dm o d e l ，d e n o i s i n g ，m u l t i l a t e r a lf i l t e r , i m p l i c i ts u r f a c e r e c o n s t r u c t i o n ，s u r f a c es p l a t t i n g 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文复印件和电 子版，允许论文被查阅和借阅。本人授权西南交通大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书 2 不保密回，适用本授权书 ( 请在以上方框内打“4 ”) 学文论文作者签名：孑刁肇 日期：唧年7 月乒日 f j 指剥雠：访彬 醐：刁年7 月乒日 西南交通大学 学位论文创新性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文研究做出贡献的个人和集 体，均已在文中做了明确的说明。本人完全意识到本声明的法律结果由本人 承担。本文的创新点有以下五个方面： ( 1 ) 改进了双边滤波器算法，提出了点模型多边滤波器降噪算法，该算 法充分考虑了点模型表面的法向量、曲率等内蕴几何量和噪声之间的关系。 第2 章2 3 2 4 节中，具体给出了算法的推导和实验。 ( 2 ) 针对带噪声的点云数据提出了一种基于b a y e s i a n 统计理论的降噪 算法。该算法利用采样点的空间位置场和法向量场，推导出了新的先验概率 模型公式。第3 章3 3 3 5 节给出了具体推导和实验结果，该先验概率模型 不仅能去除扫描点云数据的噪声，同时还能增强曲面的细节特征。 ( 3 ) 针对带噪声的，尤其是离群点噪声较多的散乱点数据，提出一种 基于r b f 的隐式曲面重建算法。用均值漂移聚类算子优化输入点云数据，并 在重建时采用一个曲面偏移点的做法都是首次提出。第4 章4 3 4 5 节具体 实现了该算法并给出了对比实验结果。 ( 4 ) 提出了一种点云数据隐式曲面快速重建算法。通过改进再生核粒 子逼近法，提出了最小二乘再生核法，改善了重建效率。此外，为了进一步 减小计算开销，又采用三种方法加快重建速度：v s 树、简化和g p u 上的稀 疏矩阵求解器。第5 章5 3 5 4 节实现了该算法，并给出了对比实验结果。 ( 5 ) 提出了一种新的基于粒子系统和s p l a t s 绘制的隐式曲面可视化算 法。本文的粒子系统专门为基于s p l a t s 的表示法而设计，可以直接转换为椭 圆s p l a t s 而不需要任何改动。因此，本算法可以快速地、高质量地绘制出复 杂的隐式曲面模型，第6 章6 4 6 6 节给出了具体实现过程和实验结果。 办 学位论文作者签名：。万彩 7 日期：夕咖年月弘日 西南交通大学博士研究生学位论文第1 页 第1 章绪论 早在1 9 8 5 年，l e v o y 等人就提出将点作为基本的绘制图元，但直到本 世纪初才被越来越多的学者所关注。一方面，三维扫描技术和设备的发展， 使得获取任何复杂物体表面的离散表示( 通常是稠密的采样点，称为点云) 成为可能；另一方面，在现实的生产实践中，要求计算机处理的模型越来越 复杂，精度越来越高，而传统的以三角形网格为核心的算法已不能完全满足 要求，因为随着几何体的日益复杂，三角网格的规模不断扩大，一个模型可 能包含多达上百万个三角形，这样不仅存储开销非常大，而且每一个三角形 在屏幕空间的投影可能只占很少几个像素，甚至是在一个像素之内。此外， 随着场景复杂性的增加，细节层次( 1 e v e l o f - d e t a i l ：l o d ) 绘制变得很有必 要，也就是说，离相机近的物体用高分辨率表示，而离相机远的物体用低分 辨率表示，这就会引入分层的数据结构，而三角网格之间的拓扑连接信息非 常不适合空间分层结构。于是，研究者开始怀疑三角网格的表现能力，并着 手寻找新的基本图元，点元正好获得了伟大的复兴。点元不仅结构简单，而 且不需要考虑点与点之间的拓扑连接关系，并可以表示如雕像、头发等表面 细节丰富的几何模型，尤其适合动态变化的场景。诸多研究工作已致力于点 模型的表面降噪、三维重建、造型、编辑以及绘制等，并逐渐发展成为一个 较为完整的学科体系基于点的计算机图形学。 1 1 基于点的计算机图形学 基于点的计算机图形学作为计算机图形学的一个分支学科是在近几年才 逐渐发展完善的。m a r k p a u l y 等人”1 在a c ms i g g r a p h 2 0 0 4 大会期间首次系统 讲授了这门课程，并总结出了点模型的三维造型管线：点云数据获取、点云 数据处理与建模、点云数据的绘制三个阶段，如图1 - 1 所示。首先利用立体 扫描设备对物理对象进行数字化离散采样，得到原始模型的粗糙点云数据( 一 般带有噪声，空洞等) ；然后转化为适当的表示形式，以便于后期处理与造型； 最后，采用合适的绘制方法将模型显示出来。本论文的研究将主要涉及该流 水线的三个内容：降噪、三维重建和绘制。 第2 页西南交通大学博士研究生学位论文 1 2 点模型 1 2 1 点模型的定义 点模型是相对于多边形网格( 通常为三角形) 模型而言的，也称点云曲 面。点模型是一个在连续的曲面上以多分辨方式组织表示的稠密离散采样点 集q = p i f ，p ，r 3 ，它是对模型描述的边界轮廓表示。点模型的表示首先 是一种表面的表示方法，基于点的几何表示的目标就是从离散点集中构造出 连续的表面。h o p p e 等人口1 将此问题一般化并提出了统一的描述：表面重构 的目的是用一个采样点集q 以及采样获取的一些信息( 如误差大小、采样密 度等) 来确定一个近似表示未知曲面s 的表面f 。 p h y s i c a l m o d e l r a wp o i n tm o d e lm o d i f i e d c l o u d r e p r e s e n t a t i o n m o d e l 图1 - 1 点模型的三维造型流水线。1 f i n a l m o d e l 离散采样点是构成点云曲面的最基本单位，一般由三维扫描设备来获取， 并满足某种采样条件如n y q u i s t 条件，且不规则地分布于物体的表面。它包 含了点以及与之关联的表面属性，称之为“面素”或“面元”( s u r f e l ：s u r f a c e e l e m e n t ) 。在文献 4 中，作者给出了如下定义： 定义1 - 1s u r f e i 是s u r f a c ec l e m e n t 或s u r f a c ev o x e l ( 用在体绘制中) 的英 文缩写，它是一个零维r 元的离散拓扑结构，既包含了模型的几何信息，如 空间坐标、法向量等，又包含了模型的表面属性，如颜色、光照等，并可以 西南交通大学博士研究生学位论文第3 页 局部逗近物体的表面。 在实际中，假设每个点p ，包含了对象空间中的空间宽度，通常将每个点 考虑为半径为，中心在p f ，且垂直于法向量珥的一个圆盘或椭圆盘，如图 1 - 2 ( a ) 所示。在图像空间中，一个面元可以包含几个像素，也可以小于一个像 素。为了可视化，一个点对应的( 椭) 圆盘必须精细地覆盖采样空间，并且 在对象空间中要彼此交迭而不留空洞，如图1 - 2 ( b ) 所示。在理想情况下，模 型曲率大的地方应采样比较密集，面元半径较小；而曲率小的地方应采样比 较稀疏，面元半径较大。 ( a ) 图1 - 2 ( a ) 面元的定义；( b ) 三维 ( b ) 物体空间中，模型表面被相互少量重迭的面元所覆盖 1 2 2 点模型的法向量和曲率 目前，绝大多数三维扫描设备获取的点云数据都带有采样点的空间坐标 和法向量，但也有少数设备只输出采样点的位置信息，而没有法向量信息， 所以对那些没有法向量信息的点云数据，在迸一步处理前必须计算各采样点 的法向量；此外，曲率信息对点云数据的简化、重建等工作起着非常重要的 作用，很有必要事先估计出各采样点在空间曲面上的曲率，最常用的方法是 协方差分析法。协方差分析法( c o v a r i a n c ea n a l y s i s ：c a ) 也称主元分析法 ( p 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 ) 。，是一种鲁棒统计方法，它不仅可 以快速估计出各采样点的空间法向量和曲率信息，还可以计算点云数据的局 部最小二乘拟合平面。 删一一咖一， 第4 页西南交通大学博士研究生学位论文 设输入点模型的采样点数据为q = p ，。，】，p 。r 3 ，给定任意一点 p q 。= 巩k ，州，所九，点集q ，是集合q 的一个子集，亦即为p 的一个局部 卜阶最小邻域，如图1 - 3 所示。采样点p 的协方差矩阵如下所示： c 忧m 习 m t ， 其中，f 表示采样点p 的邻域q ，的重心，p ，表示采样点p 的卜邻域内第i 个 c ，= 扣( 宁 m z ， 其中，是单调递减的权函数，权值大小由欧氏距离慨一刮和共同决定， & 为核的大小。以下考虑特征值问题 q q = 岛e ，e 0 , i ，2 ( 1 3 ) 因为c ，为三阶半正定对称矩阵，所以特征值o t 为实数，特征向量e ，构成一 个正交标架，对应于点集q ，的主元。e ，沿相应的特征向量方向度量曲面的变 分，总的变分也就是采样点p ，到它的重心的欧氏距离的平方和，由下式给出： h 一开= o o + b + 睦 ( 1 4 ) h 不妨设o o - o t - 0 2 ，则椭圆平面r o ) = 缸| ( x d 1 c i l 扛一西1 ) 穿过f ，并且到 采样点p 的邻域内点的距离的平方和最小。所以e o 可近似曲面在p 点的法向 量n p ，即n 。* e o ，换句话说，椭圆的两个主轴e l 和e 2 张成了一个最小二乘 西南交通大学博士研究生学位论文第5 页 拟合平面，如图1 3 所示。此处，我们按照h o p p e 等人口1 的e u c l i d e a n 最小 生成树方法，确定p 点的法向量方向。该方法从一个极值点开始，如z 坐标 值最大的点，计算该点的法线，并取远离点集重心位置f 的方向为法线的方 向。相邻点的法向量按照与已知法线方向之间的夹角小于n 2 原则选取。如 果原始曲面为可定向曲面，并且采样足够稠密，按上述方法可以获得一个一 致的法线方向。吼在数值上描述了曲面沿法向量的变化，疗l 和巩表示采样点 在切平面中的分布情况。我们定义下式为采样点p 在卜阶最小邻域内的曲面 变分： 口 t ( p ) 2 南( 1 - 5 ) 于是点模型在采样点p 处的曲面变分r ( p ) 可近似为该点的曲率，即 “t ( p ) 。 ( a )( b ) 图1 3 点模型局部邻域协方差分析的二维示意图。 ( a ) 采样点p 的局部邻域；( b ) 由特征向量e l 和e 2 张成的椭圆平面 1 2 3 点模型的数据结构 点模型的数据结构主要有两类：不分层的数据结构和分层的数据结构。 其中不分层的数据结构主要有：均匀网格、哈希网格；分层的数据结构主要 有：八叉树、k d 树、层次包围球、v s 树( v o l u m e s u r f a c et r e e s ) 等。以下 重点介绍在论文中应用的几种数据结构。 第6 页西南交通大学博士研究生学位论文 1 2 3 1 八叉树 八叉树”是一种有效的空间划分数据结构，通过自顶向下的方法来构 建。给定输入点云数据q = n ，。，p ，r 3 ，首先计算包含该点集的轴对齐的 立方体包围盒，并作为根节点；然后，将根节点平均分割成八个等尺寸的小 立方体，称为根节点的孩子节点，孩子节点又被进一步细分成八个更小尺寸 的立方体。该过程重复执行的次数称为八叉树的深度，采样点只存在于叶子 节点中。细分过程递归进行赢到达到某一设定的深度或孩子节点为空时才停 止，如图i - 4 所示。 图i - 4 八叉树的创建过程 八叉树结构非常适合点模型的近邻查找和范围搜索，但同时也存在一些 缺点：一方面，树结构中有许多节点表示了不含采样点数据的空间，虽然这 些节点可以被删除，但要浪费内存空间来存储指向这些节点的空指针；另一 方面，当遍历八叉树时，搜索点的三个坐标都要被查找，以确定是孩子节点 西南交通大学博士研究生学位论文第7 页 的哪个八分体。为了克服这些问题，本文将在隐式凸面重建算法中改进标准 的八叉树结构，用自适应的八叉树对空间进行划分，详细内容见4 4