吳 振 慧

(揚州職業(yè)大學, 江蘇 揚州 225009)

三維點云作為一種通過非接觸方式采集得到的數(shù)據(jù),信息量豐富,可反映物體三維信息,目前常用于工程、醫(yī)學、建筑、環(huán)境等諸多領(lǐng)域[1]。然而,在三維點云數(shù)據(jù)的采集過程中,由于采集設(shè)備、采集視角、采集過程等原因,采集得到的點云通常無法達到設(shè)備理論的最高精度,會存在如點云稀疏、噪聲、不完整等缺陷。因此,與完整點云相比,低質(zhì)量點云會帶來特征點稀疏、特征數(shù)目差距較大等問題,給配準帶來較大挑戰(zhàn)[2]。近年來,點云配準算法的研究不斷發(fā)展,第一類方法是對傳統(tǒng)ICP算法進行改進和優(yōu)化,這些方法旨在解決ICP算法易于陷入局部最優(yōu)的缺點,但速度比傳統(tǒng)ICP算法慢,且通用性受限[3]。第二類方法是基于深度學習方法,注入基于三維卷積神經(jīng)網(wǎng)絡(luò)的點云分割和配準方法PointNet[4],以及在此基礎(chǔ)上衍生出的諸多方法,這類方法在處理低質(zhì)量點云時需要提供諸多訓(xùn)練集,網(wǎng)絡(luò)訓(xùn)練耗費時間很長,且配準精度難保證[5]。針對低質(zhì)量點云的配準問題,筆者提出一種粗匹配和精匹配相結(jié)合的點云配準算法,即基于PPF特征進行點云的粗匹配,得到配準結(jié)果后,將其作為ICP精匹配方法的迭代初值,從而解決ICP方法容易因初值設(shè)定不佳而落入局部最優(yōu)解的問題。最終將整套配準算法在低質(zhì)量的點云上進行實驗驗證,證明了方法的有效性和魯棒性。

1 粗-精匹配結(jié)合的點云配準算法

傳統(tǒng)ICP方法在迭代初值設(shè)定合適時,可以完成點云的精確配準,但因為迭代過程較慢,通常作為精匹配算法。為解決其初值選擇的問題,本文采用基于PPF特征的粗匹配方法,形成了粗精匹配結(jié)合的點云配準算法。

1.1 基于PPF特征的粗匹配算法

PPF特征是一種三維點云的特征描述子,基于Hough Voting的思想,擺脫了傳統(tǒng)特征描述子依賴于局部特征的缺點,對于輕微變形或部分遮擋的情況,具有魯棒性好的優(yōu)點,抗噪聲能力較強,且一次可以計算出多個結(jié)果[6]。

PPF特征描述的是兩個有向點的相對位姿,假設(shè)兩個點為p1和p2,其法向量分別是n1和n2,定義矢量d=p1-p2,則將PPF定義為一個四元數(shù):F(p1,p2)=(‖d‖d2,∠(n1,d),∠(n2,d),∠(n1,n2)),這是一個非對稱的特征描述子,其中∠(a,b)∈[0,π]表示兩個矢量的夾角,其定義示意如圖1所示。

圖1 Point Pair Feature定義

在完成三維點云的PPF特征構(gòu)建后,構(gòu)建全局模型描述,具體方式為:計算三維點云表面所有點對的特征描述子,并構(gòu)建哈希表,將具有相同描述子的點對作為哈希表的值(Value),將其描述子F作為哈希表的鍵(Key)[7]。哈希表構(gòu)建見圖2。

圖2 PPF哈希表構(gòu)造

完成哈希表的構(gòu)造后,即可進行點云的粗匹配,其基本流程為:

流程一:定義模型點云為M={mi},i=1,2,…,M,真實點云為N={ni},i=1,2,…,N,其中mi,ni∈R3表示各個點的三維坐標。首先給定N中的參考點對(ni,nj),并在M中選取與參考點對具有相似特征的點對(mi,mj)。需要將匹配的兩點進行配準,則需要將點的位置和其法向量對齊。

流程二:通過變換矩陣Tn→g將ni移動到局部坐標系原點,并轉(zhuǎn)動其法向量與局部坐標系X軸重合,對真實點云也進行移動和轉(zhuǎn)動。同理,通過Tm→g對mi和模型點云也進行相同操作。

流程三:將模型點云中的mj繞著X軸轉(zhuǎn)動Rx(α)使其與nj配準。

采用PPF進行粗匹配的一大特點在于,每個參考點可能返回多個位姿,對于多個可能位姿,需要進行聚類,最終提取出得分最高的類包含的位姿均值,即為PPF粗匹配最終結(jié)果。這一結(jié)果根據(jù)機器人學原理,也可以表示為位姿矩陣的形式:

(1)

其中R∈R3×3表示旋轉(zhuǎn)矩陣,t∈R3×1表示平移向量。

1.2 基于ICP的精匹配算法

ICP(迭代最近點)方法通常分為點到點和點到面兩種[8]。本文采用點到點的ICP方法,此時匹配問題可以理解為一個優(yōu)化函數(shù)的求解問題,該目標函數(shù)為:

(2)

其中mj*表示在模型點云M中和真實點云中的(Rni+t)歐氏距離最近的點。

采用迭代最近點算法進行點云精匹配的流程概括如下:第一,在模型點云M中查找真實點云N各點的最近點,根據(jù)最近點的配對結(jié)果,采用奇異值分解計算旋轉(zhuǎn)矩陣R和平移向量t。第二,根據(jù)計算的旋轉(zhuǎn)矩陣和平移向量通過(Rni+t)移動真實點云N。第三,反復(fù)重復(fù)步驟1—步驟2,直到真實點云N中各點與其最近點的距離誤差小于閾值,完成迭代。

采用ICP進行精匹配之前,需要對點云進行預(yù)處理。首先,對大型點云進行降采樣,保留有效信息即可完成點云匹配,因為過多的點會導(dǎo)致算法時間大大延長,但效率提高甚微。接著,構(gòu)建如八叉樹或K-D樹的數(shù)據(jù)結(jié)構(gòu)存儲點云數(shù)據(jù),因為在ICP算法計算過程中,運算量最大的一步在于查找模型點云中每個點的最近點,若數(shù)據(jù)量較大且采用暴力搜索的方式,將會導(dǎo)致算法時間過長,因此需構(gòu)建加快最近點查找的數(shù)據(jù)結(jié)構(gòu)[9]。最后,對模型點云和真實點云均進行去中心化,即將用于配準的模型和真實點云坐標均分別減去其質(zhì)心坐標,直觀地可以理解為將點云質(zhì)心均移至坐標系原點,這一步可大大加快最近點查找的速度。

1.3 整體算法流程

由上文可知,采用PPF進行粗匹配可以得到一個評分最高的位姿矩陣,而采用ICP進行精匹配需要一個較好的迭代初值避免其陷入局部最優(yōu)解,因此本文設(shè)計將粗匹配計算出的結(jié)果作為精匹配的迭代初值,粗精匹配結(jié)合的點云配準算法流程如圖3所示:

圖3 整體算法流程圖

本文粗精匹配結(jié)合的點云配準算法核心步驟在于通過粗匹配的結(jié)果對模型點云M中各點的坐標進行更新:

mi′=R0mi+t0

(3)

其中R0和t0分別是從PPF計算的位姿矩陣T中提取出的旋轉(zhuǎn)矩陣和平移向量。通過該步驟對模型點云進行更新后,模型點云已經(jīng)大致移動到和真實點云一致的位置,即R0和t0已經(jīng)接近最終的配準結(jié)果,但精度不一定滿足需求。此時,將移動后的模型點云和真實點云進行ICP精匹配,實際上就是將R0和t0作為ICP精匹配的迭代初值,相較于直接用真實點云N進行匹配,這種方法可以有效避免匹配結(jié)果出現(xiàn)局部最優(yōu)解,并可以減少精匹配過程中的迭代次數(shù),從而提高算法的整體速度。

此外,本文為提高匹配算法的計算速度,在采用PPF進行粗匹配后,首先對已完成粗匹配的模型點云和真實點云計算其最近點之間的歐氏距離,當距離小于某一閾值,則判斷已完成匹配,即粗匹配精度達到要求,無需進行精匹配。根據(jù)公式(2)可知,本文設(shè)定模型點云不動,通過移動真實點云完成最終匹配,在實際計算過程中,將真實點云固定不動,移動模型點云也是可行的。由于本文考慮到點云有殘缺,若固定真實點云N不動,則需要查找模型點云M各點的最近點,會導(dǎo)致模型點云中對應(yīng)殘缺部分的點始終無法找到最近點,由此ICP算法迭代誤差保持很大,難以完成公式(2)的計算收斂。

2 算法實驗驗證和分析

為驗證本文提出的針對低質(zhì)量點云的點云配準算法,本文采用斯坦福大學的點云配準數(shù)據(jù)集,該數(shù)據(jù)集為點云匹配算法驗證的經(jīng)典公開數(shù)據(jù)集。本文對其中一組點云進行人為處理,分別構(gòu)造稀疏點云、含噪聲點云以及殘缺點云這三類低質(zhì)量點云,對其進行算法的實驗驗證。本文采用Matlab編寫算法程序,計算平臺硬件為i7-10750H處理器、16G內(nèi)存的電腦。

首先,人為設(shè)定真實點云和模型點云在X、Y、Z軸均存在10°的轉(zhuǎn)角偏差,即位姿變換矩陣為:

R=Rz(10°)Rx(10°)Ry(10°)

(4)

(5)

其中Rx(α)、Ry(α)、Rz(α)分別表示繞X軸、Y軸、Z軸旋轉(zhuǎn)α角度的三維旋轉(zhuǎn)矩陣。初始情況下,真實點云和模型點云的位姿偏差如圖4所示,其中淺色為真實點云,深色為模型點云。在實驗過程中,考慮到點云總尺度以及匹配精度的要求,本文設(shè)定ICP算法迭代收斂條件為:模型點云和真實點云中對應(yīng)最近點的距離小于2 mm(該精度滿足絕大部分的工業(yè)應(yīng)用場景),若迭代3步仍無法達到收斂條件,則退出迭代過程。配準結(jié)果中淺色和深色表示配準后的真實點云及模型點云。

