Building Rome in a Day¶

论文链接

原文：Sameer Agarwal, Noah Snavely, Ian Simon, Steven M Seitz, Richard Szeliski. Building Rome in a Day

关联：Noah Snavely, Steven M. Seitz, Richard Szeliski. Modeling the World from Internet Photo Collections

注意

由 claude 和 chatgpt 翻译整理

1 引言¶

进入 flickr.com 并搜索“罗马”一词，将返回超过 270 万张照片。这些收集代表了一个日益完整的城市摄影记录，捕捉了每一个热门场所、外观、内饰、喷泉、雕塑、绘画、咖啡馆等等。大多数这些照片是从成百上千的观点和照明条件拍摄的——单单 Trevi 喷泉就有超过 5 万张照片在 Flickr 上。在类似的收集中重建单个建筑或广场的激动人心的进展已经取得，展示了将结构化运动(SfM)算法应用于最多几千张无序照片收集的潜力。本文介绍了第一个能够从无序照片收集进行城市规模重建的系统。我们提供的模型规模比文献中报道的下一个最大结果大一个到两个数量级。此外，我们的系统使得在一天内重建 15 万张图像的数据集成为可能。

2 系统设计¶

我们的系统运行在计算机（节点）集群上，其中一个节点被指定为主节点。主节点负责各种作业调度决策。

在本节中，我们详细描述我们系统的设计，这可以自然地分为三个不同的阶段

预处理 §2.1
匹配 §2.2
几何估计 §2.4。

2.1 预处理和特征提取¶

我们假设图像在一个中心存储上可用，图像从中按固定大小的块分发到集群节点以按需方式。这自动进行负载平衡，更强大的节点接收更多的图像进行处理。

这是唯一需要中心文件服务器的阶段；系统的其余部分在没有共享存储的情况下运行。这样做是为了我们可以从互联网上独立于我们的匹配和重建实验下载图像。对于生产使用，每个集群节点从互联网爬取图像在匹配和重建进程开始时将是非常简单的。

在每个节点上，我们首先验证图像文件是否可读，是有效的图像。然后我们提取 EXIF 标签（如果存在），并记录焦距。我们还将大于 200 万像素的图像下采样，保持其宽高比并相应地缩放焦距。然后将图像转换为灰度并从中提取 SIFT 特征。我们使用 SIFT++ 实现其速度和灵活的接口。在此阶段结束时，整个图像集被划分为不相交的集合，每个节点拥有一个。每个节点拥有它所拥有的分区的图像和 SIFT 特征。

2.2 图像匹配¶

匹配两张图像的关键计算任务是兴趣点的光度匹配和使用基本或本质矩阵的稳健估计对这些匹配进行几何验证。尽管两张图像之间的所有特征的穷举匹配是不实际的，但使用近似最近邻搜索报告了优秀的结果。我们使用 ANN 库进行 SIFT 特征匹配。对于每对图像，将一个图像的特征插入 k-d 树，并将另一图像的特征用作查询。对于每个查询，我们考虑两个最近邻居，并接受通过 Lowe 比率测试的匹配。我们使用基于优先级队列的搜索方法，最大容器访问数上限为 200。依我们的经验，这些参数在计算成本和匹配准确性之间提供了良好的权衡。然后使用基于 RANSAC 的基本或本质矩阵估计对近似最近邻搜索返回的匹配进行修剪和验证，具体取决于从 EXIF 标签获得的焦距信息的可用性。这两个操作构成了我们的匹配引擎的计算内核。

不幸的是，即使使用上述匹配过程的优化实现，也不实际对我们语料库中的所有图像对进行完全匹配。对于 10 万张图像的语料库，这将转换为 50 亿次成对比较，如果用 500 个核心以每个核心每秒 10 对图像的速度运行，也需要大约 11.5 天才能完成匹配。此外，这甚至没有考虑到所有的内核都需要访问所有图像的所有 SIFT 特征向量的数据所需的网络传输。

即使我们能够做所有这些成对匹配，由于图像对的压倒性多数不匹配，这也会是计算力的浪费。这是从与广泛标签（如城市名称）相关的一组图像中可以预期的。因此，我们必须小心选择系统花时间匹配的图像对。

