增量式平移平均化方法、系统、设备转让专利
申请号 : CN202110992939.0
文献号 : CN113436230B
文献日 : 2021-11-19
发明人 : 高翔 , 李梦晗 , 马孝冬 , 解则晓
申请人 : 中国海洋大学
摘要 :
本发明属于三维重建中从运动恢复结构技术领域，具体涉及一种增量式平移平均化方法、系统、设备，旨在解决现有平移平均化方法复杂度高、准确度低、鲁棒性差的问题。本方法包括构造外极几何图；构建相机四元组集合，基于局部优化选取初始相机四元组作为初始种子视图；构建第三顶点集合；组成相机三元组，采用基于加权支撑集合的下一最优视图选取策略确定顶点的增量顺序；对当前已估计的绝对位置进行加权局部优化/加权全局优化；对全局优化后的所有已估计绝对位置的顶点进行重平移平均化。本发明降低了平移平均化方法的复杂度，并提高了绝对位置估计的准确性、鲁棒性。
权利要求 :
1.一种增量式平移平均化方法，应用于全局式从运动恢复结构中相机绝对位置的求解，其特征在于，该方法包括以下步骤：步骤S100，获取多帧图像，进行两两图像之间的特征匹配，根据外极几何关系构造外极几何图 ，进而计算匹配图像对之间的相对旋转和相对平移；其中，为顶点集合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不同图像的相机两两之间的外极几何边的集合，包含了相机之间的运动信息；
步骤S200，选取所述外极几何图中特征匹配数量最多的前 条边构成的相机四元组，构建四元组集合，并计算在局部坐标系下所述四元组集合的各相机四元组中的每一个相机的绝对位置；结合各相机的绝对位置，计算所述四元组集合中的各相机四元组的选取代价，并将选取代价最大的相机四元组对应的视图作为初始种子视图；
步骤S300，基于所述初始种子视图对应的顶点构建已估计绝对位置的顶点集合，作为第一顶点集合，将所述外极几何图中未估计绝对位置的顶点集合，作为第二顶点集合；选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的前 个顶点，构建第三顶点集合；
步骤S400，将所述第三顶点集合中的每个顶点与所述第一顶点集合中的顶点组成相机三元组，并通过线性三焦张量求解法计算所述第三顶点集合中各顶点的绝对位置；根据求得的绝对位置计算各顶点的选取代价，并将选取代价最大的顶点对应的视图作为下一最优视图；
步骤S500，固定第一顶点集合中已估计的相机绝对位置，仅对最新估计的下一最优视图对应顶点的绝对位置进行加权局部优化；完成加权局部优化后，判断当前已估计绝对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估计的绝对位置进行加权全局优化；
所述加权局部优化为：对选取的下一最优视图对应顶点的绝对位置，结合第一顶点集合中的绝对位置和第一边集合中各边连接的两个顶点之间测量得到的相对位置，计算各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集合；
所述加权全局优化为：对所有已估计绝对位置的顶点，结合各顶点的绝对位置和两两之间测量得到的相对位置，计算各外极几何边对应的相对位置误差，作为第二误差；若第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝对位置的顶点的绝对位置进行加权全局优化；
加权全局优化完成后，进一步通过所述加权全局优化方法对所有已估计绝对位置的顶点进行重平移平均化；
步骤S600，完成所有绝对位置的估计后，输出对所有可估计顶点进行加权全局优化和重平移平均化后的绝对位置，作为各相机绝对位置的最终估计结果。
2.根据权利要求1所述的增量式平移平均化方法，其特征在于，计算在局部坐标系下所述四元组集合的各相机四元组中的每一个相机的绝对位置，其方法为：其中， 分别表示在局部坐标系下相机 经优化后的绝对位置，表示平方弦距离， 为相对平移变换到全局坐标系下的表示， 表示中的任一条边， 表示四元组集合的任意一个相机四元组，、 表示相机 的初始绝对位置。
3.根据权利要求2所述的增量式平移平均化方法，其特征在于，计算所述四元组集合中的各相机四元组的选取代价，其方法为：其中， 表示相机四元组的选取代价， 表示相机四元组中每条外极几何边对应的权重。
4.根据权利要求1所述的增量式平移平均化方法，其特征在于，根据求得的绝对位置计算各顶点的选取代价，其方法为：
其中， 表示下一最优视图选择中各顶点的选取代价， 为 中的一条边， 为第三顶点集合中顶点 与第一顶点集合中各顶点之间的外极几何边的集合， 表示边对应两顶点间的相对位置， 表示第一顶点集合中顶点 当前的绝对位置估计值， 表示每条外极几何边对应的权重。
5.根据权利要求2所述的增量式平移平均化方法，其特征在于，在加权局部优化时的内值边获取方法为：
其中， 表示第一顶点集合 与选取的下一最优视图对应顶点 之间外极几何边的集合， 为 中的任意一条边， 表示 中的内值边的集合， 表示边 连接的两个相机之间的相对位置，表示顶点 当前的绝对位置估计值， 表示 初始化的绝对位置， 表示各边对应的相对位置误差， 表示设定的误差阈值。
6.根据权利要求5所述的增量式平移平均化方法，其特征在于，基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优化，其方法为：其中， 表示绝对位置 加权局部优化后的结果， 表示 中的任意一条边，表示边 连接的两个相机之间的相对位置。
7.根据权利要求6所述的增量式平移平均化方法，其特征在于，在加权全局优化时的内值边获取方法为：
其中， 表示加权全局优化时的内值边集合， 表示所有已估计绝对位置的顶点之间的边集合， 表示 中的任意一条边， 表示边 连接的两个相机之间的相对位置，表示顶点 当前的绝对位置估计值。
8.根据权利要求7所述的增量式平移平均化方法，其特征在于，基于 范数对所有已估计绝对位置的顶点的绝对位置进行加权全局优化，其方法为：其中， 表示绝对位置集合 进行加权全局优化后的结果， 为 中的任意一条边， 表示边 连接的两个相机之间的相对位置。
9.一种增量式平移平均化系统，其特征在于，该系统包括：外极几何图构造模块、初始种子视图选取模块、集合构建模块、下一最优视图选取模块、优化模块、绝对位置估计输出模块；
所述外极几何图构造模块，配置为获取多帧图像，进行两两图像之间的特征匹配，根据外极几何关系构造外极几何图 ，进而计算匹配图像对之间的相对旋转和相对平移；其中，为顶点集合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不同图像的相机两两之间的外极几何边的集合，包含了相机之间的运动信息；
所述初始种子视图选取模块，配置为选取所述外极几何图中特征匹配数量最多的前条边构成的相机四元组，构建四元组集合，并计算在局部坐标系下所述四元组集合的各相机四元组中的每一个相机的绝对位置；结合各相机的绝对位置，计算所述四元组集合中的各相机四元组的选取代价，并将选取代价最大的相机四元组对应的视图作为初始种子视图；
所述集合构建模块，配置为将所述外极几何图中已估计的和未估计绝对位置的顶点集合，作为第一顶点集合、第二顶点集合；选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的前 个顶点，构建第三顶点集合；
所述下一最优视图选取模块，配置为将所述第三顶点集合中的每个顶点与所述第一顶点集合中的顶点组成相机三元组，并通过线性三焦张量求解法计算所述第三顶点集合中各顶点的绝对位置；根据求得的绝对位置计算各顶点的选取代价，并将选取代价最大的顶点对应的视图作为下一最优视图；
所述优化模块，配置为固定第一顶点集合中已估计的相机绝对位置，仅对最新估计的下一最优视图对应顶点的绝对位置进行加权局部优化；完成加权局部优化后，判断当前已估计绝对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估计的绝对位置进行加权全局优化；
所述加权局部优化为：对选取的下一最优视图对应顶点的绝对位置，结合第一顶点集合中的绝对位置和第一边集合中各边连接的两个顶点之间测量得到的相对位置，计算各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集合；
所述加权全局优化为：对所有已估计绝对位置的顶点，结合各顶点的绝对位置和两两之间测量得到的相对位置，计算各外极几何边对应的相对位置误差，作为第二误差；若第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝对位置的顶点的绝对位置进行加权全局优化；
加权全局优化完成后，进一步通过所述加权全局优化方法对所有已估计绝对位置的顶点进行重平移平均化；
所述绝对位置估计输出模块，配置为完成所有绝对位置的估计后，输出对所有可估计顶点进行加权全局优化和重平移平均化后的绝对位置，作为各相机绝对位置的最终估计结果。
10.一种电子设备，其特征在于，包括：至少一个处理器；以及与至少一个所述处理器通信连接的存储器；其中，所述存储器存储有可被所述处理器执行的指令，所述指令用于被所述处理器执行以实现权利要求1‑8任一项所述的增量式平移平均化方法。
说明书 :
增量式平移平均化方法、系统、设备
技术领域
[0001] 本发明属于三维重建中从运动恢复结构技术领域，具体涉及一种增量式平移平均化方法、系统、设备。
背景技术
[0002] 从运动恢复结构（structure from motion）是基于图像的大规模场景三维重建中的一个关键步骤，近年来发展迅速，其输入为图像特征匹配，输出为相机绝对位姿和场景结
构。根据相机位姿初始化方式的不同，从运动恢复结构大致可以分为增量式与全局式两种。
增量式方法通过迭代式的相机位姿估计和场景结构扩展完成对相机位姿与场景结构的初
始化，在迭代过程中，为了应对不可避免的特征匹配外值，这一方法还会引入随机抽样一致
性（random sample consensus）算法和捆绑调整（bundle adjustment）技术。与增量式方法
不同，全局式从运动恢复结构主要利用运动平均化技术完成对相机位姿的初始化，通常包
括旋转平均化（rotation averaging）和平移平均化（translation averaging）两步。相比
于全局式从运动恢复结构，增量式方法更加频繁地调用基于随机抽样一致性的模型估计算
法和基于捆绑调整的参数优化技术，因而其结果也更加地准确和鲁棒。
构。根据相机位姿初始化方式的不同，从运动恢复结构大致可以分为增量式与全局式两种。
增量式方法通过迭代式的相机位姿估计和场景结构扩展完成对相机位姿与场景结构的初
始化，在迭代过程中，为了应对不可避免的特征匹配外值，这一方法还会引入随机抽样一致
性（random sample consensus）算法和捆绑调整（bundle adjustment）技术。与增量式方法
不同，全局式从运动恢复结构主要利用运动平均化技术完成对相机位姿的初始化，通常包
括旋转平均化（rotation averaging）和平移平均化（translation averaging）两步。相比
于全局式从运动恢复结构，增量式方法更加频繁地调用基于随机抽样一致性的模型估计算
法和基于捆绑调整的参数优化技术，因而其结果也更加地准确和鲁棒。
[0003] 平移平均化是指在给定相对平移测量值的情况下对相机的绝对位置进行估计。相对平移测量值一般通过本质矩阵（essential matrix）的估计和分解来获取。与旋转平均化
相比，平移平均化的难度更大，其原因有三：1）本质矩阵只蕴含了相对平移的方向信息，分
解本质矩阵求得的相对平移存在尺度不确定性问题；2）与相对旋转相比，从本质矩阵中求
得的相对平移的精度更容易受到错误特征匹配的影响；3）只有在同一平行刚性组
（parallel rigid component）中的相机才能通过平移平均化的方式被唯一估计，而旋转平
均化只需要所有相机在同一连通组（connected component）中即可。目前，平移平均化问题
虽然已被广泛研究，但与旋转平均化相比，其远未解决且一直是一个热点话题。
相比，平移平均化的难度更大，其原因有三：1）本质矩阵只蕴含了相对平移的方向信息，分
解本质矩阵求得的相对平移存在尺度不确定性问题；2）与相对旋转相比，从本质矩阵中求
得的相对平移的精度更容易受到错误特征匹配的影响；3）只有在同一平行刚性组
（parallel rigid component）中的相机才能通过平移平均化的方式被唯一估计，而旋转平
均化只需要所有相机在同一连通组（connected component）中即可。目前，平移平均化问题
虽然已被广泛研究，但与旋转平均化相比，其远未解决且一直是一个热点话题。
[0004] 现有的平移平均化方法主要侧重于以下三个方面：1）设计合适的代价函数形式和优化方案；2）研究对外极几何图的滤除/优化策略；3）引入辅助信息，如特征轨迹、相机三元
组或秩约束等。尽管上述方法已经取得了不错的结果，但由于过度依赖于复杂的目标函数
形式与优化，设计精巧的初始化操作，或者其他附加信息，这些方法的复杂度更高，效率更
低，此外，准确性和鲁棒性依然是它们面临的关键挑战。受增量式从运动恢复结构方法的启
发，本发明提出了一种增量式平移平均化方法。
组或秩约束等。尽管上述方法已经取得了不错的结果，但由于过度依赖于复杂的目标函数
形式与优化，设计精巧的初始化操作，或者其他附加信息，这些方法的复杂度更高，效率更
低，此外，准确性和鲁棒性依然是它们面临的关键挑战。受增量式从运动恢复结构方法的启
发，本发明提出了一种增量式平移平均化方法。
发明内容
[0005] 为了解决现有技术中的上述问题，即为了解决现有的平移平均化方法复杂度高、准确度低、鲁棒性差的问题，本发明第一方面，提出了一种增量式平移平均化方法，应用于
全局式从运动恢复结构中相机绝对位置的求解，该方法包括：
全局式从运动恢复结构中相机绝对位置的求解，该方法包括：
[0006] 步骤S100，获取多帧图像，进行两两图像之间的特征匹配，根据外极几何关系构造外极几何图 ，进而计算匹配图像对之间的相对旋转和相对平移；其中，为顶点集
合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不同图像的相机两两之间的外
极几何边的集合，包含了相机之间的运动信息；
合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不同图像的相机两两之间的外
极几何边的集合，包含了相机之间的运动信息；
[0007] 步骤S200，选取所述外极几何图中特征匹配数量最多的前 条边构成的相机四元组，构建四元组集合，并计算在局部坐标系下所述四元组集合的各相机四元组中的每一个
相机的绝对位置；结合各相机的绝对位置，计算所述四元组集合中的各相机四元组的选取
代价，并将选取代价最大的相机四元组对应的视图作为初始种子视图；
相机的绝对位置；结合各相机的绝对位置，计算所述四元组集合中的各相机四元组的选取
代价，并将选取代价最大的相机四元组对应的视图作为初始种子视图；
[0008] 步骤S300，基于所述初始种子视图对应的顶点构建已估计绝对位置的顶点集合，作为第一顶点集合，将所述外极几何图中未估计绝对位置的顶点集合，作为第二顶点集合；
选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的前 个顶点，构建第三顶
点集合；
选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的前 个顶点，构建第三顶
点集合；
[0009] 步骤S400，将所述第三顶点集合中的每个顶点与所述第一顶点集合中的顶点组成相机三元组，并通过线性三焦张量求解法计算所述第三顶点集合中各顶点的绝对位置；根
据求得的绝对位置计算各顶点的选取代价，并将选取代价最大的顶点对应的视图作为下一
最优视图；
据求得的绝对位置计算各顶点的选取代价，并将选取代价最大的顶点对应的视图作为下一
最优视图；
[0010] 步骤S500，固定第一顶点集合中已估计的相机绝对位置，仅对最新估计的下一最优视图对应顶点的绝对位置进行加权局部优化；完成加权局部优化后，判断当前已估计绝
对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估计的绝对位置
进行加权全局优化；
对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估计的绝对位置
进行加权全局优化；
[0011] 所述加权局部优化为：对选取的下一最优视图对应顶点的绝对位置，结合第一顶点集合中的绝对位置和第一边集合中各边连接的两个顶点之间测量得到的相对位置，计算
各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作
为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优
化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集
合；
各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作
为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优
化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集
合；
[0012] 所述加权全局优化为：对所有已估计绝对位置的顶点，结合各顶点的绝对位置和两两之间测量得到的相对位置，计算各外极几何边对应的相对位置误差，作为第二误差；若
第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝
对位置的顶点的绝对位置进行加权全局优化；
第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝
对位置的顶点的绝对位置进行加权全局优化；
[0013] 加权全局优化完成后，进一步通过所述加权全局优化方法对所有已估计绝对位置的顶点进行重平移平均化；
[0014] 步骤S600，完成所有绝对位置的估计后，输出对所有可估计顶点进行加权全局优化和重平移平均化后的绝对位置，作为各相机绝对位置的最终估计结果。
[0015] 在一些优选的实施方式中，计算在局部坐标系下所述四元组集合的各相机四元组中的每一个相机的绝对位置，其方法为：
[0016]
[0017] 其中， 分别表示在局部坐标系下相机 经优化后的绝对位置，表示平方弦距离， 为相对平移变换到全局坐标系下的表示， 表示
中的任一条边， 表示四元组集合的任意一个相机四元组，、 表示相机 的初始绝
对位置。
中的任一条边， 表示四元组集合的任意一个相机四元组，、 表示相机 的初始绝
对位置。
[0018] 在一些优选的实施方式中，计算所述四元组集合中的各相机四元组的选取代价，其方法为：
[0019]
[0020] 其中， 表示相机四元组的选取代价， 表示相机四元组中每条外极几何边对应的权重。
[0021] 在一些优选的实施方式中，根据求得的绝对位置计算各顶点的选取代价，其方法为：
[0022]
[0023] 其中， 表示下一最优视图选择中各顶点的选取代价， 为 中的一条边，为第三顶点集合中顶点 与第一顶点集合中各顶点之间的外极几何边的集合， 表示边
对应两顶点间的相对位置， 表示第一顶点集合中顶点 当前的绝对位置估计值，
表示每条外极几何边对应的权重。
对应两顶点间的相对位置， 表示第一顶点集合中顶点 当前的绝对位置估计值，
表示每条外极几何边对应的权重。
[0024] 在一些优选的实施方式中，在加权局部优化时的内值边获取方法为：
[0025]
[0026]
[0027] 其中， 表示第一顶点集合 与选取的下一最优视图对应顶点 之间连接边的集合， 为 中的任意一条边， 表示 中的内值边的集合， 表示边 连接
的两个相机之间的相对位置，表示顶点 当前的绝对位置估计值， 表示 初始化的
绝对位置， 表示各外极几何边对应的相对位置误差， 表示设定的误差阈值。
的两个相机之间的相对位置，表示顶点 当前的绝对位置估计值， 表示 初始化的
绝对位置， 表示各外极几何边对应的相对位置误差， 表示设定的误差阈值。
[0028] 在一些优选的实施方式中，基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优化，其方法为：
[0029]
[0030]
[0031] 其中， 表示绝对位置 加权局部优化后的结果， 表示 中的任意一条边， 表示边 连接的两个相机之间的相对位置。
[0032] 在一些优选的实施方式中，在加权全局优化时的内值边获取方法为：
[0033]
[0034]
[0035] 其中， 表示加权全局优化时的内值边集合， 表示所有已估计绝对位置的顶点之间的边集合， 表示 中的任意一条边， 表示边 连接的两个
相机之间的相对位置，表示顶点 当前的绝对位置估计值。
相机之间的相对位置，表示顶点 当前的绝对位置估计值。
[0036] 在一些优选的实施方式中，基于 范数对所有已估计绝对位置的顶点的绝对位置进行加权全局优化，其方法为：
[0037]
[0038]
[0039] 其中， 表示绝对位置集合 进行加权全局优化后的结果， 为 中的任意一条边， 表示边 连接的两个相机之间的相对位置。
[0040] 本发明的第二方面，提出了一种增量式平移平均化系统，该系统包括：外极几何图构造模块、初始种子视图选取模块、集合构建模块、下一最优视图选取模块、优化模块、绝对
位置估计输出模块；
位置估计输出模块；
[0041] 所述外极几何图构造模块，配置为获取多帧图像，进行两两图像之间的特征匹配，根据外极几何关系构造外极几何图 ，进而计算匹配图像对之间的相对旋转和相
对平移；其中，为顶点集合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不同
图像的相机两两之间的外极几何边的集合，包含了相机之间的运动信息；
对平移；其中，为顶点集合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不同
图像的相机两两之间的外极几何边的集合，包含了相机之间的运动信息；
[0042] 所述初始种子视图选取模块，配置为选取所述外极几何图中特征匹配数量最多的前 条边构成的相机四元组，构建四元组集合，并计算在局部坐标系下所述四元组集合的
各相机四元组中的每一个相机的绝对位置；结合各相机的绝对位置，计算所述四元组集合
中的各相机四元组的选取代价，并将选取代价最大的相机四元组对应的视图作为初始种子
视图；
各相机四元组中的每一个相机的绝对位置；结合各相机的绝对位置，计算所述四元组集合
中的各相机四元组的选取代价，并将选取代价最大的相机四元组对应的视图作为初始种子
视图；
[0043] 所述集合构建模块，配置为基于所述初始种子视图对应的顶点构建已估计绝对位置的顶点集合，作为第一顶点集合，将所述外极几何图中未估计绝对位置的顶点集合，作为
第二顶点集合；选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的前 个顶
点，构建第三顶点集合；
第二顶点集合；选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的前 个顶
点，构建第三顶点集合；
[0044] 所述下一最优视图选取模块，配置为将所述第三顶点集合中的每个顶点与所述第一顶点集合中的顶点组成相机三元组，并通过线性三焦张量求解法计算所述第三顶点集合
中各顶点的绝对位置；根据求得的绝对位置计算各顶点的选取代价，并将选取代价最大的
顶点对应的视图作为下一最优视图；
中各顶点的绝对位置；根据求得的绝对位置计算各顶点的选取代价，并将选取代价最大的
顶点对应的视图作为下一最优视图；
[0045] 所述优化模块，配置为固定第一顶点集合中已估计的相机绝对位置，仅对最新估计的下一最优视图对应顶点的绝对位置进行加权局部优化；完成加权局部优化后，判断当
前已估计绝对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估计
的绝对位置进行加权全局优化；
前已估计绝对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估计
的绝对位置进行加权全局优化；
[0046] 所述加权局部优化为：对选取的下一最优视图对应顶点的绝对位置，结合第一顶点集合中的绝对位置和第一边集合中各边连接的两个顶点之间测量得到的相对位置，计算
各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作
为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优
化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集
合；
各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作
为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优
化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集
合；
[0047] 所述加权全局优化为：对所有已估计绝对位置的顶点，结合各顶点的绝对位置和两两之间测量得到的相对位置，计算各外极几何边对应的相对位置误差，作为第二误差；若
第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝
对位置的顶点的绝对位置进行加权全局优化；
第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝
对位置的顶点的绝对位置进行加权全局优化；
[0048] 加权全局优化完成后，进一步通过所述加权全局优化方法对所有已估计绝对位置的顶点进行重平移平均化；
[0049] 所述绝对位置估计输出模块，配置为完成所有绝对位置的估计后，输出对所有可估计顶点进行加权全局优化和重平移平均化后的绝对位置，作为各相机绝对位置的最终估
计结果。
计结果。
[0050] 本发明的第三方面，提出了一种电子设备，至少一个处理器；以及与至少一个所述处理器通信连接的存储器；其中，所述存储器存储有可被所述处理器执行的指令，所述指令
用于被所述处理器执行以实现权利要求上述的增量式平移平均化方法。
用于被所述处理器执行以实现权利要求上述的增量式平移平均化方法。
[0051] 本发明的有益效果：
[0052] 本发明降低了平移平均化方法的复杂度，并提高了绝对位置估计的准确性、鲁棒性。
[0053] 1）本发明采用基于局部优化的初始四元组选取策略实现种子视图的选取与构建；采用基于加权支撑集合的下一最优视图选取策略确定顶点的增量顺序；在下一最优视图选
取与初始化之后进行加权局部或全局优化，为使绝对位置的估计更加精确和鲁棒，在加权
全局优化后再进行一步重平移平均化操作，改善了绝对位置估计的结果，提高了绝对位置
估计的准确性、鲁棒性。
取与初始化之后进行加权局部或全局优化，为使绝对位置的估计更加精确和鲁棒，在加权
全局优化后再进行一步重平移平均化操作，改善了绝对位置估计的结果，提高了绝对位置
估计的准确性、鲁棒性。
[0054] 2）由于增量参数估计方法的有效性，本发明提出的平移平均化方法较少依赖于其他方法中常用的鲁棒操作，为平移平均化的实现提供了一种更加简单高效的途径。
附图说明
[0055] 通过阅读参照以下附图所做的对非限制性实施例所做的详细描述，本申请的其他特征、目的和优点将会变得更明显。
[0056] 图1是本发明一种实施例的增量式平移平均化方法的流程示意图；
[0057] 图2是本发明一种实施例的增量式平移平均化系统的框架示意图；
[0058] 图3是本发明一种实施例的增量式平移平均化方法的详细流程示意图；
[0059] 图4是本发明一种实施例的适于用来实现本申请实施例的电子设备的计算机系统的结构示意图。
具体实施方式
[0060] 为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不
是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前
提下所获得的所有其他实施例，都属于本发明保护的范围。
是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前
提下所获得的所有其他实施例，都属于本发明保护的范围。
[0061] 下面结合附图和实施例对本申请作进一步的详细说明。可以理解的是，此处所描述的具体实施例仅用于解释相关发明，而非对该发明的限定。另外还需要说明的是，为了便
于描述，附图中仅示出了与有关发明相关的部分。
于描述，附图中仅示出了与有关发明相关的部分。
[0062] 需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。
[0063] 本发明的一种增量式平移平均化方法，应用于全局式从运动恢复结构中相机绝对位置的求解，该方法包括：
[0064] 步骤S100，获取多帧图像，进行两两图像之间的特征匹配，根据外极几何关系构造外极几何图 ，进而计算匹配图像对之间的相对旋转和相对平移；其中，为顶点集
合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不同图像的相机两两之间的外
极几何边的集合，包含了相机之间的运动信息；
合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不同图像的相机两两之间的外
极几何边的集合，包含了相机之间的运动信息；
[0065] 步骤S200，选取所述外极几何图中特征匹配数量最多的前 条边构成的相机四元组，构建四元组集合，并计算在局部坐标系下所述四元组集合的各相机四元组中的每一个
相机的绝对位置；结合各相机的绝对位置，计算所述四元组集合中的各相机四元组的选取
代价，并将选取代价最大的相机四元组对应的视图作为初始种子视图；
相机的绝对位置；结合各相机的绝对位置，计算所述四元组集合中的各相机四元组的选取
代价，并将选取代价最大的相机四元组对应的视图作为初始种子视图；
[0066] 步骤S300，基于所述初始种子视图对应的顶点构建已估计绝对位置的顶点集合，作为第一顶点集合，将所述外极几何图中未估计绝对位置的顶点集合，作为第二顶点集合；
选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的前 个顶点，构建第三顶
点集合；
选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的前 个顶点，构建第三顶
点集合；
[0067] 步骤S400，将所述第三顶点集合中的每个顶点与所述第一顶点集合中的顶点组成相机三元组，并通过线性三焦张量求解法计算所述第三顶点集合中各顶点的绝对位置；根
据求得的绝对位置计算各顶点的选取代价，并将选取代价最大的顶点对应的视图作为下一
最优视图；
据求得的绝对位置计算各顶点的选取代价，并将选取代价最大的顶点对应的视图作为下一
最优视图；
[0068] 步骤S500，固定第一顶点集合中已估计的相机绝对位置，仅对最新估计的下一最优视图对应顶点的绝对位置进行加权局部优化；完成加权局部优化后，判断当前已估计绝
对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估计的绝对位置
进行加权全局优化；
对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估计的绝对位置
进行加权全局优化；
[0069] 所述加权局部优化为：对选取的下一最优视图对应顶点的绝对位置，结合第一顶点集合中的绝对位置和第一边集合中各边连接的两个顶点之间测量得到的相对位置，计算
各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作
为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优
化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集
合；
各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作
为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优
化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集
合；
[0070] 所述加权全局优化为：对所有已估计绝对位置的顶点，结合各顶点的绝对位置和两两之间测量得到的相对位置，计算各外极几何边对应的相对位置误差，作为第二误差；若
第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝
对位置的顶点的绝对位置进行加权全局优化；
第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝
对位置的顶点的绝对位置进行加权全局优化；
[0071] 加权全局优化完成后，进一步通过所述加权全局优化方法对所有已估计绝对位置的顶点进行重平移平均化；
[0072] 步骤S600，完成所有绝对位置的估计后，输出对所有可估计顶点进行加权全局优化和重平移平均化后的绝对位置，作为各相机绝对位置的最终估计结果。
[0073] 为了更清晰地对本发明增量式平移平均化方法进行说明，下面结合附图1、3对本发明方法一种实施例中各步骤进行展开详述。
[0074] 步骤S100，获取多帧图像，进行两两图像之间的特征匹配，根据外极几何关系构造外极几何图 ，进而计算匹配图像对之间的相对旋转和相对平移；其中，为顶点集
合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不同图像的相机两两之间的外
极几何边的集合，包含了相机之间的运动信息；
合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不同图像的相机两两之间的外
极几何边的集合，包含了相机之间的运动信息；
[0075] 在本实施例中，将用于平移平均化的外极几何图记为 ，其中 和 分别表示外极几何图的顶点集合与边集合。本发明的输入为匹配图像对之间的相对平移 ，将其
通过已知的绝对旋转变换到全局坐标系中，记为 ，其中， 表示 中的任意一条
边， 是相对平移 通过公式 变换到全局坐标系下的表示，其中， 为顶点 在
全局坐标系下的绝对旋转。本发明的输出为各相机经优化后的绝对位置，记为 ，
其中，表示 中的任意一个顶点， 表示 对应的相机经优化后的绝对位置。图1为本发明
的方法流程图，主要包括以下几部分：1）采用基于局部优化的初始四元组选取策略实现种
子视图的选取与构建；2）采用基于加权支撑集合的下一最优视图选取策略确定顶点的增量
顺序；3）在下一最优视图选取与初始化之后进行加权局部或全局优化；4）为使绝对位置的
估计更加精确和鲁棒，在加权全局优化后再进行一步重平移平均化操作。具体在下述步骤
中描述。
通过已知的绝对旋转变换到全局坐标系中，记为 ，其中， 表示 中的任意一条
边， 是相对平移 通过公式 变换到全局坐标系下的表示，其中， 为顶点 在
全局坐标系下的绝对旋转。本发明的输出为各相机经优化后的绝对位置，记为 ，
其中，表示 中的任意一个顶点， 表示 对应的相机经优化后的绝对位置。图1为本发明
的方法流程图，主要包括以下几部分：1）采用基于局部优化的初始四元组选取策略实现种
子视图的选取与构建；2）采用基于加权支撑集合的下一最优视图选取策略确定顶点的增量
顺序；3）在下一最优视图选取与初始化之后进行加权局部或全局优化；4）为使绝对位置的
估计更加精确和鲁棒，在加权全局优化后再进行一步重平移平均化操作。具体在下述步骤
中描述。
[0076] 步骤S200，选取所述外极几何图中特征匹配数量最多的前 条边构成的相机四元组，构建四元组集合，并计算在局部坐标系下所述四元组集合的各相机四元组中的每一个
相机的绝对位置；结合各相机的绝对位置，计算所述四元组集合中的各相机四元组的选取
代价，并将选取代价最大的相机四元组对应的视图作为初始种子视图；
相机的绝对位置；结合各相机的绝对位置，计算所述四元组集合中的各相机四元组的选取
代价，并将选取代价最大的相机四元组对应的视图作为初始种子视图；
[0077] 初始种子视图的选取既是增量式从运动恢复结构中的关键步骤，也是本发明方法中的关键步骤。最直观的处理方式是根据下式选取具有最小旋转循环偏差的相机对或相机
三元组作为初始种子视图：
三元组作为初始种子视图：
[0078] （1）
[0079] （2）
[0080] 其中， 是 上的角距离，表示 中所有外极几何边组成的相机三元组集合。
[0081] 然而，在同一条边上，高精度的 并不能保证高精度的 ，因此，平移平均化中初始种子视图的选取应依赖于它自己的位置循环偏差而不是旋转循环偏差。此外，由于相对
平移模长的丢失，相机三元组是相机位置计算中的最小配置解，为了评估初始种子视图选
取和恢复的有效性，需额外增加一个相机。最终，出于对鲁棒性的考虑，在本实施例中，采用
相机四元组而非相机对或相机三元组进行初始种子视图的选取与构建，具体的选取方式叙
述如下：
平移模长的丢失，相机三元组是相机位置计算中的最小配置解，为了评估初始种子视图选
取和恢复的有效性，需额外增加一个相机。最终，出于对鲁棒性的考虑，在本实施例中，采用
相机四元组而非相机对或相机三元组进行初始种子视图的选取与构建，具体的选取方式叙
述如下：
[0082] 在选取之前需要注意，外极几何图中通常包含大量的四元组，特别是在顶点数量较多时，此类情况更为明显。为平衡四元组选取过程的有效性和高效性，本发明仅考虑特征
匹配数量最多的前 （ 为自然数，本发明中 优选设置为100）条边构成的相机四元组，并
将该四元组集合记为 ，其中， 表示选取的四元组集合， 表示 中的任意一个
相机四元组。
匹配数量最多的前 （ 为自然数，本发明中 优选设置为100）条边构成的相机四元组，并
将该四元组集合记为 ，其中， 表示选取的四元组集合， 表示 中的任意一个
相机四元组。
[0083] 对于 中的每一个四元组 ，可以通过下式获取在局部坐标系下该相机四元组中每一个相机的绝对位置：
[0084] （3）
[0085] 其中， 分别表示在局部坐标系下相机 经优化后的绝对位置，表示平方弦距离， 为相对平移变换到全局坐标系下的表示， 表示
中的任一条边， 表示四元组集合的任意一个相机四元组，、 表示相机 的初始绝
对位置。
中的任一条边， 表示四元组集合的任意一个相机四元组，、 表示相机 的初始绝
对位置。
[0086] 在设置绝对位置 的初始估计时，首先将 和 初始化为 和 ，再通过已知绝对旋转的线性三焦张量求解器分别在三元组 和 中初始化 和 。经上述优化
之后，利用下式为 中每个四元组 计算选取代价:
之后，利用下式为 中每个四元组 计算选取代价:
[0087] （4）
[0088] 其中， 表示相机四元组的选取代价， 表示相机四元组中每条外极几何边对应的权重。
[0089] 最后，可通过下式得到选定的初始四元组（或称之为初始种子视图）：
[0090] （5）
[0091] 其中， 表示初始四元组各顶点相机的序号，对应的四个绝对位置分别为， ， ， 。
[0092] 步骤S300，基于所述初始种子视图对应的顶点构建已估计绝对位置的顶点集合，作为第一顶点集合，将所述外极几何图中未估计绝对位置的顶点集合，作为第二顶点集合；
选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的前 个顶点，构建第三顶
点集合；
选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的前 个顶点，构建第三顶
点集合；
[0093] 下一最优视图选取是增量式从运动恢复结构的另一关键步骤，也需要着重考虑。一种较为简单的处理方式是选出与当前已估计绝对位置的相机连接边数最多的相机，将其
对应视图作为下一最优视图。然而，集合 中不同的边对应不同的相对平移测量误差
，这些边在选取过程中不应被同等对待。因此，为提升平移平均化方法的鲁
棒性，本发明设计了一种基于加权支撑集合的下一最优视图选取策略，具体流程叙述如下
对应视图作为下一最优视图。然而，集合 中不同的边对应不同的相对平移测量误差
，这些边在选取过程中不应被同等对待。因此，为提升平移平均化方法的鲁
棒性，本发明设计了一种基于加权支撑集合的下一最优视图选取策略，具体流程叙述如下
[0094] 在本实施例中，将当前已估计和未估计绝对位置的顶点集合分别记为 与 ，用表示当前已估计绝对位置的顶点集合，作为第一顶点集合，用 表示当前未估计绝对位
置的顶点集合，作为第二顶点集合，即 。下一最优视图选取的目的在于从 中选
出一个能够使增量式绝对位置计算过程更加鲁棒的顶点 。为提升下一最优视图选取的效
率，此处只考虑 中与 中所有顶点连接边数最多的前 （ 为自然数，本发明优选设置
为10）个顶点，并将该顶点集合记为 ，作为第三顶点集合，其中， 表示 中与 中
所有顶点连接边数最多的前10个顶点的集合， 表示 中的任意一个顶点。
置的顶点集合，作为第二顶点集合，即 。下一最优视图选取的目的在于从 中选
出一个能够使增量式绝对位置计算过程更加鲁棒的顶点 。为提升下一最优视图选取的效
率，此处只考虑 中与 中所有顶点连接边数最多的前 （ 为自然数，本发明优选设置
为10）个顶点，并将该顶点集合记为 ，作为第三顶点集合，其中， 表示 中与 中
所有顶点连接边数最多的前10个顶点的集合， 表示 中的任意一个顶点。
[0095] 步骤S400，将所述第三顶点集合中的每个顶点与所述第一顶点集合中的顶点组成相机三元组，并通过线性三焦张量求解法计算所述第三顶点集合中各顶点的绝对位置；根
据求得的绝对位置计算各顶点的选取代价，并将选取代价最大的顶点对应的视图作为下一
最优视图；
据求得的绝对位置计算各顶点的选取代价，并将选取代价最大的顶点对应的视图作为下一
最优视图；
[0096] 在本实施例中， 中的每个顶点 都可以与集合 中的顶点组成多个相机三元组，记作 。相机三元组在此处用于消除绝对位置估计中的尺度模糊问题，每个属
于 的三元组 都可以为 计算一个绝对相机位置，记作 。在已估计的绝对位置 和
，以及测量后的相对位置 ， 和 已知的情况下， 可以通过线性三焦张量求解法
计算得到。理想状态下，集合 中的每个绝对位置 应保持相等，但在实际情
况中，由于绝对位置估计误差和相对位置测量误差的影响，上述情形并不会发生。因此，为
进行下一最优视图的选取，需要根据下式计算集合 中每个绝对位置的选取代价：
于 的三元组 都可以为 计算一个绝对相机位置，记作 。在已估计的绝对位置 和
，以及测量后的相对位置 ， 和 已知的情况下， 可以通过线性三焦张量求解法
计算得到。理想状态下，集合 中的每个绝对位置 应保持相等，但在实际情
况中，由于绝对位置估计误差和相对位置测量误差的影响，上述情形并不会发生。因此，为
进行下一最优视图的选取，需要根据下式计算集合 中每个绝对位置的选取代价：
[0097] （6）
[0098] 其中， 表示下一最优视图选择中各顶点的选取代价， 为 中的一条边，为第三顶点集合中顶点 与第一顶点集合中各顶点之间的外极几何边的集合， 表示边
对应两顶点间的相对位置， 表示第一顶点集合中顶点 当前的绝对位置估计值，
表示每条外极几何边对应的权重。
对应两顶点间的相对位置， 表示第一顶点集合中顶点 当前的绝对位置估计值，
表示每条外极几何边对应的权重。
[0099] 随后，利用下式对集合 中代表性的绝对位置 进行选取：
[0100] （7）
[0101] 其中， 表示集合 中代表性的绝对位置的序号。最后，可通过下式得到选定的下一最优视图：
[0102] （8）
[0103] 其中， 表示选取的下一最优视图对应顶点的序号，该顶点的绝对位置被初始化为 。由于本发明提出的下一最优视图选取策略基于由重计算位置偏差进行加权的支撑
集合，因而其能够更加鲁棒地应对相对平移外值。
集合，因而其能够更加鲁棒地应对相对平移外值。
[0104] 步骤S500，固定第一顶点集合中已估计的相机绝对位置，仅对最新估计的下一最优视图对应顶点的绝对位置进行加权局部优化；完成加权局部优化后，判断当前已估计绝
对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估计的绝对位置
进行加权全局优化；
对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估计的绝对位置
进行加权全局优化；
[0105] 所述加权局部优化为：对选取的下一最优视图对应顶点的绝对位置，结合第一顶点集合中的绝对位置和第一边集合中各边连接的两个顶点之间测量得到的相对位置，计算
各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作
为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优
化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集
合；
各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作
为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优
化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集
合；
[0106] 所述加权全局优化为：对所有已估计绝对位置的顶点，结合各顶点的绝对位置和两两之间测量得到的相对位置，计算各外极几何边对应的相对位置误差，作为第二误差；若
第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝
对位置的顶点的绝对位置进行加权全局优化；
第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝
对位置的顶点的绝对位置进行加权全局优化；
[0107] 加权全局优化完成后，进一步通过所述加权全局优化方法对所有已估计绝对位置的顶点进行重平移平均化；
[0108] 在本实施例中，在下一最优视图选取后，选取顶点 的绝对位置被初始化为 ，为进一步提高绝对位置估计的准确度，本发明对当前已估计的绝对位置进行局部或全局优
化。局部优化只对最新估计的绝对位置进行优化而固定其他绝对位置，全局优化同时对集
合 中所有已估计的绝对位置进行优化。考虑到效率因素，本发明中的局
部优化与全局优化交替进行，并且仅在当前已估计的绝对位置达到一定的增长比率（本发
明中 优选设置为50%）时才进行全局优化。与初始四元组的选取和下一最优视图的选取类
似，本发明中的局部优化与全局优化也引入了加权的思想。此外，为应对增量式估计方案中
的漂移问题，在每次加权全局优化后，本发明还在局部外极几何图上进行重平移平均化。加
权局部与全局优化以及重平移平均化的具体流程叙述如下:
化。局部优化只对最新估计的绝对位置进行优化而固定其他绝对位置，全局优化同时对集
合 中所有已估计的绝对位置进行优化。考虑到效率因素，本发明中的局
部优化与全局优化交替进行，并且仅在当前已估计的绝对位置达到一定的增长比率（本发
明中 优选设置为50%）时才进行全局优化。与初始四元组的选取和下一最优视图的选取类
似，本发明中的局部优化与全局优化也引入了加权的思想。此外，为应对增量式估计方案中
的漂移问题，在每次加权全局优化后，本发明还在局部外极几何图上进行重平移平均化。加
权局部与全局优化以及重平移平均化的具体流程叙述如下:
[0109] 对于加权局部优化，在下一最优视图选取与初始化的基础上，首先求取内值边集合，公式如下：
[0110] （9）
[0111]
[0112] 其中， 表示第一顶点集合 与选取的下一最优视图对应顶点 之间连接边的集合， 为 中的任意一条边， 表示 中的内值边的集合， 表示边 连接
的两个相机之间的相对位置，表示顶点 当前的绝对位置估计值， 表示 初始化的
绝对位置， 表示各外极几何边对应的相对位置误差， 表示设定的误差阈值（即两个
位置之间夹角的误差阈值），本发明实验中为 。
的两个相机之间的相对位置，表示顶点 当前的绝对位置估计值， 表示 初始化的
绝对位置， 表示各外极几何边对应的相对位置误差， 表示设定的误差阈值（即两个
位置之间夹角的误差阈值），本发明实验中为 。
[0113] 随后，对顶点 的绝对位置 进行加权局部优化，公式如下：
[0114] （10）
[0115]
[0116] 其中， 表示绝对位置 加权局部优化后的结果， 表示 中的任意一条边， 表示边 连接的两个相机之间的相对位置。
[0117] 对于加权全局优化，与加权局部优化类似，首先需要从当前所有已估计绝对位置的边集合 中获取内值边集合 ，公式如下：
[0118] （11）
[0119]
[0120] 其中， 表示加权全局优化时的内值边集合， 表示所有已估计绝对位置的顶点之间的边集合， 表示 中的任意一条边， 表示边 连接的两个相
机之间的相对位置，表示顶点 当前的绝对位置估计值。
机之间的相对位置，表示顶点 当前的绝对位置估计值。
[0121] 随后，对集合 中的所有绝对位置进行加权全局优化，公式如下：
[0122] （12）
[0123]
[0124] 其中， 表示绝对位置集合 进行加权全局优化后的结果， 为 中的任意一条边， 表示边 连接的两个相机之间的相对位置。
[0125] 在加权全局优化后，对于重平移平均化，通过加权全局优化得到绝对位置集合，利用加权全局优化中的公式重新求取内值边集合，再次优化当前已估计的绝对位置，进一
步提高了本发明的准确性和鲁棒性。
步提高了本发明的准确性和鲁棒性。
[0126] 步骤S600，完成所有绝对位置的估计后，输出对所有可估计顶点进行加权全局优化和重平移平均化后的绝对位置，作为各相机绝对位置的最终估计结果。
[0127] 根据优化后相机的绝对位置获取点云在全局坐标系下的三维坐标，得到稀疏重建的结果。在此基础上，可以通过稠密重建、点云模型化等步骤，生成最终的三维模型。
[0128] 另外，为了验证本发明的效果，我们在1DSfM数据集上进行了测试实验，数据集的相关信息列于表1，表1中的ALM（ALM‑Alamo）、ELS（ELS‑Ellis Island）、MDR（MDR‑Madrid
Metrop）、MND（MND‑Montreal Notre Dame）、NYC（NYC‑NYC Library）、PDP（PDP‑Piazza del
Popolo）、PIC（PIC‑Piccadilly）、ROF（ROF‑Roman Forum）、TOL（TOL‑Tower of London）、USQ
（USQ‑Union Square）、VNC（VNC‑Vienna Cathedral）、YKM（YKM‑Yorkminster）表示数据集，
统称为1DSfM数据集，具体可参考文献：“K. Wilson and N. Snavely. Robust global
translations with 1DSfM. In European Conference on Computer Vision (ECCV),
pages 61–75, 2014.”。在实验中，我们将Bundler标定的结果作为相机绝对位置的真值，并
将绝对位置估计的误差中值作为评测指标。
Metrop）、MND（MND‑Montreal Notre Dame）、NYC（NYC‑NYC Library）、PDP（PDP‑Piazza del
Popolo）、PIC（PIC‑Piccadilly）、ROF（ROF‑Roman Forum）、TOL（TOL‑Tower of London）、USQ
（USQ‑Union Square）、VNC（VNC‑Vienna Cathedral）、YKM（YKM‑Yorkminster）表示数据集，
统称为1DSfM数据集，具体可参考文献：“K. Wilson and N. Snavely. Robust global
translations with 1DSfM. In European Conference on Computer Vision (ECCV),
pages 61–75, 2014.”。在实验中，我们将Bundler标定的结果作为相机绝对位置的真值，并
将绝对位置估计的误差中值作为评测指标。
[0129] 表1
[0130]
[0131] 为验证本发明中提出的关键技术的有效性，我们进行了若干消融实验，包括无基于局部优化的初始四元组选取（消融一），无基于加权支撑集合的下一最优视图选取（消融
二），无加权（消融三），无重平移平均化（消融四），无加权全局优化（消融五），无加权局部优
化（消融六），六种情况简述如下：
二），无加权（消融三），无重平移平均化（消融四），无加权全局优化（消融五），无加权局部优
化（消融六），六种情况简述如下：
[0132] 1）在无基于局部优化的初始四元组选取的情况下，初始种子视图选取为具有最小旋转循环偏差的相机三元组；
[0133] 2）在无基于加权支撑集合的下一最优视图选取的情况下，下一最优视图选取为与当前已估计绝对位置的相机连接边数最多的相机；
[0134] 3）在无权重的情况下，同等对待所有相对平移测量值；
[0135] 4）在无重平移平均化的情况下，每次加权全局优化后不再进行重平移平均化；
[0136] 5）在无加权全局优化的情况下，增量式绝对位置计算过程中不进行加权全局优化和重平移平均化；
[0137] 6）在无加权局部优化的情况下，增量式绝对位置计算过程中不进行任何优化操作，每个绝对位置均被设置为下一最优视图选取后给出的初始值。
[0138] 消融实验结果列于表2，由表可知：对大多数测试数据而言，所有消融实验中的平移平均化估计误差都是增大的，这表明本发明中提出的各项关键技术在提升方法的准确性
和鲁棒性方面均是有效的。
和鲁棒性方面均是有效的。
[0139] 表2
[0140]
[0141] 在对比实验中，我们将本发明方法与另外五种方法进行了对比，五种方法的对应文献分别为：
[0142] [1] Z. Cui and P. Tan. Global structure‑from‑motion by similarity averaging. In IEEE International Conference on Computer Vision (ICCV), pages
864–872, 2015.
864–872, 2015.
[0143] [2] C. Sweeney, T. Sattler, T. Höllerer, M. Turk, and M. Pollefeys. Optimizing the viewing graph for structure‑from‑motion. In IEEE International
Conference on Computer Vision (ICCV), pages 801–809, 2015.
Conference on Computer Vision (ICCV), pages 801–809, 2015.
[0144] [3] T. Goldstein, P. Hand, C. Lee, V. Voroninski, and S. Soatto. ShapeFit and ShapeKick for robust, scalable structure from motion. In
European Computer Vision (ECCV), pages 289–304, 2016.
European Computer Vision (ECCV), pages 289–304, 2016.
[0145] [4] B. Zhuang, L. Cheong, and G. H. Lee. Baseline desensitizing in translation averaging. In IEEE/CVF Conference on Computer Vision and Pattern
Recognition (CVPR), pages 4539–4547, 2018.
Recognition (CVPR), pages 4539–4547, 2018.
[0146] [5] Y. Kasten, A. Geifman, M. Galun, and R. Basri. Algebraic characterization of essential matrices and their averaging in multiview
settings. In IEEE/CVF International Conference on Computer Vision (ICCV),
pages 5894–5902, 2019.
settings. In IEEE/CVF International Conference on Computer Vision (ICCV),
pages 5894–5902, 2019.
[0147] 对比实验结果列于表3，由表可知：在所有进行对比的方法中，本发明提出的平移平均化方法在准确性和鲁棒性等方面达到了整体最优。在结果准确度的对比中，只有对比
实验一和对比实验四的结果与本发明的结果准确度相差较小，但这些方法需要用到附加信
息或初始化操作，如特征轨迹、局部捆绑调整和较为准确的初始值等，求解过程更加复杂。
实验一和对比实验四的结果与本发明的结果准确度相差较小，但这些方法需要用到附加信
息或初始化操作，如特征轨迹、局部捆绑调整和较为准确的初始值等，求解过程更加复杂。
[0148] 表3
[0149]
[0150] 本发明第二实施例的一种增量式平移平均化系统，如图2所示，该系统包括：外极几何图构造模块100、初始种子视图选取模块200、集合构建模块300、下一最优视图选取模
块400、优化模块500、绝对位置估计输出模块600；
块400、优化模块500、绝对位置估计输出模块600；
[0151] 所述外极几何图构造模块100，配置为获取多帧图像，进行两两图像之间的特征匹配，根据外极几何关系构造外极几何图 ，进而计算匹配图像对之间的相对旋转和
相对平移；其中，为顶点集合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不
同图像的相机两两之间的外极几何边的集合，包含了相机之间的运动信息；
相对平移；其中，为顶点集合，表示场景中拍摄图像的相机集合，为边集合，表示拍摄不
同图像的相机两两之间的外极几何边的集合，包含了相机之间的运动信息；
[0152] 所述初始种子视图选取模块200，配置为选取所述外极几何图中特征匹配数量最多的前 条边构成的相机四元组，构建四元组集合，并计算在局部坐标系下所述四元组集
合的各相机四元组中的每一个相机的绝对位置；结合各相机的绝对位置，计算所述四元组
集合中的各相机四元组的选取代价，并将选取代价最大的相机四元组对应的视图作为初始
种子视图；
合的各相机四元组中的每一个相机的绝对位置；结合各相机的绝对位置，计算所述四元组
集合中的各相机四元组的选取代价，并将选取代价最大的相机四元组对应的视图作为初始
种子视图；
[0153] 所述集合构建模块300，配置为将基于所述初始种子视图对应的顶点构建已估计绝对位置的顶点集合，作为第一顶点集合，将所述外极几何图中未估计绝对位置的顶点集
合，作为第二顶点集合；选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的
前 个顶点，构建第三顶点集合；
合，作为第二顶点集合；选取第二顶点集合中与第一顶点集合中所有顶点连接边数最多的
前 个顶点，构建第三顶点集合；
[0154] 所述下一最优视图选取模块400，配置为将所述第三顶点集合中的每个顶点与所述第一顶点集合中的顶点组成相机三元组，并通过线性三焦张量求解法计算所述第三顶点
集合中各顶点的绝对位置；根据求得的绝对位置计算各顶点的选取代价，并将选取代价最
大的顶点对应的视图作为下一最优视图；
集合中各顶点的绝对位置；根据求得的绝对位置计算各顶点的选取代价，并将选取代价最
大的顶点对应的视图作为下一最优视图；
[0155] 所述优化模块500，配置为固定第一顶点集合中已估计的相机绝对位置，仅对最新估计的下一最优视图对应顶点的绝对位置进行加权局部优化；完成加权局部优化后，判断
当前已估计绝对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估
计的绝对位置进行加权全局优化；
当前已估计绝对位置的顶点数量的增长比率，若该比率大于设定阈值，则对当前所有已估
计的绝对位置进行加权全局优化；
[0156] 所述加权局部优化为：对选取的下一最优视图对应顶点的绝对位置，结合第一顶点集合中的绝对位置和第一边集合中各边连接的两个顶点之间测量得到的相对位置，计算
各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作
为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优
化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集
合；
各边对应的相对位置误差，作为第一误差；若第一误差小于设定误差阈值，则将对应的边作
为内值边，进而基于 范数对选取的下一最优视图对应顶点的绝对位置进行加权局部优
化；所述第一边集合为第一顶点集合与选取的下一最优视图对应顶点之间外极几何边的集
合；
[0157] 所述加权全局优化为：对所有已估计绝对位置的顶点，结合各顶点的绝对位置和两两之间测量得到的相对位置，计算各外极几何边对应的相对位置误差，作为第二误差；若
第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝
对位置的顶点的绝对位置进行加权全局优化；
第二误差小于设定误差阈值，则将对应的边作为内值边，进而基于 范数对所有已估计绝
对位置的顶点的绝对位置进行加权全局优化；
[0158] 加权全局优化完成后，进一步通过所述加权全局优化方法对所有已估计绝对位置的顶点进行重平移平均化；
[0159] 所述绝对位置估计输出模块600，配置为完成所有绝对位置的估计后，输出对所有可估计顶点进行加权全局优化和重平移平均化后的绝对位置，作为各相机绝对位置的最终
估计结果。
估计结果。
[0160] 所述技术领域的技术人员可以清楚的了解到，为描述的方便和简洁，上述描述的系统具体的工作过程及有关说明，可以参考前述方法实施例中的对应过程，在此不再赘述。
[0161] 需要说明的是，上述实施例提供的增量式平移平均化系统，仅以上述各功能模块的划分进行举例说明，在实际应用中，可以根据需要而将上述功能分配由不同的功能模块
来完成，即将本发明实施例中的模块或者步骤再分解或者组合，例如，上述实施例的模块可
以合并为一个模块，也可以进一步拆分成多个子模块，以完成以上描述的全部或者部分功
能。对于本发明实施例中涉及的模块、步骤的名称，仅仅是为了区分各个模块或者步骤，不
视为对本发明的不当限定。
来完成，即将本发明实施例中的模块或者步骤再分解或者组合，例如，上述实施例的模块可
以合并为一个模块，也可以进一步拆分成多个子模块，以完成以上描述的全部或者部分功
能。对于本发明实施例中涉及的模块、步骤的名称，仅仅是为了区分各个模块或者步骤，不
视为对本发明的不当限定。
[0162] 本发明第三实施例的一种电子设备，至少一个处理器；以及与至少一个所述处理器通信连接的存储器；其中，所述存储器存储有可被所述处理器执行的指令，所述指令用于
被所述处理器执行以实现权利要求上述的增量式平移平均化方法。
被所述处理器执行以实现权利要求上述的增量式平移平均化方法。
[0163] 本发明第四实施例的一种计算机可读存储介质，所述计算机可读存储介质存储有计算机指令，所述计算机指令用于被所述计算机执行以实现权利要求上述的增量式平移平
均化方法。
均化方法。
[0164] 所述技术领域的技术人员可以清楚的了解到，为描述的方便和简洁，上述描述的设备、计算机可读存储介质的具体工作过程及有关说明，可以参考前述方法实例中的对应
过程，在此不再赘述。
过程，在此不再赘述。
[0165] 下面参考图4，其示出了适于用来实现本申请方法、系统、装置实施例的服务器的计算机系统的结构示意图。图4示出的服务器仅仅是一个示例，不应对本申请实施例的功能
和使用范围带来任何限制。
和使用范围带来任何限制。
[0166] 如图4所示，计算机系统包括中央处理单元(CPU，Central Processing Unit)401，其可以根据存储在只读存储器(ROM，Read Only Memory)402中的程序或者从存储部分408
加载到随机访问存储器(RAM，Random Access Memory)403中的程序而执行各种适当的动作
和处理。在RAM 403中，还存储有系统操作所需的各种程序和数据。CPU 401、ROM 402以及
RAM 403通过总线404彼此相连。输入/输出(I/O，Input/Output)接口405也连接至总线404。
加载到随机访问存储器(RAM，Random Access Memory)403中的程序而执行各种适当的动作
和处理。在RAM 403中，还存储有系统操作所需的各种程序和数据。CPU 401、ROM 402以及
RAM 403通过总线404彼此相连。输入/输出(I/O，Input/Output)接口405也连接至总线404。
[0167] 以下部件连接至I/O接口405：包括键盘、鼠标等的输入部分406；包括诸如阴极射线管(CRT，Cathode Ray Tube)、液晶显示器(LCD，Liquid Crystal Display)等以及扬声器
等的输出部分407；包括硬盘等的存储部分408；以及包括诸如LAN(局域网，Local Area
Network)卡、调制解调器等的网络接口卡的通讯部分409。通讯部分409经由诸如因特网的
网络执行通信处理。驱动器410也根据需要连接至I/O接口405。可拆卸介质411，诸如磁盘、
光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器410上，以便于从其上读出的计算
机程序根据需要被安装入存储部分408。
等的输出部分407；包括硬盘等的存储部分408；以及包括诸如LAN(局域网，Local Area
Network)卡、调制解调器等的网络接口卡的通讯部分409。通讯部分409经由诸如因特网的
网络执行通信处理。驱动器410也根据需要连接至I/O接口405。可拆卸介质411，诸如磁盘、
光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器410上，以便于从其上读出的计算
机程序根据需要被安装入存储部分408。
[0168] 特别地，根据本公开的实施例，上文参考流程图描述的过程可以被实现为计算机软件程序。例如，本公开的实施例包括一种计算机程序产品，其包括承载在计算机可读介质
上的计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。在这样的实
施例中，该计算机程序可以通过通讯部分409从网络上被下载和安装，和/或从可拆卸介质
411被安装。在该计算机程序被中央处理单元(CPU)401执行时，执行本申请的方法中限定的
上述功能。需要说明的是，本申请上述的计算机可读介质可以是计算机可读信号介质或者
计算机可读存储介质或者是上述两者的任意组合。计算机可读存储介质例如可以是——但
不限于——电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。
计算机可读存储介质的更具体的例子可以包括但不限于：具有一个或多个导线的电连接、
便携式计算机磁盘、硬盘、随机访问存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存
储器(EPROM或闪存)、光纤、便携式紧凑磁盘只读存储器(CD‑ROM)、光存储器件、磁存储器
件、或者上述的任意合适的组合。在本申请中，计算机可读存储介质可以是任何包含或存储
程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。而在
本申请中，计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信
号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括但不
限于电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机
可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用
于由指令执行系统、装置或者器件使用或者与其结合使用的程序。计算机可读介质上包含
的程序代码可以用任何适当的介质传输，包括但不限于：无线、电线、光缆、RF等等，或者上
述的任意合适的组合。
上的计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。在这样的实
施例中，该计算机程序可以通过通讯部分409从网络上被下载和安装，和/或从可拆卸介质
411被安装。在该计算机程序被中央处理单元(CPU)401执行时，执行本申请的方法中限定的
上述功能。需要说明的是，本申请上述的计算机可读介质可以是计算机可读信号介质或者
计算机可读存储介质或者是上述两者的任意组合。计算机可读存储介质例如可以是——但
不限于——电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。
计算机可读存储介质的更具体的例子可以包括但不限于：具有一个或多个导线的电连接、
便携式计算机磁盘、硬盘、随机访问存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存
储器(EPROM或闪存)、光纤、便携式紧凑磁盘只读存储器(CD‑ROM)、光存储器件、磁存储器
件、或者上述的任意合适的组合。在本申请中，计算机可读存储介质可以是任何包含或存储
程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。而在
本申请中，计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信
号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括但不
限于电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机
可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用
于由指令执行系统、装置或者器件使用或者与其结合使用的程序。计算机可读介质上包含
的程序代码可以用任何适当的介质传输，包括但不限于：无线、电线、光缆、RF等等，或者上
述的任意合适的组合。
[0169] 可以以一种或多种程序设计语言或其组合来编写用于执行本申请的操作的计算机程序代码，上述程序设计语言包括面向对象的程序设计语言—诸如Java、Smalltalk、C+
+，还包括常规的过程式程序设计语言—诸如“C”语言或类似的程序设计语言。程序代码可
以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、
部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。
在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络——包括局域网(LAN)
或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务
提供商来通过因特网连接)。
+，还包括常规的过程式程序设计语言—诸如“C”语言或类似的程序设计语言。程序代码可
以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、
部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。
在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络——包括局域网(LAN)
或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务
提供商来通过因特网连接)。
[0170] 附图中的流程图和框图，图示了按照本申请各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代
表一个模块、程序段、或代码的一部分，该模块、程序段、或代码的一部分包含一个或多个用
于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标
注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连表示的方框实际上可
以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意
的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行
规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的
组合来实现。
表一个模块、程序段、或代码的一部分，该模块、程序段、或代码的一部分包含一个或多个用
于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标
注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连表示的方框实际上可
以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意
的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行
规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的
组合来实现。
[0171] 术语“第一”、 “第二”等是用于区别类似的对象，而不是用于描述或表示特定的顺序或先后次序。
[0172] 术语“包括”或者任何其它类似用语旨在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备/装置不仅包括那些要素，而且还包括没有明确列出的
其它要素，或者还包括这些过程、方法、物品或者设备/装置所固有的要素。
其它要素，或者还包括这些过程、方法、物品或者设备/装置所固有的要素。
[0173] 至此，已经结合附图所示的优选实施方式描述了本发明的技术方案，但是，本领域技术人员容易理解的是，本发明的保护范围显然不局限于这些具体实施方式。在不偏离本
发明的原理的前提下，本领域技术人员可以对相关技术特征作出等同的更改或替换，这些
更改或替换之后的技术方案都将落入本发明的保护范围之内。
发明的原理的前提下，本领域技术人员可以对相关技术特征作出等同的更改或替换，这些
更改或替换之后的技术方案都将落入本发明的保护范围之内。