趙書芳

（西安工程大學(xué)電子信息學(xué)院，西安710600）

1 引 言

點云配準(zhǔn)是指經(jīng)由一定的算法或者統(tǒng)計學(xué)規(guī)律，通過計算機求解兩塊點云之間的錯位，并由此計算出最佳轉(zhuǎn)換矩陣，實現(xiàn)將兩片點集云自動配準(zhǔn)的過程。其技術(shù)是通過在源點云模型和目標(biāo)點云模型之間構(gòu)造一個三維空間變換，使源點云模型在此變換作用下能夠最大限度地和目標(biāo)點云模型重合。點云配準(zhǔn)問題實質(zhì)上是求解坐標(biāo)變換矩陣和平移向量參數(shù)，使得兩片三維點云的數(shù)據(jù)經(jīng)坐標(biāo)變換后的距離最小，直至實現(xiàn)兩點云的配準(zhǔn)。

目前最為經(jīng)典和被普遍使用的點云配準(zhǔn)算法是由Besl 和McKay 等人提出的迭代最近點（Iterative Closest Point， ICP）算法[1]。該算法雖然配準(zhǔn)精度高，但存在計算效率低和初始位置要求高等缺點，對于數(shù)據(jù)量大的點云配準(zhǔn)速度較慢，容易陷入局部極值的問題。因此許多學(xué)者對ICP 的改進(jìn)算法進(jìn)行了研究。趙夫群等人提出了基于文物點云模型的優(yōu)化配準(zhǔn)算法[2]，針對帶有噪聲的文物點云模型，采用一種由粗到細(xì)的方法來實現(xiàn)其斷裂面的精確配準(zhǔn)。楊軍提出了一種基于自適應(yīng)最優(yōu)閾值的ICP 算法[3]，實現(xiàn)了整體與部分的3D 模型間的配準(zhǔn)。鐘瑩以經(jīng)典ICP算法為基礎(chǔ)，根據(jù)主成分分析（Principal Component Analysis， PCA）算法[4]進(jìn)行粗略配準(zhǔn)，首先實現(xiàn)了兩片大致重合的點云數(shù)據(jù)的快速獲得，并在隨后通過閾值改進(jìn)的ICP 算法進(jìn)行點云數(shù)據(jù)的精確配準(zhǔn)。詹曙提出使用稀疏迭代最近點（SICP）來進(jìn)行深度圖的配準(zhǔn)[5]，通過使用稀疏誘導(dǎo)準(zhǔn)則去重新書寫配準(zhǔn)優(yōu)化公式，從而提高配準(zhǔn)的精度。張開興提出了一種以三維模型為基礎(chǔ)的數(shù)據(jù)點配準(zhǔn)方法[6]，利用掃描數(shù)據(jù)生成三角網(wǎng)格模型， 并應(yīng)用單純形優(yōu)化算法生成三維模型的最小包圍盒， 然后通過坐標(biāo)變換實現(xiàn)CAD 模型與三角網(wǎng)格模型上數(shù)據(jù)點的粗配準(zhǔn)， 最后通過ICP 算法實現(xiàn)精配準(zhǔn)。張志林使用Kinect v2獲取包含物體所在場景的點云， 利用SAC-IA 算法對相鄰兩片點云進(jìn)行粗配準(zhǔn)，并將兩兩配準(zhǔn)的ICP算法擴展到多片點云，算法策略配準(zhǔn)精度高且適用性好[7]。

以上諸算法在點云配準(zhǔn)的速度和精度等方面都有不同程度的提高，但應(yīng)用在三維人體模型和服裝模型的配準(zhǔn)效果不佳，配準(zhǔn)精度不高。為解決這一問題，在此提出一種基于ICP 算法的改進(jìn)點云配準(zhǔn)算法。此算法在初始配準(zhǔn)時使用SAC-IA 算法，對兩片點云集進(jìn)行初始配準(zhǔn)，將初始配準(zhǔn)后得到的位姿作為ICP 配準(zhǔn)算法的初始位姿，來避免ICP 算法在點云配準(zhǔn)時因為初始位姿偏差過大時導(dǎo)致配準(zhǔn)結(jié)果容易陷入局部極值的情況。

