一种适用于大规模场景的运动恢复结构方法

摘要

本发明公开了一种适用于大规模场景的运动恢复结构方法，主要包括以下步骤：根据影像匹配结果，计算两两重叠影像间的关联度得分；基于关联度得分，将影像划分为若干个影像分区；利用ISfM方法重建每个影像分区；基于光束法将已完成重建的各个影像分区融合成完整场景。该方法在保证精度的同时具有稳健、效率高且易于分布式并行实现等特点，可适用于包含不同影像规模的多种场景，尤其对于几万甚至几十万张影像的大场景具有很高的稀疏重建效率。

权利要求

1.一种适用于大规模场景的运动恢复结构方法，其特征在于，包括以下步骤：根据影像匹配结果，计算两两重叠影像间的关联度得分,所述计算重叠影像间的关联度得分，具体包括：

基于同名点个数和点位分布计算重叠影像间的关联度得分，其计算公式为：式中， 为影像间的关联度得分；

和 为权重；

为统计像对同名点数量；

、 为左右影像构成的像对中最多的同名点数；

为有效格网内像点的外接矩形面积与像幅面积的比值；

基于关联度得分，将影像划分为若干个影像分区；

利用ISfM方法重建每个影像分区；

基于光束法将已完成重建的各个影像分区融合成完整场景。

2.如权利要求1所述的适用于大规模场景的运动恢复结构方法，其特征在于，所述根据影像匹配结果，计算两两重叠影像间的关联度得分，之前还包括以下步骤：采用SIFT匹配算法，获得影像间的匹配关系。

3.如权利要求1所述的适用于大规模场景的运动恢复结构方法，其特征在于，所述基于关联度得分，将影像划分为若干个影像分区，具体包括以下步骤：对影像进行初次划分，获得第一次分区；

对第一次分区进行合并，获得影像初始分区；

对影像初始分区进行剔除弱连接分区，获得影像分区。

4.如权利要求3所述的适用于大规模场景的运动恢复结构方法，其特征在于，所述对第一次分区进行合并，获得影像初始分区，具体包括：预设影像初始分区内的影像数阈值范围。

5.如权利要求3所述的适用于大规模场景的运动恢复结构方法，其特征在于，所述对影像初始分区进行剔除弱连接分区，获得影像分区，具体包括：将影像初始分区内的弱连接分区剔除，并动态调整弱连接分区内的影像。

6.如权利要求1所述的适用于大规模场景的运动恢复结构方法，其特征在于，所述利用ISfM方法重建每个影像分区，具体包括以下步骤：S310、获得匹配结果；

S320、利用匹配点估计像对的相对位姿并获取初始的结构信息；

S330、利用已知的场景结构、2D‑3D对应关系估计待增加影像的位姿，根据准则和策略选取增加至场景中的影像集；

S340、交会得到新的稀疏结构，增大场景的覆盖范围；

S350、光束法优化场景使得重投影误差和最小；

S360、过滤可能存在的不可靠2D、3D点，剔除准则包括投影误差和交会角；

S370、循环步骤S330‑步骤S360直至场景稀疏重建完成或无法增加更多的影像至场景中为止。

7.如权利要求6所述的适用于大规模场景的运动恢复结构方法，其特征在于，所述根据准则和策略选取增加至场景中的影像集，具体包括以下步骤：S331、利用2D‑3D对应关系，估计存在关联影像的位姿，记录有效像点数量；

S332、选取步骤331中所有有效像点数中值的0.25倍作为阈值，剔除有效点数小于阈值的估计结果，得到待增加的备选影像集；

S333、基于备选影像集和场景中已排列的影像，通过三角测量获得所有可能的3D点，统计备选影像可用于光束法优化的有效像点数量；

S334、选取步骤S333中可用像点数中值的0.5倍作为阈值，大于阈值的影像将被增加至场景中；

S335、剔除不可靠结果。

8.如权利要求7所述的适用于大规模场景的运动恢复结构方法，其特征在于，所述剔除不可靠结果，具体包括以下步骤：统计误差，计算影像分区内有效点位误差的平均值，剔除大于阈值的影像分区；

相机检校参数，剔除同源相机在不同影像分区中异常的检校结果；

成功排列影像的比例；

影像分区间有效的公共地面点，将弱连接影像分区剔除。

9.如权利要求1所述的适用于大规模场景的运动恢复结构方法，其特征在于，所述基于光束法将已完成重建的各个影像分区融合成完整场景，具体包括以下步骤：计算两两影像分区间的空间相似变换参数，统一待合并影像分区的坐标系和比例尺；

确定融合任务列表；

