基于FPFH特征的點(diǎn)云配準(zhǔn)技術(shù)

陳學(xué)偉++萬(wàn)韜阮++王祖全

摘要：點(diǎn)云配準(zhǔn)是三維物體或場(chǎng)景模型重建的關(guān)鍵技術(shù)。針對(duì)傳統(tǒng)的ICP算法的收斂速度較慢，且在兩點(diǎn)云集初始位置較大時(shí)易陷入局部最優(yōu)解的問(wèn)題，該文提出了一種改進(jìn)的點(diǎn)云配準(zhǔn)算法。該算法首先計(jì)算點(diǎn)云的FPFH特征描述子，然后對(duì)點(diǎn)云的特征進(jìn)行匹配，實(shí)現(xiàn)兩片點(diǎn)云的初始變換，使兩點(diǎn)云集有相對(duì)較好的初始位姿。在經(jīng)典ICP基礎(chǔ)上使用k-d tree（k-Dimension tree）近鄰搜索加速對(duì)應(yīng)點(diǎn)對(duì)的查找，并利用方向向量閾值去除錯(cuò)誤點(diǎn)對(duì)，實(shí)驗(yàn)證明該算法具有相對(duì)較好的配準(zhǔn)精度和收斂速度，提高了配準(zhǔn)的效率。

關(guān)鍵詞： 點(diǎn)云配準(zhǔn)；ICP算法；FPFH；方向向量閾值

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）04-0207-03

The Point Cloud of Registration Technology Based on FPFH Feature

CHEN Xue-wei，WAN Tao-ruan，WANG Zu-quan

（Xi'an University of Electronic and Information Engineering，Xi'an 710048， China）

Abstract：The registration of Point cloud is the key technology in the of 3 d object or scene model reconstruction. As for the low convergence of classical ICP algorithm and the convergence to the global optimum not be guaranteed，a kind of improved ICP algorithm of point cloud registration is put forward. This algorithm firstly calculates the FPFH point cloud character description， and then to match the characteristics of point cloud， the realization of two pieces of the initial point cloud transform， make two gathered have relatively good initial position.Then it use the k-d tree （k-Dimension tree）based on classic ICP to accelerate the search speed of the corresponding point ， and use the direction vector to remove the error corresponding point to improve the efficiency of registration .

Key words：point cloud registration；ICP algorithm；FPFH；Direction vector threshold

三維重建是計(jì)算機(jī)視覺(jué)領(lǐng)域研究的一個(gè)重要研究方向，在虛擬現(xiàn)實(shí)、文物保護(hù)、逆向工程、人機(jī)交互等領(lǐng)域都有廣泛的應(yīng)用。在數(shù)據(jù)采集的過(guò)程中，由于受到環(huán)境和設(shè)備本身的限制，需要從多個(gè)角度去采集某一模型表面的數(shù)據(jù)。為了得到完整的三維數(shù)據(jù)模型，我們可以利用光學(xué)三維測(cè)量法[1-2]從不同視角采集點(diǎn)云數(shù)據(jù)并對(duì)采集的數(shù)據(jù)進(jìn)行拼接，配準(zhǔn)的精度會(huì)直接影響到后期模型重建的精度。

由Besl和McKay[3-4]提出的經(jīng)典的ICP算法是目前應(yīng)用最廣泛的點(diǎn)云配準(zhǔn)算法，它通過(guò)不斷尋找目標(biāo)點(diǎn)云和源點(diǎn)云之間對(duì)應(yīng)點(diǎn)集和計(jì)算對(duì)應(yīng)點(diǎn)集之間的最優(yōu)剛體變換矩陣，尋找兩點(diǎn)云之間的最優(yōu)匹配。但傳統(tǒng)的ICP算法[5]收斂速度較慢，且在點(diǎn)云數(shù)據(jù)集初始位置相差較大時(shí)，易陷入局部最優(yōu)解。為了改善這一問(wèn)題，本文提出一種改進(jìn)的點(diǎn)云配準(zhǔn)算法，該算法在初始配準(zhǔn)過(guò)程中引入了點(diǎn)云的特征描述子FPFH[6-7]，通過(guò)匹配點(diǎn)云特征對(duì)兩點(diǎn)云集進(jìn)行初始配準(zhǔn)，將所得到的變換矩陣[8]作為精配準(zhǔn)階段的初始估計(jì)，巧妙地解決了傳統(tǒng)ICP算法在點(diǎn)云之間的初始位置偏差較大時(shí)易陷入局部最優(yōu)解的問(wèn)題。在精配準(zhǔn)中，在傳統(tǒng)ICP算法的基礎(chǔ)上使用 k-d tree近鄰搜索法[9]提高對(duì)應(yīng)點(diǎn)對(duì)的查找速度，并利用方向向量閾值去除點(diǎn)云中錯(cuò)誤的對(duì)應(yīng)點(diǎn)對(duì)，提高了算法的魯棒性。

