盛慶紅,陳姝文,柳建鋒，王惠南

南京航空航天大學(xué)航天學(xué)院，江蘇 南京 210016

LiDAR Point Cloud Registration Based on Plücker Line

SHENG Qinghong,CHEN Shuwen,LIU Jianfeng,WANG Huinan

College of Astronautics,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China

?

基于Plücker直線的LiDAR點云配準法

盛慶紅,陳姝文,柳建鋒，王惠南

南京航空航天大學(xué)航天學(xué)院，江蘇 南京 210016

Foundation support： The National Natural Science Foundation of China (Nos.41101441;41471381)

摘要：高精度的LiDAR點云配準是實現(xiàn)點云數(shù)據(jù)整體性和保證空間目標三維表面拓撲重建的關(guān)鍵，本文提出了基于Plücker直線的LiDAR點云配準模型,利用Plücker直線表示LiDAR待配準點云與基準點云間的同名直線，根據(jù)同名Plücker直線重合的幾何拓撲關(guān)系，建立Plücker直線共線條件方程，再用最小二乘法確定待配準LiDAR點云與基準點云間的相對位姿參數(shù)。結(jié)果表明，Plücker直線共線條件配準模型幾何約束性較強，配準精度較高。

關(guān)鍵詞：LiDAR；點云配準；直線特征；Plücker直線

LiDAR是城市空間信息獲取的重要手段[1-3]，由于城市空間目標復(fù)雜度較高，LiDAR系統(tǒng)數(shù)據(jù)采集通常需要從不同視角對空間目標進行掃描，再利用配準算法將相鄰測站數(shù)據(jù)進行拼接，從而實現(xiàn)對空間目標的完整表達。根據(jù)配準基元的不同，配準算法主要是利用LiDAR點云之間的同名點、同名線和同名面特征。基于點特征的點云配準算法[4-9]，其主要為迭代最近點算法，實際上待配準的點云間不存在完全對應(yīng)的同名點特征，這使得同名點特征配準算法的精度難以得到保證。選擇平面作為特征則具有更好的準確性和穩(wěn)健性[10-11]，基于面特征的點云配準算法便于確定同名平面特征，但是匹配算法對平面的拓撲關(guān)系以及數(shù)量有限制。一般情況，直線是遙感數(shù)據(jù)中高級的幾何特征描述符號，相對于點，直線具有更強的幾何拓撲性和幾何約束性，可獲得更高的配準精度。根據(jù)配準模型的不同，配準算法主要分為旋轉(zhuǎn)矩陣與四元數(shù)，前者可用直線的單位向量代替直線求解旋轉(zhuǎn)矩陣，然后采用兩條相交直線的交點坐標求解平移矩陣[12]；后者用四元數(shù)法來表達旋轉(zhuǎn)矩陣，用兩條相交直線來求解平移矩陣，角度的配準精度可以達到0.025°[13]。

然而，上述方法沒有充分考慮空間直線的幾何拓撲關(guān)系，配準模型的幾何約束強度弱。唯一確定一條空間直線所需的最少參數(shù)是4個，然而這4維參數(shù)空間是一個4維流形，它不是4維歐幾里德空間[14]，因此采用何種數(shù)學(xué)方法描述和表達三維空間中的任意直線，才能充分發(fā)揮直線的幾何拓撲性和幾何約束性，增加配準模型區(qū)域網(wǎng)的幾何強度，是提高LiDAR點云配準精度的關(guān)鍵。

Plücker直線坐標由直線相對于空間坐標系原點的矩矢量和直線方向矢量組成，其幾何意義更加明確，形式上更加簡潔，利用螺旋的Plücker坐標進行空間直線變換表示更加有效、快捷[15-19]。本文研究利用Plücker直線構(gòu)建的點云配準模型，實現(xiàn)LiDAR點云的高精度配準。

1Plücker直線

1.1Plücker直線概念

設(shè)一空間直線上的兩個點分別為P1(x1，y1，z1)T與P2(x2，y2，z2)T，那么這條直線的方向矢量w和矩矢量v分別為

(1)

