基于局部特征的點云配準算法

趙夫群，周明全，耿國華

?

基于局部特征的點云配準算法

趙夫群1,2，周明全2,3，耿國華2

(1. 咸陽師范學(xué)院教育科學(xué)學(xué)院，陜西 咸陽 712000；2. 西北大學(xué)信息科學(xué)與技術(shù)學(xué)院，陜西 西安 710127；3. 北京師范大學(xué)信息科學(xué)與技術(shù)學(xué)院，北京 100875)

針對覆蓋率較低的點云，提出一種基于局部特征的點云配準算法。首先提取點云的局部深度、法線偏角和點云密度等局部特征，得到局部特征描述子；然后計算局部特征集的相關(guān)性，得到相關(guān)候選點集；再次通過刪減外點達到點云粗配準的目的；最后采用基于旋轉(zhuǎn)角約束和動態(tài)迭代系數(shù)的改進迭代最近點(ICP)算法，實現(xiàn)點云的細配準。實驗結(jié)果表明，基于局部特征的點云配準算法可以實現(xiàn)覆蓋率較低點云的精確配準，是一種精度高、速度快的點云配準算法。

點云配準；局部特征；迭代最近點；旋轉(zhuǎn)角約束；動態(tài)迭代系數(shù)

點云配準研究已久，其應(yīng)用領(lǐng)域涉及曲面匹配[1-2]、3D建模[3-4]、目標識別[5-7]以及姿態(tài)估計[8]等多個方面。點云配準就是將同一物體不同視角下的點云數(shù)據(jù)變換到同一坐標系統(tǒng)下的過程。點云配準中應(yīng)用最多的是基于特征的配準算法，包括基于全局特征的配準和基于局部特征的配準。全局特征描述的是整個點云模型，局部特征只對特征點的鄰域特征進行描述，與全局特征相比，局部特征更適用于部分覆蓋的點云配準。

目前的點云配準算法中，應(yīng)用最為廣泛的是由BESL和MCKAY[9]提出的ICP算法，該算法對于覆蓋率較高的點云有精確的配準效果，但是對點云的初始位置要求較高，而且對于數(shù)據(jù)量較大的點云的配準速度較慢。目前，國內(nèi)外出現(xiàn)了很多改進的迭代最近點算法(iterative closest point, ICP)及其應(yīng)用，如HAN等[10]提出了一種加強的ICP算法，能夠快速準確地實現(xiàn)點云配準；王森等[11]將Sparse ICP算法應(yīng)用到了三維耳廓識別中，得到了較高的識別精度和識別效率；LI和SONG[12]提出了一種基于動態(tài)調(diào)整因子的ICP算法，在不影響配準精度和收斂方向的情況下，大大提高了算法的配準速度；MAVRIDIS等[13]提出了一種基于混合優(yōu)化系統(tǒng)的稀疏ICP算法，提高了點云配準的精度和速度；DU等[14]提出了概率迭代最近點(probability iterative closest point, PICP)算法，提高了點云配準的抗噪性；DU等[15]提出了尺度迭代最近點（scaling iterative closest point, SICP）算法，解決了點云的尺度配準問題。以上這些算法在點云的配準精度、速度、抗噪性以及尺度因素等方面有了一定程度的改進，但都是基于全局特征的配準，因此對部分覆蓋的點云配準效果并不十分理想。

針對覆蓋率較低的點云，本文提出了一種基于局部特征的點云配準算法。該算法分為4個實現(xiàn)步驟：①提取點云局部特征，包括局部深度、法線偏角和點云密度，并生成局部特征描述子；②計算局部特征集的相關(guān)性，建立點云的候選相關(guān)點集；③刪減候選相關(guān)點集中的外點，以實現(xiàn)點云的粗配準；④通過加入旋轉(zhuǎn)角約束和動態(tài)迭代系數(shù)等參數(shù)來改進ICP算法，并用改進的ICP算法實現(xiàn)點云的細配準，到達最終精確、快速配準的目的。

1 局部特征描述子

本文所指的局部特征是一種快速、魯棒的點云特征描述子，包括局部深度、法線的偏角和點云密度等，其都具有旋轉(zhuǎn)和平移不變的特性。

1.1 局部深度特征

1.2 法線的偏角

1.3 點云密度

計算了點的3個局部幾何特征后，可以得到3個子直方圖，然后將其合成為1個直方圖，即可得到局部特征的描述子。

2 粗配準算法

采用一種基于局部特征描述子的配準算法實現(xiàn)點云粗配準，主要包含3個步驟：局部特征提取、相關(guān)性計算和外點刪減。

圖1 局部特征示意圖

2.1 局部特征提取

