基于局部和全局特征的點云對應關系構建

唐溯菡，謝曉堯，劉 嵩

(貴州師范大學 貴州省信息與計算科學重點實驗室，貴州 貴陽 550001)

0 引言

近年來，隨著物體三維信息獲取設備的發展，點云數據的獲取成本降低。對于點云數據的處理，例如剛性或非剛性配準、語義分割、特征提取、點云補全等研究開始受到廣泛的關注。構建點云對應關系，即原點云和目標點云之間的映射關系，是點云配準中非常關鍵的步驟，對應關系的精確度會影響后續的配準算法的結果以及算法效率。目前的對應關系的構建可以分為兩種：構建點-點的對應關系以及構建區域-區域的對應關系。

1 相關工作

區域-區域的對應關系是指將原點云和目標點云按照一定的方式分割，得到各個不同的部位后，在各個部位之間構建的對應關系，如圖1所示。

圖1 區域對應 Fig.1 Area Correspondence

點-點之間的對應關系即原點云和目標點云的點的映射關系。一些算法使用最近點搜索算法獲取初始對應關系，然后對原點云使用非剛性配準算法，在其逐漸變形逼近目標點云的過程中動態更新對應關系。Brian等[1]提出一種基于最近點迭代(Iterative closest point，ICP)的非剛性配準算法，使用最近點搜索算法獲取初始對應關系后，在原點云非剛性配準目標點云的過程中逐步更新對應關系。但這類方法只適用于形變程度不大、原點云和目標點云的實際上嚴格對齊的數據，如圖2所示，且對應關系必須在非剛性配準的過程中重新計算，計算效率低。

圖2 模型的初始空間位置Fig.2 Initial position of the models

另一種算法的大體思路則是通過構建點云每個點的特征描述符后，根據設置的規則計算各個點之間的相似度，來進行匹配，得到初始的對應關系，后續對這些關系進行篩選和優化。 Cao等[2]使用了一種基于概率的方法計算對應關系，首先對原點云和目標點云進行降采樣，然后使用相干點漂移配準(Coherent point drift,CPD)算法計算初始對應關系，并將兩點間距離大于設定閾值的對應關系刪除，最后使用基于自旋圖像的方法再進行進一步篩選，得到相對可靠的對應關系集合。但是該方法適用于原點云和目標點云存在正確的部位重合，如圖2所示，模型的軀干、頭部和大腿部位是較準確的重合在一起的。Guo等[3]使用基于點云FPFH特征的方法計算出初始對應關系，原點云和目標點云在未發生形變或形變較小的部分由于相似度更高，因此更容易在這個部分得到更多的對應關系，基于這個邏輯，使用隨機抽樣(Random sample consensus，RANSAC)算法進行初始剛性配準，從而找到兩個點云的重合部位(即形變較小的部分)，同時分離出不重合的部位(即發生大尺度形變的部分)，并對初始對應關系進行篩選。最后對原點云出現大尺度形變的部位與形變較小的部分的位置判斷，構建原點云和目標點云的大尺度形變部位之間的對應關系。Sahillioglu等[4]通過積分測地線距離函數計算點云的局部極值來選取特征點并構建初始的稀疏對應關系，然后通過測地線距離計算每個對應關系的等距失真值構建一個投票矩陣，得到每個對應關系的權值，接著保留權值在設定閾值內的對應關系。然后重復特征點選取的過程，并利用稀疏對應關系拓展出新的對應關系。Sahillioglu等[5]則是通過測地線距離來對點云進行采樣，并利用采樣點進行對應關系計算。這個過程是迭代的，首先測地線距離一開始會設置較大，得到數量極少的原點云和目標點云的采樣點點集，接著在兩個采樣點集之間進行兩兩對應關系的構建，并通過測地線距離計算等距失真值，來進行對應關系的篩選，然后降低測地線距離，重復以上步驟，直至達到人工設置的計算次數或者點云中的每個點已經擁有對應關系，與第一步不同的在于，之后構建對應關系時，一些點的近鄰點已經擁有對應關系，那么這些點的計算對象會被壓縮到一定的區域，從而降低計算時間。Tam等[6]提出了一種基于譜裁剪算法對對應關系進行篩選和優化的方法，在用一些方法得到初始對應關系后，對每一對對應關系，利用其近鄰點以及近鄰點的對應關系，基于測地線距離構建出一個局部的框架圖，在此基礎上使用擴散框架計算每個對應關系的置信度，從而對每個對應關系進行篩選。 李俊[7]基于滑動分析提取出點云特征點后，根據多尺度下的局部曲率構建特征點的特征描述符，利用特征描述符的歐式距離構建初始的稀疏對應關系，基于測地線距離，使用RANSAC-譜裁剪算法剔除稀疏對應關系中的錯誤匹配，接著利用得到的稀疏對應關系進行粗剛性配準，最后使用最近點搜索得到每個點的對應關系。田利利[8]使用超體素分割算法(Voxel cloud connectivity segmentation,VCCS)對點云進行降采樣操作后，使用熱核特征構建每個點的特征描述符，使用歐氏距離構建初始對應關系，然后使用聯合一致分割算法[9]，將兩個點云分割出多個一致的對應區域，并刪除對應區域不一致的對應關系。最后使用測地線距離進行篩選，得到置信度較高的稀疏對應關系。在此基礎上使用近鄰點相互匹配的方法構建剩余的每個點的對應關系。