如果將w和v的分量表示成5維射影空間上的6個齊次坐標，那么用非零標量乘以所有的齊次坐標后仍然表示同一個點，因此每條直線確定了該空間上的唯一點，這6個齊次坐標被稱作直線的Plücker坐標[20]，即

(2)

若對w進行歸一化處理，則Plücker坐標滿足條件

L2+M2+N2=1

(3)

根據(jù)式(1)，可知w×v=0，因此可得到Plücker坐標滿足的另外一個條件為

LL0+MM0+NN0=0

(4)

1.2Plücker直線空間螺旋運動

(5)

式中，ε為對偶單位，滿足ε2=0，ε≠0;i、j、k為虛數(shù)單位，滿足i2=j2=k2=ijk=-1。

(6)

(7)

(q1+εq01)+(q2+εq02)i+(q3+εq03)j+

(q4+εq04)k

(8)

圖1　Plücker直線表示的空間螺旋運動Fig.1　Plücker linear spiral movement of space

(9)

對偶四元數(shù)矩陣形式的乘法運算法則如式(10)所示[20]。由于對偶四元數(shù)乘法不滿足乘法的交換律和結(jié)合律，因此式(6)在進行計算時，要按照從左到右的順序依次相乘

(10)

2Plücker直線LiDAR點云配準模型

2.1Plücker直線共線條件方程

令l1表示待配準點云上的一條直線，l2表示基準點云上l1的同名直線，則相鄰測站點云配準的幾何條件為l1與l2完全重合，即在同一坐標系中兩條直線共線。根據(jù)Plücker直線坐標的理論[20]，兩條直線共線的充要條件為兩條直線的Plücker坐標對應(yīng)成比例，又由于Plücker直線坐標經(jīng)過式(3)的歸一化處理，因此兩條直線共線的條件是其各個坐標對應(yīng)相等，即為式(6)的展開形式。

根據(jù)式(10)對偶四元數(shù)乘法運算法則，將式(6)展開可以得到6個方程

(11)

(12)

2.2平差解算

將式(12)寫成誤差方程式的矩陣形式

V=AX+F

(13)

式中

(14)

對式(14)進行線性化，可得約束條件方程的矩陣形式為

BX+W=0

(15)

式中

假設(shè)有n對同名直線，對每對直線可列一個式(13)的誤差方程，聯(lián)合式(15)，得到Plücker直線LiDAR點云配準方程的整體平差公式為

(16)

式(16)中，V和F是6n維矩陣；A是6n×8維矩陣。根據(jù)最小二乘原理，得

Y=-N-1WY

(17)

式中

式中，K為過渡性數(shù)值。

2.3精度評定

兩條直線配準后，兩條重合直線間的距離與夾角均為0。為評價兩條直線的配準精度，可利用配準后的兩條直線之間的距離與夾角指標。

n為l1和l2的公共法向量，在直線l1和l2上各取任意一點，記為A和A′，則向量AA′在n上的投影d即為兩條直線間距離

(18)

兩條直線l1和l2的夾角θ計算公式為

(19)

d和θ的幾何意義為：當待配準點云與基準點云完成配準時，d=0 m，θ=0°；若沒有完成配準，則d≠0 m或者θ≠0°，其數(shù)值大小反映出同名直線的匹配程度。

3試驗結(jié)果分析

3.1模擬數(shù)據(jù)試驗

利用文獻[23]的建筑物數(shù)據(jù)作為基準點云，將基準點云繞z軸旋轉(zhuǎn)30°，各坐標軸方向上平移距離1 m，將所得到的數(shù)據(jù)作為待配準點云，直線分布如圖2所示。圖2中編號為①—④的直線用于配準，共4條；編號為⑤—⑩的直線為檢查直線，共6條，試驗結(jié)果見表1和表2。由表1看出，配準結(jié)果與理論值基本一致，說明本文采用的方法是正確可行的。從表2看出，直線配準后的距離精度均值為0.090 4 mm，角度均值為0.000 02°，說明算法對模擬數(shù)據(jù)具有較高的精度。

圖2　建筑物點云直線分布Fig.2　Lines distribution of building LiDAR point cloud

參數(shù)結(jié)果XS/m1.0001YS/m0.99994ZS/m0.99996φ/(°)-0.00004ω/(°)0.000005κ/(°)30.0007

