空間非合作目標的多視角點云配準算法研究

郭瑞科，王立，朱飛虎，吳云

北京控制工程研究所，北京 100190

?

空間非合作目標的多視角點云配準算法研究

郭瑞科，王立*，朱飛虎，吳云

北京控制工程研究所，北京 100190

為了提高相鄰視角間稀疏掃描點云數據配準的速度和精度，實現多視角點云精確配準，提出一種基于KD-Tree點云均勻采樣簡化算法，并且對傳統四點算法(4-Points Congruent Sets Algorithm, 4PCS)中的閾值參數進行了統一，確定了各誤差閾值參數和點云密度之間的關系，通過基于姿態校正的方法有效解決了對稱視角點云引起的誤配準問題。仿真結果表明，該方法能夠快速、有效地實現衛星稀疏點云的配準。

非合作目標；多視角；點云數據；配準；四點算法

空間非合作目標的在軌服務技術可實現對目標航天器的在軌維護、空間垃圾碎片清理、抓捕或破壞敵方軍事衛星等，具有很高的民用意義和軍事價值。在這些在軌服務任務中，服務航天器在跟蹤、接近和抓捕目標時，需要實現航天器和目標間的相對位置和姿態測量。相比較于傳統的合作目標，非合作目標上沒有光標線或者角反射器等配合標志，無法提供顯著、可靠的參考信息，這就給非合作航天器的準確位姿測量帶來了極大的挑戰。特別是對于完全未知的空間目標，需要首先在軌建立三維模型，然后利用所重構的三維模型實現六自由度位姿估計和特征識別。因而如何對未知目標進行三維重構，便成為了非合作在軌服務的一項關鍵技術。

激光掃描敏感器通過獲取目標表面的點云數據，得到目標三維模型，具有精度高、不受光照影響的優點。由于敏感器視場角的限制，要得到目標完整的三維模型，需要從多個視角對目標進行掃描，將不同視角得到的點云數據配準到同一坐標系下，因而需要研究多視角點云的配準。點云配準一般包括全局配準和精確配準兩個步驟，全局配準縮小兩片點云之間的旋轉和平移錯位，為精確配準提供比較好的初值。對于多視角點云數據的配準，某些視角需要多次旋轉平移才能配準到統一坐標系下，實現整體配準，進而重構出目標點云模型。

Wolfson等[1]提出的幾何哈希算法，可以用于點云數據的全局配準，但是需要建立哈希表，占用內存空間比較大，不適合空間應用。Rusu等[2]提出的FPFH基于局部幾何特征的全局配準方法，計算速度快，但是依賴點云的鄰域特征，導致稀疏點云數據估計曲率等特征誤差較大。Guo等[3]提出一種外形生長的多視角點云配準算法，選擇一個種子外形，迭代地進行兩兩點云配準，進而實現模型重構，該算法過于依賴兩兩配準的精度，運算量較大。

本文針對空間目標需要內存占用小、宜使用稀疏點云進行配準的特點，采用基于改進四點算法的全局配準方法，具有速度快的優點，可以得到滿足精度的全局配準結果。將全局配準的結果作為精確配準的初值，保證收斂精度的同時，提高配準的效率。通過引入航天器姿態連續變化的約束條件，可以有效處理對稱視角點云誤配準的問題,使用連續變換的方法實現多視角點云的配準。

1　點云數據的簡化

激光掃描敏感器的測量精度高，尤其是在近距離掃描時，采用高效的李薩茹掃描方式(圖1)，獲取的單幅掃描數據點數多達數萬到數十萬。這樣大的數據量對于星載計算機有限的存儲空間和計算能力帶來了比較大的挑戰。從圖1可以看到邊緣點云密度高于中間部分，而且點云都集中在掃描線上，因而并不是所有的點都可用于配準。其中冗余的點云數據如果都參與配準，不僅會降低計算速度，增加內存使用，而且點越多，越難從中找到符合特征的點對，影響配準的精度。

圖1　李薩茹掃描方式Fig.1　Lissajous scan pattern

為了解決上述問題，必須對測量的點云數據進行精簡，以提高計算速度，減少存儲空間，提高配準精度等。考慮到所處理的對象為衛星點云，在空間模型重建中對時效性要求較高，本文提出一種基于KD-Tree點云均勻采樣算法對點云數據進行精簡。

