（控制科学与工程专业论文）散乱点云三维表面重建技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 基于图像的三维几何建模是虚拟现实研究领域的一项前沿技术。如何从立体 图像生成的点云数据快速生成三维环境模型是基于图像的三维重建研究的重要内 容。面向虚拟环境仿真、移动机器人导航等应用，本文的研究目标是实现非规则 地形的快速三维重建。在包括国家“8 6 3 ”高技术课题在内的三个项目的支持下， 本文首先研究了超曲面演化理论在点模型光顺中的应用，并利用图形处理器 ( g p u ) 强大的并行运算能力加速光顺处理，然后建立了点模型的多分辨率表达， 最后完成表面的三维重建。本文的研究对基于图像的虚拟环境建模应用具有重要 意义。 本文的主要成果和创新点为： 1 提出了特征曲率的概念，作为一种曲面不变几何量，特征曲率能够更准确 地描述曲面在一点处的弯曲程度。给出了特征曲率流演化方程，并在此基础上提 出了基于特征曲率流的点云光顺算法。实验结果表明，相对于基于平均曲率流的 光顺算法，该算法在取得光顺去噪效果的同时，具有更好的特征保持能力。 2 以黎曼几何为理论基础，研究了二维超曲面的演化理论，提出了一种梯度 下降流演化方程。将该演化方程应用到点云模型光顺中，实现了基于梯度下降流 的点云光顺算法。实验结果表明，该算法在保持模型特征的基础上，可以有效地 消除点云模型中的噪声。 3 提出了基于图形处理器的点云模型快速光顺方法。首先提出了基于迹变换 的快速光顺参数求解算法；然后通过扩充矩阵对角线存储策略和稀疏矩阵压缩存 储方案，分别实现了基于g p u 的曲面变分点云快速光顺算法和基于g p u 的特征 曲率流点云快速光顺算法。实验结果表明，基于g p u 的算法显著提高了点云光顺 处理的速度。 4 提出了一种基于特征曲率的点云模型多分辨率建模方法。论文首先在k d 树层次空间剖分技术的基础上，提出了以特征曲率作为分割判据的点云模型简化 算法。然后，通过一组曲率阈值控制分层多分辨率模型的生成，提出了基于特征 曲率的点云模型多分辨率模型建模方法。最后，通过实验验证了该方法的有效性。 5 针对亏格点云模型的表面修复重建问题，首先提出了一种曲面孔洞检测算 法；然后，提出了一种基于权重的支持向量机回归模型；最后，提出一种基于分 块策略的s v m 表面重建方法。该重建方法采用空间分割技术将模型分成规模适中 的子集进行分块重建，从而提高重建效率。实验结果表明，利用该方法重建得到 的表面模型能够修复原始模型中的孔洞。 第i 页 国防科学技术大学研究生院博士学位论文 通过基于立体视觉三维重构的地形模型的应用实例研究，验证了上述方法的 可行性与有效性。本文研究成果对支撑课题的完成作出了贡献。 主题词：散乱点云，三维重建，特征曲率，光顺，图形处理器，支持向量机， 多分辨率表达 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t p a c t i m a g eb a s e dt h r e e d i m e n s i o n a lg e o m e t r i cm o d e l i n gi so n eo ft h ea d v a n c e d t e c h n o l o g y i nt h ef i e l do fv i r t u a l r e a l i t y t or e c o n s t r u c t 也et h r e e d i m e n s i o n a l e n v i r o n m e n tm o d e lf a s tf r o mp o i n tc l o u dg e n e r a t e db ys t e r e oi m a g e si sa i li m p o r t a n t t o p i co fi m a g eb a s e dt h r e e d i m e n s i o n a lr e c o n s t r u c t i o n a i m i n ga tt h ea p p l i c a t i o n ss u c h a ss i m u l a t i o ni nv i r t u a le n v i r o n m e n t , n a v i g a t i o no fm o b i l er o b o t s ，e t c ，t h eg o a lo ft h e d i s s e r t a t i o ni st or e a l i z et h et h r e e d i m e n s i o n a lr e c o n s t r u c t i o no fi r r e g u l a rt e r r a i n u n d e r t h es u p p o r to f t h r e ep r o j e c t s ，i n c l u d i n go n eo f t h en a t i o n a l “8 6 3 h i g ht e c h n o l o g yp l a n , t h ea p p l i c a t i o no fh y p e r s u r f a c ee v o l u t i o nt h e o r yi nt h es m o o t h i n go fp o i n tc l o u dm o d e l s i sr e s e a r c h e df i r s t l y a n dt h eg r a p h i c sp r o c e s s i n gu n i t ( o p u ) w h i c hi so fg r e a tp a r a l l e l c a p a b i l i t yi sa d o p t e dt oa c c e l e r a t et h ep r o c e s so fs m o o t h i n g t h e nt h em u l t i r e s o l u t i o n r e p r e s e n t a t i o no ft h ep o i n tc l o u dm o d e li sc o n s t r u c t e d a t1 a s t t h et h r e e d i m e n s i o n a l m o d e lo ft h es u r f a c ei sr e c o n s t r u c t e d n l ew o r ko ft h i st h e s i si so fg r e a ti m p o r t a n c ef o r t h ea p p l i c a t i o n so fi m a g eb a s e dv i r t u a le n v i r o n m e n tm o d e l i n g t h em a i nr e s u l t sa n di n n o v a t i o n so f t h et h e s i sa r ea sf o l l o w i n g ： 1 t h ec o n c e p to ft h ef e a t u r ec u r v a t u r ei sp r o p o s e d a san e wi n v a r i a b l eg e o m e t r i c m e a s u r eo fs u r f a c e s ，t h ec o n c e p td e s c r i b e st h eb e n dd e g r e eo fs u r f a c e sm o r ee x a c t l y a f e a t u r ec u r v a t u r ef l o we v o l u t i o ne q u a t i o ni sp r e s e n t e d ，b a s e do nw h i c hap o i l l tc l o u d m o d e ls m o o t h i n ga l g o r i t h mb a s e do nf e a t u r ec u r v a t u r ef l o wi s p r o p o s e d 1 1 1 e e x p e r i m e n tr e s u l t ss h o wt h a tt h ea l g o r i t h mc a r ld e n o i s et h em o d e le f f c c t i v e l y a tt h e s a m et i m e ，h a sb e t t e rc a p a b i l i t yo ff e a t u r ep r e s e r v i n gt h a nt h a to ft h ec l a s s i c a l s m o o t h i n ga l g o r i t h mb a s e d o na v e r a g ec u r v a t u r ef l o w 2 b a s e do nr i e m a r mg e o m e t r y ，t h e2 - d i m e n s i o n a lh y p e r s u r f a c ee v o l u t i o nt h e o r yi s r e s e a r c h e d t h e ng r a d i e n td e s c e n df l o we v o l u t i o ne q u a t i o ni sp u tf o r w a r d t h e e v o l u t i o ne q u a t i o ni sa p p l i e dt os m o o t ht h ep o i n tc l o u dm o d e l s ，f o r m e dt h ep o i n tc l o u d m o d e ls m o o t h i n ga l g o r i t h mb a s e do ng r a d i e n td e s c e n df l o w e x p e r i m e n t ss h o wt h a tt h e a l g o r i t h mc a l lr e d u c et h en o i s ee f f e c t i v e l y , p r e s e r v i n gt h ef e a t u r e s 3 t h ef a s ts m o o t h i n gm e t h o d so fp o i n tc l o u dm o d e la r ep r o p o s e db a s e do ng p u f i r s t l y ，t h eu a c et r a n s f o r m a t i o nb a s e da c c e l e r a t e da l g o r i t h m ，w h i c hi su s e dt os o l v et h e s m o o t h i n gp a r a m e t e r s ，i sp r e s e n t e d t h e n ，w i t ht h ed i a g o n a ls t o r a g es t r a t e g yf o rt h e e x t e n d e dm a t r i xa n dt h ec o m p r e s s e ds t o r a g es c h e m ef o rt h es p a r s em a t r i x ，t w o g p u - b a s e df a s ts m o o t h i n ga l g o r i t h m sf o rt h ep o 缸c l o u dm o d e lb a s e do ns u r f a c e v a r i a n c ea n db a s e do nf e a t u r ec u r v a t u r ea r ei m p l e m e n t e dr e s p e c t i v e l y t h ee x p e r i m e n t s s h o wt h a tt h ep e r f o r m a n c eo ft h ep o i n tc l o u dm o d e ls m o o t h i n gp r o c e s si sa p p a r e n t l y p r o m o t e db yt h eg p u b a s e da l g o r i t h m s 4 am u l t i - r e s o l u t i o nm o d e l i n gm e t h o do fp o i n tc l o u dm o d e l si sp u tf o r w a r db a s e d 第i i i 页 国防科学技术大学研究生院博士学位论文 o nf e a t u r ec u r v a t u r e f i r s t l y ，b a s e do nt h eh i e r a r c h i c a lk dt r e es p a c es e g m e n t a t i o n s c h e m e ，ap o i n tc l o u dm o d e ls i m p l i f i y i n ga l g o r i t h mt h a te m p l o y sf e a t u r ec u r v a t u r ea s t h es e g m e n t a t i o nc r i t e r i o ni sp r e s e n t e d t h e r e a f t e r ，a c c o r d i n gt ot h eg e n e r a t i o no fa h i e r a r c h i c a lm u l t i r e s o l u t i o nm o d e lc o n s t r a i n e db yas e r i e so fc u r v a t u r e s ap o i n tc l o u d m u l t i r e s o l u t i o nm o d e l i n ga l g o r i t h mb a s e do nf e a t u r ec u r v a t u r ei s p r e s e n t e d t h e e m c i e n c yo ft h i sa l g o r i t h mi sp r o v e db ye x p e r i m e n t s 5 i no r d e rt or e p a i ra n dr e c o n s t r u c ts u r f a c e sf r o mg e n u sp o i n tc l o u dm o d e l s ah o l e d e t e c t i o na l g o r i t h mo fg e n u ss u r f a c ei sp r o p o s e d t h e r e a f t e r , as u p p o r tv e c t o rm a c h i n e ( s v m ) r e g r e s s i o nm o d e lb a s e do nw e i g h ta t t a c h e dt os a m p l i n g si sp r o p o s e d a tl a s t ，a s e g m e n t a t i o ns t r a t e g yb a s e ds v ms u r f a c er e c o n s t r u c t i o nm e t h o di sp r e s e n t e d n l e r e c o n s t r u c t i o nm e t h o di st h a ts p a c es e g m e n t a t i o nt e c h n i q u ei sa d o p t e dt od i v i d et h e m o d e l si n t os e v e r a ls u b s e t sw i t ha p p r o p r i a t en u m b e ro f p o i n t s ，s ot h a tt h er e c o n s t r u c t i o n e f f i c i e n c yi si m p r o v e d e x p e r i m e n t ss h o wt h a to nt h es u r f a c er e c o n s t r u c t e db yt h e m e t h o d ，t h eh o l e so ft h eo r i g i n a lg e n u ss u r f a c ea r er e p a i r e ds a t i s f a c t o r i l y t h ep r o p o s e da l g o r i t h m sw e r eu t i l i z e di nt h es t e r e ov i s i o nb a s e dt h r e e d i m e n s i o n a l r e c o n s t r u c t i o na p p l i c a t i o ni n s t a n c e sf o rt h et e r r a i nm o d e l s a n d 也ef e a s i b i l i t ya n d v a l i d i t yo f 也ea l g o r i t h m sw e r ep r o v e d t h er e s e a r c hr e s u l t so ft h ed i s s e r t a t i o nh a v e m a d ea c t u a lc o n t r i b u t i o n st ot h ef u l f i l l m e n to ft h ef u n d e dp r o j e c t s k e yw o r d s ： s c a t t e r e dp o 缸c l o u d ，t h r e e d i m e n s i o n a lr e c o n s t r u c t i o n ，f e a t u r e c u r v a t u r e ，s m o o t h i n g ，g r a p h i c sp r o c e s s i n gu n i t ，s u p p o r t v e c t o r m a c h i n e ， m u l t i - r e s o l u t i o nr e p r e s e n t a t i o n 第i v 页 国防科学技术大学研究生院博士学位论文 i b m r g p u s v s v m s i m d 主要英文缩略语的中英文对照表 i m a g eb a s e dm o d e l i n ga n dr e n d e r i n g基于图像的建模与绘制 g r a p h i c sp r o c e s s i n gu n i t s u p p o r tv e c t o r s u p p o r tv e c t o rm a c h i n e 图形处理器 支持向量 支持向量机 s i n g l ei n s t r u c t i o nm u l t i p l ed a t a单指令多数据 c p u mc p ub a s e di n v e r s ep o w e rm e t h o d基于c p u 的反幂法 c p u t tc p ub a s e dt r a c et r a n s f o r mm e t h o d基于c p u 的迹变换算法 g p u - t tg i 哪b a s e dt r a c et r a n s f o r mm e t h o d基于g p u 的迹变换算法 c p u gc p ub a s e d g a u s sm e t h o d基于c p u 的高斯算法 c p u c gc p ub a s e dc o n j u g a t eg r a d i e n tm e t h o d基于c p u 的共轭梯度算法 g p u c gg p ub a s e dc o n j u g a t eg r a d i e n tm e t h o d基于g p u 的共轭梯度算法 第1 页 国防科学技术大学研究生院博士学位论文 表2 1 表3 1 表4 1 表4 2 表5 1 表目录 几种光顺算法的时间效率表5 2 g p u 的计算精度一7 0 不同分辨率三维模型对应的曲率阈值j 8 5 不同分辨率地形模型对应的曲率阈值：8 6 s v m 重建效率对比10 4 第1 v 页 国防科学技术大学研究生院博士学位论文 图目录 图2 1k 邻域图2 6 图2 2 协方差分析法2 8 图2 3 法矢量估算图例2 8 图2 4b u n n y 模型表面上的曲率对比图3 1 图2 5 d r a g o n 模型表面上的曲率对比图3 1 图2 6 地形模型表面上的曲率流对比图。3 2 图2 7曲率流分布局部对比图3 3 图2 8 噪声b u n n y 模型光顺去噪效果对比图3 4 图2 9 噪声地形模型光顺去噪效果对比图3 5 图2 1 0b u n n y 模型上的梯度流分布图。4 7 图2 11 地形模型上的梯度流分布图4 8 图2 1 2 带有噪声的地形模型光顺去噪效果对比图。4 9 图2 1 3 视觉地形模型光顺去噪效果图。5 1 图3 1向量的纹理表示5 5 图3 2 向量代数运算。5 7 图3 3 多遍渲染实现向量缩减运算5 7 图3 4 协方差矩阵在g p u 中的表示方式6 5 图3 5 特征值与特征向量求解效率对比6 9 图3 6 不同采样点规模下的求解效率对比6 9 图3 7 线性方程组求解效率对比7 4 图4 1 节点数据结构图7 9 图4 2 简化效果图8 2 图4 3 点云模型的多分辨率表达8 6 图4 4 点云模型的多分辨率表达8 6 图4 5 地形模型1 的多分辨率表达8 7 图4 6 地形模型2 的多分辨率表达8 7 图5 1临界点与内点示意图。9 0 图5 2 邻域投影图9 2 图5 3b u n n y 模型孔洞检测结果9 3 图5 4 规则曲面上孔洞检测结果9 3 图5 5 视觉地形数据孔洞检测结果9 4 第v 页 国防科学技术大学研究生院博士学位论文 图5 6 训练集划分图1 0 1 图5 7s v m 分块重建效果图10 3 图5 8 地形模型1 的s v m 重建效果图10 5 图5 9 地形模型2 的s v m 重建效果图10 6 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目1遨塾惠垂三维塞亘重建技苤盈窥 学位论文作者签名： 日期：2 0 0 9 年8 月2 8 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文 档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目 学位论文作者 作者指导教师 同防科学技术大学研究牛院博士学何论文 第一章绪论 1 1 课题研究背景 当前，机器人技术的快速发展使得现代移动机器人得到日益广泛的应用，从 工业制造到医疗服务、空间探索、军事斗争等许多领域，都可以看到机器人的身 影。而伴随着机器人应用领域的扩大，人类已经将自己的探索空间拓展到越来越 广阔的未知环境。无论是遥远的银河系还是数千米深的海底，都已进入人类的认 知范畴，正所谓“可上九天揽月，可下五洋捉鳖”。 不断扩大的探索空间大大促进了对三维建模技术的研究。低成本快速重建三 维环境特别是未知环境日益受到人们的重视。当前，利用立体视觉或坐标扫描技 术获取目标实体的散乱点云描述并实现三维重建，已成为未知环境建模的重要方 式。 例如，在空间探测领域，立体视觉技术已成为远端环境重现的重要手段。由 于太空得天独厚的经济与军事价值，以美俄为首的各大国不惜投入巨资发展太空 探测平台。为提高地面操控人员对远端空间环境的感知，研究人员利用虚拟现实 技术再现太空远端三维场景，增强操作员的临场感。然而，太空中不仅有已知实 体，而且有未知实体。前者的实体模型是己知的，而作为未知目标出现的后者的 三维信息往往是未知的。因此，如何快速构建未知目标对象模型完成空间环境的 远端再现成为空间遥现系统面临的主要困难之一。伴随着计算机视觉技术的发展， 基于图像的建模与绘制技术( i m a g eb a s e dm o d e l i n ga n dr e n d e r i n g ，i b m r ) 的出现为 解决这一难题提供了可能。i b m r 直接利用立体视觉、图像配准和增强现实等技术 从单幅或多幅图像中恢复物体的几何结构，进而重建三维场景。该技术无需待重 建物体几何信息，因此能够克服远端环境信息感知的局限性，实现远端环境的遥 现，特别适合于未知环境和复杂环境重建。美国2 0 0 3 年发射的“火星快车”探测 器利用所携带的高分辨率立体摄像机拍摄火星图像并传回地面中心f l 】，由实验小组 的科学家将所有数据转换成为几何图像，生成火星“数字地形模型”。2 0 0 4 年发 射的“勇气”号火星车上安装有全景照相系统，该系统包括两个参数相同且位置 固定的全景照相机【2 】，通过对标定后的相机获取的两幅图像进行立体匹配，提取视 差图并生成立体视觉信息，从而进行火星环境的三维重建。 在环境侦察与探测领域，利用移动机器人采用探测设备对环境进行探测，获 取环境的点云坐标，实现未知环境的三维重建是一种重要的环境建模方式。当前， 将作战实体面对的作战环境转化到数字空间并加以可视化，实现战场环境的快速 第1 页 罔防科学技术大学研究牛院博士学位论文 重建为操作员提供形象直观的环境态势显示，已成为数字化战场建设的重要内容。 密歇根大学正负责为美军研制用于城市作战的机械蝙蝠【3 】，该机械蝙蝠装备双图像 传感器以提供立体视觉信息。 在局部路径导航方面，通过给机器人安装立体视觉系统或激光雷达，利用所 获取的环境信息快速重建三维环境，然后进行路径规划或障碍检测是提高野外机 器人自主能力的重要手段。美国d a r p a 举办的“g r a n dc h a l l e n g e ”中多数参赛车 辆安装了立体视觉摄像头或激光雷达，用于障碍检测和三维环境重建。如s t a n f o r d 大学的s t a n l e y 4 1 安装有5 个激光雷达，一组立体摄像头和一个单眼视觉系统，用 于获得环境数据进而检测障碍，从而保证了s t a n l e y 能够实时避开障碍物继续沿着 正确的路线行驶。 应用领域的扩大推动着三维建模技术的不断进步，新的模型表达方式、建模 理论和建模方法不断涌现。面向三维几何数据的数字几何处理已成为计算机图形 学、计算机视觉、数字信号处理等学科的前沿研究领域和热门课题。作为一种新 型的数据载体，三维几何模型正以其高度逼真、形象直观等无可比拟的优越性逐 渐改变着人们探索和认识世界的方式。 一般而言，三维几何模型可分为两种形式：网格模型和点云模型。网格模型 是一种广为采用的模型表达方式，如医学上的c t 数据。这种类型的模型除了包含 点的空间位置信息外还包含有拓扑连接等结构化信息，其中的拓扑信息可以用来 重构三维模型。由于网格模型表示方式数据结构相对简单，绘制方便，因此在工 程上得到了广泛的应用。然而由于网格模型需要维护二维流形拓扑结构的一致性， 数据处理算法因此变得复杂，随着模型的规模越来越大，所包含的顶点越来越多， 网格模型的局限性和不足之处也随之显现出来。 近年来，立体视觉技术的发展和三维扫描仪、激光雷达等坐标测量设备的逐 渐普及，使得点云模型的获取越来越便捷。事实上，早在1 9 8 5 年l e v o y 1 0 】便提出 采用点元作为显示图元的思想。然而直到今天，点云数据作为一种新的模型表达 方式才开始受到人们的热切关注。在这样的背景下，针对点云模型的研究开始引 起人们的重视。与网格模型相比，点云模型仅包含采样点的位置、颜色等属性， 而不包含任何拓扑连接信息，数据形式简单，易于存储和编辑，因此在环境重建、 逆向工程、图像重建等领域得到日益广泛的应用【5 1 6 1 1 7 9 1 9 4 l 。目前，点云模型正越来 越多地取代三角形网格在三维几何建模中的应用，并在近几年的三维数据处理中 占据了重要地位，逐渐成为继三角网格模型之后又一种主流的模型表达方式。 利用机器人获取环境模型的方法主要有两种。一是在机器人上安装视觉装置， 通过立体视觉技术从图像对或图像序列中得到三维场景的散乱点云模型；二是利 用激光雷达等坐标测量设备扫描几何模型进行离散采样从而感知真实环境。这两 第2 页 同防科学技术大学研究牛院博士学何论文 种方法鄙町以生成目标环境的三维模型。较之传统测绘手段，方便而快捷，从而 大大简化了复杂的建模过程，为快速重建三维环境提供了可能。如何对这些点云 数据进行快速处理，构建逼真的三维环境是高技术条件下真实战场环境实时再现 面临的重要课题。 1 2 散乱点云几何处理研究现状 在点云模型得到广泛应用之前，三维模型几何处理技术主要是针对网格数据。 经过几十年的研究与应用，网格模型的处理得到了广泛而深入的研究，包括网格 模型的去噪、简化、多分辨率分析与绘制等。随着点云模型在应用领域获得越来 越多的应用，迫切需要对基于点元的三维模型数字几何处理进行理论与算法上的 深入研究，以期利用点云模型完成三维建模表达任务。然而基于点云模型的三维 表达存在诸多亟待解决的问题。 首先，由于设备获取精度、光照条件影响以及物体表面反射特性等原因，由 三维扫描仪等数据获取系统或通过基于图像的重建方法获取的三维物体采样点数 据中往往包含一定的噪声，这些噪声的存在干扰了表面重建的准确性，甚至会改 变原几何对象的拓扑结构。特别是在基于图像重建的应用中，由摄像机采集处理 得到的三维数据不是自适应的点云数据，采样存在不均匀、噪声干扰、数据孔洞 等缺陷。因此在对点云数据进一步处理之前需要进行光顺降噪处理，以消除点云 数据中包含的强噪声干扰，得到与原几何体尽可能接近的模型。 其次，点云模型通常包含上万甚至几十万个数据点，例如s t a n f o r d 大学利用 三维扫描仪重建得到的b u n n y 模型包含2 4 0 ，0 0 0 个点，而d a v i d 模型包含上千万个 点。在理想情况下，从两幅6 0 0 8 0 0 的图像得到的模型最多可以包含4 8 0 ，0 0 0 个采 样点。数据点的几何处理涉及大量的代数运算，例如，点云光顺中协方差矩阵的 计算、局部或隐式曲面拟合时方程组的求解等。庞大的数据点不仅增加了存储开 销，而且为快速重建带来了困难。对于需要快速重建的应用这往往成为系统性能 的瓶颈。如何提高几何光顺的速度成为数字几何处理面临的困难之一。 第三，随着点云模型的日益广泛应用，点云模型的多分辨率建模越来越受到 研究人员的关注。点云模型通常包含海量的采样点，对这样庞大规模的点模型进 行编辑、变形、渲染等处理需要巨大的时间和空间开销，往往超过了当前硬件系 统的交互显示能力。而在实际工程应用中，根据不同的应用对象需要不同精细程 度的模型。对于仅需要低分辨率模型的应用，稠密的采样点被视为是冗余数据。 因此，建立点云模型的多分辨率表达，允许用户根据应用环境的需要选择不同精 度的模型进行处理具有重要的意义。 最后，点云模型是原始模型的离散近似，如何从点云模型得到原始模型的紧 第3 贞 同防科学技术大学研究牛院博士学位论文 致表达是点云处理研究的重要内容。然而由于点云模型中往往存在孔洞，经上述 处理后虽然能够得到光顺的具有不同分辨率的点云模型，但却无法修复模型中的 孔洞。如何对这样的亏格模型进行重建从而得到连续表面是点云数字几何处理研 究的热点课题。 总之，与网格模型相似，点云模型数字几何处理的研究内容包括光顺去噪、 孔洞修复、多分辨率表达以及表面重建等。基于此，本文的研究内容主要包括四 部分：一是散乱点云模型光顺技术，二是基于图形处理器的点云模型快速光顺处 理技术，三是点云模型的简化与多分辨率表达技术，四是亏格点云模型的孔洞检 测和表面修复重建技术。 1 2 1 散乱点云数据光顺技术 散乱点云数据光顺是点云数字几何处理研究的重要内容。光顺是一个工程概 念，很难用形式化的方法加以描述。其主要的困难在于人们对模型光顺性的判断 是依赖于视觉的一定尺度上的直观感受，带有一定的主观性。在此需要区分“光 顺与“光滑”两个概念。首先，光顺是对模型一定尺度上的评价。换言之，只 能从一定尺度上评价曲面的光顺程度。我们可以讨论曲面在一点处的光滑性，但 却难以分析曲面在一点处的光顺性。其次，光顺是视觉上的主观感受。我们可以 定量地给出光滑的定义，但却难以给出光顺的定义。光顺与否和尺度有关，同一 条曲线在较小尺寸的模型中可以认为是光顺的，但在较大尺寸的模型中却可能是 非光顺的。以上这两点使得难以对光顺进行定量描述。虽然也有一些文献试图给 出光顺判别准则【l6 】【1 7 1 1 1 8 】，但这些准则本身也多有模糊之处。文献d 9 1 认为，光顺 包含“光滑”和“顺眼”两方面的要求。在这个意义下，较之光滑，光顺包含更 多的内涵。一条曲线可以是光滑的却未必是光顺的。例如，一条任意次可微的平 面曲线如果曲率变化太大则可能是非光顺的，而仅满足一阶连续性要求的三次b 样条【7 5 】【7 6 】构造的分片曲面却可以认为是光顺的。因此光顺不应仅仅以提高模型的 光滑性为目标。然而，光顺与光滑也存在一定的联系，两者都与表面平滑程度有 关，通过提高曲面的连续阶来剔除噪声是一种重要的光顺途径。 概括而言，散乱点云数据光顺的目标是以合理的算法复杂度剔除模型中包含 的噪声以获取平滑的点云模型，同时保持模型特征1 3 6 1 。点云光顺面临两个困难， 一是噪声识别。从信号的频谱上看，三维模型的特征和噪声均表现为信号的高频 起伏，如何在降噪的同时保持模型的几何特征成为三维模型光顺的难点之一。二 是曲面几何参数的计算。在信号处理领域，信号通常是定义在等距区间或均匀网 格上，采样点为规则的。但点云数据中采样点是非规则的，这种非规则的采样方 式增加了几何处理的难度。而且采样点之间没有拓扑连接信息，网格模型上广泛 第4 页 同防科学技术大学研究牛院博士学位论文 采用的微分几何算子计算方法难以直接推广钊离散点模型上。 由于光顺性是对模型一定尺度上的评价，因此主流的光顺算法一般采用扩散 方程或几何流演化方程从整体或局部上对曲面进行优化从而达到光顺的目的。点 云模型光顺的研究与网格模型光顺的研究一脉相承，因此有必要对网格光顺技术 作一简要介绍。 网格光顺技术已经得到深入研究【1 5 1 1 2 2 1 1 2 3 】【2 4 】【2 9 】【3 4 】。早期的网格光顺技术采用基 于l a p l a c e b e l t r a m i 算子的扩散方程平滑网格噪声。t a u b i n 在顶点1 邻域上定义 l a p l a c e 算子【2 2 】，从而将信号处理领域的l a p l a c e 滤波方法引入网格光顺中。该方 法具有线性时间和空间开销，结合表面细分技术可以处理任意拓扑结构的大规模 网格数据。所谓l a p l a c e 扩散方程是定义在曲面上的演化方程 孚：脚， ( 1 1 ) 甜 。 、7 其中，五为尺度因子，为l a p l a c e b e l t r a m i 算子，定义为 ：v z ：要+ 罢+ 芸， ( 1 2 ) a x c y 亿 采用显式积分可得迭代方程为 s 州= ( i + 2 l d t ) s ( 1 3 ) d e s b r u n 采用隐式迭代算法求解l a p l a c e 迭代方程【2 3 】【2 4 】，提高了算法的稳定性， 分析了基于扩散方程的光顺方法的局限性，指出扩散算子的切向分量将带来顶点 漂移，从而造成模型变形。为克服这一不足，d e s b n m 进一步提出基于曲率流的网 格光顺方法，曲面演化方程为 导= 一向， ( 1 4 ) 式中，向为采样点处的平均曲率，n ，为法方向。根据式( 1 4 ) 可以看出，基于曲率 流的光顺方程以平均曲率为速度沿法线反方向移动采样点。由于平均曲率流没有 切向分量，因此不会带来顶点的切向漂移。但平均曲率流是一种各向同性算子， 在平滑噪声的同时也会造成曲面的特征模糊【2 0 1 。因此寻求保特征的曲率流成为曲 率流光顺算法研究的重点。c l a r e n z 等借鉴各向异性的图像处理技术，在扩散方程 中引入各向异性扩散张量控制光顺【1 2 】，提高了扩散方程的保特征性能，从而达到 光顺的同时保持特征的目的。b a j a j 进一步研究了该方法，系统分析了二维流形和 曲面函数的几何流扩散方程，并采用细分网格求解p d e ( p a r t i a ld i f f e r e n t i a le q u a t i o n , p d e ) 方程【2 引。 受平均曲率流思想启发，赵炊喜采用反调和曲率流作为光顺算子构造分段演 化函数【2 7 1 ，选择简单的保细节各向异性演化权函数，在快速计算的同时较好地保 持了模型几何特征。x u 应用变分法推导了曲面在一般积分函数约束下的 第5 页 同防科学技术大学研究牛院博士学位论文 e u l e r l a g r a n g e 方程【2 9 】【3 4 】，在此基础上给出了曲面演化的一般方程，按此规律演化， 在曲面的微小扰动下上述积分变化最小。选择合适的积分函数可以得到平均曲率 流演化方程、高斯曲率流演化方程等。x u 采用局部曲面拟合法在网格模型上验证 了算法在曲面融合、光顺去噪等应用中的有效性。 由于散乱点云数据中不包含拓扑结构信息，因此建立在局部拓扑邻域结构上 的网格处理技术无法自动适用于点云数据处理。一种自然的思路便是为点云数据 添加拓扑结构信息将其转化为网格模型，然后采用网格模型光顺技术消除所包含 的噪声，之后再去掉光顺后的网格模型中的拓扑结构便可得到光顺的点云模型。 这种思路简单直接，可以充分利用现有的理论和技术来处理点云噪声。但是，散 乱点云数据的网格化繁琐耗时，需要耗费一定的系统资源构建并存储拓扑连接信 息；另一方面，点云数据中所包含的噪声也会影响模型的局部特征一致性。在这 样的背景下，直接基于散乱点云进行光顺成为大规模三维模型光顺去噪技术研究 的热点。研究人员提出一些基于采样点局部邻域的平滑滤波方法。按照所采用滤 波算子的不同，这些方法可以分为基于扩散方程的去噪技术、基于几何流的去噪 技术和其它去噪技术。 1 2 1 1 基于l a p l a c e b e l t r a m i 算子的光顺技术 这类算法在点云模型上寻找l a p l a c e b e l t r a m i 算子的近似计算方式，采用与网 格模型类似方法光顺点云模型。在t a u b i n 工作的基础上1 2 2 ，p a u l y 最先将t a u b i n 的方法应用到点模型中【5 1 ，用采样点的k 一邻域代替顶点的一阶邻域，将拉普拉斯 变换定义为采样点k 一邻域邻近点的加权