admin管理员组

文章数量:817300

一天建成罗马

研0狗没见过论文,看论文只好一句句翻译出来看看,不然就忘了前句说过什么。翻译水平有限,欢迎大佬们指正。

摘要

我们提出了一个系统,这个系统从极大的图片库里相互匹配并重建了一个三维场景。比如,这些图片来自网上图片分享网站,是一个已给定的城市,比如罗马。我们的系统使用新颖的并行分布式匹配和重构算法,用来最大化在每个阶段的并行性、减少序列化瓶颈。它被设计来使用问题的规模和可用的计算量。我们已经在每个阶段试验了多个可选的算法然后报告出哪个工作在并行计算环境下表现最好。实验结果表明,其现在可以在500个计算机核心的情况下能在一天时间内可能用15万张图片重建城市。

1.介绍

在flickr.com网站上搜索项-罗马,将得到超过两百万张图片。这个规模表示一个越来越完整的摄影记录,捕获了这座城市每一个受欢迎的地方,外部,内部,喷泉,雕塑,绘画,咖啡馆等。这些图片的大多数都从成百上千的视点和显示条件得到的—单特莱维喷泉在网站上就有超过5万张图片。[16,17,8]以相同规模的图片重建单个建筑已经取得了较大的突破,表明SfM算法的应用潜力在非结构化的图片多大数千个照片。这篇论文表明从数千张图片重建城市化规模的可行性。我们现在的模型是一个到两个数量级的模型 比文献中所报告的下一个最大的结果要大。 此外,我们的系统还能重建数据 在不到一天的时间内拍摄15万张照片。
城市规模的三维重建之前已经在计算机视觉的文献中被讨论过了,现在已经被广泛的应用于谷歌地球以及微软的虚拟地球。然而,现存的大规模的运动系统的结构系统是对来自结构资源的图片进行操作,比如,由一架调查机拍摄的航拍照片,或由移动车辆捕获的街道图像。这些系统以来的图像需要用相同的典型标定相机和常规采样率,或利用其它的传感器,比如GPS,内部导航单元,这极大地简化了计算。
从网络中获取的图像没有这些可供简化的特征。它们是使用各种不同的相机,在不同的显示条件下,在其中几乎没有任何与他们相关的地理信息,而且再很多情况下,没有相机校准信息。这些相似的变异性,让这些照片很难在SfM中起到作用,但也让它们蕴含了很多关于这个世界的信息。特别的是,它们能够捕捉人们感兴趣的东西,比如,值得拍摄的景观,包括,内部装饰,艺术品(比如,雕塑,绘画等等),以及外部的景观。而从这些图片所生成的重建结果并不能做到对场景表面的完整覆盖,随着时间的推移,覆盖率会通过添加航拍或街拍的照片而补充。
我们的系统的主要目标是通过利用大规模并行性,快速完成重建。这个选择是因为当前越来越普遍的像CPU(多核),网络水平(云计算)等并行计算资源所促使的。以如今的价格,你可以用10000美元租1000个结点租一天。
我们的方法的基础是一个针对大规模分布式计算机视觉问题的新系统,我们也将把这个系统发布出来。我们的算法主要是通过现存的大规模的匹配和SfM算法,包括SIFT,词汇树,bundle adjustment,以及其他技术。对于我们算法的每个阶段我们考量几种可供选择的算法,因为某些算法可以分布,但某些不行,那么发布内存使用率以及I/O带宽就变得很关键了。比如在bundle adjustment算法中,我们发现现有的实现并没有成规模,所以我们自己创作了一个高性能的实现。设计一个规模可变得系统是有挑战性的,我们在这条路上发现了许多惊喜。因此,我们的论文的主要贡献在于学习到的观点与教训,以及我们创造的提升并行性和吞吐量的科技创新。
论文的剩余部分组织如下。第二部分讨论了细节设计选择与实现。第三部分汇报了在三种不同城市规模数据集下的实验结果。第四部分得出结论以及对未来工作的导向。

2.系统设计

我们的系统运行在一簇计算机(节点),其中一个是主节点。主节点负责各种任务的调度工作。
在这个单元里,我们描述了我们系统的详细设计,这可以被分成三个不同的阶段:(1)预处理(2)匹配(3)几何估计。

2.1预处理与特征提取

