基于BFGS修正的高斯牛顿光束法平差解算方法

赵帅华 李言言 曹健,† 曹喜信

基于BFGS修正的高斯牛顿光束法平差解算方法

赵帅华1李言言2曹健1,†曹喜信1

1. 北京大学软件与微电子学院, 北京 102600; 2. 德国慕尼黑工业大学, 慕尼黑 80333; † 通信作者, E-mail: caojian@ss.pku.edu.cn

针对高斯牛顿(Gauss-Newton, GN)方法求解光束法平差模型时对初值准确度要求高、应用场景受限的问题, 提出基于拟牛顿法 BFGS (Broyden-Fletcher-Goldfarb-Shanno)修正的高斯牛顿算法——BFGS-GN 法。当高斯牛顿法的信息矩阵失去正定性后, 使用 BFGS 算法对法方程进行补充修正, 可从根本上消除高斯牛顿方法对初值敏感的数学缺陷。在数据集上的实验结果表明, BFGS-GN 算法对不同类型的初值具有鲁棒性, 在初值较好的情况下, 所提方法与高斯牛顿法具有相同的精度和迭代效率; 在初值较差的情况下, 高斯牛顿方法因发散而失效, BFGS-GN 算法仍可以收敛到较高的精度。

光束法平差; 高斯牛顿; BFGS 算法; 初值鲁棒

光束法平差(bundle adjustment, BA)是三维重建和视觉 SLAM (simultaneous localization and mapp-ing)的核心技术, 主要应用于相机位姿和路标点的后端优化。获得相机内参矩阵、外参矩阵、影像特征点和空间 3D 物点坐标初值后, 可以使用 BA 模型对以上参数进行整体优化, 消除误差, 并获得精确的视觉信息[1]。

在视觉重建中, BA 模型的目标是获得更加精确的相机位姿和空间路标点。围绕这一目标, 针对光束法平差的研究分为以下几个方向。

1)使用其他质量更高的传感器获得更高质量的初值。Zhang 等[2]着眼于使用标靶来获得精度更高的初值, 以保证优化过程中的问题收敛, 但在提高初值精度时, 往往需要精度更高的采集设备和更多的人工预处理。

2)建立包含更多约束内容的光束法平差模型。Dabeer 等[3]在 BA 模型中融合路标点特征和车道线特征来优化自动驾驶车辆的姿态信息。Yang 等[4]提出点面 BA 模型来处理纹理缺乏场景中机器人的状态优化问题。Wu 等[5]利用计算机并行计算方式, 通过使用多核 CPU 和 GPU 进行算法加速。Zhao 等[6]用影像间的视差角等角度信息代替直角坐标, 降低雅克比矩阵(Jacobian matrix)的稀疏性。

3)借助深度学习方法求解 BA 问题。这种方法往往需要基于数据特征进行精巧的设计来增强训练过程的收敛性, 且参数估计部分仍然采用传统方法, 通用性不强。如 Tang 等[7]设计 BA-Net, 通过学习到的量度特征来衡量重投影误差、优化场景深度和相机运动。

4)直接研究 BA 模型的数值优化解。这是更加基础性的研究方向, 其目标是以各种质量的传感器采集的数据为基础, 提高求解方法的准确度和可拓展性。本文详细介绍此方向的研究。

光束法平差模型的本质是非线性最小二乘求解问题, 通过多次迭代, 使 3D 路标点的重投影误差最小。在数值优化问题的诸多解法中, 牛顿法因具备二阶收敛速度而得到广泛的应用, 但在迭代求解的过程中, 牛顿法因计算复杂度过高而无法应用在数据量较大的 BA 模型求解中。这种情况下, 高斯牛顿方法通过忽略牛顿方法中产生的高阶导数, 极大地降低计算复杂度, 因此普遍应用于工程问题中。但是, 在忽略高阶项的同时也为高斯牛顿带来问题: 当输入模型的初始值偏离真值较远时, 此方法极易发散, 无法满足收敛要求。

LM (Levenberg-Marquardt)方法[8]通过为高斯牛顿增加阻尼项来实现问题可解, 但由于阻尼的具体数值是通过不断尝试得到的, 因此很难获得精准的下降方向, 并导致迭代中的下降速度较慢。CG (Conjugate Gradient)方法[9]则是在高斯牛顿方法的数学模型基础上, 使用共轭梯度的方式求解方程, 但由于信息矩阵的条件数较大, 会影响矩阵的收敛速度。CGBA 方法[10]通过分解雅克比矩阵, 能够降低矩阵的条件数, 提高收敛速度, 但基于共轭梯度方式的解算方法通常无法收敛到更高精度的局部最小点。

