一种基于大规模无序图像的多起点增量式三维重建方法

技术领域

本发明属于计算机视觉技术领域，具体涉及一种基于大规模无序图像 的多起点增量式三维重建方法。

背景技术

基于计算机视觉技术的三维重建能从二维图像中恢复场景的三维结构， 符合人类认知世界的习惯，具有广泛的应用前景。运用互联网上的现有图 像进行三维重建，可极大地简化三维重建数据采集的步骤，降低了数据采 集的成本，缩短了数据采集的时间但同时具有图像数量大、图像分辨率差 异大、相机标定参数未知、图像场景重叠关系未知的问题。

现有的大规模无序图像集合的场景三维重建采用运动恢复结构 (StructurefromMotion，SFM)的方法，包括图像匹配、初始像对选取、 增量式添加、集束调整(BundleAdjustment，BA)四个步骤；首先进行所 有可能图像对之间的特征匹配，随后进行几何验证，保留满足几何约束的 匹配。若两幅图像之间的匹配数量大于阈值，则认为这两幅图像存在场景 的重叠；在所有图像中寻找两幅具有较多的匹配数量、且具有较宽的基线 长度的图像作为重建的起点，以获得较为精确的初始三维结构；从剩下的 图像中选出一个与当前重建结果有最多重叠部分的图像，加入当前模型。 新加入图像的姿态参数由n点透视(Perspective-n-Point，PnP)算法求 出，并依据其参数引入新的三维点。如果一个图像已经被加入当前模型并 且已估到其参数，则这幅图像被称作已经标定的图像。为了避免每次加入 新的图像导致误差的累积，每加入若干幅图像之后利用BA算法进行一次全 局参数优化；以上过程不断重复直到没有新的图像可以加入重建过程。

若在添加过程中剩余所有的图像和已经标定的图像之间的匹配数量都 很少，SFM认为剩余图像和已重建模型不存在场景重叠，因此新加入的图 像参数无法被估计，重建过程将被中断；SFM只能得到部分场景的重建结 果，大部分未被标定的图片被浪费；另外，若新加入的图像与现有重建结 果之间的匹配数量不多，但足够估计相机的姿态参数，虽然重建过程不会 中断，但经过少量匹配估计的相机姿态可能不准确，而且可能会导致其后 加入的图像姿态有较严重的误差。由于从互联网获取的图像的拍摄视点不 受限制，图像之间的重叠关系无法预知，上述问题发生的概率较大。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种基于大规模 无序图像的多起点增量式三维重建方法，其目的在于解决由单一起点开始 重建导致的中断、相机姿态估计不准确和误差累积的问题。

为实现上述目的，按照本发明的一个方面，提供了一种基于大规模无 序图像的多起点增量式三维重建方法，具体包括以下步骤：

(1)从大规模无序图像集合中提取图像特征点，通过特征点匹配获取 图像之间的特征匹配点对；并根据匹配点对获得图像之间的重叠关系；根 据图像之间的重叠关系生成匹配关系图；

(2)根据图像间的相似度对匹配关系图上的节点进行聚类，获得初始 聚类，每一个初始聚类对应一个初始聚类中心；根据初始聚类中心的密度 进行筛选，获取有效聚类中心，将有效聚类中心作为初始重建起点，并采 用迭代漂移的方法对初始重建起点进行优化，获得重建起点；

(3)边界检测：采用基于分层最短路径的边界检测方法，确定每个图 像采用的重建子过程；

边界检测的步骤，是在多个对场景进行三维重建的重建子过程中，确 定各图像应该由哪个重建子过程来重建；在确定一副图像应该由哪个重建 子过程进行重建时，要求重建子过程的起点图像和该图像存在直接场景重 叠，或者二者虽然不存在直接场景重叠，但可以由一系列中间图像传递场 景重叠关系；

对于重建子过程的起点图像与该图像存在直接场景重叠的情况，这两 幅图像之间的场景重叠应该尽可能大，反映在匹配关系图上就是两个节点 之间的边具有较小的权值；

对于重建子过程的起点图像与该图像不存在直接场景重叠的情况，起 传递作用的中间图像之间应具有较大且均匀的场景重叠，反映在匹配关系 图上就是某个节点到起点之间存在路径，且路径上每一条边的权值尽可能 的小，路径上所有边的权值相似度最高；