确定融合影像分区的影像位姿和结构信息坐标初值；

利用光束法融合影像分区。

说明书

一种适用于大规模场景的运动恢复结构方法

技术领域

[0001] 本发明涉及运动恢复结构三维建模技术领域，特别涉及一种适用于大规模场景的运动恢复结构方法。

背景技术

[0002] 运动恢复结构（Structure‑from‑Motion，SfM）是通过一组具有重叠的影像恢复相机的姿态同时获得场景三维结构信息的处理过程，用于解决无GPS/POS、无相机检校参数、
无序影像的排列问题，广泛应用于4D产品生产、三维实景建模、虚拟和增强现实、机器人导
航与定位等领域。典型的SfM包括增量式SfM（IncrementalSfM，ISfM）和全局式SfM
（GlobalSfM,GSfM）两种实现形式，前者稳健性高，应用最为广泛，但存在对初始像对选取的
依赖性高、大场景重建效率低、难以分布式并行计算等缺点。

发明内容

[0003] （一）发明目的

[0004] 鉴于上述问题，本发明的目的是提出一种适用于大规模场景的运动恢复结构方案，该方法在保证精度的同时具有稳健、效率高且易于分布式并行实现等特点，可适用于包
含不同影像规模的多种场景，尤其对于几万甚至几十万张影像的大场景具有很高的稀疏重
建效率，本发明公开了以下技术方案。

[0005] （二）技术方案

[0006] 作为本发明的第一方面，本发明公开了一种适用于大规模场景的运动恢复结构方法，包括以下步骤：

[0007] 根据影像匹配结果，计算两两重叠影像间的关联度得分；

[0008] 基于关联度得分，将影像划分为若干个影像分区；

[0009] 利用ISfM方法重建每个影像分区；

[0010] 基于光束法将已完成重建的各个影像分区融合成完整场景。

[0011] 在一种可能的实施方式中，所述根据影像匹配结果，计算两两重叠影像间的关联度得分，之前还包括以下步骤：

[0012] 采用SIFT匹配算法，获得影像间的匹配关系。

[0013] 在一种可能的实施方式中，所述计算重叠影像间的关联度得分，具体包括：

[0014] 基于同名点个数和点位分布计算重叠影像间的关联度得分，其计算公式为：

[0015]

[0016] 式中， 为影像间的关联度得分；

[0017] 和 为权重；

[0018] 为统计像对同名点数量；

[0019] 、 为左右影像构成的像对中最多的同名点数；

[0020] 为有效格网内像点的外接矩形面积与像幅面积的比值。

[0021] 在一种可能的实施方式中，所述基于关联度得分，将影像划分为若干个影像分区，具体包括以下步骤：

[0022] 对影像进行初次划分，获得第一次分区；

[0023] 对第一次分区进行合并，获得影像初始分区；

[0024] 对影像初始分区进行剔除弱连接分区，获得影像分区。

[0025] 在一种可能的实施方式中，所述对第一次分区进行合并，获得影像初始分区，具体包括：

[0026] 预设影像初始分区内的影像数阈值范围。

[0027] 在一种可能的实施方式中，所述对影像初始分区进行剔除弱连接分区，获得影像分区，具体包括：

[0028] 将影像初始分区内的弱连接分区剔除，并动态调整弱连接分区内的影像。

[0029] 在一种可能的实施方式中，所述利用ISfM方法重建每个影像分区，具体包括以下步骤：

[0030] S310、获得匹配结果；

[0031] S320、利用匹配点估计像对的相对位姿并获取初始的结构信息；

[0032] S330、利用已知的场景结构、2D‑3D对应关系估计待增加影像的位姿，根据准则和策略选取增加至场景中的影像集；

[0033] S340、交会得到新的稀疏结构，增大场景的覆盖范围；

[0034] S350、光束法优化场景使得重投影误差和最小；

[0035] S360、过滤可能存在的不可靠2D、3D点，剔除准则包括投影误差和交会角；

[0036] S370、循环步骤S330‑步骤S360直至场景稀疏重建完成或无法增加更多的影像至场景中为止。

[0037] 在一种可能的实施方式中，所述根据准则和策略选取增加至场景中的影像集，具体包括以下步骤：

[0038] S331、利用2D‑3D对应关系，估计存在关联影像的位姿，记录有效像点数量；

[0039] S332、选取步骤331中所有有效像点数中值的0.25倍作为阈值，剔除有效点数小于阈值的估计结果，得到待增加的备选影像集；

[0040] S333、基于备选影像集和场景中已排列的影像，通过三角测量获得所有可能的3D点，统计备选影像可用于光束法优化的有效像点数量；

