关 闭

新闻中心

EEPW首页 > 工控自动化 > 设计应用 > 一种基于Kinect的点云配准算法

一种基于Kinect的点云配准算法

作者:赵琨时间:2016-04-26来源:电子产品世界收藏
编者按:三维点云配准是三维重建和增强现实中的关键技术,也是计算机视觉领域的重要研究方向。最近点迭代法(ICP Iterative Closest Point)是当前应用最广泛的三维点云配准算法之一。本文将分支与定界算法(Branch-and-Bound, BnB)引入三维点云配准,在解空间中,采用BnB算法做全局搜索,从根本上解决局部搜索的缺陷,与此同时,我们在定界中融合了抽样一致初始配准算法(SAC-IA),从而加快了算法的运算速度。实验表明,本算法在配准中取得了很好的效果。

摘要是三维重建和增强现实中的关键技术,也是计算机视觉领域的重要研究方向。最近点迭代法(ICP Iterative Closest Point)是当前应用最广泛的算法之一。本文将分支与定界算法(Branch-and-Bound, BnB)引入,在解空间中,采用BnB算法做全局搜索,从根本上解决局部搜索的缺陷,与此同时,我们在定界中融合了算法(SAC-IA),从而加快了算法的运算速度。实验表明,本算法在配准中取得了很好的效果。

本文引用地址:http://www.eepw.com.cn/article/201604/290273.htm

引言

  对真实世界场景进行三维感知与建模是计算机视觉和机器人领域的一项重要任务。国内外的研究者针对三维重建进行了广泛的研究。近年来,随着Kinect(如图1)的问世和不断发展,基于深度摄像机的诸多算法被越来越广泛地应用于三维重建、实时定位与绘图和机器人等领域。尤其是在三维重建中,RGB-D摄像机因其同步获取场景RGB图像和深度图的特点,使其很快成为三维重建的主要感知设备,极大推动了三维重建技术的进步。在实际重建过程中,往往因为传感器的有效探测距离限制和场景遮挡的存在,需要将多帧采集的图像序列融合到一个统一坐标系下的模型中,实现这样目标的关键技术就是3D配准。

  正因为3D配准在计算机视觉领域的应用中常常作为一个关键环节,研究者们已经针对这个问题提出了许多算法,其中最近点迭代法(ICP)是著名的配准算法。上个世纪90年代,ICP首次由Chen和McKay等人提出[1-2],在随后的二十多年中ICP不断得到改进,衍生出了许多改进版本,以至于后来的研究者很难能够完全列举出所有基于ICP的配准算法,不过,最近发表的一篇综述[3]已经列举出了一些具有代表性的ICP版本。

  尽管最近点迭代算法ICP具有思路简单直观、效果理想的优点,成为三维重建中应用最广泛的配准算法,并成功引用于计算机视觉领域。但是有一个难点,在应用ICP进行配准之前,需要给出待配准数据的初始估值,如果初始估值不恰当的话,将使ICP收敛过程步入歧途,导致配准陷入局部最优化。

  为了克服陷入局部最优化,有一类针对ICP的改进将重点放在了能量函数。这类方法是用更具鲁棒性的范数来代替原算法中的范数,如[4]中的LI和[5]中的LP。这两种方法显著提高了大量噪声和局外点鲁棒性,一定程度上克服了解空间陷入局部最优的缺陷。但是在取得了上述进步的同时,也引入了解空间非凸非平滑的问题。

  另一类对于ICP的改进是基于统计学的方法。Jian等人[6]提出的改进是基于高斯混合模型。Billings等人[7]提出的IMLP也属于基于统计学方法的ICP改进。尽管这类方法一定程度上克服了局部最优化的缺陷,并且算法思路很具有说服性,但是它们的优化方法仍然是采用局部搜索的方式。

  还有一类ICP的改进算法应用了三维点云的特征点提取与匹配[8-11]。通常,这类方法的算法框架可以归纳为两部分。首先,采用一种特征点提取算法分别在待配准点云中提取出特征点子集,并且在子集中利用特征描述符建立对应点对的匹配关系;然后,ICP算法利用这些已经匹配点对建立刚体转换关系,从而最终获得全集的配准结果。有些算法还会在配准后应用闭环检测和全局优化算法对结果进行校正。虽然这类方法克服了对精确配准初值的依赖,但是它们并没有做到全局最优化。而且高效鲁棒的三维特征点提取与匹配算法本身也是一个具有挑战性的研究课题。

  分支定界(BnB)是一个最近在计算机视觉领域得到越来越多应用的全局最优化通用框架[12-14]。在三维配准中,Hartley等人[12]提出的旋转空间搜索方法能够在仅有旋转运动的情况下获得全局最优的配准结果。本文算法将这种BnB框架扩展到平移空间,从而获得通常情况下全局最优的配准结果,为了提高算法的效率,我们会将(SAC-IA)嵌套在分支定界框架中来加速算法。