(4)多起点三维重建；基于步骤(2)所获得的多个重建起点，采用 步骤(3)确定的重建子过程，分别从这些重建起点开始，同时采用增量式 重建方法对整个场景进行重建，获得多个三维子模型；

每个重建起点对应一个重建子过程，每个重建子过程只重建其边界范 围内的图像；

(5)模型拼接：将相互存在重叠的三维子模型进行拼接，获得完整的 三维模型。

优选地，上述基于大规模无序图像的多起点增量式三维重建方法，其 步骤(1)具体包括如下子步骤：

(1.1)对于包含N幅图像的大规模无序图像集合，生成N个节点，每 个节点对应图像集合中的一幅图像；其中，N为大于1的整数；

(1.2)提取大规模无序图像集合中所有图像的特征点，并对任意不同 的两幅图像进行特征点匹配，找到两幅图像之间的匹配点对；

(1.3)对匹配点对进行几何关系验证，剔除不满足极线几何约束的错 误匹配点对；若两幅图像之间满足极线几何约束的匹配点对的数量大于第 一阈值则表明这两幅图像之间存在场景重叠，给这两幅图像对应的节点 之间添加一条无向带权的边；

(1.4)由一组节点和一组无向带权的边构成图像集合的匹配关系图G； 匹配关系图G用于描述图像之间场景重叠关系；边的权值越小，表明图像的 场景重叠程度越大。

优选地，上述基于大规模无序图像的多起点增量式三维重建方法，其 步骤(2)具体包括如下子步骤：

(2.1)对图像之间的相似度进行量化，获得图像间的相似度矩阵S； 利用该相似度矩阵S和自适应聚类算法对匹配关系图G上的节点进行初始 聚类，每个初始聚类对应于一个初始聚类中心；

(2.2)获取每一个初始聚类中心的密度，剔除密度小于第二阈值α的 聚类中心；将剩下的聚类中心作为有效聚类中心；

聚类中心的密度用匹配关系图上到该聚类中心距离小于第三阈值d₁的 节点的数量来表示；

在本发明中，匹配关系图上两个节点的距离是节点之间最短路径的长 度；若最短路径不存在，则两个节点之间的距离为无穷大；

(2.3)将有效聚类中心作为初始重建起点，采用迭代漂移的方法对初 始重建起点进行优化；

(2.4)重复步骤(2.3)，对每个有效聚类中心进行优化，获得迭代漂 移收敛后的新节点；

迭代漂移具有合并分布较近的有效聚类中心的功能；在迭代漂移过程 中，若多个聚类中心收敛到同一个节点，则将这些聚类中心合并；合并后 的重建起点数量比初始重建起点少很多，从而避免三维场景被过分割成太 多细小的碎片。

优选地，上述基于大规模无序图像的多起点增量式三维重建方法，其 步骤(2.3)具体包括如下子步骤：

(2.3.1)对一个有效聚类中心c，获取其在匹配关系图上的邻域内所有 节点作为重建起点的置信度，从中选出置信度最大的节点

其中，c的邻域是指在匹配关系图上到c的距离小于第四阈值d₂的所有 节点；

(2.3.2)步骤重复(2.3.1)，在的邻域内寻找新的置信度最大的节点， 并用该节点替换直到两次迭代取得的值相等，停止迭代漂移。

优选的，上述步骤(3)，具体包括如下子步骤：

(3.1)统计匹配关系图上所有边权值的范围，获得边权值的最小值a与 最大值b；将权值取值范围划分成L等份，每一份的长度为

(3.2)根据层级参数θ_l，构建(L+1)层匹配关系图；所述层级参数 θ_l＝l*Δ+a；其中，l＝0,...,L；

其中，第l层匹配关系图G_l是一个包含N个节点的图，每个节点对应于 一幅图像；第l层匹配关系图G_l中仅仅包含原匹配关系图G中权值小于层级 参数θ_l的边，即第l层的图上的所有边的权值均小于该层的层级参数θ_l；随 着l的增加，G_l中所包含的边的数量增加，在图上存在连通路径的节点的数 量增加，边的权重的均值和方差增加；当l＝L时，G_L＝G；