基于近期有效物体检索的工作，我们使用多阶段匹配方案。每个阶段包括一个建议和一个验证步骤。在建议步骤中，系统确定一组预计共享常见场景元素的图像对。在验证步骤中，对这些图像对执行详细的特征匹配。以这种方式获得的匹配然后指导下一个建议步骤。

在我们的系统中，我们使用两种方法生成建议：基于词汇树的整图像相似性 §2.2.1 和查询扩展 §2.2.4。验证阶段在 §2.2.2 中描述。图 1 显示了整个匹配管道的系统图。

2.2.1 基于词汇树的提议¶

受文本检索启发的方法已经非常成功地应用于对象和图像检索问题。这些方法基于将图像表示为词袋，其中的词是通过对图像特征进行量化获得的。我们使用基于分层 k 均值树的方法，其中使用分层 k 均值树对特征描述符进行量化。(参见第 3 节，关于我们如何使用小的训练集图像构建词汇树的详细信息。)这些量化结果在所有特征上进行汇总，以获得图像的词频(TF)向量，并获得图像集合的文档频率(DF)向量（图 1a-e）。文档频率向量在节点之间收集成单个向量，并在集群内广播。每个节点将其拥有的词频向量归一化以获得该节点的 TF-IDF 矩阵。这些每节点 TF-IDF 矩阵在网络内广播，这样每个节点都可以计算其 TF-IDF 向量与其余 TF-IDF 向量之间的内积。在效果上，这是分布式矩阵乘法，但每个节点只计算它拥有的图像块对应的行。对于每个图像，识别前 k1+k2 个得分最高的图像，其中前 k1 个图像用于初始验证阶段，额外的 k2 个图像用于扩大连通分量（见下文)。

我们的系统与 Nister 和 Stewenius 的系统不同，因为他们的系统有一个固定的数据库进行匹配。因此，他们可以直接在词汇树本身中存储数据库，并即时评估图像在数据库中的匹配分数。在我们的情况下，查询集与数据库相同，在编码特征时不可用。因此，我们必须有一个单独的矩阵乘法阶段来找到最佳匹配图像。

2.2.2 验证和详细匹配¶

下一步是验证候选图像匹配，然后在匹配图像之间找到详细的匹配集。如果所有图像都位于一台机器上，验证提议的匹配图像对将是简单的事情，可能会关注验证执行的顺序，以最小化磁盘 I/O。但是，在我们的情况下，图像及其特征描述符分布在集群节点上。因此，要求一个节点匹配图像对(i,j)需要它从集群的另外两个节点获取图像特征。这是不可取的，因为网络传输速度与本地磁盘传输之间存在很大差异。此外，这为三个节点创建了工作。因此，图像对应该以尊重数据的局部性并最小化网络传输量的方式分布在网络上（图 1f-g）。

我们试验了许多方法，结果令人惊讶。我们最初试图在进行任何验证之前优化网络传输。在此设置中，一旦主节点拥有所有需要验证的图像对，它会构建一个连接需要验证的图像对的图。使用 MeTiS，该图被划分成与计算节点一样多的片段。然后通过解决一个最小化每个节点所需的网络传输数的线性分配问题，将分区与计算节点匹配。对于小问题大小，该算法效果良好，但随着问题规模的增加，其性能变得降低。我们认为详细匹配所有图像对需要相同的固定时间的假设是错误的：一些节点提前完成并闲置长达一个小时。

我们尝试的第二个想法是将图过度划分成小块，并根据要求将它们分配给集群节点。当一个节点请求另一个工作块时，具有最少网络传输的块分配给它。这种策略实现了更好的负载均衡，但随着问题规模的增长，我们需要划分的图变得极大，划分本身成为瓶颈。