1算法介紹

本文提出了一種改進(jìn)的點(diǎn)云配準(zhǔn)算法，有效地改善了ICP算法收斂速度慢、魯棒性差等問(wèn)題。該算法首先計(jì)算點(diǎn)云的FPFH特征，然后通過(guò)匹配點(diǎn)云之間的特征實(shí)現(xiàn)兩點(diǎn)云的剛體變換，從而完成初始配準(zhǔn)，使兩片點(diǎn)云集獲得一個(gè)相對(duì)較好的初始位置[10]，然后利用k-d tree近鄰搜索加速對(duì)應(yīng)點(diǎn)對(duì)的查找，并使用點(diǎn)云方向向量閾值去除錯(cuò)誤的點(diǎn)對(duì)，估計(jì)對(duì)應(yīng)點(diǎn)對(duì)的剛體變換關(guān)系實(shí)現(xiàn)點(diǎn)云的精確配準(zhǔn)。流程圖如下：

2點(diǎn)云的初始配準(zhǔn)

當(dāng)點(diǎn)云的初始位置較大時(shí)，點(diǎn)云的精配準(zhǔn)易陷入錯(cuò)誤的方向，因此需要進(jìn)行點(diǎn)云的初始配準(zhǔn)，為精配準(zhǔn)提供一個(gè)良好的初值。本文在初始配準(zhǔn)是基于快速點(diǎn)特征直方圖FPFH。其算法原理如下：

1）從待配準(zhǔn)點(diǎn)云P中選取n個(gè)采樣點(diǎn)，采樣點(diǎn)之間的距離應(yīng)滿足大于預(yù)先設(shè)定最小距離閾值d，這樣可以保證所采樣的點(diǎn)具有不同的FPFH特征，

2）在目標(biāo)點(diǎn)云Q中查找與點(diǎn)云P中采樣點(diǎn)具有相似 FPFH特征的一個(gè)或多個(gè)點(diǎn)，從這些相似點(diǎn)中隨機(jī)選取一個(gè)點(diǎn)作為點(diǎn)云P在目標(biāo)點(diǎn)云Q中的一一對(duì)應(yīng)點(diǎn)。

3）計(jì)算對(duì)應(yīng)點(diǎn)之間剛體變換矩陣，然后通過(guò)求解對(duì)應(yīng)點(diǎn)變換后的“距離誤差和”函數(shù)，來(lái)判斷當(dāng)前配準(zhǔn)變換的性能。此處的距離誤差和函數(shù)多使用Huber罰函數(shù)表示，記為[i=1nH（li）]，其中：

上式中，[ml]為一預(yù)先給定值。[li]為第[i]組對(duì)應(yīng)點(diǎn)變換后的距離差。上述配準(zhǔn)的最終目的是在所有變換中找到一組最優(yōu)的變換，使得誤差函數(shù)的值最小，此時(shí)的變換即為最終的配準(zhǔn)變換矩陣[11]，進(jìn)一步可得到配準(zhǔn)結(jié)果。

2.1 快速點(diǎn)特征直方圖（FPFH）

FPFH 是利用已估計(jì)出的點(diǎn)云法線特征，計(jì)算出改點(diǎn)與其k個(gè)領(lǐng)域點(diǎn)的空間差異，它實(shí)際上是改進(jìn)的PFH（point features histograms）快速簡(jiǎn)化模型。點(diǎn)特征直方圖（PFH）描述樣本的幾何特征的方式是估算點(diǎn)云法向量之間的相互作用。PFH的計(jì)算方法如圖2。

[pq]為待計(jì)算PFH特征的點(diǎn)，確定一參考半徑內(nèi)（圖中虛線圓中）的k個(gè)鄰域點(diǎn)，計(jì)算k鄰域內(nèi)的所有點(diǎn)兩兩之間的歐式距離、法線的角度偏差。k個(gè)鄰域點(diǎn)的計(jì)算復(fù)雜度為[O（k2）]。本文提出了降低計(jì)算的復(fù)雜度FPFH快速算法，該特征描述子的計(jì)算復(fù)雜度為[O（nk）]，同時(shí)保證了PFH的大部分特征。

