（信号与信息处理专业论文）基于图片序列的三维表面重建.pdf

摹十图 序列的二三维表面重建中义摘要 基于图片序列的三维表面重建 中文摘要 随着计算机技术的发展，人们已经不再满足于在计算机屏幕中看到简单的二维画 面了，所以三维重建技术也越来越引起人们的重视，它在计算机辅助设计、计算机视 觉、虚拟现实等领域都有着广泛的应用。本文首先阐述了基于八叉树的三维重建技术 原理，然后在此基础上提出了表面点的提取及纹理张贴算法，论文主要工作和贡献体 现在以下几个方面： 首先，结合传统的八叉树三维重建算法，提出了一种三维物体表面点的提取算法。 该算法将构成物体的立方体顶点分为六种情况，根据点的不同状态( 处于立方体的顶 点、棱、面) 赋予不同的权值并通过计算处于不同立方体的顶点、棱、面的数目对点 进行打分，利用这一分值区分物体的内部点和表面点。 其次，提出了一种物体边缘轮廓的提取算法并对轮廓进行断层重建。该方法用平 行平面截取立方体，得到平面与立方体的交点，利用交点的特点，提取出边缘点。根 据物体的连通性，如果边缘点所属的立方体是连通的，那么这些点也是连通的，可以 归为一个轮廓；反之，点就属于不同的轮廓。把这些点按照不同的轮廓分类，得到每 层的轮廓数和点的对应关系，然后把这些点按照顺序连接起来，就得到了物体的断层 轮廓。通过对断层轮廓的提取，可以克服直接对表面点进行三角剖分所出现的部分三 角面片仍然在物体内部的情况，从而有利于纹理的张贴。 最后，利用纹理映射方法，恢复物体的外貌形状。选择纹理图像的准则是：判断 每幅图像的视点，亦称为图像平面的法向量，与三角面片的法向量之间的空间夹角，选 择其央角最小的一幅图像作为该面片所对应的纹理图像。 关键词：三维重建、表面点提取、断层轮廓、纹理映射 作者：苗园 指导老师：王加俊 a b s t r a c tt h r e ed i m e n s i o n a ls u r f a c er e c o n s t r u c t i o nb a s e do ni m a g es e q u e n c e t h r e ed i m e n s i o n a ls u r f a c er e c o n s t r u c t i o nb a s e do n i m a g es e q u e n c e a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ec o m p u t e rt e c h n i q u e s ，i ti sn o ts a t i s f i e da n ym o r eb y p e o p l et o s e es i m p l et w od i m e n s i o n a ls c e n e si nt h es c r e e n h e n c e ，t h r e ed i m e n s i o n a l r e c o n s t r u c t i o nt e c h n i q u e sh a v ea t t r a c t e dm o r ea n dm o r ea t t e n t i o na n dh a v eb e e nw i d e l y u s e di nt h ef i e l d so fc o m p u t e ra i d e dd e s i g n ，c o m p u t e rv i s i o na n dv i r t u a lr e a l i t y i nt h i s t h e s i s ，t h e o c t r e eb a s e d3 dr e c o n s t r u c t i o n a l g o r i t h m i s f i r s t l yd e s c r i b e da n dt h e n a l g o r i t h m sf o rs u r f a c ep o i n t se x t r a c t i o na n df o rt e x t u r ea t t a c h m e n ta r ep r o p o s e d t h em a i n w o r ka n dc o n t r i b u t i o n so ft h i sp a p e ra r es u m m a r i z e da sf o l l o w s ： f i r s t l y , c o m b i n e dw i t ht h ec o n v e n t i o n a lo c t r e eb a s e d3 dr e c o n s t r u c t i o na l g o r i t h m ，a 3 ds 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 mi sp r o p o s e d i nt h i sm e t h o d ，t h ev e r t i c e so ft h ec u b e s c o m p o s i n gt h eo b j e c ta r ec l a s s i f i e dt os i xc a s e sa n dd i f f e r e n tw e i g h t sa r ea s s i g n e dt o v e r t i c e sa c c o r d i n gt ot h e i rd i f f e r e n ts t a t e so fb e i n gav e r t e xo ri na ne d g eo ri naf a c eo fa c u b e e a c hv e r t e xi ss c o r e da c c o r d i n gt ot h en u m b e r so fv e r t i c e s ，e d g e sa n df a c e si t o c c u p i e s a c c o r d i n gt ot h es c o r e sc o r r e s p o n d i n gt ot h ev e r t i c e s ，t h e ya r ec l a s s i f i e dt ot h e i n t e r n a lp o i n t sa n dt h es u r f a c ep o i n t s s e c o n d l y , ac o n t o u re x t r a c t i o na l g o r i t h m i s p r o p o s e d f o rt h ep l a n a rc o n t o u r r e c o n s t r u c t i o n i nt h i sm e t h o d ，p a r a l l e lp l a n e sa r eu s e dt oi n t e r c e p tt h ec u b ef o ro b t a i n i n g t h ei n t e r c e p t i o np o i n t s ，a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fw h i c ht h ee d g ep o i n t sa r e e x t r a c t e d i ft h ec u b et h a tt h ee d g ep o i n t sb e l o n gt oi sc o n n e c t e dt h ep o i n t sc a nb ej u d g e d t ob ec o n n e c t e dt o oa n dt h e yc a l lb ec l a s s i f i e dt oo n ec o n t o u r o t h e r w i s e t h o s ep o i n t sw i l l b e l o n g t od i f f e r e n tc o n t o u r s t h en u m b e ro fc o n t o u r so fe a c hs l i c ea n da l s ot h e c o r r e s p o n d e n c er e l a t i o n s h i pb e t w e e np o i n t sc a nb eo b t a i n e da f t e rc l a s s i f y i n gt h ep o i n t s a c c o r d i n gt od i f f e r e n tc o n t o u r st h e yb e l o n gt o t h ep l a n a rc o n t o u rc a nb eo b t a i n e da f t e r l i n k i n gt h o s ep o i n t ss e q u e n t i a l l y a sc o m p a r e dw i t ht h em e t h o dt h a td i r e c tt r i a n g u l a t i o ni s p e r f o r m e dw i t hr e s p e c tt ot h es u r f a c ep o i n t s ，t h ep r o b l e mo fs o m et r i a n g u l a re l e m e n t s b e i n gi nt h ei n n e rp a r to ft h eo b j e c tc a nb ew e l lr e s o l v e db yt h ee x t r a c t i o no ft h ep l a n a r c o n t o u r , w h i c hi sv e r yh e l p f u lf o rt e x t u r ea t t a c h m e n t f i n a l l y , t h es h a p ea n da p p e a r a n c eo ft h eo b j e c ta r er e s t o r e dw i t ht h et e x t u r em a p p i n g m e t h o d t h et e x t u r ei m a g ei ss e l e c t e da c c o r d i n gt ot h ea n g l eb e t w e e nt h ev i e wp o i n t ( a l s o i l t h r e ed i m e n s i o n a ls u r f a c er e c o n s t r u c t i o nb a s e do ni m a g es e q u e n c e a b s t r a c t c a l l e dt h en o r m a lv e c t o ro ft h ei m a g e ) a n dt h en o r m a lv e c t o ro ft h et r i a n g u l a re l e m e n t t h a ti st h ei m a g ew i t ht h es m a l l e s ta n g l ew i l lb es e l e c t e d a st h et e x t u r e i m a g e c o r r e s p o n d i n gt ot h et r i a n g u l a re l e m e n t c o n s i d e r e d k e y w o r d s ：t h r e ed i m e n s i o n a lr e c o n s t r u c t i o n ，s u r f a c ep o i n t se x t r a c t i o n ，p l a n a r c o n t o u r , t e x t u r em a p p i n g w r i t t e nb y s u p e r v i s e db y y u a nm i a o j i a j u nw a n g 慕十图”序列的三维表血蕈建 第一章绪论 1 1 研究背景及意义 第一章绪论 视觉是人类获取信息强有力而又最有效的手段，人类有8 0 左右的信息都是通过 视觉获取的，人们利用照相机、摄像机等仪器获取信息，对信息进行传输、处理、存 储和理解。用计算机来模拟人的视觉机理获取和处理信息就叫做计算机视觉。 计算机视觉既是工程领域，也是科学领域中的一个富有挑战性的重要研究领域。 它是各个应用领域，如制造业、检验、文档分析、医疗诊断，和军事等领域中各种智 能或自主系统中不可分割的一部分，它对经济和科学研究影响重大。计算机视觉的研 究目标是使计算机或者机器人有着人类相当的视觉能力，能够融合建模、纹理等一系 列图像要素2 3 | 。 计算机视觉的研究起步于六十年代，美国麻省理工学院的r o b e r t 把二维图像分 析推广到三维景物分析，标志着计算机立体视觉技术的诞生h 1 。但是这一时期计算机 视觉的研究并没有取得大的进展，许多重要进展是在八十年代取得的。纵观计算机视 觉发展的近三十年，出现了两个具有罩程碑意义的大事件： 第一个是m a r r 在八十年代初提出的计算视觉理论，使计算机视觉成为- - f - 独立 的科学。他的核心论点是人类视觉的主体是重建可见表面的几何形状，而且这个过程 是可以通过计算实现的。m a r r 的理论第一次清晰地表达了视觉系统要做什么和怎么 做的整体框架哺。 第二个是1 9 9 2 年以来提出的相机自标定和分层重建的思想，使得计算机视觉走 出了低谷。几何计算机视觉也是在这一阶段发展起来的，它在计算机视觉研究中引入 复杂的数学( 尤其是射影几何等) ，对图像进行影射空间到仿射空间最后到欧氏空间的 变换，形成了所谓的“多视图几何州6 | 。分层重建理论得到了认知心理学实验的支持， 是九十年代计算机视觉的引导者。 计算机视觉研究的核心是单幅图像的分割问题、多幅图像的三维重建以及运动的 分割与跟踪问题。三维重建问题是目前研究的热点问题之一，它主要的目的是通过二 维图像中的基元来恢复三维空间，研究的重点是二维图像中点、线、面的二维坐标与 第一章绪论基于图片序列的二维表面重建 对应的三维空间中点、线、面的三维坐标之白j 的关系，实现对物体大小和空问物体的 相互位置关系的定量分析。三维重建属于一个多学科交叉的研究领域，是图像处理和 计算机图形学在工程中的重要应用，涉及数字图像处理、计算机图形学以及工程领域 的相关知识，属于m a r r 计算理论框架中的中级视觉部分。它采用一定的图像处理技 术，比如：关键点匹配、双目重建、表面三角化和三维点拼接技术等，对物体进行重 建。重建的步骤主要包括对图像的特征提取、相机的标定、图像的特征匹配、图像关 键点的重建、三角化以及数据融合等。重建后的效果是可以从任意视点观察物体，都 具有立体的视觉效果。图像三维重建及可视化在遥感、虚拟现实、计算机动漫、医学、 三维测量、计算流体力学、有限元分析、军事模拟等方面都有重要应用。对图像三维 重建的研究，具有重要的学术意义和应用价值。 国外一些发达国家在三维重建方面研究比较多，起步也比较早。比如日本、美国 和英国。东京大学在1 9 9 5 年的就利用物体反射的m a r r a yc o d e d 光源影像对物体表面 进行三维重建并取得进展，这种方法对设备要求较低，操作方便。芝加哥大学在1 9 9 3 年的时候也开始对三维重建进行研究，他们尝试不用传统的网格方式，而使用合理的 高斯曲线和平面来表示复杂图形，利用分散设置的控制点来恢复外形的新方法。1 9 9 5 年美国哥仑比亚大学的c h e h r o u d ib 带领的小组对细胞的形状的三维重建进行了深 入的研究，但是细胞核的形状还是不可预见的。1 9 9 5 年英国的p e a r s o n ，j e r e m yd 小组 对人造电子配件自动检测方面的二维形状测量的阶段测量方法进行了研究，并证明了 用模型方式进行三维形状重建加工过程的可行性口3 。 国内虽然起步较晚，但是也注重这方面的研究，并且也有了一定的成果。比如1 9 9 4 年工程图扫描输入及三维重建方法的研究，被四川省列为基础科研项目；浙江大学 c a d 与计算机图形学国家重点实验室的高玮等人发表了基于二维视图特征的三维重 建的论文；清华大学国家c a d 工程中心的刘世霞等人的基于三维视图形体的重建，分 别从不同方向进行三维重建的研究伸1 。 近年来出现了一些较为成功的三维重建系统。t o m a s i 和k a n a d e 等人提出了第一 个基于图像的三维重建系统蹭1 ；i n r i ab o u g n o u x 等人创建了一个提升型三维重建系 统n 们1 ；k a t h o l i e k e 大学的p o l l e f e y s 等人n 2 1 提出的物体表面自动生成系统运用了可变 内参数下的摄像机自标定技术。最近几年，三维重建技术也成为我国医学研究领域的 新热点，三维重建技术被用于医学体数据研究，通过三维重建模型，不仅可以更清晰地 2 幕十图片序列的三维表面蕈建 第一章绪论 观察分析实际存在的物体形态，而且还可以把临床采集的数据转换为直观图像，这为 医学的临床、教学和科研提供了广阔的应用前景。我困医生采用三维重建和快速自动 成型技术对患者进行颅骨缺损的个性化修复，取得了良好的效果，并已达到国际先进 水平。我国也是继美国和韩国之后第三个开展数字化虚拟人研究并建立虚拟人数据库 的国家。 在c t 、m r j 或d s a 影像指导下，经计算机精确计算和仿真校验后，最后运用新型 高精度脑立体定向手术仪进行各种脑部手术。脑血管疾病、脑血管造影三维重建成像 在脑动脉瘤、颅脑损伤的诊断和治疗中得到广泛应用。透过三维重建手段呈现隧道地 质三维影像，以提供可视化，是近年来计算机图形学的又一个重要应用。将三维重建技 术用于动漫制作也是目前发展的热点之一，三维重构的广泛应用推动动漫产业的不断 发展。三维重建在生活中随处可见，如三维电子地图、三维影视娱乐等，正在不断提 高我们的生活质量。 ” 综上所述，国外在此方向上的研究起步较早，也取得了很多成果。但国内在二维图 形的三维重建上的研究还很少。物体三维重建是计算机辅助几何设计( c a g d ) 、计算 机图形学( c g ) 、计算机动画、计算机视觉、医学图像处理、科学计算和虚拟现实、数 “ 字媒体创作等领域的共性科学问题和核心技术。为了满足面对现代化生产的快速发展 和需要，在此方向上的研究显得十分必要。它不仅在社会生活的各个方面有很大的应 用价值，而且能够节省人力物力，缩短设计周期，提高经济效益，对人工智能的发展 起着决定作用。 1 2 三维表面重建方法及现状 1 2 1 三维表面重建方法 三维重建的目的是建立适合计算机表示和处理的数学模型，是在计算机环境下对 其进行处理、操作和分析其性质的基础，也是在计算机中建立表达客观世界的虚拟现 实的关键技术。但是如何在计算机中对场景进行快速、有效的重建，一直以来都是计 算机视觉研究领域的热点和难点。三维重建是计算机视觉领域中的一个重要研究方 向，它在虚拟现实、物体识别和可视化等方面有着广泛的应用。目前的重建方法很多， 基本可以分为两类：基于几何结构的重建和基于图像的重建。 3 第一章绪论幕十图j i 序列的三维表面蕈建 ( a ) 基于几何结构的重建 基于几何结构的重建是最传统的重建方法，它主要是使用几何建模软件通过人机 交互生成人为控制下的物体三维几何模型。它不涉及真实物体的形状，不需要采集真 实物体的数据，只是采用计算机辅助设计( c a d ) 软件直接手工生成三维实体。现在比 较流行的计算机辅助三维软件有m a y a ，a u t oc a d ，3 dm a x 等。主要应用在绘制图纸， 创建精确的二维图形和三维实体。目前基于几何结构的三维建模的研究已经比较成 熟，该方法建造的场景具有良好的交互性，且视点自由，但真实感不强，采用该方法 进行大规模场景建造时，人机交互工作量大，工作效率低。为了更好地解决问题，人 们提出了基于图像的三维重建。 ( b ) 基于图像的重建 基于图像的三维重建需要采集大量的场景照片，根据获得的图片序列重建出真实 的有场景的三维图像。此方法需要先对场景进行多角度的拍摄，然后应用计算机视觉 的知识和图像的二维信息进行三维图像重建。在进行图像信息的获取时，可以利用精 密的硬件设备，直接测量出物体表面点的三维坐标，进行重建。如雷达图像本身就提 供了各坐标点深度信息，能方便地实现重建的目的。这类方法精度高，对设备的要求 也高，无法在r 常生活中得到广泛的应用。目前广泛应用的图像重建是指利用算法对 获取的二维信息进行三维重建。但是对于不同成像模型下的二维图像，进行三维重建 的方法也是不一样的。如c t 和m 刚是利用间隔切片扫描，形成序列且成比例的若 干二维图像，将这些序列图像按比例放大，再按原间隔距离组合起来，就能实现三维 空间的重建。三维重建必须获得一定的深度信息才能进行，但是对于针孔模型相机， 获取的图像几乎失去了所有的深度信息，也没有比例可言。即便如此，由于其实用、 灵活方便、价格低廉及对设备的要求低，仍是目前使用较多的一种方法，也是最难实 现的一种重建方法。 目前，从图像进行三维表面重建的方法主要有两种：基于灰度信息的重建和基于 立体视觉的重建。 ( 1 ) 基于灰度信息的重建 由明暗恢复形状的方法最早是美国科学家h o r n 为了解决月球表面的重建问题于 上个世纪七十年代末提出的n 引，主要是利用光照模型对图像反射方程进行逆向求解， 所以只需要单幅图像就可以解决表面重建问题。灰度重建主要研究的问题是如何在一 4 基十图”序列的三维表面重建第一章绪论 定的约束条件下从平滑变化的灰度图上恢复出表面取向的信息。它首先要解决的问题 是根据物体表面物理特性的不同，确定合适的反射模型，其次是给出合适的约束条件。 传统的约束条件是假定物体是光滑的，表面高度是连续的，这种约束对大多数物体适 用，但是对于自然景物图表面不一定是连续和光滑的，所以不适用于自然景物图。最 后就是算法复杂度问题，使用灰度重建算法会涉及到很多复杂的数学计算，大规模的 方程组、微积分等。采用该方法的关键在于排除或减轻噪声的影响，这种算法计算量 大、对噪声很敏感，不适用于灰度分布均匀的图像。 ( 2 ) 基于立体视觉的重建 基于立体视觉的重建是模仿人眼的立体视觉过程，基于一帧或多帧共同拍摄的图 像，由其中的二维形状信息恢复原始场景中的三维形状信息的过程。一般处理过程包 括图像配准、相机标定、三维重建。目前主要的基于立体视觉的重建方法有引： ( i ) 程距法：这种方法是直接利用测距仪获得物体的深度信息，用数值逼近的方 ； 法重建物体表面。这种方法适用于户外，是一种主动式的立体视觉方法。 ( i i ) 仅利用一幅图像推断三维形状的方法：该方法依据光学成像的透视原理及统 计假设，根据一幅场景中灰度变化信息导出物体轮廓及表面，从而推断出场景中的物 、 体的三维形状。该方法受到单一图像所能提供信息的局限性，存在难以克服的困难n 引。 ( i i i ) 由两幅或多幅图像重建三维结构的方法：该方法由物体的光照图像恢复外 謦 形，它是一种被动式的立体视觉方法，也是计算机视觉领域的一个重要分支，计算机 视觉研究的热点领域。至今，研究人员己经提出多种从二维图像中恢复三维信息的方 法，比如：直接运用特征点提取的方法进行重建、断层重建、基于八叉树的表面重建 等。 1 2 2 三维表面重建研究现状 目前，基于图像的三维表面重建是研究热点，它主要是从图像的2 d 信息恢复出 3 d 信息。近年来，八叉树算法的应用n 引，使得三维重建迈向一个新的台阶。其中， 文献 1 7 提出了快速八叉树算法，该方法在二维图像平面中根据二值图像的棋盘距离 和八叉树顶点到中心的距离大小，判断八叉树是否可以再分。利用这种方法速度快， 效果好，容易实现并且在一定程度上减少了点的数目提高了运行效率，但是此方法得 第一章绪论基于圈j f 序列的二三维表面重建 到的三维模型既包括物体表面也包括物体内部，其牵涉到的点的数目仍然较大。文献 1 8 运用了断层重建算法，该算法利用c t 得到精确的断层数据，然后进行轮廓的拼 接和连接。断层重建在医学上的作用越来越重要，目前荧光分子的断层重建有助于发 现早期的病变细胞，有利于癌症的早期诊断。哈佛大学医学院建立了3 6 0 。非接触式 的f m t ( f l u o r e s c e n c em o l e c u l a r t o m o g r a p h y ) 系统n9 2 引。我国清华大学的白净教授利用光 学成像技术和c t 技术相结合，重建物体轮廓晗。这些技术虽然在重建精度上分辨率 高，但是成本高，耗时长，需要专门的设备和专业操作人员。所以，找到一种成本低、 数据精简的重建方法是研究的目标。 1 3 本文主要工作 基于两幅或多幅图像进行重建是计算机视觉的关键组成部分，也是目前研究的热 点，八叉树重建是一种应用广泛的三维重建方法。 首先，本文根据非透明物体内部不可见的实际，提出了一种基于图片序列的三维 表面重建算法。该算法首先利用传统的八叉树算法重建出物体的三维模型，然后利用 一种新颖的表面点提取算法提取出物体表面点，最后利用这些表面点进行三角网格剖 分，进而重建出光滑的三维物体表面。 其次，本文采用了断层重建的思想。在对提取出的表面点直接进行网格剖分时， 会存在一些内部网格，不利于张贴纹理，这时候采用断层重建避免了此类问题的出现。 根据八叉树重建中立方体的不同大小选取不同间隔的平面，截取立方体，进一步提取 出物体断层边缘点，并根据立方体的连通性把轮廓进行分类，得到每层的轮廓数，以 及每个轮廓所对应的点。 再次，把相邻轮廓进行拼接，得到三角片面。在轮廓的拼接过程中，解决轮廓的 对应问题以及分支问题。 最后，进行纹理映射。计算出每个三角面片的法向量与图像平面的法向量之间的 夹角，择其夹角最小的那幅图像作为该面片所对应的纹理图像。 1 4 本文的组织结构 本文的内容组织如下： 6 暴f 图片序列的三维表面重建第一章绪论 第一章绪论：介绍了三维表面重建的发展背景和意义，目前主要的重建方法和 研究现状及本文主要工作。 第二章基于八叉树的三维重建及其表面点的提取：本章主要讲述传统的八叉树 算法的实现过程，以及八叉树重建后的三维模型表面点的提取方法，本文提出了一种 新颖的表面点提取算法，能有效的提取出表面点。 第三章基于断层的三维表面重建：本章主要对八叉树重建出的物体模型进行断 层分割，然后提取出边缘和轮廓并进行拼接，得到表面三角片面。 第四章纹理张贴：本章主要讲述纹理的映射算法，并恢复出物体的外貌。 第五章总结和展望：总结本文的研究工作，并阐述了未来的工作和研究内容。 第一二章基于八叉树的三维系建及j e 表面点的提取 基于图j 1 序列的三维表面章建 第二章基于八叉树的三维重建及其表面点的提取 2 1 八叉树重建算法思想 目前，三维重建的方法很多，比如直接运用特征点提取方法进行重建他2 1 、断层重 建瞳3 1 等。其中八叉树重建是一种应用广泛的三维重建方法，它需要从物体周围3 6 0 。 拍摄不同视点方向的图片序列，重建三维模型口4 绷，是立体视觉的一种。 传统的八又树算法可以分为两类：在三维空间汹2 7 1 和在二维平面陋5 朋1 进行重建。 在二维平面中处理维数较低，比在三维空间中更有效啪1 ，而且处理过程简单。八叉树 重建的基本思想是：首先定义一个能完全包围物体的立方体，并把其记录为根节点。 如果此立方体恰好被物体完全填充，则标记为黑色，如果完全没有被物体填充，则标 记为白色，并称黑色和白色立方体为均质立方体，其他状态的立方体称为非均质立方 体，并标记为灰色，算法过程主要是对非均质立方体进行。如果根节点是灰色节点， 则在包围物体的三维空间内平均分为8 个小立方体，每个小立方体为原来立方体的子 节点，并对每个子节点进行检测，判断其是否为均质：如果子立方体已经为均质，可 停止分解；否则，继续分解成八个卦限，直到所有立方体为均质，或是达到限定的误 差范围即停止分解。八叉树算法数据结构简单，各元素按空问位置排成一定的顺序， 顶点坐标确定，容易找到其所在的空间位置。实现步骤如图2 1 所示： 图2 1 八叉树分解流程图 图2 2 是用八叉树表示三维物体的一个例子。八叉树算法数据结构简单，各元素 按空间位置排成一定的顺序，顶点坐标确定，容易找到其所在的空间位置1 。 8 摹十幽片序列的二三维表面直建第二章幕于八叉树的三维系建及j 表面点的提取 图2 2 一个简单两层八义树的表示 传统的方法得到的立方体的数量大，为了降低复杂度，提高运行效率，文献 1 7 提出了快速八叉树重建算法。此算法利用棋盘距离作为在二维平面上的相交测试依 据，八叉树的分解层数不固定，按照预测误差决定是否继续分解，当误差达到一定程 度则停止分解，不需要分解到最底层。该方法速度快，效果好，容易实现并且在一定 程度上减少了点的数目并提高了运行效率。 2 2 八叉树重建过程 2 2 1 相机标定 相机标定是使空间坐标系和像素坐标系之间相互转化，建立三维世界坐标与二维 图像坐标之间的一种对应关系，它既和相机本身的内部参数有关( 如焦距) ，也和外 部参数有关。最经典的算法有t s a i 两步法m 3 订和张正友平面法m 2 i 。本文采用的是张 正友的经典标定方法副，此方法采用理想状态下的相机模型，即线性模型。 z c 图2 3 理想的相机模型 在图2 3 理想的相机模型中，q 称为相机光心，光轴q z c 与图像平面的交点q 9 第二章基于八叉树的三维重建及其表面点的提取基于图片序列的三维表面重建 为图像坐标系原点，直角坐标系q 置e z c 称为相机坐标系，d h ，咒e 乙为世界坐标系， q q 为像机焦距。根据文献 3 4 ，3 5 把世界坐标系中的物体坐标( k e ，z 。) 转换到像 素坐标系中的像素坐标以谚，转换关系为公式( 2 1 ) ，其中m 为标定矩阵。 l 聊11 m = l 所2 l m 1 2m 1 3m 1 4 m 2 2m 2 3m 2 4 m 3 1m 3 2m 3 3m 3 4 ：m l 蜥 z w l ( 2 1 ) 如果有个点就可以得到2 n 个线性方程，当2 n 1 1 ，即选取的点超过6 个点时，可 用最小二乘法求解，得到中m 的参数值。 在本实验中，图2 4 中的黑白棋盘格作为标定板，选取棋盘格上已知三维坐标点 进行相机标定。根据文中的方法，标定的结果如表2 1 所示。 图2 4 试验中的标定板 l o 皋十图”序列的二维表面重建第二章基于八又树的三维重建及j e 表面点的提取 表2 1 相机标定数据误差 真实世界坐标像素坐标计算出的世界坐标 ( 3 0 ，0 ，1 0 ) ( 3 1 6 ，5 3 6 )( 3 1 6 0 8 ，5 3 6 5 8 ) ( 1 0 ，0 ，3 0 )( 4 2 6 ，5 5 6 )( 4 2 5 4 8 ，5 5 7 8 3 ) ( 2 0 ，0 ，6 0 )( 6 1 4 ，5 5 2 )( 6 1 1 8 1 ，5 5 0 0 9 ) ( 1 0 0 ，2 0 ，8 0 ) ( 6 6 3 ，4 0 8 )( 6 6 3 2 2 ，4 1 0 2 3 ) ( 1 0 0 ，4 0 ，6 0 ) ( 5 7 9 ，3 2 3 )( 5 7 8 6 6 ，3 2 3 4 1 ) ( 1 0 0 ，4 0 ，2 0 )( 4 0 6 ，3 2 1 ) ( 4 0 7 0 0 ，3 2 0 5 7 ) ( 1 0 0 ，6 0 ，4 0 )( 4 9 4 ，2 3 6 )( 4 9 3 9 4 ，2 3 6 4 1 ) ( 3 0 ，0 ，9 0 )( 7 7 7 ，5 4 4 )( 7 7 8 8 7 ，5 4 3 1 5 ) 从表中可以看出，通过最小二乘法算出的结果和真实坐标相差很小，精度已经达 到要求。 2 2 2 二值图像的棋盘距离 一幅数字图像是一个二维阵列，阵列元素值称为灰度值或亮度值。只有黑白两级 臂 灰度的图像，分别用0 和1 表示，叫做二值图像。二值图像既可以去掉无关信息的干 扰，方便几何与拓扑特性的表示与分析，又可以节省存储空间。 二值图像的棋盘距离定义为：对于像素坐标为( “，1 ，) 的像素p ，查找其周围与p 像 素取值相同的像素坐标，形成中心在( 甜，1 ，) 的正方形的边长最大值一6 1 。 一幅二值图像如图2 5 ( a ) 所示，其棋盘距离表示如2 5 ( b ) 所示b 7 圳。 oo00000 o1ll1lo 011l110 ol 1 1 l l o 0 ll1110 o1l111o o0o0o00 ( a ) 二值图像 0000oo0 01l1llo 0122210 012 321o 012 22l0 o11lll0 000o0oo ( b ) 棋盘距离 图2 5 二值图像及其棋盘距离表示 第一二章桀于八又树的二维重建及j e 表面点的提取基十图j l 序列的三维表面重建 2 2 3 八叉树分解 在进行八叉树重建的过程中，参考了文献 1 7 的方法，假设总共有n 幅图片，a 是任意一个非均质的立方体，4 ( f ：lo * o n ) 是这个立方体在每个视点方向的二维投影， s ( f = 9o ) 是物体的二维灰度图像。具体算法如下： 算法2 1 步骤1 ：把原始的图像处理成二值图像，并计算出每个像素点只，的棋盘距离 d 西t m a p , ( p , j ) 。 。 步骤2 ：非均质的立方体三维顶点坐标为( _ ，m ，毛) ( x 。，y s ，z 。) ，根据相机的定 标矩阵，建立二维图像平面和三维物体空间的联系，使立方体八个顶点的三维坐标投 影到n 幅二维平面图像上，分别为( z ，们v j l ) ( 8 ，v 8 ) ( 待l ) 。 步骤3 ：对于每一幅图像平面，计算( 甜肿。) ( 珥。，v 。) ( 江1 n ) 的中心点 ( 掰，o ，v o ) ： 甜f o2 ( “f l + u i 2 + u i 3 + u i 4 + u i 5 + u i 6 + u i 7 + u i 8 ) 8 ( 2 2 ) ，o = ( v f l + _ 2 + v f 3 + _ 4 + _ 5 + _ 6 + _ 7 十v f 8 ) 8 ( 2 3 ) 其中f = l n ，且定义q ( z ，。，v 。) 为中心点。 步骤4 ：计算( ，v 。) ( 8 ，v ，8 ) ( f = l ) 到q 的距离： 口l = ( l 一坞o ) 2 + ( v j l - v , o ) 2 ： ( 2 4 ) d j 8 = ( “f 8 一o ) 2 + ( v f 8 - - 1 , , i o ) 2 并取口，口。之间的最大值m a x ( d 一d ，。) 为圆的半径，q 为圆心定义一个圆。 步骤5 ：定义q = ，：一d i s t m a p , ( c ，) ，其中d i s t m a p , ( q ) 为e l 点的棋盘距离： ( a ) 如果对于所有的i = l n ，都有e i 限定误差，则此立方体为均质的黑色立 方体，记录其信息，无需再进行分解； ( b ) 如果存在q 限定误差，则此立方体为非均质的，继续进行分解； 通过以上步骤的计算，显示出均质的黑色立方体即为所要重建物体的三维模型。 1 2 甚十l 型”序列的二三维表面重建第二章摹于八叉树的三维重建及j 表面点的提取 2 3 三维表面重建 表面重建算法包括基于八叉树的三维重建、表面点的提取、以及表面的三角剖分 等几个部分。算法框图如图2 6 所示： 2 4 表面点提取 i由相机获得3 6 0 。的图片序列 上 根据八叉树重建原理重建物体， 并对得到的立方体进行编号，对 顶点进行排序。 1 l 屎用包闸盒划分立方体，对立方体按 i空问分类，得到其近邻集。 1 l 在近邻集中对立方体顶点进行打 分，判断出顶点的状态，并提取 出表面点。 土 对表面点进行三角剖分， 重建出物体表面。 2 4 1 表面点的确定 图2 6 系统实现框图 得到立方体表示的物体之后，一方面，点的数量很大，而且直接用立方体堆积起 来的物体表面不光滑；另一方面，考虑到对于一般的非透明物体，其内部是不可见的， 因此可以只考虑其表面轮廓状况而忽略其内部点。只要在提取出物体的表面点之后进 行表面三角网格剖分，就可以取得比直接八叉树重建更好的平滑效果，而且点的数量 可大幅度减少，更有利于进行纹理映射。但是，目前还缺乏提取表面点的有效方法。 为此，本文对物体的内部点和表面点进行了仔细的分析，并在此基础上提出了一种新 第_ 二章摹于八叉树的二三维重建及j 表面点的提取幕f 图i 序列的二三维表面重建 颖的表面点提取算法。经过分析，本文将物体的内部点分为如图2 7 所示的六种情况， 其中点1 为内部点。图2 7 ( a ) 给出了内部点为8 个立方体的公共顶点的情况，图2 7 ( b ) 表 示了内部点为6 个立方体的公共顶点且位于1 个立方体的棱上的( 不包括顶点) 情况， 图2 7 ( c ) 给出了内部点是4 个立方体的公共顶点且位于2 个立方体的棱上的情况，图 2 7 ( d ) 中的内部点则是2 个立方体的公共项点，且位于1 个立方体的棱上以及1 个立方体 的面上( 不包含面的边缘) ，图2 7 ( e ) 中的内部点是4 个立方体的公共顶点且位于1 个立 方体的面上，图2 7 ( f ) n 给出了内部点是2 个立方体的公共顶点且位于3 个立方体的棱 上的情形。 露一 ( a ) ( c ) ( f ) ( d ) ( g ) 图2 7 内部点的种点情况 为了区分内部点和外部点，本文提出根据点的不同状态( 处于立方体的顶点、棱、 面) 赋予不同的权值，并通过计算点所占不同立方体的顶点、棱、面的数目对其进行 打分。首先，如果一个点处于某个立方体的顶点，则赋予权重9 0 。：其次，如果一个 点处于某个立方体的棱上，则由于一条棱具有两个顶点，故赋予权重1 8 0 。；最后， 如果一个点处于某个立方体的面上，则由于一个面含有四个顶点，故赋予权重3 6 0 。 为方便起见，用n 。表示以某点为公共顶点的立方体的个数，用行：表示以该点所在的棱 为公共棱的立方体的个数，表示以该点所在的面为公共面的立方体的个数。用 1 4 皋f 图j i 序列的二三维表面重建第_ 二章基于八又树的三维蕈建及j 表面点的提取 m ，w 3 分别表示对应于顶点、棱以及面的权重。表2 2 给出了内部点的六种情况下 ，2 l ，吃，他的取值及顶点、棱以及面所对应的权重。 表2 2 内部点的分布特点 内 9 0 0 w 2 1 8 0 。 w 3 3 6 0 0 部 点总分值 情 ，z l 胛2 圪 况 a8o07 2 0 0 b6lo7 2 0 0 c4207 2 0 。 d 2l17 2 0 0 e4o17 2 0 。 f2307 2 0 0 表2 2 中的总分值s 按如下方式计算： s = w i n l + 比他+ w 3 绝 ( 2 5 ) 由表2 2 可知，所有内部点的总分值都是7 2 0 。经过分析，所有表面点的s 值均小于 7 2 0 。，而且不可能存在s 值大于7 2 0 。的情形。所以可以用s 的取值作为判据，判断 一个点是否为表面点：如果s 7 2 0 。，则该点为表面点，否则为内部点。通过实验可 知，对不同重建目标利用本文算法进行精简，点的精简率均达到了9 0 以上，极大地 减少了点的数目。 2 4 2 立方体邻集的确定 在利用上述思想确定表面点的过程中，关键在于确定隅，编的取值。但是，由 于八叉树分解后所得到的立方体数量非常庞大，因此，在表面点的提取过程中，如果 把任意一点和其余所有立方体进行比较，其运算量非常巨大。另一方面，由于每个点 的状态只与其附近的立方体有关，因此只要将点与附近的立方体进行比较，就可以判 断出点的状态，这样可以大幅度减少计算量，节省计算时间。为了找到每个立方体的 邻集，本文借鉴了对三维散乱点集进行包围盒划分的思想钏，对立方体进行包围盒划 分，将大小不均的立方体划分为数据区域，从而确定每个立方体的邻集。在坐标 x 、y 、z 轴方向分别取，聊玎个包围盒，并对包围盒进行编号，则总的包围盒个数为 第一二章基于八叉树的三维霞建及j e 表面点的提取 基于图片序列的t 维表面重建 j 优，z 。利用包围盒思想确定立方体邻集的算法如下： 算法2 2 步骤1 ：选取立方体置( i = 0 n ，n 为生成的八叉树中立方体的个数) ，确定所 在的包围盒编号以及每个包围盒中立方体的编号，并使其对应起来； 步骤2 ：根据立方体的编号，找到它所在的包围盒及其2 6 个邻域包围盒的编号，进 一步确定每个立方体邻域中所有立方体的编号： 步骤3 ：重复，x m x 刀次步骤1 和步骤2 ，即可以找到所有的邻集。 利用上述算法，会出现一个立方体不完全属于一个包围盒，而是跨越两个或两个 以上包围盒的情况。对于这种情况，如果一个立方体跨越两个包围盒，则计算此立方 体离哪个包围盒中心更近，并把其归为中心较近的包围盒中；如果一个立方体跨越三 个或三个以上的包围盒，则把此类立方体单独归为一类，不属于任何包围盒，在进行 点的判别过程中，每个点都要和此类立方体进行比较，由于这类立方体数目较少，对 计算的速度影响不大。 2 4 3 表面点提取算法 根据以上的讨论，表面点的提取算法概括如下： 算法2 3 步骤1 ：对于由立方体表示的物体的任一顶点，利用算法2 2 确定该顶