(3.3)获取第l层匹配关系图G_l中各节点到所有起点之间的最短路径； 判断最短路径是否存在，若是，则该节点所对应的图像由最短路径长度最 短的起点所对应的重建子过程重建；若否，则在该层对该节点不做任何处 理；

遍历l直到l＝L，获得每个图像采用的重建子过程；

若一个节点在较低层找到最优重建子过程，则在更高的层不再对该节 点进行寻找最优重建子过程的处理；若一个节点在当前层到任何一个起点 都不存在最短路径，则在下一层继续对其进行处理；

按照基于分层最短路径的边界检测方法，一个节点如果在某一层找到 了到某个起点的最短路径，那么它在更高的层中仍然会找到这个起点的最 短路径，因为更高层的图包含更多的边；位于较低层的最短路径具有如下 两个优点：1)路径上每条边的权值比较小；2)路径上所有边的权值差异 比较小，这恰好满足选择最佳重建子过程的要求。

优选地，上述基于大规模无序图像的多起点增量式三维重建方法，其 步骤(4)具体包括如下子步骤：

(4.1)在图像集合中选取两幅起始图像，根据这两幅起始图像之间的 匹配计算相机的参数和稀疏三维点云，作为初始三维子模型；

(4.2)将图像集合中的其他图像加入，并计算这些图像对应的相机姿 态和稀疏三维点云，更新三维子模型；

(4.3)用集束调整算法对上述步骤(4.2)获得的三维子模型进行全 局优化，使得三维点云在所有图像上的重投影误差最小；

与现有技术不同的是，在选两幅起始图像时，起点所对应的图像固定 作为第一幅图像，然后从其它图像中选择具有较多匹配和较宽基线的图像 作为第二幅图像；多个重建子过程可以并行处理以提高重建效率；

多个重建子过程获得的三维子模型相互独立，分别描述了场景的一个 局部；

优选地，上述基于大规模无序图像的多起点增量式三维重建方法，其 步骤(5)具体包括如下子步骤：

(5.1)根据三维子模型所包含的公共三维点的数量，判断三维子模型 之间是否存在重叠关系，若是，则进入步骤(5.2)；若否，则不做任何操 作；

子模型之间的公共三维点越多，则三维子模型相互重叠越大；

(5.2)确定一组有重叠的三维子模型的拼接顺序；根据以下方法确定 一组有重叠的子模型的拼接顺序：

(a)包含三维点数量少的三维子模型向包含三维点数量多的三维子模 型拼接；

(b)若一个含三维点数量少的三维子模型同时与多个三维子模型存在 公共三维点，则将其向包含公共三维点数量最多的三维子模型拼接；

(c)如果两个三维子模型之间存在场景重叠，则根据所述两个三维子 模型的公共三维点，采用鲁棒的最小二乘法估计三维空间的相似变换对所 述两个三维子模型进行拼接。

优选的，步骤(1)中的第一阈值为20。

优选地，边的权值w(i,j)按照如下方式获取：

w(i,j)＝1-s(i,j)

其中，|F_i∩F_j|表示图像i和图像j之间公共的匹配特征点的 个数，|F_i∪F_j|表示表示图像i和图像j上与其它图像匹配的特征点的总个数； 权值w(i,j)位于区间[0,1]内，其大小反映了两幅图像之间重叠程度：权值越 大则重叠程度越小，权值越小则重叠程度越大；

图像集合中的图像具有不同的分辨率和纹理信息；分辨率高的图像对 比分辨率低的图像对之间拥有更多的匹配；纹理信息丰富的图像对之间会 比纹理信息弱的图像对之间拥有更多的匹配；如果使用匹配点数量来衡量 场景的重叠程度，会受上述因素的影响产生误差；采用上述方法获取边的 权值，能有效抵消由不同图象分辨率和纹理带来的差异。

优选地，步骤(2)中对图像之间的相似度进行量化，根据获得图像间的相似度矩阵S；利用该相似度矩阵S和自适应聚类算法对匹配 关系图上的节点进行初始聚类，获得聚类中心；其中，|F_i∩F_j|表示图像i和 图像j之间公共的匹配特征点的个数，|F_i∪F_j|表示表示图像i和图像j上与 其它图像匹配的特征点的总个数。