BFGS (Broyden-Fletcher-Goldfarb-Shanno)方法[11]是一种常见的拟牛顿方法, 具有良好的正定保持特性, 因此是数值优化领域常用的优化方法。sBFGS-BA 是利用 BFGS 的正定保持特性提出的一种新解算方法[12], 但每步迭代都需计算海森矩阵(Hessian matrix)的高阶信息, 无法实现实时运行。本文通过分析高斯牛顿方法对初值敏感的原因发现, 在解算过程中, 是由于近似海森矩阵失去正定特点, 才导致下降方向无法求解。本文引入 BFGS 方法迭代求解目标方程的高阶导信息, 更加精准的表现求解目标中的海森矩阵, 在增加少量可控计算量的基础上, 可以极大地提高方法的鲁棒性。在较差初值的情况下, 本文方法也可以获得较好的下降方向, 从根本上解决基于高斯牛顿方法的光束法平差方法对初值敏感的问题。

1 基于高斯牛顿方法的光束法平差的缺陷分析

1.1 光束法平差模型

可以将 BA 问题描述为

其中,是所有未知参数的集合;是一个协方差矩阵, 使用同一个传感器进行观测时, 我们认为误差之间是相互独立的, 故通常将作为一个对角阵存在, 实际中通常取单位矩阵。通过对目标方程的解算, 可以获得最终优化的结果。

1.2 高斯牛顿方法对初值敏感的原因

牛顿法是求解无约束优化问题最早的算法之一, 主要思路是使用迭代点处的一阶导数和二阶导数对目标方程进行近似, 然后将二次模型的极小点作为新的迭代点, 不断重复, 达到满足的精度为止。对式(3)进行二阶泰勒展开:

可以看出, 在迭代求解过程中, 缺少高阶导数信息的高斯牛顿算法必须满足 Hessian 矩阵正定的条件, 并且要求式(7)中雅克比矩阵必须是列满秩矩阵, 否则算法失效。Jacobian 矩阵是相机参数与观测的三维特征点之间的一种表示方式, 随输入参数的变化而变化[13]。因此, 对 Jacobian 矩阵的要求就转化成对观测初值的要求, 当初值不好时, 优化问题通常无法求解, 这就是高斯牛顿方法容易发散的根本原因。

2 基于 BFGS 修正的高斯牛顿解算方法

针对高斯牛顿法存在的问题, 我们结合 BFGS算法进行修正, 继而提出更加鲁棒的 BA 模型解算方法。

2.1 BFGS算法的正定保持特点

BFGS 是一种常用的拟牛顿方法, 如式(8)所示:

由于是正定矩阵, 利用 Cuchy-Schwarz 公式进行分解可得

因此, 在式(12)等号成立时, 有

在式(12)等号不成立并严格小于时, 有

2.2 BFGS-GN算法

对于第一次迭代的修正方法是: 在开始求解矩阵时, 增加阻尼项0:

式(17)和(18)中,+1是新得到的海森矩阵, ||.||表示L2 范数距离。

修正后的通用形式的矩阵可以定义如下:

式(19)得到的+1是一个精确的矩阵, 可以更好地模拟Hessian矩阵,+1是一个稠密矩阵, 通过式(8)获得。基于BFGS修正的GN算法如下。

算法 BFGS-GN

已知: 相机位姿、路标点和特征点

我们将非零元素分为两类: 对角元素和非对角元素。若将它们都保留在增益矩阵+1中, 可以获得更好的实验结果。因此, 通过滤波器的Hadamard乘法, 可以得到+1的稀疏矩阵, 记为:

3 实验与讨论

3.1 实验数据

为了验证本文提出的 BFGS-GN 方法的有效性, 使用 4 个数据集进行实验, 将实验结果与传统的高斯牛顿解算方法进行比较①代码地址: https://github.com/shzhao/BFGS-GN。。为了确保公平性, 两个算法在同样的计算平台及软件环境下编写和运行: MATLAB-2016b 和华硕 3.4 GHz Windows 系统, 对参数进行同样的初始化操作。采用同样的标准进行限制: 最大迭代次数 100 次。

