（计算机科学与技术专业论文）渐进式图像建模系统中的计算问题.pdf

硕士论文渐进式图像建模系统中的计算问题 摘要 y - 6 本文首先回顾了计算机视觉的一个重要领域一一基于图像建模的发展，指 出了现有方法和软件的不足之处。 接着，本文提出了一个基于单幅或多幅未校准图像的渐进交互式三维建模 方法及相应系统r e l i e v o 。 该方法的主要特点在于，按照一般人的建模习惯，由租到细地通过图像重 建目标三维模型，在确定大致形状的基础上，由用户添加或者修改投影约束与空 间约束，并旌加拓扑修改，逐步实现照相机定标，粗糙模型的求精，并最终完成 对具有任意几何及拓扑物体的重建。在交互过程中，我们将交互抽象为三大类若 干种算子。对于每种算子对应的计算目标，系统提供了一个灵活而且功能强大的 计算平台。该平台由一个基于优化求解器的计算核心和一个采用了树型结构的表 达式系统组成。求解器和表达式系统运用良好的设计模式组建，结构清晰，功能 强大。表达式系统采用基于符号与数值的混合形式，具有很高的计算效率，满足 了系统的实时性要求。 采用这种方法，系统在接受使用者的交互之后，可以实时地求解几何参数 与照相机投影矩阵，并即时地在一个三维窗口中显示重建结果，做到真正的所见 即所得。 【关键词】 基于图像建模、渐进式建模、计算机视觉、最优化问题、设计模式 第t 页 硕士论文 渐进式图像建模系统中的计算问题 a b s t r a c t t h i sp a p e r f i r s t l yr e v i e wam o s ti m p o r t a i nf i e l do ft h ec o m p u t e rv i s i o n ， i m a g e - b a s e dm o d e l i n g ，a n dt h e np r e s e n t sa ni n t e r a c t i v ep r o g r e s s i v e m o d e l i n g a p p r o a c ha n ds y s t e mb a s e do ns i n g l eo rm u l t i p l ep h o t oi m a g e so fu n k n o w n c a m e r ap a r a m e t e r s t h ed i s t i n c tf e a t u r eo ft h i sa p p r o a c hi st or e c o n s t r u c tt h e 3 dm o d e lo ft a r g e tf r o mi m a g e s p r o g r e s s i v e l yi na c c o r d a n c e w i t ht h e g e n e r a l m o d e l i n gc o n v e n t i o n s n a m e l y ，u s e rf i r s t l yd e t e r m i n e st h er o u g hm o d e la n d p u t sp r o j e c t i o na n ds p a t i a lc o n s t r a i n t so ni ta sw e l la st o p o l o g i c a lo p e r a t i o n s s t e pb ys t e pt ol e tt h es y s t e mr e c o v e rt h ec a m e r ap a r a m e t e r sa n dr e f i n et h e m o d e l b y t h i sm e a n s 。u s e rc a nr e c o v e rt h em o d e lw i t ha r b i t r a r yg e o m e t r ya n d t o p o l o g y d u r i n gt h ei n t e r a c t i o n ，t h er e c o n s t r u c t e dr e s u l t sc a nb ec o m p u t e d a n dd i s p l a y e di n s t a n t l yb e c a u s ew eu s ee no p t i m i z a u o n _ t r e eb a s e ds y m b o l i c a n dn u m e r i c h y b r i d0 d t i m i z a t i o n s o l v i n ga p p r o a c h 【k e y w o r d s i m a g e b a s e dm o d e f i n g 、p r o g r e s s i v em o d e l i n g 、c o m p u t e rv i s i o n 、 o p t i m i z a u o n 、d e s i g np a t t e m 第2 页 硕士论文渐进式图像建模系统中的计算问题 第一章序论 第一节问题的提出 逼真的三维场景模型是影视特效制作、虚拟现实、仿真、三维游戏等许多 应用中重要的组成部分。 传统的计算机辅助三维造型技术，首先是通过拉伸、放样、蒙皮、变形等 多种几何造型工具建立几何，再对几何表面赋予精心设置的纹理和光照属性，最 后才能够构造出比较逼真景物模型。对于建模者而言，使用这种建模方法不仅需 要对空间、色彩、光照关系有相当高的把握能力和审美能力，而且过程相当复杂 而费时。 更重要的是，对于一些现有物体，采用这样的方法建模，要保证所建模型 与真实物体在视觉上表现基本一致是相当困难的。 为了解决这些问题，近年来基于图像的造型技术( i m a g e b a s e dm o d e l i n g ， l b m ) 成为国际研究的新热点。 所谓i b m 技术，就是通过技术手段从真实的图像中恢复物体的几何及其表 面纹理和其他属性信息，使得所创建模型在视觉上更加真实。 从图像中恢复三维信息一直是人们努力的目标，这也是计算机视觉研究的 一个核心问题。其中主要的技术手段大致可分为主动视觉和被动视觉两种。采用 主动视觉技术一一如主动获取技术( a c t i v e ) 、基于稠密采样的图像序列 ( p o l l e f e y s ) 的重建技术等，往往需要用特殊的硬件设备来获取图像及一些重要 的相关信息，由此获得较高的可靠性。但在实际中往往受限于目标模型尺寸、设 备使用环境等外在因素，且系统往往造价昂贵，不能适用于多数场合。相对来说， 被动视觉技术，只需普通相机拍照，图像获取方便简易。但从被动获取到的未校 准的单幅或者多幅照片中，自动地对三维场景进行建模时，存在着种种不确定性 的缺陷，其可靠性和结果的准确性很容易受到输入的影响。因此使用被动视觉技 术，通常要在自动技术的基础上引入一定的人工干预。 主动视觉技术主要应用在机器入视觉中，我们需要的是使用被动视觉方法 的照片级图像建模系统。本文主要讨论被动视觉意义下i b m 技术。 第5 页 硕士论文渐进式图像建模系统中的计算问题 近几年来，国内外的视觉研究者从不同的角度，实现了各自的图像建模系 统。下一节，我们先回顾一下已有的相关工作。 第二节相关的工作 在被动视觉技术中，有两类主要的方法： 一类是基于离散点的几何重建方法，它利用多幅图像上的对应点并采用立 体视觉原理来恢复点的三维坐标，再通过给出这些点之间的拓扑连接来建立多边 形网格模型。 另一类方法是基于预定义体素的建模方法。通过人机交互给出目标模型的 一个三维几何参数化模型，再通过建立三维模型与图像间的对应点线关系及三维 几何本身的约束关系，利用优化的方法确定几何模型的精确参数。 1 基于离散点重建的系统 使用基于离散点的重建方法的代表软件有： i m a g e m o d e l e r i m a g e m o d e l e r 是由r e a l v i z 公司在t o t a l c a l i b 系统f r q 的基础上开发的商 用软件。用户通过该系统在两幅图像上指定对应点对，并利用计算机视觉中的极 线约束来实现对两幅图像照相机问的校准，及空间位置的重建。在交互操作的后 切，也允许用户在输入点的基础上建立简单的空间关系。 r e k o n r e k o n 是l i g u m 小组开发的一个原型产品 p o u l i n l 9 9 8 ，其实现方法也是 通过交互确定平面点对间的对应关系，实现照相机校准与几何重建。与 i m a g e m o d e l e r 不同的是，它允许定义一些线性的约束，例如平行、垂直、入射， 用以辅助重建。 p h o t o m o d e l e r p h o t o m o d e l e r 是另一个具有较强功能的产品【p m l ，用户通过在校准好的图 像上输入三维物体的特征及对应关系实现对三维物体的重建。 基于离散点的几何重建方法的优点在于理论上可以重建任意形状的几何； 缺点是在实际应用中对于具有复杂几何及纹理的物体，在多幅图像间自动地选择 第6 页 硕士论文 渐进式图像建模系统中的计算问题 并匹配对应点存在着可靠性低的问题，而手工进行对应点匹配则存在着交互量过 大的问题。此外，确定三维点之间的拓扑连接关系也同样存在着可靠性与交互量 之间的矛盾。在大多数情况下，用户无法对重建计算进行干预，缺乏交互性。另 一个局限在于这种重建方法不能处理单幅图像。 2 基于预定义体素重建的系统 使用预定义体素重建方法的代表软件系统有： f a c a d e 【d e b e v e c1 9 9 6 提供给用户一个类似传统造型系统的环境，用户实现图像 元素与几何元素的对应。系统通过迭代，对非线性的投影关系方程进行优化，从 而计算出几何元素的参数。 c a n o m a m e t a c r e a t i o n s 公司开发的c a n o m a 【c a n o m a l 与f a r t a d e 的方法类似，通 过创建预定义的几何元素并由用户指定图像与平面对应关系实现造型。 基于预定义体素方法的优点在于利用了模型本身的约束关系，因此交互量 相对于前一种方法较小，且可处理单幅图像；缺点是需要预先构建参数化模型， 这就限制了可恢复目标模型的几何类型。因此能否提供丰富的体素模型成为该类 型软件适用性的重要评价标准。 附表一几个已有图像建模系统的比较 j 黧雾黼黼鞭爱晒瓣_ ；| ；l鬟囊黼羹嘲霎瑟蓥i 浚；谣巍i 鲻一 软件目标研究项目研究项目商业软件 图像上放置的2 维元素线线与点点与线 放置2 维元素位置的方式交互交互交互 3 维元素预定义体素面，多边形预定义体素 是否需要校准的物体是不需要不需要 是否需要利用场景的知识是是 是 优化求解方法非线性迭代方法线性迭代方法 未知 约束隐含于体索中线性的弱约束舱含与体素中 第7 页 硕士论文 渐进式图像建模系统中的计算问题 j 。= 霉h 9 t 潮蝴一”im 躲鲤弱i 豳囊妊蚰蜉 软件目标商业软件商业软件研究项目 图像上放置的2 维元素点点点 放置2 维元素位置的方式 交互有一定引导交互有一定引导交互 3 维元素多边形、立方体、圆柱多边形、立方体、多变形、用户定义 圆柱 是否需要校准的物体不需要不需要 不需要 是否需要利用场景的知识 不是必须不是必须不是必须 优化求解方法耒知未知线性迭代 约束提供空间约束不支持约束 弱约束条件 纹理 与视点无关 第三节系统的目标 新系统的目标是建立一个适用于城市建筑物的照片建模系统。从上述产品 和研究成果来看，都不能完全满足要求。先考虑一下在城市场景中，建筑物的表 现特征： 城市中建筑物往往会相当拥挤，拍摄对相机的位置受到比较大的限制，有 些位置甚至根本无法到达，因此获得某个建筑物完整的图像序列进行重建有一定 的难度。这也就意味着我们的系统不能对输入照片有太高的要求。 建筑物的几何形状一般比较简单，其边界主要是平面，在图像上则表现为 直线形。 建筑物内部单元或与其他建筑之间为常见的平行、垂直、贴合关系。 城市建筑本身的构成通常遵循一定的模式。这一点意味着预定义体素方法 将会比较适合。 城市建筑物通常数量众多，需要有一个快速的建模手段。 城市建筑物通常体积较大，观察者在比较远的位置观看，不需要有太精确 的细部表现。 第8 页 硕士论文渐进式图像建模系统中的计算问题 从上述特征，我们发现城市建筑物很适合使用照片建模的方法来重建。 由此，可以提出新系统的几个特征标志作为系统目标： 提供直观方便快捷的用户交互界面，即该系统为面向没有太多专业知识的 普通用户的应用系统 系统必须能对用户的修改做出实时的反应，即计算必须实时化 用户只需要提供一些建筑物照片，不需要经过特殊处理，就可以作为建模 系统的输入，对于照片不能有太多要求 提供丰富的预定义体素，并支持用户自定义体素 允许用户对基本体素的拓扑进行修改以创建用户所需的细节 与现有产品比较，新系统应具备的特征如下 第9 页 硕士论文 渐进式图像建模系统中的计算问题 第二章系统介绍 第一节r e l i e v oi b m 建模系统简介 在第一章最后一节我们提出了系统目标。从这个目标出发，我们采用基于 被动视觉的技术，实现了r e l i e v oi b m 建模系统。系统的输入是单幅或多幅未定 标的图像，且不对图像获取的手段作任何假设。这使得系统具有足够的独立性， 不依赖于获取手段，可处理更多类型、各种尺度的物体。 渐进式图像建模系统r e l i e v o 旨在为普通用户提供一个基于现有建筑物数 字图像或照片的快速而方便的三维造型工具，通过照片半自动地获取建筑物较为 精确的三维几何和表面纹理信息，从而能够快速、真实的恢复地面建筑物的三维 模型。 r e l i e v o 系统具有以下特点： 可多角度多方位对造型结果进行观察和修改：提供预览三维物体以及在二 维图片上的三维体素多视图便捷交互手段； 允许动态交互造型：系统采用基于约束的动态交互造型方法，利用基于符 第1 0 页 硕士论文渐进式图像建模系统中的计算问题 号运算的即时动态优化求解算法获取较为精确的三维几何信息； 基于一个场景的单幅或多幅照片，根据三维模型自动获取纹理信息，保证 造型结果的美观与可用性。 r e l i e v o 提供的造型方法可以在单张照片上获取建筑物三维几何与纹理信 息，用户的交互比较少，没有三维造型经验的普通用户，也可以很快创建具有真 实物体大小比例以及具有真实感的三维模型。通过引入优化求解的方法，还可对 多幅照片中出现的同一物体的冗余信息予以最优化的利用。 在使用上，具体的造型方法混合了基于几何和基于图像的两种造型方法， 用户可以通过在图像中拖动若干建有内部约束的基本体素的顶点来建立约束方 程，利用非线性优化求解算法，在用户交互中动态求解三维几何信息，从而完成 三维造型。同时，根据对照片投影位置的分析，系统还能生成与视点相关的纹理 信息，实现真实感的绘制。 从这个角度上说，r e l i e v o 构建了一个通用、开放的造型软件平台。 第二节r e l i e v o 中的渐进式建模方法 这一节，我们将展现r e l i e v o 系统中使用的渐进式建模方法的概貌。首先， 先介绍支持渐进式建模方法的系统体系结构：然后，我们将讨论渐进式建模方法 的理论基础：最后，我们将从交互功能的焦度分解渐进式建模的具体过程。 1渐进式建模方法的体系结构 r e l i e v o 使用基于预定义体素的方法，并融入离散点方法的思想，提出了渐 进交互式的基于图像建模方法。这一方法的主要特点在于，充分考虑了一般人建 模的习惯，使得用户可以由粗到细地重建目标三维模型，在确定大致形状的基础 上通过人机交互及系统自动解算来不断增加细节。 基于这样的建模方法，我们开发了一个具有高通用性、高可靠性、高易用 性的i b m 建模系统r e l i e v o 。其中高通用性是指能从单幅和多幅图像中重建出具 有任意几何形状的模型；高可靠性是指重建过程的稳定性和重建结果的准确性不 受输入图像影响：高易用性是指在所见即所得模式下以尽可能少的交互量完成建 模过程，且建模过程中三维重建结果根据用户的交互输入实时地计算更新。 渐进式建模系统主要由三个部分构成，我们称之为系统表示的三个层次。 第 页 硕士论文 渐进式图像建模系统中的计算问题 下图为三个层次的图示。 图渐进式建模系统的层次结构图 首先，面向用户的是交互界面，就是最上层的交互层或称用户层。用户在 这个层次上进行操作，指导系统读入照片，根据建筑物的形状，创建若干基本体 素，指定他们之间的约束，拖动顶点位置甚至直接修改拓扑的顶点和边来逼近理 想中原有模型的几何，逐步恢复出照片中的三维模型。这些操作都是自然和直观 的。用户所要考虑的仅仅是如何创建一个拓扑，并将其顶点在各幅照片中找到相 应的位置。本文不过多讨论交互层的实现。 中间层是算子系统，这个层又称为表示层。由于用户的每一步操作都意味 着某些计算要被执行，也就是说操作必须被转化为计算语言，所以我们需要一个 用来沟通计算层和用户层的中间语言。算子系统提供的这种语言，封装了计算功 能。它负责将用户的交互操作命令翻译为算子语言，这种语言的基本单位就是算 子。同时，每个算子绑定一定的计算操作，所以算子语言就可以被计算平台解释 执行。本文将在第三章讨论整个算子系统。 计算平台位于最底层，又称为计算层。计算平台的目标是实现对算子系统 所需要的所有计算功能的支持。但是计算层不直接和用户层打交道，它专注于计 算功能的实现，这样更符合软件设计的原则。在r e l i e v o 中，最重要的计算功能 是优化计算。应此在计算层上对于优化求解做了专门的优化处理，提出了基于表 达式树的优化求解器。本文将在第四、五章讨论计算平台。 第1 2 页 硕士论文渐进式图像建模系统中的计算问题 2 渐进式建模方法的理论基础 基于图像建模是根据图像的信息恢复三维模型，不失一般性的，我们认为 需恢复的三维模型都可以表示成网格。而网格模型m 可由一个四元组( k ，v ，d ，s ) 表示 h o p p e l 9 9 6 。其中，v 是一个顶点位置的集合v = v l ，v n 。v i e r 3 ，定义了 网格在r 3 上的形状：k 表示v 之间的连接关系，定义了网格的拓扑；d 定义了 模型表面的离散属性，如表面材质标识号；s 定义了模型表明的连续属性，如颜 色、法向、纹理坐标等。基于图像的重建的目标就是根据图像恢复空间中的这样 一个四元关系m 。同时，h o p p e 证明了对于空间中两个网格m “与m o 之间的转 化只需有限步操作就可以实现 h o p p e l 9 9 6 。 我们将这样的思想引入到基于图像建模技术中，提出了一种基于图像的渐 进交互式建模方法。 我们假设从若干幅图像撕= 1 n ) 中所需恢复的模型为m ”，其中顶点v 。必须 满足投影约束关系： m = s p ； 其中帕为图像口上的平面点，s 为投影系数，毋为图像垂所对应的照相机 投影矩阵( 蒯和竹表示为齐次坐标形式) 。实际建模中，耐由用户所输入，为已 知条件。而因为我们假设对照相机参数未知，所以厅和v 都是未知的。 除投影约束外，在恢复过程中还可利用的约束关系有： 照相机间的极线约束f ( m , m ) = 0 ，它定义了在同一空间点在不同图像间平 面投影点对应关系。 顶点问的空间约束条件g ( 哟= o ，如共面、共线，线线、线面、面面平 行，线线、线面、面面垂直等约束。 我们把所有的投影约束、极线约束和空间约束表示为一个约束关系方程组 f 。从理论上说，当约束关系足够多时且满足一定条件时，通过求解f 能恢复出 顶点集合v 。另外，若我们将d ，s 简化为网格表面的纹理和纹理坐标，则当网 格的拓扑k 和顶点集合v 已知后，可根据投影约束得到每个面中的顶点在图像 平面上的投影，通过投影矩阵的逆矩阵反求出该面的纹理及顶点的纹理坐标。因 此，事实上网格( k ，v ，d 。s ) e 以通过对( k ，f ) 进行相应的计算得到，即i b m 中，网 格实际上是一个二元组。 第1 3 页 硕士论文 渐进式盈像建模系统中的计算问题 我们的建模系统可以看作一个网格状态机，用户与系统的交互被分解为对 状态机旖加的若干算子叩。网格状态机的状态可由( k i 。f5 ) 所表示，系统通过对 ( 瞄f5 ) 进行计算可得到网格模型m j ，这些m ( j _ 0 n ) 将不断地逼近最终的网格 m 。 ( k o ，f 0 ) o ( k l ，f 1 ) 堕一堕 ( p o p 3 = 0 异只p o 日= 0 异只x 岛与= 0 蜀只= 日昱 昂只= 号e ；卫忍= b 弓 另外，与内部约束相对应的还有外部几何约束，也称为空间约束。用来描 述几个基本体素之间的点线面的几何关系，包括平行约束、垂直约束、贴合约束 等，具体的定义在第三章第三节的空间约束算子中有详细说明。如下图表示了一 个面面贴合的关系，两个c u b e 的顶点之间满足右边的外部几何约束表达式。 f 只巧( k 巧x 巧巧) = 0 b ( 以吃) = o p 2l 1 只( 蚝吒k 圪) = 0 4 反求几何 利用投影约束与空间约束，在输入的n 幅图像中，对网格的顶点集合v 的 进行求解，可以表示为如下的形式： m i n y 。t ，_ ：。, i p j v 一一卅 i ( 4 3 5 ) ，= o = 0 、。， s t g ( v o ，) = 0 其中毋为上一节的方法恢复出的图像口的照相机矩阵，而为手的顶点圻的 投影，g 为所有空间约束条件。1 只v l 一叫l 为将空间点按当前的相机参数决定的 投影约束，在第j 张照片上的投影点和用户指定的投影点的距离。 目标表达式的含义是：用户将要拖动体素的某个顶点到达的位置( 在照片 上的二维坐标) 必须和顶点( 到达该位置后的) 的三维坐标经过投影计算得到的 投影点坐标一致。 第3 4 页 硕士论文渐进式图像建模系统中的计算问题 由于整个目标表达式中，需要确定的是螈而竹我们采用参数化表示。每种 体素有不同的参数以及表示方法，这些参数决定了体素的基本几何形态。因此， 最优化问题求解若有解，意味着存在这样的参数，可以确定体素的几何形态，反 求几何的目标即达到。 第四节纹理及纹理坐标求解 在完成照相机定标与模型重建之后，就可以获取模型每个面片所具有的纹 理属性，在获取纹理数据之前，系统提供了对图像数据进行处理的工具( 如印章、 抠图、填充等) ，通过这些工具，可以弥补图像数据带来的一些缺陷性的结果， 提高恢复到的网格m 的s 精度。 纹理反求操作实际上就是一种图像变换。图像变换是一种将图像从源空间 ( u ，v ) 到目标空间( x ，y ) 映射变换t 。通过求解一个投影变换的逆变换即可 以获取t 。由于每个面在不同角度的照片下有不同的投影纹理，其间又存在遮挡、 阴影等影响，同一个空间点在不同照片上投影点颜色可能是不一样的。我们采用 综合考虑面片在各图像中的可见性、面片法向与各相机视线方向的夹角、面片在 图像中投影面积的大小等各方面因素，通过一个权值比较函数以面片为单位恢复 高质量的基于视点的纹弹_ d e b e v e c 9 6 u n s t r u c t u r e2 0 0 2 ，或者选择最合适的图 像直接恢复与视点无关的纹理。对于不可见的区域，采用边界区域向内扩展的方 法，保证获取纹理的完整性。 第3 5 页 硕士论文渐进式图像建模系统中的计算问题 第五章算子系统的优化求解计算平台 第一节基于表达式树的优化求解器 在上一章，我们单独分析了算子系统中的几个重要的计算问题，并给出了 对应的解法。但是整个算予系统的核心计算问题一如何快速有效地求解最优化 计算问题，还没有得到解决。这一章，我们将展开对优化问题求解方案的讨论。 在本文提到的算子系统中，两次提到求解最优化问题，一是求解基础矩阵 ( 决定相机参数) 时；一是反求几何参数时。这两次求解任务所特有的表现是： 对计算实时性要求较高； 函数表达式的规模庞大； 目标函数和约束表达式的形式不同定； 为了提供对渐进式建模方法的核心一一算子系统的支持，本文就优化求解 器的设计提出了如下的要求： 在交互的过程中，用户对( k ，f ) 每施加一次算子，应能实时地由约束组f 反求出模型的顶点集合v ，让用户能立即见到操作的结果。 为了提高系统扩展性，需要允许用户自定义参数化体素。不同体素有不同 的参数化形式，同时在渐进式建模过程中不断施加的k - o p 类算子也会引起体素 内顶点表达形式的变化，这导致了目标函数、约束函数的内容及形式都将动态变 化，因此需要求解器能支持动态变化的目标函数、约束函数。 求解器应能自由配置多种数值求解方法，以满足不同精度及计算效率的要 求。如不同的线性搜索方法，乃至不同的优化算法。 概言之，求解平台必须具备计算实时性、形式动态化以及功能模块化。 基于以上的要求，我们设计出下图所示的计算平台。该平台分为三个主要模 块和一个接口。 首先，存在一个将算子的计算目标具体化的模块，称之为计算目标集模块。 该模块中的每个类对象负责一个计算目标，如反求几何的模块、投影约束求解模 块、空间约束求解模块等。主要的计算目标我们在上一章已经都分析过。 第3 6 页 硕士论文 渐进式图像建模系统中的计算问题 然后，系统有一个优化求解器，可以提供不同的优化算法设置不同的中止条 件。第二节主要介绍优化问题以及求解器的模型。 相应的，系统为了支持求解器的运作，需要实现表达式系统，来存储和管理 求解过程需要的大量的表达式( 第三节内容) 。 优化器和表达式系统之间通过一个数值接口通讯，保持各自的独立性。 计算平台在算子系统之下，当算子系统要求实现某个算子操作时，它把该算 子( 句子) 翻译成一系列计算目标( 单词) 的集合。每个计算目标又可以表示为 目标函数、约束函数组构成的集合。计算目标要求表达式管理器创建它所需要的 表达式。同时计算目标选定一种优化算法，初始化优化求解器，注册表达式的数 值接口到求解器中。然后，求解器开始工作，当它需要目标表达式或者约束表达 式的数值的时候就到数值接口中取，直到求解器算出结果。最后，求解器将结果 返回计算目标。 第3 7 页 i 一一 ：一i 1 蕊誓丽矗孬矗霹4 熏 i l 计论谴i ；童 _ l l 嚣弊簿鼹 _ i 兰l瞬疆 - q i i 豁标貅标 l i l23n - _ i l - ，一一一 一_ = ，k 一i z - - 一+ 。 e 解器 袭遮述铃觥 h 、 数 纛达式i 卜一 中 骢 接 l止 i | | 毒达式2 一 【 条 件 一 袭达藏n 卜一 i 赣缮臻辩臻黼：l? 滚燧凌幕统 硕士论文渐进式固像建模系统中的计算阀题 第二节优化求解器模型 优化求解过程 1 1最优化问题的一般表述 最优化问题的一般形式为 m i n 厂( x ) s t x x ( 5 2 1 ) 其中，x r “是决策变量，f ( x ) 是目标函数，x cr “为约束集或可行域。 具体在本例中，我们需要的最优方案就是如何能够得到一套参数，这些参 数可以正确的描述场景几何和相机，从而在投影之后跟图像能够达到匹配。假设 空间顶点为吖，投影矩阵p ，则其投影点为胍有 m = p m ：l m i i 童】m ( 5 2 2 ) 其中k 是相机的标定矩阵，r 是相机的旋转矩阵，0 是相机投影中心在世 界坐标系中的坐标。这样，优化方程可以表示为 m i n f ( x ) = u m 一埘1 s a * g s ( x ) 0 ，i = 1 ，棚； ( 5 2 3 ) h i ( x ) = 0 ，j = 1 ， 其中，g i 和h j 分别表示约束条件中的不等式约束和等式约束两个部分。我 们先讨论无约束的情况，此时对应于针对单个体素进行优化，不涉及体素之间的 关系；然后再讨论在有外部约束的情况下优化方程的求解。 1 2一维搜索 在这之前，我们首先来考察一维搜索的情况，此时最优化问题可以被看作 是单变量的优化问题，又可以称之为线性搜索。一维搜索是最优化问题的基础。 在自变量x 扩展到多维的情况下，基本的迭代格式为： 第3 8 受 硕士论文渐进式图像建模系统中的计算问题 x i + l = + 吼d l ( 5 2 4 ) 其关键就是构造迭代方向d 。和迭代步长因子。 设妒 ) = ，( 以+ 口d k ) ，这样，9 , x 。出发，沿搜索方向d 。，确定步长因 子吼，使得妒( 吼) o 是用户可以接受的，则称这样的搜 索为近似一维搜索。在实际计算中，理论上精确的最优步长一般不能取到，就算 能取到也会花费相当大的计算量，因此，我们一般使用近似一维搜索。同时，在 理论上可以证明，近似一维搜索与精确一维搜索在收敛性质上是一致的。 对于目标函数认口) = 八靠+ 口d k ) 来说，假设其在吼附近是关于岱的单峰 函数。则可以使用黄金分割法进行一维搜索。具体步骤如算法5 1 所示。 第3 9 页 硕士论文渐进式图像建模系统中的计算问题 算法5 1 算法5 1 提出的一维搜索方法要求函数为单峰，这与实际情况是有所出入 的。当目标函数不满足单峰条件时，有可能出现搜索得到的函数值反而大于初始 区间两端点处函数值的情况。根据h 6 p f i n g e r ( 1 9 7 6 ) 的建议，每次缩小区间时， 不应只比较两个内点处的函数值，而是要比较两内点和两端点的函数值。当左边 第一个和第二个点是这四个点中函数值最小的点时，丢弃右端点，构成新的搜索 区间；否则丢弃左端点，构成新的搜索区间，这样的算法将会更可靠一些。具体 步骤如算法5 2 。 第4 0 页 鬻一 鹫 硕士论文渐进式图像建模系统中的计算问题 算法5 2 1 3 无约束的非线性最优化问题 在一维搜索的基础上。我们考虑多维变量的情况。首先还是考虑没有约束 的情况，即无约束最优化闯题。 假设函数，( 在心点附近连续可微，且吼= v f ( x 。) 0 ，则进行t a y l o r 一 阶展开，有： ，( z ) = ( 坼) + ( x 一砟) 7 v ：( x , ) + o o j x 一砟) ( 5 2 6 ) 由此，假设x 一坼= 口d 。，则满足以7 9 。 f 口f f ，则其显然为一征定矩阵。 j 因此，只要叱大于q 最负特征值的绝对值，就能保证矩阵q + v 。，为正定。 第4 3 页 硕士论文渐进式图像建模系统中的计算问题 根据以上分析，我们可以得到矩阵g 。特征值绝对值的一个上界： 矿= l 唑 ( q ) r 乏l ( g k ) 口1 ) l ( 5 _ 2 1 5 ) f ， f 同时，给定一个占 0 ，则令v 。= v + 占，有哦+ v k l 正定。 以上算法的复杂度为o ( n 2 ) ，实际上相当于对矩阵瓯进行一次遍历，甚至 可以在矩阵求值的同时完成，在求解速度的角度看来，这样无疑可以获得很大的 提高。但应当注意到，本方法在选取咋时所使用的上界相当粗糙，实际选取的矿 是矩阵g 。所有特征值绝对值的上界而不止是负特征值绝对值的上界。当矩阵的 最负特征值绝对值比较小，而某个正特征值比较大的时候，使用本方法求得的迭 代方向会过于偏离牛顿方向，而靠近最速下降方向。但在实际程序运行过程中， 因为我们所处理的方程形式并不复杂，由迭代方向偏差带来的速度差异几乎可以 忽略不及。但是在算法复杂度上的优势使得本方法可以实现比较理想的用户实时 交互。 同时，针对牛顿迭代的修正，还有很多其它的方法，但其中绝大多数都是 数值方法，h e s s i a n 矩阵g 。是通过差分的方法求得。具体到本文所讨论的例子 中，优化目标为平面距离，则方程的形式如下： 卿删2 善】- ，( x ) ，m 珂( 5 2 1 6 ) 其中，：r ”_ r ”是z 的非线性函数。如果r ( 力是线性函数，则问题( 5 1 6 ) 简化为线性最4 - - 乘问题。否则，为我们通常所说的非线性最4 - - - 乘问题。 非线性最小二乘问题可以看作是无约束极小化的特殊情形，也可以看作是 解方程组 ( x ) = 0 ，i = 1 ，m ( 5 2 1 7 ) 其中，( 功称为残量函数，当m 聆时，方程组( 5 1 7 ) 为超定方程组；当m = n 时，方程组( 5 1 7 ) 退化为确定方程组。 设j ( x ) 是r ( x ) 的j a c o b i n 矩阵： 第4 4 页 硕士论文 渐进式瞄像建模系统中雕计算问题 j = 钆钆 o x lo x 丸帆 缸。 则f ( x ) 的梯度为 g ( x ) = r x x ) w a x ) = ，( x ) 7 ，( x ) ，( x ) 的h e s s i a n 矩阵为 g ( x ) ；兰( v ( x ) v ( x ) r + i ( x ) v z o ) ) ：，( x ) r t ，( x ) + s ( x ) ( 5 2 1 8 ) 其中， m s ( x ) = i ( z ) v2 ( 力 i a l 因此，目标函数f ( x 1 的二次模型为： m 。( x ) = 厂( 坼) + g ( 坼) 7 0 一) + 三。一) 7 g ( 扎) 一扎) = j 1 ，o 。) 7 r ( ) + d ( ) 7 ，( k ) 厂。一) + 丢。一致) 7 d ( h ) “) + s ( ) x x - - x k ) 从而，求解方程( 5 9 ) 的牛顿法可以表示为 x k 。= 一c ，( 坼) 7 ，( ) + s ( 以) ) _ j ( x k ) r r ( x k ) ( 5 2 1 9 ) 不难看出，使用数值的方法，矩阵g 。的二阶信l g 项s ( x ) 通常难以计算或者 需要花费很大的工作量。而牛顿方法的各种优化和修正其实也主要是针对s ( x ) 这一部分。在本文中，由于最终的优化方程是根据预先定义的基本几何体素和几 何体素之间几种内部、外部约束构成的，我们完全可以得到目标函数的j a c o b i n 矩阵、h e s s i a n 矩阵的解析形式，而不必使用数值近似。在此基础上，我们可以 得到二阶信息项s ( x ) 的准确值，这样可以大大的提高求解精度和求解速度。同 时，虽然优化方程是包含了三角函数的超越方程，但是如以上分析，其本质上仍 然只是非线性最4 - - 乘问题，具有相当明确的定义，因此使用通用的方法进行方 第4 5 页 硕士论文 渐进式图像建模系统中的计算问题 程求解在效率上并不是很好的考虑。由于采用了用户交互的手段，我们可以得到 与最优解相当接近的初值，并且目标函数在极小点附近应当与二次函数相接近， 牛顿方法在这种情况下会有非常好的表现。 在1 9 6 7 年，g o l d s t e i n 和p r i c e 还提出了另外一种针对牛顿方法的修正： 当q 非正定时，采用最速下降方向一既，其实质是将g o l d f e l d 提出的将牛顿方 向进行调整以偏向最速下降方向的思想进行极端化，即使用最速下降方向完全取 代牛顿方向。同时，g o l d s t e i n 和p r i c e 给出了一种角度法则用来选取迭代方向， 即： 以； = 一g k & ，如果c 。硝，一) r ； l - 既 其中r 0 是预先给定的常数，这样，搜索方向d k 总满足c o s ( 吐，一g 。) 坪， 从而保证了算法的收敛性。在本文中，对两个方向进行角度求解计算并不必要， 但是却提供了一种将两种优化方法综合起来的思路。 判断h e s s i a n 矩阵是否正定的算法需要耗费很大的计算量，而实际上应当 注意到，矩阵g 。是否正定对于迭代过程是否收敛是一个充分条件而并非必要。 如果能保证每一步迭代方向都是目标函数的下降方向，贝t j l l p 便g 。非正定，我们 也完全有可能得到一个收敛序列。因此，在进行每一步迭代的时候，针对当时具 体的凰，只要满足氍7 - g k g 。 0 即可，此时的迭代方向即是函数的下降方向。 但这时只有算法最终会收敛的结论，无法给出具体的收敛速度。在实际计算中， 因为矩阵q 的具体值随着函数迭代的进行一直在变化，与判断g 。是否正定相 比，这样会节省很多计算量。 另外还应考虑到当g k 奇异的情况，这时我们可以选用最速下降方向进行迭 代。因此，最终我们的算法是将最速下降方法和经过修正的牛顿方法进行综合， 即当条件合适的时候，使用牛顿方向进行迭代以保证最快的迭代求解速度；否则， 使用“最速下降方向”进行迭代，保证求解的正确性；同时，尽量使搜索方