英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
g2o：图形优化的一般框架
摘要：在机器人和计算机视觉许多流行的问题包括各种类型的同步定位与地图创建（SLAM）或束调整（BA）可以表述为一个可以用图形表示的最小二乘法优化的误差函数。本文介绍了此类问题的一般结构，并且提出了G 2O，一个为了优化基于图的非线性误差函数的一个开源的C 框架。我们的系统被设计成易于扩展到各种各样的问题，并且一个新的问题通常可以在几行代码中指定。目前的成果为SLAM和BA的几种变体提供了解决方案。我们提供广泛的真实世界和模拟数据集的评估。结果表明，在一般情况下，对于特定的问题G 2o提供的性能相当于目前使用的最先进技术的方案。
机器人和计算机视觉中的一系列问题涉及到可以用图表示的非线性误差函数的最小化。典型的实例是同步定位和地图创建（SLAM）[ 19 ]，[ 5 ]，[ 22 ]，[ 16 ]，[ 26 ]或束调整[ BA ] [ 27 ]，[ 15 ]，[ 18 ]。这些问题的总体目标是找到参数或状态变量的配置，最大限度地解释受高斯噪声影响的一组测量量。例如，在基于图的SLAM中，状态变量可以是环境中机器人的位置，也可以是地图上可以用机器人的传感器观察到的地标位置。因此，测量量仅依赖于状态变量的相对位置，如连续两个姿势之间的一个里程计测量只取决于连接的姿势。同样，在BA或基于地标的SLAM中，三维点或地标的一个测量量只取决于所观察点在世界坐标上的位置和传感器的位置。
所有这些问题都可以用图表示。而图中的每个节点代表一个优化的状态变量，两个变量之间的每个边代表对它连接的两个节点的成对观察。在文献中，已经提出了许多方法来解决这类问题。一个新的成就是使用标准的方法如Gauss Newton法，Levenberg Marquardt（LM）法、Gauss-Seidel松弛，或梯度下降法的变体通常提供大多数应用程序可接受的结果。然而，为了达到最大的性能，需要大量的努力和领域知识。
在本文中，我们描述了一个一般的框架进行优化这个可以表示为一个图形非线性最小二乘问题。我们称这种框架为G2O（一般图优化）。图1给出了一个可以通过使用G 2O作为后端优化来解决的各种问题的概述。所提出的系统表想出与国家的最先进的算法相媲美的性能，同时能够接受一般形式的非线性测量。
我们通过
bull;利用图的稀疏连通性，
bull;利用上述问题中经常出现的图的特殊结构，
bull;用先进的方法求解稀疏线性系统，
bull;利用SIMD指令等现代处理器的特性，优化使用缓存的算法来实现效率。
图1.用我们的系统处理的实际数据集：（a）的第一行显示维多利亚公园数据集，其中包括二维测距和二维地标测量。 （a）的第二行描绘了多级停车库的3D姿态图。 左图显示了初始状态，右列显示了优化过程的相应结果。 （b）对威尼斯束调整数据集进行优化后的完整和缩放视图。 该数据集由871个相机姿态和2,838,740个投影组成。
除了它的效率，G2 O是高度的通用的和可扩展的：一个二维的SLAM算法可以用不超过30行的C 代码实现。用户只需指定误差函数及其参数。
本文将g 2O应用于不同类别的最小二乘优化问题，并比较其性能实现特定问题算法的算法的优缺点。我们提出了一套在大量真实世界和模拟数据集上进行的评估；在所有实验中，G 2O表现出的性能与其他的最先进的方法相媲美，在一些情况下甚至优于他们。
本文的其余部分如下行文。我们首先讨论相关的工作，特别强调SLAM和束调整问题的解决方案。随后，在第三节我们描述的通过我们的系统解决的graphembeddable优化问题，并讨论通过高斯牛顿法或LM解决非线性最小二乘法。在第四节中，我们将讨论我们的成果所提供的特性。最后，在第五节中，我们提出了一个广泛的实验评估的G 2O，并比较它与其他目前国家的最先进的，特定于问题的方法。
相关的工作
在过去，图形优化问题已经在机器人学和计算机视觉领域得到了广泛的研究。一个开创性的工作，是Lu和Milios [ 19 ]在两次扫描之间的相对运动运用扫描匹配法测量，并且结果图是通过迭代线性优化。虽然在那个时候，优化的图形在实时性能方面被认为太耗时了，发展直线求解器的最新进展（例如，[ 4 ]），基于图形的SLAM重新流行，并提出了大量各种不同的方法来解决SLAM的图形优化的问题。例如，霍华德等人。[ 12 ]应用松弛度来绘制地图。Duckett等人。[ 6 ]提出了利用 Gauss-Seide松弛法最小化网络约束中的误差。弗里斯等人[ 8 ]介绍了多级松弛（MLR），Gauss Seidel松弛的一个变形形式，适用于在不同分辨率水平的松弛。最近，奥尔森等人。【22】提出了一种梯度下降法来优化位姿图。后来，grisetti等人。[ 10 ]通过采用基于树的参数化来提高收敛速度，从而扩展了这种方法。这两种方法都很有力的证明了初始猜测都，而且很容易实现。然而，他们假定协方差大致是球形的，从而优化姿势图在一些约束与零空间协方差或特征值的实质差异上有很多困难。
图优化可以被看作是一个非线性最小二乘问题，这通常是通过在当前状态下形成一个线性系统求解，迭代。求解线性系统的一个很有前途的技术是预处理共轭梯度法（PCG），这被Konolige [ 17 ]以及蒙特莫罗和Thrun [ 20 ]用作大型稀疏的姿态约束系统的高效的求解器。由于它在解决某些问题上效率高，G 2O包括一个稀疏的PCG解算器的成果，它应用块雅可比预调节器[ 13 ]。
图2.这个例子说明了如何用一个图来表示一个目标函数。
最近，Dellaert和他的同事们提出了一个系统，称为[ 5 ]，他们使用稀疏直接线性求解器[ 4 ]实现的。凯斯等人。[ 14 ]介绍了这个的变形叫iSAM，它能够更新与非线性最小二乘问题相关的线性矩阵。Konolige等人展现了如何[ 16 ]利用线性系统的典型稀疏结构有效地构造线性矩阵。然而，后一种方法仅限于二维姿态图。在g2o中我们和这些系统有着相似的想法。我们的系统可以应用于SLAM和BA优化问题的所有变体，例如，2D SLAM与地标，使用单眼相机的BA，或使用立体视觉的BA。然而，相比于这些系统在我们用于评估上的所有数据的表现，G 2O显示了显著的性能改进。
在计算机视觉中，稀疏束平差法（27）是一种非线性的最小二乘法，它利用点和摄像机姿态之间的雅可比矩阵的稀疏性。最近，已经有几个系统[ 15 ]，推进相似的线性求解器的概念[ 13 ]，并且为大型系统Schur降维提供有效计算（见第iii-d）（sim;100m稀疏矩阵的元素）。也有一些基于非线性共轭梯度，没有形成明确的线性系统的新系统[ 1 ]，[ 2 ]；这些系统收敛比较慢，但可以在非常大的数据集上工作（sim;1000m矩阵元素）。在本文中，我们比较g2o与SSBA系统[ 15 ]，一个至今表现最好的公开可用的系统。
III.基于最小二乘法的非线性图优化
机器人或计算机视觉中的许多问题可以通过找到这种形式的函数的最小值来解决：
（1）
（2）
在这里， 是一个向量参数，其中每个 表示一类的参数块，和Ωij分别代表均值和约束有关的参数 和 的信息矩阵，是一个衡量参数块和有多满足约束信息矩阵 的向量误差函数，当和完全满足约束时，它是一个0向量。
为了简便，在本文的其余部分中，我们将对误差函数指数的测量进行编码：
（3）
注意，每个错误函数、每个参数块和每个误差函数都可以跨越不同的空间。这种形式的一个问题可以用一个有向图有效地表示。图中一个节点i代表参数块 并且在节点i和j之间的一条边代表两个参数块 和 之间的一个约束。图2显示了一个图和一个目标函数之间的映射的例子。
A.最小二乘法优化
如果一个好的初始猜测参数是已知的，方程（2）的数值解可以通过使用流行的高斯牛顿或LM算法[ 23，15.5 ]得出。其思想是用一阶泰勒公式在最初猜测附近展开来近似误差函数。
（4）
（5）
在这里，是在初始值中计算的雅可比式，并且 。将方程（5）带入方程（1）中的误差项，我们得到
用这个局部近似，我们可以重写公式（1）中给出的函数f（x）为：
公式（13）中的二次形式是由公式（12）通过设置 ， 和得到的。它可以通过求解线性系统在中最小化。
这里，H是系统的信息矩阵。解决的办法是通过增加增量对初始猜得到的。
流行的高斯牛顿算法在方程（13）中线性化迭代，方程（14）的答案，更新的一步式（15）。在每次迭代中，以前的解决方案被用作线性化点和初始猜测直到满足给定的终止准则。
LM算法引入一个阻尼因子和对Gauss Newton的备份操作来控制收敛。而不是解决公式14，LM解决了阻尼版本
这里lambda;是一个阻尼因子：lambda;越高，Delta;x越小。这对于控制非线性表面的取值范围来说很有用。 LM算法背后的想法是动态地控制阻尼因子。在每次迭代中新配置的误差被监视。如果新的误差低于前一个， 下一次迭代lambda;下降。否则，解决方案将被恢复并且lambda;增加。有关LM算法的更详细的解释在我们的框架中实现，我们参考[18]。
B.可选参数
上述程序是多元函数最小化的一般方法。他们认为参数x的空间是Euclidean，这在SLAM或捆绑调整等几个问题中是无效的。为了解决具有跨越非欧几里得空间的状态变量，一个常用的方法是表示增量在一个与参数中的一个不同的空间。
例如，在SLAM问题的背景下，每一个 参数块由一个平移向量和 旋转分量。平移向量显然形成 欧几里德空间。相反，旋转的分量 跨越非欧几里得2D或3D旋转 群SO（2）或SO（3）。为了避免奇点，这些空间 通常以超参数化的方式来描述，例如通过 旋转矩阵或四元数。直接将公式（15）应用于 这些过度参数化的表示违反了由过度参数化引起的限制。为了克服 这个问题，可以使用一个最小的表示法 旋转（如3D中的欧拉角）。然而，这是 受奇点影响.
另一种想法是构建一个新的误差函数，其中是当前变量周围的扰动。使用旋转的最小表示法，而使用超参数化的表示法。 由于通常很小，所以它们远离奇点。通过非线性算子⊞：Dom（xi）times;Dom（Delta;xi）→Dom（xi）应用增量可以得到优化后变量的新值，如下所示：
例如，在3D SLAM的情况下，可以通过平移向量和归一化四元数的轴表增量。 位姿点被表示为一个平移向量和一个完整的四元数。 在将增转换为与状态变量相同的表示形式之后，⊞运算符通过使用标准运动合成运算符oplus;（见[25]）将增量应用于：
使用此运算符，新误差函数可以被定义为：
其中跨越原始的超参数化空间。雅可比行列式变成了：
由于增量 是在初始猜测的局部欧几里得环境中计算的，因此需要通过⊞运算符将它们重新映射到原始冗余空间。
我们的框架允许为增量和状态变量简单定义不同的空间，从而支持在同一问题任意参数化形式。无论参数化的选择什么形式，Hessian H的结构一般都保留下来。
C. 线性化系统的结构
根据公式 （13）中，矩阵H和矢量b是通过对一组矩阵和矢量求和而获得的，每个约束一个。如果我们设定和我们可以把b和H重写为
每一个约束条件都会为系统添加一个加数 。这个加数的结构取决于误差函数的雅可比行列式。由于误差函数的约束条件只取决于两个节点的值，方程（5）中的雅可比行列式具有如下形式：
这里和是误差函数关于和的导数。从方程 （9）我们得到了矩阵块如下的结构形式：
为了简单表示，我们省略了零块。读者可能会注意到矩阵H的块结构是图中的邻接矩阵。 因此，它有一些与图中边数成比例的非零块。这通常导致H矩阵的稀疏。在g2o中，我们通过运用最先进的技术来利用H矩阵的这个特性方法来解决方程（14）的线性系统。
图3.我们的框架概述。为了解决新的优化问题，只需要指定灰色框。 此外，该框架允许添加不同的线性求解器。
D.具有特殊结构的系统
某些问题（例如BA）会导致具有更多特征结构的H矩阵。我们的系统可以利用这些特殊的结构来提升性能。在BA中一般有两种类型变量，即摄像机的姿势p和摄像机观察到的地标的姿势l。通过重新排列方程式（14）中的变量，这样摄像机姿态就有了我们获得系统的较低指数
可以看出，通过取H矩阵的Schur补充[7]形成了一个等价的简化系统。
注意计算很简便，因为是一个对角线矩阵。求解方程 （25）得到相机的增量，并使用这个我们可以求出：
这导致用于调整观察到的世界特征。通常情况下，这个世界的特征点超过了相机的位姿点，因此方程（25）可以比方程（14）更快的求解，尽管花了额外的时间来计算方程（25）左手边的矩阵。
IV。实施
我们的C 实现旨在保持整体的情况下尽可能快。我们通过在图形中将基类抽象成顶点和边来实现这一目标 两个基类都提供了一组虚拟函数，以方便用户进行子类化，而大多数内部操作都是使用模板参数实现的，以提高效率。 我们使用Eigen线性代数包[11]，它将SSE指令应用于其他优化技术中，如懒惰评估和循环展开以实现高性能。
图3描述了我们的系统的设计。只用定义灰色方框以解决一个新的
全文共9139字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11390]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