测试 4 个数据集由高质量摄像机拍摄的近景及航空摄影测量图像组成。表 1 列出数据集的整体参数, 包含数据类型、图像大小、影像张数、投影点数量和 3D 点的个数等信息。第 1 个数据集是使用Cannon 相机在 350m 的高度拍摄的 63 幅野外图像, 产生 4961 个 3D 点和 23150 个投影点。第 2 个数据集是将专业的光度测量摄像机 DMC 安装在 1000m米高的机载结构上, 拍摄的 90 幅航拍图像和 37705个投影。第 3 个数据集是近景数据集, 图像来自公共机器人数据集合, 其中的 51652 个投影使用开源软件 L2SIFT 提取。第 4 个数据集是从无人机(UAV)平台上采集的 468 幅分辨率为 5616×3744 的大学校园图像。

提取高质量的图像投影点后, 使用基于相对姿态估计的算法, 计算两个相邻摄像机之间的相对姿态。在获得两个相邻摄像机的所有相对姿态后, 通过将相对姿态转换为第一摄像头坐标的方式, 将本地坐标参考系中的相机姿态初始化。然后, 通过交点算法实现 3D 点的初始化。将每个数据集整理为 4 个 txt 文件, 分别是相机的内参文件、每张影像的位姿信息、每张影像的特征点文件和特征点对应的空间路标点文件。最后, 将摄像机姿态和路标点位置输入基于高斯牛顿法的光束法平差方法和基于 BFGS 修正的高斯牛顿方法中。统一使用优化参数计算得到的预测点和真实点间的均方误差(MSE)来衡量算法的准确性。

3.2 实验结果与讨论

实验结果分为两种情况。如图 2 所示, 对于数据集 DunHuan 和 Village, 高斯牛顿方法(GN)和本文提出的基于 BFGS 修正的高斯牛顿方法(BFGS-GN)具有相同的收敛精度和收敛速度。本文方法在中间迭代点处下降更快速(图 2(a)), 图 2(b)中两种方法取得相同的收敛效果。说明在数据集初值较好的情况下, 两种方法均能很好地模拟真实 Hessian 矩阵, 达到较好的收敛效果。

如图 3 所示, 对于数据集 Magala 和 College, 使用高斯牛顿方法优化相机姿态和 3D 点坐标时, 迭代过程经过振荡后, 最终的结果出现发散。BFGS-GN 方法仍然可以将数据优化到较高的精度。从图3 可以看出, 高斯牛顿方法出现发散的原因在于, 数据集的初始值距离真实值较远, 所以高斯牛顿方法中的近似 Hessian 矩阵不能很好地表示真实的Hessian 矩阵, 并且在优化的过程中失去正定性。BFGS-GN 方法通过对高斯牛顿的目标方程进行修正, 可以更加准确地逼近真实 Hessian 矩阵, 并且始终有能力使矩阵在迭代过程中保持正定特性。对于Malaga 数据集, BFGS-GN 方法可以收敛到 0.512; 对于 College 数据集, 仅需 7 步就能使 MSE 收敛到0.352。

表1 测试数据集的整体参数

图2 Dunhuan 和 Village 数据集收敛情况

测试数据集的初始误差、迭代次数和最终收敛精度如表 2 所示, 其中的第 3 和第 4 列分别表示使用初始未知参数计算的均方误差和使用最优参数计算的收敛后的均方误差, 以像素作为统一的单位。此外, 我们还记录了迭代次数。

从整体上看, 与基于高斯牛顿的光束法平差方法相比, 对于初值较好的数据, BFGS-GN 方法具有不弱于高斯牛顿的迭代效率和收敛精度。对于拥有较差初值的数据, BFGS-GN 方法可以顺利地收敛, 解决了基于高斯牛顿的光束法平差方法因对初值敏感而应用场景受限的问题。

表2 高斯牛顿和BFGS-GN优化的收敛结果

4 结语

高斯牛顿法是光束法平差中的重要方法, 因收敛精度高和超线性收敛速度而得到广泛应用。但是, 高斯牛顿法由于理论上的缺陷, 使得其对相机姿态和空间路标点的初始值具有较高要求, 当初始值远离真值时, 算法极容易发散, 丧失优化功能。本文通过对高斯牛顿方法初值敏感原因进行探索, 提出基于 BFGS 算法修正的高斯牛顿方法(BFGS-GN 方法)。在每次迭代前, BFGS-GN 方法会对高斯牛顿信息矩阵的正定性进行判断, 在不满足正定规则时, 对高斯牛顿的目标方程进行修正。