优选地，一个节点v作为重建起点的置信度c(v)根据以下方法获得：

c(v)＝c₁+c₂-c₃

其中，c₁是指节点v在匹配关系图上的度，c₂表示节点v的邻域N(v)内所 有节点在匹配关系图上的平均度，c₃表示节点v与其邻域N(v)内所有节点之 间边的权值的平均值；

第一项c₁反映了与v所代表的图像有场景重叠的图像的个数；第二项c₂反映了与v所代表的图像虽然没有场景重叠，但能通过中间图像建立场景重 叠的图像的个数；第三项c₃表示v所代表的图像跟与其有场景重叠的图像的 重叠程度；置信度c(v)越高，表明与节点v存在较大的场景重叠的图像越多， 节点v有更强的潜力把三维结构向周围空间进行传播，越适合作为重建起点。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够 取得下列有益效果：

(1)本发明提供的基于大规模无序图像的多起点增量式三维重建方法， 其中，大规模是指所处理的图像数量的量级在10的3次方以上；该三维重 建方法能自适应地从大规模图像集合中选取多个起点同时对整个场景进行 三维重建；当匹配关系图只包含一个连通分量时，本发明方法能获得和传 统单一起点方法相同的效果；当匹配关系图包含多个不连通或者弱连通的 子图时，本发明的方法相比传统单一起点方法在重建效率、精度和完整度 上都有很大改善，可用于对大尺度场景如社区、校园、景点、城市的三维 建模；

(2)本发明提供的基于大规模无序图像的多起点增量式三维重建方法， 由于多个不同的重建子过程可以并行处理，解决了传统增量式重建耗时的 问题，很大程度上提高了三维重建的性能；

(3)本发明提供的基于大规模无序图像的多起点增量式三维重建方法， 根据基于分层最短路径的边界检测方法，从一个图像的所有重建子过程中 选择一个重叠程度最高的对其进行重建，解决了由于较少的场景重叠导致 的相机姿态估计不准确的问题；而现有技术采用的单一起点重建方法，若 在重建过程中加入了一幅与当前重建模型重叠程度比较小的图像，则该图 像对应的相机姿态估计可能存在较大的误差；与现有技术相比，本发明提 供的这种三维重建方法提高了对相机姿态估计的准确度；

(4)本发明提供的基于大规模无序图像的多起点增量式三维重建方法， 由于每个重建子过程只负责重建其起点附近的图像，避免了传统的单一起 点重建方法中需要重建和起点距离很远的图像，因此解决了长距离增量式 重建导致的误差累积问题；

(5)本发明提供的基于大规模无序图像的多起点增量式三维重建方法， 在每个独立场景中分别选择重建起点，并对其分别进行重建，得到每个独 立场景的三维子模型，解决了在场景不连续时模型不完整的问题；当图像 集合包含多个互相不重叠的独立场景时，现有技术的单一起点重建方法会 因为缺乏场景重叠无法添加新的图像而中断；本发明解决了现有技术由单 一起点开始重建导致的中断问题，提高了模型的完整度。

附图说明

图1是本发明提供的大规模无序图像三维重建方法的流程图；

图2为实施例中匹配关系图与重建起点的示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图 及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体 实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的 本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可 以相互组合。

图1所示，是本发明提供的基于大规模无序图像的多起点增量式三维 重建方法的流程图；从输入的大规模无序图像集合中恢复场景的三维信息， 包括经过图像匹配关系图构建、起点选择、分层最短路径边界检测、多起 点三维重建、重叠检测与模型拼接的步骤；结合实施例具体阐述如下：

(1)数据准备；

在具体实施例中，用户根据需要重建的目标场景的关键词从互联网上 搜集图像，获取大规模无序图像集合；

(2)图像匹配和匹配关系图构建：从大规模无序图像集合中提取图像 特征点，通过特征点匹配获取图像之间的匹配点对；并根据特征匹配点对 判断图像之间的重叠关系；根据图像之间的重叠关系生成匹配关系图；

本发明采用匹配关系图G这一数据结构来描述任意两幅图像之间的场 景重叠关系；对于一个包含N幅图像的大规模无序图像集合，其图像匹配 和匹配关系图构建的过程，具体包含以下步骤：