我们假设图像是存储在中央上,它们以对固定尺寸块的要求被分发到集群节点上。其自动执行负载均衡,更强大的节点接受更多的图片。
这是唯一一个需要中央文件服务器的阶段,系统的其他部分并不需要任何共享存储。这样我们就可以从匹配和重建实验的独立互联网上下载图片了。对生产使用,在匹配和重建过程的开始对每一个节点将会从互联网上抓取图片。
在每个节点上,我们通过识别图片是否可读,可用开始。之后我们提取SIFT标签,如果得到了,就记录焦距(focal length)。我们也降低取样那些大于两个像素的图片,保存其外观比率并缩放调整其焦距。我们将会从这张图片中提取SIFT特征并将其转换成灰度图。因为其速度和灵活接口,我们采用Andrea Vedaldi实现的SIFT++。在这个阶段结尾,图片的全部集合将分成不连接的集合,分布在每个节点中。通过这种划分,每个节点都拥有图片和SIFT特征。

表格一 我们的多阶段并行匹配算法。在接下来这些步骤执行后,会有N个输入图片分布在M个运算节点中。(a)SIFT特征提取,词汇树向量定量,词句频率计算。(b)文档频率计算(c)TFIDF计算以及信息预测(d)TF基础匹配可能性的计算(e)主节点的聚合(f)每张图片基于前K1次匹配的匹配识别任务的分布(g)匹配验证,可选的结点特征向量交换(h)匹配建议扩展,每张图片使用接下来最好的前K1次匹配,在连接组件CC中(i)更多的分布式识别(j)比四轮更多的查询拓展和验证(k)踪迹是根据当地的验证匹配结果而分离(l)通过C个连接的组件进行踪迹聚合(m)通过连接组件与分布分离的图片进行最终的踪迹分布

2.2图片匹配

当匹配两张图片的关键计算任务是兴趣点的光度匹配,以及粗略估计基础和重要的矩阵的几何验证。然而在两张图片之间的全部特征的详尽匹配代价昂贵的让人却步,最好的结果可以用近似最邻近搜索得到。我们使用了ANN库来匹配SIFT特征。对每对图片,一张图片的特征被嵌入到一颗K-d树,其他图片的特征则被用来查询。对每次查询,我们考量两个距离最近的邻居点,匹配采用Lowe率。对于搜索方法,我们使用优先级队列,设置访问的最大上限个数为200个。在我们的经历中,这些参数使计算消耗和匹配精准度之间达成了一个很好的平衡。通过近似最邻近搜索返回的匹配结果,使用基本或关键矩阵的RANSAC估计进行验证,其取决于来自EXIF标签的焦距信息的可用性。这两个操作组成了我们的匹配引擎的操作性核心。
不幸的是,即便描述如上的匹配过程被实现的最佳但也无法完成匹配我们语料库中所有对图片的任务。对于一个100000大小的语料库,其将转化为五十亿对比较,这需要500个CPU核心,每个核心每秒处理10对图片的话,这需要11.5天来完成匹配操作。此外,这个过程甚至没有考虑对所有核心传输所有图片的SIFT特征数据所需要的网络传输状况。
尽管我们的确能够完成这些成对的匹配,但这是一种对计算能力的浪费,因为一类占压倒性优势的图片没有匹配。这是期望从一组与宽标签相关联的图像,就像一个城市的名字。因此,我们对系统花费时间进行匹配的图片对要仔细选择。
以上工作建立在有效对象检索的基础上,我们采用多阶段匹配调度。每个阶段由一个提议阶段和验证步骤组成。在提议阶段,系统决定一组能够有共同的常见元素的图片。在验证阶段,对图片进行细节特征匹配。在这个阶段完成的匹配工作将会用在下一个提议阶段中。
在我们的系统中,我们采用两个方法生成提议:基于全部图片相似度的词汇树(2.2.1)和查询拓展(2.2.4)。验证阶段被描述在(2.2.2)。表1显示了系统运行过程中的匹配表格。

2.2.1词汇树提议