KD-Tree是三維數據中常用的一種數據格式，可以快速實現K最近鄰域的搜索[4]。在基于KD-Tree點云均勻采樣算法中，首先利用KD-Tree對點云數據建立空間拓撲結構，搜索點集中每個點的K最近鄰域，計算該點與K個最近鄰點的重心，用該重心代替這點，最后對所得到的點集均勻采樣，可以得到簡化的稀疏點云。

圖2是從一個視角掃描得到的單幅原始衛星模型點云，包含10 171個數據點，采用上述簡化算法，K取4，采樣率設置為7%。圖3是簡化后的點云，數據點數為710，可以看到數據得到精簡，衛星模型的特征也可以比較好地保留。

圖2　原始點云Fig.2　Original point cloud

圖3　簡化后的點云Fig.3　Simplified point cloud

2　基于改進四點算法的全局配準　 算法

對于兩片三維點云的配準，至少需要從各自點云中選取對應不共線的三點，才能計算出二者的剛體變換矩陣。若待配準兩片點云P(Data數據集)、Q(Model數據集)分別有m、n個點，在P、Q中選取對應的三點計算旋轉平移矩陣，時間復雜度可達O(m3n3)。Irani等[5]采用基于隨機采樣一致性(Random Sample Consensus，RANSAC)的方法配準，可以降低復雜度到O(n3lg n)，然而對于空間應用，時間復雜度還是太高。考慮在P點云中選取更多的共面點(5個或者以上)，則在Q點云中能成功選擇到正確的對應點集的概率急劇降低，難以實現配準[6]。

四點算法(4-Points Congruent Sets Algorithm，4PCS)是Aiger等[7]于2008年提出的一種基于RANSAC法則的全局配準算法，可成功用于三維點云數據的配準，時間復雜度只有O(n2)。本文針對原始四點算法中閾值參數比較多的情況，通過點云密度對閾值參數進行了統一，簡化了多視角點云配準時的閾值參數設置；針對該算法處理對稱點云時成功率低的問題，提出了基于姿態連續變化來校正對稱引起誤配準的方法，有效提高了點云配準的成功率。

2.1四點算法

四點算法在每次的迭代中，在P數據集中隨機尋找不在同一條直線上的共面4點，根據共面4點的兩條對角線交點將線段所分的比例r1、r2在剛體變換中的不變性(見圖4)，在Q數據集中選取對應的共面4點(見圖5)，這兩對共面4點組成一致共面4點集，利用該一致共面4點集可以計算出旋轉矩陣R和平移矩陣T。4點算法不需要計算復雜的幾何特征，速度快，對噪聲具有比較高的魯棒性。

圖4　P中所選的共面4點[7]Fig.4　Four (approximately) coplanar points extracted formP

圖5　Q中對應的共面一致4點Fig.5　Affine invariant congruent 4 points extracted formQ

四點算法中，Q點集中候選點對可以用共面4點長度來篩選：

(1)

式中：δ1為尋找近似長度相等線段a′b′與ab的誤差閾值。根據不變量r1、r2可以確定可能的交點e′：

(2)

式中： q1、q2是從點集Q找到的長度符合線段對應的候選共面4點。近似相等交點所對應的點對即組成Q點集中的共面一致4點。利用點集(a,b,c,d)和(a′,b′,c′,d′)可以計算對應的歐氏變換矩陣，用所得到的歐氏變換矩陣作用與點集P，驗證在一定閥值下，P點集中成功配準到Q點集的點數目，即一致性度量。

2.2四點算法的閾值參數設置方法

文中所配準的點云數據是從完全非合作目標掃描所得到的，全局配準中沒有點云數據的先驗知識，同時四點算法中涉及的誤差閾值參數眾多，這給算法中的閾值參數設置帶來了挑戰。在軌模型重建中需要多次點云配準，每次配準的兩幅點云特征都有所差別，如果分別設定這些閾值參數，可能會費時費力，甚至會導致不能成功配準。

點云數據密度是稀疏點云的關鍵幾何特征，待配準點云的密度τ，本文通過計算點云中所有點K最近鄰域距離的平均值來確定，該值越小，表示點云密度越大，反之則越小。一般三維散亂點云的最近鄰域點數可設置為6，即前后左右上下6個方向，這樣可以比較好地保持點云的三維特征，準確確定它的局部幾何特征。本文中待配準的點云是經過簡化的衛星點云，衛星太陽翼和本體部分以平面特征為主，因而最近鄰域點數設置為4，即只選取沿平面方向的4個點，能比較好地保留衛星點云特征，準確估計點云數據密度。本文通過確定點云密度與各誤差閾值參數的關系，對誤差閾值參數進行了統一。