2 配準(zhǔn)算法概述

一般情況下點云配準(zhǔn)算法的實現(xiàn)可分為初始配準(zhǔn)和精確配準(zhǔn)。點云配準(zhǔn)就是一片點云數(shù)據(jù)與另一片點云數(shù)據(jù)根據(jù)坐標(biāo)變換矩陣進(jìn)行整體分析并配準(zhǔn)的過程[8]，其實質(zhì)是求解坐標(biāo)旋轉(zhuǎn)矩陣和平移向量，使得在不同坐標(biāo)系下測得的兩片點云的三維數(shù)據(jù)經(jīng)過坐標(biāo)變換后的距離最小。

該算法首先對點云數(shù)據(jù)進(jìn)行VoxelGrid 濾波處理，然后進(jìn)行快速點特征直方圖（Fast Point Feature Histogram， FPFH）特征提取，之后，再利用采樣一致性初始配準(zhǔn)算法（SAC-IA， Sample Consensus Initial Aligment）得到兩片點云之間的對應(yīng)關(guān)系，從而完成初始配準(zhǔn)，使兩片點云集獲得一個相對較好的初始位姿[9]。最后，運用ICP 算法將點云的初始配準(zhǔn)結(jié)果進(jìn)行第二次精確配準(zhǔn)，從而完成兩片點云的精確配準(zhǔn)，達(dá)到優(yōu)化配準(zhǔn)結(jié)果的目的。點云配準(zhǔn)流程圖如圖1 所示。

圖1 點云配準(zhǔn)流程圖

3 VoxelGrid 濾波

在點云處理時一般將濾波處理作為預(yù)處理的第一步，濾波處理的效果決定著后續(xù)的點云處理步驟的好壞，影響很大。為了更好完成配準(zhǔn)、特征提取、曲面重建、可視化等后續(xù)步驟，必須在濾波處理時將離群點、空洞、噪聲點等按照后續(xù)點云處理的需求進(jìn)行定制的濾波預(yù)處理。

VoxelGrid（體素網(wǎng)格）濾波法具有很好的濾波效果。體素網(wǎng)格的概念類似于像素，使用AABB 包圍盒將點云數(shù)據(jù)體素化。一般體素越密集的地方信息越多。體素網(wǎng)格可以去除噪音點和離群點。另一方面如果使用高分辨率相機等設(shè)備采集點云數(shù)據(jù)，那么得到點云數(shù)據(jù)通常會較為密集。過多的點云數(shù)量會對后續(xù)點云配準(zhǔn)等工作帶來困難。使用體素濾波器不僅可以達(dá)到向下采樣的目的，同時也保持了點云數(shù)據(jù)本身的幾何結(jié)構(gòu)。

在此使用VoxelGrid 濾波[10]方法實現(xiàn)下采樣，在減少了點云數(shù)據(jù)的同時也保持了點云的原始形狀特征，適用于點云配準(zhǔn)、曲面重建等三維點云算法中，以提高點云算法的運算速度。PCL 中的濾波函數(shù)VoxelGrid 類經(jīng)由輸入的點云數(shù)據(jù)創(chuàng)建了一種三維體素柵格（一般將體素柵格當(dāng)做空間的微小三維立方體的集合），然后在每一個體素格內(nèi)，體素中的其他點用其重心點來表示，因此經(jīng)過體素格濾波后的點云數(shù)據(jù)，其所有點都可以用一個重心點來代替表示。通過上述下采樣的方法達(dá)到點云濾波的效果，也可同時減少點云數(shù)據(jù)的處理量。將其作為點云配準(zhǔn)和曲面重建等實驗的預(yù)處理，能夠在很大程度上提高點云處理的速度。