(2.1)从每幅图像上提取图像特征点，计算这些特征点的特征描述符， 并对任意两幅不同的图像进行图像特征匹配，获得两幅图像之间的匹配点 对；其中，图像特征点提取和匹配算法采用尺度不变特征变换(Scale InvariantFeatureTransform，SIFT)算法；

(2.2)对任意两幅图像之间的特征匹配进行几何验证，剔除不满足几 何约束的错误匹配；其中，采用随机抽样一致(RANdomSAmpleConsensus， RANSAC)算法鲁棒地估计两幅图像之间的基础矩阵(如果相机内参数已 知，可以估计本质矩阵)，剔除不满足基础矩阵约束的错误匹配；

(2.3)构建匹配关系图；

根据大规模无序图像集合中图像的个数N，生成一组节点，每个节点 对应于大规模无序图像集合中的一幅图像；

(2.3.1)判断两幅图像之间满足极线几何约束的匹配点对数量是否大 于第一阈值若是，则表明该两幅图像之间存在场景重叠，在这两幅图像 对应的节点之间添加一条边；

若否，则这两幅图像对应的节点之间不添加边；本实施例中，第一阈 值取20；

(2.3.2)根据w(i,j)＝1-s(i,j)，获取边的权值w(i,j)；

其中，|F_i∩F_j|表示图像i和图像j之间公共的匹配特征点的 个数，|F_i∪F_j|表示表示图像i和图像j上与其它图像匹配的特征点的总个数； 权值w(i,j)位于区间[0,1]内，其大小反映了两幅图像之间重叠程度：权值越 大则重叠程度越小，权值越小则重叠程度越大；

若边的权值w(i,j)＝0，则表示图像i和图像j包含了完全相同的场景；若 w(i,j)＝1，则表明图像i和图像j之间不存在场景重叠；由于实施例中，从互 联网下载的图像分辨率差异较大，包含的纹理信息的丰富程度也不尽相同； 分辨率高的图像对比分辨率低的图像对之间拥有更多的匹配；纹理信息丰 富的图像对之间会比纹理信息弱的图像对之间拥有更多的匹配；

如果使用匹配点数量来衡量场景的重叠程度，会受上述因素的影响产 生误差；采用本发明提供的这种方法获取边的权值，能有效抵消由不同图 像分辨率和纹理带来的差异。

在实施例中，从互联网下载的大规模无序图像集合包含2364幅图像， 分辨率在450×600～1600×1200范围内；采用上述步骤，所构建的匹配关系图 G包含2364个节点，45395条边。

(3)根据图像间的相似度对匹配关系图上的节点进行聚类，获得初始 聚类，每个初始聚类对应于一个初始聚类中心；根据初始聚类中心的密度 进行筛选，获取有效聚类中心，将有效聚类中心作为初始重建起点，并采 用迭代漂移的方法对初始重建起点进行优化，获得重建起点；具体如下：

(3.1)采用相似度矩阵对图像之间的相似度进行量化， 利用该相似度矩阵S，采用自适应聚类算法对匹配关系图上的节点进行初始 聚类，获得初始聚类，以及每个初始聚类对应的初始聚类中心；

实施例中，采用近邻传播聚类(AffinityPropagation，AP)算法进 行初始聚类，使用AP聚类算法能够自适应地确定数据聚类的个数，具有更 广泛的应用范围和更强的处理复杂数据的能力；另外，每个聚类中心都是 样本集合中的一个实际样本，而非统计意义上的均值；实施例中，对2364 幅图像经过初始AP聚类获得236个初始聚类；

(3.2)获取每一个初始聚类中心的密度，剔除密度小于第二阈值α的 初始聚类中心；将剩下的聚类中心作为有效聚类中心；

步骤(3.1)所获得的初始聚类中有些初始聚类所包含的样本数量很少， 有些初始聚类所包含的样本点分布较为稀疏，样本之间的相似性较弱；这 些类的中心都不适合用作重建的起点；

实施例中，根据初始聚类中心的密度进行筛选，获得有效聚类中心； 具体地，将密度小于一个第二阈值α的初始聚类中心剔除，将剩下的聚类中 心作为有效聚类中心；