上述四點算法中涉及的參數有：在Q點集中篩選候選對應點對時的誤差閾值δ1；選取近似相等交點時的誤差閾值，‖e1-e2‖<δ2；一致性度量時的距離誤差閾值δ3。

本文通過仿真試驗確定了各誤差閾值δi與點云密度τ之間的關系，有效提高了配準算法的穩定性和自動化程度：

(3)

2.3對稱視角的校正

對于衛星等對稱性比較高的航天器，某些視角的點云是對稱的，配準時會出現沿某個本體軸翻轉180°的情況，這就為正確配準帶來了挑戰。考慮到相鄰視角的點云姿態變換角度不會太大，根據配準得到的旋轉矩陣可以計算出相鄰視角點云間的相對姿態，對于姿態角過大的情況進行識別、校正，就可以有效解決對稱情況下配準偏差的問題。

多視角點云配準中，每對相鄰視角點云之間都存在旋轉矩陣R，據此可以定義P數據集所在視角測量坐標系相對Q數據集所在視角測量坐標系的姿態。常用的姿態描述方式有歐拉軸/角式，有4個參數，轉軸的單位矢量在參考坐標系中的3個方向余弦ex、ey、ez及繞此軸的轉角Φ；歐拉角式，采用3-1-2旋轉順序，轉角分別是ψ、φ、θ。上述姿態參數與旋轉矩陣存在如下關系[7]：

(4)

(5)

設Vo、Vb分別是矢量V在觀測坐標系和本體坐標系的值，存在轉換矩陣R，繞x軸的基元旋轉記為Rx，誤配準的旋轉矩陣記為Rw。Vo=RVb，

(6)

對繞本體x軸翻轉180°的誤配準情況，有Vo=R·Rx(π)·Vb，因而Rw=R·Rx(π)，其中

可以得到誤配準的姿態角，ψw=-ψ，φw=φ，θw=θ，即姿態角只有符號變化，絕對值大小沒有變化，對于繞y軸或者z軸的翻轉有類似的結果，這個特點可以用到校正中。

設校正后的歐拉軸/角參數是exc、eyc、ezc、Φc，旋轉矩陣是Rcorrection，σ是角度閾值，誤配校正算法如下：

1)判斷歐拉轉角是否大于閾值，如果Φ>σ則需校正，執行下一步；

3)找到最大的三軸歐拉角對應的旋轉軸，記為k，令ekc=ek；

4)找到最小的三軸歐拉角對應的旋轉軸，記為j，令ejc=ej；第三個轉軸eic=ei；

6)使用校正的旋轉矩陣Rcorrection更新點云數據，作為精確配準的初值。

3　基于ICP算法的精確配準算法

Besl和McKay于1992年提出了點到點的迭代最近點(Iterated Closest Points，ICP)算法，ICP算法是在兩個點集中搜索最近的點對，以這些最近點對作為控制點來估算旋轉變換矩陣和平移變換矩陣，并將這個坐標變換作用到待配準點集上，迭代進行這一操作過程，直到正確匹配[9]。

由于待配準的兩幅點云只有部分區域是重合的，在搜索最近點對的時候，不可避免地會存在錯誤的匹配點對。為了消除這些錯誤匹配點對對精確配準結果的影響，需要剔除這些錯誤匹配點對。點云數據密度是稀疏點云的關鍵幾何特征，全局配準時已經估計過點云的密度。對于部分重疊的兩片點云，只有使用重疊區域的最近點對，才能準確計算出兩者之間的變換矩陣，而非重疊區域的最近點對距離偏大。本文采取距離閾值的方法來剔除錯誤匹配點對，即認為搜索的最近點距離大于點云密度一定倍數的點對為錯誤匹配點對。

4　多視角點云的配準

分析多個視角點云的配準方法：直接將相鄰兩個視角點云依次配準，每次配準后都去除重疊部分，合并成一幅點云，直到配準到最后一個視角,見圖6。經過實際配準試驗發現，隨著已配準點云幅數的增加，合并起來的視角所組成的點云數目增大，重疊率降低，配準精度并沒有提高，反而難以配準，花費時間過大。

圖6　多視角掃描Fig.6　Multiple-view scan

考慮這樣的方法：每次都只配準相鄰的兩個視角，再用所得到的變換矩陣計算得到最終的配準結果。具體說明如下：