4 點特征直方圖描述子

采樣一致性初始配準(zhǔn)（SAC-IA，Sample Consensus Initial Alignment）算法依賴特征直方圖[11]，因此一般要先將點云的快速特征點直方圖描述子（FPFH， Fast Point Feature Histogram）計算出來。FPFH 是根據(jù)已估計出的點云法線的特征值，計算出該點和它k 個鄰域點之間的空間差異，其本質(zhì)上是點特征直方圖（PFH）的快速簡化模型[12]。FPFH 很大程度上減少了計算復(fù)雜度，提高了計算效率，并且保留了PFH 的大部分特征和功能。

新算法利用了提高計算效率的FPFH 快速算法，同時保留了PFH 的主要特性。FPFH 特征描述子的求解方法如下：

1) 針對某個查詢點Pr，求取它和鄰域點之間的矩陣關(guān)系，將此計算關(guān)系稱為簡化的點特征直方圖（SPFH，Simple Point Feature Histograms），記作S(Pr)；

2) 再次設(shè)定每個點k 鄰域，然后通過鄰域點計算出的SPFH 的值來求解點Pr的FPFH 特征值，記作H(Pr)為：

上式wl為第l 個鄰域點SPFH 特征的權(quán)重，表示查詢點Pr和它的鄰近點Pm之間的距離，用于評定一組點對(Pr，Pm)的關(guān)系。FPFH 計算原理如圖2 所示。

圖2 FPFH 計算原理圖

5 點云配準(zhǔn)方法

5.1 初始配準(zhǔn)

為了避免使點云配準(zhǔn)陷入局部最優(yōu)解從而導(dǎo)致配準(zhǔn)失敗，在精配準(zhǔn)之前進(jìn)行了點云的初始配準(zhǔn)。在初始配準(zhǔn)時采用的是SAC-IA 算法，其算法步驟如下所述：

1) 從待配準(zhǔn)點云M 中選取k 個采樣點，為了使每個采樣點的FPFH 特征都不一樣，每兩個采樣點之間的距離應(yīng)該大于設(shè)置的最小距離閾值dmin。

2) 尋找目標(biāo)點云N 中和待配準(zhǔn)點云M 中的采樣點具有相似FPFH 特征的所有的點，在這些相似點中任意選取一些點作為點云M 在目標(biāo)點云N 中的相互對應(yīng)點。

3) 求解對應(yīng)點之間的剛體變換矩陣，然后再利用計算對應(yīng)點云的度量誤差來評價變換矩陣的質(zhì)量。此處的距離誤差多使用Huber 函數(shù)表示：

式中ur為預(yù)設(shè)值，ri為第i 組對應(yīng)點變換之后的距離差。重復(fù)以上三個步驟直至取得最佳度量誤差結(jié)果，即得到誤差函數(shù)的最小值，此時剛體變換矩陣就是最優(yōu)的，也是最終的點云配準(zhǔn)變換矩陣[11]，通過此矩陣即可計算出點云配準(zhǔn)結(jié)果。

5.2 IPC 算法

通過SAC-IA 算法得到的剛體變換矩陣使得兩個點云數(shù)據(jù)大體上重合，得到一個較好的精確配準(zhǔn)的初始位姿，還需在此基礎(chǔ)上再做一次精確配準(zhǔn)。ICP 算法作為經(jīng)典的精確配準(zhǔn)算法，實際上是基于最小二乘法的最優(yōu)配準(zhǔn)方法。該算法是通過重復(fù)選擇滿足對應(yīng)關(guān)系的點對，計算出最優(yōu)剛體變換，直到達(dá)到配準(zhǔn)的收斂精度要求。ICP 算法的主要思想就是找到旋轉(zhuǎn)矩陣和平移參數(shù)，將兩個不同坐標(biāo)系下的點云，以其中一個點云坐標(biāo)系為全局坐標(biāo)系，另一個點云經(jīng)過旋轉(zhuǎn)和平移后兩組點云對應(yīng)部分完全重疊。在每次進(jìn)行ICP 算法時，一般先通過給定的規(guī)則找出對應(yīng)點集C 與D，此處有：C∈?A， D∈?B，對應(yīng)點對的個數(shù)設(shè)置為n。最后根據(jù)最小二乘法迭代計算出坐標(biāo)變換矩陣，包括旋轉(zhuǎn)矩陣Z 和平移向量T，使誤差函數(shù)式達(dá)到最小，其式如下：

