李 健，楊靜茹，何 斌

?

一種應(yīng)用于大角度變換點云的配準方法

李 健1，楊靜茹1，何 斌2

(1. 陜西科技大學(xué)電氣與信息工程學(xué)院，陜西 西安 710021；2. 同濟大學(xué)電子與信息工程學(xué)院，上海 201804)

針對傳統(tǒng)配準法不能很好解決大角度變換點云的配準這一問題，提出一種基于精確對應(yīng)特征點對及其鄰域點云的配準方法。首先分別計算兩組點云的FPFH值，根據(jù)特征值建立點云間的對應(yīng)關(guān)系；然后通過RANSAC濾除其中錯誤的匹配點對，得到相對精確的特征點對集合；之后通過KD-tree搜索的方式分別找出特征點對半徑鄰域內(nèi)的點，應(yīng)用ICP算法得到兩部分點云的最優(yōu)收斂；最后將計算得到的相對位置關(guān)系應(yīng)用到原始點云上得到配準結(jié)果。通過對斯坦福大學(xué)點云庫中Dragon、Happy Buddha模型以及Kinect采集的石膏像數(shù)據(jù)進行配準和比較，實驗表明該方法能夠有效解決大角度變換點云的配準問題，是一種具有高精度和高魯棒性的三維點云配準方法。

點云配準；快速點特征直方圖；隨機采樣一致；迭代最近點；KD-Tree

三維重建是計算機視覺中的一個重要組成部分，包含點云的采集、去噪、配準、融合、紋理映射等步驟，點云配準是三維重建中最重要也是最復(fù)雜的一步。現(xiàn)有的深度相機等三維測量設(shè)備一次只能測量物體一個方向上的數(shù)據(jù)，因此要得到物體的三維模型就必須將多次測量得到的點云數(shù)據(jù)通過配準合并成一個完整的三維模型。

點云配準這一概念自上世紀提出以來，涌現(xiàn)出了許多經(jīng)典的算法。BESL等[1-2]提出的迭代最近點(iterative closest point，ICP)算法原理簡單且易于實現(xiàn)，但需要為待配準點云提供一個較好的初值，否則迭代結(jié)果容易陷入局部最優(yōu)。在基于特征的配準算法中，RUSU等[3]提出的點特征直方圖(point feature histograms，PFH)計算方式通過多維直方圖來描述查詢點與鄰域點之間的空間差異。PFH的改進算法稱為快速點特征直方圖(fast point feature histograms，F(xiàn)PFH)[4-5]，F(xiàn)PFH在降低算法復(fù)雜度的同時保留了PFH大部分的特性，但該方法容易生成錯誤的對應(yīng)關(guān)系從而導(dǎo)致配準失敗。在基于幾何形狀的配準算法中，4PCS算法[6-7]通過查找兩個點集上全等且共面的四邊形建立對應(yīng)關(guān)系，但對于重疊區(qū)域較小的點集，通常難以找到對應(yīng)關(guān)系?；?PCS方法的Super4PCS算法[8]改善了這一問題，但其時間復(fù)雜度仍然遠高于同類算法。

上述算法對于簡單的點云配準問題大都能得到較好的效果。但實際的應(yīng)用場景中，待配準的點云往往存在重合區(qū)域過小、點云間變換角度大等情況，傳統(tǒng)算法在這樣的場景下往往難以得到理想的效果。本文提出一種基于精確對應(yīng)特征點對及其鄰域點云的配準方法，融合FPFH、隨機采樣一致性(random sample consensus，RANSAC)算法[9]與ICP算法，基于PCL[10]實現(xiàn)，能夠較好地解決復(fù)雜場景下的點云配準問題。

1 算法總體描述

當兩片點云的初始位置變換角度過大時，難以通過一次配準就得到滿意的結(jié)果，因此通常需要先經(jīng)過粗配準步驟對兩片點云進行初始配準，得到近似的旋轉(zhuǎn)平移矩陣。在粗配準提供的良好初始匹配的基礎(chǔ)上，精配準步驟通過進一步的計算能夠得到兩幀點云間更為精確的相對位置關(guān)系。本文方法分為粗配準和精配準兩個步驟，具體流程如圖1所示。

圖1 本文算法流程示意圖

