艾 達，王 苗，倪國斌

(1.西安郵電大學 公安部電子信息勘查應用技術重點實驗室，西安 710121)2.西安郵電大學 通信與信息工程學院，西安 710061)

基于FPFH特征的三維場景重建

艾 達1，王 苗2，倪國斌2

(1.西安郵電大學 公安部電子信息勘查應用技術重點實驗室，西安 710121)2.西安郵電大學 通信與信息工程學院，西安 710061)

文章在闡述不同視角下在對一對三維點云數(shù)據(jù)集兩兩配準的基礎之上，針對ICP精確匹配算法須使初始點云收斂否則無法獲取準確匹配結(jié)果的問題，提出了基于FPFH特征描述子的特征點云粗匹配;調(diào)整兩片點云的初始位置，為ICP算法提供了良好的初始位置進一步提高點云的匹配精度;并且在此基礎上通過大量實驗得到點云對應點對之間的最大距離與擬合系數(shù)的函數(shù)關系，得到粗匹配最優(yōu)值，進而得到最佳配準效果。實驗證明通過粗匹配最高能將匹配擬合系數(shù)提高60.3%。

兩兩配準;FPFH特征;粗匹配

0 引言

三維場景重建(three-dimensional scene reconstruction)技術[1]在三維視覺領域快速發(fā)展并流行的一門新技術，通過計算機數(shù)字化手段，將客觀世界中的三維實體真實再現(xiàn)在計算機中，是計算機視覺、人工智能、虛擬現(xiàn)實、人機交互等前沿領域的熱點和難點,與傳統(tǒng)的通過圖片等二維圖像，利用先驗知識從物體的二維信息中推斷出三維模型的建模技術相比，其在重建效率、精度和實時性方面都有很大提高。

點云配準作為三維重建技術的關鍵技術之一，能將多角度下獲取的點云，變換到同一坐標系下[2]。文獻[3]在基于傳統(tǒng)四元數(shù)算法的基礎上提出迭代最近點(iterative closest points)ICP算法。文獻[4]對文獻[3]進行改進，通過特征度量建立迭代優(yōu)化函數(shù)。文獻[5]提出基于GPU的KinectFusion重建技術，文獻[6]利用測量得到的橫向和縱向噪聲分布，應用于KinectFusion系統(tǒng)體融合及管道內(nèi)姿態(tài)估計，得到精細模型重建。文獻[7]提出運動恢復結(jié)構(gòu)(structure from motion，SFM)算法，在攝像機定位和稀疏表面重建重建效果精確。

這些算法被提出之后，很快廣泛的應用到三維重建的領域中，取得了一些成果[8],但是對于透明物體和平面物體的重建效果并不是很好，因此文章在前人研究的基礎上，介紹了迭代最近點(iterative closest points)ICP算法通過配準和融合將獲得的深度圖像合并起來[9]，但是ICP算法要求待配準的點云具有較好的初始位置，否則難以獲得較好的匹配效果。因此在ICP精匹配之前，應先對點云進行粗配準，調(diào)整兩片部分重疊點云的初始位置。在對點云的粗配準的計算過程中，首先計算兩幅圖像的關鍵點，其次計算其關鍵點處快速點特征直方圖描述子(FPFH)[10],然后提取三組隨機點對，計算點對之間的轉(zhuǎn)換關系，將該對應關系應用于所有點對的轉(zhuǎn)換，最后設置閾值，得到最佳的轉(zhuǎn)換關系。

1 三維場景重建及其步驟

圖1是三維重建流程圖，首先利用激光掃描儀[11]或三維相機[12]等獲取三維景深數(shù)據(jù)。其次進行點云預處理，消除由于設備精度、環(huán)境因素等點云數(shù)據(jù)中的噪聲點，濾波作為點云處理流程的第一步，對后續(xù)處理管道影響很大。對濾波后的點云進行下采樣能在不影響精度的情況下，簡化點云數(shù)量，提高匹配效率。再次，對得到的點云進行配準[13]，先求取三維數(shù)據(jù)的法線信息，然后利用其法線信息提取一對點云的FPFH特征，最后使用采樣一致性初始匹配算法(SAC-IA算法)獲取點云的初始變換矩陣，在粗匹配的基礎上進行ICP精確配準。最后使用貪婪投影三角化算法對點云進行三角化得到重建表面。

圖1 三維重建流程圖

2 點云匹配算法

在實際的點云獲取過程中，由于點云的獲取會出現(xiàn)孔洞、旋轉(zhuǎn)錯位、平移錯位等，因此要得到完整的重建表面就需要對初始點云進行配準，以得到被測物體的完整三維模型。點云配準算法按照實現(xiàn)過程可以分為粗匹配和精確配準，確定一個剛體變換，將從各個視角得到的點集轉(zhuǎn)換到一個統(tǒng)一的坐標系下形成完整的數(shù)據(jù)點云，最后進行可視化操作。配準的最終目的是求得坐標變換參數(shù)R(旋轉(zhuǎn)矩陣)和T(平移矩陣)，使得不同視角下獲得的三維數(shù)據(jù)經(jīng)坐標變換后的距離最小。

