閆　利，譚駿祥，楊容浩，李少達

1. 武漢大學測繪學院，湖北 武漢 430079； 2. 成都理工大學地球科學學院，四川 成都 610059

?

一種閉合條件約束的全局最優(yōu)多視點云配準方法

閆利1，譚駿祥1，楊容浩2，李少達2

1. 武漢大學測繪學院，湖北 武漢 430079； 2. 成都理工大學地球科學學院，四川 成都 610059

摘要：針對已有多視點云配準存在的問題，提出了一種嚴密的閉合條件約束配準方法。該方法首先采用“點-切平面”迭代最近點算法分別求解各對應點云間的坐標轉換參數(shù)；再以單站點云為配準單元，并將轉換參數(shù)視為隨機觀測值構建條件方程，采用條件平差方法對轉換參數(shù)作改正以達到全局最優(yōu)。通過地面三維激光掃描儀實測兩組點云數(shù)據(jù)進行試驗，驗證了該方法有效且可行。試驗結果表明，對采樣間隔為毫米級和厘米級的點云，增加掃描重疊度能夠提高配準精度和可靠性。

關鍵詞：多視配準；ICP算法；七參數(shù)；誤差累積；條件平差

三維激光掃描儀能直接、快速地獲取物體表面點云3D坐標。為了完整地重構物體表面形狀，需要從不同視角進行掃描，每次掃描獲得的點云(待配準點云)往往基于獨立的局部坐標系統(tǒng)，需要轉換至統(tǒng)一的全局坐標系統(tǒng)中，這一過程稱為“點云配準”[1]。點云配準是點云處理的重要步驟，配準精度直接影響點云數(shù)據(jù)處理的整體精度[2]。

根據(jù)所處理視角數(shù)的不同，點云配準可分兩視配準和多視配準。兩視配準較為成熟，代表性的算法為迭代最近點(iterative closest points，ICP)配準[3-6]。而在多視配準方面，起初采用序貫(Sequential)配準[4]，即先選擇一幅模板點云，然后按點云對應關系依次以前一點云為基準，后一點云為待配準點云，采用兩視配準方法進行配準，依此完成配準。該方法直接易行，但前后配準點云之間有誤差累積，影響整體配準的精度與可靠性[7-8]。為避免配準誤差累積，提高配準精度，文獻[9—11]設計了同時(Simultaneous)配準，該方法按各點云對應關系同時一次性完成多視配準。同時配準的迭代收斂速度慢且會占用大量計算機內(nèi)存，降低了配準的可靠性和效率[12]。

近些年來，許多學者提出利用平差方法估計全局最優(yōu)坐標轉換參數(shù)提高多視配準效率、精度與可靠性的方法。文獻[13—16]均使用條件平差法進行簡易平差，分別對平移和旋轉參數(shù)的閉合差進行分配。轉換參數(shù)不是最原始的觀測值，它們之間往往不獨立，從這個意義上講，簡易平差方法不嚴密。文獻[17]依據(jù)整體平差模型構建誤差方程，采用間接平差法獲得最小二乘意義下的最優(yōu)轉換參數(shù)，但因誤差方程復雜而在平差中僅考慮了部分方程，方法也不嚴密。文獻[18]對多視配準的全局一致性進行了研究，但并沒有分析轉換參數(shù)的具體求解方法。點云配準是確定點云的位置和姿態(tài)參數(shù)的過程，即點云定向[19]。文獻[20—21]以掃描站射向標靶中心的光束為單元建立平差方程，一次性解算多站地面掃描點云坐標轉換參數(shù)；文獻[22]首先進行初始配準，再采用ICP配準進行優(yōu)化，實際上它們采用的仍然是同時配準方式。

本文研究一種閉合條件約束的多視配準方法，首先闡述兩視配準估計轉換參數(shù)的具體方法；然后以單站點云為單元，嚴密推導多視配準的閉合差分配方式；再展示兩組代表性的實測數(shù)據(jù)試驗，以驗證所提方法的有效性和可行性。

1兩視配準轉換參數(shù)估計

兩視點云配準包括初始配準和精確配準兩個步驟，初始配準的主要目的是為精確配準提供初始方位，以減少同名點的搜索空間，提高搜索的效率和可靠性[12]。不失一般性，初始配準的方法是在待配準點云S和基準點云T的重疊區(qū)域選取不共線且盡量均勻分布的3對近似同名點[23]，然后利用單位四元數(shù)法[24]計算轉換參數(shù)，再利用轉換參數(shù)對S進行轉換。

