Hybrid Parallel Bundle Adjustment for 3D Scene Reconstruction with Massive Points

Bundle adjustment(BA) is a crucial but time consuming step in 3D reconstruction.In this paper,we intend to tackle a special class of BA problems where the reconstructed 3D points are much more numerous than the camera parameters,called Massive-Points BA(MPBA) problems.This is often the case when high-resolution images are used.We present a design and implementation of a new bundle adjustment algorithm for efficiently solving the MPBA problems.The use of hardware parallelism,the multi-core CPUs as well as GPUs,is explored.By careful memory-usage design,the graphic-memory limitation is effectively alleviated.Several modern acceleration strategies for bundle adjustment,such as the mixed-precision arithmetics,the embedded point iteration,and the preconditioned conjugate gradients,are explored and compared.By using several high-resolution image datasets,we generate a variety of MPBA problems,with which the performance of five bundle adjustment algorithms are evaluated.The experimental results show that our algorithm is up to 40 times faster than classical Sparse Bundle Adjustment,while maintaining comparable precision.     

面向大规模三维重建的快速鲁棒集束调整算法

集束调整是运动推断结构的核心,针对现有算法在大规模场景下易受外点影响,空间占用率过高和效率较低问题,提出一种快速鲁棒的集束调整(fast and robust bundle adjustment,FRBA)算法.首先,为了避免外点(outliers)的影响,采用Cauchy损失降低外点的权重,提高算法精度.其次,充分利用运动推断结构中三维点与摄像机之间的稀疏性对大规模集束调整进行稀疏分解,降低内存空间的使用.最后,根据稀疏分解后矩阵的固有特性,采用快速矩阵分解法求解正态方程的解.在合成数据集、BAL数据集和真实图像数据集上对FRBA算法进行测试,并与现有经典算法进行比较.实验结果表明无论在时间效率还是精度上,FRBA算法均处于领先位置.     

面向嵌入式平台的单目ORB-SLAM稠密化建图实现

针对现有方法在机器人室内定位中无法同时满足高精度定位、快速处理及稠密地图重建的问题,在拥有跟踪、地图构建和回环检测三线程的ORB-SLAM3系统基础上设计了三维稠密地图构建算法,分别在跟踪阶段、局部光束法平差阶段（bundle adjustment,BA）和全局BA阶段,对满足需求的关键帧进行二次采样和位姿更新,然后通过关键帧和对应位姿计算得到三维点云,最终获得稠密地图。实验结果表明,所提方法在Jetson AGX Xavier嵌入式平台上对TUM数据集的定位速度达到了10.8?frame/s,均方根误差仅有0.213%,验证了该系统的高精度与快速性,可以满足机器人室内定位与建图需求。     

电子经纬仪测量大型圆柱构件同轴度转站新方法

为了提高电子经纬仪测量大型圆柱构件同轴度的精度,提出一种基于多公共点的测量转站方法,使得电子经纬仪可以在不严格调水平的状态下进行测量。该方法以捆集调整(bundle adjustment)为基础,采用基于模式搜索的Hooke-Jeeves算法求解非线性最优化问题,提高了转站测量精度。实验表明该方法与基于两公共点电子经纬仪严格调水平状态测量方法相比较,不仅提高了测量效率,最大偏差也由原来的±6 mm缩小到±3 mm。     

基于雷达复杂1维距离数据的3维重建算法

基于刚体目标3维运动过程中的几何不变性,可以利用目标上多个散射点在单天线雷达1维距离像序列中的1维距离数据,重建出目标未知的3维结构和运动路径。针对此1维到3维的几何重构问题,提出了一种雷达刚体目标结构和运动的3维重建算法,该算法可利用散射点复杂的1维距离数据进行重建,并且采用非线性优化技术实现了对目标重建参数的捆绑调整(bundle adjustment)。另外,该算法中引入了目标的平移模型,使目标的平移参数能够与旋转参数一并求解,从而避免了距离对准操作的误差对重建精度的影响。仿真实验结果表明,由于重建数据中散射点的数量以及目标3维运动的丰富性得到了显著提高,尤其是最优化技术在算法中的成功应用,重建算法的鲁棒性得到了有效增强。     

基于引力模型的三维运动点集的非精确匹配

本文提出了一种基于引力模型(attractive model)的非精确匹配算法,应用于三维空间运动点集的对应点匹配问题.根据引力模型,我们将匹配和运动估计问题转化为一个代价函数的全局优化问题,实现了无对应点的运动估计和总体匹配.这种算法是一个鲁棒(robust)估计和匹配方法,可以处理包含非匹配点对的三维运动点集.大量计算机模拟实验结果充分证明了算法的鲁棒性和有效性.     

PLA分解与输入变量最小集的求解方法