圖4 初始位姿偏差

2.1 稀疏點云配準

針對點云稀疏的情況,對真實點云中的點進行降采樣,模擬在點云數(shù)據(jù)采集過程中采集點數(shù)目較少的情況。在實驗過程中,本文隨機刪去真實點云中的部分數(shù)據(jù)點,選用原始點云50%、20%、10%數(shù)目的點作為稀疏點云進行配準,在ICP算法、PPF算法以及本文提出的粗精匹配結(jié)合的算法上進行匹配,結(jié)果如圖5、圖6、圖7所示。

圖5 50%稀疏點云配準結(jié)果

圖6 20%稀疏點云配準結(jié)果

圖7 10%稀疏點云配準結(jié)果

由上圖可見,在進行稀疏點云配準時,采用傳統(tǒng)ICP方法難以完成準確的點云配準,存在較大誤差,采用PPF方法配準結(jié)果較好,采用粗精匹配結(jié)合的方法驗證了PPF配準結(jié)果的準確性,最終輸出結(jié)果匹配精度高。

2.2 含噪聲點云配準

針對真實點云無法避免的采集噪聲,本文給真實點云人為添加均值為0,方差不同的高斯噪聲,模擬點云數(shù)據(jù)存在噪聲波動的情況,分別設(shè)定標準差為0.5 mm、0.7 mm、1 mm,其數(shù)值越大表示點云的噪聲越強烈。點云配準結(jié)果如圖8、圖9、圖10所示。

圖8 方差0.5 mm噪聲點云配準結(jié)果

圖9 方差0.7 mm噪聲點云配準結(jié)果

圖10 方差1 mm噪聲點云配準結(jié)果

由上圖可見,在對含噪聲的點云進行配準時,傳統(tǒng)ICP算法在三種噪聲情況不同的點云上均無法完成準確配準。在方差0.5 mm噪聲點云上,采用PPF粗匹配即可完成準確配準;在方差0.7 mm噪聲點云上,采用PPF粗匹配僅可完成大致定位,在此基礎(chǔ)上采用ICP精匹配可實現(xiàn)對點云的準確配準;在方差1 mm噪聲點云上,采用粗精匹配結(jié)合的方法雖然無法完成非常準確的配準,但配準精度高于僅采用PPF或ICP匹配方法。

2.3 殘缺點云配準

考慮到點云在采集過程中會因存在遮擋而導(dǎo)致點云殘缺的情況,筆者在X、Y、Z三個方向上分別模擬點云殘缺的情況,需要注意的是,殘缺點云雖然表現(xiàn)的也是點云數(shù)據(jù)的缺少,但和稀疏點云存在區(qū)別:殘缺點云缺少集中的部分區(qū)域,造成點云整體形狀變化;稀疏點云數(shù)據(jù)量雖少,但點云整體形狀與原始點云接近,缺乏的是點云表面的細節(jié)特征。本文實驗采用的殘缺點云如圖11所示,其中深色部分為原始點云,淺色部分為刪去部分區(qū)域后的殘缺點云。

圖11 殘缺點云示意圖

分別針對三種殘缺點云的配準結(jié)果如圖12、圖13、圖14所示。

圖12 X方向殘缺點云配準結(jié)果

圖13 Y方向殘缺點云配準結(jié)果

圖14 Z方向殘缺點云配準結(jié)果

由上圖可見,針對Y方向和Z方向殘缺的點云,采用ICP算法配準效果一般,這是因為剩余部分的點云保留了大部分顯著特征,可支持ICP算法完成迭代計算。針對X方向殘缺的點云,采用ICP算法難以完成配準,采用PPF算法配準效果一般,采用本文提出的粗精匹配結(jié)合的方法配準準確。

2.4 配準速度分析

由上述三類實驗已知,本文提出粗精匹配結(jié)合的配準算法可完成對低質(zhì)量點云的準確配準。此外,為驗證本文提出的方法快速性,本文對上述三類共九組實驗的計算時間進行了統(tǒng)計,見表1。

表1 計算時間 單位:s

分析上表可知,采用本文提出的粗精匹配點云配準算法,其計算時間通常小于傳統(tǒng)ICP算法。此外,因為PPF算法的計算時間包含在本文算法中,所以單獨采用PPF進行配準的時間較短。綜上所述,采用本文的點云配準算法,不僅可以對低質(zhì)量點云完成精確配準,其配準時間也小于傳統(tǒng)ICP點云配準方法,做到了速度和精度兩方面的提高。

3 結(jié)語

針對低質(zhì)量點云配準存在的困難,本文提出了一種粗精匹配結(jié)合的點云配準算法,基于PPF的粗匹配方法和ICP的精匹配方法設(shè)計了整套算法流程。實驗驗證了對稀疏點云、含噪聲點云以及殘缺點云的配準結(jié)果,配準精度高、速度快,可用于對工業(yè)現(xiàn)場采集的真實點云的配準。