从文字检索得出来的方法已经成功应用到图片检索和目标问题。这些方法是通过把图片表示为一些单词,这些单词是通过定量化图片特征得到的。我们使用了一个基于词汇树的方法。
层次结构的K均值树被用来量化表示特征描述符。(模块3里详细描述了我们是怎样使用训练图片的语料库来简历词汇树的)。这些定量把所有特征聚合来获得语料库里图片的TF(词频)向量,和DF(句频)向量,表格1(a-e)。句频向量把结点聚集到一个单维向量里,广播给节点集群。每个节点都规范化词频向量,来获得本结点的TFIDF矩阵。这些结点的TFIDF矩阵都广播给网络,因此每个节点都能计算出其TFIDF向量和剩下的TFIDF向量之间的内积(inner product)。实际上,TFIDF向量本身就是一个分布式的产品,但每个节点只计算和它拥有的图片所对应的行块。对于每张图片,得分前K1+K2高的图片被识别,前K1张图片被用来初始化验证阶段,另外K2张图片被用来扩大连接组件(见下)。
我们的系统不同于 Nister and Stewenius的,因为他们的系统拥有一个固定大小的数据库,用以匹配即将到来的图片。因此他们可以把数据库存储在词汇树本身,然后评估图片的匹配得分。在我们的系统中,查询集就等同于数据库,当特征被编码的时候是不可用的。因此我们必须有一个单独的矩阵乘法阶段来寻找最佳匹配图像。

2.2.2验证和细节匹配