圖1中的原始點云分別為源點云和參考點云。在粗配準過程中，采用基于特征的FPFH方法得到初始對應(yīng)關(guān)系，再通過RANSAC算法濾除誤匹配，得到相對精確的對應(yīng)關(guān)系。在精配準過程中，為減少計算量，采用KD-Tree搜索[11]的方式選取精確對應(yīng)點對的半徑鄰域點云，應(yīng)用ICP算法計算兩部分點云的位置關(guān)系，將該變換關(guān)系應(yīng)用到原始點云上得到最終的配準結(jié)果。

2 算法詳細描述

2.1 基于FPFH的粗配準

粗配準采用基于快速點特征直方圖計算方式的方法來實現(xiàn)，具體的步驟包括特征計算、誤匹配篩除等步驟。

2.1.1 快速點特征直方圖描述子搜索對應(yīng)點

FPFH是一種空間局部點特征描述子，通過計算查詢點與其鄰域內(nèi)元素的法線之間的關(guān)系來表示點云表面的變化情況，并通過一個多維直方圖對點云的幾何特性進行描述。FPFH計算的影響區(qū)域如圖2所示。

圖2 FPFH影響區(qū)域示意圖

查詢點P位于圖2中半徑為的球形中心，查詢點與其所有鄰元素相互連接。為方便計算兩點間的關(guān)系，在坐標系中計算任意兩點P和P及與其對應(yīng)的法線n和n之間的相對偏差。坐標系如圖3所示。

圖3 UVW坐標示意圖

3個方向分別用、、表示，其中

使用的坐標系，法線n和n之間的差可以化解為下面3個角度的差異，即

分別將、、從0°~360°等分為11個區(qū)間，創(chuàng)建一個有33個等分區(qū)間的直方圖，每個區(qū)間對應(yīng)特定范圍內(nèi)特征值的個數(shù)。按照如下步驟計算查詢點的FPFH值：

步驟1.計算查詢點P與其影響區(qū)域內(nèi)所有點的3個特征值，統(tǒng)計每個區(qū)間所對應(yīng)的特征值的個數(shù)，得到簡化的點特征直方圖SPFH。

步驟2.重新確定每個點的鄰域，根據(jù)式(3)使用鄰近的SPFH計算的最終FPFH。

其中，P為P的鄰域點；權(quán)重W是P與P之間的距離；為鄰域點P的個數(shù)。

計算得到的快速點特征直方圖如圖4所示，圖4(b)為4(a)中某點的快速點特征直方圖。

2.1.2 RANSAC濾除誤匹配

通過比較FPFH值得到的對應(yīng)關(guān)系并不是完全正確的，采用RANSAC算法剔除其中的錯誤匹配，能夠得到相對準確的對應(yīng)關(guān)系。

RANSAC算法是一種簡單有效的去除誤匹配的方法，通過建立一個特定的數(shù)學(xué)模型將數(shù)據(jù)點分為“內(nèi)點”和“外點”，采用迭代估計的方法計算出最優(yōu)參數(shù)模型，找到的不符合該模型“外點”為誤匹配點，符合模型的“內(nèi)點”為精確匹配。以圖5為例，圖中實線對應(yīng)正確匹配，線條兩點為“內(nèi)點”，虛線為誤匹配，線條端點為“外點”。

圖4 快速點特征直方圖示例

圖5 RANSAC示意圖

RANSAC步驟結(jié)束后可以得到較為正確的匹配關(guān)系。但由于FPFH計算方式描述的是查詢點與其鄰域點之間的關(guān)系，這一特性導(dǎo)致在點云表面曲率變化較小或者點云密集的區(qū)域中相鄰點的FPFH值非常接近，因此可能會發(fā)生對應(yīng)到正確匹配附近點的情況，如圖5中2號對應(yīng)關(guān)系所示，由于相鄰點的FPFH值非常接近，所以根據(jù)特征值判定圖5中2號線兩端的點為對應(yīng)點。該對應(yīng)關(guān)系雖不完全準確，但卻在RANSAC步驟所建立數(shù)學(xué)模型的容差范圍內(nèi)，所以認定其為正確匹配。這種不準確的映射關(guān)系會對配準結(jié)果產(chǎn)生負面影響，也是需要精配準步驟的原因。

2.2 基于關(guān)鍵點鄰域的精配準

在粗配準所提供的初始匹配的基礎(chǔ)上，精配能夠進一步改進和完善配準結(jié)果。精配準分為基于KD-tree的關(guān)鍵點鄰域搜索和ICP計算變換關(guān)系兩個步驟。

2.2.1 基于KD-tree的關(guān)鍵點鄰域搜索