2.1 點云粗匹配的步驟

點云粗匹配是指在點云之間初始轉(zhuǎn)換矩陣位置是，通過提取各自點云里的特征點并獲取其位置處的特征描述符來唯一性的代表各自點云，繼而正確的匹配兩點云的特征描述符，求取平移向量和旋轉(zhuǎn)矩陣，經(jīng)過轉(zhuǎn)換將散亂點云初始位置對齊，提高ICP算法精確匹配的匹配精度，圖2所示為點云粗匹配流程圖。

圖2 點云粗匹配流程圖

2.2 點特征直方圖(PFH)

點特征直方圖(PFH)是一種以統(tǒng)計直方圖的形式來描述一個樣本點周圍的局部幾何特征信息的點特征表示方法，PFH統(tǒng)計的是樣本點與其k鄰域之間的關系和它們估計的法線之間的關系，即通過估計法線方向之間所有的相互作用，試圖得到最好的樣本表面變化情況，以描述樣本的幾何特征。圖3所示表示的是一個查詢點(pq)的PFH計算的影響區(qū)域，半徑為r，(pq)的所有k鄰元素全部互相連接在一個網(wǎng)絡中，最終PFH描述子通過計算鄰域內(nèi)所有兩點之間關系而得到的直方圖。

圖3 查詢點pq的PFH計算的影響區(qū)域

其具體計算如下：

1)對樣本點p查詢其鄰k臨域內(nèi)所有鄰近點。

2)對點p的k鄰域中每對點ps和pt(s!=t)和它們對應的估計法線ns和nt，定義一個uvw坐標系來計算ps和pt以及它們對應的估計法線ns和nt之間的偏差，在其中的一個點上定義一個固定的局部坐標系，如圖4。

圖4 一個固定的局部坐標系

(1)

使用上圖的uvw坐標系，用下面一組角度來表示估計法線ns和nt之間的偏差：

(2)

(3)

(4)

‖pt-ps‖表示兩點間的歐式距離，pq的所有k近鄰點中任意兩點之間的關系就可以用(α,β,θ,d)表示。鄰域內(nèi)所有的四組值以統(tǒng)計的方式放進直方圖，就得到pq點的直方圖特征。

2.3 快速點特征直方圖(FPFH)

快速點特征直方圖FPFH(fast point feature histograms)[10]是在PFH的基礎上通過簡化鄰域間的互聯(lián)降低了直方圖的特征計算復雜度，使其復雜度由O(nk2)降低為O(nk)，F(xiàn)PFH對每一個樣本點，首先計算這個點和它的k鄰域內(nèi)每個點之間α,β,θ3個特征值，統(tǒng)計輸出成一個簡化的點特征直方圖SPFH(simple point feature histograms)，然后重新確定每個點的k鄰域，利用公式(5)：

(5)

結(jié)合鄰近點pk的SPFH值來計算pq最終的直方圖FPFH。式中，權(quán)重ωk定義為查詢點pq和 鄰近點pk間的距離，表1是各個描述子維度對比。

表1 局部特征描述符比較

從表1中可以看出相比于其它3個描述符，F(xiàn)PFH的維度最小，大大降低了其時間復雜度，提高了運算速度。

3 ICP點云精確匹配算法

ICP算法的核心思想是：對不同坐標系下的兩個點云，找到其對應點迭代的縮小匹配點間的距離，直到距離小于設定的閥值，最終得到點云集間的最優(yōu)剛體變換，實現(xiàn)點云的配準，計算過程如下所示：

1)基于投影映射法的匹配點對獲取，由于攝像機一直處于運動狀態(tài)，所以必須將攝像機不同位置下獲得的點云數(shù)據(jù)由攝像機坐標轉(zhuǎn)換為全局坐標，進行融合。ICP算法利用基于投影映射法獲取匹配點對，首先計算每幀攝像機坐標Ok到全局坐標Og的剛體變換矩陣，用Tk,g=[Rk,g/tk,g]表示變換矩陣，Rk,g表示旋轉(zhuǎn)矩陣，tk,g表示平移向量。對于點云空間集Vk中任意一點S，坐標向量為Vk(u,v)，按照(5)式將攝像機坐標系下的任意定點坐標向量Vk,g(u,v)及法向量Nk,g(u,v)，轉(zhuǎn)換到全局坐標系Og下，利用(6)式前一幀變換逆矩陣，將Og下任意點向量Vk,g(u,v)映射到Ok-1坐標系下，然后通過攝像機反透視投影獲得對應點坐標(u',v')。