[0041] S334、选取步骤S333中可用像点数中值的0.5倍作为阈值，大于阈值的影像将被增加至场景中；

[0042] S335、剔除不可靠结果。

[0043] 在一种可能的实施方式中，所述剔除不可靠结果，具体包括以下步骤：

[0044] 统计误差，计算影像分区内有效点位误差的平均值，剔除大于阈值的影像分区；

[0045] 相机检校参数，剔除同源相机在不同影像分区中异常的检校结果；

[0046] 成功排列影像的比例；

[0047] 影像分区间有效的公共地面点，将弱连接影像分区剔除。

[0048] 在一种可能的实施方式中，所述基于光束法将已完成重建的各个影像分区融合成完整场景，具体包括以下步骤：

[0049] 计算两两影像分区间的空间相似变换参数，统一待合并影像分区的坐标系和比例尺；

[0050] 确定融合任务列表；

[0051] 确定融合影像分区的影像位姿和结构信息坐标初值；

[0052] 利用光束法融合影像分区。

[0053] （三）有益效果

[0054] 本发明公开的一种适用于大规模场景的运动恢复结构方法，具有如下有益效果：

[0055] 该方法在保证精度的同时适用于包含不同影像规模的多种场景，尤其具有稳健、效率高且易于分布式并行实现等特点，可用于解决几万甚至几十万张影像大场景的稀疏重
建问题；为了保证重建结果的完整性，将被剔除分区中的影像重新划分至其他分区中，实现
分区动态调整影像；为了保证算法的稳健性和场景重建结果的完整性，出现融合失败时，涉
及的影像按分区动态调整的策略进行处理；无论是分区ISfM还是融合分区，每一步均是相
互独立的过程，因此可将每个处理过程分配至多个计算节点，实现分布式并行处理，以提高
大场景的处理效率。

附图说明

[0056] 以下参考附图描述的实施例是示例性的，旨在用于解释和说明本发明，而不能理解为对本发明的保护范围的限制。

[0057] 图1是本发明公开的一种适用于大规模场景的运动恢复结构方法的流程图；

[0058] 图2是本发明公开的有效格网和无效格网的示意图；

[0059] 图3是本发明公开的步骤S200流程图；

[0060] 图4是本发明公开的影像分区的分区过程和对应影像分区结果的示意图；

[0061] 图5是本发明公开的步骤S300流程图；

[0062] 图6是本发明公开的影像分区融合的ISfM方法流程图；

[0063] 图7是本发明公开的ISfM流程图；

[0064] 图8是本发明公开的选取增加至场景中影像集的流程图；

[0065] 图9是本发明公开的步骤S335的流程图；

[0066] 图10是本发明公开的步骤S400的流程图。

具体实施方式

[0067] 为使本发明实施的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行更加详细的描述。

[0068] 需要说明的是：在附图中，自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。所描述的实施例是本发明一部分实施例，而不是全部的实施
例，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。基于本发明中
的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，
都属于本发明保护的范围。

[0069] 在本发明的描述中，需要理解的是，术语“中心”、“纵向”、“横向”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所
示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装
置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明保护
范围的限制。

[0070] 下面参考图1‑10详细描述本发明公开的一种适用于大规模场景的运动恢复结构方法的的第一实施例。本实施例主要应用于大规模场景的运动恢复结构，该方法具有稳健、
效率高且易于分布式并行实现等特点，可用于解决几万甚至几十万张影像大场景的稀疏重
建问题。

[0071] 如图1所示，本实施例主要包括以下步骤：

[0072] S100、根据影像匹配结果，计算两两重叠影像间的关联度得分；

[0073] S200、基于关联度得分，将影像划分为若干个影像分区；

[0074] S300、利用ISfM方法重建每个影像分区；

[0075] S400、基于光束法将已完成重建的各个影像分区融合成完整场景。

[0076] 本实施例中，将每个处理过程分配至多个计算节点，实现分布式并行处理，以提高大场景的处理效率；为了保证重建结果的完整性，将被剔除分区中的影像重新划分至其他
分区中，实现分区动态调整影像；为了保证算法的稳健性和场景重建结果的完整性，出现融
合失败时，涉及的影像按分区动态调整的策略进行处理，重新划分至其他分区中并按ISfM
方法完成重建。

[0077] 在步骤S100、根据影像匹配结果，计算两两重叠影像间的关联度得分之前，还包括以下步骤：

[0078] 步骤S000、采用SIFT匹配算法，提取影像特征，获得影像间的匹配关系，通过对比特征，获得影像间的匹配关系。