FPFH特征描述子的計(jì)算過(guò)程如下：

1）對(duì)于每個(gè)查詢點(diǎn)[pq]，計(jì)算出該待求點(diǎn)與其所有鄰域點(diǎn)之間的相對(duì)關(guān)系，記作[SPFH（pq）]；

2）重新確定每個(gè)點(diǎn)k鄰域，并通過(guò)SPFH特征， 來(lái)估計(jì)FPFH特征，如下式所示：

[FPFH（pq）=SPFH（pq）+1ki=1kwi?SPFH（pi）] （2）

其中，[wi]為第i個(gè)鄰域點(diǎn) SPFH 特征的加權(quán)值。[1wi]代表[pq]與其第i個(gè)鄰域點(diǎn)的距離值，用于表示點(diǎn)對(duì)（[pq]，[pi]）的關(guān)系.

FPFH 的整個(gè)計(jì)算過(guò)程可用圖3表示：

3點(diǎn)云的精確配準(zhǔn)

經(jīng)過(guò)粗配準(zhǔn)后兩片點(diǎn)云集具有較好的初始位姿，但兩點(diǎn)云之間仍存在偏差，配準(zhǔn)的精度也達(dá)不到實(shí)際的需要，因此還需要進(jìn)行精配準(zhǔn)。在精配準(zhǔn)過(guò)程中，本文對(duì)傳統(tǒng)ICP算法進(jìn)行了優(yōu)化，使用k-d tree近鄰搜索法加速對(duì)應(yīng)點(diǎn)對(duì)的查詢，同時(shí)利用方向向量閾值去除錯(cuò)誤點(diǎn)對(duì)，提高每次對(duì)應(yīng)點(diǎn)對(duì)集之間變換矩陣的估計(jì)質(zhì)量，提高配準(zhǔn)的效率。

方向向量閾值：

在對(duì)應(yīng)點(diǎn)對(duì)的查詢過(guò)程中不可避免地會(huì)引入噪聲點(diǎn)對(duì)，而噪聲點(diǎn)對(duì)的引入會(huì)影響最后的配準(zhǔn)結(jié)果。為了縮小這種影響，本文采用方向向量閾值法剔除引入的噪聲點(diǎn)對(duì)。計(jì)算點(diǎn)云表面的每個(gè)點(diǎn)的法向量以及對(duì)應(yīng)點(diǎn)對(duì)之間的法向量夾角。如果對(duì)應(yīng)點(diǎn)對(duì)之間的法向量夾角小于預(yù)先設(shè)定的閾值 t，就認(rèn)為是正確的點(diǎn)對(duì)。反之，則認(rèn)為是錯(cuò)誤點(diǎn)對(duì)，將之從對(duì)應(yīng)點(diǎn)集中剔除，避免迭代朝著一個(gè)錯(cuò)誤的方向進(jìn)行，提高配準(zhǔn)效率。

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

為了驗(yàn)證本文算法的有效性，本文采用了斯坦福大學(xué)提供的開(kāi)放數(shù)據(jù)源bunny和數(shù)據(jù)規(guī)模較大，曲面復(fù)雜度較高的Happy Buddha作為試驗(yàn)對(duì)比數(shù)據(jù)，bunny點(diǎn)云有40000左右個(gè)點(diǎn)。Happy Buddha數(shù)據(jù)點(diǎn)要稍大于bunny，約為75000個(gè)。

實(shí)驗(yàn)平臺(tái)為：win8系統(tǒng)，CPU主頻為2.6Ghz，內(nèi)存8G，Vistual C++編程，進(jìn)行了兩組數(shù)據(jù)的配準(zhǔn)試驗(yàn)，實(shí)驗(yàn)結(jié)果如下。

（a）配準(zhǔn)前的Happy Buddha （b） 初始配準(zhǔn)后的Happy Buddha

（c） 本文算法配準(zhǔn)后的Happy Buddha

由上圖可知，圖（b）可知此時(shí)兩片點(diǎn)云數(shù)據(jù)已大致重合，但是依然存在一定的偏差，此時(shí)兩片點(diǎn)云配準(zhǔn)誤差分別為2.286e-5、3.307e-5，而工程上要求的標(biāo)準(zhǔn)是不大于e-5，因此還需要進(jìn)行精確配準(zhǔn)。