给出最佳结果的方法是使用简单的贪婪装箱算法（其中每个箱表示发送到节点的一组作业），具体工作原理如下。主节点维护每个节点上的图像列表。当一个节点请求工作时，它运行需要验证的图像对列表，如果它们不需要任何网络传输，则添加到箱中，直到箱满或没有更多可以添加的图像对。然后它选择一个图像（特征向量列表），将其传输到节点，该图像允许它向箱中添加尽可能多的图像对。重复该过程直到箱满。这个算法有一个缺点：它可能需要对所有需要匹配的图像对进行多次扫描。对于大型问题，调度作业可能成为瓶颈。一个简单的解决方案是每次只考虑一部分作业，而不是试图全局优化。这种窗口化方法在实践中非常有效，我们的所有实验都是用这种方法运行的。

验证图像对是一个两步过程，包括特征描述符之间的光度匹配和使用基本或本质矩阵对匹配进行稳健估计，具体取决于相机标定信息的可用性。在本质矩阵估计成功的情况下，两台相机的拍摄方向之间有足够的角度，并且匹配数量超过阈值时，我们会进行完整的两视图欧几里得重建并存储它。这些信息用于后面的阶段（参见第 2.4 节）以减小重建问题的规模。

2.2.3 合并连通分量¶

在此阶段，考虑图像的图，其中连接两个图像的边表示在它们之间找到匹配特征。我们称之为匹配图。为了获得尽可能全面的重建，我们希望此图中的连通分量数最少。为此，我们进一步利用词汇树的建议，试图连接此图中的各个连通分量。对于每个图像，我们考虑词汇树建议的接下来 k2 个图像。从这些图像中，我们验证那些跨越两个不同连通分量的图像对（图 1h-i）。我们仅对大小为 2 或更多的组件中的图像执行此操作。因此，与前 k1 个建议匹配中任何图像都不匹配的图像将被有效放弃。得到的图像对再次进行详细特征匹配。图 2 说明了这一点。请注意，在第一轮之后，匹配图有两个连通分量，在第二轮匹配后合并成一个组件，查询扩展迅速增加了组件内连接的密度。最后一列显示与最终匹配图对应的骨架集。骨架集算法可以在确定无法进行可靠重建的情况下破坏匹配阶段找到的连通分量，这就是本例中发生的情况。

2.2.4 查询扩展¶

在执行两轮如上所述的匹配后，我们得到一个通常不足以可靠产生良好重建的匹配图。为了补救这一点，我们使用文档检索研究中的另一个想法——查询扩展。

最简单的形式中，查询扩展是首先找到与用户查询匹配的文档，然后用它们再次查询数据库，从而扩展初始查询。系统返回的结果是这两个查询的某种组合。从本质上讲，如果我们在一组文档上定义一个图，其中相似文档由边连接，并将查询视为一个文档。那么查询扩展等价于找到距离查询顶点两步之内的所有顶点。

在我们的系统中，我们考虑图像匹配图，其中图像 i 和 j 如果它们有一定数量的共同特征则连接。现在，如果图像 i 与图像 j 相连，图像 j 与图像 k 相连，我们进行详细匹配以检查图像 j 是否与图像 k 匹配。可以固定次数重复此过程，或者直到匹配图收敛。

进行多轮查询扩展时的一个问题是漂移。次要查询的结果可能会迅速偏离原始查询。这在我们的系统中不是问题，因为查询扩展的图像对在连接为匹配图的边之前，必须经过详细的几何验证。

2.3 轨迹生成¶

匹配过程的最后一步是合并所有两两图像之间的匹配信息以在图像间生成一致的轨迹，也就是在特征图中找到并标记所有连通分量。由于匹配信息保存在计算生成它的本地节点上，轨迹生成过程分两个阶段进行（图 1k-m）。首先，每个节点使用它本地可用的所有匹配数据生成轨迹。这些数据汇总在主节点并广播到所有的网络节点。请注意，每个连通分量的轨迹可以独立处理。然后每个计算节点被分配一个它需要生成轨迹的连通分量。当我们根据共享特征合并轨迹时，可能生成不一致的轨迹，其中同一图像中的两个特征点属于同一轨迹。在这种情况下，我们从轨迹中删除冲突的点。

