基于信息论的KL-Reg点云配准算法

秦红星徐 雷

(重庆邮电大学计算智能重庆市重点实验室 重庆 400065)

(重庆邮电大学计算机科学与技术学院 重庆 400065)

基于信息论的KL-Reg点云配准算法

秦红星*徐 雷

(重庆邮电大学计算智能重庆市重点实验室 重庆 400065)

(重庆邮电大学计算机科学与技术学院 重庆 400065)

针对含有高噪声、体外点及不完整点云数据的配准失效问题，该文提出以信息论为理论基础，相对熵度量点云相似度的KL-Reg算法。该算法不需要显式地建立对应关系，首先将点云数据建模为高斯混合模型，然后用相对熵度量高斯混合模型间的分布距离，最后通过最小化分布距离计算模型变换。实验结果表明所提的KL-Reg算法配准精度高、稳定性强。

机器视觉；点云配准；KL散度；高斯混合模型

1 引言

点云数据配准是计算机视觉和计算机图形学中的重要研究内容，是3维重建、图像配准[1]和3维形状检索[2,3]的核心技术，其主要目的是寻找一个模型变换以实现两幅点云的对齐。点云配准过程面临许多挑战。首先，数据本身存在的高噪声、体外点等会影响配准精度；其次，在3维数据采集过程中，由于扫描仪的视角和自遮挡问题，获得的数据经常存在缺失或者只有少部分重合等问题。使得寻找点到点的对应关系变得非常困难，并由于点云间对应不准确往往造成配准失效。另外，点云数据的初始位置也会影响配准算法的性能。

目前的点云配准算法主要分为3类：迭代最近点配准算法ICP(Iterate Closed Point)[4,5]、基于统计的方法和基于特征对应的配准方法。1992年Besl和McKay提出了ICP[4]算法，该方法以欧式距离最近的点对作为对应点对，思想简单、易于实现是最常用的点云配准算法。但是ICP算法依赖对应关系[6]，对两幅点云的初始距离比较敏感。2013年Tagliasacch等人[5]提出稀疏迭代最近点算法(sparse iterative closet point)，该算法在配准含噪声和体外点的点云数据时可以保持很好的鲁棒性，但当两幅点云距离较远时，配准的效果仍不理想。为了解决ICP算法对噪声敏感问题，基于统计的配准方法[7−11]被相继提出。Myronenko等人[8]提出的CPD (Coherent Point Drift)算法，基本思想是先通过E步确定对应概率，根据对应概率建立似然函数，再通过M步最大化似然函数计算变换模型。不同于ICP算法中对应点是一对一的关系，这类方法用概率建立两幅点云之间的软对应(多对多)关系。另一类基于特征的配准算法[12−17]一般是通过特征匹配建立点对的对应关系，其中Lombaert 等人[16]提出的方法根据点的热核坐标[18,19]寻找对应点。虽然特征方法在计算线性变换时的性能优良，但需要大量的计算资源而且同样会面临特征对应不准确的问题。

上述3类方法存在的缺点是当对应缺失或者对应不准确时，会严重影响配准结果。本文提出的基于信息论的KL-Reg配准算法，不需要建立显式的对应关系，解决了由于对应不准确造成的配准失效问题。与Jian[8]和CPD算法[9]相比本文方法不需要优化高斯混合模型中的每一个高斯组件的权值。

2 KL-Reg算法思想

设点云M, S都是从一个实体对象采样获得的两幅点云数据，p(x|S,r), p(x|M,w)表示点云S, M的采样模型分布，配准S, M，就是使它们的分布模型尽可能相似。本节内容包括：点云数据的分布模型表达；用信息理论中的KL散度度量分布距离的方法；最后是如何最小化距离目标函数计算映射变换。

2.1 点云数据的模型表达

点云模型是由大量的散乱点混合在一起，设这些散乱点独立同分布，则可用高斯分布来建立点云分布模型。文献[8]把点云中的每一个点表达为一个单高斯模型(组件)，点云M的高斯混合模型表达为p(x|M)其中mj为M中第j的坐标，为第j个点的高斯分布，wj为第j个组件的权值，, δ为高斯核函数的宽度，N为M中

M点的数量。

