（计算机应用技术专业论文）三维重构中关键算法研究.pdf

安徽大学博士论文 摘要 计算机视觉的研究目标是从二维图像获取三维景物的结构信息，其过程是 一个复杂的逆问题，需要借助各种优化技术和射影几何理论来解决，而且对噪 声或离散化引起的误差极其敏感。图像匹配和摄像机标定是实现三维重构的基 础，但二者的求解是病态问题，所以对其研究具有一定的理论意义和实用价值。 本文认为，改进算法的着眼点应该是优化方法的寻求和约束条件的确定。在上 述思路指导下，本文给出了基于图谱理论基础上的图像特征匹配、基于图割优 化算法下的图像密集匹配、基于射影几何理论的摄像机自标定等算法。 本论文针对三维场景重构中关键步骤：图像匹配和摄像机标定展开研究 给出了如下匹配和标定算法： 1 ，基于图的l a p l a c e 谱的特征点匹配算法。根据两幅图像的特征点分别定义 其l a p l a c e 矩阵，分析该矩阵的特征值及特征向量，构造特征点匹配矩阵。根据 匹配矩阵元素的大小和位置信息，实现特征点匹配。并从理论上证明本算法在 对图像作等距变换或相似变换下能获得精确匹配。真实实验表明该算法匹配精 度可以达到8 0 以上。 2 基于图割优化的图像密集匹配算法。通过建立能量函数，把匹配问题转 化为能量函数最小化问题；并构造网络，建立能量与网络割的容量之间的联系； 最后利用图的网络流理论给出能重最小化解，从而获得图像匹配的视差数据。 与目前已有的基于图割匹配算法比较，本算法将标号从1 维向量推广到2 维向 量，适用于更一般情形下的视觉匹配，并且在全局上获得能量函数最小。真实 实验表明该算法可以达到7 5 以上的准确率。 3 。基于埸景平面结构信息的摄像机自标定算法。给出了场景中的平面与像 平面的单应关系、绝对二次曲线及其图像，以及虚圆点对摄像机内参数的约束 等显式形式。应用上述形式，给出了基于矩形、梯形和等边三角形等三种不同 场景平面结构信息的摄像机自标定方法。实验结果表明，所给出的方法都具有 安徽大学博士论文 较高的求解精度。 4 基于一维移动物体的双目装置自标定算法。给出了平移运动的一维物体 所在平面的虚圆点图像及其对摄像机内参数的约束，并给出了约束方程的数值 求解方法( 从而获得摄像机的内参数) ，进一步通过恢复空间点在摄像机坐标系 中的坐标，求解出双目摄像机之间的方位( 摄像机的外参数) 。对于一维物体的 一般刚体运动，给出了把它转化为平移运动的方法。模拟实验和真实图像实验 结果表明该方法具有较高的求解精度，同时也有一定的应用价值。 关键词：三维重构，图像匹配，摄像机标定，l a p l a c e 谱，图割，平面结构信息， 一维物体 i i 安徽大学博士论文 a b s t r a c t t h eo b j e c to fc o m p u 缸v i s i o ni st om a k e 恤c o n l p u t c rh a v e 也ea b i l 埘o f 姐d e r s t a i n g3 de n v i r o 姗e n t a li n 南m l a t i o n舶m2 di m a g e s ， w h i c hi sa c o m p l i c a t e di n v e r s ep r o b l e ms i l l c ei tr e c u r st 0t l l ec o m b i n a t o r i a lo p t i m i z a t i o n t e c l l i l i q l l e s 蚰dp r o j e c t i v eg e o m e 廿ym e o r ya t l di sv e r ys e n s i t i v et oe 玎o r sc a u s c db y n o i s e s 蛐dd i s c r e t i z a t i o n h n 硼r em a t c l l i n ga n d 锄e r ac a l i b r a t i o na r et l l ef 0 舶d a t i o n s f o rr e a l i 2 i n g3 d 嗽o n s 饥l c t i o n ，w h i c ha r eb 0 也a ：b n o 衄a lo np r o b l e m ss o l v i n g 。h e n c e r c s e a r c ho ni m a g em a t c h i n ga n dc 锄e r ac a l i b r a 士i o 玎h 酗b 0 协t 1 1 e o r e 廿c a 】s j g l 】i f i c 蛐c c 觚dp r a c t i c a lv 山e s w et h i n km a t 也ef o c u so fi m p r o v i n gn l ea b o v e 伽ok i n d so f a l g o r i t h m ss h o u l db es e a r c l l i n go p t i i n 铡o nm e t h o d sa n dd e t e r n l i l l i n gm ec o i l s 打a i m c o n d i t i o n s u n d e r & b o v ei d e a ，廿1 e 也e s i sp r e s e m sa l g o d t l l m so ff b a n l r em a t c h i n go f i m a g e sb 船e do ns p e c t l 谢f 印hm e o r y d e n s em a t c l l i n go fi m a g e sb 够e do ng r a p hc u t o p t i m i z a t i o n ，蛆dc 啦e 糟c a l i b 删o nb 晒e do np 蚵e c t i v eg e o m e 仃ym e o 巧 t h et 1 1 e s i sf b c u s e so nm e k e ya l g 嘶t h m so f3 dr e c o n s 仇l c t i o n ：i m a g ema _ t c h i n g 鼬dc 锄e r ac a l i b r a t i o n ，a n da o q u 如st h em a i na c h i e v e m e n t sa sf 0 1 l o w s ： l t h ea l g o r i m mo ff e a t i l r ep o i m sm a t c h 主n gb 鼬e do n l a p l a c i 觚s p e c t r a l 也e o r e y g i v e nf e a n i r ep o i n t so ft w oi m a g e s ，w ed e f h l e l 印l a c i a nm a 啊c e sr c s p e c t i v e l y a l l a l y s i s 也ee i g e n v a l u e s 锄de i g e n v e c t o r so fm em a 仃i c e s ，蛆dc o n s t m c taf b a 乱 p o i n t sm a t c h i l l gm 删x b yi 1 1 f o n n a t i o no fm a g n i t l l d ea n dp o s “i o no fe n 埘e si n 圮 m 8 t 出n gm 删x ，w er e a l i t l l ef c a t u r e p o i n 乜m a t c h i n g f u 坩1 e 玎n o r e ，w e t l l e o f e t i c a l l yp r o v et h a to u ra l g o 一也mc a l la c q u i r ea 1 1e x a c tm a t c h i n gu n d 盯锄 e q u i l o n g 仃黜f o m a 廿o no re q u i f b 珊订a 1 1 s f b m a t i o no ni m a g e s r e a le x p e 血l e 出 s h o wt l l a tt l l em a c l l i n gr a t em a ya t a i n8 0 u p w a r d s 2 t 1 1 ea l g o r 主廿l mo fd e i l s em 删n go fi m a g e sb a s e do ng r 印hc m so p t i m i z a t i o n f i r s t l y ，t h ee n e r g yf h n c 吐o ni se s t a b l i s h e d 锄d 1 ep r o b l e mo fm a t c h i n gc a nb e 订姐s f o h n e d 如t 0 也a to fe n e r g y 矗m c t i o nm i n i m i z a t i o n an e t w o r ki sc o n s t m c t e ds u c h m a tt l l ee i l e r g i e sc a nb er e l a t e dt o 也ec 印a c “i e so ft 量1 ec u t so ft l l en e t w o r k f i n a l l y ， i i i 安徽大学撙士论文 也em i n i n l i z a t i o no ft h ee n e r g yf h n c t i o ni sd b l a j h e db yt 王l et l l e o r yo fn e t 、 r o 】k - f l o w s ， 蚰dh 雠c et h ed i 印a r i t y 出妞a r eo b t a i n c d c o m p a r i n gw i 也s 啪ek i l o w na 1 9 0 r i t l l m s b 船e do ng r a p hc u t s ，也ea l g o r i t l l m i i l 血i sp 印e re x t e n d s t h e l d b e l f 如m1 dv e c t o r t o 2 dv e c t o r a n da d a p t sv i s l l a lm a t c 血i n go fm o r eg 雠e 蹦c a s ；向r t l l 蜘n o r et h e 8 l g o r i t h n lc 蛆o b t 毫i i t l 吐l ei n i n 油i z a t i o ni ng i o b a l r e a le x p e r i m e n 乜s h o wt h a t 龇 m a t c b 主n gr a t ec a na c h i e v e7 5 u p w a r d s 3 n l ea l g o d t h md f 姗e r as e l f 二c a l i b r a t i o nb a s e dd np i a n a r 曲咖a li n f b 咖a t i o n o fs c e n e s w eg i v ee x p l i c i tf o m l so fm eh o m o g r 印h yb e t w e e nap l a n ei n 也es c e n e a n d _ 【h a to fa ni r n a g e ，也ea b s o l u t ec o n i ca n di t si m a g e s ，a i l dt l l ec o n s 订a i m so fc i f c l l l a r p o i n t st on l ec a m e r ai n t r i n s i cp 煳e t e r s a p p l y i n ga b o v ef 0 皿s ，w e 垂v em e m o d so f c a m e r as e l f c a l i b r a t i o nb a s e do nt l 】r e ek i n d so f 口l a n a rs t m c t 眦l i n f o m l a t i o no fs c e n e 谢l i c ha r e 袱妇a 西e s ，i s o s c e l e st r 印e z o i d s ，e q u i l a t e r a lt r i a n 舀e s e x p e r i m e n t a lf e 姒t s s h o w 也a ta l lm e t l l o d sh a v el l i g ha c c u r a c y 4 t h ea l g o 打c l l mo fc 啪e r as e l f - c a l i b r a t i o nw i mm o v i l l g1 do b j e c t su s i n ga b i - c a m e r 船s c 札i n g f i r s t ，w eg i v e 廿l e 妇a 雩r e so fc i r c u i a rp o i n t sm t h ep l a n ew h j c h 也e 1 do b j e c t 仃眦s l a t e so n ，髓d1 1 l ec o n s 仃a i m so fm e mt om ec a m e r ai n t r i n s i cp a r a m e t e r s ， a n da l s og i v eam m l c r i c a ls o l v i n gm e m o do ft 1 1 ec o n s n a i m se q u a t i o n s ( a l l d 栅l c e o b t a i n 也ec 锄e r ai n l n 璐i cp a m m e t e r s ) b y c o v e r i n gt h ec 0 0 r d i n a t e so f3 dp o i n 协 u n d e rc 舡n e r ac o o r d i n a t e ss y s t c m ，w ec a nr e s o l v et h ep o s e sb e t 、e e nt w oc a m e r 船( i e t h ec 吼e me x t e m a lp a r a r n e t e r s ) f o rag e i l e r a lr i g i dm o t i o no f1 do b j e c t s ，w eg i v ea m e t l l o dw h i c h 岫s f o 釉si ti n t o 仃a n s l a t i 0 i l s e x p e r i m e m 甜r e s u l t so fb o t l ls i m u l a t e d d a t aa i l dr e a l - w o r l dd a t as h o wm 砒t l l i sm 础o dh a sah i g ha c c l l r a c y 啦d 删i c a l v a l u e s 融即7 0 r d s ：3 d 旭c o n s t n k t i o n ，油a g em a t c h j n g c 锄e r 8c a l i b r a t i o n ，l 印l a c i 髓s p e c 廿a ， 铲印hc m ，p l 蛆甜s t r u c t u r a l 妯f o m a t i o n ，1 do b j e c t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得塞徽太堂或其他教育机构的 学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：多7 纬签字日期：堋一年印月，驴日 学位论文版权使用授权书 本学位论文作者完全了解安徽大学有关保韬、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅本人授权安徽大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：多，缸 签字日期：声c 舻j 一年年月d 日 学位论文作者毕业去向：安徽大学 导师签名 签字日期 钐缸 训厂年华月，d 日 工作单位：安徽大学电子科学与技术学院 电话：0 5 5 1 - 5 1 0 7 3 2 4 通讯地址：合肥市肥西路3 号 邮编：2 3 0 0 3 9 安徽大学博士论文第一章绪论 第一章绪论 计算机视觉研究的一个重要目标是：使计算机具有通过二维图像认知三维环 境信息的能力，而这种能力通常是建立在三维景物的结构重构之上。 近十几年来，被计算机视觉界称之为几何计算机视觉的研究取得了显著进展 h a r t l e y 2 0 0 0 ，韦。2 0 0 2 】，它提出了由一幅、两幅或图像序列恢复三维景物的形 状和摄像机运动的新理论和新算法。与早期计算机视觉中得到广泛研究的、传统 的由运动求结构( s 仃u c t u r e f r o m m 0 t i o n ) ”的算法不同，它不要求预先已知摄 像机内参数( 可以允许内参数在摄像的过程中发生变化) ，而是直接通过图像求 解出摄像机内参数( 也称摄像机自标定) ，并进一步估计出景物的结构、运动( 可 以是景物中物体的运动或摄像机位置的变化) ， 这些三维景物重构的算法是建立在对多视图几何的理解和建模的基础上，本 质上是一种多参数估计问题，而恢复三维景物欧氏重构的个关键问题是摄像机 内参数估计。与科学和工程计算中的许多逆问题( i n v e r s e p r o b l e m ) 相似，它的 解以及解的鲁棒性都依赖于测量数据的预处理，而数据预处理的核心就是图像匹 配的准确度和鲁棒性问题。由三维景物到二维图像的过程不仅是射影几何框架下 一种降维的几何映射，而且是许多因素的函数，例如三维景物的几何特征( 包括 它们的形状、空间位置和相对位置) 、物理特征( 例如物体材料表面性质、物体 的颜色、光照) 以及摄像机参数等。因此，从二维图像信息反推三维结构是一个 复杂的、病态的逆问题，而且对噪声或离散化引起的误差极其敏感。 目前。对三维重构的研究，虽然国内外诸多学者已经做了大量的工作，并在 某些特定条件下取得局限应用，但是从某种意义上说，目前的研究成果在鲁棒性、 实用性方面都存在不足，可以说，图像匹配至今仍是计算机视觉中的一个基本难 题。事实上，图像匹配和摄像机标定仍然是当前计算机视觉领域( 特别是三维景 物重构) 研究的热点。 本章的余下部分，通过分析三维重构中的关键算法图像匹配和摄像机标 定在国内外的研究现状，我们认为改进上述算法的着眼点应该是优化方法的寻求 安徽大学博士论文 三维重构中关键算法研究 和约束条件的确定，并扼要地介绍本论文在此总思路下展开研究工作的框架。 1 1 图像匹配 图像匹配的任务是在两幅或多幅图像中寻找景物中某一物理点投影到不同 图像平面上的像素点之间的对应关系( 视差信息) 。这里，我们主要研究在运动 情况下拍摄的图像之间的匹配问题。这种运动可以是视点的运动，例如在双眼匹 配中，图像是由同一时间不同视点所拍摄的；也可以是物体的运动，例如在运动 匹配中，图像是由不同时刻所拍摄的。 图1 1 三角形原理从左边一幅图像无法确定像点x 所对应的空间点x 的具体 位置，但由两幅图像中的对应点x 和x 就能确定了。 在两幅或多幅图像中寻找对应点的过程就是图像匹配，图像匹配的几何原 理可以用图1 1 中示意的三角形原理加以说明。对于三维空间物体表面上的任意 一点x ，如果用单个摄像机c 观察，看到它在摄像机c 上的图像点位于x ，但 我们无法由x 得知x 的三维位星。事实上，在c x 连线上的任意一点x 在该图像 上的像点都是x ，因此，由x 点的位置，我们只知道空间点x 位于c x 连线上的 某一位置( 或者说，我们无法知道点x 的深度) 。但是，如果我们用左、右两个 摄像机c 与c 同时观察x 点；并且，能够确定在左摄像机c 上的点x 与在右摄 像机c 上的点f 是空间同一点x 的像点，情况就不同了，一旦我们知道了空间 安徽大学博士论文第一章绪论 点x 既位于c x 上，又位于c x 上，则点x 是c i 与c 两条直线的交点，即它 的三维位置是唯一确定的。因此，确定不同图像上对应点之间的匹配问题是进 行三维重构的第一步工作。 但是，如果左、右两个摄像机c 与c 不能同时观察到x 点，例如，假设摄 像机c 看到的是在c x 连线上的x 点的前一点x ，那么在左摄像机c 上的点i 与 在右摄像机c 上的点x 不是空间同一点x 的像点：换句话说，由于遮挡，点x 在 摄像机c 的图像上没有对应点。此外，几何失真、测量误差及噪声等因素都影 响匹配准确性。因此，图像匹配是一个瘸态问题。 根据视差数据的分配情况，匹配可以大致地分为稀疏视差匹配和密集视差匹 配两大类。稀疏视差匹配 h s i e h 1 9 9 2 】一般以图像上的特征点、线段等为匹配基 元，仅匹配两幅图像中某些特征区域，获得比较稀疏的结果。在计算机视觉的一 些具体应用中，例如图像识别和图像数据库的索引等，人们可以利用图像的低级 特征( 如特征点和特征线) 及其相互关系构造成结构图进行图像处理和识别。 密集视差匹配【s c h a r s t e 抽2 0 0 2 】以图像像素和其它特性作为匹配基元，通常 由候选点邻域间的相关程度作为判别依据，给出所有( 或几乎所有) 像素的视差 信息，为整体景物的三维重构提供必要的数据。 1 1 1 稀疏视差匹配 稀疏视差匹配基于图像特征的某种或多种相似性，这些特征可以是点，例如 图像经过简单去噪处理后的像素点、角点、边缘上的像素点 g r i m s o n 1 9 8 1 ；或 者是线段以及其他特征，例如区域的分割线【a y a c h e 1 9 8 7 】等。稀疏视差匹配方 法通常所需的计算量较少，并且在特征提取比较精确的前提下有较强的鲁棒性。 特征点匹配方法是稀疏视差匹配研究的一个重点。 经典的基于图像灰度相关的匹配是图像匹配的主要方法之一 s o n k a 2 0 0 2 】， 它主要依据不同像素的灰度、颜色和纹理的连惯性来测量。在许多情景中，如果 不同图像中的两个像素是景物中同一物理点的像，那么它们的灰度应当相似( 通 常称为l a m b e r t i 8 l l 假设或恒常亮度假设) 。大多数匹配算法使用此约束，但在实 际的场景中也存在若干例外。比如，如果景物中的物理点是镜面反射物体上的某 安徽大学博士论文三维重构中关键算法研究 一点，那么从不同角度观察到它的像的像素的灰度是不同的；又比如，现实生活 中常见的一种极端情形含有扁平的白色无纹理物体的场景( 如白墙、玻璃窗 等) ，其在图像中形成了一个均匀的亮度区域。寻找这样一个区域中点的对应时， 灰度相关性约束就失去了意义。 基于图像灰度相关的图像匹配方法以图像的灰度信息为基础，用灰度相关性 和相似性作为相关匹配判决准则，该方法易于理解和实现，但具有运算量大的缺 点，并且无法解决有遮挡、镜面反射、纹理相似等问题。更为严重的是，图像间 的畸变会导致图像直接相关运算变得毫无意义。因此，图像灰度相关仅适用于较 小畸变的情况。 而基于物体的角点或边缘上像素点等图像特征的对应，不直接利用图像灰 度，而是通过对灰度的预处理导出符号特征，有选择地采用能表示景物自身特 性的特征，通过更多地强调空间景物的结构信息来解决匹配过程中的歧义性。 如周骥等【周一2 0 0 2 】利用场景深度的局部连续性作为解决匹配过程中的歧义性约 束；z h 弛gz h e n g y o u 等( z h a l l g - 1 9 9 5 】利用了对极线约束( 如图1 1 所示，x 为左 图像中的点，由对极约束知，x 在右图像上的对应点x 一定在对极线l 上由于 不知道空间点x 的深度，因而不知道x 在对极线l ，上的确切位置，所以不能仅 使用对极线约束，但对极线约束将潜在的2 维搜索空间降为1 维。) ；章权兵 【章2 0 0 3 ，章2 0 0 4 】利用矩阵理论分别推导出了仿射变换和射影交换下图像点集 匹配的闭合公式，并利用所得闭合公式和随机抽样一致算法实现了图像的匹配。 从上文的，绍中我们不难看出：图像匹配就其数学的本质而言就是建立在某 些约束下的优化问题。因此为解决计算机视觉中的这个基本难题，人们广泛地 借用了各种优化算法，包括代数、几何和统计( 参数的或非参数的) 等方法。例 如，t r i g g s 【t r i g g s - 2 0 0 1 】引入了“联合特征分布( j o i n t f e a n l r e d i s t r i b u t i o n ) ”， 给出了利用统计技术求对应点的匹配方法；l u o 等【l u o - 2 0 0 2 】则利用了e m ( e x p e c t a t i o nm a x i n m m ) 算法来构建图像的匹配算法；s l l n 等【s u n 2 0 0 3 将双眼 匹配问题形式化为一个m a r k o v 网络问题，然后利用贝叶斯置信传播( b a y e s i a l l b e l i e f p r o p a g a t i o n ) 进行了求解；f 娩g i b b o n 等 f n z g i b b o n 一2 0 0 3 】利用 l e v e n b e r g m a r q u a r d t 迭代算法给出了一个点集匹配的鲁棒估计方法；d u f o 啪a u d 4 安徽大学博士论文第一章绪论 等【d u 向1 r n 卸d 2 0 0 4 】研究了不同分辨率图像的匹配问题。 同样，由于图像匹配就是一种建立在某些约束下的优化问题所以近年来， 图的谱方法在图像匹配问题的研究中也越来越受到关注。图谱理论在处理某些优 化问题时是一种有效的工具 c h u n g 一1 9 9 7 】，它在结构化学和邮路理论( r 0 u t h l g 1 k o r y ) 领域较早、较广泛地得到应用，但在计算机视觉领域的应用起步较晚。 初期的研究路线可以归纳为：根据图像的低级特征( 或模式) 及其相互关系构造 图：再利用图的亲和矩阵或邻接矩阵的特征值和特征向量，把图像特征( 或模式) 以向量的形式嵌入到图的特征空间( 即谱嵌入) ，建立在特征空间之上体现l 匹配 的矩阵；最终的匹配是以矩阵或向量的闭合形式显式给出。 综合分析所阅读的文献，发现几乎所有的研究都把图的构造和图的代数表示 作为重点。例如： u m e y a m a 【u m e y a m a - 1 9 8 8 用邻接矩阵( a d j a c e n c ym a t r i x ) 表示具有相同节 点和边结构的两幅图，采用矩阵特征分解的方法来寻找二邻接矩阵之间的最佳置 换矩阵( 以使得一个邻接矩阵和另一个经过置换相似后的矩阵之间的距离( 或范 数) 最小) ，从而实现了图之间的精确匹配，也就是说找到保持点邻接性的图节 点之间的对应关系。 借助结构化学的思想，s c o t 【和l o n g u e t - h i g g m s 【s c 眦一1 9 9 l 】根据两幅图像之 间点的距离构造联系矩阵 i n t e r i n l a g ep o i n ta s s o c i a t i o nm a t r i x 】，对此矩阵进行 s v d 分解，获得对应关系，这种方法可以适用于大小不同的点集，但在点集之 间存在较大旋转的情况下，匹配效果不好。 为了克服s c o t t 和l o n g l l e t - h i g g i n s 方法的不足，s h 印i r o 和b r a d y 【s h 印i r o - 1 9 9 2 】 根据图像内部点之间的距离构造亲和矩阵 i n 拄a i i n a g ep o i n tp r o x i i l l 时m a 订i x 】。其 方法的主要思想是：对同一个图像，利用点之间距离的高斯函数值构造亲和矩阵， 分别计算亲和矩阵的特征值和特征向量。根据特征值大小对特征向量排序，这些 有序的特征向量构成一个正交矩阵，用正交矩阵的行向量表示图像的点特征，而 行向量之间距离的大小反映了点特征之间的亲近程度，从而获得了匹配。在点集 大小相同的条件下，这种方法不受随机点抖动和仿射、旋转与缩放的影响，可以 安徽大学| 毒士论文三维重构中关键算法研究 给出鲁棒的结果。 h o 姗l l d 和s o s 豫【h o m u d 1 9 9 5 基于线连通图的内在( i i l l m a n e m a l ) 多项式构 造l a p l a c e 矩阵，通过比较多项式的系数能够对一个大容量的线框图数据库进行 检索。 由于特征向量的计算已经有现成、高效的线性代数软件，且多数算法都采用 成熟的s v d 分解的方法；w j i s s 等m i s s 1 9 9 9 】对匹配和分割中所用到的大多数 矩阵分解方法进行了比较，对所用到的亲和矩阵进行评价，并指出如果对矩阵进 行适当的归一化，算法性能可以达到很大改进的结论。 此外，谱方法与其它优化方法的有效结合在不同场合也有较好的应用结果。 例如： 文献 s 8 r k a 卜2 0 0 0 】中介绍了如何将图谱方法和自学习分组结构组合起来使 用。 文献【s l l i - 1 9 9 7 】把图像或数据分割问题转化为图的规范割( n o 眦a l i 嚣e dc u t ) 最小化问题，而后者可以通过计算图的l 印l a c e 矩阵的第二特征向量( 对应于第 二特征值) 而获得。 文献 c a r c 鹊s o i l i - 2 0 0 3 a 把图谱分析方法和双步( d u a l s t e p ) e m 算法结合起 来，通过点的亲和矩阵来获得点匹配的概率。为了获得更精确的匹配结果，文献 【c a r c a s s o n i - 2 0 0 3 b 】采用了一种分层方法来解决匹配问题，在高层次上，通过模式 分析得到点聚类中心的对应，在低层次上用聚类中心对应来约束个体点的对应。 文献【m y e r s - 2 0 0 1 】提出了贝叶斯框架下的基于多模式的遗传算法，解决图像 中不确定特征点集的匹配问题。 文献【b g o e 乜【e a 2 0 0 2 】引入了分类估计算法( e s t i m a t i o no fd i s t r i b u t i o n a 1 9 0 r i n l r n s ) 实现不精确图的匹配。 根据文献的报道，我们认为目前用图理论来解决图像的匹配、目标识别和图 像分割的研究已取得了一定进展，在特征点( 或特征线) 的提取比较精确的情况 下，图谱技术可以获得快速有效的匹配和聚类。虽然图谱技术在计算机视觉中的 应用仍存在许多待解决的问题，但这种新方法的前景令人鼓舞。然而，特别遗憾 的是这些初期研究并没有引起计算机视觉研究界的兴趣，甚至缺乏认同。2 0 0 4 塞堂奎兰整主丝奎 茎= 童堑笙 年7 月l a 、】v r e i l c eb 刚【c l y 国家实验室d i r l g 课题组在i c m l ( i n t 啪8 t i o n a l c o n f e r e l l c eo nm a c h i n el e a m i n g ) 会议上作了关于谱聚类的工作专题报告 d l g 2 0 0 4 】，才引起计算机视觉研究界的关注。 通过上述分析，我们认为：图的邻接谱技术与计算机视觉的结合已得到许多 有价值的结论，而且，如果应用图谱理论较新的研究成果( 如图的l a p l a c e 谱理 论) 研究上述问题，一定会得到更多有价值的结论。从某种意义上说，图的l 坤l 踮e 谱包含的信息比邻接谱多，而且更加自然和重要( m o h 盯1 9 9 1 ) 。综述文章 m e r r i s - 1 9 9 4 】、【m o h 小1 9 9 1 】以及专著 c h 蛆g - 1 9 9 7 中都报道了l a p l 8 c e 谱研究 中的若干专题以及应用，这些最新的研究成果为图理论在计算机视觉中应用，特 别是在图像匹配和模式识别的研究中，提供了理论基础和可以借鉴的新方法。 1 1 2 密集视差匹配 从本质上说，密集视差匹配与稀疏视差匹配是类同的。但是，因为密集视差 匹配原则上要求每一个像素的对应关系，因此计算量更大，挑战性更强并得到更 多的关注。目前，我们了解到的密集匹葛已算法包括：基于光流的算法【h o m 1 9 8 1 】， 相关算法【g e n n e r y 一1 9 8 0 ，运动模型的层描述算法【d 蛳1 1 1 9 9 1 】和没有运动模型 的层描述算法【w e i s s 1 9 9 7 】，动态规划算法【o h t a - 1 9 8 5 】，模拟退火算法 【( k n 脚卜1 9 8 4 ，m a n _ 0 q l l i i l - 1 9 8 7 ，b a m a r d - 1 9 8 9 】等。然而，这些算法仅在较理想的 条件( 如低噪声和相当好的纹理数据等) 下，才能得到较好的结果；但是，在较 差的条件下，这些算法的性能下降很快。 近年来，随着基于图方法的优化算法引入到计算机视觉中的匹配、聚类等关 键问题研究中，一种将密集视差匹藉己转化为基于图割( g r a p hc u t ) 的能量函数 最小化问题的研究倍受关注；特别是在s c 妇j l l 和s z e l i s k i ( 后者为微软研究 院专家) s c h a r s t e i l l 2 0 0 2 】，s z e l i s k i 和z a b m 【s z e l i s k i 2 0 0 0 】发表他们非常有 影响的算法比较研究结果之后。他们把当前常用的几个优化算法进行了比较( 见 图1 2 ) ，发现：与传统的8 种算法( 如模拟退火法、m 估计法等) 相比，图割优 化算法不仅总体精度高( 青色) ，而且在不连续区域( 紫色) 和低纹理区域( 绿 色) 精度也比其它方法都高。不仅如此，即便有些方法( 例如模拟退火方法) 的 7 塞鍪奎差竖主堡塞三丝蔓塑主茎堡墨鎏受塑 精度与图割算法的精度接近，但图割的算法比模拟退火算法在优化过程中收敛速 度更快( 见图1 _ 3 ) 。 图1 2 ：圈割方法与当前常用的几个优化算法的精度的比较，其中青色衰示总 体误差比，紫色表示不连续区域误差比，绿色表示低纹理区域误差比。 1 0 1 图1 3 ：图剖方法与模拟退火方法收敛情况对比，其中蓝色表示模拟退火方法， 绿色表示圈割方法。 显然，由于图像像素的数目巨大，能量函数的维数也就巨大；而且由于图像 匹配的病态特征，不免有许多局部最小，如果采用传统的优化方法如梯度下降法 和模拟退火法，难免计算代价大，实时性差，并易陷于局部最小。图割优化方法 之所以在所比较的几种优化方法算法中表现出明显的优势其中个重要的原因 淼裟淼黧裟。 i i 室塑查堂堡主造塞墨二妻堕丝 是：它们把所研究问题的不同约束项( 包括软约柬和硬约束) 纳入到能量函数( 即 目标函数) 中，问题的可能解对应到某个有限实数子集( 即标号集) 上的映射， 通过构造恰当的图网络，能量函数最小化问题转化为图割框架下的组合优化问 题，并通过图的网络流理论实现最小能量的求解。 在基于图割的能量函数优化问题研究上，z a b j h 课题组提出了基于图割的两 种能量最小化算法f b o y k o v 2 0 0 l 】：扩张算法和交换算法。他们的算法在某些特 定情况下( 如二值图像) 可以找到全局最小的能量，并且扩张算法在相差一个常 数的意义下可以求得全局最小的能量。他们不仅在理论上给出能量函数能够用图 割得到优化的必要条件【k o l m o g o r o v 2 0 0 2 】，还提供了用图割优化能量函数的一 个通用的图网络构造方法。当然他们的算法也存在进一步改进的地方：例如选取 更恰当的约束条件( 如梯度光滑代价) 、自动设置参数以及适当计算亚像素级的 视差。 另外，我们发现在星前几乎所有的基于图割的能量函数最小化求解中 【r o y - 1 9 9 8 ，i s l l i k a w a 一1 9 9 8 ，b o y k o v - 2 0 0 1 ，v e k s l e r 1 9 9 9 ，k o l m o g o r o v 2 0 0 l ， k 0 1 m o g o r o v - 2 0 0 2 ，k o l m o g o r o v 2 0 0 4 】，全局优化算法仅能处理一维标号问题( 即 假定摄像机只沿摄像机x 轴或y 轴方向作纯平移运动) ，这显然远远不能适 用于双眼匹配或目标跟踪应用的要求，必须改进已有算法，寻求二维标号处理的 算法。此外，如何针对不同的应用问题，最佳能量函数的构造方法及其选择准则 和图网络构造方法也是当前有较大研究空间的问题。 1 2 摄像机标定 摄像机标定是计箕机视觉领域中从二维图像获取三维欧氏结构信息必不可 少的关键一步，因为在摄像机未标定情形下，无法得到三维结构的欧氏信息， 而只能实现射影重构。 传统的标定方法 t s a i 一1 9 8 6 ，z l l a n g - 1 9 9 9 ，m e n g - 2 0 0 0 】是通过测量一个结构 已知的物体( 如标定块) 在图像平面中的成像来标定摄像机的。由于此类方法需 要有精度很高的标定块。所以其实际应用受到了很大限制，例如不适用于在线标 定和不可能使用标定块的场合，比如空间机器人、在危险恶劣环境下工作的机器 安徽大学博士论文三维重构中关键算法研究 人等。 基于主动视觉系统的自标定方法是通过控制摄像机的运动，如绕光心旋转 【h a n l e y - 1 9 9 7 】或纯平移【m o o i l s 1 9 9 6 ，m a 1 9 9 6 】等，获取多幅图像来标定内参数。 该方法的优点是算法简单，往往能获得线性解【m a 1 9 9 6 】，可以克服传统标定方 法的某些缺点，但它需要一个可以精确控制的主动视觉平台，实际应用也受到了 一定的限制，不能适用于摄像机运动未知或无法控制的场合( 如手持摄像机等) 。 近十几年来，被计算机视觉界称之为几何计算机视觉的研究提出了由一幅、 两幅或图像序列恢复三维景物的形状和摄像机运动的新理论和新算法。它不要求 预先已知摄像机的内参数( 并且允许内参数在摄像的过程中发生变化) ，可以对 摄像机进行自标定( s e l f - c a l i b r a t i o n ) ，并进一步地从图像估计出景物的结构、运 动( 可以是景物中物体的运动或摄像机位置变化) 。 自标定方法克服了传统方法和基于主动视觉方法的缺点，它不需要标定块， 也不需要控制摄像机的运动，而仅仅依靠多幅场景图像对应点之间的关系直接进 行标定。自从1 9 9 2 年f a u g e r 嬲，l u o n g ，m a y b a i l k 【f a u g e r a s 1 9 9 2 ，m a y b a i l k 1 9 9 2 首次提出摄像机自标定的思想后，摄像机自标定及相关研究己成为计算机视觉领 域的研究热点之一。近年来在国际计算机视觉会议( i c c v ) 、欧洲计算机视觉会 议( e c c v ) 、计算机视觉和模式识别会议( c v p r ) 、国际模式识别会议( i c p r ) 以及相关领域的重要国际杂志上大量相关内容文章的问世充分说明了这一点。在 摄像机自标定研究方面，国际上有代表性的研究组有：英国牛津大学的z i s s e m 眦 组，比利时的v 孤g o o l 组，瑞典的h e y d 组，法国的f a u g e r a s 组和1 h g g s 及s t i l | m 组，美国1 1 1 i n o i s 大学的m a ，m i c m s o f 【研究院的张正友，澳大利亚的h a n l e y 。 以色列的s h 略h u a 等。在这方面，最完善的参考书首推2 0 0 0 年出版的由h a n l e y 和z i s s e 肌a n 合著的m u m p l e e wg e o m 哪i nc o n l p u t e r s i o n 一书 h 8 n l e y 2 0 0 0 】。 尽管文献中有各式各样摄像机自标定方法的报导，但大多数研究方法的本 质均是基于射影变换的不变量：绝对二次曲线( a b s o l u t ec o l l i c ) 或其对偶 绝对二次曲面( a b s o l l 船q u a 越c ) 的方法。例如： 塞墼奎堂堕主望壅苎= 童堕丝 f a u g e f a s ，l u o n g ，m a y b a n k 等提出的自标定方法是：先利用绝对二次曲线的 像和极线变换的概念推导出融砷p a 方程，然后再求解融u p p a 方程【m a 1 9 9 6 ， h a m c y - 1 9 9 2 。最早，f a u g e m s ，m a y b a n k 等 f a u g e r 髂一1 9 9 2 ，m a y b 趾k - 1 9 9 2 】提出 的算法完全基于代数几何的概念，但算法对噪声极其敏感，普通计算机的浮点运 算已不足以满足其要求。而h o n g 【l u o n g 1 9 9 2