其中，聚类中心的密度用匹配关系图上到该聚类中心距离小于第三阈 值d₁的节点的数量来表示；在本发明中，匹配关系图上两个节点的距离是他 们之间最短路径的长度；若最短路径不存在，则两个节点之间的距离为无 穷大；在实施例中，第三阈值d₁表示统计密度时的局部邻域范围大小，取 值为1.5；

在实施例中，第二阈值α取值为30；第二阈值α指标倾向于选择那些 代表较大的而且较紧凑聚类的聚类中心；实施例中，236个初始聚类中心经 过步骤(3.2)的筛选，获得57个有效聚类中心。

(3.3)采用迭代漂移的方法，优化重建起点；

步骤(3.2)获得的有效聚类中心是数据分布意义上的最优值，但不一 定是重建意义上的最优选择；以下步骤，将有效聚类中心作为初始重建起 点，并利用迭代漂移方法对其进行优化；

对每个有效聚类中心c，采用c(v)＝c₁+c₂-c₃计算其在匹配关系图上的邻 域内所有节点作为重建起点的置信度，从中选出置信度最大的节点

其中，c₁是指节点v在匹配关系图上的度，c₂表示节点v的邻域N(v)内所 有节点在匹配关系图上的平均度，c₃表示节点v与其邻域N(v)内所有节点之 间边的权值的平均值；

其中，c的邻域是指在匹配关系图上到c的距离小于第四阈值d₂的所有 节点；在实施例中，第四阈值d₂表示进行漂移时局部搜索的范围大小，取 值为1.0；

迭代重复，继续在的邻域内寻找新的置信度最大的节点，并用该节点 替换当两次迭代获得的置信度最大的节点相同，表明迭代过程已收敛， 停止迭代漂移；

对每个有效聚类中心都进行上述迭代漂移，获得迭代漂移收敛后的新 的节点；

在本实施例中，上述57个有效的聚类中心作为初始重建起点，经过步 骤(3.3)的迭代漂移优化，获得3个重建起点；图2描述了实施例对应的 匹配关系图与三个重建起点。

(4)采用基于分层最短路径的边界检测方法，确定每个图像所采用的 重建子过程：具体如下：

(4.1)确定层级参数；

统计匹配关系图上所有边权值的范围，得到权值的最小值a和最大值b； 将权值取值范围划分成L等份，每一份的长度为获取一组递增的 层级参数θ_l＝l*Δ+a；其中，l＝0,...,L；

(4.2)构建分层匹配关系图；

根据上述阈值，构建(L+1)层匹配关系图；

其中，第l层匹配关系图G_l是一个包含N个节点的图，每个节点对应于 一幅图像；G_l中仅包含G中权值小于θ_l的边；随着l的增加，G_l中所包含的 边的数量增加，在图上存在连通路径的节点的数量增加，同时，这些边的 权重的均值和方差也增加；当l＝L时，G_L＝G；

(4.3)根据分层最短路径，为节点所对应的图像选择最佳的重建子过 程；

对第l层匹配关系图G_l，获取图中每个节点到所有起点之间的最短路径； 若最短路径存在，则该节点所对应的图像由最短路径中长度最短的路径的 对应起点所对应的重建子过程重建；

若最短路径不存在，则在该层对该节点不做任何处理；从最低层(l＝0) 到最高层(l＝L)，在每一层筛选重建子过程；若一个节点在较低层找到最 优重建子过程，则在更高的层不再对该节点进行处理；若一个节点在当前 层到任何一个起点都不存在最短路径，则在下一层为其选择最佳重建子过 程；

按照上述分层最短路径方法，对于一个节点而言，若在某一层找到了 到某个起点的最短路径，那么它在更高的层中仍可找到这个起点的最短路 径，因为更高层的图包含更多的边；但是，位于较低层的最短路径具有如 下两个优点：1)路径上每条边的权值较小；2)路径上所有边的权值差异 较小；使得三维结构能通过较大并且较均匀的重叠从起点传递到该图像。

(5)基于上述多个重建起点，以及确定的重建子过程，分别从这些重 建起点开始，同时采用增量式重建方法对整个场景进行重建；