粗配準步驟結(jié)束后，可以直接通過ICP算法計算點云的變換關(guān)系，但在已經(jīng)得到較為精確的對應(yīng)關(guān)系的前提下，通過KD-tree搜索的方式選擇對應(yīng)點鄰域計算相對位置關(guān)系，可以節(jié)省計算成本。使用KD-tree搜索的方式選擇對應(yīng)點對半徑內(nèi)的點云計算最終的變換關(guān)系矩陣。

在具體的搜索過程中，將特征點作為查詢點輸入，給定查詢點和查詢距離的閾值(即查詢半徑)，從點云找出所有與查詢點距離小于閾值的點。如圖6所示，以空間中一點P為圓心，給定的查詢距離為半徑畫球體，球體內(nèi)點與P的距離小于半徑的點即為所要查找的鄰域點。

圖6半徑搜索示意圖

2.2.2 ICP計算變換關(guān)系

通過半徑搜索得到的對應(yīng)區(qū)域是整體模型的一部分，只計算該部分點云的變換關(guān)系能夠節(jié)約計算成本，將計算得到的、矩陣應(yīng)用到原始模型上即可得到最終配準結(jié)果。

三維點云的配準問題可轉(zhuǎn)化為求解使式(5)中目標函數(shù)最小時的和的問題，即

其中，為點集中對應(yīng)點對的個數(shù)；、分別為旋轉(zhuǎn)、平移變換矩陣。

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

本文以斯坦福大學(xué)三維點云庫中Bunny模型為例，詳細分析本文方法在實驗中的具體步驟，并以斯坦福大學(xué)點云集中的Dragon、Happy Buddha以及Kinect采集的石膏像模型為例，將本文方法與ICP算法和Super 4PCS算法從配準效果和計算效率上做以對比。實驗環(huán)境如下：

(1) 電腦配置：Intel Core i7-4790 CPU/8 G，RAM/AMD Radeon R7 250顯卡/無GPU加速；

(2) 數(shù)據(jù)集來源：斯坦福大學(xué)點云集；

(3) 算法實現(xiàn)：PCL點云庫/C++語言。

斯坦福兔子掃描數(shù)據(jù)Bunny000和Bunny045模型在初始狀態(tài)下的位置關(guān)系如圖7(a)所示，Bunny000和Bunny045是對同一個兔子模型分別從0°和45°掃描得到的點云數(shù)據(jù)，兩片點云間含有部分不共有的數(shù)據(jù)。

圖7 實驗步驟

在粗配準過程中：首先對圖7(a)中的點分別計算其FPFH值，根據(jù)設(shè)定的閾值選擇特征相近的點作為對應(yīng)點對。圖7(b)的連線為根據(jù)閾值篩選出的對應(yīng)點對之間的連線，該對應(yīng)關(guān)系并不完全正確。圖7(c)為通過RANSAC步驟濾除誤匹配后得到的對應(yīng)關(guān)系。

在精配準步驟中：首先通過KD-tree搜索的方式找出特征點對半徑鄰域內(nèi)的點，如圖7(d)所示，圖中的亮點為特征點，附近的點為其鄰域點。圖7(e)為選取圖7(d)中的點分別作為目標點集和參考點集通過ICP算法進行配準得到的結(jié)果，圖7(f)為在原始點云上應(yīng)用圖7(e)計算出的變換矩陣、得到的配準結(jié)果。

為驗證本文方法的魯棒性，選取了3種共計5組各具特色的模型進行實驗。Stanford 點云集中的Dragon模型表面曲率變化較大且具有豐富的細節(jié)，選取Dragon中的Dragon0與Dragon24兩幀數(shù)據(jù)在掃描時有24°的旋轉(zhuǎn)，因此含有部分點云不共有的點。在此基礎(chǔ)上將Dragon24模型分別沿、、軸旋轉(zhuǎn)30°，平移0.05 m，模型位置關(guān)系如圖8(a)所示。

圖8(b)為本文方法的配準結(jié)果，圖8(c)、8(d)分別為ICP和Super4PCS算法的配準結(jié)果。

圖9的數(shù)據(jù)來源為Dragon模型中的Dragon0與Dragon48兩幀數(shù)據(jù)，二者掃描時的角度差為48°，相比于圖9中的數(shù)據(jù)，Dragon0與Dragon48的重疊區(qū)域更少。在此基礎(chǔ)上，將Dragon48模型分別沿著、、軸旋轉(zhuǎn)60°，平移0.1 m，得到圖9(a)所示位置關(guān)系。圖9(b)~(d)分別為本文算法、ICP算法和Super4PCS算法的實驗結(jié)果。

