基于點云配準(zhǔn)的曲面三維差異檢測*

羅錦鴻，陳新度，吳 磊

(廣東工業(yè)大學(xué)機電工程學(xué)院，廣州 510006)

0 引言

在視覺引導(dǎo)機器人的智能化自動化加工任務(wù)中，工件的形狀誤差分析和三維差異數(shù)據(jù)提取是一個關(guān)鍵研究問題。本文針對陶瓷素胚工件的機器人自動化打磨任務(wù)，需要對陶瓷素胚工件的部分表面進行差異比對以識別定位加工區(qū)域。為了獲取待加工工件的點云數(shù)據(jù)，如圖1a所示，利用了三維掃描儀來掃描待加工工件的表面，如圖1b所示，有標(biāo)準(zhǔn)模型曲面點云(白色)和通過掃描得到的待檢測曲面點云(藍色)。

近年來，研究人員通過對三維視覺方法獲取的實測曲面的三維數(shù)據(jù)進行分析，來實現(xiàn)曲面差異檢測，而使用點云配準(zhǔn)的方法來讓標(biāo)準(zhǔn)模型數(shù)據(jù)與實測數(shù)據(jù)對齊用來實現(xiàn)差異檢測逐漸成為趨勢，比如李宇萌等[1]采用了ICP精確配準(zhǔn)的方法進行模型與實測數(shù)據(jù)對齊，在102 s內(nèi)將2萬左右點云的精確對齊，實現(xiàn)了轉(zhuǎn)子表面的缺陷檢測。馬維康等[2]通過手持式智能激光掃描儀對試驗件不同工序段進行掃描測量,將掃描的三維點云數(shù)據(jù)與設(shè)計的理論數(shù)模進行對比分析,得出型面精度的偏差情況,以此來檢驗試驗件是否合格。

但是前人的方法大部分是針對全局配準(zhǔn)或者位姿容易確定的情形，可以使用ICP算法直接進行數(shù)據(jù)對齊。在面向待配準(zhǔn)點云數(shù)據(jù)是模型的局部實測數(shù)據(jù)的情形時，這些方法并不適用的。本文針對這種局部曲面配準(zhǔn)情況，測試了兩種基于局部特征的配準(zhǔn)方法，實現(xiàn)了快速粗配準(zhǔn)。在精確配準(zhǔn)階段，由于ICP配準(zhǔn)算法在面對大型點云數(shù)據(jù)時耗時長，滿足不了本文的實時性的要求。本文實現(xiàn)了一種由CUDA加速的ICP算法，實現(xiàn)了大型曲面點云的快速對齊。而且在曲面對齊后，通過本文設(shè)計的引入Octree預(yù)檢測的差異提取方法可以快速地提取曲面的三維差異。

通過本文設(shè)計的實驗證明，在面對要求實時性比對檢測目標(biāo)曲面與標(biāo)準(zhǔn)模型曲面的任務(wù)時，本文的方法具有精度高、可靠、快速的特點。

(a) 得到工件單幀掃描點云 (b) 掃描點云(藍)和模型點云(白)

1 基于Hough投票的粗配準(zhǔn)

點云配準(zhǔn)是指利用兩幅點云的匹配點，利用匹配關(guān)系來估算兩幅點云的旋轉(zhuǎn)平移關(guān)系，從而使兩幅點云正確地重合在一起。首先要解決的是精確配準(zhǔn)的初值問題，即解決粗配準(zhǔn)問題。

點云的粗配準(zhǔn)方法有很多，研究人員針對工件點云的粗配準(zhǔn)問題上進行過很多研究，比如陳巍等[3]、周欣康[4]和項輝宇等[5]分別在校正葉片工件的裝夾誤差研究中、航空葉片型面檢測中以及板金屬沖壓零件表面模型與實測點云配準(zhǔn)研究中，都使用了PCA(主成分分析)的全局配準(zhǔn)算法，對實測點云與模型點云進行粗對齊。但是由于PCA算法要求實測點云形狀與模型相近，這就需要在獲取數(shù)據(jù)時，完整地掃描工件。

本文要對工件的待加工處的部分掃描點云與整體模型點云進行配準(zhǔn)，顯然PCA全局配準(zhǔn)方法不合適，文章考慮了基于局部特征的粗配準(zhǔn)算法，基于局部特征的配準(zhǔn)方法主要有SAC-IA[6](Sample Consensus Initial Alignment)、RANSAC[7]和三維霍夫投票[8](Hough voting)。本文分別對三維霍夫投票法和SAC-IA兩種算法進行了測試。

