（计算机软件与理论专业论文）三维重建应用系统研究.pdf

山东大学博士学位论文 摘要 物体三维重建是指对三维物体建立适合计算机表示和处理的数学模型，是在 计算机环境下对其进行处理、操作和分析其性质的基础，也是在计算机中建立表 达客观世界的虚拟现实的关键技术。因此，物体三维重建是计算机辅助几何设计 ( c a g d ) 、计算机图形学( c g ) 、计算机动画、计算机视觉、医学图像处理、 科学计算和虚拟现实、数字媒体创作等领域的共性科学问题和核心技术。 在计算机内生成物体三维表示主要有两类方法。一类是使用几何建模软件通 过人机交互生成人为控制下的物体三维几何模型，另一类是通过一定的手段获取 真实物体的几何形状。前者实现技术已经十分成熟，现有若干软件支持，比如： 3 d s m a x 、m a y a 、a u t o c a d 、u g 等等，它们一般使用具有数学表达式的曲线 曲面表示几何形状。后者一般称为三维重建过程，三维重建是指利用二维投影恢 复物体三维信息( 形状等) 的数学过程和计算机技术，包括数据获取、预处理、 点云拼接和特征分析等步骤。本文建立了一套独立的以三维重建为核心的应用系 统，实现了基于三维扫描的建模模块、三维碎片拼接模块、三维人脸识别模块以 及基于二维编辑的三维造型后处理功能；同时将基于鱼眼镜头的双目视觉算法与 三维重建进行了融合。其中三维建模和三维点云数据特征分析是至关重要的部 分，也是本文研究的重点内容。 本文的工作以国家自然科学基金课题“基于海量数据点的三维表示中的关键 问题研究、山东自然科学基金课题“海量数据处理中的高精度三维表示问题研 究”等重点课题为依托，讨论了这个领域中的一系列关键问题。这些问题包括： 三维扫描过程分析、三维面片数据拼接、空间点云几何不变量研究、双目视觉与 全景技术融合进行三维重建以及基于二维编辑的三维造型技术等。具体说来，主 要贡献包括以下几点： ( 1 ) 实现了基于白光结构光栅的非接触式三维扫描仪，为三维重建和后续 工作提供了丰富和精确的数据。普通镜头存在多种几何畸变，严重影响实验数据 的获取；而边缘检测的策略也直接影响到了深度数据的精确性。在这个阶段的工 作中主要提出了迭代式镜头几何校正算法、结构光栅图像亚像素精度边缘检测算 山东大学博士学位论文 法，并实现r 空间散乱点云数据的血片口j 视化。 ( 2 ) 提出了一种基于导数动态时间规整( d d t w ) 的三维碎片自动拼接方 法，可以计算两块碎片之间最优的拼接方式。同时设计了一种基于抗噪区间拟合 的挠率估计方法和常数时间复杂度的三维重叠检测方法，大幅度提高了拼接的速 度和准确性。首先确定物体碎片的轮廓曲线，查找角点，根据角点将轮廓曲线分 段成子轮廓线，计算子轮廓曲线的挠率特征串；然后使用d d t w 对两个特征串 进行匹配，并给出匹配度的度量值，继而根据对应点的空间位置关系对碎片进行 放缩和刚体变换，调用三维重叠检测方法排除重叠匹配；最后根据给定的评价标 准找到最优匹配作为最终拼接结果。实验表明，该方法实现简单，鲁棒性强，能 快速得到三维碎片集合的拼接结果。 ( 3 ) 对三维空间点云数据进行几何特征分析，找到了人脸表情无关的几何 特征不变量。使得人脸在不同表情下扫描获得的空间数据最终能够表示为统一的 形式，很大程度上排除了表情对人脸三维空间数据表示的影响，建立了三维人脸 数据库，实现了基于三维扫描表情无关的人脸识别系统，为身份验证和安全保障 工作提供了新的思路和方式。 ( 4 ) 研究了全景图自动拼接的方式方法，提出了基于图像变形的图像自动 匹配算法，实现了基于鱼眼镜头和数码相机多幅图像的自动拼接，获得了竖直视 角1 8 0 度、水平视角3 6 0 度的全景浏览。在此基础上改变全景拍摄高度，可以获 得在不同拍摄点对同一场景拍摄的不同视角的全景图片。利用双目视觉的有关原 理，以多视角全景图为数据，实现了场景三维点云数据场的重建，为现场保留、 重现工作提供了强有力的技术支持。这项工作也可以作为三维重建中一个新的分 支。 ( 5 ) 做为三维重建系统的有益补充，本文提出了基于二维图像编辑的三维 表面造型方法。利用简单和通用的二维平面编辑操作进行三维表面造型定义，然 后建立二维平面坐标系与三维几何体表面区域的映射关系，最终将造型定义展现 到三维几何体表面。 关键词：三维重建；三维扫描；几何特征：三维拼接；三维匹配；几何不变量； 全景拼接；人脸识别 山东大学博士学位论文 a b s t r a c t 3 dc o n s t r u c t i o nf o ro b j e c t sm e a n st oc r e a t em a t h e m a t i c a lm o d e l sf o r3 do b j e c t s w h i c ha r es u i t a b l ef o rc o m p u t e rt or e p r e s e n ta n dp r o c e s s i ti st h eb a s ef o rd a t a p r o c e s s ，m a n a g e m e n ta n da n a l y s i s i nc o m p u t e re n v i r o n m e n t i ti sa l s ot h ek e y t e c h n o l o g y i n c r e a t i n g v i r t u a lr e a l i t yt oe x p r e s st h ee 赋e m a lw o r l d s o3 d r e c o n s t r u c t i o nf o ro b j e c t si st h ec o m m o ms c i e n c ep r o b l e ma n dk e yt e c h n o l o g yi n m a n yd o m a i n s ，i n c l u d i n gc o m p u t e ra i d e dg e o m e t r i cd e s i g n ( c a g d ) ，c o m p u t e r g r a p h i c s ( c o ) ，c o m p u t e ra n i m a t i o n ，c o m p u t e rv i s i o n ，m e d i c a li m a g ep r o c e s s i n g ， s c i e n c ec a l c d a f i o n ，v i r t u a lr e a l i t ya n dd i g i t a lm e d i ai n v e n t i o n ，e t c t h e r ea r et w ok i n d so fa p p r o a c h st og e n e r a t e3 dr e p r e s e n t a t i o nf o ro b j e c t s o n e w a yi s t oi n t e r a c tw i t l lg e o m e t r i cm o d e l i n gs o f t w a r et og e n e r a t e3 dg e o m e t r i c m o d e l sf o ro b je c t sa c c o r d i n gt om a n u a ld e s i g n t h eo t h e rw a yi st oo b t a i nr a n g ed a t a f r o mr e a lo b je c t s t h ef o r m e ri sm o r em a t u r e ，a n dh a sr i c hs o f t w a r es u p p o r t ，s u c ha s ： 3 d s m a x ，m a y a , a u t o c a da n du g ，e t c t l l e yd e s c r i b eo b j e c t sw i t hc u r v e sa n d s u r f a c e sd e f i n e db ym a t h e m a t i ce x p r e s s i o n s g e n e r a l l y ，t h el a t t e ra p p r o a c hi sc a l l e d a3 dr e c o n s t r u c t i o nw h i c hm e a n st or e s u m e3 di n f o r m a t i o no fo b je c t sf r o mt h e i r2 d p r o j e c t i o ni m a g e s i ti n v o l v e ss e v e r a lf u n c t i o nm o d u l e s ，s u c ha sd a t ao b t a i n i n g , d a t a p r e p r o c e s s i n g ，d a t ac l o u dr e - a s s e m b l ya n dg e o m e t r i cf e a t u r ea n a l y s i s o u rw o r k i st o c o n s t r u c taw h o l e3 dr e c o n s t r u c t i o na p p l i c a t i o ns y s t e m , i n c l u d i n g3 dm o d e l i n g m o d u l e ，3 df r a g m e n tr e - a s s e m b l ym o d u l e ，3 df a c er e c o g n i t i o nm o d u l ea n d3 d s h a p i n gm o d u l eb a s e do n2 de d i t i n g s i m u l t a n e o u s l y ，w em a k eaf u s i o no fs t e r e o v i s i o na n d3 dr e c o n s t r u c t i o n a m o n gt h e m , t h e3 dr e c o n s t r u c t i o na n dr a n g ed a t a p o i n tc l o u df e a t u r e a n a l y s i ss e e mt ob em o r ei m p o r t a n tw h i c ha r ea d d r e s s e di nt h i s p a p e ra sk e yp o i n t s i nt h i sp a p e r ，w eo r g a n i z es o m er e s e a r c hw o r kd o n ew i t hs u p p o r to f r e s e a r c h o i lk e yp r o b l e m si n3 dr e p r e s e n t a t i o nb a s e do nm a s s 砌珂b yt h en a t i o n a ln a t u r a l s c i e n c ef u n d sa n d r e s e a r c ho np r o b l e m si na c c u r a t e3 1 9r e p r e s e n t a t i o nd u r i n gm a s s d a t ap r o c e s s i n b yt h es h a n d o n gp r o v i n c en a t u r a ls c i e n c ef u n d s t h ek e yr e s e a r c h p o i n t si n c l u d e ：t h ep r o c e s sa n a l y s i s o f3 ds c a n n i n g ，3 df r a g m e n t sa u t o m a t i c r e a s s e m b l y ，g e o m e t r yi n v a r i a n to f3 dr a n g ep o i n td a t ac l o u da n dt h em e r g eo f s t e r e o 1 1 1 山东大学博士学位论文 v i s i o na n dp a n o r a m as t i t c h i n g ，e t c s p e c i f i c a l l y ，山e ya r el i s t e da sf o l l o w f i r s t ，aw h o l es t r u c t u r e dw h i t el i g h tb a s e du n t o u c h i n g3 ds c a n n i n gs y s t e mi s i m p l e m e n t e d i ta n dc a np r o v i d er i c ha n da c c u r a t ed a t af o r3 dr e c o n s t r u c t i o na n d o t h e rr e l a t e dw o r k c o m m o nl e n sh a s g r e a t eg e o m e t r yd i s t o r t i o n ，w h i c hc a na f f e c tt h e q u a l i t yo fs c a nd a t ab a d l y a n dt h ee d g ed e t e c t i o na l g o r i t h mw i l la l s od e t e r m i n et h e a c c u r a c yo fr a n g ed a t a h e r e ，a ni t e r a t i v em e t h o di sc a r r i e do u tt op e r f o r mt h e a u t o m a t i cl e n sc a l i b r a t i o n t h e nad a t a - f i t t i n gb a s e dm e t h o di sp r o p o s e dt oi m p r o v e t h ea c c u r a c yo f s u b p i x e le d g ed e t e c t i o n f i n a l l y ，t h ev i s u a l i z a t i o no ft h ed a t ac l o u di s g i v e n s e c o n d ，w ep r e s e n ta na u t o m a t i cr e a s s e m b l ym e t h o df o rm a t c h i n g3 df r a g m e n t s ， w h i c hc a nc o m p u t et h eb e s tm a t c ho fap a i ro fb r o k e np i e c e s t oi m p r o v e s p e e da n d a c c u r a c y ，w eg i v eat o r s i o ne s t i m a t i o nm e t h o db a s e do na n t i n o i s es e c t i o na n daf i x e d c o n s t a n tt i m ec o s t3 d o v e r l a p p i n gt e s tm e t h o d f i r s t , t h ec o n t o u rc u r v e so ff r a g m e n t s a r ef o u n d ，t h e nt h ec o m e rp o i n t s c o n t o u rc u r v e sa r ed i v i d e di n t os e v e r a l s u b - c o n t o u r s s e c o n d ，t h et o r s i o ns e q u e n c e sa r eo b t a i n e df o rt h ed d t wb a s e d m a t c h i n gw o r k t h u s ，t h es c a l ea n dt r a n s l a t i o nm a t r i x e sc a nb ec o m p u t e dt oc h a n g e t h es i z ea n dp o s i t i o no fo n ef r a g m e n t b e s tm a t c h i n gr e s u l tw i l lb ef i n a l l yc h o s e n a c c o r d i n gt om a t c h i n gt e s ta n de x t r ae v a l u a t i o n s e x p e r i m e n tr e s u l t ss h o wt h a tt h i s m e t h o di ss i m p l ea n dr o b u s t ，a n dc a ng e tp r o p e rm a t c h i n gr e s u l t sq u i c k l y t h i r d ，t h ee x p r e s s i o ni g n o r e di n v a r i a n to f3 df a c es c a nd a t ai sd i s c o v e r e dd u r i n g t h ef e a t u r ea n a l y s i so n3 dr a n g ed a t ap o i n tc l o u d t h i sm a k e si tp o s s i b l et h a tf a c e s u r f a c ed a t a 谢t hd i f f e r e n te x p r e s s i o n sc a r ls h a r eau n i f o r md a t ap r e s e n t a t i o n t h i sc a n h e l pt oi d e n t i f yh u m a nf a c en om a t t e rw h a te x p r e s s i o nh em a k e s t h e na3 dh u m a n f a c ed a t a b a s ei ss e t u pa n ds e r v e sap r a c t i c a lf a c er e c o g n i t i o ns y s t e m t h e s ee f f o r t s p r o v i d en e wt h o u g h t sa n df a s h i o n st oi d e n t i t yr e c o g n i t i o na n ds e c u r i t yg u a r a n t e e a p p l i c a t i o n s f o u r t h ，a na u t o m i t i cp a n o r a m as t i t c h i n gm e t h o di sc a r r i e do u t a ni m a g e t r a n s f o r m a t i o nb a s e dm e t h o di sp r o p o s e dt op r o v i d ea u t o m a t i cs t i t c h i n gf o rf i s h - e y e p a n o r a m ap i c t u r e s t h u s ，w i t haf i s h - e y el e n sa n dac o m m o nd i g i t a lc a m e r a ，p e o p l e c a ng e taw h o l ep a n o r a m ap i c t u r ee a s i l y ，w h i c hc a l lc o v e r18 0d e g r e e sv e r t i c a l l ya n d 36 0d e g r e e sh o r i z o n t a l l y t h e nt h ec a p t u r ep o s i t i o ni sc h a n g e d s oa p a i ro fp i c t u r e s 谢md i f f e r e n tv i e wa n g l ei st a k e n t h es t e r e ov i s i o na l g o r i t h mi sa l s oc o m b i n e di nt h e a p p l i c a t i o nt oo b t a i nt h e3 dr a n g ed a t ac l o u do ft h es c e n e t h i sw o r ki sv e r yu s e f u l 山东大学博士学位论文 f o rs c e n er e s e r v a t i o na n dr e v i e w t h i sr e s e a r c hc a r la l s ob er e g a r d e da san e wb r a n c h o f3 dr e c o n s t r u c t i o n f i n a l l y ，t op r o v i d ea d d i t i o n a la b i l i t yt om , a i l i p u l a t e3 ds h a p e , w ei m p l e m e n ta3 d e d i t i n gm e t h o db a s eo n2 dd r a w i n g 3 ds h a p ec a l lb ed e f i n e di n2 dd o m a i ni ns i m p l e a n d g e n e r a lw a y s ，a n dt h e nc r e a t eam a p p i n gf r o m2 dd o m a i nt o3 dd o m a i n ，t h u st h e s h a p ed e f i n i t i o nc a nb ep r e s e n t e do nt h es u r f a c eo ft h e3 dg e o m e t r ym o d e la s3 d s h a p e s k e yw o r d s ：3 dr e c o n s t r u c t i o n ；3 ds c a n ；g e o m e t r yf e a t u r ea n a l y s i s ；3 d s t i t c h i n g ；3 dm a t c h i n g ；g e o m e t r yi n v a r i a n t ；p a n o r a m a s t i t c h i n g ；f a c e r e c o g n i t i o n v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 鸯鱼。1日期：跫! 缘堑丑2 1 回 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：；萤纠导师签名： 期：雄j 刁岁曰 山东大学博士学位论文 1 1 研究背景 第1 章绪论 物体三维重建是指为其建立适合计算机表示和处理的数学模型，是在计算机 环境下对三维物体进行处理、操作和分析其性质的基础，也是在计算机中建立表 达客观世界的虚拟现实的关键技术。随着信息技术的飞速发展，如何在计算机上 实时逼真地建立客观世界的虚拟海量信息空间，生成具有重要价值的三维形状信 息，运用计算机的高性能数据存贮、压缩、计算和传输能力，快速有效地实现对 这些三维形状信息的分析、挖掘、检索和高效利用，已经成为国家、社会和科技 发展中许多重大应用需求的关键科学问题。 国内外已经出现了若干专业人员致力于物体三维重建的研究。根据硬件使用 的不同，目前的三维重建主要包含四类方式：第一类是根据三维物体的断层扫面 所得二维图像提取轮廓，然后根据一定的原则进行相邻两个轮廓的连接和三角 化，从而得到物体表面形状。该方法主要用于对物体内部构造进行拓扑结构可视 化，比如：医学影像的三维重建、深埋管道器件的外部检测等。第二类是使用探 针或激光读数器逐点获取数据，然后进行整体三角化，此类方法测量精确，但速 度很慢，难以在短时间内获得大量数据。第三类是基于双目视觉的重建方式，深 度数据计算精度较低，主要应用于机器人视觉领域。最后一类就是应用硬件光学 三维扫描仪主动获得物体的点云数据，然后进行重建获得物体的整体表面信息。 其中基于光学三维扫描仪的重建方法应用范围最为广泛，同时也是本文研究的主 要内容。其应用领域主要包括： ( 1 ) 制造业与逆向工程 在当代制造业中，某些部件需要创作者手工完成创作或需要根据现有形体仿 制，然后以原始模型为基础经过若干次倒模操作实现最终真实部件的生产，这个 过程需要耗费大量的物质制作模具和倒模材料，同时因为倒模的不精确性会使倒 出的模子出现很多粗糙的细节甚至变形，又需要手工修正和琢磨，进而更多的浪 费人力物力。应用三维重建技术，可以将创作者完成的设计模型准确的变为计算 山东大学博士学位论文 机中的三维实体模型，如果有需要也町以在计算机中完成修正操作，最后由计算 机根据实体模型数据控制加工设备完成部件加工，此过程省去了传统设计制作过 程中若干复杂环节，大大的节省了开发成本。这个过程一般称为逆向工程。 ( 2 ) 建筑行业与土木工程 对建筑物如桥梁、工厂、纪念碑等大型建筑的重绘、质量控制等也有一定的 辅助作用。例如某处有一颇具艺术价值的建筑需要修缮，利用三维重建技术可以 将其局部或整体在计算机中精确再现，包括其实际尺寸和空间位置、方向等；进 而可以进行相应的力学计算和结构分析，以便指导实际施工过程。整个过程不需 要对实际物体进行任何操作，可以有效的保护建筑物，最大限度的减小了修缮工 作中的破坏风险。 ( 3 ) 娱乐 三维扫描仪也被娱乐产业用来制造数字化三维模型，以提供给电影和视频游 戏作为素材。这样做是因为如果虚拟世界中需要现实世界中的某一物体，直接对 真实物体扫描获得模型比使用软件进行手工绘制效率要高很多。同时，更为频繁 出现的情况是艺术家在创作艺术作品的时候无须将实物做出即可在计算机上看 到预想的结果，极大程度的减小了工作量，可以将绝大部分精力放到创作上而不 是制作上。 ( 4 ) 文化遗产的保存 积累至今，文化遗产数量巨大，门类繁多，所以需要对这些遗产进行有效的 保存和管理。为了更精确、更形象的保存有价值文物，我们就需要对文物进行三 维重建操作，以便获取文物精准的几何和色彩信息。这样可以保证文物所具备大 部分信息能够永远的被保存下来，从而可以最大限度的减少由于文物破损或丢失 所引起的损失。 ( 5 ) 口腔科辅助设计 在现代口腔医学中经常需要给病人植入义齿，但是绝大部分口腔科医生只能 依靠牙齿取模操作来获得病人口腔内部的几何形状，然后根据模型来确定义齿的 尺寸、形状和角度，这样做会因为取模、凝模工序中不可避免的形变引起偏差， 最终导致义齿并不能真正适应病人口腔内部的情况。在某些情况下，医生可以通 过修正来弥补这种偏差，但是在很多情况下这种修正也会失败。所以，如果应用 2 山东大学博士学位论文 三维扫描技术，事先对病人口腔内部进行三维重建，通过具备一定策略的c a d 软件进行辅助分析，计算得出义齿的各项参数，就会完全避免此类偏差的产生。 ( 6 ) 矫正辅助设计 在许多需要矫正的场合下，都是需要事先获得矫正对象的实际空间分布情 况，然后通过一系列的应力计算，如有限元分析算法等，最终获得精确的矫正方 案。此时，亦需要通过三维扫描进行三维重建，以获得精确的原始信息。 ( 7 ) 质量控制 当代工业生产流程大多数运用自动化控制生产流水线，但是其中质量检测部 分有很多还是人工完成，这样既消耗工时又不能保证检测的精确性。如果对被检 测物体首先进行三维重建，由计算机根据既定检测原则与标准模型进行比对，计 算得出工件质量参数，则会省时省力，又能提高检测的准确性。 三维扫描和重建已被广泛应用于各行各业，其中文化遗产方面的应用显得尤 其重要，因为一旦宝贵文物被破坏或遗失，其损失是无法弥补的。对此国内外学 者和机构都已给予了高度的重视。1 9 9 9 年，两支不同的研究队伍开始了对米开 朗基罗雕像的扫描工作。斯坦福大学一个只由m a r cl e v o y 带队的研究小组携带 c y b e r w a r e 公司制作的激光扫描仪来到佛罗伦斯，目标是d a v i d 和p r i g i o n i 以及 m e d i c i 神庙里的四尊雕像。此次扫描的精度为每0 2 5 毫米1 个数据点，足以看 清楚米开朗基罗当年的每一凿痕。精细的扫描工作产生出大量的数据( 超过 3 2 g b ) ，对数据的处理也花费了5 个月的时间。大约在同一时期，m m 也有一支 队伍开展了类似的工作，除了获取几何数据，还保存了颜色信息，当时的组织者 是h r u s h m e i e r 和eb e m a r d i n i 。2 0 0 2 年，d a v i dl u e b k e 等人扫描了托马斯杰 斐逊的蒙蒂塞洛。当时使用的是d e l t a s p h e r e3 0 0 0 激光扫描仪。扫描所得数据和 数码照片后来被人们整合在一起形成了虚拟蒙蒂塞洛，并于2 0 0 3 年在美国新奥 尔良艺术博物馆展出。展览中使用双目立体三维展示的方式使浏览者产生真实的 现场效果，同时视线追踪器能够根据浏览者眼睛的运动改变视野。2 0 0 3 年， s u b o d hk u m a r 等人负责了对古代楔形文字石匾的扫描工作，这一次激光扫描仪 再一次得到了运用。2 0 0 5 年，g a b r i e l eg u i d i 等人负责扫描一个名为“p l a s t i c od i r o m aa n f i c a ”的罗马塑像，这一次的扫描工作异常艰巨，因为该塑像体积庞大， 同时又有很多细微之处的需要表现，于是一般的激光扫描仪很难派上用场。他们 山东大学博士学位论文 最后选择厂结构光扫描结合三角激光扫面的方式。2 0 0 1 年起，山东大学计算机 科学与技术学院联合文化历史学院共同开展了建立山东大学数字博物馆的浩大 工程。不仅将数以万计的文物有条不紊的整理罗列，更通过三维重建的方式将诸 多重要文物在网络上展现出来，使得中华瑰宝再放光彩，也为后人留下了真实而 宝贵的历史数据。近期国家发改委批复投资2 6 1 亿用于敦煌莫高窟保护利用工 程，由中国科学院计算机研究所、武汉大学、浙江大学联手攻关，其中投资最大 的项目是“数字敦煌”，其课题组致力于将莫高窟外形、洞内雕塑等一切文化遗 迹，以毫米的精度虚拟在电脑里。可见开展以三维重建为基础的科研工作已是刻 不容缓。 最近几年，本人在国家自然科学基金课题“基于海量数据点的三维表示中的 关键问题研究”和山东自然科学基金课题“海量数据处理中的高精度三维表示问 题研究 等项目的支持下，对三维重建进行了深入的理论和应用研究，本文的研 究工作正是在这样的背景下进行的。 1 2 研究现状 图1 1 三维重建流程 三维重建工作是一个连续而复杂的过程( 见图1 1 ) ，首先需要获得物体原始 点云( 包括轮廓) 数据。一般说来一次获取到的数据只是整个物体的一部分信息， 这就需要对若干局部进行对齐和整合，使之成为完整的数据描述。由于数据获取 过程中难免会存在噪声，数据整合之后也需要进一步进行优化，一方面是为了有 效消除噪声，另一方面在必要的情况下需要对数据进行平滑和简化等操作，使数 据在数量和质量上达到一定要求。三维重建除了直接根据点云数据实现，也有其 4 山东大学博士学位论文 他的辅助方式，比如将双目视觉和全景拼接算法相结合，可以实现大规模场景三 维重建，虽然精度有所限制，但是也可以产生更为直观和可钡0 量的三维模型。 重建之后得到的数据可被广泛应用。除了利用这些数据直接进行实物造型外 也可对其进行进一步的分析计算，产生更深入的应用。如三维人脸识别：首先对 目标人脸重建数据进行分析计算，得到表情无关几何不变量信息，以此为特征值 通过一定策略在特征数据库中进行比对，可更为精确的匹配出人脸的身份。另一 方面在很多场合下并不是直接运用重建数据，而是以此为原始数据，通过某种方 式进行数据修改和调整以便实现某些特殊效果，比如要在原始模型上进行有目 的修改工作( 通常称作“三维雕刻”) ，就需要通过一定手段在人机交互的二维操 作域与三维模型表面的几何空间域之间建立灵活的映射关系，实现人机交互对模 型表面造型的直接控制。 1 2 1 三维空间教据获取 o 目q 絮 震譬赍青 占口 图1 2 各种二维模型 目前三维章建整体流程框架结构已经很规范了1 1 1 l “，首先在一系列准备j = 作 完成后通过对一个物体的多个视图获取强度或深度信息。然后将多个视图置于同 一个坐标系内，并使之恢复原来的相对位置关系和正常的尺寸比例关系。随后将 山东大学博士学位论文 局部的面片整合为一个整体作为原始物体的三维模型表示( 见图l2 ，摘自i n s p e c k 公司网站) 。最后在实际应用或其他科学计算进行之前按照一定的要求，对所得 三维模型进行优化操作，包括简化、平滑、去噪等操作，具体操作根据具体要求 不同而有所变化。目前在数据获取阶段最为广泛应用的是= 维扫描仪( 见图13 ) 。 唯区l 囊 图1 3 各公司目前已经成型的商业三维扫描仪 根据数据获取过程的区别，立体物体空间信息的获取大致分为三种形式： ( 1 ) 交互式的表面勾勒：通过记录点触设备在被测量物体表面走过的自由 路径产生出物体大致轮廓o 】。该方式需要操作人员手持点触设备在物体表面进行 多次接触才能得到能够较为真实的表现原始物体的几何模型。这种方式适合对数 据分布要求不是很高的情况。同时如果被测量物体体积较大又或者物体不便被接 触，则该方法完全失效。 ( 2 ) 基于平面轮廓线的重建：通过连接相邻两层轮廓线获得物体而信息的 方式洲”。该方法常见于医学影像的三维重建，但是其中分叉问题始终是难点问 题。 ( 3 ) 基于体数据的重建：多角度对物体进行测量，然后将每个角度所得数 据整台为个整体”。该方法是目自u 最直接、应用最为广泛的一类方法，但是数 据的自动对齐和整合也是始终很难得到彻底解决的。 从使用的物理设备和工作机制角度加以区别，数据获取方式又可以分为； ( 1 ) 物理接触式：a l l a n s o n t l 等人采用将物体切片然后根据轮廓线采样获取 数据，但这类方法般局限于较软和可被破坏的物体范围。d 刮a r d i n s 4 1 使用点触 设备对较硬的物体表面进行描绘，如果被测物体本身较软又或者根本不允许触 碰，则该方法无效。此类方法一般局限于某个单独的应用范围，而且速度非常慢， 因为这类方式都是基于机械运动实现的。目前这些方；击基本已经被替代。 ( 2 ) 回波描计术：利用回声定位技术洲1 0 i 、核磁共振技术1 13 1 或者化 山东大学博士学位论文 学物质标定成像技术【1 6 】【1 7 1 实现了物体形体的扫描。可以对物体内部构造进行 观测，但是准确性较差，一般只应用于生物医学领域。 ( 3 ) 光学测量：一类方法是计算光线自发射器发出经物体反射回到接收器 的时间乘以光的速度常数作为被测物体到发射器的实际距离。还有一类方法就是 将特定光栅照射到物体表面，如果物体有凹凸起伏，则以不同于光线方向的视角 拍摄到的图像里面光栅会有形变，如原来的直线变成了弧线，然后根据三角学原 理计算出物体凹凸程度，即相对深度，结合事先的对准矫正过程可以得到物体上 每个点相对于拍摄点的绝对深度值。具体说来光学测量又分为三个体系： 1 ) 基于运动的测量：b l a c k 1 8 】【1 9 】利用物体和亮线相对运动产生的轮廓序列实 现了物体三维重建；k i s h i n o 等人【2 0 】【2 1 1 解决了扫描中的凹洞问题。 2 ) 脉冲式测量：j a r v i s 2 2 1 2 3 1 等人将超声波和激光进行调频和调幅，然后释放 于被测物体表面，通过计算声波和光波往返消耗时间乘以对应速度值得到相应的 距离值。此类测距仪已被较为广泛的使用，其中c y b e r w a r el a s e rr a n g es c a l l n e l 是 当今著名的品牌。该测量方式速度比较快，产生数据量大，但是一般不能用于人 头部的扫描，因为激光对于人眼的伤害作用非常大。 3 ) 三角学测量：一类方法是被动的双目视觉方式，其中有基于区域匹配的 算法【2 4 】【2 ”，基于特征匹配的方法【2 6 1 1 2 7 ，基于轮廓匹配的方法【2 8 】，还有基于立体 摄影测量的方法【2 9 】。另一类就是主动式的基于结构化光栅的扫描方式3 0 】【3 1 1 。此 类方法将已编码的光栅一幅或多幅图像照射到被测量物体表面，通过计算图像序 列信息得到物体表面几何数据。目前此类方式得到了越来越广泛的应用，原因在 于其测量精确度较高，测量时间很短，同时一般使用的光栅为白光、有色可见光 或低功率红外线，对人眼没有任何伤害，适合进行人体造型三维重建。山东大学 计算机科学与技术学院已经完成的“数字化博物馆项目”就是应用了这样的扫描 设备，生产厂家是加拿大i n s p e c k 公司。 目前三维扫描的应用范围大致分为两个方面。一个是医学应用和管道、器件 内部检测，该应用主要考虑到被观测物体不便被解剖或拆解，应使用核磁、超声 波等外部透视手段进行测量。另外一个应用方面就是要获得物体外表面形状信 息，如果允许接触表面，则可以使用接触式测量方法；如果不便接触或表面硬度 不够则需要使用光学测量方法，包括激光脉冲法和光栅扫描法，但是考虑到人体 山东大学博士学位论文 特别是眼睛的脆弱性，对于人体的扫描一般不使用激光设备，而是使用低强度白 光或有色光设备。 完整的数据获取分类总结见图1 4 。 1 2 2 三维碎片缝合 图1 4 数据获取方式分类图 无论是通过三维扫描还是其他方式获得的三维空间数据一般情况下不会一 次性获得整个物体的所有几何数据，每次只能获得一个局部，若干局部彼此间有 一定的重叠部分，但是一般不会处于相同的坐标系环境中，这样就需要将每次得 到的数据进行整体缝合最终获得物体的整体描述。对齐和缝合描述的是同一件事 情，一旦各局部被放置到了同一坐标系下，并且确定好了相对位置关系和尺寸比 8 山东大学博士学位论文 例关系，也就意味着数据已经被缝合了。 最为直接的对齐方式是手工选择对应点，然后计算空间变换矩阵得到对齐信 息，但是我们一般期望计算机能够实现自动对齐操作，而且其准确性要达到一定 要求。常见的自动整合方法有：视图变换空间的启发式搜索( h e u r i s t i cs e a r c hi nt h e v i e w t r a n s f o r m a t i o ns p a c e ) 1 3 2 1 、最近点面迭代法( i c p s ) 3 3 】、最近点迭代法( i c p ) 【3 4 】1 3 5 】【3 6 1 和逆向测距校准( r e v e r s er a n g e f i n d e rc a l i b r a t i o n ) d 7 3 8 1 等，这些方法并 不能完全实现自动整合，大都需要手工指定粗略的初始条件，然后由算法完成精 确整合的计算过程。同时这些算法还有一个限制就是它们不能忽略噪点数据的影 响，而有些方法可以做到这一点：多视角同时匹配法( r e 西s t e ra l lv i e w s s i m u l t a n e o u s l y ) 3 9 1 4 0 1 ，加权最小二乘法( w e i g h t e dl e a s t s q u a r e st e c h n i q u e ) h 1 1 ， 最小方差评价器( m v e ，m i n i m u mv a r i a n c ee s t i m a t o r ) 【4 2 】。 1 2 3 三维碎片拼接 三维拼接是个古老而又复杂的问题，在学者们多年的潜心研究过程中积累了 若干方法，但在很多具体情况下仍然不能很好的解决拼接问题。一般认为物体的 自动拼接可以分为两个阶段，首先根据碎片的纹理、颜色和几何信息进行局部匹 配，找出所有可能的、较为合理的拼接方案，然后采用某种全局算法搜索最优拼 接。这两个阶段的处理都非常重要，第二个阶段的处理直接以第一个阶段的结果 为数据，所以第一个阶段