1)假設試驗相鄰視角相差45°，共有8幅點云需配準成完整的點云模型，分別是0°、45°、90°、135°、180°、225°、270°、315°視角下的點云數據，最終所有視角點云都配準到0°視角。

2)記315°視角點云配準到270°視角下的變換矩陣為R1、T1，270°視角點云配準到225°視角下的變換矩陣為R2、T2，依次類推，45°配準到0°的變換矩陣為R7、T7。記315°、270°、225°、45°、0°視角下的點云數據分別為X315、X270、X225、X45、X0，有X270=R1X315+T1，X225=R2X270+T2，…，X0=R7X45+T7，即45°視角點云經過一次變換R7、T7，就可以變換到0°視角；

3)315°視角的點云變換到0°視角可以由下式計算得到:

(7)

其他視角點云變換到0°視角由類似的公式可以得到。

所有視角點云都統一到0°視角之后，采用文獻[10]中的平差方法，降低整體誤差，再合并重合部分的點云，就可以得到完整的點云模型。

5　試驗仿真

本文仿真試驗使用某衛星仿真點云數據，點云相鄰視角間隔分為45°數據為0°、45°、90°、135°、180°、225°、270°、315°這8個視角下的點云。不同視角下的點云數目有所變化，測試算法的有效性和魯棒性。在主頻為3.20 GHz，內存為4 GB，WINXP操作系統的PC機上，以7.8.0版本的Matlab為平臺進行算法仿真。配準誤差定義為均方根誤差(Root Mean Square Error，RMSE)：

(8)

式中：N為兩塊待配準點云重疊部分點數目；pi、qj分別為點云中重疊區域的點。

5.1相鄰視角的配準效果

對于相鄰視角點云的配準，選取90°和45°視角下的點云數據，分別作為Model點云和Data點云，相應的數據點數1 136、1 204。

圖7(b)所示為粗配準的點云，藍色為Model點云，紅色為Data點云，二者有部分重疊區域。可以看到兩幅點云基本配準，沿滾轉軸方向仍有偏差，配準誤差為0.138 9。為了近一步提高點云配準精度，使用改進的ICP算法進行優化，可以看到兩片點云已經重合，配準誤差降低到0.093 8。

圖7　90°視角點云配準向45°視角結果Fig.7　Pair-wise registration result

5.2對稱視角配準的校正

本體點云對稱，誤配準如圖8(b)所示，Data點云繞本體軸旋轉了180°，采用算法校正之后，可以得到圖8(c)所示的正確配準結果。

對所有兩兩相鄰視角點云進行配準，圖9所示為未采用校正算法和采用校正算法后，配準成功率的比較，可以看到有對稱視角點云(45°和225°視角點云)的配準成功率均有明顯提高，整體成功率平均提高31.52%。

圖8　對稱點云誤配準的校正Fig.8　Mis-registration correction of symmetry point cloud

圖9　各視角的配準成功率Fig.9　Success rate of adjacent point cloud registration

5.3噪聲對配準誤差的影響

對上述90°和45°視角下的點云數據添加均值為零、方差變化的高斯噪聲，驗證算法在噪聲影響下的有效性，如圖10所示。可以看到經改進的四點算法在噪聲標準差小于0.15 m時能保證配準誤差小于0.14 m，且整體精度優于原4PCS算法。然而在噪聲過大(超過0.15 m)時，兩種算法配準誤差都變大。

圖10　噪聲對配準誤差的影響Fig.10　RMSE under variable noise

5.4整體配準結果

嘗試對多個相鄰視角進行了配準，無噪聲情況下，從圖11可以看到文中改進的配準算法精度都高于4PCS算法。不同相鄰視角誤差有所變化，是因為不同相鄰視角的點云密度有所不同，都在比較小的區域里面波動。

將所有視角點云統一到同一個視角中，由于相鄰視角點云存在重疊部分，這樣直接得到的點云模型存在大量重疊部分。需要合并重疊部分，才能用于后續的曲面重建等處理。對比圖12和圖13，可以看到點云數目從11 060降低到3 532，點云得到了簡化，同時模型的特征也較好地保存下來。

圖11　相鄰視角的配準誤差Fig.11　RMSE of adjacent point cloud registration

圖12　統一到同一坐標系下，未去除重疊部分Fig.12　Multiple-view point cloud in a global coordinate system with overlap section

圖13　去除重疊部分點云Fig.13　Removing the point cloud of overlap section

6　結束語