(5)

(6)

2)點到切平面距離誤差函數(shù)估計配準參數(shù)，距離誤差函數(shù)的優(yōu)化，本文采用文獻[14]提出的方法，將當前幀點云中的點到其在前一幀點云中的對應點所在切平面的距離作為誤差函數(shù)，誤差函數(shù)如(7)式：

(7)

(8)

(9)

其中，

4)重復迭代：當兩次迭代更新矩陣滿足一定的閥值，則停止迭代，轉(zhuǎn)換矩陣等于最后一次迭代矩陣。

4 仿真結(jié)果及分析

仿真實驗在VisualStdio2010環(huán)境下Inter(R)—core(TM)i3-4050 3.5GHz，4GB內(nèi)存的PC機上結(jié)合PCL點云開源庫[15]運行，為了驗證本文方法的有效性，實驗數(shù)據(jù)采用待配準的兩只斯坦福兔子點云分別作為源點云和目標點云。

4.1 特征點估計

表面法線是幾何體表面的重要屬性，由于我們獲取的點云數(shù)據(jù)集在真實物體的表面表現(xiàn)為一組頂點樣本，因此我們直接從點與數(shù)據(jù)集中近似推斷表面法線。圖5按每10個點顯示法線方向，由圖中可以看出點云表面法線方向一致。

圖5 點云法線估計

4.2 點特征直方圖

表面法線和曲率估計是某個點幾何特征的基本表示法，雖然計算快速容易，但獲取的信息有限，通過有限的參數(shù)值來近似表示一個點的K鄰域的幾何特征。然而大部分場景中包含許多特征點，這些特征點有非常相近的特征值，因此采用點特征直方圖，減少全局的特征信息。下圖分別是bun0和bun4兩個三維點云及其對應點的FPFH點特征直方圖，通過點特征直方圖獲得特征描述子，獲得匹配點對。

圖6(a)(b) 分別表示每幅圖對應的關鍵點處的FPFH點特征直方圖，可以看出使用局部特征的直方圖形式表示后，特征之間的差異量化的更加明顯。

圖6 兩幅點云各自關鍵點處的FPFH

4.3 對應點估計

通過兩側(cè)掃描的點云數(shù)據(jù)獲得的兩組特征向量，在此基礎上，找到相似特征獲得數(shù)據(jù)的特征點對，在此基礎上對點云進行配準,如圖7所示。

圖7 對應點估計

圖8～圖10 分別展示了點云未配準之前，直接使用ICP算法和使用改進型算法所得效果?？梢钥闯?，未配準之前，點云散亂的堆積在一起; 直接使用ICP配準，雖有一定效果，但誤差非常大; 而使用改進型算法配準后的點云完美的結(jié)合到一起。

圖8 點云未配準前

圖9 直接使用ICP算法進行精確配準

圖10 本文方法

本文采用基于FPFH特征點對的點云粗匹配，采用SAC-IA算法執(zhí)行配準計算，在該算法中有一個最關鍵的參數(shù)，即Maxcorrespondencediatance，為兩個點云中對應點對之間的最大距離，圖11是對應點最大距離與擬合系數(shù)的對應關系圖:

圖11 對應點對與擬合系數(shù)函數(shù)關系

從圖中可以發(fā)現(xiàn)，隨著對應點距離的增大，對應的擬合系數(shù)也在逐漸增大,當增加到一定程度，趨于一個定值。但是對應點對最大距離的減小又會直接增加時間復雜度，當擬合系數(shù)為0.000 02時就可達到良好的匹配效果，因此綜合計算復雜度與匹配精度，與之對應的該參數(shù)值為0.01，得到粗匹配結(jié)果，然后對其結(jié)果進行ICP精確匹配，最終匹配精度為0.000 025，與未進行點云粗匹配的匹配精度0.000 063相比，提高了百分之60.3%，此時的轉(zhuǎn)移矩陣和平移向量分別為:

為了進一步驗證本文算法的有效性，對ICP算法和本文改進的算法精度進行比較，如表2所示，相比于經(jīng)典ICP算法，本文克服了其初始點云不收斂從而引起較大匹配誤差的缺點，大大提高了匹配精度。與現(xiàn)有的其它兩種匹配算法相比本文算法得到的匹配誤差最小。

表2 同類方法配準精度比較

綜上實驗結(jié)果，在大量的實驗基礎上，利用FPFH特征描述符對原始散亂點云進行粗匹配的基礎上，再進行ICP精確匹配，圖像匹配精度提高，很好的實現(xiàn)了點云配準。

最后對配準后的點云進行三角化得到最終的重建模型，如圖12所示。

圖12 三維模型

5 小結(jié)