寻求函数输入变量最小集和函数列阵分解问题,无论对于PLA或门阵列的制版布线及测试设计都是十分重要的。本文将它们统一考虑为用求解质蕴涵项表的覆盖矩阵取补(锐积)法求解。实际上PLA分解需要两次求解覆盖问题。首先求出各子列阵输入变量的全部最小集(或无冗余子集);然后再寻求其输入变量最小集能够覆盖全部子列阵输入变量最小集的一组子列阵,于是便获得函数列阵的分解结果。 本文针对上述这类规模较大的覆盖问题,围绕如何提高速度、节省内存,运用覆盖矩阵取补法构造出寻求输入变量最小集及PLA分解的算法。其特点是规则性强,实现方便,几乎不需另外占用内存便可求解出这些规模较大的覆盖问题。根据这些算法构成的自动逻辑综合软件可用于以寄存器传输级硬件描述语言(如DDL、AHPL等)为输入的计算机设计自动化系统。     

基于DBP的TOp-k高效用项集挖掘算法

针对Top-k高效用项集挖掘算法在挖掘过程中忽略内存管理的问题,提出基于DBP的Top-k高效用项集挖掘算法TKBPH(Top-k buffer pool high utility itemsets mining),采用数据缓冲池(DBP)结构存储效用链表,并由索引链表记录效用链表在DBP的位置.数据缓冲池根据挖掘过程情况在数据缓冲池尾部动态插入和删除效用链表,通过索引链表直接读取效用链表避免项集搜索时频繁的比较操作,有效减少内存空间和运行时间消耗.不同类型数据集上的实验结果表明,TKBPH算法在挖掘过程中执行速度更快、内存消耗更少.     

基于超节点LDL分解的大规模结构计算

采用列压缩稀疏(Compressed Sparse Column,CSC)矩阵存储策略对矩阵LDL分解前进行填充元优化排序;基于消去树进行LDL符号分解,使之独立于数值分解,避免多余的内存消耗,减少不必要的数值运算.利用矩阵非零元的分布特性分析并实现超节点LDL分解算法,将稀疏矩阵的分解运算变为一系列稠密矩阵运算,并使用优化的BLAS函数库加速分解.测试表明:算法在成倍地提高计算速度的同时进一步降低内存消耗,适用于大规模的结构计算.     

大规模三维点云快速拾取技术研究

为三维点云处理系统点云查询与交互编辑功能的实现,在系统总结当前计算机三维图形拾取主要方法的基础上,提出三维点云拾取基本方法.针对实际LiDAR(激光雷达)点云处理中往往为大规模点云数据,通过层次包围盒引入四叉树,提出了基于四叉树的大规模三维点云快速拾取系列算法,并从提高四叉树构建速度、降低四叉树内存占用角度,采取有效策略,使得算法整体效率得到进一步优化,实验结果表明算法在大规模三维点云拾取速度和精度上均达到了很好的效果.     

Robust bundle adjustment for large-scale structure from motion

Bundle adjustment (BA) is the problem of refining a visual reconstruction to produce jointly optimal 3D structure and viewing parameter (camera pose and or calibration) estimates, and it is almost always used as the last step of feature-based 3D reconstruction algorithm. Generally, the result of Structure from Motion (SFM) mainly relies on the quality of BA. The problem of BA is often formulated as a nonlinear least squares problem, where the data arises from keypoints matching. For 3D reconstruction, mismatched keypoints may cause serious problems, even a single mismatch will affect the entire reconstruction. Therefore, to further impove the robustness of BA algorithm is very necessary. In this paper, we propose a robust Bundle Adjustment (RBA) algorithm to optimize the initial 3D point-clouds and camera parameters which are produced by the SFM system. In the proposed RBA algorithm, we firstly use the Huber loss function to potentially down-weight outliers. Secondly, we split a large-scale bundle adjustment problem into some small ones by making use of the sparsity between 3D points and the cameras for reducing the requirements of memory. Thirdly, according to the inherent property of the matrix after it spare decompose, we use a fast matrix factorization algorithm to solve the normal equation to avoid calculating the inverse of large-scale matrix. Finally, we evaluate the proposed RBA method and compare it with the state-of-the-art methods on the synthetic dataset, BAL benchmark and real image datasets, respectively. Experimental results show that the proposed RBA method clearly outperforms the state-of-the-art methods on both computational cost and precision.     

Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication

Sparse bundle adjustment (SBA) is a key but time- and memory-consuming step in three-dimensional (3D) reconstruction. In this paper, we propose a 3D point-based distributed SBA algorithm (DSBA) to improve the speed and scalability of SBA. The algorithm uses an asynchronously distributed sparse bundle adjustment (A-DSBA) to overlap data communication with equation computation. Compared with the synchronous DSBA mechanism (SDSBA), A-DSBA reduces the running time by 46%. The experimental results on several 3D reconstruction datasets reveal that our distributed algorithm running on eight nodes is up to five times faster than that of the stand-alone parallel SBA. Furthermore, the speedup of the proposed algorithm (running on eight nodes with 48 cores) is up to 41 times that of the serial SBA (running on a single node).     