以上算法均使用的是基于點云的局部特征的對應關系計算方法。局部的特征提取容易受到噪聲的影響，且也沒有考慮到三維場景上的人類視覺系統特征[10]。視覺特征是人類視覺系統的一個重要特征，它描述了人類對某個場景的注意力分布情況，因此能提取出場景中相對周圍區域更獨特的部分，這些區域通常對點云的對應關系構建、配準等計算具有很好的參考意義，因此本文基于文獻[10]的局部和全局特征融合的特征檢測，提出了一種點云的對應關系構建方法。該特征檢測方法提取出原點云和目標點云在視覺上具有代表性的區域，這些區域通常都具有較高一致性。因此可以通過在這些區域間構建初始的稀疏對應關系，然后基于得到的稀疏對應關系對2個點云進行剛性配準，使2個點云的相似部位最大程度重合，來對稀疏對應關系進行最終的優化。利用得到的稀疏對應關系，使用對應關系的近鄰點的局部匹配方法，為剩余的點構建對應關系。最后使用測地線距離計算對應關系的誤差來進行評價。結果證明，本文方法對在人體模型上能得到較好的結果。

2 特征計算

本文方法考慮了點云的局部特征和全局特征，局部特征用于表示每個點與該點周圍的差異，而全局特征的目的是用于檢測整個點云模型中獨特的區域，并忽略頻繁出現的區域。計算步驟大致如下：1)局部特征值的計算；2)全局特征值的計算；3)局部和全局特征值非線性組合得到點云每個點最終的特征值。

局部特征值的計算使用的是快速點特征直方圖(FPFH)[11]。假設點pi∈P，P是計算局部特征的點云對象，FPFH(pi)指代點pi的FPFH描述符，點pi的局部特征值D(pi)計算公式為：

(1)

其中，R指pi的用于計算的近鄰點，‖pi-pj‖是指兩點間的距離。χ2(pi,pj)是兩點的自定義距離，其定義如下:

(2)

最后使用分段抑制函數，來防止標記過多點。最終點pi的局部特征值F(pi)為:

(3)

h是動態閾值，局部特征值按照從大到小排序后，對排名在20%以后點的局部特征值進行抑制。

全局特征值的計算的計算則是使用點云超體素化分割方法[12]將點云分割成多個像素區域，如圖3所示，得到點云的像素區域集合C。設某個像素區域ci∈C，FPFH(ci)表示區域ci的FPFH描述符，該描述符定義為該區域的點的FPFH平均值。則區域ci的初始全局特征值G(ci)為：

