（基础数学专业论文）用松弛金字塔算法配准的自标定多视角视觉曲面重构.pdf

论文题目 专业： 硕士生： 指导老师 用松弛金宇塔算法配准的自标定多视角视觉曲面重构 基础数学 吴竣峰 赵育求教授 摘要本文提出一种新的视觉曲面重构方法，用以从不同角度的照片中 重构曲面的形状和位置。这种方法用松弛金字塔算法进行配准，用基于奇异值 分解的标定方法进行几何标定。松弛金字塔算法是一种按基准点分层的由疏到 密的金字塔算法，并在每一层中用松弛法选择与基准点相应的配准点本文的 几何标定用奇异值分解逐步计算出摄像机运动的旋转和平移，是多视图下进行 几何摄像机标定的一种线性代数方法。 关键字：配准，标定重建，松弛金字塔算法，奇异值分解。 t n l e ： m a j o r ： n a i n e ： s u p e r v i 8 0 r ： a8 e l c a l i b r a t e dm u l t i v i e ws u r f a c er e c o n 8 t r u c t i o nm e 七h o d w i t hr e l a xp y r a 埘i dm a t c h i n g8 l g o r i t h m p u r em a 乇h e m 砒i c s j u n f e n gw u p r o f 瞄s o ry t l q i uz h a 0 a b s t r a c t t h i sp 印e rp r e s e n t san o v e lc o m p u t e rv i s i o m e t h o dt or e c o n - s t r u c tas u “a c ef r o md i 矗b r e n tv i e w s t h em e t h o da p 站i e sr e l a x 计r 咖dm e t h o d i nm a t c h j n g a n du 8 鹪as v e k b a 8 e da k o r i t h mt oc a l i b r a 七et h ec 啪e r af b l a x p y r a m i dm e t h o dg r o u p st h er e f e n c ep o i t 8m o r e8 n dm o r ed e i l 宕e j yi n t o1 8 册， 明ds e a r c l l gt h e j rc a r r 脚p o d i n gp o i n t si na n o t h e rv i e wl a 水rb yl a y e rb y 七h e m e a n so f r e i a x t i o n t h ec a l i b r a t i o n 村g o r i t h mi nt 1 1 i sp a p e ru s e ss v dt oc o r n _ p 1 1 t et h er o 七a t i o na n dt r a n s l a t i o no ft h ec a i n e r a i t sb n1 l n e 8 r 柚g d ) r am e t h o d f o rg e o m e t r i cc 蛐e r & c a l b r a t i o n k e yw o r d s ：m a t c h ，c 出i b r a t e ，r e c o n s t r u c t ，r e l a xp y r 舭l i da l g o r i t h m s v d i i 1 导言 视觉曲面重构是讨论如何从视觉信息中恢复出曲面的形状和位置的问题。 本文的视觉曲面重构处理的视觉信息主要是摄像机拍摄的照片。用专业术语来 说，照片是一种影像我们用摄像机从不同的角度拍摄同一个物体上同个曲 面之后怎样才能从这些不同角度拍摄下来的影像计算出物体的这个曲面呢? 本文称这一问题为多视角的视觉曲面重构并尝试对这个问题给出一个比较充 分的讨论。 视觉曲面重构是计算机视觉中的一个重要内容计算机视觉是一个处于知 识前沿的领域尽管在这一领域中经常可以看到一些缺乏权威性的现象，许多 有用的做法缺乏充分的理论基础，而一些理论在实际应用中又难以应用，但这 都只是这一领域初期发展所表现出来的一些表象也正因为如此，为这一领域 的发展略尽一分绵力，是作者作为一个初步涉足这领域的学术人所应尽的义 务。 虽然现在世界已经进入互联网时代。与计算机相关的很多信息技术都已 经日趋成熟，但计算机视觉仍然只处于自身发展的一个关键时期。人们从2 0 世 纪6 0 年代起就一直为利用计算机视觉原理构造出有用的计算机视觉系统而努 力，但这一目标只是在最近才得到初步实现。这主要是因为现在的计算机和图 像系统日趋普及使人们能比以前更容易得到这些设备，从而更容易从事计算 机视觉的相关研究与此同时，许多与计算机视觉相关的现实问题开始得到人 们的关注例如人们希望将收集的图片组织起来为他们所在的周围环境构造 三维模型又例如人们希望从视觉的角度来管理与编辑视频数据本文所讨论 的问题是前者的一部分。很多物体都由若干个曲面组成，因而用视觉信息构造 物体的三维模型常常要进行曲面的视觉重构。正因为如此。这一问题逐渐引 起了人们的注意因此对曲面视觉重构的研究不但是促进计算机视觉领域发展 的一个义务而且时机也已经到来 1 1 多视角的视觉曲面重构的主要环节 多视角视觉曲面重构主要通过三个环节来完成这三个环节是配准、标定 和重建。配准的目的是为了找出曲面上的点在不同视图中的投影的对应关系。 标定的目的是利用配准所获得的投影对应关系计算出各个视图之阃的摄像机模 型参数最后一个环节一重建一则是根据配准与标定所获取的数据恢复出曲面 的三维模型。 我们称摄像机在一个位置和一个角度拍摄的一个影像为一个视图。曲面上 各点的位置是兰维的。但它们在每个视图中的投影都是二维的因此，就单个 视图而言，从曲面上的点到视图中的投影，是一种不可逆的信息缺失。然而， 如果我们能够把各个视图有效地组织起来，这种信息缺失的不可逆性就能消 除，我们就能从视图中的投影的二维信息重构出各点位置的三维信息。 为了实现从二维到三维的这一逆向过程，我们首先要找出一个视图中的一 个投影点在另一个视图中对应哪一个投影点。这个找的过程就是配准因为配 准是在两个视图之间进行的，所以我们往往有必要区分这一过程中的两个视 图。其中的一个视图既要选定配准的区域，也要选定需要确定对应关系的投影 点，我们称这个视图为基准视图另外一个视图则要与基准视图建立起对应关 系。我们称这个视图为配准视图。相应地，我们称基准视图中需要确立对应关 系的投影点为基准点称配准视图中与基准点对应的投影点为配准点这样的 每一个基准点与配准点的配对，我们称为一对同名点因此。简而言之，配准 就是找出同名点的对应关系 在配准之后我们接着要进行的环节是标定。摄像机有就严密的数学模 型，用以描述它所执行的从三维到二维的拍摄过程的数学规律这些模型由多 个参数来控制其中，基准视图到配准视图的摄像机运动是参数中最重要的一 部分摄像机的运动包括平移和旋转确定了这些参数，就能够掌握摄像机的 投影规律标定就是这个确定摄像机模型参数的过程 经过配准和标定这两个环节，我们就能进入最后一个环节重建重建是 利用备个视图之间的同名点对应关系和摄像机的模型参数计算出曲面上各个点 的三维坐标的过程因为影像的摄取到配准到标定的各个环节都不可避免地产 生误差所以重建的关键问题是如何处理误菱所带来的负面影响同时，在重 建之后，如何评价备点的重建误差，也是应该考虑的一个问题。 总而言之，配准、标定和重建，就是多视角视觉曲面重构的三个环节 1 2 与视觉曲面重构相关的历史资料 尽管计算机视觉只是一个发展中的领域，但众多著名学者已经为这一领域 做了很多工作和贡献下面的历史资料不一定根全，只希望能够给出一个大致 的回顾 1 2 1 配准 配准主要有影像相关和特征匹配两大类方法目前很难说两者之间哪个更 好。作者个人的理解是，在纹理比较均匀和显著的情况下前者较为准确，但只 能产生稀疏的测量集 反之，后者在均匀区域下结果不好但在纹理区域处能 提供稠密对应其实两类方法且前都仍在不断进步之中因此上述评价来必符 合每一个实际情况 论证f 1 4 1 。b a k e r 和b i n f o r d 在1 9 8 1 年4 1 ，o h t 卿k 踊鲥e 在1 9 8 5 年f 2 8 1 ，提出并讨 论了匹配表面特征的顺序约束。b a k 盯和b i n 妇d 设计了利用顺序约束的一个特 征匹配的扫描线算法。o h t a 和k a n a d e 则使用动态规划对上述算法进行扫描线 内和扫描线外的优化除了上述两类方法，还有与配准有关的另一个层次的方 法在1 9 8 8 年l i m 和b i n f 0 1 m 提出了用金字塔算法匹配两幅图像中的曲线、表 面和体积【2 1 1 。在1 9 9 7 年，a y a c l l e 和n v e 日o n 将预测校正方法应用到图像学的图 像描述上【3 】 1 2 2 标定 标定涉及到几何摄像机模型，因而这里的历史资料包括了这方面的内容 与摄像机模型有关的包括：c r 8 i g 在1 9 8 9 年详细介绍了摄像机的坐标表示和 运动学【7 1 f b u 蝉蛆在1 9 9 3 年【0 1 ，h 缸t l e y 和z 蕊e r m 啦在2 0 0 0 年f 1 6 1 ，以及 f 8 u g e r 等在2 0 0 1 年1 1 ，给出了严密的几何摄像机模型。0 h t a 、m a e l l o b u 和 s a k a i 在1 9 8 1 年把类透视投影引入计算机视觉1 2 7 1 ，a j o j m o n o s 在1 9 9 0 年研究了它 的性质【2 1 b r i 在1 9 9 6 年分析了类透视投影和仿射投影的关系 5 1 口f a u g e r 和 p 印a d o p o u l o 在1 9 9 7 年推导了用p l u c k 甜c o d i n a t e s 坐标系表示的直线的透视投 影方程f l o 】 因为本文的标定涉及本征矩阵。所以下面补充与选方面( 以及它的推广一 基础矩阵) 有关的历史资料本征矩阵作为外极约束的代数形式，由l o n g u e t h i g 醇n s 在1 9 8 1 年提出【2 2 1 h u a n g 和n 姆r 拈在1 9 8 9 年进一步阐明了它的特性【1 8 1 基础矩阵由l u o g 在1 9 9 2 年f 2 4 】l u o n g 和f a u g e r 在1 9 9 6 年【2 5 1 引入。从对应点 集估计基础矩阵的鲁棒方法也包括z h a l l g 等( 1 9 9 5 ) f 3 4 】v i e v i u e 和n u g e r 在1 9 9 5 年讨论了内部参数改变的摄像机的情况 3 3 1 f a u g 盱鹋，l u o n g 和m 8 y b a n k 在2 0 0 4 年给出了用l o u p p a 方程处理内参数的方法 1 2 】。 1 2 3 重建 虽然本文在重建中的处理相对简单化，只恢复曲面上若干点的三维坐标， 但在某些情况下，这样做是远近不够的特别是在数字地面模型的重建中，人 们常常需要做更多的工作在2 0 世纪6 0 年代到7 0 年代，s c h u t 提出了咎动啦面拟 合法，a r t h mh a r d y 提出了多面函数内插法，k m u b 和m j k h a i l 提出了最小二乘 内插法e b n e r 提出了重建的有限元法。2 0 世纪7 0 年代，m a k 眦i c 提出了渐进 采样和混合采样方法到了近些年，重建这方面的方法得到了更多的发展 3 1 3 本文所做的工作 本文所做的工作主要是两个方面。一方面是几何标定的一种新方法，用本 征矩阵的估计值的奇异值分解计算几何摄像机模型的外参数另一方面是配准 的松弛金字塔算法。 1 3 1 本文的几何标定方法 嗣为内标定的相对独立性，不妨设摄像机是针孔摄像机设视图l 与视 图2 的同名点配对在成像坐标系中的坐标是 视图1 ： 扣1 1 ， l ，1 )( u 1 2 ，f l ，2 ) ( u l m 也，n ) 视图2 t ( “2 1 ，啦，1 )( u 2 ，2 ，u 2 ，2 ) ( t 2 ，n ，也一) 其中n 8 如何从这些数据计算出摄像机运动的平移方向国旋转冗? 为了计算出平移方向t 和旋转r ，我们首先计算出本征矩阵f 的估计值f 这 个估计值与矩阵 ，9 l ，ln ，2 口l ，9 g = l 鼍1 鼍二：一冀一| k 。一：，。 的乘积g 7 g 这个非负定矩阵的最小特征值的特征向量口有关其中， 出，l = 8 l j 0 2 ，j 野2 = 0 1 j b 2 ，如 毋，3 = 0 1 j 0 2 ，j 鲫4 。6 l j 0 2 j ， 毋，5 = 6 1 ，k ， 鲫r 6 = 0 1 ，j c 2 ，j 9 j t 2 q j d 2 j ， 珊b ；c l j 6 2 j ， 岛，9 1 c l ，c 2 j ， 鲰j 2 6 j = c k j = 址 皿 1 - j r ，= 拇万瓦石， 我们可以用带平移的反幂法求出这个特征向量日。设求出来 1 ；( ”lq 2 1 9 ) 7 ， 则 = ( 篆囊囊) 4 然后，对a 进行奇异僮分解，得到 a = e 1 呀， 其中， e = ( 1 a z a 。) ， - a z a 。 再取 亩= u e y r 这里 u= = v= 队， 。) h 本文着重指出，即使是在单位化的条件下，这个估计值也不一定是吲约近似 值，因为 e 盯e e ， 其中 o e ；士l 但其符号未知。 在计算出雪之后由上面计算出来的 u = ( 戮臻) 得出平移方向t 的估计值# ， f = ( u 1 3 ，“2 ，3 ，a ) 同样地，即使是在单位化的条件下，这个估计值也不一定是舳近似值，因为 f 叽- t ， 其中 但符号未知。 尽管我们不知道即和吼，但我们可以计算出a 矗吼从而我们能计算出唯 一的旋转矩阵r 为了计算出冗。我们计算每一个 岵= ( n l ，j6 l dc 1 j ) 圈：雪( a 引屯，jc 2 ，) 丁 。 玖 龇卜、_ 茗 根据叫的符号分两种情况：当w o 时，取 r = u p y t 当 时，取 = 一t 反之当口曼口时，取 t = 由于导言的篇幅所限，这里不可能对本文的标定方法做进一步的解释，因 此它将在后面用一节做更详细的讨论。 1 3 2本文的松弛金字塔配准算法 本文的松弛金字塔算法是一个渐进的配准算法，它是配准穷举法的替代算 法。配准穷举法的计算复杂度是指数级的。而松弛金字塔算法的计算复杂度则 只是多项式级的尽管名字非常相近，但本文的松弛金字塔算法与金字塔影像 相关算法很不同前者按基准点分层后者按影像频道分层本文的方法在每 一层中用松弛法选择配准点，从而用较小的计算量实现每一层的同名点配对 本文的松弛金字塔配准算法在后面也用一节做更详细的讨论 6 。触 = 叫 后然 2标定 几何标定，或简称标定。是用配准数据恢复摄像机几何参数的环节。摄像 机的拍摄过程是从三维到二维的投影过程，这一投影过程可以用几何摄像机模 型描述。摄像机模型由多个参数决定这些参数称为摄像机的几何参数。只要 计算出这些参数，那么我们就能把各个不同的视图组织起来，从而能通过最后 的重建环节，实现从二维到三维的逆向重构 本文的第一小节简要地解释摄像机模型及其参数。因为本文的几何标定方 法与计算机视觉中的本征矩阵有重要关系，所以本文的第二小节介绍计算机视 觉的本征矩阵这一节的第三小节将讨论本文的几何标定方法 2 1 摄像机的几何参数 摄像机的几何参数是指摄像机透视投影模登的几何参数，可以分为内参数 和外参数两大类。它们是摄像机的数学模型的重要内容在上世纪9 0 年代和本 世纪初，计算机视觉领域的几个著名学者，包括h 1 1 9 e r ，h 8 r t l e y 和z i e r m a n ， 为摄像机的几何模型的严密化做了很多工作和贡献。本文所用到的摄像机模型 是比较常用的一种内参数只与摄像机的内部结构有关。很多情况下可以事先 测定。外参数则是摄像机与外界的关系，特别是摄像机与被拍摄的曲面的关 系，因而不容易事先测定在本文的情况内参数是很容易事先测定的，因而 本文的算法不考虑内参数的影响至于内参数不能或者难以事先确定的情况， 有兴趣的读者可以参阅f b u g e r 凹，l u o n g 和m a y b 虮k 的c b i n e r as e l f c a u b r a t k n ： t h e o r ya n de x p e r i m e t 8 一文。 2 1 1 内参数 摄像机有五个内参数，并且这些内参数都和摄像机坐标系o k z k 执钝与 成像坐标系g u o 之间的关系有关。这五个内参数分别是像素的$ 轴比例因 子口和讥轴比例因子风成像坐标系e 删中u 轴与 轴的夹角口，还有光心0 在 成像坐标系g 饥中的u 轴坐标u o 和 轴坐标。 在摄像机坐标系d $ 讥强中，原点d 是摄像机光心所在的位置z k 轴指 向摄像机的右方，瓠轴指向摄像机的上方。强轴指向摄像机的前方。在摄像 机前方( “ o ) 的每一个点p = p k ，珊，稚) 都可以归一化为( 鲁，磐) ，然 后经过比例变换变为( 口氅，卢尝) ，然后因为成像坐标系的偏歪变为( o 磬( 1 一 c o t 一) ，声氅c s c 口) 最后被平移到 嚣( 1 一0 0 t 日) + t o ，口磬c 口+ ) 。因此从 摄像机坐标系到成像坐标系的变换是 f ”、：土ra n c o t 8 “o 口c 8 c p 7 、， 巩拈张 ， 、 伽 因为这些内参数是在本文的情况中是可以事先测定的，并且摄像机拍摄的 影像都可以用这些内参数做数字纠正，所以在本文后面的部分，我们总是假设 a = 口= l 。 口= ；， 砌= t b = 0 换而言之，我们假设所讨论的摄像机都是针孔摄像机 2 1 2 外参数 摄像机有六个外参数，并且这些外参数都和摄像机坐标系仇。k 魄张与世界 坐标系o 们的关系有关这六个外参数分别是从世界坐标系0 它v 。到摄像机坐 标系0 。i v 铋的旋转风的三个角度和平穆“的三个分量。它们有以下关系： ( ) = ( 繁? ) ( ：) 其中旋转m 是3 3 正交矩阵，平移“是3 l 矩阵， r = ( 。 玑钆) ，p ；( v = ) 7 2 2 本征矩阵 在双目立体视觉系统中，任何一个物点的第一个像点必定位于它的第二个 像点和两个摄像机光学中心所形成的平面中。在摄像机内部参数已知的情况 下，这种外极约束可以用代数方法描述为一个3 3 矩阵，称为本征矩阵。 假定摄像机的内参数已知，则通过影像纠正的方法总可以把它当作针孔 摄像机来对待在针孔摄像机的情形下设有两个观测点0 l 和仍，则任意物 点p ，都必使得三个向量石p ，瓯和石荔共面等价地，这可表示为 础- ( 西蕊帝) = o 设在d 处的摄像机坐标系是d z 挑硌，膏= l ，2 ，设刁蕊在d l 1 n 丑中的表示 是t ，并设从0 2 2 讹砘到d 1 2 1 掣l 瓤的旋转是尺即在坐标系0 2 2 抛靠中的自由向 量w 在坐标系0 l o l v l 以中的坐标为脚，则由上式可得 p l ( t x ( r p 2 ) ) ；o ( 1 ) 其中m 是帮在坐标系o 如靠中的坐标值得注意的是。对任意非零的常 数c 1 ，0 2 ，c a ，由( 1 ) 可得 c l p l ( c 扣( r c 3 p 2 ) ) ；c l c 2 c 3 ( p l ( t ( 丑p 2 ) ) ) ， 因而( 1 ) 等价于 扣l ， l ，1 ) t ( ( t 1 ，t 2 ，屯) t ( r 0 2 ，也，1 ) t ) ) = o ， 8 其中( “ ，v 女，1 ) 是p 在成像坐标系c k “k ”* 中的投影，而( o l ，赴，如) 则是t 方向的单 位矢量把上式写成矩阵形式，就得到 川( 三。莒静( 举) 一o ( u l 1 ) ( 亡3 o t 1 i rc ? l = o ( 2 ) 一t 2 t l o l 因此若记 e = ( 三。乏3 静， e = it a o t l j 丑， ( 3 ) 一2 t l o 则总有 一 ( “1 l1 ) e ( 吐2 啦! ) 1 耋o 这个矩阵e 就是我们所说的本征矩阵 如何从配准数据计算出本征矩阵，是我们关心的向题设物点p l ，p 2 ，r 在 针孔摄像机的成像坐标系n “1 n 和岛”2 口2 中的投影分别是 ( u l ，1 ， 1 1 ) ，( u l ，2 ，也，2 ) ，( u l 一，”1 ，n ) 和 2 ，l ，u 2 ，1 ) ，( 2 ，2 地2 ) ，( u 2 地，n ) ， 则我们关心的是如何从这些”k i 中求出矩阵e 设 e ；旧誉鬈1 ， 8 3 ie 8 。2e 3 ，3 则由( 2 ) 和( 3 ) 可得 川- 憾瓢扒军) 一o ，。m句，1e 3 ，28 3 ，3 1 上式叉可写成 ge = o ， ( 4 ) u l 。l 地，1 g ：l 磐2 i ： u 1 n 2 ，n e=( e 1 1 e i ，j t l ，1 也1u l ，l l ，1 u 2 ，lu 1 1 ”2 ，1 “1 ，2 也，2 “1 ，2 ”1 。2 2 饥，2 啦，2 1 “也一 “1 ，nu 1 n 地，n也，n 2 ，n e l ，3e 2 1e 2 ，2钾，3e 3 ，1e 3 ，2 9 1 1u 2 1 1 2u 2 t u 1 n“2 。n 8 卵) 7 引 因此，d 刖记a f ( 咧t h 和j e a np o n c e 所著的c o m p u t e rv i 8 i o n ：am 0 r d e r na p - p r o a c l l 在多视角几何学一章中提及一种求解同拘方法：当n 8 时，利用方程的 齐次性可以固定某个8 ，j 为1 ，例如固定 e 3 3 = 1 ， 就可以把它化为非齐次线性方程组 ； ( 一1 1 1 1 111 1 ) r e 1 1 e 1 2 e 1 3 e 2 1 e 2 2 屹3 e 3 1 e 3 ，2 当n = 8 时，这个方程组可以直接求解；当n 8 时，则可以用最小二乘法求 解当然，当输入数据有误差时，这样算出来的结果往往不符合本征矩阵应该 满足的条件，因而只能是本征矩阵的估计值。下面这一小节会讨论本征矩阵应 该满足的条件而这些条件在本文的几何标定方法中是相当重要的。 2 3 本文的几何标定方法 本文的几何标定方法是先计算本征矩阵e 的估计值，再解出摄像机的外参 数，包括平移t 和旋转矗， 首先，对上述平移t 和旋转矗，本文的单位同向本征矩阵是指可分解为 e = ( 三。葛3 毒，) r 的矩阵f ，其中 8 i + s ：+ s = 1 ( 5 ) ( 6 ) 并且 ( 。l ，。2 ，$ 3 ) t t = i l t n ( 7 ) 这里，( 6 ) 称为本征矩阵的单位化条件。( 7 ) 称为本征矩阵的同向条件如果没 有这两个条件，则只能称e 觏本征矩阵定义单位同向本征矩阵的目的是为了 让问题的解唯 下面开始给出一个引理和两个定理 1 0 、 l 2 n 似似：似 l 2 n地咖： j 二 一 饥札 1 2 n 坤? ：以 n = s l 吼 l 2 n地忱地 j 二 m 机 n l 2 n眦眦眦 l 2 n蛐曲呐 毗机 毗 1 2 nh蝉“ 毗虮 毗 ，jil 引理1 ( 差秉与旋转矩阵的关系) 设 “1 ，2u 1 3 、 ”2 ，2”2 ，3l u 3 ，2 “3 3 是旋转矩阵( 鄂行尉式为正钓正交矩降) 则 均j 。 = u ( 矿p ) r ， 一l 3 k = u e ( u p t ) 证明：因为矿是正交矩阵且d e t 矿 0 ，所以 又因为 ：；r ( 。，。) r“1 t l “2 ，l “3 ，1j 【”i ，2 “2 2 ”3 3j u 2 1 2 一u 2 ，2 u 3 ，1如1 u 1 2 一u 3 ，2 u 1 ，lu l ，l u 2 2 一u 1 ，2 u 2 ，1 一u 1 ，2一u 2 ，2一u 3 ，2 u 1 ，1u 2 ，1u 3 ，1 “1 3“2 ，3“3 3 一u l ，1 u 2 ，2 + u 1 。2 “2 ，1 o 一“3 ，l “2 ，2 + “3 2 “2 1 一“1 ，l u 3 2 + u 1 2 u s ，l u 2 ，1 u 3 ，j + u 2 ，2 “3 ，1 0 f 3 】。= 矿( 矿p ) t 同理可验证 一f u 3 】= 矿( u p r ) t 口 定理1 ( h u a i l g 和f h u g e r a s 韵本征矩阵奇异值定理) 3 3 矩佯e 为本赶矩阵 当a 仅当它的一个奇异值为o ，另锌两个奇异值指等 1 l u u u ， = u 厂卜芸。 0 o o o 0 l o 。o 。o o飞。帅 l 0 0 o d 0 一 ，亡0哪 ， = i i f | e p 崮 ，坩 u u 、0二 0 o 0 u u卜r j 浮芦0 r ” t 们伽们 “ j l 1 1 口0拟嚣吣=毗 本文对这个定理给出的证明是作者给出的，因而如果证明有误，是作者的错 误，而不是h u 曲g 和g e r 硒的错误。 证明：先证充分性设 e = u e y t 其中u 和y 都是正交矩阵， 趾( 3 。) ， 往证存在矢量( t 1 ，如，t 3 ) 和旋转矩阵r ，使得 e = ( 三。j 3 讣 为此分两种情况讨论： 当d e t ， 0 并且d e t 矿 o 时 e = u e y t = 口e ( v 尸) r ( u p ) y t = ( u e ( u p ) 7 ) ( u p y r ) 其中， 将引理1 运用于此，得 u e ( u p ) 7 = a u 3 1 。 若记冗= u p y 7 ，则由阢只y 都是正交矩阵并且行列式均为正，可知冠是旋转 矩阵。因而 e = a 【如】x r 是本征矩阵，对应c = ( 舳1 3 “2 。3 蛳，3 ) 当d 酏矿 o ，从而化为第一神情况 充分性证毕 下面证必要性设存在矢量t = ( t 1t 2 屯) 和旋转矩阵r 使得 e = 【f 1 。且， 这里 忙( 三。 往证存在正交矩阵u 和y ，使得 瓣) e = u y t 其中，若记a = 、压f 再i 碣，则 = f a1 为此，记u 。= ( u l p u 2 au 3 ，3 ) 7 并扩充 “3 ) 为r 的一组标准正交基 u 1 ，u 2 ，u 3 ) 则 u j = ( u l ju 2 ju 3 j ) t ， j = 1 ，2 ，3 是正交矩阵，并且 其中 于是若记 则y 是正交矩阵并且 必要性证毕口 u l ，2u 1 3 、 “2 ，2 3i u 3 ，2 “3 ，3 u e ( 矿p ) t = 嗍。 p = ( ) 矿= r t u p e ； ； = 嘲x r u e ( ，p r 丘 u 矿t h 如如 一一rx = 1 1 1 i u ”u “ ， = u 斛爿 奠滢擎i ， p _ ( 。1 ，) ， e = ( q - s ( 0 l p ) r ) ( ( 0 ，p ) q 手) = ( 0 1 s ( 口l p t ) r ) ( ( 0 1 p 7 ) q ) ， 这里，根据引理1 ，矩阵 。= 0 l s ( 0 l p ) 7 和矩阵 p ? 】。= 0 l s ( q l p 7 ) t 都是差乘矩阵，并且 i x _ 制。乩。vf 0 。一苫。甚1 ， 一u 2 ，3t 1 ，3 o 因而 。 t l =d e t y ( u l ，3 u 2 ，3 u 3 ，3 ) 1k 亡2 = 一d e t y ( u 1 ，3u 2 ，3u 3 ，3 ) 。， r l = q l 尸q j ， r 2 = q l p r q 满足d e t 冗1 = 1 ，d e t 冠2 = l ，r l ，r 2 都是正交矩阵，和 e = p 1 x r l = i 2 】x r 2 这样我们就构造出两个不同的分解了。 下面证明只有这两个分解满足条件。 设t 1 和屯满足 e ；p 1 】r l = p 2 】r 2 ， 则“和2 必定线性相关。事实上。若不然，则由 t 船7 一t e 矿= ( o o o ) ， 可知非负定对称矩阵曰e 7 的特征值为0 的特征向量至少有两个。但因为f 是非 零的本征矩阵，根据定理1 ，j 陋7 的特征值为0 的特征向量只有一个，矛盾 因为在证明定理1 时我们已经知道。本征矩阵e 的非零奇异值a 正是1 和2 的 欧氏长度， 慨0 2 = 1 1 2 = ， 所以“和亡2 不但线性相关，而且 t 1 = 士t 2 为了进一步得到0 1 和2 的关系，我们要证明只能有一个行列式为1 的正交 矩阵r l ，使得 e = 。r 1 1 5 设行列式为l 的正交矩阵r l 和盈满足 e = l 】r l = f t l 】r l 则 。l 只1 ) = e 对f t l 。进行奇异值分解，得 i 1 1 。= u ( 矿p ) 7 ， 这里， u= e ； p = a 盅 u 1 3 盘 u 2 3 = 3 5 d e t u ； 耻1 】。( r l 一五1 ) = u e ( ( u p ) r ( r 1 一袁1 ) ) = e 可得 ( p t 矿7 r 1 一毋v 7 壶1 ) 竺e 由此可知正交矩阵p r u t r l 和正交矩阵p t 矿r 直l 的第一行和第二行都相同，从 而联系正交矩阵的性质知p r u t r l 的第三行必定是_ p r 矿t 五1 的士1 倍。再注意 d e t p r u r r l ) = d e t p d e t ，d 札r 1 = 1 ， d e t ( p 7 护直1 ) = d e t p d 鼬c ，d e t 虎l ；1 ， 就可以知道第三行也相同，因而得到 ，矿月1 = f 矿7 矗l ， 从而等式两边同时乘以矿p 得 r 1 = r 1 上面的论述说明当 e = 耻l 】r 1 和 e = 。岛 1 6 是两个不同的分解时，必定 n t 2 又因为总有t 1 ；士t 2 ，所以这样的分解只能有两个，并且 t 1 = 一t 2 口 上面的定理1 给出了一个本征矩阵应该满足的条件，而定理2 则对本征矩阵 的分解进行了详细的讨论。这篇文章的几何标定算法正是用了这两个定理柬计 算摄像机的外参数的。具体的算法如下： 2 3 1 均衡化配准数据的权 为了使标定误差尽可能地小，我们首先要使每对同名点在标定的过程中的 权尽可能地一致为此根据成像坐标系侥u 1 仇和g 2 “2 ”2 中的n 对匹配数据 扣1 ，l ，”l ，i ) ( “2 ，1 ，啦，1 ) ( l ，2 ，”l ，2 ) 2 ，2 ， 2 ，2 ) 生成两组三维单位向量 扣l ，l ，b 1 ，1 ，c l ，1 ) ( 口l ，2 ，b l ，2 ，c 1 2 ) ( 衄，1 ，6 2 ，l ，c 2 ，1 ) ( 0 2 ，2 ，b 2 ，。2 ，2 ) ( “1 ，n ，”l ，n ) ( u 2 ，“，u 2 ，“) ( 口l 。n 加1 t n ，。1 m ) ( 0 2 6 2 mc 2 ，n ) 为了把这一点的理由说得更清楚 产生的误差的界限在均衡化权之后 是最小化函数 我们一起观察每对同名点在标定中所能 我们计算单位本征矩阵的估计值的方法 h 俾) = ( ( o l ，k 6 l ，kc m ) e ( 啦，女幻ic 2 ， ) 1 ) 2 - = l 如果不均衡化权，则对应的目标函数应该是 风( e ) = ( ( ( u ”毗，k1 ) e ( u 2 ，k 。，b 1 ) 7 ) 2 兰l 因为单位本征矩阵有两个奇异值是1 ，一个奇异值是0 ，所以 o s ( ( d 1 bb l ， c l ， ) e ( 口2 ，kb ，kc 2 ，k j l ) 2 s l ， o ( ( ( u i ， ， 1 ) 刀( “2 i 啦， 1 ) 1 ) 2 s r k 嚏 由此可知这两个目标函数是很不同的 1 7 = l j = = w r d 6 c 中其 2 3 2求目标函数h 的其中一个最小值点” 为了求出上述目标函数日( e ) 的其中一个最小值点 ，用上面生成的两组三 维单位向量生成一个9 的矩阵 9 1 1m t 2 9 l ，9 g = 一一0 9i ， i ： - ： l 卧，1 如，2 肌，9 这里， 毋1 =o l j 口2 j ， 野2 = o l j + b j ， 珊，3 = 0 1 j + c 2 ， 乃，4 = 6 1 j 十d 2 j ， 珊s = b 1 j + k j ， 毋，6 = 6 1 j 十c 2 j ， 毋，7 2c l j + 0 2 j 9 j ，b = c 1 ，j + b j ， 珊，9 = o l j + c 2 ，j 由曰和翻拘定义可以知道 日( f ) = 柙7 ( e ) g r g 叩( 司， 其中 叩( e ) 篁( e 1 ，le l ，2e 1 3e 2 ，le 2 2e 2 ，3e 3 ，le 3 ，2e 3 ，3 ) t 得到目标函数之后，我们还要决定最优化问题的约柬条件约束条件的选 择可以有很多例如，我们已经在本征矩阵的那一小节中介绍过取约束条件 为e 3 3 1 的算法但我们现在要避免用这样的约束条件，原因是很难事先知 道曰的哪个元素不是霉，而且固定不同的元素，最优化问题的有效区域就会不 同从而导致我们要在不同的意义下估计e 。一个较合理的约束条件是令 m e ) 0 2 = l ， 这里 怖炉归了百i 再瓦i 昏i 了i 砑万石 在这个约束条件下。我们就可以在统一的条件下寻找蚓均估计值 为了在约束条件胁( f ) = l 下找出日( e ) 的摄小值点目，我们用带平移的反 幂法对任给的e 0 ，矩阵点k = 伊g + e ，都是正定矩阵。从而它的逆日f 1 都 是正定矩阵设g 的特征值和对应的特征向量是 1a 2 o f l 如6 1 8 其中 a l a 2 o o ， 则皿的特征值是 l + e ， 2 + ， o + e ， 5 p 1 的特征值是 111 l + e 2 + 一a 9 + e 其中 。 a 9 时， 1 i mt = 士6 这个极限就是我们要求的 2 3 3 计算单位同向本征矩阵e 的估计值雪 设我们计算出 q = ( 吼q 2 叶9 ) 则我们可令 a ：f 琵篡翟1 ， 叩7 铂啦 做奇异值分解 a = h 曙， 其中， l 九i ， l b2 h 沁 豆= u y t u= e= v= c “， 。) - a ， 1 e 令以 可 就 “ ， h 吐 础d，id 如同在导言中所说的一样即使是在单位化的条件下，这个估计值也不一定 是目的近似值，因为 e 口b e ， 其中 船= 士1 但其符号未知 2 3 4 计算平移方向的估计值f 由上面计算出来的 u = ( 鞋强) 得出平移方向瑚估计值f f = ( u l ，3 ，”2 3 ，”3 ，3 ) r 同样地，即使是在单位化的条件下，这个估计值也不一定是啪近似值，因为 f 巩t ， 其中 但符号未知 2 3 5 计算旋转r 尽管我们不知道。e 和吼，但我们可以计算出口e - 叽从雨根据定理2 ，我们 能计算出唯一的旋转矩阵r 为了计算出口b 矶我们计算每一个 t 吩= ( n 1 j6 1 jc 1 j ) 同：亩( 口2 j 6 2 ，jc 2 ，j ) r 然后 ”2l q ，= l 就可以计算出 叼m = ! ，：；： 要验证这一结论，只需注意 用：亩 一( 巩矿f ) f c ) 。e = 一慨即) 嗍：r = ( 巩盯岳) ( f t t 7 ) r ， 从而，当配准数据无误差时。若记 口1 j =a r c c 0 8 ( ( 8 1 j 6 1 ，j c l j ) t ) ，。 岛j = a r c c o s ( 一t 7 r ( 口2 ，j6 2 j c 2 ，) 1 ) ， 则 ( 毋口苫) q = ( c o s ( 一口l 。j p 2 ，j ) + c 口i j s 段，j ) = ( 一o o s ( 虬+ 岛，) + c o s 风j c 傩岛，) = 8 i n 卢1 ，8 i n 岛j 0 仅当t 一士( q ，j6 1 ，jc l j ) 7 时q = o 当然，也可以根据叉乘的方向来验 计算出叼- 叽之后。根据引理l 和定理2 容易知道 r = 茹= 芸： 2 3 6 计算平移方向t 为了确定吼的符号以便确定t 的值，计算每个 乏：三：黧盔戡黜麓h0 2 j皇a r c o o s 一e ，r 她2 j 曲2 ，j ，e 2 ，j ) 1 ) ， 不难知道a 1 ，j 是方向( l j ，b l ，j ，c l ，j ) 与方向溯夹角的弧度，啦j 是方向一与方 向( 0 2 ，j ，幻加c 2 j ) 的夹角的弧度如果m = 1 ，那么n 1 ，j 和口2 ，j 是三角形的两个内 角的弧厦，从而 口l j + a 2 j 丌 因此只须再计算 。 a = ( 0 l j + ) j = 1 就可取 叽= 兰。，：嚣 从而按照 计算出平移方向t t = 仉t 3配准 配准是多视角视觉曲面重构的第一个环节这个环节的任务是找出不同视 图之间的同名点对应关系。同名点是物体上的同一个点在不同视图上的投影 点。为了确定投影点之间的这种对应关系，我们首先要固定一个基准视图，并 在上面指定要配准的基准点；然后，把另一个视图作为配准视图，并找出每个 基准点在这个视图上所对应的配准点 配准的主要方法有影像相关与特征相关两类。但不管是哪一类，部不可避 免地会出现错误匹配的现象会了减少错误匹配的发生概率，本文的松弛金字 塔算法考虑了各个基准点之间的联系。下面的这一小节，是对这种方法的介 绍。 3 1 松弛金宇塔算法 本文的松弛法考虑的是曲面上各点的几何关系。设观测点0 - 处的成像坐 标系是a “l ”i ，观测点0 2 处的成像坐标系是c k “2 如，西“l 吼中待匹配的点集 是 p l ， ，对每个p l 在岛u 2 抛中都有若干个匹配的可能值 p 2 ，1 ，马， ，2 ，b i m ， 它们对应的相关系数分别是跏，1 ，5 ”，却m 。本文的松弛法的任务是为每 个p 1 从这此可能值中挑选出最合理的一个作为匹配值p 2 n 为了让我们的算法限制在要重构的曲面上进行，我们首先在基准影像上选 择一个矩形区域，这个区域位于曲面之上。然后我们在配准影像上点出这个矩 形区域对应的四个角点的位置。将这两个影像和四个点的坐标作为输入参数启 动算法我们的初匹配就可以开始了。 我们将基准影像中的上述矩形区域等分为n n 部分然后击寻找划分 这n n 部分的m + 1 ) + 1 ) 个点在配准影像中的坐标因为其中有四个点的 对应坐标是已知的，所以实际上我们只需要找出舻+ 2 n 一3 个点的对应坐标 这个过程实际上可以近似地描述为一个隶目标函数擐大值的数学过程，这个目 标函数是 n n 壬= 由蟠， 涪l j = l 其中垂。j 是基准影像中的上述矩形区域的第 行第j 列部分依赖乎上述铲+ 2 n 一 3 个未知坐标在配准影像中所对应的区域与它本身之间的相关系数。 为此，我们首先求出每个未知点在配准影像中的坐标的可能值。这一步的 方法是用相关运算求出未知点在配准影像中的可能区域中的相关系数函数井 搜索出所有的这个函数的所有极大值点，这些极大值点就是可能值 然后，我们要在这些可能值中作出选择，为每一个未知点选择一个最好的 可能值。这里的最好是在上述目标函数的意义下而言的。最简单的方法是用穷 举法。设每个未知点都有m 个可能值，则在这些可能值下，这竹2 + 2 n 一3 个点 的搭配方案有m + 2 ”_ 3 个只要计算出这m + 2 n 一3 个搭配方案所对应的圣值， 我们就能知道哪个搭配方案是最好的尽管这个方法简单。