ICP算法是廣泛使用的精確配準方法，其算法模型為[1]

(1)

式中，Si=[SxiSyiSzi]T是待配準點；Ti=[TxiTyiTzi]T為Si的同名點；t=[txtytz]T為平移向量；m代表尺度因子；R表示旋轉矩陣，是關于繞z、x和y軸的歐拉旋轉角φ、θ和γ的函數(shù)；N為同名點數(shù)。ICP算法模型的幾何意義為T和S之間所有同名點間的距離平方和最小。

ICP算法主要包括點-點ICP[3]和點-切平面ICP[4]。點-切平面ICP能建立更精確的同名點，收斂速度較快、精度更高[12]，它是基于法向量方向上的距離平方和最小為目標，因此筆者將式(1)改進為

F(m,R,t)=

(2)

式中，ni=[nxinyinzi]T表示Si的法向量，其他參數(shù)與式(1)一致。

經(jīng)初始配準后，S與T的相對偏移較小，因此將歐拉旋轉角φ、θ、γ視為微小量，并且旋轉矩陣R的值近似為

將R帶入式(2)得

(3)

(4)

(5)

2多視配準閉合差分配

2.1閉合環(huán)條件方程

將掃描獲得的M個站(或者視角)點云記為V1,V2,…,VM，對應M個獨立的坐標系。在兩兩配準求解出轉換參數(shù)后，對應視角Vi+1與Vi之間存在坐標轉換關系，可以表示為Vi+1=Ci,i+1(ti,mi,Ri)Vi。如圖1所示，以單站點云為單元，將V1,V2,…,VM按照相鄰視角依次排列，除第一個視角和最后一個視角外，余下視角均恰好存在兩個相鄰視角，則這M個視角之間的轉換參數(shù)構成一個視角鏈；若每個視角均恰好存在兩個相鄰視角，則這M個視角之間的轉換參數(shù)構成一個視角閉合環(huán)。

圖1　視角鏈與閉合環(huán)示意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表示系數(shù)矩陣

L為常數(shù)項

2.2閉合差分配

在閉合環(huán)條件方程中，總的觀測值個數(shù)為7M，其中必要觀測數(shù)為7(M-1)，多余觀測數(shù)為r=7，即對應7個獨立的條件方程。對式(9)的系數(shù)陣A進行SVD分解得A=U·V·D，其中U、D為可逆的方陣；V為對角矩陣，對角線元素不為0的個數(shù)恰好等于多余觀測數(shù)7。式(9)兩邊同時乘以U的逆矩陣U-1并取獨立的7個方程得

(10)

(11)

在轉換參數(shù)的條件平差中，平差前轉換參數(shù)協(xié)因數(shù)陣和先驗權值根據(jù)式(5)進行計算。由于各視角之間的兩視配準是獨立進行的，因此可以認為不同轉換關系之間的轉換參數(shù)具有相互獨立的性質(zhì)，對應的協(xié)因數(shù)矩陣元素為0，即Q為分塊對角矩陣。

3試驗結果與分析

為驗證所提方法的有效性和可行性，試驗采用地面三維激光掃描儀FARO FOCUS3DS120獲取兩組具有不同特征的點云數(shù)據(jù)。如圖2所示，第1組是孔子像的掃描數(shù)據(jù)，布設了4個掃描站，采樣間隔為毫米級，但相鄰點云視角重疊度較小。第2組是結構比孔子像規(guī)則的體育館掃描數(shù)據(jù)，布設了19個掃描站，采樣間隔為厘米級，而相鄰視角重疊度較大。