圖3 點云超體素化結果示例Fig.3 Example of VCCS results of Point Cloud

(4)

其中‖ci-cj‖是指兩個像素區域的中心點的距離，χ2(ci,cj)的定義與公式(2)相同，N是指整個區域集合。

得到每個區域的初始全局特征值后，借鑒隨機游走算法的思想，將每個像素區域的初始全局特征值引入到區域的每個點中。隨機游動算法常用于二維圖形中的分割，在待分割的圖形中選取一些具有特征意義的種子點，以這些種子點為起始，通過隨機游走模型，將一些屬于各種子點范圍內的像素挑選出來，從而完成圖像的分割[13]。

在實驗過程中，由于使用的點云的點數量較大，文獻[10]中的全局特征計算方法通過構建整個點云的路徑圖來計算每個點屬于某個種子點的概率，從而得到每個點的全局特征值，消耗時間較長，因此本文對全局特征值的計算做了部分改進，對于任何一個點，僅使用測地線距離最近的前幾個種子點來計算該點的全局特征值，從而減少計算成本。

設置閾值h1和h2，選出特征種子點和非特征種子點。初始全局特征值大于h1的像素區域設為特征像素區域，其中心點設為特征種子點。初始全局特征值小于h2的區域設為非特征像素區域，其中心點設為非特征種子點。其中，h1和h2定義為：

h2=mean(G)

Δ=max(G)-mean(G)

(5)

對于任意沒有標記為種子點的點pi，計算pi與所有種子點的測地線距離，點pi屬于測地線距離最近的那個種子點，則點pi的全局特征值G(pi)為：

G(pi)=exp(-G(ci)×‖pi-ci‖×u)

(6)

其中，當點pi屬于特征種子點時，u=0.1。當點pi屬于非特征種子點時，u=0.001?！琾i-ci‖表示點pi與其所屬種子點的距離，G(ci)表示特征點所屬的像素區域的初始全局特征值。

最后，對每個點的全局特征值和局部特征值進行非線性整合。將每個點的全局特征值和局部特征值從大到小進行排序，對于全局特征值和局部特征值排名均在前20%的點，保留其中的最大值；對于全局特征值或局部特征值排名在最后20%的點，取兩者的乘積；剩余情況，則取兩值的平均值。

3 對應關系計算

利用得到的特征值提取出特征點集，在特征點集之間兩兩構建初始稀疏對應關系，然后根據FPFH距離和相關系數對初始稀疏對應關系進行初步篩選，接著使用ICP配準算法[14]進行一個粗對齊，再基于距離進行篩選，得到稀疏對應關系。然后通過稀疏對應關系的近鄰點匹配的方式，計算剩余點的對應關系。

3.1 特征點選取以及初始稀疏對應關系構建

對點云的特征值進行排序，選取特征值排名在前50%的點作為備選特征點點集，并在該點集中選取特征點用于稀疏對應關系的構建。首先設置特征點點集F，以及備選特征點點集的訪問隊列flag，flag隊列的長度為備選特征點點集長度，且初始值均為0，用于表示某個點是否被訪問過。人為設置要獲取的特征點數量kF。接下來的特征點選取算法步驟如下：

1)查詢當前備選特征點點集中特征值最大且訪問隊列參數不為1的點，將該點加入特征點點集F，該點的訪問隊列參數設置為1；

2)以該特征點為中心，一定半徑內的屬于備選特征點點集的近鄰點的訪問隊列參數設置為1；

3)如果特征點點集F的元素數量等于kF，或者訪問隊列參數均為1，停止，否則到步驟1。

這樣就得到了點云的特征點點集，這里kF設置大小為6。然后在原點云和目標點云的特征點點集之間兩兩構建對應關系，也就是有kF·kF個初始稀疏對應關系。

在上一步得到初始稀疏對應關系后，需要將錯誤的對應刪除，這里使用點的FPFH以及相關系數為每個對應關系計算一個初始權值。然后基于對應關系對原點云和目標點云進行粗剛性配準，在兩者不斷逼近的過程中重新計算對應關系權值，并加入空間距離，最后得到置信度較高的稀疏對應關系。