2.2 相關(guān)性計算

2.3 外點刪減

3 細配準算法

以上步驟實現(xiàn)了點云的粗配準，接下來的細配準采用一種改進的ICP算法來實現(xiàn)。即在ICP算法的基礎(chǔ)上添加旋轉(zhuǎn)角約束和動態(tài)迭代系數(shù)。

3.1旋轉(zhuǎn)角約束

旋轉(zhuǎn)角約束是指為剛體變換中的旋轉(zhuǎn)角設(shè)置邊界（即上界和下界），可以降低因旋轉(zhuǎn)角變化過大而引起的配準效果不佳的問題。

3.2 動態(tài)迭代系數(shù)

3.3 改進的ICP算法

加入旋轉(zhuǎn)角約束和動態(tài)迭代系數(shù)后，改進的ICP算法的具體實現(xiàn)步驟如下：

4 實驗結(jié)果與分析

實驗采用的3D點云數(shù)據(jù)源于Stanford 3D Scanning Repository[19]，如圖2所示。圖2(a)為初始兔子點云數(shù)據(jù)模型，圖2(b)為初始龍點云數(shù)據(jù)模型。采用本文點云配準算法，首先通過局部特征提取、相關(guān)性計算和外點刪減等步驟后，得到的粗配準的結(jié)果如圖3(a)所示，然后采用本文提出的改進ICP算法進細配準，細配準結(jié)果如圖3(b)所示。

圖2 待配準點云

圖3 點云配準結(jié)果

從圖3的配準結(jié)果可見，本文提出的基于局部特征的點云配準算法具有良好的配準效果。為了進一步驗證本文算法的良好性能，在細配準階段，分別采用ICP算法、文獻[20]中特征改進的ICP算法和本文改進的ICP算法進行細配準，其點云類型、初始點云大小、采用算法、配準點數(shù)、配準誤差（均方根）、迭代次數(shù)和耗時等參數(shù)見表1。

從表1的配準結(jié)果可見，ICP算法、文獻[20]算法和改進的ICP算法均能實現(xiàn)點云的細配準，但是文獻[20]算法和改進的ICP算法的配準精度明顯提高、耗時明顯縮短。特別是改進的ICP算法，其配準精度比ICP算法和文獻[20]算法分別提高了約50%和40%，配準速度比ICP算法和文獻[20]算法分別提高了約65%和50%。這是由于在ICP算法中引入了旋轉(zhuǎn)角約束，可以降低點云因旋轉(zhuǎn)角變化過大而引起的配準效果不佳的問題，由此大大提高了算法的配準精度。此外，在ICP算法中還引入了動態(tài)迭代系數(shù)，可以在不影響算法的配準精度和收斂方向的情況下，大大提高算法的迭代速度，降低耗時。因此說，本文的基于局部區(qū)域的點云配準算法是一種精度更高、速度更快的點云配準算法。

表1 細配準算法的配準參數(shù)

5 結(jié) 論

通過描述點云局部特征的方式，本文提出了一種快速、高精度的低覆蓋率點云配準算法。該算法利用局部深度、法線偏角和點云密度等局部特征生成特征描述子，并據(jù)此建立點的相關(guān)性，進而通過改進的ICP算法實現(xiàn)點云的快速、精確配準，對低覆蓋率的點云具有良好的配準效果。在將來的點云配準算法研究中，要綜合考慮多種因素，做進一步的深入研究，比如進一步完善特征描述子，融入更多的空間信息；在算法的抗噪性方面做進一步的研究，提高算法的配準精度；將算法應(yīng)用到特殊剛體曲面的配準中，如兵馬俑碎塊的斷裂面匹配，以擴大算法的應(yīng)用范圍。

[1] ALBARELLI A, RODOLà E, TORSELLO A. Fast and accurate surface alignment through an isometry-enforcing game [J]. Pattern Recognition, 2015, 48 (7): 2209-2226.

[2] GONG M G, WU Y, CAI Q, et al. Discrete particle swarm optimization for high-order graph matching [J]. Information Sciences, 2016, 328: 158-171.

[3] LIU A A, WANG Z Y, NIE W Z, et al. Graph-based characteristic view set extraction and matching for 3D model retrieval [J]. Information Sciences, 2015, 320: 429-442 .

[4] 林曉, 王燕玲, 朱恒亮, 等. 基于自適應(yīng)權(quán)值的點云三維物體重建算法研究[J]. 圖學(xué)學(xué)報, 2016, 37(2): 143-148.

[5] ALHAMZI K, ELMOGY M, BARAKAT S. 3D object recognition based on local and global features using point cloud library [J]. International Journal of Advanced Computer Science. 2015, 7(3): 43.

