访问阿里云主机网站,固原住房和城乡建设厅网站,睢县房产网站建设,杨思网站建设公司摘要
增量式地运动结构恢复是从无序图像集合中进行三维重建的一个普遍策略。虽然增量式地重建系统在各个方面上都取得了巨大的进步#xff0c;但鲁棒性、准确性、完整度和尺度仍然是构建真正通用管道的关键问题。我们提出了一种新的运动结构恢复技术#xff0c;它改进了目前…摘要
增量式地运动结构恢复是从无序图像集合中进行三维重建的一个普遍策略。虽然增量式地重建系统在各个方面上都取得了巨大的进步但鲁棒性、准确性、完整度和尺度仍然是构建真正通用管道的关键问题。我们提出了一种新的运动结构恢复技术它改进了目前的技术水平朝着这个最终目标又迈进了一步。完整的重建管道作为开源实现向公众发布。
1 介绍
近年来无序图像的运动结构恢复(SfM)已经发生了巨大的变化。早期的自标定度量重建系统为新型重建系统奠定了基础这些新型系统通过城区的互联网图片来进行三维重建。受这些作品的启发越来越大规模的重建系统被开发出来从数十万张、数百万张到最近的1亿张互联网图像。已经提出了多种SfM策略包括增量式、分层式和全局式方法。可以说增量式SfM是重建无序图片集最流行的策略。尽管增量式策略被广泛使用但我们仍然没有设计出一个真正通用的SfM系统。虽然现有的系统已经极大地提高了技术水平但是鲁棒性、准确性、完整度和尺度仍然是增量SfM中的关键问题这阻碍了它成为通用方法。在本文中我们提出了一种新的SfM算法来实现这一最终目标。新方法在各种具有挑战性的数据集上进行了评估代码作为名为COLMAP的开源实现贡献给研究社区可在https://github.com/colmap/colmap上获得。 图1 在75千张图片中配准了21千张重建罗马的结果 2 运动结构恢复综述
SfM是指从一系列不同视觉拍摄的图像中恢复出三维结构。增量式SfM(本文中表示为SfM)是一个具有迭代重建组件的顺序处理管道(图2)。它通常从特征提取和匹配开始然后进行几何验证。生成的场景图是重建阶段的基础该阶段使用精心挑选的双视图重建为模型提供种子然后逐步注册新图像、三角测量场景点、过滤异常值并使用光束调整(BA)细化重建。接下来的章节将详细说明这一过程定义整篇论文中使用的符号并介绍相关工作。
2.1 对应关系搜索
第一阶段是对应关系搜索它在输入图像 I { I i ∣ i 1 ⋯ N I } \mathcal{I}\{I_i|i1\cdots N_I\} I{Ii∣i1⋯NI}中查找场景重叠并识别重叠图像中相同点的投影。输出是一组经过几何验证的图像对 C ˉ \bar{C} Cˉ和每个点的图像投影图。
特征提取。 对于每幅图像 I i I_i IiSfM检测位置 x j ∈ R 2 x_j \in \mathbb{R}^2 xj∈R2处的局部特征集 F i { ( x j , f j ) ∣ j 1 ⋯ N F i } \mathcal{F}_i\{(x_j,f_j) | j 1\cdots N_{F_i}\} Fi{(xj,fj)∣j1⋯NFi}由外观描述符 f j f_j fj表示。这些特征应该在辐射测量和几何变化下保持不变以便SfM可以在多幅图像中唯一地识别它们。SIFT及其变体以及最近基于学习的特征是鲁棒性方面的黄金标准。另外二进制特征提供了更好的效率但鲁棒性降低了。 图2 增量式运动结构恢复管道 特征匹配。 接下来SfM利用特征 F i \mathcal{F}_i Fi作为图像的外观描述来发现看到相同场景部分的图像。这种简单的方法可以测试每一对图像是否存在场景重叠。通过比较特征的外观 f i f_i fi可以找到图像 I a I_a Ia中与图像 I b I_b Ib中每个特征最相似的特征最终得到特征对应关系。这种方法的计算复杂度为 N I 2 N F i 2 N_I^2N_{F_i}^2 NI2NFi2这对于大图像集而言是不可行的。有多种方法可以解决尺度和高效匹配问题。输出是一组可能重叠的图像对 C { { I a , I b } ∣ I a , I b ∈ I , a b } \mathcal{C}\{ \{ I_a,I_b \} | I_a,I_b \in \mathcal{I}, a b \} C{{Ia,Ib}∣Ia,Ib∈I,ab}及其相关的特征对应关系 M a b ∈ F a × F b \mathcal{M}_{ab}\in \mathcal{F}_a \times \mathcal{F}_b Mab∈Fa×Fb。
几何验证。 第三阶段验证可能重叠的图像对 C \mathcal{C} C。由于匹配仅基于外观因此不能保证相应的特征实际上对应到相同的场景点。因此SfM通过特征点的变换来验证匹配而这个变换使用射影几何估计。根据图像对的空间配置不同的映射描述它们的几何关系。单应矩阵 H H H描述了纯旋转或纯平移相机拍摄平面场景时的变换。对极几何通过本质矩阵 E E E已标定或基础矩阵 F F F未标定描述运动相机的关系并且可以使用三焦点张量扩展到三个视图。如果有效的变换在图像之间映射了足够数量的特征则认为它们通过了几何验证。由于匹配得到的对应关系经常受到异常值污染因此需要使用诸如RANSAC之类的稳健估计技术。该阶段的输出是一组经过几何验证的图像对 C ˉ \bar{\mathcal{C}} Cˉ、它们相关的内点对应关系 M ˉ a b \bar{\mathcal{M}}_{ab} Mˉab以及可选的它们之间的几何关系描述 G a b G_{ab} Gab。为了确定适当的关系可以使用GRIC之类的决策标准或QDEGSAC之类的方法。此阶段的输出是所谓的场景图其中图像为节点经过验证的图像对为边。
2.2 增量式重建
重建阶段的输入是场景图。输出是已配准图像的估计位姿 P { P c ∈ S E ( 3 ) ∣ c 1 ⋯ N P } \mathcal{P}\{ P_c \in SE(3) | c 1\cdots N_P \} P{Pc∈SE(3)∣c1⋯NP}和重建的场景结构以点集的形式 X { X k ∈ R 3 ∣ k 1 ⋯ N X } \mathcal{X}\{ X_k \in \mathbb{R}^3 | k 1\cdots N_X \} X{Xk∈R3∣k1⋯NX}表示。
初始化。 SfM使用精心选择的双视图重建来初始化模型。选择合适的初始图像对是至关重要的因为无法从错误的初始图像对中恢复出三维结构。此外重建的鲁棒性、准确性和性能取决于增量过程的种子位置。使用许多重叠的相机从场景图中的密集位置进行初始化通常会由于冗余度增加而产生更加鲁棒和准确的重建。相比之下从较稀疏的位置进行初始化会缩短运行时间因为BA处理的问题会变得较稀疏。
图像配准。 从度量重建开始可以通过求解PnP问题将新图像注册到当前模型中。PnP问题涉及估计未标定相机的位姿 P c P_c Pc及其内参。因此集合 P \mathcal{P} P由新注册图像的位姿 P c P_c Pc扩展。由于2D-3D对应关系通常受到异常值污染因此一般使用RANSAC和最小位姿求解器来估计已标定相机的位姿。对于未标定的相机存在各种最小化求解器或基于采样的方法。我们在第4.2节中提出了一种新颖的鲁棒的次优图像选择方法用于准确的位姿估计和可靠的三角测量。
三角化。 新注册的图像必须观测现有的场景点。此外还可以通过三角测量扩展点集 X \mathcal{X} X来增加场景覆盖率。只要至少再注册一张同样覆盖新场景部分但不同视点的图像就可以对新的场景点 X k X_k Xk进行三角测量并将其添加到 X \mathcal{X} X中。三角测量是SfM中的一个关键步骤因为它通过冗余增加了现有模型的稳定性并且通过提供额外的2D-3D对应关系实现了新图像的配准。存在大量多视图三角测量的方法。这些方法在SfM中使用时存在鲁棒性有限或计算成本高的问题我们通过在第 4.3节中提出一种鲁棒且有效的三角测量方法来解决。
光束调整。 图像配准和三角测量是独立的过程即使它们的产物高度相关——相机位姿的不确定性会传递到三角测量点反之亦然而额外的三角测量点可以通过增加冗余度来改善初始相机位姿。如果不进一步改进SfM通常会很快偏离到不可恢复的状态。BA是相机参数 P c P_c Pc和点参数 X k X_k Xk的联合非线性优化可最小化重投影误差 E ∑ j ρ j ( ∣ ∣ π ( P c , X k ) − x j ∣ ∣ 2 2 ) (1) E \sum_j \rho_j (||\pi (P_c,X_k) - x_j||_2^2) \tag{1} Ej∑ρj(∣∣π(Pc,Xk)−xj∣∣22)(1) 使用函数 π \pi π将场景点投影至图像空间使用损失函数 ρ j \rho_j ρj来降低异常值的权重。LM方法可以用来求解BA问题。BA 问题中参数的特殊结构启发了Schur补技巧其中首先求解简化的相机系统然后通过回代来更新点。这种方案通常更有效因为相机的数量通常小于点的数量。解决该系统有两种选择精确和非精确步骤算法。精确方法通过存储和分解系统为稠密或稀疏矩阵来解决系统空间复杂度为 O ( N P 2 ) O(N_P^2) O(NP2)时间复杂度为 O ( N P 3 ) O(N_P^3) O(NP3)。非精确方法近似地求解系统通常使用迭代求解器例如预条件共轭梯度(PCG)其时间和空间复杂度均为 O ( N P ) O(N_P) O(NP)。直接算法是多达几百台相机的首选方法但在大规模设置中成本太高。虽然稀疏直接方法大大降低了稀疏问题的复杂性但由于连接图通常更加密集因此对于大型非结构化照片集而言它们是禁止的。在这种情况下间接算法是首选方法。特别是对于网络照片BA花费大量时间来优化许多近似重复的图像。在第4.5节中我们提出了一种识别和参数化高度重叠图像的方法以实现密集照片集的有效BA。
3 挑战
虽然目前最先进的SfM算法可以处理大规模互联网照片集中图像的多样化和复杂分布但它们在完整度和鲁棒性方面往往无法产生完全令人满意的结果。很多时候系统无法配准大量根据经验应该可配准的图像或者由于配准错误或漂移导致系统产生破裂的模型。首先这可能是由于对应关系搜索产生不完整的场景图例如由于匹配近似造成的因此既没有提供完整模型所需的连接性也没有提供可靠估计所需的足够冗余度。其次这可能是由于重建阶段由于场景结构缺失或不准确而无法配准图像造成的——图像配准和三角测量具有共生关系因为图像只能配准到现有的场景结构中而场景结构只能从配准的图像中进行三角测量。在增量式重建的每个步骤中最大化准确性和完整度是SfM中的一个关键挑战。在本文中我们解决了这一挑战并在完整度、鲁棒性和准确性方面显著提高了当前最先进的结果第5节同时提高了效率。
4 贡献
本节介绍了一种改进SfM中主要挑战的新算法。首先我们引入一种几何验证策略该策略通过信息扩充场景图从而提高初始化和三角测量组件的鲁棒性。其次下一个最佳视图选择可最大限度地提高增量重建过程的鲁棒性和准确性。第三一种鲁棒的三角测量方法可以以更低的计算成本产生比现有技术更完整的场景结构。第四迭代BA、重新三角测量和异常值过滤策略可通过减轻漂移效应显著提高完整度和准确性。最后通过冗余视图挖掘对稠密照片集进行更有效的BA参数化。这使得系统在保持效率的同时在鲁棒性和完整度方面明显优于当前最先进的技术。我们将我们的贡献与当前最先进的系统Bundler(开源)和VisualSFM进行了对比。所提出的系统作为开源实现发布。
4.1 场景图增强
我们提出了一种多模型几何验证策略以适当的几何关系增强场景图。首先我们估计了基础矩阵。如果至少发现 N F N_F NF个内点我们就认为该图像对已通过几何验证。接下来我们通过确定同一图像对的单应性内点的数量 N H N_H NH来对变换进行分类。为了近似GRIC等模型选择方法如果 N H / N F ϵ H F N_H/N_F \epsilon_{HF} NH/NFϵHF我们假设相机在一般场景中运动。对于标定后的图像我们还估计了一个本质矩阵及其内点 N E N_E NE的数量。如果 N E / N F ϵ E F N_E/N_F \epsilon_{EF} NE/NFϵEF我们认为标定正确。在标定正确和 N H / N F ϵ H F N_H/N_F\epsilon_{HF} NH/NFϵHF的情况下我们对本质矩阵进行分解从内点对应关系中对点进行三角化并确定三角化角度中值 α m \alpha_{m} αm。利用 α m \alpha_m αm我们区分了纯旋转场景全景和平面场景平面。此外互联网照片中一个常见的问题是水印、时间戳和帧WTFs错误地链接了不同地标的图像。我们通过在图像边界估计带有 N S N_S NS内点的相似变换来检测这样的图像对。如果图像对满足 N S / N F ϵ S F N_S/N_F\epsilon_{SF} NS/NFϵSF或 N S / N E ϵ S E N_S/N_E\epsilon_{SE} NS/NEϵSE则认为它是WTF并不把它插入到场景图中。对于有效的图像对我们用模型类别一般、全景、平面来标记场景图同时记录支持该类别的最大内点数 N H N_H NH或 N E N_E NE或 N F N_F NF。模型类别仅用于重建初始图像对的选择我们优先使用非全景和已标定的图像对。已经增强的场景图能够有效地为鲁棒重建过程找到最佳初始化。此外我们没有对全景图像对进行三角化以避免退化点从而提高三角化和后续图像配准的鲁棒性。 图3 对于L3图像中具有不同分布上和下和不同点数左和右的分数。 4.2 下一个最佳视图选择
次优视图规划已经在计算机视觉、摄影测量和机器人领域得到了研究。在鲁棒SfM中选择次优视图的目的是最小化重建误差。在这里我们提出了一种有效的次优视图策略该策略遵循不确定性驱动的方法最大限度地提高了重建鲁棒性。
选择下一个最佳视图是至关重要的因为每个决定都会影响剩余的重建。一个错误的决定可能会导致一连串的相机错误配准和错误的三角化。此外选择次优视图会极大地影响位姿估计的质量以及三角测量的完整度和准确性。准确的位姿估计对于鲁棒的SfM至关重要因为如果位姿不准确点的三角测量可能会失败。关于选择下一个最佳视图的决定是具有挑战性的因为对于互联网照片集来说通常没有关于场景覆盖和相机参数的先验信息因此决定完全基于来自外观的信息、双视图对应、以及增量重建场景。
一种流行的策略是选择看到最多三角点的图像目的是最大限度地减少相机resection的不确定性。Haner等人提出了一种不确定性驱动的方法使重建误差最小化。通常除了观测配置条件不佳的情况外选择看到最多三角点的相机。为此Lepetit等人通过实验表明使用PnP求解出来的相机位姿精度取决于观测值的数量及其在图像中的分布。对于网络照片将标准PnP问题扩展到缺少或不准确的先验标定情况下的内参估计。大量的2D-3D对应为这种估计提供了冗余而点的均匀分布避免了不良配置并使内参的估计可靠。
下一个最佳视图的候选对象不是那些至少看到 N t 0 N_t 0 Nt0个三角点的尚未配准的图像。使用特征轨迹图可以有效地实现对该统计数据的跟踪。对于互联网数据集这个图可能非常密集因为许多图像可能看到相同的结构。因此在重建的每个步骤中都有许多候选视图可供选择。Haner等人提出的穷举协方差传播是不可行的因为每一步都需要计算和分析每个候选的协方差。我们提出的方法使用高效的多分辨率分析近似于它们的不确定性驱动方法。
我们必须同时跟踪每个候选图像中可见点的数量及其分布。可见点越多这些点的分布越均匀分数 S S S就越高这样具有更好条件的可见点配置的图像就会被优先配准。为了实现这一目标我们将图像离散到一个固定大小的网格中在两个维度上都有 K l K_l Kl个bins。每个单元格有两种不同的状态空和满。在重建过程中只要空单元格中的一个点变得可见单元格的状态就会变为满的并且图像的分数 S i S_i Si增加一个权重 w l w_l wl。通过这个方案我们量化了可见点的数量。由于单元格对整体得分只有一次贡献我们更倾向于均匀的分布而不是当点聚集在图像的一部分时即只有少数单元格包含所有可见点。但是如果可见点的数量为 N t ≪ K l 2 N_t \ll K^2_l Nt≪Kl2则该方案可能无法很好地捕获点的分布因为每个点都可能落在一个单独的单元格中。因此通过在每个连续的级别上使用更高的分辨率 K l 2 l K_l 2^l Kl2l来划分图像我们将前面描述的方法扩展到 l 1 … L l 1\dots L l1…L的多分辨率金字塔。分数是通过分辨率相关的权重 w l K l 2 w_lK_l^2 wlKl2在所有级别上累积的。该数据结构及其分数可以在线高效更新。图3显示了不同配置的分数第5节展示了使用该策略改进的重建鲁棒性和准确性。
4.3 鲁棒和高效三角化
特别是对于稀疏匹配的图像集合利用传递对应可以提高三角测量的完整度和准确性从而改善后续图像配准。近似匹配技术通常倾向于外观相似的图像对因此两视图对应通常源于具有小基线的图像对。利用传递性在具有较大基线的图像之间建立对应关系从而实现更准确的三角测量。因此我们通过连接两视图对应来形成特征轨迹。
针对噪声图像观测的三角测量研究人员已经提出了多种方法。虽然提出的一些方法对一定程度的离群值污染具有鲁棒性但据我们所知没有一种方法可以处理特征轨道中经常出现的高离群值比率图6。我们参考Kang等人对现有多视图三角测量方法的详细概述。在本节中我们提出了一种有效的、基于采样的三角化方法该方法可以鲁棒地估计异常值污染特征轨道内的所有点。
由于错误的沿极线模糊匹配的双视图验证特征轨道通常包含大量的异常值。单个不匹配会合并两个或多个独立点的轨迹。例如错误地合并四个长度相等的特征轨迹会导致75%的异常值比率。此外由于高重投影误差不准确的相机位姿可能使轨迹元素无效。因此对于鲁棒的三角测量有必要在使用多个视图执行优化之前找到一致的轨迹元素集。此外为了从错误合并中恢复特征轨迹的潜在多个点需要一个递归三角化方案。
Bundler对轨迹元素的所有成对组合进行采样执行双视图三角化然后检查是否至少有一个解具有足够的三角化角度。如果找到条件良好的解则对整个轨迹进行多视图三角化如果所有观测值都通过了cheirality约束则接受此多视图三角化。该方法对异常点不具有鲁棒性因为不可能恢复合并到一个轨道中的独立点。同时由于穷举的两两三角化计算量大。我们的方法克服了这两个限制。
为了处理任意水平的异常污染我们使用RANSAC制定了多视图三角测量问题。我们考虑特征轨迹 T { T n ∣ n 1 … N T } \mathcal{T} \{ T_n | n 1…N_T\} T{Tn∣n1…NT}作为一组具有先验未知内点比例 ϵ \epsilon ϵ的测量值。测量 T n T_n Tn由归一化图像观测值 x ˉ n ∈ R 2 \bar{x}_n \in \mathbb{R}^2 xˉn∈R2和相应的相机位姿 P n ∈ S E ( 3 ) P_n \in SE(3) Pn∈SE(3)组成它表示从世界到相机帧的投影 P [ R T , − R T t ] P[R^T,-R^Tt] P[RT,−RTt]其中 R ∈ S O ( 3 ) R\in SO(3) R∈SO(3) t ∈ R 3 t\in \mathbb{R}^3 t∈R3。我们的目标是最大限度地支持符合条件良好的双视图三角测量 X a b ∼ τ ( x ˉ a , x ˉ b , P a , P b ) w i t h a ≠ b (2) X_{ab} \sim \tau(\bar{x}_a,\bar{x}_b,P_a,P_b) \ with \ a \neq b \tag{2} Xab∼τ(xˉa,xˉb,Pa,Pb) with ab(2) 其中 τ \tau τ表示选择的三角化方法本文中使用的是DLT方法 X a b X_{ab} Xab是三角化点。请注意我们没有从全景图像对进行三角测量第4.1节以避免由于不准确的位姿估计而导致错误的三角测量角度。一个条件良好的模型满足两个约束。首先有足够的三角测量角 α \alpha α c o s α t a − X a b ∣ ∣ t a − X a b ∣ ∣ 2 ⋅ t b − X a b ∣ ∣ t b − X a b ∣ ∣ 2 (3) cos\alpha \frac{t_a-X_{ab}}{||t_a-X_{ab}||_2}\cdot \frac{t_b-X_{ab}}{||t_b-X_{ab}||_2} \tag{3} cosα∣∣ta−Xab∣∣2ta−Xab⋅∣∣tb−Xab∣∣2tb−Xab(3) 其次关于视图 P a P_a Pa和视图 P b P_b Pb的正深度 d a d_a da和 d b d_b db也即cheirality约束深度定义为 d [ p 31 p 32 p 33 p 34 ] [ X a b T 1 ] T (4) d[p_{31} \ p_{32} \ p_{33} \ p_{34}] [X_{ab}^T\ 1]^T \tag{4} d[p31 p32 p33 p34][XabT 1]T(4) 其中 p m n p_{mn} pmn定义为矩阵 P P P的第 m m m行第 n n n列元素。如果测量值 T n T_n Tn的深度 d n d_n dn为正且其重投影误差 e n ∥ x ˉ n − [ x ′ / z ′ y ′ / z ′ ] ∥ 2 w i t h [ x ′ y ′ z ′ ] P n [ X a b 1 ] (5) e_n\begin{Vmatrix} \bar{x}_n - \begin{bmatrix} x/z \\ y/z \end{bmatrix} \end{Vmatrix} _2 \ with \ \begin{bmatrix} x \\ y \\ z \end{bmatrix} P_n \begin{bmatrix} X_{ab} \\ 1 \end{bmatrix} \tag{5} en xˉn−[x′/z′y′/z′] 2 with x′y′z′ Pn[Xab1](5) 小于固定阈值 t t t时则认为该测量值 T n T_n Tn符合模型。RANSAC作为一种迭代方法最大化 K \mathcal{K} K通常它均匀地随机采样大小为2的最小集合。然而由于对于小 N T N_T NT可能对相同的最小集进行多次采样因此我们定义随机采样器仅生成唯一的样本。为了确保至少有一个无离群值的最小集被采样RANSAC必须运行至少 K K K次迭代。由于内点的先验初始比率 a a a是未知的我们将其设置为一个小的初始值 ϵ 0 \epsilon_0 ϵ0并在找到更大的共识集自适应停止准则时调整 K K K。因为一个特征轨迹可能包含多个独立的点我们通过从剩余的测量中删除共识集来递归地运行这个过程。如果最新共识集的大小小于3则递归停止。第5节中的评估表明所提出的方法在降低计算成本的同时提高了三角测量的完整度。
4.4 光束调整
为了减少累积误差我们在图像配准和三角测量后执行BA。通常不需要在每个步骤之后执行全局BA因为增量SfM只在局部影响模型。因此我们在每个图像配准后对连接最多的图像集执行局部BA。与VisualSFM类似我们只在模型增长到一定百分比后才执行全局BA从而使SfM的线性运行时间平摊。
参数化。 为了考虑潜在的异常值我们采用柯西函数作为局部BA中的鲁棒损失函数 ρ j \rho_j ρj。对于多达几百个相机的问题我们使用稀疏直接求解器对于更大的问题我们依靠PCG。我们使用Ceres Solver并提供在任意图像组合中共享任意复杂的相机模型的选项。对于无序的互联网照片我们依赖于一个简单的相机模型只有一个径向畸变参数因为估计依赖于纯粹的自标定。
过滤。 BA后一些观测值与模型不符。因此我们对重投影误差较大的观测值进行过滤。此外对于每个点我们通过在所有观察射线对上执行最小化三角测量的角度来检查条件良好的几何形状。在全局BA之后我们还检查退化相机例如由全景或人工增强图像引起的相机。通常情况下这些相机只能观察到异常值或者它们的内参收敛到一个虚假的最小值。因此我们没有将焦距和畸变参数限制在一个先验的固定范围内而是让它们在BA中自由优化。由于主点标定是一个不适定问题对于未标定的相机我们将其固定在图像中心。在全局BA后视场异常或畸变系数量级较大的相机被认为估计和滤波不正确。
重新三角化。 与VisualSfM类似我们执行重新三角测量RT来解释全局BApre-BA RT之前的漂移效应。然而BA通常会显著改善相机和点参数。因此我们建议用一个额外的后BA-RT步骤来扩展非常有效的前BA-RT。这一步的目的是通过延续之前无法三角化的点的轨迹例如由于不准确的位姿等来提高重建的完整度比较第4.3节。而不是增加三角测量阈值我们只继续跟踪那些误差低于滤波阈值的观测值。此外我们尝试合并轨迹从而为下一个BA步骤提供更多的冗余。
迭代优化。 Bundler和VisualSfM执行BA和过滤的单个实例。由于漂移或前BA-RT通常BA中很大一部分观测值是异常值随后被过滤。由于BA受离群值的影响比较严重第二遍BA可以显著改善结果。因此我们建议在迭代优化中执行BA、RT和过滤直到过滤的观测值和后BA-RT点的数量减少。在大多数情况下经过第二次迭代后结果显著改善优化收敛。第5节揭示了所提出的迭代优化显著提高了重建完整度。
4.5 冗余视图挖掘
BA是SfM中的主要性能瓶颈。在本节中我们提出了一种方法利用增量SfM和稠密照片集合的固有特征通过将冗余相机聚类到高场景重叠组中从而更有效地参数化BA。
由于兴趣点的受欢迎程度不同互联网图片集通常具有高度不均匀的可见性模式。此外无序的集合通常聚集成在许多图像中共视的点片段。许多先前的工作利用这一事实来提高BA的效率包括Kushal等人他们分析了可见模式用来高效地预处理简化的相机系统。Ni等人将相机和点划分为子图并通过分隔变量连接将划分视为连接相机和点参数图上的图割问题。然后BA在固定相机和点和优化分隔变量之间交替进行反之亦然。Carlone等人的另一种方法将多个低秩点分解为单个因子对相机施加高秩约束从而在相机共享多个点时提供计算优势。
我们提出的方法是受到这些前人工作的启发。与Ni等人类似我们将问题划分为子图这些子图的内部参数被分解。我们有三个主要的贡献。其一一种利用SfM固有特性的高效相机分组方案取代了Ni等人使用的昂贵的图切方法。其二我们将场景划分为许多小的、高度重叠的相机组而不是将许多相机聚类到一个子图中。每组中的相机被压缩成一个单独的相机从而降低了求解简化相机系统的成本。其三由于相机组更小高度重叠我们通过跳过分隔变量优化来消除Ni等人的交替方案。
SfM根据图像和点的参数是否受到最新增量模型扩展的影响将其分为两组。对于大型问题大部分场景不受影响因为模型通常在局部扩展。BA自然会对新扩展的部分进行优化而其他部分只有在漂移的情况下才会改进。此外网络照片通常有一个不均匀的相机分布和许多冗余的视点。基于这些观察结果我们将未受影响的场景部分划分为具有高度重叠图像的组 G { G r ∣ r 1... N G } \mathcal{G}\{ G_r | r 1...N_G \} G{Gr∣r1...NG}并将每个组 G r G_r Gr参数化为单个相机。受最新扩展影响的图像被独立分组以允许对其参数进行最佳优化。注意这会导致标准BA参数化Eq. 1。对于未受影响的图像我们创建基数为 N G r N_{G_r} NGr的组。如果在最新的模型扩展期间添加了图像或者如果其观测值的比例大于 ϵ r \epsilon_r ϵr则我们认为图像受影响以改进重新三角化相机。
一组内的图像应尽可能冗余图像之间共视点的数量是描述它们相互作用程度的一种度量。对于一个有 N X 个 N_X个 NX个点的场景每张图像可以用一个二值可见向量 v i ∈ { 0 , 1 } N X v_i \in \{0,1\}^{N_X} vi∈{0,1}NX来描述其中如果点 X n X_n Xn在图像 i i i中可见则 v i v_i vi中的第 n n n个条目为1否则为0。图像 a a a和 b b b之间的交互程度是通过对它们的向量 v i v_i vi进行位运算来计算的 V a b ∣ ∣ v a ∩ v b ∣ ∣ / ∣ ∣ v a ∪ v b ∣ ∣ (6) V_{ab}||v_a \cap v_b|| / || v_a \cup v_b|| \tag{6} Vab∣∣va∩vb∣∣/∣∣va∪vb∣∣(6) 为了构建组我们对图像进行排序 I ˉ { I i ∣ ∣ ∣ v i ∣ ∣ ≥ ∣ ∣ v i 1 ∣ ∣ } \bar{\mathcal{I}}\{ I_i \Big | ||v_i|| \geq ||v_{i1}|| \} Iˉ{Ii ∣∣vi∣∣≥∣∣vi1∣∣}。我们通过从 I ˉ \bar{\mathcal{I}} Iˉ中删除第一张图像 I a I_a Ia并找到最大化 V a b V_{ab} Vab的图像 I b I_b Ib来初始化组 G r G_r Gr。如果 V a b V V_{ab} V VabV和 ∣ G r ∣ S |G_r|S ∣Gr∣S图像 I b I_b Ib从 I ˉ \bar{\mathcal{I}} Iˉ中删除并添加到组 G r G_r Gr中。否则初始化一个新的组。为了减少寻找 I b I_b Ib的时间我们采用了启发式算法将搜索限制在空间上最近邻的 K r K_r Kr上这些图像在 ± β \pm \beta ±β度范围内具有共同的观察方向这一事实的动机是这些图像具有很高的相似性它们共享许多点。 图4 高斯分布点 x j ∈ [ 0 , 1 ] × [ 0 , 1 ] x_j \in [0,1]\times [0,1] xj∈[0,1]×[0,1]的次优视图分数该高斯分布的平均值为 μ \mu μ标准差为 σ \sigma σ。右图的 μ \mu μ为0.5。
然后组内的每张图像在一个共同的组内局部坐标系上进行参数化。对于一组图像的BA代价函数公式1为 E g ∑ j ρ j ( ∣ ∣ π g ( G r , P c , X k ) − x j ∣ ∣ 2 2 ) (7) E_g\sum_j \rho_j \Big( || \pi_g \big( G_r,P_c,X_k \big) -x_j ||_2^2 \Big) \tag{7} Egj∑ρj(∣∣πg(Gr,Pc,Xk)−xj∣∣22)(7) 其中 G r ∈ S E ( 3 ) G_r\in SE(3) Gr∈SE(3)为外部组参数 P c P_c Pc为固定值。然后定义组 r r r中图像的投影矩阵为组与图像位姿的级联 P c r P c G r P_{cr} P_cG_r PcrPcGr。总代价 E ˉ \bar{E} Eˉ是分组成本贡献和未分组成本贡献的总和。为了有效地串联 G r G_r Gr和 P i P_i Pi的旋转分量我们依赖于四元数。相对于 π \pi π由于计算 π g \pi_g πg的开销较小较大的组可以带来更大的性能优势。请注意即使对于组大小为2我们也能观察到计算优势。此外性能优势取决于问题的大小因为相机数量的减少对直接法的 O ( N 3 ) O(N^3) O(N3)时间复杂度的影响大于间接法的 O ( N ) O(N) O(N)时间复杂度第2节。
5 实验
我们在大量不同的数据集上运行实验与最先进的增量Bundler, VisualSFM和全局SfM系统DISCO, Theia进行比较评估所提出的组件和整个系统。这17个数据集共包含144953张无序的互联网照片分布在一个很大的区域并且相机密度变化很大。此外Quad有相机位置真值。在所有实验中我们使用RootSIFT特征并使用在不相关数据集上训练的词汇树将每个图像与其100个最近的邻居进行匹配。为了确保不同方法之间的可比性在具有256GB RAM的2.7GHz机器上不包括对应搜索步骤。 图5 Quad的下一个最佳视图结果在增量SfM期间共享的配准图像数量和重建误差。 图6 对于Dubrovnik数据集的三角化统计。左图特征轨迹的离群比分布。右图三角测量N个视点所需的平均样本数。 图7 平均相对运行时间。标签1表示标准全局BA、穷举三角化。标签2表示分组BA、RANSAC三角化。初始化和下一个最佳视图选择所有策略的运行时间小于0.1%。 下一个最佳视图选择。 一个综合实验图 4评估了分数S对点的数量和分布的反映程度。我们使用 L 6 L6 L6的金字塔层级生成 ( σ , μ ) (\sigma,\mu) (σ,μ)的高斯分布图像点。更大的 σ \sigma σ和更中心的 μ \mu μ对应于更均匀的分布正确地产生了更高的分数。类似地当点数很少时分数由点的数量决定否则由它们在图像中的分布决定。另一个实验图5将我们的方法金字塔与现有策略在重建误差方面进行了比较。其他方法是Number它最大化三角测量点的数量以及Ratio它最大化可见点与潜在可见点的比例。在每个图像配准后我们测量策略之间共享的配准图像数量交集/联合和重建误差作为到相机位置真值的中位数距离。虽然所有策略都收敛到同一组配准图像但我们的方法通过为图像选择更好的配准顺序来产生最准确的重建。
鲁棒和高效地三角测量。 在Dubrovnik数据集上的实验图6和表2对由47M个验证匹配组成的2.9M条特征轨迹进行了评估。我们与Bundler和穷尽策略进行比较该策略对轨迹中的所有成对组合进行采样。我们设置 α 2 ° \alpha2° α2° t 8 t8 t8px ϵ 0 0.03 \epsilon_00.03 ϵ00.03。为了避免组合爆炸我们将穷举方法限制为10K次迭代也即 ϵ m i n ≈ 0.02 \epsilon_{min} \approx0.02 ϵmin≈0.02 η 0.999 \eta0.999 η0.999。多样化的内点比分布通过递归、穷举方法确定证明需要一种鲁棒的三角测量方法。我们提出的递归方法比非递归方法恢复更长的轨道和更多的轨道元素。注意基于RANSAC的递归方法的点数越多轨迹长度就越短。基于RANSAC的方法产生的轨迹略差但速度更快10-40 倍。通过改变 η \eta η很容易平衡速度和完整度。 表1 最先进的SfM系统在大规模无序互联网图片集上的重建结果。 表2 η 1 0.99 \eta_10.99 η10.99和 η 2 0.5 \eta_20.5 η20.5时的三角测量结果。 图8 不同的场景覆盖 V V V ϵ r 0.02 \epsilon_r0.02 ϵr0.02 S 10 S10 S10时在标准分组BA中的相机数目。 冗余视图挖掘。 我们在稠密分布图像的无序集合上评估了冗余视图挖掘。图8显示了固定BA迭代次数下参数化相机数目在全局BA中的增长速率。根据强制的场景重叠 V V V我们可以通过一个重要的因子来减少求解相机系统的时间。总运行时间的有效加速分别为5% V 0.6 V0.6 V0.614% V 0.3 V0.3 V0.332% V 0.1 V0.1 V0.1而平均重投影误差分别从0.26px标准BA降低到0.27px、0.28px和0.29px。当 V 0.3 V0.3 V0.3时这几种配置下的重建质量相差不大。 V V V越小重建质量越差。使用 V 0.4 V 0.4 V0.4对于Colosseum的整个管道的运行时间减少了36%但重建的质量是基本相同的。
系统。 表1和图1展示了整个系统的性能从而也评估了系统中各个组件的性能。对于每个数据集我们报告最大的重建组件。Theia是最快的方法而我们的方法获得的时间比VisualSFM略差比Bundler快50倍以上。图7显示了各个模块的相对时序。对于所有数据集我们在完整度方面明显优于任何其他方法特别是对于较大的模型。重要的是增加的轨迹长度导致BA中更高的冗余。此外我们在Quad数据集上实现了最佳位姿精度DISCO 1.16米Bundler 1.01米VisualSFM 0.89米本文的方法 0.85米。图9对比了我们的方法和Bundler的重建结果。我们鼓励读者查看补充材料对结果进行额外的视觉比较展示我们方法的优越鲁棒性完整度和准确性。 图9 我们的方法和Bundler在Gendarmenmarkt下的重建结果。
6 结论
本文提出了一种克服关键挑战的SfM算法为实现通用SfM系统迈出了一步。所提出的算法组件在完整度、鲁棒性、准确性和效率方面提高了现有技术水平。在具有挑战性的大规模数据集上进行的综合实验证明了各个组件和整个系统的性能。整个算法作为开源实现向公众发布。
致谢。 我们感谢J. Heinly和T. Price的校对。我们还要感谢C. Sweeney提供了Theia实验。 Supported in part by the NSF No. IIS-1349074, No. CNS-1405847, and the MITRE Corp.
参考文献
略