Robust refinement methods for camera calibration and 3D reconstruction from multiple images

This paper proposes robust refinement methods to improve the popular patch multi-view 3D reconstruction algorithm by Furukawa and Ponce (2008). Specifically, a new method is proposed to improve the robustness by removing outliers based on a filtering approach. In addition, this work also proposes a method to divide the 3D points in to several buckets for applying the sparse bundle adjustment algorithm (SBA) individually, removing the outliers and finally merging them. The residuals are used to filter potential outliers to reduce the re-projection error used as the performance evaluation of refinement. In our experiments, the original mean re-projection error is about 47.6. After applying the proposed methods, the mean error is reduced to 2.13.     

基于未标定多幅图的三维重建算法

为得到鲁棒的三维重建效果,提出了一种基于未标定多幅图像的三维重建算法。该算法首先采用Harris算法检测特征点,针对双向匹配算法匹配速度慢的缺点,使用改进的双向匹配算法进行特征点匹配,在已知摄像机参数的情况下进行两幅图的三维重建;接着采用四元数算法进行坐标转换,将由每两幅图得到的不同部分的重建结果转移到同一坐标系下,实现了多幅图像的三维重建;最后利用集束调整优化重建结果。实验结果证明,该算法能获得比较满意的重建效果。     

线性多视图重构的新算法

研究了由多幅图像恢复摄像机矩阵和空间物体三维几何形状这一多视图三维重构问题,改进了由Hartley和Rother等人分别给出的基于由无穷远平面诱导的单应进行射影重构的算法,提出了一种新的线性算法,它仅需要空间中3个点在每幅图像上均可见。因为空间中不在同一直线上的3个点恰好确定一个平面,所以它避免了Hartley和Rother等方法中需要确定空间4个点是否共面这一比较棘手的问题。大量实验结果表明,这种方法快速、准确且受噪声影响小。     

Weak-perspective structure from motion by fast alternation

This paper addresses the problem of moving object reconstruction. Several methods have been published in the past 20 years including stereo reconstruction as well as multi-view factorization methods. In general, reconstruction algorithms compute the 3D structure of the object and the camera parameters in a non-optimal way, and then a nonlinear and numerical optimization algorithm refines the reconstructed camera parameters and 3D coordinates. In this paper, we propose an adjustment method which is the improved version of the well-known Tomasi–Kanade factorization method. The novelty, which yields the high speed of the algorithm, is that the core of the proposed method is an alternation and we give optimal solutions to the subproblems in the alternation. The improved method is discussed here and it is compared to the widely used bundle adjustment algorithm.     

一种基于场景图分割的混合式多视图三维重建方法

针对大范围三维重建, 重建效率较低和重建稳定性、精度差等问题, 提出了一种基于场景图分割的大范围混合式多视图三维重建方法.该方法首先使用多层次加权核K均值算法进行场景图分割; 然后,分别对每个子场景图进行混合式重建, 生成对应的子模型, 通过场景图分割、混合式重建和局部优化等方法提高重建效率、降低计算资源消耗, 并综合采用强化的最佳影像选择标准、稳健的三角测量方法和迭代优化等策略, 提高重建精度和稳健性; 最后, 对所有子模型进行合并, 完成大范围三维重建.分别使用互联网收集数据和无人机航拍数据进行了验证, 并与1DSFM、HSFM算法在计算精度和计算效率等方面进行了比较.实验结果表明, 本文算法大大提高了计算效率、计算精度, 能充分保证重建模型的完整性, 并具备单机大范围场景三维重建能力.     

Projective Reconstruction from Multiple Views with Minimization of 2D Reprojection Error

The problem of projective reconstruction by minimization of the 2D reprojection error in multiple images is considered. Although bundle adjustment techniques can be used to minimize the 2D reprojection error, these methods being based on nonlinear optimization algorithms require a good starting point. Quasi-linear algorithms with better global convergence properties can be used to generate an initial solution before submitting it to bundle adjustment for refinement. In this paper, we propose a factorization-based method to integrate the initial search as well as the bundle adjustment into a single algorithm consisting of a sequence of weighted least-squares problems, in which a control parameter is initially set to a relaxed state to allow the search of a good initial solution, and subsequently tightened up to force the final solution to approach a minimum point of the 2D reprojection error. The proposed algorithm is guaranteed to converge. Our method readily handles images with missing points.     

大场景三维重建中多核并行捆集调整算法

将三维重建中捆集调整算法用于优化重建结果,是非常关键的步骤,然而传统单核串行算法耗时量大不太适合大场景重建。对此,首先对捆集调整算法本身进行了改进;然后在此基础上提出了多核并行捆集调整算法并采用图像处理器(GPU)实现该算法。实验表明,所提出的多核并行捆集调整算法提高了算法优化参数的精度和处理速度。