由于試驗待配準數(shù)據(jù)是由基準數(shù)據(jù)整體旋轉(zhuǎn)平移后得到的，未考慮同名直線匹配誤差。為此，模擬實際測量中匹配誤差，在待配準數(shù)據(jù)直線的2個端點(6個坐標值)加入高斯白噪聲，且加入的白噪聲互不相關(guān)?？紤]實際數(shù)據(jù)LiDAR點云精度為10 mm，噪聲標準差設(shè)定在0~0.01 m之間變化，為了保證結(jié)果的穩(wěn)定性，在每一個噪聲水平上，程序運行100次，得到的噪聲標準差對配準精度的影響結(jié)果如圖3和圖4所示。由圖3和圖4可以看出，當噪聲標準差在0~0.01 m之間變化過程中，直線配準的距離誤差和角度誤差都呈現(xiàn)線性增大的趨勢，但是距離誤差均值在0~4.5 mm之間，角度誤差均值在0°～0.055°之間，由此可見距離誤差小于噪聲標準差變化，距離誤差和角度誤差均可以滿足LiDAR點云配準精度要求。

表2　配準精度

圖3　不同噪聲水平下配準距離誤差曲線圖Fig.3　Distance error under different noise levels

圖4　不同噪聲水平下配準角度誤差曲線圖Fig.4　Angle error under different noise levels

3.2實際數(shù)據(jù)試驗

為了驗證算法在實際LiDAR點云配準中的實用性，利用文獻[13]中的直線特征作為試驗數(shù)據(jù)，數(shù)據(jù)為奧地利Riegl公司的LMS-Z420系列地面LiDAR設(shè)備采集得到的某建筑物立面點云，采樣精度為10 mm?；邳c云的線狀特征提取，采用的方法是首先通過人機交互的方式選擇相應(yīng)的LiDAR點云實現(xiàn)平面的擬合，在此基礎(chǔ)上，通過平面相交的方法來實現(xiàn)線狀特征的精確提取。選取編號2和4兩條直線進行試驗，配準結(jié)果見表3。選取編號1和3的直線作為檢查直線，按照式(18)和式(19)計算實際精度，得到的結(jié)果見表4。

從表3看出，3種方法結(jié)果基本相同。在計算效率方面，Plücker直線法與四元數(shù)法基本相同，由于兩種方法都避免了繁瑣的三角函數(shù)運算，因此相比歐拉角法效率更高。

從表4看出，Plücker直線法配準后的距離精度均值為5.7 mm，角度精度均值為0.023 9°，均高于四元數(shù)法和歐拉角法。這是因為歐拉角法的外方位元素之間存在相關(guān)性，如Xs與φ、Ys與ω等，導(dǎo)致最小二乘估計存在復(fù)共線性，不再是最優(yōu)估計。四元數(shù)法雖然采用兩個端點描述直線，但基元本質(zhì)上仍是點的三維坐標。而本文方法用方向矢量與矩矢量將直線描述為5維空間中的6個齊次坐標，將6個齊次坐標描述的直線作為基元，并且直接利用同名直線重合的空間拓撲關(guān)系建立共線條件方程，是真正的基于直線的點云配準方法。

表3　LiDAR點云配準結(jié)果對比

表4　配準精度對比

4結(jié)論

本文提出了一種基于Plücker直線的LiDAR點云共線條件配準方法，首先通過Plücker坐標描述同名直線，然后利用單位對偶四元數(shù)表示Plücker直線的空間螺旋運動，根據(jù)同名Plücker直線的共線條件建立LiDAR點云配準模型。分別進行了模擬數(shù)據(jù)試驗和實際數(shù)據(jù)試驗，試驗結(jié)果表明，本文方法充分利用了待配準點云與基準點云同名直線間的空間拓撲關(guān)系，增強了配準模型的幾何約束性。然而本文配準方法未考慮存在比例縮放的點云數(shù)據(jù)，這是下一步需要解決的問題。

參考文獻：

[1]張東, 黃騰, 李桂華. 地面LiDAR點云數(shù)據(jù)先局部后整體配準方法[J]. 測繪工程, 2012, 21(2): 6-8.

