（模式识别与智能系统专业论文）联合sfs和gcp的动态规划立体匹配算法.pdf

中国科学技术大学硕士学位论文摘要 捅要 立体匹配和阴影重建是实现图像三维重建的两种基本方法，各自有着长足的 发展，同时也存在着相应的不足，是计算机视觉中的难点和热点问题。本文在调 研了阴影重建和立体匹配方法的基础上，对如何更好地进行场景物体的三维重建 进行了深入的研究： 1 提出了一种基于图像分割的动态规划立体匹配算法。该算法首先利用m e a n s h i f t 图像分割算法对左右图像对进行分割处理，从而得到分割域的深度范 围约束；然后结合窗口匹配及可信度约束得到地面控制点；综合地面控制 点和其所属分割域的深度一致性关系可以有效剔除部分不可信点：以地面 控制点和分割域作为约束信息，对动态规划的数据能量项和遮挡能量项加 入分割域关系约束，利用动态规划算法得到最终视差图。实验结果表明， 该算法可得到较好的视差结果。 2 提出了将阴影重建方法作为一种新的立体匹配全局特征算子的想法。基于 该想法，将阴影重建的深度结果作为立体匹配的一种特征，并以左右图像 相应特征之间的相似度作为基于颜色的立体匹配的附加约束，提高立体匹 配的准确率和鲁棒性。实验结果表明，该方法有效提高了立体匹配的准确 率，获得了更为良好的视差匹配结果。 关键词：三维重建，立体匹配，阴影重建，动态规划，图像分割，均值偏移算法， 阴影重建匹配特征 中国科学技术大学硕士学位论文 a b s t r a c t a b s t r a c t s h a p e f r o m s t e r e oa n ds h a p e f r o m s h a d i n ga r et w om e t h o d s o f3 dr e c o n s t r u c t i o nf r o m i m a g e s e a c ho ft h e mh a sb e e nf u l l ys t u d i e da n dg r e a tp r o g r e s sh a sb e e nm a d e ，w h i l et h e r e a r es t i l ls o m es h o r t c o m i n g sa n dw e a k n e s s e si nb o t h h o wt oe f f e c t i v e l yu s et h e mt oe s t a b l i s h t h e3 dm o d e lo fas c e n ef r o mi m a g e sb e c o m e sac h a l l e n g i n gt a s ki nc o m p u t e rv i s i o n r e s e a r c h t oa c h i e v et h i sg o a l ，t h i sd i s s e r t a t i o nd os o m es t u d ya n dr e s e a r c ho nt h ef i e l d so f s t e r e om a t c h i n ga n ds h a p ef r o ms h a d i n g f i r s t l y , t h i sd i s s e r t a t i o np r o p o s e sam e t h o do fs t e r e om a t c h i n gb a s e do nr e g i o n sa n d d y n a m i cp r o g r a m m i n g t h i sm e t h o du s e sm e a n s h i f ta l g o r i t h mt oa c c o m p l i s ht h ei m a g e s s e g m e n t a t i o na n dd e t e c tt h ed i s p a r i t yr a n g eb o u n do fs e g m e n t s 。t h e nw i n d o wm a t c h i n ga n d t h er e l i a b i l i t yc o n s t r a i n ta r eu s e dt od e t e c tg r o u n dc o n t r o lp o i n t s a n dt h ed i s p a r i t y c o n s i s t e n c yc o r r e l a t i o nb e t w e e ng c p sa n ds e g m e n t sw h i c hg c p sp e r t a i nt oi su s e dt or e m o v e s o m es u s p i c i o u sg c p s a tl a s t ，w eh s et h eg r o u n dc o n t r o lp o i n t sa n ds e g m e n t sa sc o n s t r a i n t s a n dm o d i f yt h ed a t at e r ma n dt h eo c c l u d et e r mw i t hs e g m e n t a t i o ni n f o r m a t i o nt oc o m p u t et h e d i s p a r i t ym a pu s i n gd pa l g o r i t h m e x p e r i m e n t a lr e s u l t ss h o wt h i sm e t h o dc a l lg e tag o o d p e r f o r m a n c e s e c o n d l y , t h i sd i s s e r t a t i o np r o p o s e sam e t h o do fc o n s t r u c t i n gt h es f sg l o b a lf e a t u r e t r a n s f o r mt oa s s i s tt h ep i x e l - t o p i x e lm a t c h i n gi ns t e r e om a t c h i n g a f t e rt h e o r e t i c a lp r o o fa n d e x p e r i m e n t a lv a l i d a t i o n ，i tc o u l db ev e r i f i e dt h a tt h ed i s p a r i t yr e s u l t so fs h a p ef r o ms h a d i n g c o u l db eag l o b a lf e a t u r eo fs t e r e om a t c h i n g b a s e do i lt h i s ，w ec o n s t r u c tt h es f sg l o b a l f e a t u r ev e c t o rw i t ht h ed i s p a r i t yi m a g e so b t a i n e db yt h em e t h o d so fs h a p ef r o ms h a d i n ga n d u s et h e mt oh e l pt h es t e r e om a t c h i n g t h ee x p e r i m e n t a lr e s u l t so nm i d d l e b u r yt e s ts e ti n d i c a t e t h a to u rm e t h o di m p r o v e st h ea c c u r a c yo fs t e r e om a t c h i n ga n do b t a i n saw e l lp e r f o r m i n g d i s p a r i t yr e s u l t s k e y w o r d ：3 dr e c o n s t r u c t i o n ，s t e r e om a t c h i n g ，s h a p ef r o ms h a d i n g ，d y n a m i cp r o g r a m m i n g , i m a g es e g m e n t a t i o n ，m e a ns h i f t ，s f sg l o b a lf e a t u r et r a n s f o r m i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特 别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一 同 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论 文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相 一致。 保密的学位论文在解密后也遵守此规定。 口公开 作者签名： 签字日期： 签字日期： 沙1 0 ，d 墨、；6 中国科学技术大学硕士学位论文第一章绪论 1 1 课题背景与研究意义 第一章绪论 随着现代科技的不断发展，在人类用计算机实现视觉信息处理的过程中，计 算机视觉的研究工作也得到长足发展。在几十年的研究发展中，计算机视觉的一 个主要目标就是使得计算机通过二维图像获取并认知三维场景信息，感知场景中 物体的具体几何信息，如形状、姿态、位置、运动等，并对这些信息进行描述、 存储、识别和理解。三维场景信息主要通过运动或通过立体场景来得到。这两种 途径都需要解决立体匹配和三维重构的问题 1 】。 三维重建是从图像出发恢复出被摄物体空间点的三维坐标的过程，其实质是 计算机图形学的逆过程。由于信息的丢失和残缺，使得如何根据存在干扰或者不 完全的二维图像信息来恢复三维信息成为一大难点。立体匹配和阴影重建都是具 体实现这过程的方法，各自有着长足的发展，同时也存在着各自的问题，是计 算机视觉中的难点和热点问题。 三维重建在逆向工程、基于图像的绘制、三维测量等领域有着广泛的应用， 并成为计算机辅助几何设计、医学图像处理和虚拟现实等领域的核心技术【2 】。 在未来的发展中，三维重建技术会得到更广泛的应用，如电子商务系统商品的三 维展示，三维模型的自动建模，大规模场景的复原等等。 图1 1 计算机视觉的研究应用 中国科学技术大学硕士学位论文第一章绪论 近年来，现实生活对基于图像的三维重建技术的需求日益迫切，对场景的精 确重建和重建环境、条件、手段的低要求化成为研究人员需要解决的问题。在近 几年的研究中，引入更多更好的研究方法和手段，并对以往的各种算法进行融合 改进，发展了许多优秀的三维重建技术。 1 2 三维重建研究工作和方法 三维重建工作主要有单幅图像三维重建及多幅图像三维重建两种主要途径。 前者的一个重要实现就是阴影重建法s f s ，通过对场景的一些合理假定，并利用 图像灰度与场景深度信息的关系得到被摄场景的估计深度，从而重建整个场景。 多幅图像三维重建一般分为双目视觉和多目视觉。双目视觉因其与人类视觉的相 似性，被中外学者广泛研究，已经成为一种较为成熟的三维重建技术。下面简单 地介绍其中的阴影重建方法和双目立体匹配方法。 1 。2 1 阴影重建法s f s 阴影重建s h a p ef r o ms h a d i n g ( 简称s f s ) 即由阴影恢复形状的方法，利用 图像中的明暗信息，获得物体的二维形状信息。这一方法在7 0 年代由m i t 的 h o r n 3 ，4 】等人提出，利用漫反射性质，根据图像中灰度的明暗变化来恢复场景表 面各点的相对高度及表面法向量等信息，从而可以进一步对被摄物体三维重建。 这种方法一般仅通过一幅图像即可重建场景物体的三维形状，且算法复杂度低， 可以实时恢复采集的图像。故s f s 方法在医学图像处理、卫星遥感技术、工业过 程监测等诸多领域都有着广泛的应用。 目前，基于阴影重建s f s 的三维重建技术已经得到了广泛的研究，许多有价 值的算法被相继提出。这些研究主要集中于改善现有的光照反射模型及能量约 束，以提高重建的准确性，它们有着各自不同的出发点和解决方案。随着研究的 深入，s f s 方法在理论和应用上都取得了新的进展。c h e l l a p p a 5 在h o r n 的能量最 优化的基础上引入可积性约束，并由图像本身计算给出实际未知光源的近似方位 角。r o u y 6 ，7 】等人基于雅克比方程和粘稠解得：至o s f s 问题的稳定解，加快了求解 过程的收敛速度。t s a i 和s h a h 8 提出一种离散线性化方法来求解该问题，该方法 简单快速，且有相对良好的求解结果。k i m m e l 和b r u e k s t e i n 9 提出水平集方法来 获得s f s 问题的全局最优解。l e e 和k u o 1 0 在求解s f s 问题过程中，提出将逐步 近似的表面看成是三角基点的线性组合，从而将该问题转换成一个离散最小值问 题进行求解。p r a d o s 和f a u g e r a s 11 】将光源的距离考虑进来，利用近景光源解决了 以往s f s 问题存在的凹凸歧义，使得s f s 问题成为一个完全问题。在相关的应用 2 中国科学技术大学硕士学位论文第一章绪论 研究上，s h i m o d a i r a 1 2 将s f s 与先验知识结合起来，实现了多面体的重建工作。 赵歆波【1 3 】等人将s f s 与分形理论结合起来，在对遥感图像的重建中取得了很好 的效果。 尽管有很多方法提出，s f s 问题仍然很难获得精确的重建结果。由于实际反 射的多样性，很难确定合适的反射模型，并且光源条件、图像质量等都难以得到 保证，如何给出合适的约束条件成为许多研究者需要面对的难题。由于以上等原 因，s f s 方法的具体应用和效果都受到较大限制。在实际场景中的s f s 方法重建 结果往往会差强人意，尽管可以重建出局部较为细致的深度信息，但在整体深度 上的偏差会比较大，而且由于平滑等约束，难以避免过平滑及丢失细小特征的结 果。 1 2 2 双目视觉立体匹配s t e r e o 2 0 世纪八十年代，m i t 的m a r r 提出了一种计算机视觉理论，并将其应用在双 目视觉匹配上，使得同一场景的两张有视差的平面图像可以产生具有深度的立体 图形，由此奠定了双目视觉立体匹配的理论基础。 双目视觉立体匹配( b i n o c u l a rs t e r e ov i s i o n ) 是一种由左右图像对获取物体三 维信息的方法。模仿人眼，由两个摄像机观察拍摄同一场景，以获得场景在不同 视角下的图像，通过几何成像原理计算同一物点所形成的两图像像素间的位置偏 差来获得视差图，从而得到被摄场景的三维信息。 在双目视觉立体匹配的研究工作中，自8 0 年代至今，研究者们已进行了大量 的研究并提出了许多优秀的方法。b a r n a r d 和f i s c h l e r 1 4 总结了1 9 8 1 年以前主要立 体匹配研究工作，介绍了三维重建的基本原理、评估标准及主要的算法实现。 d h o n d 1 5 弓i 入分层处理方法，并提出增加额外一目来加强约束，减少误匹配， 同时总结了大量的立体匹配算法。s c h a r s t e i n 矛d s z e l i s k i 1 6 对双目稠密视差立体匹 配算法进行了实验分析并详细归类和给出实验评价，将现有立体匹配算法分成4 个相对独立的模块：匹配代价计算( m a t c h i n gc o s tc o m p u t a t i o n ) 、匹配代价累积 ( m a t c h i n gc o s ta g g r e g a t i o n ) 、视差计算与优化( d i s p a r i t yc o m p u t a t i o n o p t i m i z a t i o n ) 、 视差处理校正( d i s p a r i t yr e f i n e m e n t ) 。并建立了一个对双目视觉立体匹配算法分析 评价的通用软件平台。近年来，研究者们将马尔科夫随机场方法引入到立体匹配 中，将视差图描述为马尔科夫随机场，并利用图割算法( g r a p hc u t s ) 【1 7 】、置 信传播( b e l i e f p r o p a g a t i o n ) 【1 8 ，1 9 等优化算法求解，取得了很好的实验结果。 随着研究的深入和硬件设备的改善，双目视觉立体匹配的相关理论不断得到 完善，其应用也愈加广泛。其中一些算法已经可以满足一定的实时要求，并有不 错的重建结果。但目前为止，大多数的双目视觉立体匹配算法主要针对的是稠密 3 中国科学技术大学硕士学位论文第一章绪论 视差的场景重建，而对纹理稀疏的场景和物体的重建效果则不佳【2 0 】。在处理稀 疏纹理域上，双目视觉立体匹配还存在着一些盲点和不足。对于图像中的纹理稀 疏区域，目前主要通过图像分割处理后，利用基于区域的方法来进行求解，它结 合了全局匹配和局部匹配的方法，可以较好地处理纹理稀疏域。 但由于匹配过程中的各种不确定性，立体匹配问题始终不能得到一个很好的 解决方案，尤其是针对非稠密视差场景的重建。重建结果往往会在细节上出现比 较大的偏差。如何得到更加精细准确的视差图，是双目视觉立体匹配当前所面临 的问题之一。 1 2 3 基于阴影重建与立体匹配的三维重建 阴影重建s f s 方法在图像细节上可以得到比较精细的结果，而立体匹配 s t e r e o 在场景的整体视差恢复上表现比较良好。如何结合利用两种方法得到更好 的三维重建结果 2 l ，2 2 】，成为三维重建研究工作的思路之一。 鉴于s f s 方法在遮挡边界上的问题，l e c l e r c 和b o b i c k 2 3 考虑先利用立体匹 配的方法得到初始深度并确定边界范围，从而改善s f s 方法的重建效果。s h a o 2 4 】 等将s f s 弓i 入到立体匹配中，利用s f s 方法得到左右图像相同点的表面法向量关 系，并将此作为匹配过程的额外约束，提高立体匹配的结果。c r y e r 2 5 等人注意 到阴影重建与立体匹配重建结果之间的互补性，采用h a l l 滤波综合阴影重建与立 体匹配的重建结果，取阴影重建结果的高频部分，即图像的细节纹理，同时取立 体匹配重建结果的低频部分，即图像的整体结果，从而得到较好的总体重建结果。 h a i n e s 和w i l s o n 2 6 贝j j s u 用置信传播方法得到一个较好的立体匹配结果，在此基 础上估计各个点的反射率，后继的s f s 重建得到可能的表面法向量，迭代得到更 加准确的重建结果。 阴影重建和立体匹配问题都可以归结为能量优化问题，故此在方法上，两种 研究工作也彼此有所借鉴。近几年，研究者们将置信传播、图割等最优化方法引 入到阴影重建中来，取得了较好的结果。 对于阴影重建与立体匹配方法的结合 2 7 】，研究者们做过了许多有益的尝 试，并且取得了很多有意义的结果。阴影重建方法通常局限于单幅图像的重建， 而且往往存在对真实场景重建的巨大误差。其对环境条件存在着较高要求，同时 因观察角度的不同而分别对左右图像对的阴影重建结果很难彼此配对及产生约 束，从而影响了其与立体匹配方法的结合。但其良好的细节重建及理论上与立体 匹配重建结果的天然互补，仍然吸引着许多研究者研究发展如何有效地综合阴影 重建与立体匹配方法。 4 中国科学技术大学硕士学位论文 第一章绪论 1 3 本文研究内容与创新点 本文主要致力于基于阴影重建和立体匹配方法的三维重建研究。全文主要内 容和结构安排如下： 第一章综述阴影重建研究工作及立体匹配研究工作的发展现状，并简要地介 绍了结合两者进行三维重建的主要研究工作； 第二章介绍阴影重建问题的基本原理及对该问题的一些传统的解决方法，以 及对该问题模型的改进及一些新的研究方法； 第三章介绍双目视觉立体匹配工作中存在的一些问题及具体的算法步骤，并 从局部和全局两个方面简要介绍了目前的主要研究方法。 第四章介绍一种基于图像分割的动态规划立体匹配算法，并通过实验验证该 算法的有效性。 第五章提出了以阴影重建方法作为全局匹配特征算子，并论证了这一方法的 正确性和可行性，通过实验验证了该算子对立体匹配工作的改进作用。 第六章对全文工作进行了总结与展望，对进一步的研究方向和值得关注的热 点进行了探讨。 中国科学技术大学硕士学位论文 第二章阴影重建理论 第二章阴影重建理论 本章首先介绍阴影重建的基本原理和数学模型，对常用的约束条件进行了归 纳总结，随后系统介绍了四种主要的阴影重建方法，并对其原理进行阐述。最后 总结了阴影重建方法的优点和不足。 2 1s f s 问题的基本原理 场景中的物体在光照下，由于表面朝向的差异会表现出不同的亮度，即产生 了明暗变化。这种变化也会表现在观察者的视觉图像里，即在拍摄图像过，3 d 场景物体投影至i j 2 d 图像平面上也会形成不同的灰度。图像灰度的变化分布由以 下四个因素影响：1 ) 投影成像部分的表面曲率；2 ) 光源分布及其入射强度和方 向角；3 ) 物体成像表面的反射特性；4 ) 观察者相对物体的距离和方位。 ( q 图2 1 影响图像灰度变化的因素 物体表面由椭圆面元表示，其表面法向量为亓，反射率为p ：光源的入射方 位角为( 口，谚) ，入射强度为厶：观察者的方位角为( p ，群) ：反射强度为，由上 述4 个因素决定。 为方便起见，我们通常会依据成像系统来建立坐标系，即建立以观察者为中 心的坐标系，以光轴为z 轴，组成右手坐标系。这样，表面可以用函数z = 化力 来表述。物体表面法向量可表述为： 凡( x ，y ) = ( - p ，一q ，1 ) r ，p ：i o z ，q ：= a z ( 2 1 ) 7 中国科学技术大学硕士学位论文 第二章阴影重建理论 根据光学反射原理，物体表面点亮度e ( x ，y ) 可表述为： e ( x ，y ) = p ( z ，y ) l ( x ，j ，f ) 墨 ( 2 2 ) 其中p ( x ，y ) 为物体表面点的反射率，三瓴y ，d 为受观察角度和光源约束的反 射比，光源分布为s 。则当物体光成像到图像时，图像灰度i ( x ，力与物体亮 度e ( x ，y ) 关系为： i ( x ，y ) = 砖( x ，y ) e ( x ，y )( 2 - 3 ) 故此，成像到图像的灰度分布的模型可表述为： l ( x ，j ，) = i s ，。n ( z ，y ) p ( x ，y ) l ( x ，y ，f ) ( 2 4 ) 这个模型通常会经过简化处理，一般地，我们会有如下假设： ( 1 ) 光源为单一点光源，且距离物体非常远，可视为平行光； ( 2 ) 物体表面为理想散射表面，即郎伯体( l a m b e r t i a n ) 表面； ( 3 ) 成像几何关系为正交投影； ( 4 ) 物体反射率p ( x ，力恒定。 以上假设大大简化成像模型，成像系数k r ( x ，y ) 可视为常数，光源可表述为 蜃= ( - p , ，一吼，1 ) 7 1 ，l ( x , y ，f ) 与观察者角度无关，亦可视为常数。归一化处理后， 我们可以得到新的简化模型： ，(x，y)=两季2：万；f罟呈q譬气赫1,1p ( 2 - 5 ) p + +；+ g ：+ l 此即为最基本的阴影重建问题方程，也称为图像亮度约束方程，写成更为一 般的形式： i = r ( p ( x ，力，g ( 五j ，”( 2 - 6 ) 图像亮度约束方程将图像灰度与物体的表面法向量联系起来，意味着我们可 以考虑由图像的灰度分布求取物体表面法向量的分布，进而可求解物体成像表面 的深度分布。但物体法向量的朝向有两种可能，故仅仅图像亮度约束方程不能求 解法向量分布，这使得s f s i 口- j 题成为一个病态问题( i l l p o s e dp r o b l e m ) 2 8 1 。我们需 要引入额外的约束，建立附加方程来解决该问题， 即为正则化( r e g u l a r i z a t i o n ) 方法。 2 2 约束条件 主要的约束条件如下： 1 亮度约束 8 中国科学技术大学硕士学位论文第二章阴影重建理论 h o r n 首先将s f s n 题改写为亮度约束的形式，该约束是s f s i b - 题应满足的基 本约束关系，直接由图像亮度约束方程推出： j f ( ，y ) - r ( p ( x , y ) ，g ( 训) ) ) 2d xdy(2-7) 该约束表明输入图像与重建结果之间的亮度误差，当误差趋于o 时，重建结 果趋近于真实场景。故使得该约束能量最小的解即为s f s 问题的最优解。 2 平滑约束 平滑约束是第二个主要约束，该约束假定要求重建的场景物体是平滑的 【2 9 ，即物体表面函数z ( x ，力满足连续性： ( 蠢+ + 蠢+ g ；) 螂( 2 - 8 ) 该约束条件确保曲面在各个方向上是平滑的，也可以减弱这一约束，成为一 个弱平滑约束： 骢诚+ q 2 ) d x d y ( 2 - 9 ) 3 可积性约束 该约束要求物体表面是可积的，即图像中每点应满足如下约束： ( 以一q ，) 2 d x d y ( 2 - 1 0 ) 这一约束限定了p 与q 的相对变化，从而减少了可能解。 4 灰度梯度变化约束 这一约束要求恢复物体与原物体的灰度梯度变化是一致的，进一步加强对 s f s 问题的可能解的约束： 肌( l b ) 2 + ( 一b ) 2 ) d x d y ( 2 - 1 1 ) 5 归一化约束 这一约束要求表面法向量模为l ，保证结果的合理性： i n ( x ，y ) l l - 1 ) d x d y ( 2 1 2 ) 以上约束使得我们可以求解s f s 问题，但也不同程度地限制了s f s 方法的适 用性，使最终解偏离真实解。平滑约束与亮度约束相结合是比较普遍的做法，但 这一方法要求必须使用边界点值作为迭代初值，由遮挡边界向表面内部推算。故 此平滑约束不适合表面变化不连续和跳变的地方，会带来过平滑问题。而可积性 约束并不是足够强的约束，通常作为一种补充。灰度梯度变化约束对物体表面性 质有一定假设，在边界处同样不能得到满足。 研究者们通常会选用其中的一种或多种附加约束与亮度约束结合在一起，选 择比较好的方法来解决这一问题。 9 中国科学技术大学硕士学位论文第二章阴影重建理论 2 3 传统s f s 方法介绍 2 3 1 传统s f s 方法分类 阴影重建s f s 算法主要通过三种途径来求取s f s 问题，偏微分方程、误差能 量最优化、亮度约束方程直接求解。c r y e r 3 0 d , 组和d u r o u 3 1 ，3 2 】小组分别对此 进行了详尽归纳总结，其中亮度约束方程直接求解又可分为局部方法和线性化方 法。故通常s f s 可分为四类：最小化方法、演化方法( p d e ) 、局部方法和线性 化方法。 1 最小化方法( m i n i m i z a t i o na p p r o a c h e s ) 最小化方法通过最小化一个误差能量方程来获取s f s 问题的解，这是一种全 局算法，从整体上处理图像信息。该方法的关键是如何构造合适的能量方程并选 择合适的最优化数值算法。上文中提到的几种约束都可以被引入其中，构成如下 方程函数： i i f ( x ，y ，p ，q ，p x ，q ，p y ，q y ) d x d y ( 2 - 1 3 ) 该方程函数对应于下列欧拉方程： ( 2 - 1 4 ) 不同的能力方程函数有着不同的欧拉方程表示，研究者们对如何构造并求解 这些欧拉方程提出了各种方法 3 3 1 。i k e u c h i 和h o m 弓 入平滑约束，组成如下的能 量方程： 小( e ( x ，y ) 一r ( p ，g ) ) 2 + 兄( 成2 十乃2 + 皈2 十巩2 ) ) 出砂( 2 - 1 5 ) 引入拉普拉斯算子并离散逼近拉普拉斯算子可得到如下迭代方程： 2 p , 3 1 = 历。，+ 毛( e ，j 只( 式，g ：) ) ( 或，口i ) ( 2 - 1 6 ) g 等1 = 虿，+ - 毛- d ( e , j - r ( ，g i ) ) r p ( p ；：，g ；：，) ( 2 - 1 7 ) 如果已知初始值，通常是遮挡边界的值，则可以利用j a c o b i ，g a u s s - s c i d e l 等方法求得方程组的解。h o r n 等人l 也对加入可积性约束的能量方程进行了求解， 避免了因积分路径不同而导致曲面梯度与曲面高度不能一一对应的问题。 z h e n g 和c h e l l a p p a 用灰度梯度约束代替平滑约束，并对其对应的欧拉过程进 行变换，泰勒级数展开后线性离散化高度函数和表面梯度，得到一个线性收敛的 1 0 0 0 = = 易 a一钞a一砂 0 a一缸a一锄 中国科学技术大学硕士学位论文 第二章阴影重建理论 迭代式，并应用多网格( m u l t i p l eg r i d ) 方法快速求得方程的解。 l e e 和k u o 直接用有限元方法离散化表面高度函数，应用三角形小面元来逼 近表面，直接求得三角形小面元顶点的格点值，其余点值由插值方法得到。 2 演化方法( p r o p a g a t i o na p p r o a c h e s ) 演化方法实质是一类求解动力系统问题的方法。从动力学角度出发，s f s 问 题可以被看作是一个h a m o l t o n 系统问题 3 4 1 ，图像亮度约束方程可改写为如下的 h a m o l t o n j a c o b i 方程形式： 日= e ( z ，y ) 一尺( x ，y ) = e ( 矗y ) 一了军手；i p 葶s p 亏j + ：q 。左q 雨+ 1 ( 2 - t 8 ) 这是一个一阶非线性偏微分方程，当给定初值或边界条件确定时，该方程成 为一个初值问题( c a u c h y 问题) 或边界问题( d i r i c h l e t i b - j 题) 。这类问题求解方法 很多，大致有特征线( c h a r a c t e r i s t i cs t r i p s ) 方法、粘稠解( v i s o s i t ys o l u t i o n ) 方 法及水平集( 1 e v e ls e t s ) 方法。 求解问题的关键步骤是找到图像中的起始点，该点的形状可以得到确定，在 s f s 问题中往往是最亮点，然后从这些点出发进而求得整个表面的解，这一过程 可应用演化方法来实现，该演化过程是时间可微的。 b i c h s e l 和p e n t l a n d 3 5 基于d u p u i s 和o l i e n s i s 3 6 的方法，提出了一种p d e 算法 最小下山法( m i n i m u md o w n h i l la p p r o a c h ) 来求解s f s 演化问题。当确定了 图像奇点( 图像灰度最大值点) 的表面形状后，搜索该点的邻点，找出其中远离 光源的所有邻近的点，然后从这些点中选取其中最接近光源方向的点，由此构成 演化路径来计算图像每点的高度值，最终得到整个表面的高度。 在此算法中，b i c h s e l 和p e n t l a n d 设表面某点的沿偏角9 方向的切向量为 ( e o s 伊d s ，s i n r p d s ，d z ) ，若该点对应的表面法向量为n ( 惕，n 2 ，2 3 ) ，则它们的关系如 下： c o s ( o d s 啊+ s i n 伊d s n 2 + 比传= 0 ( 2 1 9 ) 对每个方向缈的邻点，在该邻域点亮度决定的等亮度线上寻找最快上升斜 率，并由表面梯度与法向量的关系可以得到如下关系( 口为等亮度线参数) ： ( c o sc p p ( a ) + s i na p q ( a ) ) = 0 ( 2 2 0 ) 选择远离光源方向的表面梯度值来求得仃( 伊) ，然后由各方向上的邻域点高 度值求得当前点高度值，迭代过程中，可以得到逐步逼近真实值的高度z ： z o + 1 ( _ ) c ，y ，9 ) = z ( x + 出c o s 9 ，y + d s s i n g - d s o ( q o ) ) ( 2 - 2 1 ) 大多数的算法过程较为复杂，在此不一一赘述。 中国科学技术大学硕士学位论文第二章阴影重建理论 l e e 和r e s e n f e l d 的局部分析方法【3 7 】是对p e n t l a n d 局部分析方法的一种改进， 盼匿篡班 仁功 y = a r c t a n i 2 一 ( 2 - 2 3 ) e l c o s 2 c o s e t + e v s i n r c o s c r j 善 = a r c c o s 毒 ( 2 砷 p = 昙= 钆_ 川，9 = 熹= z ，q u 户o ，m 一1 ；j = 0 ，一2 - 2 5 ) - 1 ( 2 - 2 5 p 2 瓦2z ，厂刁h 9 。面2 弓，厂钆，声u ， 一 2 u ，川 f ( z ) = e 一r ( 刁，一z i , j - i , , 乞一刁- 1 ) = 0 ( 2 - 2 6 ) o = f ( g i , j ) 八咧) + 如- 动若( 幼 ( 2 - 2 7 ) 中国科学技术大学硕士学位论文 第二章阴影重建理论 迭代计算n 次后，即可得到接近真值的稳定值解： 若垅_ 1 ) 叫母c 而黄甭一孝群赫- z s ， 该方法实现起来非常简单，且对场景物体要求较少，在对实物的三维重建中， 属于效果比较良好的算法之一。在后文的算法实现中，本文利用了该算法来实现 阴影重建s f s 部分。 2 3 2 方法比较 在文献 3 0 】中，选取了6 种主流的算法来比较它们对图像重建的结果性能。 z h e n g & c h e l l a p p a 方法以及l e e & k u o 方法属于上节提到的最小化方法，前者用灰 度梯度约束代替了平滑约束作为额外约束，后者采用了应用三角形小面元来逼近 表面的离散化方法。b i c h s e l & p e n t l a n d 方法则是一种演化方法，利用最小下山法 准则求解s f s 问题。l e e & r o s e n f e l d 方法和p e n t l a n d 方法均为一种局部方法，采用 球形表面假定对线性偏微分方程直接求解。t s a i & s h a h 是一种线性化方法，通过 离散反射函数并线性化逼近来迭代求解s f s 问题。表2 1 是这六种算法对虚拟图像 的重建性能比较： 表2 1 各算法性能对虚拟图像重建性能比较。 m e t h o d ss u mo f e r r o r r a n k i n g z h e n g & c h e l l a p p a 4 2 6 2 l e e & k u o4 1 31 b i c h s e l & p e n t l a n d4 6 13 l e e & r o s e n f e l d5 5 85 p e n t ! a n d 5 5 6 4 t s a i & s h a h5 9 56 从表2 1 可以看到，对于虚拟图像的重建，最小化方法属于一种较好的重建 方法，而t s a i & s h a h 方法应放弃了平滑约束等额外约束，重建的结果会比较粗糙， 对应的误差也相对较大。但对于真实图像的重建，文献 3 0 1 给出的六种方法中， t s h a & s h a h 方法的重建结果相对而言比较良好，如图2 2 所示： ， ， l e n a 图像 2 2 a e n g c n a ：a p p a l e e k u o b i c l u e i p e n t ；a n c ll e e r o s e a f e = | d f 辚 1 t s a i s h a h 圈22 旧影重建方泣对真实图像l e n a 的重建结果 从图22 可以看到，阴影霞建方法对真实图像的重建效果欠佳，最小化方法 z h e n g c h a l l a p p a 和l e e k u o 因平滑约束等额外约束的引入，其结果出现“过 f 滑”的现象，凹凸性歧义也导敏r 部分区域重建出现极大偏差。演化方法b i c h s e l p e n t l a n d 悃为初始点( 灰度最大值点) 的影响，不能完成j r 确的重建。局部 方法l e e r o s e n f e l d 及p e n d a n d 的重建效果也不是根好，这主要是网为对图像的 倒设不够合理及对光源分布的估计币足。线性化方法t s a i s h a h 相对其它五种方 法敬果较为良好，对图像细节保留比较完好虽然也h 现了凹凸性歧义，但其结 果可以反映出原图像的纹理和颜色信息。 印打，一堪“f黉勘 中国科学技术大学硕士学位论文第二章阴影重建理论 2 4 改进的s f s 模型和算法 2 4 1 光照模型的改进 传统的s f s 模型对光照模型进行了简单的假设，认为场景光源是无穷远处的 点光源，被照射的物体表面是理想朗伯体表面。这一假设简化了问题模型及其求 解过程，但同时也很大程度上限定了阴影重建方法的应用范围和重建效果。研究 者们对场景的光照模型进一步深入研究，对成像条件作了更复杂和切合实际的假 设。 传统的s f s 方法使用的是局部光照模型的l a m b e r t 漫反射模型【3 8 】，该模型认 为一个理想漫反射物体表面上反射出来的漫反射光的强度同入射光及物体表面 法向量的点积有关，并由此引出来反射函数。但实际上，朗伯体表面只是一种理 想的漫反射表面，在真实场景中很少有物体可以很好地呈现出这种反射特性，通 常投射到物体表面上任意一点的反射光还包括镜面反射光和环境反射光。因此， 简单的l a m b e r t 漫反射模型并不能很好地拟合真实光照条件，研究者们进一步提 出了更加复杂的光照模型。 p h o n g 光照模型。镜面反射是一种很常见的反射类型，它是光源在平滑表面 上产生的具有一定方向性的反射光，其位置往往随着观察者的方位不同而变化。 p h o n g 于1 9 7 3 年提出该模型 3 9 】，采用镜面反射方向r 和视线方向v 的夹角的余弦 函数的幂来反映表面的镜面反射光的空间分布，并认为表面反射光是环境反射 光、漫反射光、镜面反射光三个分量的线性组合，其光照模型表示如下： i = 丸+ ( 吒( s l q ) + k , z p s ( h n ) ) ( 2 _ 2 9 ) 其中砖，屯，以为光照系数，且屯+ t = 1 ；0 为环境光亮度，为漫反 射光亮度，j 耶为镜面光亮度，蜃为光源方向角，疗为镜面反射光主轴方向角。 该模型较好地拟合了真实反射光构成，且比较简单，很多阴影重建方法对该 模型下的s f s t 口1 题也进行了算法设计和重建。但该模型也尚有许多不足之处，它 只是个关于表面反射光的经验模型，且暗含着这样的假设：物体表面是足够平滑 的。这些与实际情况并不相符，故研究者们在此基础上提出了其它的光照模型。 整体光照模型。整体光照模型可以同时模拟光源和环境照射光，其代表有 w h i e f d 模型【4 0 】和辐射度模型。w h i e f d 模型将环境光和光源的光能贡献综合考 虑，认为物体任一点的光照亮度可由反射光、透射光和泛光项线性拟合： i i o 1 = l 诅+ i i d i l s 陋3 0 ) 乙为环境反射光亮度，厶为环境透射光亮度，气为光源照射亮度。该方法 中国科学技术大学硕士学位论文 第二章阴影重建理论 原理简单，在3 d 成像领域得到广泛应用，但对于阴影重建问题，如何拟合环境 光的影响是一个非常困难的事情，因为我们并不能对物体的形状有一个先验知 识。但该模型在多图像阴影重建三维恢复研究领域有着一定的应用。 光照模型是s f s i 司题的难点之一，对其合适的建模关系到阴影重建算法能否 顺利得到良好的重建效果。 2 4 2 随机场方法 阴影重建问题可以被描述为一种随机场问题，利用马尔科夫随机场后验估计 来表述阴影重建三维恢复。在马尔科夫随机场理论框架下，我们可以利用随机变 量来表示每个像素表面法向量p ，q 的取值范围和概率，并以随机变量的相互影响 和依赖关系描述相邻像素之间的相互关系，将亮度约束方程及其它额外约束作为 随机变量之间的影响关系。在这一理论下，阴影重建问题转化为最大后验概率估 计，可以用能量最优化方法来解决该问题。 图割算法。c h a n g 等人将图割算法【4 l 】应用n s f s 问题里，结合了l e e & r o s e n f e l d 的局部化方法和最小化方法，利用图割算法来优化全局能量函数从而得 到最终的重建结果。其全局能量函数表示如下： e ( o ) = ( 岛) + ( 巳，岛) 佗3 1 ) p( j 口，q ) e n 其中r ，为度量真实仰角与估计仰角之间差异的能量项，为表面法向量p 分量与q 分量之间的平滑能量项。通过对该全局能量函数应用图割算法，可以得 到一个比较好的结果。