圖2　點云數(shù)據(jù)基本情況，百分比表示重疊度，括號里面為采樣間隔(單位: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所示?？鬃酉裣噜忺c云視角的ICP配準所求轉換參數(shù)如表1所示。

圖3　孔子像數(shù)據(jù)初始配準和ICP配準后的效果Fig.3　Renderings of initial alignment and ICP registration for the Confucius data

圖4　體育館數(shù)據(jù)始配準和ICP配準后的效果Fig.4　Renderings of initial alignment and ICP registration for the gymnasium data

從兩視配準的結果來看，初始配準后各視角點云數(shù)據(jù)已大致拼合成了一個整體，經(jīng)過進一步的ICP配準，相鄰視角的重疊區(qū)域幾乎重合。為了評定轉換參數(shù)的求解精度，并檢驗求解的可靠性，接下來使用已經(jīng)求得的轉換參數(shù)構建閉合環(huán)條件方程進行平差計算，對閉合差進行分配。

孔子像的點云V1至V4構成視角閉合環(huán)，根據(jù)式(7)求得轉換參數(shù)的閉合差為f1=[-0.000 588,0.008 67,-0.003 26]T，并且

平差后的單位權中誤差為0.7 mm，轉換參數(shù)及其中誤差分別如表2和表3所示。體育館的點云V1至V19構成視角閉合環(huán)，根據(jù)式(7)求得轉換參數(shù)的閉合差為f1=[0.029 83,-0.005 67,0.014 19]T，并且

表1　孔子像數(shù)據(jù)ICP配準所求轉換參數(shù)

表2　孔子像數(shù)據(jù)平差后的轉換參數(shù)

表3孔子像數(shù)據(jù)轉換參數(shù)的中誤差

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，轉換參數(shù)中誤差較大的結果如表4所示。

表4體育館數(shù)據(jù)轉換參數(shù)中誤差較大的結果

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中平移參數(shù)的中誤差能夠達到0.01 mm級；旋轉參數(shù)的中誤差能夠達到s級；縮放參數(shù)的中誤差為10-6級；相鄰視角V2-V3和V4-V1的旋轉參數(shù)和尺度參數(shù)中誤差較大。表4顯示，平移參數(shù)的中誤差能夠達到0.01 mm級；旋轉參數(shù)的中誤差能夠達到0.1 s級；縮放參數(shù)的中誤差達到10-7級。

對比表3和表4，兩組數(shù)據(jù)的平移參數(shù)的中誤差幾乎是一個數(shù)量級，而體育館數(shù)據(jù)旋轉參數(shù)和尺度參數(shù)的中誤差小一個數(shù)量級。結合圖2，兩組數(shù)據(jù)的平均采樣間隔分別為毫米級和厘米級，表明點云采樣間隔對轉換參數(shù)中誤差的影響很?。坏鬃酉竦腣2-V3和V4-V1的重疊度僅3%和4%，并且體育館數(shù)據(jù)相鄰點云視角的重疊度較大，表明重疊度對轉換參數(shù)中誤差的影響較大，對尺度參數(shù)和旋轉參數(shù)中誤差的影響大于平移參數(shù)中誤差。因此，對于采樣間隔小的點云數(shù)據(jù)，為了提高配準精度與可靠性，增大相鄰點云的重疊度是一種有效的方式。

4結論

本文提出了一種閉合條件約束的多視點云配準方法，對坐標轉換參數(shù)估計進行了嚴密推導。該方法首先進行ICP配準求解轉換參數(shù)及其協(xié)因數(shù)矩陣；再將轉換參數(shù)作為隨機觀測值構建視角閉合環(huán)，使用行條件平差法分配閉合差，以達到全局最優(yōu)，并分析了配準精度與可靠性。其中，ICP配準利用七參數(shù)相似變換模型作為轉換模型，并采用梯度下降法估計轉換參數(shù)。

通過孔子像和體育館兩組實測掃描數(shù)據(jù)進行試驗，驗證了所提方法的有效性和可行性。試驗結果表明，對采樣間隔為毫米級和厘米級的點云，采樣間隔對轉換參數(shù)中誤差的影響很??；重疊度對轉換參數(shù)中誤差，特別是尺度參數(shù)和旋轉參數(shù)的中誤差影響較大；增加掃描重疊度能夠提高配準精度和可靠性。然而，只對單個視角閉合環(huán)的多視點云配準進行了試驗，對區(qū)域網(wǎng)的的轉換參數(shù)平差還需進一步分析和研究。

參考文獻：

[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]盛業(yè)華, 張卡, 張凱, 等. 地面三維激光掃描點云的多站數(shù)據(jù)無縫拼接[J]. 中國礦業(yè)大學學報, 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]姚吉利, 馬寧, 賈象陽, 等. 光束法區(qū)域網(wǎng)平差的地面激光掃描多站點云自動定向方法[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]李彩林, 郭寶云, 季錚. 多視角三維激光點云全局優(yōu)化整體配準算法[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

基金項目：測繪地理信息公益性行業(yè)科研專項資助(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)

引文格式：閆利，譚駿祥，楊容浩,等.一種閉合條件約束的全局最優(yōu)多視點云配準方法[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.