英语原文共 8 页
从运动到线性时间增量结构
摘要：相对于摄像机的数量，来自运动的增量结构（SfM）的时间复杂度通常被称为。通过预处理共轭梯度（PCG）显着改善了约束调整（BA），因此值得重新审视增量SfM的快速程度。我们引入了一种新的BA策略，可在速度和准确度之间取得良好的平衡通过算法分析和大量实验，我们证明增量SfM在包括BA在内的许多主要步骤上仅需要O(n)时间。我们的方法通过定期重新三角测量最初未能进行三角测量的特征匹配来保持高精度。我们在大型照片集和各种设置的长视频序列上测试我们的算法，并表明我们的方法为大规模重建提供了最先进的性能。所提出的算法作为VisualSFM的一部分提供，网址为http://homes.cs.washington.edu~ccwu/vsfm/。
1 引言
运动结构（SfM）已成功用于重建越来越大的不受控制的照片集[8,2,5,4,7]。尽管可以将大型照片集合缩减为用于重建的图标图像[8,5]或骨架图像[15,2]的子集，但是对于大型场景组件，常识之中增量SfM的成本仍然很高。最近，通过使用离散和连续优化的组合证明了方法[4]。然而，对于SfM来说，实现低复杂性和高可扩展性仍然至关重要。
本文通过以下贡献证明了我们为进一步提高SfM效率所做的努力：
(1)我们引入了抢占式特征匹配，可以将图像匹配对减少高达95％，同时仍然可以恢复足够的重建匹配。
(2)我们分析时间复杂度共轭梯度束调整方法。通过理论分析和实验验证，我们表明束调整在实践中需要时间。
(3)我们展示了增量SfM的许多子步骤，包括BA和点过滤在内，在使用新的BA策略时仅需要时间。
(4)在不牺牲时间复杂度的情况下，我们引入了一个重新拼接步骤来处理累积漂移的问题而没有明确的循环闭合。
本文的其余部分安排如下：第2部分介绍了背景和相关工作。我们首先在第3节中介绍了抢先特征匹配。我们在第4节中分析了束调整的时间复杂度，并在第5节中提出了新的SfM算法。实验和结论在第6节和第7节中给出。
2 相关工作
在典型的增量SfM系统[14]中，首先在两个图像之间成功匹配时估计两个视图重建，然后通过从良好的两视图重建初始化，重复添加匹配图像，三角测量特征匹配以及三维模型来重建三维模型。束调整结构和运动。对于n个图像，这种增量SfM算法的时间复杂度通常已知为，并且这种高计算成本阻碍了在大型照片集上应用这种简单的增量SfM。
大规模数据通常包含大量冗余信息，这使得3D重建的许多计算可以近似有利于速度，例如：
图像匹配Agarwal等人并没有将所有图像相互匹配[2]。首先使用词汇树识别[11]为每个图像识别少量候选，然后使用近似最近邻居匹配特征。结果表明，图像匹配的双重近似仍然保留了足够的SfM特征匹配。弗拉姆等人[5]利用近似的GPS标签，仅将图像与附近的图像匹配。在本文中，我们提出了一种抢占特征匹配，以进一步提高匹配速度。
光束法平差由于BA已经利用了非线性优化问题的线性近似，因此通常不必解决精确的下降步骤。最近的算法通过使用预条件共轭梯度（PCG）来近似求解线性系统[2,3,1,16]，从而实现了显着的加速。类似地，不需要为每个新图像运行完整BA，或者总是等到BA / PCG收敛到非常小的残差。在本文中，我们展示了对大规模不受控制的照片集合进行束调整所需的线性时间。
场景图大型照片集通常包含足够多的图像以进行高质量的重建。通过减少高成本SfM的图像数量可以提高效率[8,5]。使用标志性图像作为场景图的主要骨架[15,2]，而从密集场景图中提取骨架图。实际上，对于大规模SfM的其他类型的改进应该与场景图简化一起使用。然而，为了突破增量SfM的极限，我们考虑重构单个连通分量而不简化场景图。
与增量SfM相比，其他工作试图避免贪婪的方式[6]。通过平衡分支和合并提出了分层SfM，通过要求较少的大型模型的BA来降低时间复杂度[13]。从消失点恢复相对相机旋转，并将SfM转换为有效的3D模型合并。最近，Crandall等人[4]利用基于GPS的初始化和模型SfM作为全局MRF优化。这项工作是对增量SfM的重新调查，并且仍然存在一些局限性，例如影响完整性的初始化，但不依赖于额外的校准，GPS标签或消失点检测。
使用n、p和q分别表示重建期间的摄像机点和观测数量。假设每个图像具有有限数量的特征，则我们具有和。由于本文考虑单个连接的场景图，因此n也用作滥用符号的输入图像的数量。
3 抢占特征匹配
图像匹配是SfM最耗时的步骤之一。完全成对匹配对于n个输入图像需要时间，但是对于大型数据集来说计算匹配子集（例如通过使用词汇树[2]）是合适的，并且整体计算可以减少到。此外，图像匹配可以轻松并行化到多台机器[2]或多个GPU[5]上，以实现更快的速度。然而，功能匹配仍然是瓶颈之一，因为典型的图像包含数千个功能，这是我们尝试处理的方面。
由于大型照片集中视点的多样性，大多数图像对不匹配（我们实验的大型数据集的75％-98％）。如果我们能够稳健有效地识别好的对，则可以节省大部分匹配时间。通过利用不变特征尺度[10]，我们建议为此目的进行以下抢先特征匹配：
1.将每个图像的特征排序为递减比例顺序。这是一次预处理。
2.使用所有对或选择子集[2,5]生成需要匹配的对列表。
3.对于每个图像对(并行)，执行以下操作：
（a）匹配两个图像的前个特征。
（b）如果子集中的匹配数小于，则返回并跳过下一步。
（c）进行常规匹配和几何估计。
其中是子集大小的参数，是预期匹配数的阈值。子集和全集的特征匹配使用相同的最近邻算法和距离比测试[10]，并要求匹配的特征相互最接近。
令和是两个图像的特征数，并且。当使用多达个顶级特征时，让和为推定和内部匹配的数量。我们将特征匹配的产量定义为：
我们感兴趣的是特征子集的产量如何与最终产量相关联。如图1(a)所示，即使对于非常小的，例如100，和的分布也与密切相关。图1(b)显示了具有a的可能性。顶级功能内的匹配与其他功能相同。这意味着顶级子集具有保持匹配的大致机会，这远远高于随机采样特征的机会。此外，大多数的匹配时间减少到因子以及更好的缓存。在本文中，我们考虑效率和鲁棒性选择h = 100。
由于以下几个原因，顶级特征匹配良好：1）由于较高高斯水平上的特征数量减少，少量的顶级特征可以覆盖相对大的范围； 2）特征匹配结构良好，使得一个图像中的大尺度特征经常与另一个图像中的大尺度特征匹配。两个匹配特征之间的尺度变化由相机运动和场景结构共同决定，因此多个特征匹配的尺度变化不是彼此独立的。图1(c)显示了我们的特征尺度变化的统计数据。由于视点变化小或结构良好的场景深度，图像对的特征尺度变化通常具有小的变化。出于同样的原因，我们使用多达8192个功能进行常规功能匹配，这对于大多数情况都是足够的。虽然大型照片集包含多余的视图和功能，但我们的抢先功能匹配允许将大部分工作放在更有可能匹配的照片上。
图1.（a）显示了最终产量与一系列顶级特征的产量之间的关系。对于具有大致相同的最终产量的每组图像对，我们计算不同的子集产量的中值。（b）给出特征匹配的两个索引的最大值的直方图，其中索引是按比例递减顺序的位置。我们可以看到在顶级功能中匹配的可能性与其他功能类似。（c）显示了从130M特征匹配计算出的两个尺度变化分布。两个图像之间的平均尺度变化由红色曲线给出，而尺度变化与平均值的偏差由蓝色曲线给出。由于视点变化小或结构化的场景深度，尺度变化的变化通常很小。
4 光束法平差有多快？
束调整（BA）是结构和运动参数的联合非线性优化，Levenberg-Marquardt（LM）是选择的方法。最近，预处理共轭梯度（PCG）[1,3,16]显著改善了大规模束调整的性能，因此值得重新检查BA和SfM的时间复杂度。
令x为参数矢量，为3D重建的重投影误差矢量。我们希望解决的优化是非线性最小二乘问题：。设J是的雅可比行列式，Lambda;为正则化非正对角矢量，然后LM重复求解下面的线性系统：
当时，更新。矩阵 被称为Hessian增广矩阵。高斯消元通常用于首先获得相机参数的简化线性系统，该相机参数被称为Schur补充。
Hessian矩阵需要空间和时间来计算，而Schur补集需要空间和时间来计算。通过Cholesky分解求解线性系统需要立方时间或。由于摄像机的数量远小于点的数量，因此Schur补充方法可以通过大的常数因子来减少因子分解时间。这个算法的一个令人印象深刻的例子是Photo Tourism [14]使用的Lourakis和Argyros的SBA [9]。
对于共轭梯度方法，主导计算是多重CG迭代中的矩阵向量乘法，其时间复杂度由所涉及的矩阵的大小确定。通过仅使用空间Hessian矩阵并避免Schur补集，CG迭代实现了时间复杂度[1,3]。最近，多核束调整[16]通过使用Hessian矩阵和Schur补集的隐式乘法更进了一步，这需要仅构造空间雅可比矩阵。在这项工作中，我们使用GPU版本的多核束调整。图2（a）显示了来自我们的束调整问题的CG迭代的时序，其展示了CG迭代的时间Tcg与n之间的线性关系。
在每个LM步骤中，PCG需要次迭代来精确求解线性系统[12]，其中是线性系统的条件数。通过使用良好的预处理器可以获得小的条件数，例如，已经使用blockjacobi预处理器证明了快速收敛速度[1,16]。在我们的实验中，PCG使用平均20次迭代求解线性系统。
令人惊讶的是，如果在BA中存在CG迭代，则束调整的时间复杂度已经达到。虽然CG / LM迭代的实际数量取决于输入问题的难度，但我们从大量不同问题规模的BA收集的统计数据很好地支持了CG / LM迭代的假设。图2(b)给出了BA使用的LM迭代的分布，其中平均值为37％且93％的BA在小于100次LM迭代内收敛。图2(c)显示了总CG迭代的分布（由BA的所有LM步骤使用），它们通常也很小。在实践中，我们选择每BA最多使用100次LM迭代，最多使用每个LM 100次CG迭代，保证了大多数问题的良好收敛。
图2.光束法平差统计信息中（a）表明，无论场景图结构如何，Tcg都与n大致呈线性关系。（b）和（c）显示BA使用的LM和CG迭代次数的分布。可以看出，BA通常在少量的LM和CG迭代中收敛。请注意，如果均方误差降至0.25以下或无法降低，则我们认为BA会收敛。
5 运动的增量结构
本节介绍了我们的SfM设计，它实际上具有线性运行时间。束调整可以在时间内完成的事实打开了推动增量重建时间更接近的机会。如图3所示，我们的算法在每次迭代时添加一个图像，然后运行完整BA或部分BA。在BA和过滤之后，我们在继续下一次迭代和重新三角测量步骤之间做出另一种选择。
图3. 建议的增量SfM的单次迭代，重复直到没有图像可以添加到重建
5.1增量SfM的速度有多快
在重建期间，摄像机和3D点通常会快速稳定，因此无需在每次迭代时优化所有摄像机和点参数。典型的策略是在添加恒定数量的摄像机（例如）之后执行完整的BA，其中所有完整的BA的累积时间是
使用PCG时。这已经从基于Cholesky因子分解的BA的时间显着减少。随着模型变得越来越大，越来越稳定，可以省去更昂贵的BA，因此我们希望在不失去准确性的情况下研究我们能走得多远。在本文中，我们发现通过使用完整BA的几何序列，BA的累积时间可以更多地减少到。我们建议仅在模型的大小相对增加某个比率r（例如5％）时执行完全优化，并且花费在完整的BA上的结果时间近似变为
虽然后者添加的摄像机通过较少的完整BA进行优化，但通常没有精度问题，因为对于具有较大误差的部分，完整的BA总是会提高更多。随着模型变大，在运行完整BA之前会添加更多相机。为了减少累积误差，我们通过在最近添加的恒定数量的相机（我们使用20个）及其相关的3D点上使用部分BA来继续运行局部优化。这种部分优化涉及个摄像机和点参数，因此每个部分BA需要个时间。因此，在完整的BA和部分BA上花费的时间增加了，这通过图6中的时间曲线进行实验验证。
在BA步骤之后，我们对具有大的重投影误差或小的三角测量角度的点进行滤波。全点滤波步骤的时间复杂度是。幸运的是，我们只需要处理已经改变的3D点，因此部分BA之后的点过滤可以在时间内完成。尽管在完整BA之后的每个点过滤花费时间，但是由于几何序列它们仅添加到。因此，所有点过滤的累计时间也是。
另一个昂贵的步骤是组织切除候选者并向3D模型添加新的相机。我们通过使用新添加的图像的特征匹配来跟踪SfM期间潜在的2D-3
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