[0079] 在步骤S100中基于影像中同名点个数和点位分布计算两两影像间的关联度得分，如图2所示，统计像对同名像点数量 ，按影像像幅划分格网，例如15*15，如果同名点落
在某个格网内，则格网内数值累加1，所有同名点划分完毕后，累加值小于阈值的格网为无
效格网，累加值大于阈值的格网为有效格网。按照公式（1）计算影像间的关联度得分corr：

[0080]

[0081] 式中， 为影像间的关联度得分；

[0082] 和 为权重；

[0083] 为统计像对同名点数量；

[0084] 、 为左右影像构成的像对中最多的同名点数；

[0085] 为有效格网内像点的外接矩形面积与像幅面积的比值，其中外接矩形面积为统计有效格网所有像点坐标x和y方向的最大最小值下边界的矩形面积。

[0086] 如图3和图4所示，在一种实施例中，上述步骤S200中基于关联度得分，将影像划分为若干个影像分区，具体包括以下步骤：

[0087] S210、对影像进行初次划分，获得第一次分区。将场景中每张影像看作一个独立分区，合并其领域内关联度得分最高的同名影像，获得第一次分区。记录每张影像关联度得分
最高的一张影像，按影像关联度得分分数从高到低排列，遍历排序结果，依次将未分区的影
像与得分最高的同名影像划分到同一分区，完成影像初次划分，此时每个分区内至少包含
两张影像。

[0088] S220、对第一次分区进行合并，获得影像初始分区。取不同第一次分区间影像关联度得分的最大值作为两个分区的关联度得分，依次合并关联度最大的两个影像第一次分
区，也就是将“小”的分区逐步合并为“大”的分区，重复此过程，得到场景的影像初始分区结
果。

[0089] 在一种实施方式中，为了避免初始分区内影像过多或过少的情况出现，预设初始分区内影像数阈值的范围，例如预设初始分区内的影像数阈值范围为15张至75张，若某个
初始分区内的影像数小于阈值，将该初始分区划归至关联度得分最高的分区中，若该初始
分区内的影像数大于阈值，则返回至步骤S210或步骤S220中，继续对影像进行分区，回溯分
区影像汇聚过程，将该初始分区分成两个或更多个满足阈值的初始分区。

[0090] S230、对影像初始分区进行剔除弱连接分区，获得影像分区。统计两两初始分区间的公共地面点数量及每个初始分区与其领域的点数最大值，若某初始分区与其领域的最大
点数小于阈值，视为弱连接分区，将视为弱连接分区剔除，并动态调整影像将该影像重新划
分至其他初始分区中。

[0091] 如图5‑图7所示，在一种实施方式中，步骤S300中利用ISfM方法重建每个影像分区，具体包括以下步骤：

[0092] S310、获得匹配结果；

[0093] 利用影像匹配算法获取匹配点，通常使用SIFT特征描述子提取影像特征，利用影像检索技术识别匹配影像对，通过比较特征的欧式距离获得匹配结果。

[0094] S320、利用匹配点估计像对的相对位姿并获取初始的结构信息；

[0095] 选取两张影像作为初始影像对，利用匹配点估计像对的相对位姿并获取初始的结构信息，常用5点法估计本质矩阵E再分解出 矩阵，光束法优化得到更加精确的影像
位姿和结构。

[0096] S330、利用已知的场景结构、2D‑3D对应关系估计待增加影像的位姿，根据准则和策略选取增加至场景中的影像集。

[0097] 如图8所示，本实施例中选用的准则和策略选取增加至场景中的影像集，包括以下步骤：

[0098] S331、利用2D‑3D对应关系，估计存在关联影像的位姿，记录有效像点数量；

[0099] S332、选取步骤331中所有有效像点数中值的0.25倍作为阈值，剔除有效点数小于阈值的估计结果，得到待增加的备选影像集；

[0100] S333、基于备选影像集和场景中已排列的影像，通过三角测量获得所有可能的3D点，统计备选影像可用于光束法优化的有效像点数量；

[0101] S334、选取步骤S333中可用像点数中值的0.5倍作为阈值，大于阈值的影像将被增加至场景中；

[0102] S335、剔除不可靠结果。

[0103] 考虑到影像匹配精度、地形起伏、飞行方式、相机检校特性及其他不确定性因素，为了保证完整重建结果的正确性，需进一步检测可看作是相互独立的分区重建结果，以期
剔除可能存在的不稳定项。

[0104] 如图9所示，在步骤S335中剔除不可靠结果，具体包括以下步骤：

[0105] S3351、统计误差，计算影像分区内有效点位误差的平均值，剔除大于阈值的影像分区；