與Dragon相比，Happy Buddha模型表面曲率變化相對平緩，但缺乏細節(jié)。圖10中的數(shù)據(jù)來源為Happy Buddha模型中相鄰的兩幀數(shù)據(jù)Happy Buddha0與Happy Buddha24。

圖8 Dragon0和Dragon24數(shù)據(jù)對比結(jié)果(下行為俯視圖)

圖9 Dragon0和Dragon48數(shù)據(jù)對比結(jié)果

圖10 Happy Buddha0和Happy Buddha24數(shù)據(jù)對比結(jié)果(下行為俯視圖)

Happy Buddha0與Happy Buddha24在掃描時的旋轉(zhuǎn)角度為24°，在此基礎(chǔ)上，將Happy Buddha24分別沿著、、軸旋轉(zhuǎn)90°，平移0.15 m，得圖10(a)中的初始位置關(guān)系。圖10(b)~(d)分別為各算法對比結(jié)果。

圖11中的數(shù)據(jù)來源為Happy Buddha模型中的Happy Buddha0與Happy Buddha48兩幀數(shù)據(jù)，二者在掃描時的旋轉(zhuǎn)角度為48°，相較于圖11中的模型，重疊的點云數(shù)據(jù)更少。在此基礎(chǔ)上，將Happy Buddha48模型分別沿、、軸旋轉(zhuǎn)120°，平移0.2 m，位置關(guān)系如圖11(a)所示，圖11(b)為本文算法配準結(jié)果，圖11(c)為ICP算法配準結(jié)果，圖11(d)為Super4PCS算法的配準結(jié)果。

圖11 Happy Buddha0和Happy Buddha48數(shù)據(jù)對比結(jié)果(下行為俯視圖)

圖12中的數(shù)據(jù)為手持Microsoft Kinect相機在隨機角度上采集的兩幀點云數(shù)據(jù)，點云未經(jīng)濾波去噪等處理，初始位置如圖12(a)所示。

圖12(b)為本文算法配準結(jié)果，圖12(c)為ICP算法的結(jié)果，圖12(d)為Super4PCS算法的結(jié)果。

表1為本文算法與ICP算法和Super4PCS算法的對比結(jié)果。從圖8~12中可以看出，ICP算法配準大角度變化點云容易陷入局部最優(yōu)，從而導(dǎo)致配準失敗。在對表1第一組數(shù)據(jù)Dragon0和Dragon24的配準中，相比于ICP算法，本文算法的RMS值降低了75.2%，相比于Super4PCS算法RMS值降低了42.0%，在時間花費上，本文算法花費時間高于ICP算法14.2%，但由于ICP算法配準失敗，該數(shù)據(jù)不具有參考價值，Super4PCS所用時間為本文算法的7倍；在第二組數(shù)據(jù)中，本文算法的RMS相比于ICP和Super4PCS算法分別降低了62.2%、15.2%，花費時間為Super4PCS算法的11.8%；在第三組數(shù)據(jù)中，本文算法的RMS相比于ICP和Super4PCS算法分別降低了64.3%、36.1%，花費時間為Super4PCS算法的16.6%；在第四組數(shù)據(jù)中，本文算法的RMS相比于ICP和 Super4PCS算法分別降低了46.8%、6.5%，花費時間為Super4PCS算法的2.9%；在第五組數(shù)據(jù)中，本文算法的RMS相比于ICP和 Super4PCS算法分別降低了50.0%、6.3%，花費時間為Super4PCS算法的30.4%。綜上所述，本文算法能夠有效解決大角度變換點云的配準問題，并得到相對優(yōu)于ICP和Super4PCS算法的結(jié)果。

圖12 Kinect采集數(shù)據(jù)隨機兩幀對比結(jié)果(下行為俯視圖)

表1 算法對比表

4 結(jié)束語

本文通過總結(jié)和分析點云數(shù)據(jù)配準算法的研究現(xiàn)狀，發(fā)現(xiàn)了點云配準中存在的大變換角度點云難以配準這一問題，提出了一種基于精確對應(yīng)特征點對及其鄰域點云的配準方法。通過利用點云的特征信息找出初始對應(yīng)關(guān)系，再濾除掉錯誤對應(yīng)點對得到粗配準結(jié)果，在此基礎(chǔ)上選擇精確對應(yīng)點對鄰域點云計算最優(yōu)收斂。實驗表明，該方法能夠在節(jié)約計算成本的同時有效解決大角度變換、只有部分重合點云的配準問題。

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

