一种闭合条件约束的全局最优多视点云配准方法
2016-05-16谭骏祥杨容浩李少达
闫 利，谭骏祥，杨容浩，李少达
1. 武汉大学测绘学院，湖北 武汉 430079； 2. 成都理工大学地球科学学院，四川 成都 610059
一种闭合条件约束的全局最优多视点云配准方法
闫利1，谭骏祥1，杨容浩2，李少达2
1. 武汉大学测绘学院，湖北 武汉 430079； 2. 成都理工大学地球科学学院，四川 成都 610059
摘要：针对已有多视点云配准存在的问题，提出了一种严密的闭合条件约束配准方法。该方法首先采用“点-切平面”迭代最近点算法分别求解各对应点云间的坐标转换参数；再以单站点云为配准单元，并将转换参数视为随机观测值构建条件方程，采用条件平差方法对转换参数作改正以达到全局最优。通过地面三维激光扫描仪实测两组点云数据进行试验，验证了该方法有效且可行。试验结果表明，对采样间隔为毫米级和厘米级的点云，增加扫描重叠度能够提高配准精度和可靠性。
关键词：多视配准；ICP算法；七参数；误差累积；条件平差
三维激光扫描仪能直接、快速地获取物体表面点云3D坐标。为了完整地重构物体表面形状，需要从不同视角进行扫描，每次扫描获得的点云(待配准点云)往往基于独立的局部坐标系统，需要转换至统一的全局坐标系统中，这一过程称为“点云配准”[1]。点云配准是点云处理的重要步骤，配准精度直接影响点云数据处理的整体精度[2]。
根据所处理视角数的不同，点云配准可分两视配准和多视配准。两视配准较为成熟，代表性的算法为迭代最近点(iterative closest points，ICP)配准[3-6]。而在多视配准方面，起初采用序贯(Sequential)配准[4]，即先选择一幅模板点云，然后按点云对应关系依次以前一点云为基准，后一点云为待配准点云，采用两视配准方法进行配准，依此完成配准。该方法直接易行，但前后配准点云之间有误差累积，影响整体配准的精度与可靠性[7-8]。为避免配准误差累积，提高配准精度，文献[9—11]设计了同时(Simultaneous)配准，该方法按各点云对应关系同时一次性完成多视配准。同时配准的迭代收敛速度慢且会占用大量计算机内存，降低了配准的可靠性和效率[12]。
近些年来，许多学者提出利用平差方法估计全局最优坐标转换参数提高多视配准效率、精度与可靠性的方法。文献[13—16]均使用条件平差法进行简易平差，分别对平移和旋转参数的闭合差进行分配。转换参数不是最原始的观测值，它们之间往往不独立，从这个意义上讲，简易平差方法不严密。文献[17]依据整体平差模型构建误差方程，采用间接平差法获得最小二乘意义下的最优转换参数，但因误差方程复杂而在平差中仅考虑了部分方程，方法也不严密。文献[18]对多视配准的全局一致性进行了研究，但并没有分析转换参数的具体求解方法。点云配准是确定点云的位置和姿态参数的过程，即点云定向[19]。文献[20—21]以扫描站射向标靶中心的光束为单元建立平差方程，一次性解算多站地面扫描点云坐标转换参数；文献[22]首先进行初始配准，再采用ICP配准进行优化，实际上它们采用的仍然是同时配准方式。
本文研究一种闭合条件约束的多视配准方法，首先阐述两视配准估计转换参数的具体方法；然后以单站点云为单元，严密推导多视配准的闭合差分配方式；再展示两组代表性的实测数据试验，以验证所提方法的有效性和可行性。
1两视配准转换参数估计
两视点云配准包括初始配准和精确配准两个步骤，初始配准的主要目的是为精确配准提供初始方位，以减少同名点的搜索空间，提高搜索的效率和可靠性[12]。不失一般性，初始配准的方法是在待配准点云S和基准点云T的重叠区域选取不共线且尽量均匀分布的3对近似同名点[23]，然后利用单位四元数法[24]计算转换参数，再利用转换参数对S进行转换。
ICP算法是广泛使用的精确配准方法，其算法模型为[1]
(1)
式中，Si=[SxiSyiSzi]T是待配准点；Ti=[TxiTyiTzi]T为Si的同名点；t=[txtytz]T为平移向量；m代表尺度因子；R表示旋转矩阵，是关于绕z、x和y轴的欧拉旋转角φ、θ和γ的函数；N为同名点数。ICP算法模型的几何意义为T和S之间所有同名点间的距离平方和最小。
ICP算法主要包括点-点ICP[3]和点-切平面ICP[4]。点-切平面ICP能建立更精确的同名点，收敛速度较快、精度更高[12]，它是基于法向量方向上的距离平方和最小为目标，因此笔者将式(1)改进为
F(m,R,t)=
(2)
式中，ni=[nxinyinzi]T表示Si的法向量，其他参数与式(1)一致。
经初始配准后，S与T的相对偏移较小，因此将欧拉旋转角φ、θ、γ视为微小量，并且旋转矩阵R的值近似为
将R带入式(2)得
(3)
(4)
(5)
2多视配准闭合差分配
2.1闭合环条件方程
将扫描获得的M个站(或者视角)点云记为V1,V2,…,VM，对应M个独立的坐标系。在两两配准求解出转换参数后，对应视角Vi+1与Vi之间存在坐标转换关系，可以表示为Vi+1=Ci,i+1(ti,mi,Ri)Vi。如图1所示，以单站点云为单元，将V1,V2,…,VM按照相邻视角依次排列，除第一个视角和最后一个视角外，余下视角均恰好存在两个相邻视角，则这M个视角之间的转换参数构成一个视角链；若每个视角均恰好存在两个相邻视角，则这M个视角之间的转换参数构成一个视角闭合环。
图1 视角链与闭合环示意Fig.1 Sketch map of view chain and closed view loop
Vj=tj-1+mj-1Rj-1tj-2+…+
(6)
(7)
f1(t,m,φ,θ,γ)≈f1(t0,m0,φ0,θ0,γ0)+
f2(t,m,φ,θ,γ)≈f2(t0,m0,φ0,θ0,γ0)+
(8)
AV+L=0
(9)
式中，V=[dtTdmTdφTdθTdγT]T；A表示系数矩阵
L为常数项
2.2闭合差分配
在闭合环条件方程中，总的观测值个数为7M，其中必要观测数为7(M-1)，多余观测数为r=7，即对应7个独立的条件方程。对式(9)的系数阵A进行SVD分解得A=U·V·D，其中U、D为可逆的方阵；V为对角矩阵，对角线元素不为0的个数恰好等于多余观测数7。式(9)两边同时乘以U的逆矩阵U-1并取独立的7个方程得
(10)
(11)
在转换参数的条件平差中，平差前转换参数协因数阵和先验权值根据式(5)进行计算。由于各视角之间的两视配准是独立进行的，因此可以认为不同转换关系之间的转换参数具有相互独立的性质，对应的协因数矩阵元素为0，即Q为分块对角矩阵。
3试验结果与分析
为验证所提方法的有效性和可行性，试验采用地面三维激光扫描仪FARO FOCUS3DS120获取两组具有不同特征的点云数据。如图2所示，第1组是孔子像的扫描数据，布设了4个扫描站，采样间隔为毫米级，但相邻点云视角重叠度较小。第2组是结构比孔子像规则的体育馆扫描数据，布设了19个扫描站，采样间隔为厘米级，而相邻视角重叠度较大。
图2 点云数据基本情况，百分比表示重叠度，括号里面为采样间隔(单位:cm)Fig.2 Basic information of the point clouds,where percentages are overlaps and values in the brackets are sampling intervals (unit: cm)
点云初始配准与ICP配准后的效果如图3和图4所示。孔子像相邻点云视角的ICP配准所求转换参数如表1所示。
图3 孔子像数据初始配准和ICP配准后的效果Fig.3 Renderings of initial alignment and ICP registration for the Confucius data
图4 体育馆数据始配准和ICP配准后的效果Fig.4 Renderings of initial alignment and ICP registration for the gymnasium data
从两视配准的结果来看，初始配准后各视角点云数据已大致拼合成了一个整体，经过进一步的ICP配准，相邻视角的重叠区域几乎重合。为了评定转换参数的求解精度，并检验求解的可靠性，接下来使用已经求得的转换参数构建闭合环条件方程进行平差计算，对闭合差进行分配。
孔子像的点云V1至V4构成视角闭合环，根据式(7)求得转换参数的闭合差为f1=[-0.000 588,0.008 67,-0.003 26]T，并且
平差后的单位权中误差为0.7 mm，转换参数及其中误差分别如表2和表3所示。体育馆的点云V1至V19构成视角闭合环，根据式(7)求得转换参数的闭合差为f1=[0.029 83,-0.005 67,0.014 19]T，并且
表1 孔子像数据ICP配准所求转换参数
表2 孔子像数据平差后的转换参数
表3孔子像数据转换参数的中误差
Tab.3Root mean square errors of the transformation parameters for Confucius data
Cδtx/mmδty/mmδtz/mmδφ/(″)δθ/(″)δγ/(″)δmC1,20.130.040.053.00.90.95.6×10-6C2,30.060.040.036.72.82.51.1×10-5C3,40.130.050.062.81.31.18.3×10-6C4,10.060.020.026.62.62.59.9×10-6
平差后的单位权中误差为1.2 mm，转换参数中误差较大的结果如表4所示。
表4体育馆数据转换参数中误差较大的结果
Tab.4Larger root mean square errors of the transformation
parameters for gymnasium data
Cδtx/mmδty/mmδtz/mmδφ/(″)δθ/(″)δγ/(″)δmC1,20.030.020.010.180.120.145.9×10-7C3,40.030.060.050.130.310.241.2×10-6C5,60.050.080.050.180.120.171.8×10-6C11,120.090.090.080.180.290.301.7×10-6C12,130.090.110.060.470.230.198.1×10-7C13,140.030.050.040.210.120.154.8×10-7C14,150.030.040.020.200.140.135.0×10-7C16,170.040.040.040.230.320.228.5×10-7C17,180.060.020.040.160.140.241.3×10-6C18,190.030.040.020.340.200.139.3×10-7
在精度方面，表3中平移参数的中误差能够达到0.01 mm级；旋转参数的中误差能够达到s级；缩放参数的中误差为10-6级；相邻视角V2-V3和V4-V1的旋转参数和尺度参数中误差较大。表4显示，平移参数的中误差能够达到0.01 mm级；旋转参数的中误差能够达到0.1 s级；缩放参数的中误差达到10-7级。
对比表3和表4，两组数据的平移参数的中误差几乎是一个数量级，而体育馆数据旋转参数和尺度参数的中误差小一个数量级。结合图2，两组数据的平均采样间隔分别为毫米级和厘米级，表明点云采样间隔对转换参数中误差的影响很小；但孔子像的V2-V3和V4-V1的重叠度仅3%和4%，并且体育馆数据相邻点云视角的重叠度较大，表明重叠度对转换参数中误差的影响较大，对尺度参数和旋转参数中误差的影响大于平移参数中误差。因此，对于采样间隔小的点云数据，为了提高配准精度与可靠性，增大相邻点云的重叠度是一种有效的方式。
4结论
本文提出了一种闭合条件约束的多视点云配准方法，对坐标转换参数估计进行了严密推导。该方法首先进行ICP配准求解转换参数及其协因数矩阵；再将转换参数作为随机观测值构建视角闭合环，使用行条件平差法分配闭合差，以达到全局最优，并分析了配准精度与可靠性。其中，ICP配准利用七参数相似变换模型作为转换模型，并采用梯度下降法估计转换参数。
通过孔子像和体育馆两组实测扫描数据进行试验，验证了所提方法的有效性和可行性。试验结果表明，对采样间隔为毫米级和厘米级的点云，采样间隔对转换参数中误差的影响很小；重叠度对转换参数中误差，特别是尺度参数和旋转参数的中误差影响较大；增加扫描重叠度能够提高配准精度和可靠性。然而，只对单个视角闭合环的多视点云配准进行了试验，对区域网的的转换参数平差还需进一步分析和研究。
参考文献：
[1]GRUEN A, AKCA D. Least Squares 3D Surface Matching[M]. Inst. Für Geodäsie Und Photogrammetrie, 2007.
[2]浦石, 李京伟, 郭四清. 融合语义特征与GPS位置的地面激光点云拼接方法[J]. 测绘学报, 2014, 43(5): 545-550.DOI:10.13485/j.cnki.11-2089.2014.0075.
PU Shi, LI Jingwei, GUO Siqing. Registration of Terrestrial Laser Point Clouds by Fusing Semantic Features and GPS Positions[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(5): 545-550. DOI:10.13485/j.cnki.11-2089.2014.0075.
[3]BESL P J, MCKAY H D. A Method for Registration of 3D Shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.
[4]CHEN Yang, MEDIONI G. Object Modelling by Registration of Multiple Range Images[J]. Image and Vision Computing, 1992, 10(3): 145-155.
[5]RUSINKIEWICZ S, LEVOY M. Efficient Variants of the ICP Algorithm[C]∥Proceedings of the 3rd International Conference on 3D Digital Imaging and Modeling. Quebec City: IEEE, 2001: 145-152.
[6]SALVI J, MATABOSCH C, FOFI D, et al. A Review of Recent Range Image Registration Methods with Accuracy Evaluation[J]. Image and Vision Computing, 2007, 25(5): 578-596.
[7]BERGEVIN R, SOUCY M, GAGNON H,et al. Towards a General Multi-View Registration Technique[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(5): 540-547.
[8]GAGNON H,SOUCY M,BERGEVIN R,et al.Registration of Multiple Range Views for Automatic 3D Model Building[C]∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Seattle: IEEE, 1994: 581-586.
[9]BLAIS G, LEVINE M D. Registering Multiview Range Data to Create 3D Computer Objects[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(8): 820-824.
[10]EGGERT D W, FITZGIBBON A W, FISHER R B. Simultaneous Registration of Multiple Range Views for Use in Reverse Engineering[C]∥Proceedings of the 13th International Conference on Pattern Recognition. Vienna: IEEE, 1996: 243-247.
[11]NEUGEBAUER P J. Geometrical Cloning of 3D Objects via Simultaneous Registration of Multiple Range Images[C]∥Proceedings of International Conference on Shape Modeling and Application. Los Alamitos: IEEE, 1997: 130-179.
[12]PULLI K. Multiview Registration for Large Data Sets[C]∥Proceedings of the 2nd International Conference on 3-D Digital Imaging and Modeling. Ottawa: IEEE, 1999: 160-168.
[13]ZHO H, BASAKI R. Reconstructing Urban 3D Model Using Vehicle-borne Laser Range Scanners[C]∥Proceedings of the 3rd International Conference on 3-D Digital Imaging and Modeling. Quebec City: IEEE, 2001: 349-356.
[14]盛业华, 张卡, 张凯, 等. 地面三维激光扫描点云的多站数据无缝拼接[J]. 中国矿业大学学报, 2010, 39(2), 233-237.
SHENG Yehua, ZHANG Ka, ZHANG Kai, et al. Seamless Multi Station Merging of Terrestrial Laser Scanned 3D Point Clouds[J]. Journal of China University of Mining & Technology, 2010, 39(2): 233-237.
[15]徐源强, 高井祥, 张丽, 等. 地面三维激光扫描的点云配准误差研究[J]. 大地测量与地球动力学, 2011, 31(2): 129-132.
XU Yuanqiang, GAO Jingxiang, ZHANG Li, et al. Research on Point Cloud Registration Error of Terrestrial Laser Scanning[J]. Journal of Geodesy and Geodynamics, 2011, 31(2): 129-132.
[16]何朝明. 离散点云处理的关键技术研究[D]. 成都: 西南交通大学, 2007.
HE Chaoming. Research on the Key Technologies of Discrete Point Clouds Process[D]. Chengdu: Southwest Jiaotong University, 2007.
[17]张剑清, 翟瑞芳, 郑顺义. 激光扫描多三维视图的全自动无缝镶嵌[J]. 武汉大学学报(信息科学版), 2007, 32(2), 100-103.
ZHANG Jianqing, ZHAI Ruifang, ZHENG Shunyi. Automatic Seamless Registration of 3D Multiple Range Views[J]. Geomatics and Information Science of Wuhan University, 2007, 32(2): 100-103.
[18]LIU Yuan,ZHOU Wen,YANG Zhouwang,et al. Globally Consistent Rigid Registration[J]. Graphical Models, 2014, 76(5): 542-553.
[19]姚吉利, 马宁, 贾象阳, 等. 球形标靶的固定式扫描大点云自动定向方法[J]. 测绘学报, 2015, 44(4): 431-437. DOI: 10.11947/j.AGCS.2015.20130357.
YAO Jili, MA Ning, JIA Xiangyang, et al. An Approach for Automatic Orientation of Big Point Clouds from the Stationary Scanners Based on the Spherical Targets[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(4): 431-437. DOI: 10.11947/j.AGCS.2015.20130357.
[20]姚吉利, 马宁, 贾象阳, 等. 光束法区域网平差的地面激光扫描多站点云自动定向方法[J]. 测绘学报, 2014, 43(7): 711-716, 723.DOI:10.13485/j.cnki.11-2089.2014.0099.
YAO Jili,MA Ning,JIA Xiangyang,et al. Auto-Registration for Terrestrial Laser Scanning Multi-Stations Point Clouds with Bundle Block Adjustment Method[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(7): 711-716, 723. DOI:10.13485/j.cnki.11-2089.2014.0099.
[21]姚吉利, 贾向阳, 马宁, 等. 地面激光扫描多站点云整体定向平差模型[J]. 测绘学报, 2014, 43(8): 835-841.DOI:10.13485/j.cnki.11-2089.2014.0023.
YAO Jili, JIA Xiangyang, MA Ning, et al. Overall Orientation Adjustment Model of Terrestrial Laser Scanning Multi-Station Point Clouds[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(8): 835-841.DOI:10.13485/j.cnki.11-2089.2014.0023.
[22]李彩林, 郭宝云, 季铮. 多视角三维激光点云全局优化整体配准算法[J]. 测绘学报, 2015, 44(2): 183-189. DOI: 10.11947/j.AGCS.2015.20130737.
LI Cailin, GUO Baoyun, JI Zheng. Global Optimization and Whole Registration Algorithm of Multi-view 3D Laser Point Cloud[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(2): 183-189. DOI: 10.11947/j.AGCS.2015.20130737.
[23]BERNARDINI F, RUSHMEIER H. The 3D Model Acquisition Pipeline[J]. Computer Graphics Forum, 2002, 21: 149-172.
[24]HORN B K P. Closed-form Solution of Absolute Orientation Using Unit Quaternions[J]. Journal of the Optical Society of America A, 1987, 4(4): 629-642.
(责任编辑：张艳玲)
修回日期： 2015-08-10
First author： YAN Li(1966—), professor, PhD，PhD supervisor, majors in research and education on photogrammetry, remote sensing and LiDAR.
E-mail： lyan@sgg.whu.edu.cn
E-mail： tanjunxiang89@163.com
A Method of Globally Optimal Registration for Multi-view Point Clouds Constrained by Closed-loop Conditions
YAN Li1,TAN Junxiang1,YANG Yonghao2,LI Shaoda2
1. School of Geodesy and Geomatics, Wuhan University, Wuhan 430079, China； 2. College of Earth Sciences, Chengdu University of Technology, Chengdu 610059, China
Abstract：This paper proposes a rigorous registration method of multi-view point clouds constrained by closed-loop conditions for the problems of existing algorithms. In our approach, the point-to-tangent-plane iterative closest point algorithm is used firstly to calculate coordinate transformation parameters of all adjacent point clouds respectively. Then the single-site point cloud is regarded as registration unit and the transformation parameters are considered as random observations to construct conditional equations, and then the transformation parameters can be corrected by conditional adjustments to achieve global optimum. Two practical experiments of point clouds acquired by a terrestrial laser scanner are shown for demonstrating the feasibility and validity of our methods. Experimental results show that the registration accuracy and reliability of the point clouds with sampling interval of millimeter or centimeter level can be improved by increasing the scanning overlap.
Key words：multi-view registration; iterative closest point algorithm; seven parameters; error accumulation; conditional adjustment
Corresponding author：TAN Junxiang
通信作者：谭骏祥
第一作者简介：闫利(1966—)，男，教授，博士生导师，主要从事摄影测量、遥感和三维激光扫描技术的教学与科研工作。
收稿日期：2015-01-08
基金项目：测绘地理信息公益性行业科研专项资助(201512008)
中图分类号：P227
文献标识码：A
文章编号：1001-1595(2016)04-0418-07
Foundation support： The Scientific Research Foundation for Public Walfare Industry of Surveying and Mapping and Geographic Information & Disaster Reduction(No. 201512008)
引文格式：闫利，谭骏祥，杨容浩,等.一种闭合条件约束的全局最优多视点云配准方法[J].测绘学报，2016,45(4)：418-424. DOI:10.11947/j.AGCS.2016.20150018.
YAN Li,TAN Junxiang,YANG Yonghao,et al.A Method of Globally Optimal Registration for Multi-view Point Clouds Constrained by Closed-loop Conditions[J]. Acta Geodaetica et Cartographica Sinica,2016,45(4):418-424. DOI:10.11947/j.AGCS.2016.20150018.