[6] GUO Y L, SOHEL F, BENNAMOUB M, et al. A novel local surface feature for 3D object recognition under clutter and occlusion [J]. Information Sciences, 2015, 293: 196-213.

[7] LIANG R, SHEN W, LI X X, et al. Bayesian multi-distribution-based discriminative feature extraction for 3d face recognition [J]. Information Sciences, 2015, 320: 406-417.

[8] GUO Y, BENNAMOUN M, SOHEL F, et al. An integrated framework for 3-d modeling, object detection, and pose estimation from point clouds [J]. IEEE Transactions on Instrumentation and Measurement. 2015, 64(3): 683-693.

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

[10] HAN J D, YIN P, HE Y Q. Enhanced ICP for the registration of large scale 3D environment models: an experimental study [J]. Sensors, 2016, 16(2): 228.

[11] 王森, 王璐, 洪靖惠, 等. 基于 Sparse ICP 的三維點云耳廓識別[J]. 圖學(xué)學(xué)報, 2015, 36(6): 862-867.

[12] LI W M, SONG P F. A modified ICP algorithm based on dynamic adjustment factor for registration of point cloud and CAD model [J]. Pattern Recognition Letters, 2015, 65: 88-94.

[13] MAVRIDIS P, ANDREADIA A, PAPAIOANNOU G. Efficient sparse ICP [J]. Computer Aided Geometric Design, 2015, 35-36: 16-26.

[14] DU S Y, LIU J, ZHANG C J, et al. Probability iterative closest point algorithm for-D point set registration with noise [J]. Neurocomputing, 2015, 157: 187-198.

[15] DU S Y, ZHENG N N, XIONG L, et al. Scaling iterative closest point algorithm for registration of-D point sets [J]. Journal of Visual Communication and Image Representation, 2010, 21(5-6): 442-452.

[16] MITRA N J, NGUYEN A. Estimating surface normals in noisy point cloud data [C]//SCG′03 Proceeding of the 19thACM Annual Symposium on Computational Geometry. New York: ACM Press, 2003: 322-328.

[17] KAMMERL J, BLODOW N, RUSU R B, et al. Real-time compression of point cloud streams [C]// IEEE International Conference on Robotics and Automation (ICRA), New York: IEEE Press, 2012: 778-785 .

[18] WIKIPEDIA. Rotation matrix [EB/OL]. [2017-1-15]. http://en.wikipedia.org/w/index.php?title=Rotation_matrix&oldid=624815514.

[19] Stanford University Computer Graphics Laboratory. The stanford 3D scanning repository [EB/OL]. [2017-1-14]. http://graphics.stanford.edu/data/3Dscanre.

[20] 賀永興, 歐新良, 匡小蘭. 鄰域特征在點云配準中的應(yīng)用[J]. 計算機應(yīng)用, 2012, 32(3): 762-765, 769.

Point Cloud Registration Algorithm Based on Local Features

ZHAO Fuqun1,2, ZHOU Mingquan2,3, GENG Guohua2

(1. School of Education Science, Xianyang Normal University, Xianyang Shaanxi 712000, China; 2. School of Information Science and Technology, Northwest University, Xi’an Shaanxi 710127, China; 3. School of Information Science and Technology, Beijing Normal University, Beijing 100875, China)

Aiming at low-coverage-rate point clouds, a registration algorithm was proposed based on local features in the paper. Firstly, local features including the local depth, deviation angle between normals and point cloud density are extracted, and the local feature descriptor is obtained. Secondly, the correspondence of local feature sets is calculated and the corresponding candidates are gained. Thirdly, the outliers are eliminated and coarse registration is achieved. Lastly, an improved iterative closest point (ICP) algorithm based on the rotation angle constraint, and the dynamic iterative coefficient is employed to complete fine point cloud registration. The experiment results reveal that the point cloud registration algorithm could achieve the precise registration of low-coverage-rate point cloud, based on local features, a high-precision and fast one.

point cloud registration; local feature; iterative closest point; rotation angle constraint; dynamic iterative coefficient

TP 391

10.11996/JG.j.2095-302X.2018030389

A

2095-302X(2018)03-0389-06

2017-02-14；

2017-03-16

國家自然科學(xué)基金項目(61731015)；咸陽發(fā)展研究院服務(wù)地方經(jīng)濟社會發(fā)展項目(2018XFY007)

趙夫群(1982-)，女，山東臨沂人，博士研究生。主要研究方向為圖形圖像處理。E-mail：fuqunzhao@126.com

周明全(1954-)，男，陜西西安人，教授，博士，博士生導(dǎo)師。主要研究方向為圖形圖像處理。E-mail：354449904@qq.com