圖（c）本文算法精配準(zhǔn)后的點(diǎn)云數(shù)據(jù)，從圖可見(jiàn)，兩幀點(diǎn)云中兔子的各個(gè)部位均得到了較好的配準(zhǔn)。由表1可知兩組數(shù)據(jù)的精度分別為4.712e-6、6.448e-6，相比初始配準(zhǔn)有了較大的改善。

[點(diǎn)云名稱＼& 傳統(tǒng)ICP算法＼& 本文配準(zhǔn)算法＼& 點(diǎn)的個(gè)數(shù)＼& 配準(zhǔn)時(shí)間（s）＼&配準(zhǔn)誤差（m）＼&配準(zhǔn)時(shí)間（s）＼&配準(zhǔn)誤差（m）＼&Bunny＼&123＼& 4.045e-5＼& 66＼& 4.712e-6＼&40000個(gè)左右＼&Happy Buddha＼&147＼&5.746e-5＼& 84＼&6.448e-6＼&75000個(gè)左右＼&]

由表2分析可知，本文算法比傳統(tǒng)ICP算法有相對(duì)較好的配準(zhǔn)精度和收斂速度。當(dāng)數(shù)據(jù)量較大時(shí)，點(diǎn)云配準(zhǔn)誤差會(huì)有所增大，收斂速度有所變緩，但依然能夠滿足實(shí)際的需要

5結(jié)束語(yǔ)

本文提出一種基于特征點(diǎn)描述子FPFH點(diǎn)云配準(zhǔn)算法，該算法首先利用SAC-IA算法實(shí)現(xiàn)點(diǎn)云的初始剛體變換，使兩片點(diǎn)云具有一個(gè)較好的初始位置，避免算法陷入局部最優(yōu)解的問(wèn)題。然后在經(jīng)典ICP基礎(chǔ)上提出k-d tree近鄰搜索方法加速對(duì)應(yīng)點(diǎn)對(duì)的查找，并利用方向向量閾值去除錯(cuò)誤點(diǎn)對(duì)，提高算法的效率。實(shí)驗(yàn)表明，該算法的配準(zhǔn)精度和收斂速度在一定程度上都有所提高，具有一定的實(shí)際應(yīng)用價(jià)值。

參考文獻(xiàn) ：

[1] 呂江昭，達(dá)飛鵬，鄭東亮. 基于 Sierra Lite 抖動(dòng)算法的散焦投影光柵測(cè)量[J]. 光學(xué)學(xué)報(bào)，2014，34（3）：0312004.

[2]安東，蓋紹彥，達(dá)飛鵬. 一種新的基于條紋投影的三維輪廓測(cè)量系統(tǒng)模型[J].

光學(xué)學(xué)報(bào)，2014，34（5）：0512004.

[3] Best PJ，McKay HD.A method for registration of 3-D shapes.IEEE Transactions on Pattern Analysis and Machine Intelligence 1992： 14（2）： 239-56.

[4] Besl P J，Mckay N D.A method for registration of 3-dshapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14（2）： 239-256.

[5] 鐘瑩，張蒙.基于改進(jìn)ICP算法的點(diǎn)云自動(dòng)配準(zhǔn)技術(shù)[J].控制工程，2014，21（1）： 37-40.

[6] 陸軍，彭仲濤，董東來(lái)，等.點(diǎn)云FPFH 特征提取優(yōu)化配準(zhǔn)算法[J].新型工業(yè)化，2014，4（7）：75-81.

[7]Radu Bogdan Rusu ，Nico Blodow，Michal Beetz.Fast Point Feature Histograms （FPFH） for 3D Registration [A].2009 IEEE International Conference On Robotics and Automation [C].Japan. 2009，3212-3217.

[8] 宋林霞. 三維點(diǎn)云配準(zhǔn)方法的研究[D].濟(jì)南大學(xué)，2013.

[9] 戴靜蘭，陳志揚(yáng)，葉修梓.ICP 算法在點(diǎn)云配準(zhǔn)中的應(yīng)用[J].中國(guó)圖象圖形學(xué)報(bào)，2007，12（3）：517-521.

[10] 朱延娟，周來(lái)水. 散亂點(diǎn)云數(shù)據(jù)配準(zhǔn)算法. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（4）： 475-481.

[11] 涂志強(qiáng)，張珂，楊成龍，等.三維模型重建中點(diǎn)云ICP拼接算法的改進(jìn) [J].焊接學(xué)報(bào)，2013，34（1）：97-100.