兩幅點云的配準是多幅點云配準的基礎和關鍵。針對空間非合作目標，點云的配準算法要兼顧精確性、快速性和內存占用大小等因素。本文針對衛星掃描點云數據，提出基于KD-Tree點云均勻采樣簡化算法，在保持衛星特征的情況下較好地實現了點云簡化。對于衛星稀疏點云數據，使用基于改進四點算法進行全局配準，將全局配準結果作為精確ICP配準的初值，實現了點云數據的配準。對于四點算法中誤差閾值參數多的情況，給出了誤差閾值參數與點云數據密度之間的關系，有效提高算法的穩定性。提出根據衛星姿態變化的連續性，解決衛星點云中存在對稱視角導致誤配的問題。對多視角點云進行了配準，實現了衛星點云模型重構。

References)

[1]WOLFSON H, RIGOUTSOS I. Geometric hashing: an overview[J]. IEEE Computer Science and Engineering, 1997, 4(4):10-21.

[2]RUSU R B. Fast point feature histograms (FPFH) for 3D registration[C]∥Robotics and Automation, 2009.ICRA 09.IEEE International Conference, Kobe, May 12-17, 2009:3212-3217.

[3]GUO Y L, SOHEL F, BENNAMOUN M. An accurate and robust range image registration algorithm for 3D object modeling[J]. IEEE Transactions on Multimedia, 2014, 16(5): 1377-1390.

[4]BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM, 1975, 18(9): 509-517.

[5]IRANI S, RAGHAVAN P. Combinatorial and experimental results for randomized point matching algorithms[J]. Computational Geometry, 1999, 12(1-2): 17-31.

[6]YAO L,RUGGERI,TADDEI P, et al. Robust surface registration usingN-points approximate congruent sets[J]. EURASIP Journal on Advances in Signal Processing, 2011(1): 72.

[7]AIGER D, NILOY M J. 4-Points congruent sets for robust pairwise surface registration[J].ACM Transactions on Graphics (TOG), 2008, 27(3): 85-94.

[8]呂振鐸, 雷擁軍. 衛星姿態測量與確定[M]. 北京: 國防工業出版社, 2013: 30-35.

[9]BESL P J, MCKAY N D. A method for registration of 3D shape[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.

[10]李彩林, 郭寶云, 季錚. 多視角三維激光點云全局優化整體配準算法[J]. 測繪學報, 2015, 44(2): 183-189.

LI C L, GUO B Y, JI Z. Global optimization and whole registration algorithm of multi-view 3D laser point cloud[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(2): 183-189(in Chinese).

(編輯：高珍)

Research on registration algorithm of multiple-view point cloud for non-cooperative spacecraft

GUO Ruike, WANG Li*, ZHU Feihu, WU Yun

Beijing Institute of Control Engineering, Beijing 100190, China

The point cloud data registration is one of the key technical aspects of three-dimensional reconstruction for non-cooperative spacecraft. To solve the pair-wise registration issue of sparse point cloud, and align the multiple-view point cloud accurately,an optimization registration method was presented. A novel point cloud simplification algorithm using uniform sampling was proposed based on KD-Tree and the uniform relation of the threshold parameters in the 4PCS(4-Points Congruent Sets) algorithm was established via the density of the point cloud. By using the mis-registration correction method based on attitude,the mis-registration problem of the symmetry point cloud was solved.The results show that the proposed algorithm can effectively achieve good alignments of the sparse point cloud of the satellite, besides, the stability and the success rate of the algorithm is also improved.

non-cooperative spacecraft; multiple-view;point cloud data; registration;4-points congruent sets

10.16708/j.cnki.1000-758X.2016.0055

2016-03-28；

2016-05-20；錄用日期：2016-08-22；

時間：2016-09-2113:41:18

http:∥www.cnki.net/kcms/detail/11.1859.V.20160921.1341.003.html

國家重點基礎研究發展計劃(973)(2013CB733100)

郭瑞科(1989-)，男，碩士研究生，ruikeguo@163.com,研究方向為空間圖像處理

王立(1977-)，男，研究員，bheart@263.net，研究方向為空間圖像處理、模式識別以及視覺導航

V391.41

A

http:∥zgkj.cast.cn

引用格式：郭瑞科,王立,朱飛虎,等. 空間非合作目標的多視角點云配準算法研究[J].中國空間科學技術, 2016,36(5)：

32-39.GUORK,WANGL,ZHUFH,etal.Researchonregistrationalgorithmofmultiple-viewpointcloudfornon-cooperativespacecraft[J].ChineseSpaceScienceandTechnology, 2016,36(5)：32-39(inChinese).