有个很常见的英文谚语：Rome was not built in a day. 译作：罗马不是一天建成的。
背景
传说特洛亚王子的后裔公主来茜西尔维娅被战神马尔斯所幸,生下了孪生兄弟罗马路斯和莱谟斯.当时的国王知道后杀死了他们的母亲,并把兄弟俩装进篮筐,扔进波涛翻滚的台伯尔河.是一只母狼救了他们,并用自己的乳汁哺育了兄弟两人.后来兄弟俩长大成人,为了替母亲报仇,他们想法杀死了国王,这两个天赋异禀的狼养大的孩子一夜之间建造了罗马城.
实际上,原文的意思是“罗马不是在一个白天建成的”,not “in a day”,应该是在晚上“in a night”.
后来,随着时间的推移,这句话的意思慢慢转变,由于古罗马城建筑先进、繁复、建筑技术高超、设计精湛,后人用“罗马不是一天建成的”,表示很多先进技术、物质文明、甚至一个成就,都不是简单达成的,而是经由很多人、或者很多努力,才能够完成的.
摘自网络
2009年，S. Agarwal, Y. Furukawa和N. Snavely在ICCV上发表了题为「Building rome in a day.」的论文（10.1109/ICCV.2009.5459148），利用15万张来自网络的图片进行三维重建工作，真实地还原出了一个数字化版本的罗马城。时隔多年，计算机的计算力和网络数据量都发生了显著变化，甚至有使用上百万张图片进行三维重建的例子出现（10.1109/CVPR.2015.7298949），但这并不影响S. Agarwal等人工作的经典地位（按照Google的统计，该论文已被引用上千次）。
通篇读下来后，目前还有不少细节没能真正理解，因此带着记笔记的心态梳理一下整篇论文的脉络，加深对大型三维重建系统的理解。
引入
问题
城市规模的三维重建系统已有研究先例和实际应用，比如Google Earth/Microsoft’s Virtual Earth。然而，目前这些系统使用的图片数据集均是结构化的：使用参数已知的相机，沿一定的拍摄轨迹（航拍或路面全景相机），得到清晰度一致的、按照一定顺序排列的图片集合。这些条件极大简化了重建工作的计算量。
然而，这样结构化的数据一方面不易获取，另一方面规模非常小。而互联网上的数据规模就庞大很多——它们是不同用户采用不同相机在不同光照条件下拍摄出的不同视角和清晰度的图片——虽然不便于直接使用，但更易获取、更有价值，因为这些照片通常都是人们感兴趣的景物：建筑结构、室内场景、喷泉、雕塑、绘画等。此外，因为不保证这些照片能够覆盖场景所有表面，还需补充若干「假想图片」。
目标
- 分而治之：提高系统的并行程度，突破串行计算的瓶颈。
- 张弛有度：当问题规模扩大、计算力增长时，模型依然适用，问题依然可解。
结果
在重建工作的每个阶段都尝试了若干流行的方法，有些直接迁移了他人工作，有些需要自己开发。最后他们使用500个计算单元，一天内高精度重建15万张图片构成的数据集。（500个计算单元的租用总费用为5000$/天，以2009年的计算力和对应价格的水平，这个项目真的很烧钱…）
系统设计
这部分算是整篇论文的核心，故篇幅较长。
整个系统运行在若干个计算节点上，其中一个节点作为主节点，主节点负责任务调度和决策。整个管线的设计如下图所示：
下面介绍每一步的详细内容。
预处理和特征提取
图片来源：利用爬虫从互联网的图片库获取。
获取的过程中，需要保证每个计算节点负载平衡。
预处理：验证每张图片可读、有效->提取EXIF标签（如果有），获得焦距->对像素点多于2M的图片进行下采样（降低分辨率，保留长宽比，缩放焦距）->利用Andrea Vedaldi等人的现有系统[1]提取SIFT特征->将整个图像集合划分为若干不相交的子集，同对应SIFT特征一起放入计算节点。
EXIF标签：可以理解为图片文件格式头部的记录信息，包括快门、光圈、白平衡、感光度、焦距等。
图像匹配
匹配两幅图像时的关键计算任务主要有：
- 兴趣点的光度匹配
- 这些匹配进行几何验证
通过枚举来比较两个图像中的特征是一件十分困难的事（原文写的prohibitively expensive..可以理解成比登天还难），这就需要用到近似最近点对(ANN, Approximate Nearest Neighbor)搜索。对于任意一对图像，先将其中一幅图像的特征放入k-d树[2]，将另一幅图像的特征作为查询指令。对每一次查找，考虑k=2的情况即可（即找到欧式距离最近的两个特征点）。查找采用优先队列，最大访问次数200。在实验中，这种方法在计算复杂度和匹配准确度之间起到了一个很好的平衡。
接下来用基于RANSAC的估计方法[3]对匹配结果进行剪枝和验证。
上述操作构成了图像匹配过程中的计算核心。
即便上述优化看上去已经无可挑剔，但对于大规模图像集合的匹配而言仍显得力不从心（例如，对于10万张图片的数据集，两两组合就有50亿种）。即使从理论上而言，我们需要将图片进行两两匹配，但实际上大多数图片之间是不匹配的，因此需要仔细筛选出真正可能匹配的图片集合，并放入计算单元中。
我们采用多阶段匹配策略，每个阶段均采用假设-验证两步走的方式。假设部分采用词汇树方法来估计图片相似度，并在验证后扩大搜索。假设和验证的详细方法在下文描述。
词汇树假设
词汇树（Vocabulary Tree）起初是文本检索领域的方法，研究人员发现迁移到图像处理方面仍然适用。这种方法将图像化为词袋模型（bag of words,BoW），「word」是量化后的图像中的特征。
基于这种模型，运用分级k-means树来量化特征描述子（k-means是一种常见的聚类算法，可参考[4]），量化后形成一幅图像的词频（term frequency,TF）向量，对于一个集合内的图片生成对应的文档频率(document frequency, DF)向量。每个计算节点求得自己的TF向量和DF向量后化为TFIDF矩阵，通过网络广播至其他节点，同时接收其他节点广播的矩阵，与自己的TFIDF矩阵作内积。对每一幅图像，找出与之最匹配的$k_1+k_2$幅图像，其中$k_1$幅图像用于第一次验证步骤，$k_2$幅图像用于扩大搜索。
验证与详细匹配
接下来是验证候选图片的匹配，并找到匹配的图像集合。由于我们的系统为分布式计算结构，则在一个节点上计算图像i和j的匹配度可能需要从另外两个节点获取图像i和j的信息，这是很不好的策略：一方面给三个节点施加了任务，另一方面网络传输速度远低于本地计算速度。因此我们需要尽量减少网络传输的次数。
研究人员尝试了三种方法，获得了一些意外的收获。
- 优化网络传输
主节点负责任务调度，为需要进行验证的图像建立连通图，运用[5]中的MeTis系统将图划分成小区域，区域数目与计算节点数目等同。将这些子图交付每个计算节点进行计算。
这个算法对于小规模问题十分有效，但规模逐步扩大后，性能下降很快：由于不同节点的任务完成时间不一样，导致资源未能有效利用。
- 细化分割
将上述算法变形，使分割粒度更细，保证负载均衡。
困难在于，高效地分割和组合本身成为了瓶颈。
- 贪婪装箱算法(Greedy bin-packing algorithm)
这是系统中最后决定采用的方法，每个箱子代表计算单元的任务量。
主节点保存每个节点图像的列表（可以看成索引），当一个节点需要工作时，主节点扫描待工作节点的列表，找到可以匹配的图像对，将图像对加入箱子，直到箱子满或没有能够加入的图像对。接下来选择一个图像传输给该节点，同时扩大箱子容积，直到所有图像匹配完毕。
ps.这一部分感觉没有理解到核心，放个原文
The master node maintains a list of images on each node. When a node asks for work, it runs through the list of available image pairs, adding them to the bin if they do not require any network transfers, until either the bin is full or there are no more image pairs to add. It then chooses an image (list of feature vectors) to transfer to the node, selecting the image that will allow it to add the maximum number of image pairs to the bin, This process is repeated until the bin is full.
匹配完成后验证，主要分两步：光度一致性和相机校准信息。
匹配图的生成到骨架集算法的过程如下图所示：
下文详述。
子图连通
首先定义一个概念：匹配图（Match graph，为了不和「图像」的概念混淆，本段将其简称为G，子图简称为subG）。G中的一个点对应一幅图像，两点之间的边代表这两幅图像存在能够匹配的特征点。在第一遍匹配完成后，通常会得到若干不相连通的subG。在前文「词汇树假设」阶段，我们提到了用$k_1+k_2$幅图像作为候选，其中$k_1$幅图像已在前文用到，剩下的$k_2$幅就要用在这里了。
对每个点数大于等于2的subG，我们对其中每幅图像用$k_2$个候选图像进行匹配测试。因此，与$k_1$幅候选图像没有任何匹配的点（也就是图中孤立的点），会在这个阶段被舍弃。而在$k_1$幅图像中有匹配的点，则会在这个阶段进行扩展，并可能与其他子图连通，构成更大的子图。
扩展查询
在经过$k_1$和$k_2$两轮匹配后，匹配图仍然比较稀疏，还不能很好地用于重建三维场景。为了弥补这一点，我们使用来自文本检索领域的方法——扩展查询（query expansion）。
简单的说就是，如果图像$i$和$j$匹配（即在图G中存在相连的边），图像$j$和图像$k$匹配，则检测图像$i$和$k$的匹配度，在匹配的情况下连接边$i-k$。
轨迹生成
匹配处理中的最后一步就是合并所有匹配信息，在图像之间生成一致的轨迹。由于图像的特征和匹配情况分布地存储在各个计算节点上，轨迹生成需要如下两个步骤：
- 每个计算节点处理局部匹配轨迹
- 主节点获取其他计算节点的轨迹结果，通过广播分配全局任务
轨迹生成后需要提取特征点的二维坐标和颜色信息。
几何估计
接下来根据匹配情况生成相机位置和特征点的3D坐标。
大部分处理无序图片几何估计的系统都是增量式（incremental）的，即从一个小规模重建开始，逐渐迭代，并进行光束法平差(bundle adjustment，等价于执行非线性最小二乘优化)，直到加入所有相机。由于本系统规模较大，采用增量式方法会相当缓慢。
增量式方法通常会基于这种假设：所有图像对于重建的地位等同。这对于按照一定规律采集的图片而言比较正确，但对于大量来自互联网的图片就另当别论了。由于后者冗余性较大，将每幅图片都视为等价显然不合理，因此我们需要找到一个最小的子集来开展重建。
寻找最小子集的方法选用骨架集算法(Skeletal Sets Algorithm)[5]，大意是从G中找出那些对于整个图的连通性影响最大的点集。
光束法平差
直接参考[6]，相对底层的东西目前还没有深挖。
分布式计算引擎
该系统的基础是一个分布式计算引擎。
优点：内核小，易移植，跨平台的，可扩展。
实验数据
计算节点参数：1GB/s以太网接口，32GB RAM，1TB硬盘，Win2008 64位操作系统。
设置$k_1 = 10$,$k_2 = 10$.
执行四轮扩展查询。
匹配和重建数据：
部分重建结果（更加完整的重建可访问[7]）：
讨论
- 系统中光束法平差的计算已经可以做到针对问题规模对并行化程度合理缩放，但是轨迹生成、骨架集算法和重建算法都是在连通图的基础上进行的，这就导致无法进行深层次的并行化计算。
- 另一个明显的问题是数据集的冗余。
- 匹配系统的运行时间主要取决于验证工作在网络中的分布情况。
参考资料
[1] http://vision.ucla.edu/~vedaldi/code/siftpp.html
[2] http://111qqz.com/2017/10/kd-tree-%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/
[3] http://blog.csdn.net/u013339596/article/details/18797667
[4] http://111qqz.com/2017/08/k-means-clustering-%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/
[5] http://www.cs.cornell.edu/~snavely/projects/skeletalset/SkeletalSets_cvpr08.pdf
[6] http://blog.csdn.net/OptSolution/article/details/64442962
[7] http://grail.cs.washington.edu/rome/
后记
这篇论文从读到整理前后大概用了3天，还有若干细节问题没有完全理解：
- Bundle Adjustment
- Skeletal Sets Algorithm
- RANSAC
- …
以及，这个工作其实还有不少需要完善的地方：一开始我以为所谓的重建罗马是指整个城市，但系统最终的效果表明只有照片多的地方才有比较好的效果（比如风景名胜、经典建筑等）。此外，按照我上一篇系统调研的博文来看，只完成了整个重建工作的第一个步骤——稀疏点云重建，后续还有密集点云重建、表面重建和纹理映射，
虽然有不少细节没能完全理解，但这篇论文整体思路可以说是非常清晰明确了，还描述了一些试错和调研的过程，对后续科研工作者而言有不少启发。