(5.1)根据无序图像集合中的两幅起始图像之间的匹配计算相机的参 数和稀疏三维点云，作为初始三维子模型；

(5.2)加入无序图像集合中的剩余图像，并计算它们的相机姿态和对 应的稀疏三维点云，更新三维子模型；

(5.3)采用集束调整算法对三维子模型进行全局优化，使得三维点云 在所有图像上的重投影误差最小；与传统方法不同的是，在选两幅起始图 像时，起点所对应的图像固定作为第一幅图像，然后从其他图像中选择具 有较多匹配和较宽基线的图像作为第二幅图像；多个重建子过程可以并行 处理以提高重建效率；当所有的重建子过程终止以后，获得每个子过程重 建得到的三维子模型。

(6)将相互存在重叠的三维子模型进行拼接，获得完整的三维模型； 多个重建子过程得到的三维子模型是相互独立的分别代表场景中的某个局 部；为了得到统一的场景，需要根据各个三维子模型之间的重叠关系的顺 序变换进行三维子模型拼接；具体如下：

(6.1)根据子模型之间的重叠关系，确定拼接顺序；根据空间的三维 点与图像上的特征点之间的对应关系，判断两个子模型之间是否有公共的 三维点；若两个子模型之间存在公共的三维点，则对其进行拼接；

根据以下方法确定拼接顺序：

包含三维点数量少的子模型总是向包含三维点数量多的子模型拼接；

若一个包含三维点数量少的子模型同时和多个子模型都存在公共三维 点，则将包含三维点数量少的子模型向公共三维点数量最多的三维子模型 拼接；

(6.2)根据公共三维点估计两个子模型之间的变换，对其进行拼接； 在实施例中，该变换模型是相似变换，描述模型在空间中的旋转、平移和 尺度缩放三个方面的差异；由于公共三维点中可能包含噪声，因此采用随 机抽样一致(RANdomSAmpleConsensus，RANSAC)算法估计相似变换；完 成子模型拼接。

(7)输出并保存拼接后的三维点云和相机参数，得到完整的三维模型， 完成三维重建。

在上述实施例中，通过本发明所构思的以上技术方案与现有技术相比， 能够取得下列有益效果：

(1)本发明提供的基于大规模无序图像的多起点增量式三维重建方法， 能自适应地从大规模输入图像集合中选取多个起点同时对整个场景进行三 维重建；当匹配关系图只包含一个连通分量时，本发明方法能获得和传统 单一起点方法相同的效果；当匹配关系图包含多个不连通或者弱连通的子 图时，本发明的方法相比传统单一起点方法在重建效率、精度和完整度上 都有很大改善；

(2)本发明提供的基于大规模无序图像的多起点增量式三维重建方法， 由于多个不同的重建子过程可以并行处理，解决了传统增量式重建耗时的 问题，很大程度上提高了三维重建的性能；

(3)本发明提供的基于大规模无序图像的多起点增量式三维重建方法， 根据基于分层最短路径的边界检测方法，从一个图像的所有重建子过程中 选择一个重叠程度最高的对其进行重建，解决了由于较少的场景重叠导致 的相机姿态估计不准确的问题；而现有技术采用的单一起点重建方法，若 在重建过程中加入了一幅与当前重建模型重叠程度比较小的图像，则该图 像对应的相机姿态估计可能存在较大的误差；与现有技术相比，本发明提 供的这种三维重建方法提高了对相机姿态估计的准确度；

(4)本发明提供的基于大规模无序图像的多起点增量式三维重建方法， 由于每个重建子过程只负责重建其起点附近的图像，避免了传统的单一起 点重建方法中需要重建和起点距离很远的图像，因此解决了长距离增量式 重建导致的误差累积问题；

(5)本发明提供的基于大规模无序图像的多起点增量式三维重建方法， 在每个独立场景中分别选择重建起点，并对其分别进行重建，得到每个独 立场景的三维子模型，解决了在场景不连续时模型不完整的问题；当图像 集合包含多个互相不重叠的独立场景时，现有技术的单一起点重建方法会 因为缺乏场景重叠无法添加新的图像而中断；本发明解决了现有技术由单 一起点开始重建导致的中断问题，提高了模型的完整度。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已， 并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等 同替换和改进等，均应包含在本发明的保护范围之内。