一旦生成了轨迹，下一步是从对应的图像特征文件中提取出现在轨迹中的特征点的 2D 坐标。我们还提取每个这样的特征点的像素颜色，后来用于用特征点相关的平均颜色渲染 3D 点。同样，这个过程也分两个步骤进行。给定每个组件的轨迹，每个节点从它拥有的 SIFT 和图像文件中提取特征点坐标和点颜色。这些数据汇总并通过网络广播，在每个连通分量的基础上进行处理。

2.4. 几何估计¶

一旦轨迹被生成，接下来的步骤是在匹配图的每个连通分量上运行结构运动（SfM），以恢复每个相机的姿态和每个轨迹的三维位置。大多数用于无序照片集合的 SfM 系统是增量的，从一个小的重建开始，然后逐步增加几幅图像，三角测量新点，并进行一轮或多轮非线性最小二乘优化（称为束调整【19】），以最小化投影误差。这个过程会重复进行，直到不能再添加更多相机为止。然而，由于我们收集的规模，将这样的增量方法同时应用于所有照片是不现实的。上述描述的增量重建过程中隐含了一个假设，即所有图像对于重建的覆盖和精度都有更多或更少的相等贡献。然而，互联网照片集合本质上是冗余的——许多照片是从附近的视点拍摄的，处理所有这些照片不一定会增加重建的精度。因此，最好是找到并重建一组捕捉匹配图的基本连接性和场景几何的最小照片子集【8, 17】。一旦完成了这一步骤，我们可以使用姿态估计添加回所有剩余的图像，三角测量所有剩余的点，然后进行最终的束调整以优化 SfM 估计。为了找到这个最小集，我们使用【17】中的骨架集算法，该算法计算出一个跨度照片集，以保留图像图中的重要连接信息（例如大型循环）。在【17】中，为每对具有已知焦距的匹配图像计算了两帧重建。在我们的系统中，这些成对的重建是作为并行匹配过程的一部分计算出来的。一旦计算出骨架集，我们使用【16】中的增量算法估计每个结果组件的 SfM 参数。骨架集算法通常会在弱连接边界处分割连接的组件，从而导致更大的组件集。

2.4.1 束调整¶

在将 SFM 问题的规模缩小到骨架集之后，重建过程中的主要瓶颈是非线性最小化的投影误差，或者束调整（BA）。公开可用的性能最佳的 BA 软件是 Lourakis＆Argyros 的稀疏束调整（SBA）【9】。其高性能的关键在于使用所谓的舒尔补技巧【19】来减小每次 Levenberg-Marquardt（LM）算法迭代中需要解决的线性系统的大小（也称为正规方程）。这个线性系统的大小取决于 3D 点和相机参数，而舒尔补的大小仅取决于相机参数。然后，SBA 使用稠密的 Cholesky 分解来分解和求解所得到的减小的线性系统。由于典型的 SfM 问题中的 3D 点数量通常比相机数量大两个数量级或更多，因此可以实现显著的节省。这对于小到中等大小的问题有效，但是对于具有数千个图像的大问题来说，计算舒尔补的稠密 Cholesky 分解成为空间和时间瓶颈。然而，对于大问题，舒尔补本身相当稀疏（一个 3D 点通常只在几个相机中可见），利用这种稀疏性可以节省大量的时间和空间。我们开发了一个新的高性能束调整软件，根据问题的大小，它在截断和精确步长 LM 算法之间进行选择。在第一种情况下，使用块对角线预处理的共轭梯度方法来近似求解正规方程。在第二种情况下，使用 CHOLMOD【4】，一种用于计算 Cholesky 分解的稀疏直接方法，通过舒尔补准确求解正规方程。与 SBA 相比，由此产生的代码使用的内存明显更少，运行速度高出一个数量级。准确的运行时间和内存节省取决于所涉及的线性系统的稀疏结构。

2.5 分布式计算引擎¶

