趙夫群，周明全，耿國華

?

基于局部特征的點(diǎn)云配準(zhǔn)算法

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

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

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

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

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

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

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

1 局部特征描述子

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

1.1 局部深度特征

1.2 法線的偏角

1.3 點(diǎn)云密度

計(jì)算了點(diǎn)的3個(gè)局部幾何特征后，可以得到3個(gè)子直方圖，然后將其合成為1個(gè)直方圖，即可得到局部特征的描述子。

2 粗配準(zhǔn)算法

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

圖1 局部特征示意圖

2.1 局部特征提取

2.2 相關(guān)性計(jì)算

2.3 外點(diǎn)刪減

3 細(xì)配準(zhǔn)算法

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

3.1旋轉(zhuǎn)角約束

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

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

3.3 改進(jìn)的ICP算法

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

4 實(shí)驗(yàn)結(jié)果與分析

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

圖2 待配準(zhǔn)點(diǎn)云

圖3 點(diǎn)云配準(zhǔn)結(jié)果

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

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

表1 細(xì)配準(zhǔn)算法的配準(zhǔn)參數(shù)

5 結(jié) 論

通過描述點(diǎn)云局部特征的方式，本文提出了一種快速、高精度的低覆蓋率點(diǎn)云配準(zhǔn)算法。該算法利用局部深度、法線偏角和點(diǎn)云密度等局部特征生成特征描述子，并據(jù)此建立點(diǎn)的相關(guān)性，進(jìn)而通過改進(jìn)的ICP算法實(shí)現(xiàn)點(diǎn)云的快速、精確配準(zhǔn)，對低覆蓋率的點(diǎn)云具有良好的配準(zhǔn)效果。在將來的點(diǎn)云配準(zhǔn)算法研究中，要綜合考慮多種因素，做進(jìn)一步的深入研究，比如進(jìn)一步完善特征描述子，融入更多的空間信息；在算法的抗噪性方面做進(jìn)一步的研究，提高算法的配準(zhǔn)精度；將算法應(yīng)用到特殊剛體曲面的配準(zhǔn)中，如兵馬俑碎塊的斷裂面匹配，以擴(kuò)大算法的應(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)值的點(diǎn)云三維物體重建算法研究[J]. 圖學(xué)學(xué)報(bào), 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 的三維點(diǎn)云耳廓識(shí)別[J]. 圖學(xué)學(xué)報(bào), 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] 賀永興, 歐新良, 匡小蘭. 鄰域特征在點(diǎn)云配準(zhǔn)中的應(yīng)用[J]. 計(jì)算機(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é)基金項(xiàng)目(61731015)；咸陽發(fā)展研究院服務(wù)地方經(jīng)濟(jì)社會(huì)發(fā)展項(xiàng)目(2018XFY007)

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

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