本文總算法流程如圖2所示。有模型點云M={m1,…,mi}和通過實測掃描點云S={s1,…,sj}，分別對M和S進行濾波得到稀疏的下采樣點云M′={m1′,…,mk′ }和S′={s1′,…,sl′ }。計算M′和S′中的每個點的局部特征描述子F(M′)={fm1′,…,fmk′ }，F(xiàn)(S′)={fs1′,…,fsl′}和局部參考坐標(biāo)系LRF(M′)={rm1′,…,rmk′ }，F(xiàn)RF(S′)={rs1′,…,rsl′}。使用Hough投票法或采樣一致性初始對齊(SAC-IA)算法得到粗對齊矩陣T1，使用T1變換S中的每個點，得到粗對齊點云S_initial，然后用CUDA加速的ICP算法完成S_initial與M的精確對齊，得到最終配準(zhǔn)完成的掃描點云S_dest，在提取差異點云步驟中，遍歷S_dest點云中的所有點，當(dāng)查詢點與其在M中最近的點之間的距離大于設(shè)定閾值時，將該查詢點看作是差異點，加入到差異點集合S_d，遍歷完成后，最終的集合S_d是差異點云。

圖2 三維差異檢測算法流程圖

1.1 體素柵格采樣

體素柵格采樣是點云數(shù)據(jù)精簡的一種非常實用的方法，它首先創(chuàng)建一個三維的體素柵格，輸入點云將包含在柵格中的三維立方體內(nèi)，然后用三維立方體中所有的點計算平均值得到重心點，用來近似表示體素中其他點，統(tǒng)計重心點集合將得到下采樣點云。

實驗表明，對于以本文中的工件為代表的典型平滑曲面點云，由于點云密集以及曲面光滑，三維局部特征十分相似，如果直接使用原始數(shù)據(jù)進行粗配準(zhǔn)會導(dǎo)致計算量非常大而且失敗。于是本文采用了柵格濾波算法對模型點云M和掃描點云S進行濾波。數(shù)據(jù)量在210 000左右的模型點云和數(shù)據(jù)量在34 000左右掃描點云下柵格濾波后的數(shù)據(jù)量為8 200和1 300左右。輸入點云柵格下采樣后的點云如圖3所示。點云濾波后，在空間分布上具有規(guī)律性，在計算三維局部特征時，通過采用柵格濾波后的點作為關(guān)鍵點將有效地去冗余點云，以及減少了計算特征描述子要考慮的近鄰點數(shù)，加快了粗配準(zhǔn)的速度以及成功率。

圖3 柵格采樣后的模型點云和掃描點云的狀態(tài)

1.2 3D-Hough投票

3D-Hough[8]中算法具體步驟如下：

(1)輸入模型的下采樣曲面點云M′={m1′,…,mk′ }和下采樣掃描點云S′={s1′,…,sl′}。

(2)計算M′和S′中的每個點的局部三維特征描述子F(M′)={fm1′,…,fmk′ }，F(xiàn)(S′)={fs1′,…,fsl′}和局部參考坐標(biāo)系LRF(M′)={rm1′,…,rmk′ }，F(xiàn)RF(S′)={rs1′,…,rsl′}。

(3)在本實驗中，將重心點作為Hough投票的參考點。于是先計算M′的重心點c_m，再計算M′中每個點到重心點c_m的向量vmk=c_m-mk′，得到向量集合V_M={vm1,…,vmk}。

(4)通過局部三維特征描述子歐式距離作為匹配度來計算大小為n的匹配集。

(5)遍歷匹配集合，匹配上的對應(yīng)點mn和sn對應(yīng)的兩個參考坐標(biāo)系：rmk′到rsl′之間有變換矩陣Tn，于是有Tn*vmn=vsn，即估計的掃描點云的重心點為csn=Tn*vmn+sl′。

(6)通過步驟(5)的計算就會得到一個重心點集合C_S={cs1,…,csn}。集合C_S即是三維Hough空間中的投票。

(7)為集合C_S設(shè)置區(qū)間步長劃分投票空間，當(dāng)投票數(shù)超過一定時，選取投票數(shù)最大的區(qū)間，該峰值區(qū)間中的所有投票重心求平均值即為掃描點云的參考點(掃描點云重心)。

(8)通過對峰值區(qū)間篩選的對應(yīng)關(guān)系，可以計算出模型點云與掃描點云之間的旋轉(zhuǎn)平移變換矩陣。

本文分別對6組在不同的位置拍攝的單幀掃描數(shù)據(jù)進行了測試，粗配準(zhǔn)后狀態(tài)如圖4所示。