[0106] 计算影像分区内有效点点位误差的平均值，所有影像分区点位误差平均的2倍作为阈值，剔除大于阈值的分区。

[0107] S3352、相机检校参数，剔除同源相机在不同分区中异常的检校结果；

[0108] 异常的检校结果包括焦距、主点、畸变参数。

[0109] S3353、成功排列影像的比例。如某分区内成功排列的影像数与总数比值小于阈值（如0.5），认为重建结果不可靠，将其剔除；

[0110] S3354、影像分区间有效的公共地面点，将弱连接影像分区剔除。

[0111] 统计两两影像分区间有效的公共地面点数量及每个初始分区与其邻域的点数最大值，如某影像分区与其邻域的最大点数小于阈值，视为弱连接分区将其剔除。

[0112] 为了保证重建结果的完整性，将被剔除分区中的影像重新划分至其他影像分区中，实现影像分区动态调整影像，并ISfM方法完成重建，算法从分区动态调整影像作为输
入，从后方交会流程开始执行。

[0113] S340、交会得到新的稀疏结构，增大场景的覆盖范围。

[0114] S350、光束法优化场景使得重投影误差和最小。

[0115] S360、过滤可能存在的不可靠2D、3D点，剔除准则包括投影误差和交会角；

[0116] 利用光束法优化和过滤两个步骤需循环执行几次，光束法优化后过滤掉不可靠的点，利用剩余点进行光束法优化，再进行过滤，如此反复几次，消除不稳定点对优化可能造
成的影响，提高精度供后续进一步增量使用。

[0117] S370、循环步骤S330‑步骤S360直至场景稀疏重建完成或无法增加更多的影像至场景中为止。

[0118] 如图10所示，在一种实施方式中，上述步骤S400中基于光束法将已完成重建的各个影像分区融合成完整场景，其融合影像分区的目的在于将已完重建的各个影像分区利用
公共的地面点合并成场景完整的重建结果，具体包括以下步骤：

[0119] S410、计算两两影像分区间的空间相似变换参数，统一待合并影像分区的坐标系和比例尺；

[0120] 通过分区间公共的地面点计算两两分区的三维空间线性变换7参数，统一待合并分区的坐标系和比例尺。

[0121] S420、确定融合任务列表；

[0122] 视每个分区与其邻域有效点数累加和为关联性指标，按从小到大顺序排列，简记为 ，优先融合关联度指标小的分区。首先，选取 作为基准，有效点数最
多的 与其融合，标记 和 为已处理；其次，对于尚未标记的 ，设其有效点数最多
的为 ，若 已标记，则将 追加至 的融合列表中，否则 与 融合，并标记为
已处理分区；最后，不断重复该过程，直至所有分区被标记，得到了融合任务列表。

[0123] S430、确定融合影像分区的影像位姿和结构信息坐标初值；

[0124] 利用S410中计算的两两分区间的变换参数，假如一个融合任务仅涉及两个分区，可任选其中一个为基准，将另一个变换至基准分区。当存在三个及以上分区需融合至一起
时，选取关联性指标最大的分区为基准，如果其他分区与基准存在有效的变换参数时，直接
将其变换至基准分区。当某分区与基准分区无法直接变换时，则根据空间相似变换的刚体
特性及两两间的变换参数，以传递的方式通过多次变换将其转换至基准分区。

[0125] S440、利用光束法融合影像分区。

[0126] 遵循先融合“场景”再融合“相机”的原则。融合“场景”时每个影像分区的相机检校参数相互独立，光束法优化影像位姿和结构坐标。融合“相机”时将同一相机的多套检校参
数合并为一套后再进行光束法优化，使得相机检校参数唯一。前述过程为一个融合循环，不
断重复该过程，直至所有分区融合成完整场景为止。

[0127] 为了保证算法的稳健性和场景重建结果的完整性，出现融合失败时，涉及的影像按影像分区动态调整的策略进行处理，重新划分至其他影像分区中并按ISfM方法完成重
建。

[0128] 本实施例中，无论是影像分区ISfM还是融合影像分区，每一步均是相互独立的过程，因此可将每个处理过程分配至多个计算节点，实现分布式并行处理，以提高大场景的处
理效率。基本的并行调度方案设计包括主机端和计算节点端。主机端负责数据组织、场景分
区、确定融合任务列表、计算任务划分、分区动态调整与结果回收。计算节点端负责接受主
机端指定的任务，包括单独分区ISfM和分区间融合两部分，同时将计算结果返还至主机端。

[0129] 以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应
涵盖在本发明的保护范围之内。因此，本发明的保护范围应以所述权利要求的保护范围为
准。