[2] 趙夫群, 周明全. 改進的概率迭代最近點配準算法[J]. 圖學(xué)學(xué)報, 2017, 38(1):15-22.

[3] RUSU R B, MARTON Z C, BLODOW N, et al. Learning informative point classes for the acquisition of object model maps [C]//International Conference on Control, Automation, Robotics and Vision. New York: IEEE Press, 2008: 643-650.

[4] RUSU R B, BLODOW N, BEETZ M. Fast point feature histograms (FPFH) for 3D registration [C]//IEEE International Conference on Robotics and Automation. New York: IEEE Press, 2009: 3212-3217.

[5] 馬大賀, 劉國柱. 改進的基于FPFH特征配準點云的方法[J]. 計算機與現(xiàn)代化, 2017(11):46-50.

[6] AIGER D, MITRA N J, COHEN-OR D. 4-points congruent sets for robust pairwise surface registration [J]. Acm Transactions on Graphics, 2008, 27(3):1-10.

[7] 余文利, 周明全, 稅午陽,等. 基于曲率的點云自動配準方法[J]. 系統(tǒng)仿真學(xué)報, 2015, 27(10):2374-2379.

[8] MELLADO N, AIGER D, MITRA N J. Super 4PCS fast global pointcloud registration via smart indexing [J]. Computer Graphics Forum, 2015, 33(5):205-215.

[9] CHUM O, MATAS J, KITTLER J. Locally optimized RANSAC [C]//Joint Pattern Recognition Symposium. Berlin: Springer, 2003:236-243.

[10] RUSU R B, COUSINS S. 3D is here: point cloud library (PCL) [C]//IEEE International Conference on Robotics and Automation. New York: IEEE Press, 2011:1-4.

[11] ANGELO L D, GIACCARI L. An efficient algorithm for the nearest neighbourhood search for point clouds [J]. International Journal of Computer Science Issues, 2011, 8(5):1-11.

A Registration Method for Large-Angle PointClouds

LI Jian1, YANG Jingru1, HE Bin2

(1. School of Electrical and Information Engineering, Shaanxi University of Science & Technology, Xi’an Shaanxi 710021, China; 2. School of Electronics and Information Engineering, Tongji University, Shanghai 201804, China)

To the problem of traditional registration algorithm are difficult to get the desired effect in large-angle pointcloud registration. We proposed a registration method based on exact correspondence feature point pairs and its-neighbour pointclouds. Firstly, calculate the FPFH of the pointclouds separately, establishing correspondences between point clouds According to the eigenvalues; Then remove the erroneous matching point pairs by RANSAC, and obtain a relatively accurate set of feature point pairs; Moreover, using KD-tree search get the-Rad region of the feature point pairs respectively, and applying ICP to obtain the optimal convergence of pointclouds. Finally, applying the ICP relative position relationship to the original pointclouds to get the final registration result. Through registration testing and comparison of the Stanford Dragon, Happy Buddha pointcloud models, and Gypsum data scanned by Kinect, The experiment shows that this method can effectively solve the registration problem of pointclouds with large angle transformation, its a 3D pointclouds registration method with high accuracy and robustness.

pointcloud registration; fast point feature histograms; random sample consensus; iterative closest point; KD-tree

TP 391

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

A

2095-302X(2018)06-1098-07

2018-03-26；

2018-04-18

國家自然科學(xué)基金項目(51538009)；陜西省工業(yè)攻關(guān)項目(2015GY044）

李 健(1975-)，男，陜西蒲城人，教授，博士，碩士生導(dǎo)師。主要研究方向為計算機視覺、計算機圖形學(xué)。E-mail：lijian@sust.edu.cn

何 斌(1975-)，男，安徽安慶人，教授，博士，博士生導(dǎo)師。主要研究方向為新型機器人動力學(xué)及智能控制、多種傳感器技術(shù)與數(shù)據(jù)網(wǎng)絡(luò)集成應(yīng)用、大型復(fù)雜機構(gòu)動力學(xué)與在線監(jiān)測、圖像檢測與識別技術(shù)及應(yīng)用。E-mail：hebin@#edu.cn