我们的匹配和重建算法是作为一个双层系统实现的。在系统的基础上是一个与应用无关的分布式计算引擎。除了一个很小的核心很容易移植外，该系统是跨平台的，可以在所有主要的 UNIX 和 Microsoft Windows 版本上运行。该系统小而可扩展，虽然它带有许多调度策略和数据传输原语，但用户可以自由添加自己的内容。该系统针对在大量数据上操作的批处理应用程序，具有广泛的应用数据本地缓存和网络数据按需传输的支持。如果有共享文件系统可用，可以使用它，但为了获得最佳性能，所有数据都存储在本地磁盘上，仅在需要时通过网络传输。它支持各种调度模型，从简单的数据并行任务到通用的 map-reduce 风格计算。分布式计算引擎编写为一组 Python 脚本，计算的每个阶段都是由 Python 和 C++代码的组合实现的。

3 实验¶

我们在从 flickr.com 下载的三个城市数据集上运行系统的结果如下：克罗地亚的杜布罗夫尼克，意大利的罗马和威尼斯。图 3（a），3（b）和 3（c）显示了这些数据集中最大连通分量的重建情况。由于空间限制，这里只显示了一部分结果样本，我们鼓励读者访问 http://grail.cs.washington.edu/rome，这里发布了完整的结果，并且随着时间的推移，还会发布额外的结果、数据和代码。实验在一个由 62 个节点组成的集群上运行，每个节点都有双四核处理器，私有网络上有 1GB/秒的以太网接口。每个节点配备了 32 GB 的 RAM 和 1 TB 的本地硬盘空间。节点上运行着 Microsoft Windows Server 2008 64 位操作系统。所有实验都使用了相同的词汇树，这棵树在线下训练中使用了从罗马的 20000 张图像中提取的 1918101 个特征。我们训练了一棵分支系数为 10，总共有 136091 个顶点的树。对于每个图像，我们使用词汇树找到前 20 个匹配图像。在第一次验证阶段中使用了前 k1 = 10 个匹配图像，在第二次组件匹配阶段中使用了接下来的 k2 = 10 个匹配图像。进行了四轮查询扩展。我们发现在所有情况下，执行的匹配次数与验证的匹配次数之比在四轮后开始下降。表 1 总结了这三个数据集的统计数据。表 1 中的重建时间数据需要一些解释。令人惊讶的是，杜布罗夫尼克的 SfM 时间要比罗马的时间多得多，几乎与威尼斯相同，而后两者的数据集要大得多。原因在于数据集的结构。罗马和威尼斯数据集本质上是地标的集合，在大规模上具有简单的几何和可见性结构。另一方面，杜布罗夫尼克中的最大连通分量捕捉了整个古城。由于其狭窄的巷道、复杂的可见性和广泛变化的视点，这是一个更复杂的重建问题。这反映在与最大连通分量相关联的骨架集的大小上，如表 2 所示。如上所述，骨架集算法通常会在弱连接边界处分割连接的组件，因此匹配系统返回的连通分量的大小（CC1）大于骨架集算法返回的连通分量（CC2）的大小。

4 讨论¶

在撰写本文时，在 Flickr.com 上搜索关键词“罗马”或“罗马”会得到超过 270 万张图片。我们的目标是能够在 24 小时内从这些照片中重建出尽可能多的城市。目前，我们的系统与这个目标相差一个数量级。我们相信我们目前的方法可以扩展到这个规模的问题。然而，仍然存在一些问题需要解决。轨迹生成、骨架集和重建算法都在连通分量的水平上操作。这意味着最大的几个组件完全主导了这些阶段。目前，我们的重建算法只在解决束调整问题时利用多线程。虽然这有所帮助，但对于问题来说，这不是可扩展的解决方案，因为根据匹配图的连通性模式，这可能需要过多的时间和内存。我们能够重建这些大规模图像集的关键原因是因为互联网集合中存在大量的冗余，而骨架集算法正是利用了这种冗余。我们目前正在探索三个步骤的并行化方法，特别是在 SfM 系统上的重点。匹配系统的运行时性能在很大程度上取决于验证作业在网络中的分布情况。这是由初始将图像分布在集群节点上的方式来实现的。早期决策是根据用户的名称和图像的 Flickr ID 存储图像，这意味着同一用户拍摄的大多数图像最终会在同一个集群节点上。查看匹配图时，事实证明（事后来看是相当自然的），同一个人拍摄的照片在彼此之间有很高的匹配概率。拍摄照片的人的 ID 只是与这些图像关联的一种元数据。更复杂的策略将利用与图像相关的所有文本标签和地理标签，预测可能匹配的图像，并相应地分发数据。最后，我们的系统是针对批处理操作而设计的。更具挑战性的问题是从我们系统的输出开始，随着可用的图像的增加而添加更多的图像。

