（计算机应用技术专业论文）复杂场景建模和绘制中若干关键问题的研究.pdf

摘要 作为c a d c a m 、虚拟现实、增强现实、科学计算可视化等领域的基础和核心，场景的建模 和绘制一直是计算机图形学中最活跃的研究热点。随着计算机图形学应用领域的不断扩展， 绘制的场景越来越复杂，对模型精度和绘制真实感的要求也越来越高，这使传统的建模和绘 制技术面临着严峻的挑战。近年来，研究人员不断地探索和研究新的场景建模与绘制技术， 相继提了基于图像的建模与绘制( i b m r ) 、基于点的建模与绘制、逆向工程等技术。这些技 术基于全新的理论和方法，以满足复杂场景的高真实感实时显示的需要为目标，绘制效率不 断提高，建模与绘制质量不断改进，在虚拟现实、科学计算可视化等领域得到愈来愈广泛的 应用，同时也展现出更加广阔的研究空间。本论文针对这些建模与绘制技术中的一些关键问 题，包括基于图像的建模与绘制中的立体匹配与图像变形和基于散乱点集的曲面重建与优化 等，进行了较深入的研究，所取得的成果对于相关技术的进一步发展，具有重要的理论意义 和应用前景。论文的主要工作和创新之处如下： ( 1 ) 针对i b m r 技术中的关键问题多幅图像的立体匹配问题进行了研究，提出一种基 于窗口匹配和遗传算法的立体匹配算法，先用基于窗口的匹配算法快速求出图像的匹配，再 考虑立体匹配中的唯一性约束和顺序性全局约束，使用遗传算法重新对错误匹配点求解出正 确的匹配关系。此外，通过对立体匹配中重要的算法协同算法和z i t n i c k 的3d 协同算法的 分析，找出了其中影响匹配计算速度的原因，并对其中的三个关键冈素进行了改进，大大减 少了计算量，提高了立体匹配的速度。 ( 2 ) 通过对i b r 中图像变形的常用算法的分析和研究，提出一种基于区域边界的变形算法， 针对变形算法中特征指定、变形效果、计算代价三个关键方面给出了相应的改进策略。在特 征指定方面采用任意形状的封闭环，不仅定义非常方便，还有着表现力丰富和适用性强的特 点。在变形效果方面，算法重点关注特征区域，使扭曲局部化，易于用户对特征区域变形的 预测和控制，可保证关键区域的轮廓精度。图像重建采用空间可变线性颜色插值，保证了变 形图像的颜色精度。在计算代价方面，将复杂的区域自动剖分为简单三角形区域，使区域扭 曲函数简单、统一，加快了计算速度。同时利用连贯性实现了像素点和三角形区域的位置关 系的快速判定，降低了计算代价。 ( 3 ) 在基于散乱点集的曲面重建方面，提出了曲面法向量场驱动和曲面曲率驱动的重建 方法，分别采用法向量和曲率来度量网格和待建曲面的误差，给出了基于法向量和曲率的三 角形面片生成规则。该方法在重建曲面拓扑的同时，可自适应地优化网格，即在曲面平坦( 曲 率较小) 的k 域生成较大的三角面片，在曲率较人的区域生成较小的面片。两种方法都显式 地给出了三角形面片与曲面之间误差的度量，以用直观、统一的重建精度参数方便地控制曲 面重建的整体精度。 ( 4 ) 通过采用网格局部区域的法向量来度量边折叠代价，提出了特征保持的基于边折叠 的网格简化方法。该方法无论是在模型的高曲率区还是低曲率区都能在高简化率下保持网格 的特征。提出了基于特征的质点一弹簧模型对简化后的网格进行局部优化，采用边的平均曲 率作为弹簧的弹性系数，使得网格能够根据形状特征进行优化，从而保持网格的原有细节特 征。 关键词：基于图像的建模与绘制；立体匹配；图像变形；散乱点集；曲面重建；网格优化 a b s t r a c t m o d e l i n ga n dr e n d e r i n gm e t h o do fs c e n e si so n eo ft h em o s ta c t i v er e s e a r c hf i e l d si nc o m p u t e r g r a p h i c s a sm o r ea n dm o r eh i g hp r e c i s i o na n dd e t a i l e dm o d e l sa r er e q u i r e di nm a n ya p p l i c a t i o n s ，i t i sd i f f i c u l t yt oc r e a t ea c c u r a t em o d e la n dr e a l i s t i ci m a g ew i mt r a d i t i o n a lm o d e l i n ga n dr e n d e r i n g m e t h o d so np o p u l a rh a r d w a r ep l a t f o r m s s o m en e wm o d e l i n ga n dr e n d e r i n gm e t h o d ss u c ha si m a g e b a s e dm o d e l i n ga n dr e n d e r i n g ，p o i n tb a s e dm o d e l i n ga n dr e n d e r i n g ，r e v e r s ee n g i n e e r i n ga r e p r e s e n t e dr e c e n t l y s e v e r a lk e yt e c h n i q u e si nt h o s en e wm e t h o d sa r ed i s c u s s e di nt h ed i s s e r t a t i o n t h em a i nr e s e a r c hc o n t e n t sa n di n n o v a t i o n sa r ea sf o l l o w s ： ( 1 ) s t e r e om a t c h i n gb e t w e e nt w or e a li m a g e si sak e yc o m p o n e n ti ni b m r ，i nt h i sd i s s e r t a t i o n ， w ep r e s e n tan e wh y b r i ds t e r e om a t c h i n gm e t h o db a s e do ng e n e t i ca l g o r i t h m t h em e t h o di s c o m p o s i t eo ft w op a r t s ：al o c a lw i n d o w - b a s e ds t e r e om a t c h i n ga l g o r i t h mi se m p l o y e dt om a t c h i m a g er a p i d l yt h o u g ht h e r ea r es o m em i s m a t c h e si nt h er e s u l t a f t e rf i l t e r i n gt h o s em i s m a t c h e s ，t h e g e n e t i ca l g o r i t h mi su s e dt oc o r r e c tt h o s em i s m a t c h e sb yg l o b a lc o n s t r a i n t s a d d i t i o n a l l y , w ea l s o a n a l y s i sa n o t h e rt y p i c a ls t e r e om a t c h i n gm e t h o dw h i c hi sc a l l e dc o o p e r a t i v ea l g o r i t h mp r e s e n t e db y c l z i t n i c k b yi m p r o v i n gt h ea l g o r i t h mi nt h r e ea s p e c t s t h ec o m p u t a t i o nc o s to fn e wa l g o r i t h mi s m u c hl o w e rt h a nz i m i c k sa l g o r i t h m ( 2 ) an e wi m a g em o r p h i n ga l g o r i t h mb a s e do nb o u n d a r yo fr e g i o n si sp r e s e n t e d t h es t u d y f o c u so nt h r e ek e yp o i n to fi m a g em o r p h i n g ：f e a t u r e so fi m a g e sa r es p e c i f i e dc o n v e n i e n t l yb y a r b i t r a r yp o l y g o n s ，t h o s ep o l y g o n sa l s od i v i d et h ew h o l ei m a g ei n t os o m es u b - r e g i o n sw h i c ha r e c l a s s i f i e di n t of e a t u r er e g i o i l sa n dn o n - f e a t u r er e g i o i l s f e a t u r er e g i o n sc o n t a i nd e t a i l so fi m a g e s i n o r d e rt og e th i g h e rq u a l i t yo fm o r p h i n g w a r p i n gf u n c t i o n si nf e a t u r er e g i o na r ed e t e r m i n e do n l yb y i t so w nb o u n d a r yw h i l ew a r p i n gf u n c t i o n si nn o n - f e a t u r er e g i o na r ed e t e r m i n e db yb o u n d a r yo f s e v e r a ln o n - f e a t u r er e g i o n s d i v i d i n gt h ep o l y g o nr e g i o ni n t ot r i a n g l em e s ha u t o m a t i c a l l yc a nn o t o n l ys i m p l i f yt h ew a r p i n gf u n c t i o n sb u ta l s or e d u c et h ec o m p u t a t i o nc o s t t h es p a c e v a r i a n tl i n e r i m a g ei n t e r p o l a t i o ni su s e dt or e c o n s t r u c tah i 。曲q u a l i t yi m a g e ( 3 ) r e c o n s t r u c t i n gam e s hs u r f a c ef r o mag i v e ns c a t t e rp o i n t sh a sb e c o m ea l li m p o r t a n t m o d e l i n gm e t h o d ，m o s to fp r e v i o u sr e c o n s t r u c t i o nm e t h o da r eo n l yb a s e do nt h ec o o r d i n a t e i n f o r m a t i o no ft h es c a t t e rp o i n t s w ep r e s e n tan e ws u r f a c er e c o n s t r u c t i o nm e t h o db a s e do nn o r m a l a n dc u r v a t u r eo fs a m p l e ds u r f a c e n o r m a la n dc u r v a t u r ea sk e yf e a t u r e so fs u r f a c ec a l lb e c o m p u t e df r o mt h ec o o r d i n a t ei n f o r m a t i o no fs c a t t e rp o i n t s d r i v e nb yn o r m a la n dc u r v a t u r e ，t h e m e s hs u r f a c ec a nb er a p i d l yr e c o n s t r u c t e da n di sa l s oo p t i m i z e df o ri t sd e t a i l e dm a i n t a i n i n gt h e s h a p ef e a t u r e ( 4 ) m o s to ft h es i m p l i f i c a t i o na l g o r i t h m su s ead i s t a n c em e t r i ca ss i m p l i f i c a t i o nc r i t e r i a t h e d i s t a n c em e t r i ci sn o tg o o df o rp r e s e r v i n gt h es h a p eo ft h eo r i g i n a lm e s h i nt h ed i s s e r t a t i o n ，w e p r e s e n tan e wm e s hs i m p l i f i c a t i o na l g o r i t h mb a s e do nv e r t e x sn o r m a l ，w h i c hu s ee d g ec o l l a p s e m e t h o dt or e d u c et h ed e n s i t yo fm e s h e s a st h en o r m a li su s e f u lt oe n h a n c et h es h a p ed e s c r i p t i o n , t h ea l g o r i t h mc a ns i m p l i f yt h em e s hw h i l ep r e s e r v i n gt h ef e a t u r e so ft h es u r f a c e am o d e lb a s e do n m a s s - s p r i n gs y s t e mi su s e dt oo p t i m i z et h es i m p l i f i e dm e s h ，t a k i n ga v e r a g ec u r v a t u r eo ft h ee d g eo f m e s ha st h et e n s i o no ft h es p r i n g ，t h ev e r t e xo ft h em e s hc a nb eo p t i m i z e da n dm o s to ff e a t u r eo f o r i g i n a lm e s ha r ep r e s e r v e d k e yw o r d s ：i b m r ；s t e r e om a t c h i n g ；i m a g em o r p h i n g ；s c a t t e rp o i n t s ；s u r f a c er e c o n s t r u c t i o n ； m e s ho p t i m i z a t i o n 插图清单 图2 1基于几何与基于图像的建模与绘制比较1 6 图2 2 典型的i b m 流程1 7 图2 3 基于图像的建模与绘制实例1 7 图2 4 全景函数一l8 图2 5 成像模型。1 9 图2 6 外极几何约束。2 2 图2 7 窗口算法。2 3 图2 8窗口算法的匹配结果。2 6 图2 9 匹配样本图像2 9 图2 1 0 窗口相关算法和遗传算法的视差图2 9 图2 1 13 d 视差空间局部支持区域3 l 图2 1 23 d 视差空间抑制区和支持区2 d 切片示意图( r 为常数) 。3 1 图2 1 3改进的三维协同算法视差图3 4 图3 1 ( b l a e ka n dw h i t e ) ) 。3 5 图3 2 视图变形。3 6 图3 3 均匀过渡3 8 图3 4 非均匀过渡3 8 图3 5 基于特征的变形。4 0 图3 6图像的总变形区域和特征区域。4 3 图3 7 区域边界的映射关系4 4 图3 8 变形区域的三角剖分4 6 图3 9 凸多边形区域的三角剖分4 6 图3 1 0 凹多边形区域的三角剖分4 7 图3 1 l区域的三角剖分4 8 图3 1 2 三角形区域的映射关系4 8 图3 1 3点与三角形位置关系判定5 0 图3 1 4 源图像和目标图像区域划分5 3 图3 1 5 渐变效果5 3 图4 1数据采集设备分类5 6 图4 2 三维激光扫描仪和三角形方法的激光扫描仪原理5 7 图4 3k 一近邻数据结构6 l 图4 4 点云法向量估算6 3 图4 5 密贴曲面三角形6 5 图4 6n 的法向量锥6 5 图4 7 密贴曲面三角形法向量分布一6 6 图4 8 网格元素分类6 7 图4 9 生长边的搜索空间一6 8 图4 1 0 顶点合并7 0 图4 1 1 法向量场驱动的曲面重建7 3 图4 1 2 基于曲率的曲线误差度量7 4 图4 1 3 基于曲率的三角形误差度量7 5 图4 1 4 新顶点的确定7 7 图4 1 51 , j 点满足重建精度区域7 7 图4 1 6曲率驱动的曲面重建结果7 9 图5 1 边折叠操作8 5 图5 2 网格的描述一8 7 图5 3 基于法向量的折叠代价计算。8 8 图5 4 拓扑结构的改变。9 0 图5 5 新顶点的确定9 0 图5 6 边交换操作。9 2 图5 7 网格顶点的局部优化。9 2 图5 8 质点一弹簧模型。9 3 图5 9 质点一弹簧模型9 4 图5 1 0 质点受力分析9 5 图5 1 l面具模型原始网格9 7 图5 1 2n c o s t = 0 0 1 时的简化、优化结果9 7 图5 1 3n c o s t - - 0 0 3 时的简化、优化结果9 8 图5 1 4n c o s t = 0 0 5 时的简化、优化结果9 9 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金垦王些态堂 或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 签字日期p 7 年舢2 钼 学位论文版权使用授权书 本学位论文作者完全了解金g 旦王些盔堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金起王 些盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 彳擀 签字日期7 蛳月脚 学位论文作者毕业去向： 工作单位： 通讯地址： 新虢膨乃 签字日期： 电话： 邮编： 年2 呀日 致谢 值此论文完成之际，首先向我的导师张佑生教授表示崇高的敬意和衷心的感谢! 张老师 渊博的学术知识、一丝不苟的治学精神、诲人不倦的工作态度给我留下了深刻的印象，是我 永远的榜样。多年来，不论学术研究，还是为人处事，张老师都身体力行、言传身教，使我 终生受益。 在这里，还要特别感谢高隽教授。高老师具有敏锐的学术洞察力和开阔的视野，在论文 的研究和撰写过程中，给了我许多建设性意见和指导，同时给我提供了良好的科研环境和学 术氛围。 衷心感谢计算机学院的刘晓平教授、梁华国教授、檀结庆教授。三位老师在我的论文的 撰写过程中，给了我热情的指导和关心，使我受益匪浅。 感谢胡学钢教授、王浩教授对我的支持和关心。 感谢沈明玉副教授、汪荣贵副教授、胡敏副教授和薛峰博士对我的帮助和支持。 感谢计算机学院图象信息处理研究室和图形图象研究室的全体老师和同学。 还要感谢计算机学院的徐静老师、曹航老师、王新生老师和杨孙梅老师给我提供的帮助。 尤其要感谢我的爱人李敏红女士。她在自身困难的条件下，从未放弃对我的关心、鼓励 和生活上无微不至的照顾，使我能坚定信念，完成学业。感谢我的儿子偶宇翔对我的理解和 支持。 最后感谢我的家人和所有关心支持我的同事、亲人和朋友们! 偶春生 2 0 0 7 年1 1 月 第一章绪论 第一章绪论 场景的建模和绘制是计算机图形学中最活跃的研究领域。c a d c a m 、虚拟现实、增强现 实、计算机艺术、影视特技以及计算机视觉、科学计算可视化等都把场景建模和绘制技术作 为基础和核心。飞机、汽车、船舶、叶轮的流体动力学分析，工业产品的设计造型，山川、 海浪、植物等自然景物模拟，人体外貌和内部器官的三维重建，科学计算中的应力、应变、 温度场、速度场、电磁场的可视化等，无不需要强有力的场景建模工具和绘制方法的支持。 随着应用领域的不断扩展，场景复杂度越来越高，精度要求也越来越高。这对传统的基于几 何的场景建模和绘制方法提出了挑战。对于十分复杂的场景建模，传统几何建模技术往往只 能望洋兴叹。为了能在具有普通计算能力的微型计算机上实现复杂场景的建模和绘制，基于 图像的建模与绘制、基于点的建模与绘制、逆向工程等新技术不断地被提了出来并绲到了愈 来愈广泛的应用。 1 1 基于几何的场景建模技术 传统的基于几何的场景建模技术，可以分为分解表示、构造表示和边界表示三大类。 分解表示( d - r e p ) 是将场景按某种规则分解为较小较易于描述的部分，每- - d , 部分又 可分为更小的部分，直至每一小部分都能够直接描述为止。分解表示方法的优点是简单，容 易实现形体的交、并、差计算。但是它存在如下缺点：占用的存储量大，物体的边界面没有 显式的解析表达式，不便于运算等等。因此，它不适于复杂场景的建模。 构造表示按照生成过程来定义形体，常用的有扫描表示、构造的实体几何表示。扫描 表示基于一个基体沿某一路径运动而产生形体。 扫描是生成三维形体的有效方法，被大量 的造型系统采用，但扫描方法不能直接获取形体的边界信息，表示形体的覆盖域也非常有限。 构造的实体几何( c s g ) 表示通过体素的运算而得到新的形体。体素可以是立方体、圆柱、 圆锥等，也可以是半空间，运算为变换或正则集合运算( 并、交、差等) 。c s g 表示方法数 据结构比较简单，数据量比较小，内部数据的管理比较容易，可方便地转换成边界( b r e p ) 表示，且形体的形状容易修改，但形体的表示受体素的种类和运算种类的限制，对形体的局 部操作不易实现，且c s g 表示的形体的显示与绘制需要较长的时间。 边界表示( b - r e p ) 是几何造型中最成熟的表示法。实体的边界通常是由面的并集来表 示，而每个面又由它所在的曲面的定义加上其边界来表示。边界表示的一个重要特点是，描 述形体的信息包括几何信息和反映顶点、边、面的连接关系的拓扑信息两个方面。b - r e p 表 示方法覆盖域大，原则上能表示所有的形体，而且易于支持形体的特征表示，比较容易确定 几何元素间的连接关系，绘制速度较快，容易支持对物体的各种局部操作，便于在数据结构 上附加各种非几何信息，b r e p 表示己成为当前几何造型的主要表示方法之一。 2 合肥工业大学博上学位论文 当今的计算机图形学应用领域中，已经有着丰富的模型表面的表达技术，即曲面造型 技术。主要的曲面造型技术有以下几类：参数曲面造型、隐式曲面造型、细分曲面造型、变 形曲面造型等。 1 1 1 参数曲面造型技术 f e r g u s o n 于1 9 6 3 年最早引入参数三次曲线，构造t f e r g u s o n 双三次曲面片。2 0 世纪6 0 年 代c o o n s 、b e z i e r 等奠定了其理论基础。2 0 世纪7 0 、8 0 年代d eb o o r 、c o x 等将b 样条理论用于 形状描述，提出了b 样条曲线和曲面，较成功地解决了局部控制问题，并在参数连续性基础 上解决了连续拼接问题。1 9 7 5 年，v e r s p r i l l 首先提出了有理b 样条方法，克服了先前方法不 能精确地表示除抛物线和抛物面外的二次曲线曲面的缺陷。2 0 世纪8 0 年代后期p i e g l 和t i l l e r 将有理b 样条发展成非均匀有理b 样条( n u r b s ) 方法，现今n u r b s 尸, 成为自由曲线和曲面造 型的最为流行的技术。1 9 9 6 年e c k 等3 提出了用b 样条曲面来对任意给定拓扑网格进行重建的 方法。1 9 9 7 年，l e e 等瞳1 人给出了一种用多阶b 样条曲面重建算法，1 9 9 9 年y a n g 和l e e 1 提出 了一种基于边数据分割的二次参数曲面重建方法，2 0 0 0 年p i e 9 1 和t i l l e r 在h 1 中提出了用b 样条 曲面逼近离散采样点的方法。参数曲面表示一直是描述几何形状的主要工具。 1 1 2 隐式曲面造型技术 曲面造型的另一个重要工具就是隐式曲面陌1 。参数曲面由于存在代数次数高及求交等 操作的不封闭性等缺点，其发展和也用受到了一定的限制。隐式曲面与参数曲面相比，具有 更多的自由度，在构造复杂曲面的时候能得到更高光滑度，可提供更多的形状控制手段。隐 式曲面表达形式紧凑，而且具有几何运算下的封闭性。任何参数或隐式曲面之间如求交、等 距操作等几何运算的结果均可表示成隐式形式。隐式曲面在进行人体的肌肉、水滴、云、烟 等物体的造型和动画方面有很人的优势。元球( m e t a b a l l ) 造型技术是隐式曲面造型技术一个 成功应用。 1 1 3 细分曲面造型技术 由于计算机图形学的诸多应用领域对任意拓扑结构的光滑曲面造型的需求日益迫切， n u r b s 曲面在表示复杂拓扑物体方面存在着许多困难，无法满足这一要求，而细分方法能够 很好地产生拓扑结构复杂的曲面。 细分曲面“2 侧是一类采用多边形网格的点、线、面及其拓扑信息进行完整描述的曲面。 细分的基本方法是：从初始多面体网格开始，按照某种规则递归地计算新网格上的每个顶点， 这些顶点都是原网格上相邻的几个顶点的加权平均，随着细分过程的不断进行，控制网格就 被逐渐磨光，在一定细分规则下，细分无穷多次之后多边形网格将收敛到一张光滑曲面。细 分曲面的最大优点就是算法简单，几乎可以描述任意复杂的曲面，因而得到了广泛的运用。 特别是上世纪9 0 年代以来，以网格细分为特征的离散造型成为一个热门的研究领域。 第一章绪论3 1 1 4 变形曲面造型技术 许多复杂曲面是由多张曲面拼接而成的。如果用传统的曲面编辑技术对物体的外形进行 整体或局部的修改，既繁琐又费时，且难以达到预期效果。为了解决这个问题，在几何造型 和计算机动画中产生了变形曲面造型( d e f o r m a t i o n w a r p i n g ) 技术。 该技术通过将事先确定初始拓扑结构的初始曲面，沿着一定的方向进行形变，最终得到 的曲面作为最终的重建曲面。这种方法往往可以得到比较复杂的曲面，但相对来说不容易控 制曲面外形。m i l l e 等于1 9 9 1 年在文n ”中提出了一种几何变形模型进行闭曲面重建。先将一 种小模型放入需要重建的闭曲面内部，然后让其膨胀变形，同时以要重建的曲面上的采样点 作为对膨胀变形的约束条件。当几何模型的变形达到某一平衡点时，就得到该曲面的数学模 型。r u p r e c h t “引和w i t k i n n 训等人则是通过赋予曲面一定的物理属性，曲面的物理属性和外 力的综合作用，使得曲面最终变形为所求的重建曲面。t u r k 和0 b r i e n 啪1 提出了一类利用二 维物体隐式形变技术对切片数据进行曲面重建的方法。w h i t a k e r 和b r e e n 心1 也1 将l e v e ls e t 方法引入曲面重建当中，提出了一类基于l e v e ls e t 模型的曲线重建方法。变形曲面造型技 术具有良好的交互性，且与物体的具体表示无关，从而使其能很容易集成到现有的几何造型 或动画系统中。 此外，曲面造型的其它技术还有基于形状混合的曲面造型技术、蒙皮造型技术、基于 变分原理的造型技术、分形造型技术、小波曲线曲面的造型方法等等。 1 2 基于图像的建模与绘制( i b m r ) 技术 虽然传统的基于几何的建模和绘制方法已能用于较复杂场景的建模和真实感图形绘 制，但是高复杂度场景的建模型和绘制需要高强度的计算和海量的存储，即便是简化后的场 景，现有的一般计算机系统仍无法满足实时绘制的要求。尤其是在虚拟现实、i n t e r n e t 等应 用领域，传统方法面临着巨大的挑战。 近年来，基于图像的建模和绘$ i j ( h m g e b 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 与传统 绘制技术相比，有着鲜明的特点： ( 1 ) 场景绘制独立于场景复杂性，仅与所要生成画面的 分辨率有关；( 2 ) 预先存储的图像( 或环境映照) 既可以是计算机合成的，亦可以是实际拍摄 的画面，而且两者- f 以混合使用。i b m r 技术已经得到了愈来愈广泛的应用，展示出诱人的 前景。i b m r 技术的出现改变人们对计算机图形学的传统认识，推动了计算机图形学进一步 4合肥- t 业大学博十二学位论文 发展和更广泛的应用。 基于图像的绘制( i m a g e b a s e dr e n d e r i n g ，i b r ) 技术基于一些预先生成的图像( 或环境 映照) 来生成不同视点的场景画面，该技术最早可追溯到传统的纹理映射方法。在早期的应 用中，环境映照以景物中心为固定视点，将周围场景的图像记录在以该点为中心的环境映照 球面或立方体表面上。凶此，环境映照实际上以全景图像的方式提供了其中心视点处的场景 描述。但单一环境映照无法完全描述一个场景，一个自然的选择是在一些路径上选取一些采 样点作为视点，预先生成存储该点处的全景图像。在漫游时，沿给定路径前进，并根据采样 点处的全景图像生成画面。a p p l e 公司的q u i c kt i m ev r 系统使用这种技术摆脱了固定漫游路 线的约束，在中低档硬件平台上实现了复杂场景的漫游。 近年来，随着i b m r 的一些商用系统推出，该技术加快了发展步伐，应用也更加广泛。 1 2 1i b r 技术 对于i b r 技术，依据其对几何信息的利用，可分为三大类：( 1 ) 不含几何信息的绘制， 如基于全光函数的绘制、全景图绘制、基于光场绘制等；( 2 ) 内含几何信息的绘制，如图像 变形、视图插值等；( 3 ) 几何信息与图像信息混合绘制，如3 d 图像变形，层次图像存储技 术等。具体描述如下： 1 基于图像投影变形技术的全景图绘制 该技术将两幅相同视点但不同视线方向的图像联系起来，当两幅图像部分重合时，将它 们无缝地粘接成一幅更大的画面。这一技术的代表是图像马赛克算法。该算法首先由用户绕 一固定点拍摄场景，得到一图像序列( 其中每相邻两帧图像都包含一定的重叠区域) ，然后 将图像序列拼接起来，形成一幅全景图像( 环境映照) 。对全景图像重采样就可得到新的画面。 这一技术的发展，有力地促进 q u i c kt i m ev r 心3 1 类型系统的实用化，已成为目前应用最为 成功的i b r 算法。 投影变形技术只适用于摄像机绕全景图像中心旋转时中间画面的生成，而不适用于摄像 机位置移动的情形。在摄像机做前后移动时，由于景物前后遮挡关系的改变，所得图像并不 完全是原存储图像的重新投影和简单变形，其画面内容在局部区域中发生变化。解决这一问 题的有效方法是在原给定的图像序列中引入可见点的深度信息，以提供原始场景的部分三维 信息。 2 视图插值算法 视图插值技术在相邻采样点图像之间建立光滑自然的过渡，从而真实再现了各相邻采样 点间场景透视变换的变化。视图插值算法的基本思想是利用给定图像上可见点的深度值，局 部重建场景的三维几何信息，并基于这些三维信息对可见点直接进行投影变换，或建立该图 像与其相邻图像像素的对应关系。对于前者，由单幅图像即可生成相邻视点处新的图像。对 于后者，则需给定多幅相邻的深度图像。算法在预先处理阶段先计算存储好这种对应关系， 第一章绪论5 绘制时只需在对应像素间进行插值即可获得中间过渡画面。视图插值过程是一种特殊的二维 图像变形技术。由于这一算法不再要求新图像的视点与原图像的视点位置重合，从而摆脱了 第一类投影变形技术的严格限制，该算法可在不同视点的图像序列之间生成连续过渡的中间 画面。因而，若在预处理中已生成好场景中各采样点处的深度全景图像，则可实现对场景的连 续漫游，此时，前后帧画面之间不再具有跳跃感。 e r i cc h e n 幢“的视图插值算法是第一个在给定两帧深度图像之间实现画面自然过渡的 i b r 算法。该算法采用线性插值技术模拟各相邻采样点间场景透视变换的变化。之后，该算 法被m c m i l l a n 旧副等扩展成一个更具一般性的全景函数造型技术。基于可见点深度信息投影变 形技术的缺点是在所生成的中间画面上可能存在空洞。这是由于所给定的图像无法提供中间 画面空洞处可见点的信息而造成的。空洞的填补非常复杂、耗时，填充效率严重影响各中间 画面生成的实时性和质量。空洞依据其成因大致可分为两类：一是由于可见景物在屏幕上的 投影区域扩张而引起的空洞，二是由于场景中景物的可见性发生变化而引起的空洞。对第一 类空洞，可通过插值相邻像素颜色或插值相邻像素在源图像中的相应偏移向量来近似填补； 对于第二类空洞，精确填补涉及对场景的重新采样。当然，亦可采用多个源图像来生成同一 视点和视线方向的多幅画面，利用这些画面空洞的互补性，经合成得到无空洞的中间画面。 为有效减少中间过渡画面上的空洞数目，m c m i l l a n 等许多研究者近年来提出了逆向投影变形 技术。 尽管存在空洞问题，深度图像的重投影变形技术可在一定精度内将原给定图像上的相 邻像素组合成子块图像，以一个整体进行投影变换。因而计算效率非常高，能在低档的硬件 平台上实现给定图像间的实时过渡。 从整体来看，基于深度图像的重投影变形技术本质上是一个由深度图像重建局部三维 几何并重新采样该局部几何的过程。因而，问题的关键是如何由离散深度值重建连续几何景 物表面。对于这一计算机视觉中的重要研究内容，目前已有多种由深度图像近似重建局部场 景的实用算法。m c m i l l a n 等先后提出了图像空间的高斯重建算法和基于b 样条曲面片的三维 几何重建算法。其中，前一算法利用了椭圆加权平均滤波器对所有源采样点和样本深度差之 平方和进行滤波，进而得到编码所需的码表。它本质上是一个标准的矢量量化过程，所得的 码表就是源图像的一个剖分，且每一个编码均对应屏幕上具有相近深度值的小块区域。类似 地，s i l l i o n 等利用基于深度信息的边缘提取技术对源图像进行分层，然后在每一层中利用传 统三角剖分技术来完成对图像的分割，进而建立起所需的三维网格几何作为原场景几何的一 个局部近似。由于上述三维几何重建方法往往生成大量细小的分割区域，给后续画面绘制的 效率及精度带来了极大的影响，为此，可以通过对深度信息引入一非线性变换，使图像深度 的变化旱线性关系，并利用l a p l a c e 算法及二叉剖分技术实现图像的分割，从而恢复出原场 景几何的三维网格。与传统算法相比，重建所生成的网格数较少，算法精度及效率较高。深 度图像重投影技术的主要优点是该技术适合于实拍图像。如果我们能基于计算机视觉理论求 6合肥工业大学博士学位论文 得实拍图像的摄像机参数及深度信息，则重投影变形技术就可生成相邻画面的自然过渡。通 常，采用图像立体匹配技术来解决图像上可见点的深度恢复问题。 3 光场重建 光场重建是在全景函数重建基础上发展起来的一种新的i b r 技术。一般地，全景函数由 一参数方程来描述，它定义了空间任一处在任何时刻和任一波长范围内场景中的所有可见信 息。对空间中的任一视点矿( 屹，k ，k ) ，从它出发的任一条视线均可用一球面角。和、i ，来定义。 若记光波长为九，则在t 时刻视点v 处的全景函数可定义为p = p ( o ，v ，九，v ，v v ，v z ，t ) a 全 景函数事实上刻画了一给定场景的所有可能的环境映照，因而它以图像的方式给出了场景的 精确描述。为生成一帧给定视点沿特定方向的视图，只需将视点y ( 圪，v ，圪) 和球面角0 、i ， 及时刻t 代入全景函数即可。这其实是对全景函数的采样过程，所得视图即为全景函数的一 个样本。因此，基于图像的绘制问题可描述为：给定全景函数的离散样本集合，生成该全景 函数的一个连续表示。基于这一描述 b r 可分解为全景函数的采样、重建和重采样三个过 程。一般来说，全景函数的获取是非常困难的，因为它所包含的信息量远远超出了当前计算 机的处理能力。m c m i l l a n 等对场景进行采样，并采用无底圆柱环境映照来描述一个采样点处 的全景函数，然后采用投影变形函数来建立两相邻采样点环境映照之间的过渡。尽管在每一 采样点处全景函数降为二维函数，但从总体来看，该算法仍是五维函数( e ，、i ，v ，u ，v z ) 。 l e v o y 心6 1 等的光场函数重建算、法和g o r t l e r 旧7 1 等的l 1 1 1 1 1 i 伊a p h 方法在一定条件下将五维全景函 数降为四维。就目前的状况看，光场函数重建技术还不足以用来绘制一般场景，其中仍有许 多问题有待解决。 4 层次图像存储 该技术同时采用几何及图像作为基本元素，根据一定的标准，动态地将部分场景简化为 映射到简单几何(