实验结果表明, 对于高斯牛顿法不能实现收敛的数据集, BFGS-GN 算法可以正常地收敛, 并获得较高收敛精度; 对于高斯牛顿法可以收敛的数据集, BFGS-GN 算法同样可以获得相同的精度和迭代效率。因此, 本文提出的方法可以很好地解决高斯牛顿方法对于初值敏感的问题, 在保证收敛精度的前提下, 可以增加算法的鲁棒性, 有效地拓展应用场景。

[1] Yan Lei, Chen Rui, Sun Huabo, et al. A novel bundle adjustment method with additional ground control point constraint. Remote Sensing Letters, 2017, 8(1): 68–77

[2] Zhang Chunsen, Zhu Shihuan, Zang Yufu, et al. GPS-supported bundle adjustment method of UAV by con-sidering exposure delay. Acta Geodaetica et Cartogra-phica Sinica, 2017, 46(5): 565–572

[3] Dabeer O, Gowaikar R, Grzechnik S K, et al. An end-to-end system for crowdsourced 3D maps for autono-mous vehicles: the mapping component // IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Vancouver, 2017: 634–641

[4] Yang S C, Song Y, Kaess M, et al. Pop-up SLAM: semantic monocular plane SLAM for low-texture environments // IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Daejeon, 2016: 1222–1229

[5] Wu Changchang, Agarwal S, Curless B, et al. Mul-ticore bundle adjustment // The 24th IEEE Confe-rence on Computer Vision and Pattern Recognition (CVPR). Providence, RI, 2011: 3057–3064

[6] Zhao Liang, Huang Shoudong, Sun Yanbiao, et al. ParallaxBA: bundle adjustment using parallax angle feature parametrization. The International Journal of Robotics Research, 2015, 34(4/5): 493–516

[7] Tang Chengzhou, Tan Ping. BA-Net: dense bundle adjustment networks [EB/OL]. (2019–08–25) [2019–12–01]. https://arxiv.org/abs/1806.04807

[8] Madsen K, Tingle O, Nielsen H B, et al. Methods for non-linear least squares problems. 2nd ed. Lyngb: Technical University of Denmark, 2004

[9] Hager W W, Zhang H. A survey of nonlinear con-jugate gradient methods. Pacific Journal of Optimi-zation, 2006, 2(1): 35–58

[10] Byröd M, Astrom K. Conjugate gradient bundle ad-justment // European Conference on Computer Vision. Heraklion, 2010: 114–127

[11] Zhou Weijun, Chen Xiaojun. Global convergence of a new hybrid Gauss-Newton structured BFGS method for nonlinear least squares problems. Siam Journal on Optimization, 2010, 20(5): 2422–2441

[12] Li Yanyan, Fan Shiyue, Sun Yanbiao, et al. Bundle adjustment method using sparse BFGS solution. Remote Sensing Letters, 2018, 9(8): 789–798

[13] 高翔, 张涛. 视觉 SLAM 十四讲: 从理论到实践. 北京: 电子工业出版社, 2017: 248–253

A BFGS-Corrected Gauss-Newton Solver for Bundle Adjustment

ZHAO Shuaihua1, LI Yanyan2, CAO Jian1,†, CAO Xixin1

1. School of Software and Microelectronics, Peking University, Beijing 102600; 2. Technische Universität München, Munich 80333; † Corresponding author, E-mail: caojian@ss.pku.edu.cn

Aiming at the problem that the Gauss-Newton (GN) method is sensitive to the initial information matrixin the Bundle Adjustment (BA) model, which leads to limited application scenarios, the paper proposes a novel method BFGS-GN using BFGS (Broyden-Fletcher-Goldfarb-Shanno) algorithm to improve the traditional Gauss-Newton method. When the information matrix of the Gauss-Newton method loses positive definiteness, BFGS algorithm can be used to modify the normal equations, which fundamentally eliminates the mathematical defect that the Gauss-Newton method is sensitive to initial values. Experimental results demonstrate that proposed method is robust to different types of initials. The same accuracy and the number of iterations as GN can be obtained when the initial values are good. As for bad inputs, GN-based BA method cannot work but BFGS-GN can converge to a minimum.

bundle adjustment; Gauss-Newton;BFGS algorithm;initial value robustness

10.13209/j.0479-8023.2020.098

国家重点研发计划(2018YFE0203801)资助

2019-12–10;

2020–02–04