圖4 粗配準(zhǔn)后的模型點云和掃描點云的狀態(tài)

如表1所示，在同等效果的情況下，使用基于局部特征的的3D-Hough投票算法更快，平均運行時間在0.3 s以內(nèi)。這是由于SAC-IA方法是在匹配點集中不斷抽取必要數(shù)目的匹配點去估算變換矩陣，所以要進行多次抽取來選取最小誤差的估算變換參數(shù)，而3D-Hough投票算法，通過找出峰值的方式來剔除錯誤匹配點對，一次估計就可以求解出變換矩陣，所以速度更快。

表1 測試SAC-IA和Hough投票法

續(xù)表

2 CUDA加速的點云精確配準(zhǔn)

2.1 ICP

在點云精確對齊領(lǐng)域，Besl P J等[9]提出了經(jīng)典的ICP(Iterative Closest Point)配準(zhǔn)算法，通過迭代最近點的方法實現(xiàn)了兩個點云的精確配準(zhǔn)。通過上面的粗配準(zhǔn)步驟后，再通過ICP算法進行精確配準(zhǔn)可以使得兩個點云精確對齊。

ICP算法基本原理是：分別在待配準(zhǔn)的目標(biāo)點云P和源點云Q中，按照一定的約束條件比如鄰近關(guān)系，找到對應(yīng)點對最鄰近點對，構(gòu)建基于距離的誤差函數(shù)式(1)。不斷迭代計算出最優(yōu)匹配參數(shù)R和t，使得誤差函數(shù)最小，直至達到滿意的誤差要求，一般使用SVD或者非線性優(yōu)化方法求解。

(1)

2.2 CUDA-ICP

直到最近，幾乎所有的視覺實現(xiàn)都使用了GPU或FPGA等方法進行加速[10-11]。由于本文模型以及點云點數(shù)較多，而且面對曲率變化小，特征不明顯的點云下采樣后在精確配準(zhǔn)時會損失精度甚至可能配準(zhǔn)失敗。本文利用了GPU的超高性能計算能力，以及CUDA架構(gòu)的簡易開發(fā)性，編寫了CUDA程序來加速ICP算法，以實現(xiàn)實時配準(zhǔn)。

在實驗中，首先利用了K-D tree(k-dimensional樹)數(shù)據(jù)結(jié)構(gòu)實現(xiàn)了快速的最近點搜索，對一個模型點云構(gòu)建一次K-D tree可以用于多次迭代中的最近鄰搜索。其次，通過在對應(yīng)估計的步驟中利用多線程來同時計算搜索近鄰。再者，在剛體變換掃描點云S步驟中，開啟多線程同時對每個點進行矩陣運算。最后，在需要規(guī)約計算的地方使用CUDA提供的Thrust庫的接口thrust::reduce實現(xiàn)快速規(guī)約運算，這些方法都極大地加速了配準(zhǔn)過程。

圖5是本文中的CUDA-ICP算法計算和優(yōu)化的流程圖以及詳細步驟。

圖5 CUDA-ICP算法流程圖

(1)初始化：輸入M={m1,…,mm}和經(jīng)過粗對齊后的掃描點云S={s1,…,sn}。輸入收斂閾值τ和連續(xù)收斂次數(shù)閾值t以及最大近鄰閾值d；

(2)對模型點云M構(gòu)建K-D tree，用于最近鄰查詢；

(3)開啟大于n數(shù)量的線程并行：通過已經(jīng)構(gòu)建好的K-D tree實現(xiàn)最近鄰搜索，尋找到S中每個點sn在M中的最近點mm，當(dāng)對應(yīng)點之間的距離小于d時加入對應(yīng)點集合。最終得到對應(yīng)點集合M′和S′；

(4)使用thrust庫進行規(guī)約：計算集合M′和S′之間的誤差et；

(5)計算迭代誤差前后變化Δe=|et-et-1|，當(dāng)Δe大于設(shè)定收斂閾值τ，則繼續(xù)執(zhí)行。當(dāng)Δe小于τ時則認為本次迭代收斂，若連續(xù)收斂的次數(shù)大于設(shè)定的次數(shù)閾值t，就結(jié)束計算，本實驗中t=5；

(6)使用thrust庫進行規(guī)約：計算M′和S′的重心點M_c和S_c；

(7)開啟大于n數(shù)量的線程并行：計算去重心點集合M_2和S_2；

(8)開啟大于n數(shù)量的線程并行：計算去重心點集合M_2和S_2之間的協(xié)方差矩陣集合W；