對任意點pi，利用點pi以及其近鄰點構建協方差矩陣Ci，該點相關系數factor(pi)定義如下：

(7)

其λ1，λ2，λ3是矩陣Ci的特征值，λ1>λ2>λ3。

設稀疏對應關系中的一對對應關系(sj,ti)，sj和ti分別是原點云和目標點云上的一個點，這對對應關系的權值wij為：

wij=exp(-factor_dis)+exp(-FPFH_dis)

(8)

其中，factor_dis是點sj和ti的相關系數相減取絕對值，FPFH_dis是兩點間的自定義距離，定義與公式(2)相同。

然后對每個對應關系的權值從大到小進行排序，本文采用[14]中的剛性配準的思想，取其中權值排名前20%對應關系，作為粗剛性配準的初始數據。

在進行了一次剛性配準后，重新計算所有對應關系的權值。計算公式如下：

wij=wij×?1+exp(-‖sj-ti‖)·(1-?1)

(9)

?1是人為設定的值，這里設置為0.5，然后每個對應關系的權值從大到小重新進行排序，依舊取權值排名前5對對應關系作為下一次剛性配準的新的數據。以上過程重復進行，直至剛性配準的結果不再發生改變或者達到設置的迭代次數。在剛性配準迭代的過程中，隨著2個模型逐漸重疊，距離在對應關系的權重中所占的比值會逐漸增加。此時會得到1個原點云和目標點云的相對有意義的空間位置。然后使用剛性配準方法對兩者進行最后的一次配準，得到原點云和目標點云剛性部位較好重合的結果，基于這個結果，計算2個點云的特征點兩兩之間的距離，取距離在一定范圍內并且最短的特征點作為對應點，得到最終的稀疏對應關系。

3.2 最終對應關系構建

利用已得到的稀疏對應關系，本文采用一種對應關系的近鄰點相互匹配的思路為剩余的點構建對應關系，假設一對對應關系(sj,ti)，分別為原點云sj和目標點云上的點ti，搜索對應關系中各點的近鄰點，得到sj和ti的近鄰點集合，則sj的近鄰點的對應點搜索范圍則限制在ti的近鄰點集合中，得到的新的對應關系又作為下一次對應關系計算的基礎。這樣既可以有效減少搜索空間，又可以提高準確率。該算法的步驟如下：

1)設置對應關系集合H，將已得到的稀疏對應關系放入集合H中，設置訪問隊列S_H和T_H，長度分別初始化為原點云和目標點云的點數量，用于表示原點云和目標點云中的點是否已經有對應點。

2)遍歷關系集合H，設一對對應關系(sj,ti)∈H，sj和ti分別是原點云和目標點云上的1個點，通過kd樹查詢得到sj的沒有對應點的近鄰點集合sj_n，ti的沒有對應點的近鄰點集合ti_n，計算sj_n和ti_n的中每個點之間的空間距離和自定義距離(見公式(2))的和，取每個點對應和最小的點作為一對對應關系，并加入集合H。當S_H或T_H表示所有點已經擁有對應關系時，停止遍歷，得到原點云和目標點云最終的對應關系集合。

4 實驗結果與分析

本文使用測地線距離計算得到的對應關系的等距失真Diso。測地線距離是指曲面上2點之間的最短距離[15]。

(10)

其中，diso(sj,ti)是個體對應關系(sj,ti)對整體等距失真的貢獻值：

(11)

g(sj,sm)是兩點間的測地線距離。

本文使用FAUST數據集中的tr_reg_000～tr_reg_003，和SCAPE數據集中的mesh020～mesh022模型進行實驗。以數據tr_reg_000作為目標點云，tr_reg_001作為原點云進行示例，由于原始數據已經是對齊狀態，如圖2所示，為了驗證本文方法的有效性，對數據集中模型通過手工的方式，將空間相對位置全部打亂，如圖4所示，左邊是原點云(紅)和目標點云(藍)的原始空間相對位置，右邊是人為改變后的相對位置。