致谢¶

本工作部分得到了 SPAWAR、NSF 资助（授予号 IIS0811878）、Office of Naval Research、University of Washington Animation Research Labs 和 Microsoft 的支持。我们还感谢 Microsoft Research 慷慨提供他们的 HPC 集群。作者还要感谢与 Steven Gribble、Aaron Kimball、Drew Steedly 和 David Nister 的讨论。

参考文献¶

References

[1] Amazon Elastic Computer Cloud. http://aws.amazon.com/ec2.

[2] M. Antone and S. Teller. Scalable extrinsic calibration of omni-directional image networks. IJCV, 49(2):143–174, 2002.

[3] S. Arya, D. Mount, N. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. JACM, 45(6):891–923, 1998.

[4] Y. Chen, T. Davis, W. Hager, and S. Rajamanickam. Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate. TOMS, 35(3), 2008.

[5] O. Chum, J. Philbin, J. Sivic, M. Isard, and A. Zisserman. Total recall: Automatic query expansion with a generative feature model for object retrieval. In ICCV, pages 1–8, 2007.

[6] C. Fr ̈ uh and A. Zakhor. An automated method for large-scale, ground-based city model acquisition. IJCV, 60(1):5–24, 2004.

[7] G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SISC, 20(1):359, 1999.

[8] X. Li, C. Wu, C. Zach, S. Lazebnik, and J. Frahm. Modeling and Recognition of Landmark Image Collections Using Iconic Scene Graphs. In ECCV, pages 427–440, 2008.

[9] M. I. A. Lourakis and A. A. Argyros. Sba: A software package for generic sparse bundle adjustment. ACM TOMS, 36(1):1–30, 2009.

[10] D. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91–110, 2004.

[11] D. Nister and H. Stewenius. Scalable recognition with a vocabulary tree. In CVPR, pages 2161–2168, 2006.

[12] M. Pollefeys, D. Nister, J. Frahm, A. Akbarzadeh, P. Mordohai, B. Clipp, C. Engels, D. Gallup, S. Kim, P. Merrell, et al. Detailed real-time urban 3D reconstruction from video. IJCV, 78(2):143–167, 2008.

[13] G. Schindler, M. Brown, and R. Szeliski. City-scale location recognition. In CVPR, pages 1–7, 2007.

[14] I. Simon, N. Snavely, and S. M. Seitz. Scene summarization for online image collections. In ICCV, pages 1–8, 2007.

[15] J. Sivic and A. Zisserman. Video Google: A text retrieval approach to object matching in videos. In ICCV, pages 14701477, 2003.

[16] N. Snavely, S. M. Seitz, and R. Szeliski. Photo Tourism: Exploring photo collections in 3D. TOG, 25(3):835–846, 2006.

[17] N. Snavely, S. M. Seitz, and R. Szeliski. Skeletal graphs for efficient structure from motion. In CVPR, pages 1–8, 2008.

[18] P. Torr and A. Zisserman. Robust computation and parametrization of multiple view relations. In ICCV, pages 727–732, 1998.

[19] B. Triggs, P. McLauchlan, H. R.I, and A. Fitzgibbon. Bundle adjustment - a modern synthesis. In Vision Algorithms’99, pages 298–372, 1999.

[20] A. Vedaldi. Sift++. http://vision.ucla.edu/ ̃vedaldi/code/siftpp/siftpp.html.

[21] L. Zebedin, J. Bauer, K. Karner, and H. Bischof. Fusion of feature- and area-based information for urban buildings modeling from aerial imagery. In ECCV, pages IV: 873–886, 2008.