針對點云處理流程中，因ICP算法需要收斂的初始位置，文中使用基于FPFH描述子的點云粗匹配，提高匹配精度，取得了良好的拼接效果，從而實現(xiàn)了三維重建。實驗結(jié)果證明本文的方法可以有效地實現(xiàn)三維重建，具有一定的實際應用價值。

[1]ArafaMajdi,MohamedChafikBakkayandEzzeddineZagrouba.3DModelingofIndoorEnvironmentsUsingkinectsensor[A].2013IEEESecondInternationalConferenceonImageInformationProcessing(ICIIP)[C].Shimla,IEEE, 2013, 67-72.

[2] 艾 達,喬明明.三維激光掃描技術在犯罪現(xiàn)場重建中的應用[D].西安：西安郵電大學學報,2013.

[3]BeslPJ,McKayHD.AMethodforRegistrationof3DShape[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 1992. 14(2): 239-256.

[4] 王 君.基于kinect的三維場景重建研究[D].長沙：中南大學，2013.

[5]RichardANewcombe,ShahramIzadi,OtmarHilliges,DavidMolyneaux,DavidKim.KinectFusion:Real-TimeDenseSurfaceMappingandTracking[A].2011 10thIEEEInternationalSymposiumonMixedandAugmentedReality(ISMAR)[C].Basel.2011,127-136.

[6]NguyenCV,IzadiS,LovellD.ModelingKinectsensornoiseforImproved3DReconstructionandTracking[A].Proceedingsofthe2012SecondInternationalConferenceon3DImaging,Modeling,Processing,Visualization&Transmission,2012[C].IEEEComputerSociety.

[7]WanY,WangJ,HuJW.AStudyin3D-ReconstructionUsing

KinectSensor3D-Reconstruction[A].2012 8thInternationalConferenceonWirelessCommunications,NetworkingandMobileComputing(WiCOM)[C].Shanghai,China.2012,1-7.

[8] 葉日藏.基于Kinect深度傳感器的三維重建技術應用研究[D].廣東:華南理工大學，2013.

[9] 何文峰. 大型場景三維重建中的深度圖像配準[D].北京：北京大學,2004.

[10]RaduBogdanRusu,NicoBlodow,MichaelBeetz.FastPointFeatureHistograms(FPFH)for3DRegistration[A].2009IEEEInternationalConferenceonRoboticsandAutomation[C].Japan.2009,3212-3217.

[11]高珊珊.基于三維激光掃描儀的點云配準[D].南京：南京理工大學，2008.

[12] 張旭東,吳國松等.基于TOF三維相機相鄰散亂點云配準技術研究[J].機械工程學報，2013,49(12):8-22.

[13]陳聰梅.基于Kinect的三維點云數(shù)據(jù)處理[D].蘇州：蘇州大學,2013.

[14]SzymonRusinkiewiczMarcLevoy.EfficientVariantsoftheICPAlgorithm[A].Proceedings.ThirdInternationalConferenceon3-DDigitalImagingandModeling[C]. 2001:145-152.

[15]RaduBogdanRusuandSteveCousinsWillowGarage. 3Dishere:PointCloudLibrary(PCL)[A].InternationalConferenceonRoboticsandAutomation(ICRA)[C]. 2011IEEE.Shanghai:2011,1-4.

[16]胡修祥,張 良.結(jié)合NARF特征的改進型3D-NDT多視野點云配準[J].信號處理,2015,31(12):1674-1679.

Research and Realization of 3D Restruction Based on FPFH

Ai Da1，Wang Miao1，Ni Guobin2

(1.Xi’an University of Posts and Telecommunications, Key Laboratory of electronic information application technology of Site-survey of Ministry of public security, Xi’an 710061,China)2.School of Electronic Engineering,Xi’an University of Posts and Telecommunications, Xi’an 710061, China)

The article describes a different perspective on the basis of three-dimensional point cloud pairwise data registration,for accurate matching algorithms ICP need to make an initial point cloud convergence, otherwise unable to obtain accurate matching results, this artice proposes a feature based on FPFH Descriptors coarse matching feature method.Adjust the initial position of two point clouds for ICP algorithm provides a good initial position to further improve the matching precision point cloud. And on this basis to get through a lot of experiments as a function of the largest point distance and the best fitness score between correspondence pairs to obtain the optimal value match, it is proved that coarse matching can make the best fitness score up to 60.3%.

registration;FPFH descriptors;coarse matching

2016-01-12；

2016-03-07。

公安部重點實驗室項目(2014GABJC02)。

艾 達(1975-)，男，博士，高工，碩導，主要從事數(shù)字圖像處理方向的研究。

1671-4598(2016)07-0232-05

10.16526/j.cnki.11-4762/tp.2016.07.063

TP391 文獻標識碼：A