假设点云中的每一个点都是以相同的概率从一个高斯混合模型随机采样获得，则每一个高斯组件的权值是相同的，设wj=1/NM。为了对噪声和体外点建模，高斯混合模型中增加一个额外的统一采样分布p(x|M')=1/NM表示噪声和体外点。假定点云M, S都是从一个实体对象采样获得的数据，则两个高斯混合模型的高斯核宽度相同，噪声比例相同。加入噪声后M的高斯混合模型可表达为

其中0≤p(x|mj)≤1,wj=1/NM, η表达点云中噪声点所占比重。同理点云S的高斯混合模型可表达为

其中0≤p(x|si)≤1,

当两幅点云距离越近时，其模型相似度就越高。因此配准的目标可以描述为，寻找一个模型变换T，使点云M经过该变换后与点云S的模型分布距离最小。

2.2 高斯混合模型的相似性度量

我们采用相对熵度量点云M和点云S分布的相似程度。Hershey等人[20]论证了度量高斯混合模型KL散度的可行性，因此保证了本文算法的有效性。设f(x)和g(x)为D维空间中的两个分布函数，其KL散度定义为

由KL散度的性质可知：当密度函数f(x)=g(x)时，kl(f(x)||g(x))=0；当f(x)与g(x)的差异越大，kl(f(x)||g(x))值越大。两幅点云的模型分布距离为kl(p(x|S,r)||p(x|M,w))。因此配准问题可表达为

2.3 目标函数优化

我们通过优化两个分布模型距离的上界间接优化式(3)目标函数，分布函数f(x),g(x)的KL散度可转化为

其中H(f(x),g(x))为f(x)和g(x)的交叉熵，H(f(x))为f(x)的信息熵。根据Hershey的方法[20]，式(4)的上界可表示为

其中klub(f(x),g(x))表示式(4)的上界，Hup(f(x), g(x))为H(f(x),g(x))上界，Hlb(f(x))为H(f(x))的下界。令f(x)=p(x|S,r ),g(x)=p(x|M,w,T)则有

其中

优化问题转化为求解式(1)上界，即式(6)来求解变换参数。当2δ确定时，上述目标函数可化为

式(7)目标函数是机器视觉领域中常见的优化问题，可以通过梯度下降法[9]来解决。高斯函数的宽度δ的选择是上述优化问题收敛的关键。本文2δ的选取采取自适应的方法，令

在每次迭代中，点云M经过模型变换后同时调整δ2。事实上可以将δ2等同于模拟退火算法中的温度，即随着迭代次数的增大，参数δ2逐渐减小。另外当点云之间旋转角度较大时，算法往往会陷入局部最优，当迭代次数达到迭代的上限并且δ2仍然未收敛到时，即认为配准失败。收敛阈值的大小取决于对配准时间和配准精度的要求，实验表明阈值越小配准的精度越高，但配准的时间就越长。本文结合蚁群算法[21]的思想，当迭代次数达到一个阈值，并且算法不收敛时就选择一个比较差的解，重新迭代。实验表明一般经过两次调整后即可找到全局最优解。

3 实验结果与分析

本文算法用Matlab实现，硬件平台为2.5 GHz Intel CPU, 2G内存空间。实验包括2维点云和3维点云配准实验以及定量对比实验。为了与其他方法[8]的实验结果进行对比，本文采用文献[8]中使用的数据和3维扫描仪的扫描数据进行配准实验。配准实验收敛阈值取为10−8，调整解空间的迭代次数为30次。

3.1 2维点云配准实验

图1为KL-Reg算法与CPD算法[8]配准2维鱼形点云[22]的对比实验，图1(a), 1(b), 1(c)为点云的初始分布，图1(d),1(e),1(f)为CPD算法的配准结果，图1 (g),1(h),1(i)为KL- Reg算法的配准结果。实验结果表明CPD算法配准图1 (b)中数据时不能得到全局最优解，文献[7]的算法对2维鱼形点云可适应的旋转弧度范围为[−2.0, 2.0]。本文根据蚁群算法[21]的思想，自动调整解空间，一般经过两次调整后就能找到全局最优解，实验表明KL-Reg算法可适应的旋转角度范围为[−π, π]。

图1(c),1(f),1(i)为数据不完整时的配准实验，当点云数据只有部分重合或者点云数据不完整时往往难以建立准确的对应关系，从而造成配准失败。实验结果表明，KL-Reg算法在对应不准确时仍然可以准确地配准点云，算法稳定性强。

图1(a), 1(d), 1(g)为配准含噪声和数据不完整点云时的实验，图1 (d), 1(g)分别为CPD算法和KL-Reg算法配准结果。在配准此类数据时，KL-Reg算法比CPD算法的配准结果更准确。

3.2 3维点云配准实验

图2数据为斯坦福扫描的中国龙点云数据[23]，采集中国龙点云时两个扫描仪夹角分别为24°，图2(a), 2(d)分别为从正面和背面观察两幅点云的初始位置。图2(b), 2(e)为CPD算法配准的结果，图2(c), 2(f)为KL-Reg算法配准结果。可以发现，图2(b), 2(e)采用CPD算法配准的结果中龙头处存在较大误差，而KL-Reg算法取得了较好的配准结果(图2(c), 2(f))。

3.3 量性对比实验

为了更加详尽地验证KL-Reg算法的有效性，本文与ICP[4], CPD[8], KC-Reg[9]和EM-ICP[10]算法进行了实验对比，配准数据为2维鱼形点云。对比实验包括：配准含不同比例噪声点云时各个算法的配准时间和误差；配准不完整点云数据时各个算法的配准误差。图3中配准时间单位为s，误差计算公式为

其中dis(c(M,N))为配准后两幅点云中对应点的距离和函数，Nc为对应点的个数。

表1为各个算法在配准数据不完整点云时的配准误差。实验结果表明KL-Reg算法的配准误差一直稳定在10−16左右，并不会随噪声比例的增加而增加，而CPD算法的配准误差对不完整点云数据比较敏感。KC-Reg算法、EM-ICP算法和ICP算法的配准误差会随噪声的比例递增而递增，其中ICP算法的配准误差递增的速度最快。图3为配准含不同比例噪声数据的时间对比，ICP算法的配准时间最短，虽然KL-Reg算法时间复杂度与CPD算法相当，而配准误差一直保持稳定，说明KL-Reg算法要比CPD算法鲁棒性更高。

表1 数据缺失时的配准误差

图1 2维鱼形点云配准实验

图2 中国龙3维点云配准实验

图3 含噪声点云数据配准时间对比

4 结束语

针对配准含有高噪声、体外点点云及不完整点云数据时，由于难以找到准确的对应关系导致的配准失效问题。本文提出的基于信息论的KL-Reg点云配准算法，提高了在对应关系不准确时配准的有效性和稳定性。KL-Reg算法认为点云从一个实体对象表面采样获得，且存在一个共同的采样分布，那么配准后的两幅点云应该符合这个采样分布，因此配准的过程描述为两个采样分布的拟合过程。与文献[7]和文献[8]CPD算法相比，本文方法不需要优化高斯混合模型中的每一个高斯组件的权值，本文基于总体分布的思想更为简单，易于实现。最后与ICP[4], CPD[8], KC-Reg[9]和EM-ICP[10]算法的实验表明，本文算法不仅能够精确配准点云，而且在配准不完整点云及有噪声点云时鲁棒性更高。

[1] Zitova B and Flusser J. Image registration methods: a survey[J]. Image and Vision Computing, 2003, 21(11): 977-1000.

[2] Lian Z, Godil A, Bustos B, et al.. A comparison of methods for non-rigid 3D shape retrieval[J]. Pattern Recognition, 2013, 46(1): 449-461.

[3] Liu M, Vemuri B C, Amari S I, et al.. Shape retrieval using hierarchical total bregman soft clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(12): 2407-2419.

[4] Besl P J and McKay N D. Method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 586-606.

[5] Tagliasacchi A, Bouaziz S, and Pauly M. Sparse iterative closest point[J]. Computer Graphics Forum, 2013, 32(5): 113-123.

[6] Tam G K L, Cheng Z Q, Lai Y K, et al.. Registration of 3D point clouds and meshes: a survey from rigid to nonrigid[J]. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(7): 1199-1217.

[7] Jian B and Vemuri B C. Robust point set registration using gaussian mixture models[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1633-1645.

[8] Myronenko A and Song X. Point set registration: coherent point drift[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(12): 2262-2275.

[9] Tsin Y and Kanade T. A correlation-based approach to robust point set registration[C]. Computer Vision-ECCV 2004. Springer Berlin Heidelberg, Prague, 2004: 558-569.

[10] Granger S and Pennec X. Multi-scale EM-ICP: a fast and robust approach for surface registration[C]. Computer Vision—ECCV 2002, Springer Berlin Heidelberg, Copenhagen, 2002: 418-432.

[11] Hermans J, Smeets D, Vandermeulen D, et al.. Robust point set registration using EM-ICP with information-theoretically optimal outlier handling[C]. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Colorado, USA, 2011: 2465-2472.

[12] Lipman Y, Yagev S, Poranne R, et al.. Feature matching with bounded distortion[J]. ACM Transactions on Graphics, 2014, 33(3), DOI: 10.1145/2602142.

[13] Paulus S, Dupuis J, Mahlein A K, et al.. Surface feature based classification of plant organs from 3D laserscanned point clouds for plant phenotyping[J]. BMC Bioinformatics, 2013, 14(1), DOI: 10.1186/147-2105-14-238.

[14] Zeng Y, Wang C, Gu X, et al.. A generic deformation model for dense non-rigid surface registration: a higher-order MRF-based approach[C]. IEEE International Conference on Computer Vision (ICCV), Sydney, Australia, 2013: 3360-3367.

[15] Hou T and Qin H. Robust dense registration of partial nonrigid shapes[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(8): 1268-1280.

[16] Lombaert H, Grady L, Polimeni J R, et al.. FOCUSR: feature oriented correspondence using spectral regularization−a method for precise surface matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, Australia, 2013, 35(9): 2143-2160.

[17] Chang W and Zwicker M. Automatic registration for articulated shapes[J]. Computer Graphics Forum, 2008, 27(5): 1459-1468.

[18] Bronstein M M and Kokkinos I. Scale-invariant heat kernel signatures for non-rigid shape recognition[C]. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, 2010: 1704-1711.

[19] Sun J, Ovsjanikov M, and Guibas L. A concise and provably informative multi-scale signature based on heat diffusion[J]. Computer Graphics Forum, 2009, 28(5): 1383-1392.

[20] Hershey J R and Olsen P A. Approximating the Kullback Leibler divergence between Gaussian mixture models[C]. IEEE International Conference on Acoustics, Speech and Signal Processing, Honolulu, 2007(4): 317-320.

[21] Karaboga D, Gorkemli B, Ozturk C, et al.. A comprehensive survey: artificial bee colony (ABC) algorithm and applications[J]. Artificial Intelligence Review, 2014, 42(1): 21-57.

[22] Chui Hai-li. Point matching[OL]. http://www.cise.ufl.edu /～anand/students/chui/research.html. 2014.5.

[23] Stanford computer graphics laboratory. 3Dscanrep[OL]. http://graphics.stanford.edu/data/3Dscanrep/. 2014.5.

秦红星： 男，1978年生，教授，主要研究方向为计算机图形学与可视化.

徐 雷： 男，1989年生，硕士生，研究方向为计算机图形学.

Information Theory Based KL-Reg Point Cloud Registration

Qin Hong-xing Xu Lei
(Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)
(College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

The registration of point clouds with high noises, outliers and missing data will be failure because the correspondence between point clouds is inaccurate. This paper proposes a information theory based point cloud registration method called KL-Reg algorithm without building correspondence. The method represents the point cloud with Gaussian mixture model, then computes the transformation through minimizing the KL divergence without build explicit correspondence. Experimental results show that KL-Reg algorithm is precise and stable.

Machine vision; Point clouds registration; KL-divergence; Gaussian mixture model

TP391

： A

：1009-5896(2015)06-1520-05

10.11999/JEIT141248

2014-09-25收到，2015-02-27改回

国家自然科学基金青年科学基金(61100113)，国家教育部留学归国基金教外司留[2012]940号，重庆市首批青年骨干教师项目(渝教人(2011)31号)，重庆市基础与前沿研究计划项目(cstc2013jcyjA 40062)，重庆邮电大学学科引进人才基金(A2010-12)和重庆市研究生科研创新项目(CYS14142)资助课题

*通信作者：秦红星 qinhx@cqupt.edu.cn