下一步是验证候选图片匹配,然后发现匹配图片之间的详细的匹配集。如果图片被保存在同一个机器,验证被提议的匹配图片的任务就成了一个简单的事情,或许有人会注意到验证过程来最小化磁盘IO的顺序。然而,在我们的系统里,图片以及其特征描述是分布在各个节点的。因此,要求一个结点去匹配图片对(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算法,来为每条踪迹,每台摄影机每个3D位置恢复一个造型。大多数SfM系统对于无序图片集是递增的,开始于一个小型的重建,之后每次增加一些图片,三角形化新点,经过一次或多次非线性最小二乘优化(包适应)来最小化重投影错误。这个过程一直重复到没有摄像机可被添加。然而,因为我们数据集的规模,在所有照片上运行这样一种递增的方法是不现实的。
上面所描述的递归的重建方法,有一个隐含的假设,即所有的图像都或多或少地贡献了覆盖和重建的准确性。互联网图片集,他们天然就是很丰富的—-许多照片都是从邻近点拍的,处理它们并不一定会增加到重建效果里。因此,更倾向于找到并重建一小部分照片,获取到匹配图与几何场景之间的基本连通性。一旦完成,我们就可以在所有剩下的图像中加上姿态评估,三角化所有剩余的点,然后完成最后一束,来重定义SfM评估。
为了找到最小集,我们采用骨架集算法,其计算一组生成的照片,这些照片保存了图片图的重要的连通信息(比如一个大圈)。这是一种双帧重构,其在已知焦距的情况下对每对匹配图像进行计算。在我们的系统中,这些图片对重建被计算为并行匹配过程的一部分。一旦一个骨架集被计算出来,我们就使用递增算法评估每个结果组件的SfM参数。骨架集算法通常断开连接在弱连接上的连接组件边界,来生成更大的组件集。

2.4.1光束法平差

在把SfM算法的规模减少到骨架集以后,在重建过程的主要瓶颈是投影误差的非线性最小化或光束法评差(BA)。当前公共可用的表现最好的BA软件是SBA。其表现最佳的关键在于使用了所谓的舒尔补充技巧,其可以减少线性系统(也被称为标准等式)的规模,其需要在LM算法每次迭代中被解决。这个线性问题的规模主要取决于3D点以及摄像机参数,然而,舒尔补充的规模只取决于摄像机参数。后来,SBA使用密集Cholesky因数分解为各个因数,来解决简化线性系统的问题。因此在经典SfM问题中3D点的数量通常要用两个数量级或者说要比摄像机的数量要大,这也产生了本质上的节省。这适用于小到中等大小的问题,但对于数千张图片的大型问题,计算舒尔补充的密集Cholesky因数分解成为了一个空间和时间上的瓶颈。然而对于大型问题,舒尔补充本身是比较稀少的(一个3D点通常只在少数摄像机可见),利用 这种稀疏会导致大量的时间和空间节省。
我们已经开发了一个高性能的光束法平差软件,其取决于问题的规模,根据问题的规模,在截断和精确LM算法中选一个使用。在第一种情况下,一个块对角线的共轭 采用梯度法求解近似法方程。在第二个情况下,CHOLMOD,一个用来计算Cholesky因数分解的稀疏直接方法被用来经由舒尔补充技巧精准地解决标准式。第一个算法在每次的循环里时间复杂度较低,但是使用更多的LM迭代过程,而第二个算法在每次的循环里需要消耗更多的时间和内存,从而完成更快的收敛。结果代码将会明显比SBA使用更少的内存并以更快的速度运行。精准地运行时间和内存取决于线性问题的稀疏结构

2.5分布式计算引擎

我们的匹配与重建算法被实现为一个两层系统。系统的基层是一个应用程序agonstic分布式计算引擎。除去一个易传输的小的核心,这个系统是跨平台的,能够运行在所有主要的UNIX和微软视窗系统上。这个系统是小型的且可扩展的,虽然它附带了一些调度策略 数据传输原语,用户也可以自由地添加他们自己的。
这个系统是针对处理大量数据的批处理应用程序。它对当地应用数据的缓存以及经由网络按需传输数据有广泛的支持。如果共享文件系统可用,就可以使用,但如果需要取得最佳性能,则要把所有数据存储在本地磁盘,在需要的时候经过网络传输。其支持各种调度任务,从普通数据并行任务到映射规约模式风格计算。这种分布式计算引擎被写作Python脚本的集合,其每个计算阶段都被实现为Python和C++代码的混合体。

3.实验

我们运行了三个城市数据集的:克罗地亚 杜布罗夫尼克,罗马以及意大利的威尼斯。其图片均来自flickr网站,表3(a),3(b),3(c)显示了在这些数据集里面的最大的连接组件的重建。因为考虑到论文空间大小,只有结果的一部分样本被展示在这里,我们建议你们访问下面这个网址 rome,在这里展示出了完整的结果,额外的结果数据,以及代码。
实验跑在62个结点簇上,双四核处理器,个人网络,以太网接口1G/s,每个节点配有32GRAM,1TB本地磁盘,节点操作系统是64位windows2008。
在所有实验中使用相同的词汇树。它从20000张罗马的图片中提取出了1,918101个特征参与训练(没有用在呈现在这里的实验中)。我们训练了一棵具有10个分支因子的树,总共有136,091个顶点。对每张图片,我们使用词汇树来找到前20张匹配图。前K1 = 10次匹配的图被用在首次验证的阶段,接下来k2 =10次匹配被用在第二次组件匹配阶段。四轮查询扩展也被完成。我们发现,所有的情况下,匹配执行的匹配数量的比率将会在四轮后掉下来。table1总结了三个数据集的统计情况。
table1中的重建时序数有一些解释,杜布罗夫尼克的SfM时间令人惊讶,因为比罗马要多得多,而且几乎和威尼斯一样,两者都是更大的数据集。原因可能就在数据集是如何被组织的。罗马和威尼斯的数据集本质上是一组地标,在大规模有简单的几何和可见性结构。另一方面,杜布罗夫尼克中最大的连通组件获得到了整座旧都市。对于狭窄的巷道, 复杂的可见性和不同的视点,这是一个更复杂的重建问题。这反映了和最大连通组件相关的骨架集的规模,正如table2中所反应的那样。正如上文所提到的,骨架集算法通常断开连接在弱连接上的连接组件边界,因此,由匹配系统CC1所返回的连接组件的规模要大于连接组件CC2,这也是骨架集算法所返回的。

4.谈论

在写这篇文章的时候,在flickr网站上搜索关键字,罗马将会返回超过270万张图片。我们的目标是能够在24小时内重建尽可能多的城市。我们当前的系统距离这个目标还差一个数量级。我们相信我们现在的方法是可以扩展到这个规模的问题的,然而仍然存在许多开放式问题。
踪迹生成,骨架集,重建算法,都是在连接组件的级别上运行的。这意味着最大的少数组件将会主宰这些阶段。当前,我们的重建算法在解决光束法平差问题时利用了多线程。虽然有帮助,但这并不是一个针对问题规模可变的算法,因为取决于匹配图的连通模式,其可能会变成一种无节制的时间和空间。我们能够重建这些大图片集的关键原因在于互联网上的丰富的资源,这些是骨架集算法所能够利用的。目前我们正在 探索并行化这三个步骤的方法,特别是SfM系统。
匹配系统的运行时间主要取决于验证工作是否能好好地分布在网络中。这是通过集群节点上的图像的初始分布来实现的。之前想要根据用户名以及图像的Flickr ID来存储图像,这就意味着大多被同一个用户使用的将会结束在同一个集群节点。看匹配图可知(事后),一个用户自己的图片将有很大可能性会匹配到它自己。使用照片的用户的ID只是一种和这些图片相连接的一类元数据。一种更复杂的策略是利用所有的文本标签和图片的地理标记来预测图片有可能匹配什么,然后相应的分布数据。
后来,我们的系统是根据批量操作设计的。一个更具挑战性的问题是,从我们的系统的输出开始,然后随着他们变得可用来添加更多的图像。

感谢

本文标签: 一天建成罗马