(9)使用thrust庫進行規(guī)約：對集合W進行規(guī)約得到協(xié)方差矩陣w。使用SVD分解w得到本次迭代的變換矩陣T；

(10)開啟大于n數(shù)量的線程并行：使用變換矩陣T來旋轉(zhuǎn)平移掃描點集合S中的每個點，變換后的掃描點集合作為S跳到步驟(3)；

(11)結(jié)束計算。

表2 測試CUDA-ICP

續(xù)表

本文對6組實驗數(shù)據(jù)進行了測試，如表2結(jié)果所示，本文改進的CUDA-ICP算法將原本運行時間在7 s左右的基于K-D tree的標(biāo)準(zhǔn)ICP配準(zhǔn)算法加速到了0.5 s左右。本文配準(zhǔn)精度控制在RMS誤差小于0.5 mm，每次迭代時間控制在配準(zhǔn)耗時控制在1.5 ms以內(nèi)，滿足本文中的三維差異定位任務(wù)的準(zhǔn)確性和實時性的要求。

3 三維差異提取

本文認為掃描點云S_dest={sd1,…,sdj}的當(dāng)前查詢點與其在模型點云M={m1,…,mi}上的最近點的距離大于某個設(shè)定的距離閾值時，就認為該查詢點是差異點。這樣遍歷算法的時間復(fù)雜度為O(i*j)。通過八叉樹(Octree)數(shù)據(jù)結(jié)構(gòu)實現(xiàn)了三維差異的快速提取。

如圖6所示，八叉樹結(jié)構(gòu)通過對三維空間的集合實體進行體元剖分，每個體元具有相同的時間和空間復(fù)雜度，通過循環(huán)遞歸的劃分方法對大小為2n×2n×2n的三維空間的幾何對象進行剖分，從而構(gòu)成一個具有根節(jié)點的方向圖。通過遞歸地比較模型點云構(gòu)建的Octree的樹結(jié)構(gòu)和掃描點云構(gòu)建的Octree結(jié)構(gòu)，可以對比得到不同的差異節(jié)點，通過記錄新增節(jié)點和缺少節(jié)點并記錄其對應(yīng)點云，從而實現(xiàn)檢測差異。

本文通過Octree節(jié)點預(yù)先得到存在差異點云的體素，再通過有差異點的體素及其周圍體素中的點云對標(biāo)準(zhǔn)模型點云進行近鄰搜索，得到最終的差異點云。Octree數(shù)據(jù)結(jié)構(gòu)示意圖如圖6所示。

圖6 Octree數(shù)據(jù)結(jié)構(gòu)示意圖

(1)設(shè)置距離閾值d_min，則Octree的最小子節(jié)點步長度為V=d_min，輸入模型點云M構(gòu)建Octree，輸入掃描點云S_dest構(gòu)建Octree；

(2)通過比對兩個Octree得到新增的Octree節(jié)點，提取新增節(jié)點及其鄰近節(jié)點處的點云。可以快速得到初步差異點云S_d_initia={s1″,…,sn″}，如圖7a所示；

(3)遍歷S_d_initia，查詢點sq″與在模型點云M上的最近點mq之間的距離為dq=distance(mq,sq″)，當(dāng)dq>d_min時認為當(dāng)前查詢點sq″是差異點，將該點加入到差異點集合S_d中。如圖7b～圖7d所示；

(4)輸出差異點云S_d，如圖7d所示。

通過上述計算，可以正確獲得需要提取的差異點云，差異提取步驟在CPU端中運行時間為0.15 s。使用CUDA加速后耗時在1 ms以內(nèi)。

(a) 初步差異點云S_d_initia (b) 差異點云S_d距離示意圖

(c) 最終差異點云S_d(紅) (d) 點云S_d細節(jié)圖7 差異點云提取

4 結(jié)束語

本文針對初始位姿不確定的平滑點云數(shù)據(jù)的差異提取問題進行了研究，利用曲面配準(zhǔn)，以及近鄰搜索等方法實現(xiàn)了三維差異檢測。而且針對算法運行速度問題，測試了SAC-IA與3D-Hough投票兩種點云的粗配準(zhǔn)方法，使用了Octree數(shù)據(jù)結(jié)構(gòu)實現(xiàn)了差異的快速定位以及K-D tree實現(xiàn)快速近鄰搜索，并利用了CUDA來加速程序。最終在本課題馬桶陶瓷素胚的曲面形狀差異檢測上，將點對誤差控制在0.5 mm以內(nèi)，運行時間在控制在1 s以內(nèi)，實現(xiàn)了快速精確的工件三維差異檢測與定位。