圖4 人為改變相對位置Fig.4 Artificial change of relative position

目標點云和原點云的特征值計算結果如圖5所示，圖5(A)是目標點云的特征值示意圖，圖5(B)是原點云的特征值示意圖。從左到右分別為點云的局部特征值、全局特征值、局部和全局特征值融合結果。特征點則選取如圖6所示。

圖5 特征值結果示意圖Fig.5 Features results

圖6 特征點的選取結果Fig.6 Selection results of feature Points

兩個特征點之間構建的最終稀疏對應關系如圖7所示，基于稀疏對應關系的剛性配準結果如圖8所示，圖8(A)是本文提出的算法的計算結果，圖8(B)是傳統ICP算法的計算結果。為驗證本文改進的ICP算法的有效性，設置了以下幾組實驗數據，如圖9所示，其中，紅色為目標點云，藍色為原點云，配準結果通過均方根誤差RMSE評價，該誤差定義如下：

圖7 稀疏對應關系計算結果示意圖Fig.7 Coarse Correspondence results

圖8 配準結果Fig.8 Registration results

圖9 配準前的相對位置Fig.9 Relative position before registration

(12)

其中，qi表示原點云上的一點，pj是qi的對應點，‖qi-pj‖表示兩點間的歐氏距離。一般來說，當值小于0.008時，結果是可靠的。本文方法的對齊效果如圖10所示，傳統ICP方法的對齊效果如圖11所示，誤差如表1所示，可以看出，當模型位置差異較大時，本文方法能得到一個較好的對齊結果。因為傳統ICP算法是通過最近點搜索得到對應關系，在此基礎上進行配準，當模型的動作差異較大時，效果較差，本文在傳統ICP方法的基礎上計算了比較可靠的稀疏對應關系作為前置條件，因此能得到較好的配準結果。

圖10 本文配準結果Fig.10 Our registration results

圖11 傳統ICP配準結果Fig.11 ICP registration results

表1 剛性配準結果評價Tab.1 Evaluation of registration results

點云剩余點的對應關系計算過程示意如圖12所示，圖12(A)是已經計算得到的對應關系，圖12(B)是通過對應關系之間的近鄰點匹配構建新的對應關系，圖12(C)展示了部分最終計算得到的對應關系結果。以FAUST數據集的tr_reg_000為目標點云，tr_reg_001～tr_reg_003為原點云，其對應組分別為a、b、c。以SCAPE數據集的mesh020為目標點云，mesh021和mesh022為原點云，其對應組分別為d和e，最終對應關系計算結果如圖13所示，以上幾組模型的對應關系結果的等距失真如表2所示，同時將本文方法與文獻[5]、文獻[6]的方法進行了對比。由于文本方法依賴于配準結果，所以當原點云和目標點云擁有較少形變部分的情況下，如實驗組a、b、c和d，能取得較好的結果，但是在實驗組e上結果較差。而文獻[5]與文獻[6]的方法主要依賴于點云的特征描述，因此在面對不同形變程度的模型時，結果相對比較穩定。

表2 對應編號的點云對應關系各項評價數據Tab.2 Evaluation of Point Cloud Correspondence

圖13 最終對應關系計算結果示意圖Fig.13 Results of final Correspondence

5 結束語

本文提出了一種基于局部和全局特征融合進行特征檢測的方法來計算點云對應關系的方法，該方法能夠穩定的獲得原點云和目標點云的具有較高一致性的特征區域，從而為后續獲得較可靠的稀疏對應關系提供了良好的條件，且只需要擁有坐標數據的點云就可自動實現，不需要額外的信息。通過在不同幾個數據組上的實驗結果表明，本文方法在形變程度不是很大的人形點云數據上表現較好。由于本文方法比較依賴于剛性配準的結果，在應對形變程度較大的點云數據時表現不理想，因此，本文方法在配準這一步還有改進的空間。