1 三维点云配准与ICP算法

  我们定义待配准点云中,当前点云记为,其中;目标点云记为,其中piqj分别表示当前点云和目标点云中的一个任意点,即。ICP算法将在以下两个步骤间迭代:

  1)在PsPt间计算匹配的最邻近点对:

(1)

  2)通过最小化下列L2范数形式的误差目标函数E,计算最邻近匹配点对的刚体运动

(2)

  ICP的具体描述如下:

2 本文提出的算法

2.1 分支定界框架

  分支定界是一个用途广泛的算法,其基本思想是对有约束条件的最优化问题的完全可行解空间进行搜索。该算法在执行过程中,将全部可行解空间不断分割为越来越小的子集(分支),并为每个子集计算一个上界或下界(定界),凡是超过已知界限的子空间将被舍弃,从而缩小搜索范围,直到求得最优解。以下是通用BnB框架的具体描述:

2.2 三维配准中可行解空间的参数化

  将分支定界算法应用于三维点云配准问题的一个重要前提是可行解空间的参数化,只有实现了解空间的参数化,才可以将连续的优化转换成离散问题。下面将分别介绍本文采用的参数化模型。

  1)旋转空间

  因为配准的数学化目标是公式(2)中误差目标函数的最小化。所以本文采用图2所示的角轴表示来参数化旋转空间。

  对于任意一个旋转在图2中用向量表示,的模表示绕旋转轴旋转的角度,所以g可以用表示。

  2)平移空间

  对于平移空间的参数化,本文采用图3所示的一个边界值为的正方体来表示。设定为能够使得待匹配点云产生重叠的最小值,立方体内的任意一点的坐标(x,y,z)即表示一个空间中的平移运动。

2.3 嵌套的BnB

  在解决了三维配准中可行解空间的参数化问题的前提下,在应用分支定界算法前还要解决的一个问题是上下界的确定。

  假设对于一个旋转空间的子集Cr,其空间半边长记为,空间的中心对应一个旋转记为ro,P为点云中一个点,易得到如下结论:

(3)

表示空间Cr对应的旋转漂移半径。

  假设对于一个平移空间的子集Ct,其空间半边长记为,空间的中心对应一个平移记为toP为点云中一个点,我们有如下结论:

(4)

  rt是Ct对应的平移漂移半径。

  将上述结论应用到一般的三维场景中,即同时存在一个旋转子集Cr和平移子集Ct,对于空间中任意一点pi,公式(2)中的残差函数与公式(3)(4)结合可以得到如下结论:

(5)

  因此本文定义残差函数上界如下式:

 (6)

  由公式(5)得到残差函数下界如下式:

(7)

  将点云中每个点的上下界做黎曼和即为本文分支定界算法的上下界函数,即:

 (8)

 (9)

2.4 集成SAC-IA

  当本文的分支定界执行到第9行时,算法找到了一个更加接近最优解的子集,此时利用SAC-IA求得相比于子集中心更加精确的运动估计来更新目前为止的上界阈值。以这种形式集成SAC-IA可以加快分支定界的搜索,忽略不必要的多余空间。