ZHANG Dong, HUANG Teng, LI Guihua. Registration Method of Terrestrial LiDAR Data from Parts to Whole[J]. Engineering of Surveying Mapping, 2012, 21(2): 6-8.

[2]陳卓, 馬洪超. 基于機載LiDAR數(shù)據(jù)的大型立交橋三維建模方法[J]. 測繪學(xué)報, 2012, 41(2): 252-258.

CHEN Zhuo, MA Hongchao. Automatic Extracting and Modeling Approach of City Cloverleaf from Airborne LiDAR Data[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(2): 252-258.

[3]方莉娜,楊必勝. 車載激光掃描的三維道路自動提取方法[J]. 測繪學(xué)報, 2013, 42(2): 260-267.

FANG Lina, YANG Bisheng. Automated Extracting Structural Roads from Moblie Laser Scanning Point Clouds[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2): 260-267.

[4]BESL P J, MCKAY N D. A Method for Registration of 3-D Shapes[J]. IEEE Transactions on Pattern Analysis and Machines Intelligence, 1992, 14(2): 239-256.

[5]ROBERT J M P. Theory and Application of Weighted Least Squares Surface Matching for Accurate Spatial Data Registration[D]. Australia: The University of Newcastle, 2004.

[6]ROSENHOLM D, TORLEGARD K. Three-dimensional Absolute Orientation of Stereo Models Using Digital Elevation Models[J]. Photogrammetric Engineering and Remote Sensing, 1988, 54(10): 1385-1389.

[7]張劍清, 翟瑞芳, 鄭順義. 激光掃描多三維視圖的全自動無縫鑲嵌[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 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.

[8]童禮華,程亮,李滿春,等. 基于建筑輪廓的車載和航空LiDAR數(shù)據(jù)配準[J].測繪學(xué)報, 2013, 42(5): 699-706, 714.

TONG Lihua, CHENG Liang, LI Manchun, et al. Registration of Vehicle and Airborne LiDAR with Building Contours[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(5): 699-706, 714.

[9]戴靜蘭, 陳志楊, 葉修梓. ICP算法在點云配準中的應(yīng)用[J]. 中國圖象圖形學(xué)報, 2007, 12(3): 517-521.

DAI Jinglan, CHEN Zhiyang, YE Xiuzi. The Application of ICP Algorithm in Point Cloud Alignment[J]. Journal of Image and Graphics, 2007, 12(3): 517-521.

[10]何文峰, 查紅彬. 基于平面特征的深度圖像配準[C]∥中國人工智能進展-中國人工智能學(xué)會第10屆全國學(xué)術(shù)年會論文集.北京: 北京郵電大學(xué)出版社, 2003:643-648.

HE Wengfeng, ZHA Hongbin. Registration of Range Data Based on Planar Features[C]∥Advances in Chinese Artificial Intelligence.Beijing: Beijing University of Posts and Telecommunications press, 2003, 643-648.

[11]PARK S Y, SUBBARAO M. An Accurate and Fast Point-to-Plane Registration Technique[J]. Pattern Recognition Letters, 2003, 24(16): 2967-2976.

[12]GUAN Yunlan, ZHANG Hongjun. Initial Registration for Point Clouds Based on Linear Features[C]∥Proceedings of 2011 4th International Symposium on Knowledge Acquisition and Modeling.Sanya: IEEE, 2011: 474-477.

[13]王永波, 楊化超, 劉燕華, 等. 線狀特征約束下基于四元數(shù)描述的LiDAR點云配準方法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2013, 38(9): 1057-1062.

WANG Yongbo, YANG Huachao, LIU Yanhua, et al. Linear-Feature-Constrained Registration of LiDAR Point Cloud via Quaternion[J]. Geomatics and Information Science of Wuhan University, 2013, 38(9): 1057-1062.

[14]AYACHE N, FAUGERAS O D. Maintaining Representations of the Environment of a Mobile Robot[J]. IEEE Transactions on Robotics and Automation, 1989, 5(6): 804-819.

[15]FUNDA J, TAYLOR R H, PAUL R P. On Homogeneous Transforms, Quaternions, and Computational Efficiency[J]. IEEE Transactions on Robotics and Automation, 1990, 6(3): 382-388.

[16]ZHANG Wenxiang. Plücker Coordinates of Screws and Their Applications in Gear Studies[J]. Journal of Huainan Mining Institute, 1991, 11(1-2): 86-97, 56.

[17]RONDA J I, VALDES A, GALLEGO G. Camera Autocalibration Using Plücker Coordinates[C]∥IEEE International Conference on Image Processing 2005. Genova: IEEE, 2005: 3125-3128.

[18]SARIYILDIZ E, TEMELTAS H. Solution of Inverse Kinematic Problem for Serial Robot Using Dual Quaterninons and Plücker Coordinates[C]∥Proceedings ofIEEE/ASME International Conference on Advanced Intelligent Mechatronics. Singapore: IEEE, 2009: 338-343.

[19]李靜, 王惠南, 劉海穎. 基于普呂克直線的交會對接相對位姿確定算法[J]. 中國空間科學(xué)技術(shù), 2013, 33(1): 69-74.

LI Jing, WANG Huinan, LIU Haiying. Plucker Line Based Relative Position and Attitude Determination Algorithm for RVD[J]. Chinese Space Science and Technology, 2013, 33(1): 69-74.

[20]SELIG J M. 機器人學(xué)的幾何基礎(chǔ)[M].楊向東, 譯.北京: 清華大學(xué)出版社, 2008.

SELIG J M. Robotics Foundations of Geometry[M]. YANG Xiangdong, trans.Beijing: Tsinghua University Press, 2008.

[21]CHASLES M. Note sur les Proprietes Generales du Systeme de Deux Corps Semblables Entreux et Places Dune Maniere Quelconque Dans Lespace; et sur le Deplancement Fini ou Infiniment Petit dun Corps Solide Libre[J]. Bulletin des Science Mathematiques, Astronomiques, Physiques et Chimiques, 1830, 14: 321-326.

[22]ROONEY J. A Comparison of Representations of General Spatial Screw Displacement[J]. Environment and Planning B Planning and Design, 1978, 5(1): 45-88.

[23]LASENBY J, FITZGERALD W J, LASENBY A N, et al. New Geometric Methods for Computer Vision: An Application to Structure and Motion Estimation[J]. International Journal of Computer Vision, 1998, 26(3): 191-213.

(責任編輯：張艷玲)

修回日期： 2015-06-05

First author： SHENG Qinghong(1978—), female, PhD, assciate professor,majors in digital photogrammetry and remote sensing image processing.

E-mail： qhsheng@nuaa.edu.cn

LiDAR Point Cloud Registration Based on Plücker Line

SHENG Qinghong,CHEN Shuwen,LIU Jianfeng,WANG Huinan

College of Astronautics,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China

Abstract：The high precision LiDAR point cloud registration is the key to achieve overall point cloud data, in the meantime, to ensure the 3D topological reconstruction of spatial objects. In this paper, a new registration method based on Plücker line is proposed. The conjugate lines between reference point cloud and point cloud to be registered are expressed by Plücker line. Then the collinearity equation based on Plücker line is established by the geometric topology relation of the conjugate lines. Finally the relative position and attitude parameters between reference point cloud and point cloud to be registered are solved by least squares method. Experimental results show that the method has strong geometric constraint and high registration precision.

Key words：LiDAR; point cloud registration; linear features; Plücker line

作者簡介：第一 盛慶紅(1978—)，女，博士，副教授，研究方向為數(shù)字攝影測量、遙感影像幾何處理。

收稿日期：2014-08-14

基金項目：國家自然科學(xué)基金(41101441；41471381)

中圖分類號：P237

文獻標識碼：A

文章編號：1001-1595(2016)01-0058-07

引文格式：盛慶紅,陳姝文,柳建鋒,等.基于Plücker直線的LiDAR點云配準法[J].測繪學(xué)報，2016,45(1)：58-64.DOI:10.11947/j.AGCS.2016.20140415.

SHENG Qinghong,CHEN Shuwen,LIU Jianfeng,et al.LiDAR Point Cloud Registration Based on Plücker Line[J]. Acta Geodaetica et Cartographica Sinica,2016,45(1):58-64.DOI:10.11947/j.AGCS.2016.20140415.