此式取得最小值時即達(dá)到滿意的誤差要求。

ICP 算法分為4 個主要步驟：

①針對目標(biāo)點云中的每個點，求解源點云中與其匹配的最近點;

②計算出使上述對應(yīng)點對令函數(shù)式(3)值最小的剛體變換，然后求取旋轉(zhuǎn)矩陣和平移向量；

③使用獲得的旋轉(zhuǎn)矩陣和平移向量來配準(zhǔn)原始點云和目標(biāo)點云；

④重復(fù)上述三個步驟，直到滿足終止迭代的條件（迭代次數(shù)或誤差小于閾值）。此處的誤差最小，可以是相鄰兩次均方根差的絕對值小于某一限差。

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

實驗中的人體模型和服裝模型來自Poser 6.0。Poser 是MetaCreation 公司開發(fā)的一款優(yōu)秀的人體造型和動畫制作軟件，為用戶提供了男性模型、女性模型等，且存儲了很多的身體姿勢、動作以及逼真的面部表情的三維人體模型和服裝模型[13]。此外Poser還有較強的交互能力，具備了3ds、obj 等文件格式的接口，能和輸出為上述文件格式的軟件程序進(jìn)行模型信息交互。在實驗中，把Poser 6.0 中的三維模型數(shù)據(jù)導(dǎo)出為obj 格式的數(shù)據(jù)文件，然后利用程序?qū)bj 格式的人體模型轉(zhuǎn)化為pcd 的點云格式，最后再進(jìn)行三維人體模型與服裝的點云配準(zhǔn)。

實驗使用C++編程和PCL 開源數(shù)據(jù)庫，一共進(jìn)行了兩組三維人體模型和服裝模型數(shù)據(jù)的配準(zhǔn)。在配準(zhǔn)之前，在Maya 里對人體模型和服裝模型的尺寸進(jìn)行了調(diào)整，將服裝變形到適合人體模型的尺寸大小。實驗結(jié)果如圖3 和圖4 所示。實驗使用的改進(jìn)配準(zhǔn)算法與傳統(tǒng)ICP 算法配準(zhǔn)所消耗的時間對比如表1 所示。

圖3 男裝點云配準(zhǔn)結(jié)果比較

圖4 女裝點云配準(zhǔn)結(jié)果比較

表1 改進(jìn)算法與傳統(tǒng)ICP 算法處理速度對比

圖3(b)和圖4(b)為ICP 算法配準(zhǔn)后的數(shù)據(jù)。由圖中可以看出此時兩片點云數(shù)據(jù)沒有完全重合。圖3(c)和圖4(c)為實驗算法配準(zhǔn)后的效果圖，兩片點云數(shù)據(jù)中的各個部位都得到了較好的融合，實現(xiàn)了人體模型和服裝模型的配準(zhǔn)。

7 結(jié) 束 語

針對ICP 算法收斂速度慢，容易陷入局部極值等問題，基于SAC-IA 對ICP 點云配準(zhǔn)算法進(jìn)行了改進(jìn)。經(jīng)過實驗驗證，新改進(jìn)的算法適用于人體模型和服裝模型等剛體的配準(zhǔn)，當(dāng)兩點云重疊區(qū)域較少時依然有較高的配準(zhǔn)精度。與傳統(tǒng)ICP 算法相比，改進(jìn)算法點云配準(zhǔn)的精度和收斂速度都有了明顯的改善，具有很好的實用價值。