3 实验与分析

  为验证本文提出的算法,我们采用目前国际上应用广泛的配准素材进行对比实验(Stanford models)。我们使用的实验环境是一台Windows 7系统的工作站,配备Intel Xeon 2.0GHz CPU和16G内存。对比的算法包括Standard ICP、Point-to-Point ICP、Point-to-Plane ICP和近年来提出的GICP。借助于库PCL,我们可以很方便地实现上述对比算法。在衡量算法精度时,本文分别计算配准后最邻近点对间欧氏距离的最小值、最大值以及均方根误差RMSE。在验证算法效率时,本文记录各算法配准过程所消耗的物理时间,实验结果如表1所示。图4所示为本文算法的直观结果。

  从配准的统计和直观结果可以清晰看出,本文提出的算法在精度和效率上都超过了对比算法,同时直观配准结果也显示了本文算法取得了良好的配准结果。

4 结论

  本文提出了一种基于分支定界的三维点云配准算法。该算法一方面利用分支定界的框架,在配准问题的完全可行域中搜索最优解,克服了传统配准算法容易陷入局部最优化的缺陷;另一方面通过集成SAC-IA算法,加速分支定界的过程,忽略不必要的可行域子集,克服了传统分支定界时间效率低的缺陷,同时保持了配准算法的高效性。对比实验结果表明,本文算法达到了有效克服局部最优化的目的,精度更高,速度更快,取得了理想的配准效果。

参考文献:

  [1]Y. Chen and G. Medioni, “Object modeling by registration of multiple range images,” in Robotics and Automation, 1991. Proceedings., 1991 IEEE International Conference on. IEEE, 1991, pp. 2724–2729

  [2]P. J. Besl and N. D. McKay, “Method for registration of 3-d shapes,” in Robotics-DL tentative. International Society for Optics and Photonics, 1992, pp. 586–606

  [3]F. Pomerleau, F. Colas, R. Siegwart, and S. Magnenat, “Comparing icp variants on real-world data sets,” Autonomous Robots, vol. 34, no. 3, pp. 133–148, 2013

  [4]A. W. Fitzgibbon, “Robust registration of 2d and 3d point sets,” Image and Vision Computing, vol. 21, no. 13, pp. 1145–1153, 2003

  [5]S. Bouaziz, A. Tagliasacchi, and M. Pauly, “Sparse iterative closest point,” in Computer graphics forum, vol. 32, no. 5. Wiley Online Library, 2013, pp. 113–123

  [6]B. Jian and B. C. Vemuri, “A robust algorithm for point set registration using mixture of gaussians,” in Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, vol. 2. IEEE, 2005, pp. 1246–1251

  [7]S. D. Billings, E. M. Boctor, and R. H. Taylor, “Iterative most-likely point registration (imlp): a robust algorithm for computing optimal shape alignment,” PloS one, vol. 10, no. 3, 2015

  [8]A. S. Huang, A. Bachrach, P. Henry, M. Krainin, D. Maturana, D. Fox, and N. Roy, “Visual odometry and mapping for autonomous flight using an rgb-d camera,” in International Symposium on Robotics Research (ISRR), 2011, pp. 1–16

  [9]J. Xie, Y.-F. Hsu, R. S. Feris, and M.-T. Sun, “Fine registration of 3d point clouds with iterative closest point using an rgb-d camera,” in Circuits and Systems (ISCAS), 2013 IEEE International Symposium on. IEEE, 2013, pp. 2904–2907

  [10]X. Li, W. Li, H. Jiang, and H. Zhao, “Automatic evaluation of machining allowance of precision castings based on plane features from 3d point cloud,” Computers in Industry, vol. 64, no. 9, pp. 1129–1137, 2013

  [11]M. Salem, H. Ramadan, M. I. Roushdy et al., “Comparison of 3d feature registration techniques for indoor mapping,” in Computer Engineering & Systems (ICCES), 2013 8th International Conference on. IEEE, 2013, pp. 239–244

  [12]R. I. Hartley and F. Kahl, “Global optimization through rotation space search,” International Journal of Computer Vision, vol. 82, no. 1, pp. 64–79, 2009

  [13]M. Sun, M. Telaprolu, H. Lee, and S. Savarese, “An efficient branchand-bound algorithm for optimal human pose estimation,” in Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on.IEEE, 2012, pp. 1616–1623

  [14]C. Yu, Y. Seo, and S. W. Lee, “Global optimization for estimating a brdf with multiple specular lobes,” in Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010, pp. 319–326


本文来源于中国科技期刊《电子产品世界》2016年第4期第31页,欢迎您写论文时引用,并注明出处。



评论


技术专区

关闭