基于點對特征的三維點云匹配算法*

易 杰， 李 蹊， 易輝成， 劉 苗， 鐘 凱， 胡 興

(1.湖南工業職業技術學院，湖南 長沙 410208；2.華中科技大學 材料成形與模具技術國家重點實驗室，湖北 武漢 430074；3.湖南航天天麓新材料檢測有限責任公司，湖南 長沙 410600)

0 引 言

三維物體識別旨在實現三維場景中目標物體的檢測及定位，在工農業已得到了廣泛的應用[1]。目前，三維物體識別方法主要有兩大類：基于全局特征的識別方法[2]和基于局部特征的識別方法[3]。全局特征識別方法需要從場景中將待檢測的物體分割出來，然后將該物體與要搜索的目標物體表面的全部或最顯著的幾何特征進行對比，從而把場景中的目標物體識別出來；而局部方法則是由局部信息來識別整體，只需要從場景中提取出關鍵點、面片等局部特征并與要搜索的目標物體進行比對就可以把場景中的目標物體識別出來。兩類方法各有特點，但在有遮擋和混疊的場景中識別效果均不理想。

在全局特征識別方法方面，Rabbani T[4]等人使用廣義霍夫變換的變體來識別物體，由于恢復三維姿態計算量巨大，該方法僅適用于立方體、球體等形狀簡單的物體；Park I K[5]通過對物體的模式進行比對從而識別出場景中的目標物體，該方法的計算量較大，需采用GPU進行加速。

在局部特征識別方法方面，Chua C[6]等人提出了一種基于點簽名的三維物體識別方法，將點簽名作為匹配依據從而識別出場景中的目標物體，該方法對噪聲比較敏感，且易出現誤匹配；Rusu R B[7]等人提出了一種基于點特征直方圖的三維物體識別方法，通過比對直方圖上的統計信息從而把場景中的目標物體識別出來，但該方法同樣存在計算量大、識別速度較慢的問題。

為了保證三維物體在有遮擋和混疊場景中的識別效果，本文提出一種基于點對特征的三維點云匹配算法，此算法融合基于點對特征的全局模型描述和基于快速投票方案的局部曲面匹配方法，無需對場景進行分割，對遮擋和混疊具有良好的適應性。

1 基于點對特征的全局模型描述構建

點對特征[8]可以用來描述兩個點的相對位置以及法線方向。對于任意兩個點m1,m2以及它們各自的法矢量n1,n2，令差矢量d=m2-m1，并且定義特征F為

F(m1,m2)=(‖d‖2,∠(n1,d),∠(n2,d),

∠(n1,n2))

(1)

點對特征F的4個分量如圖1所示。

圖1 點對特征

全局模型描述表示從點對特征空間到模型的映射，具體來說是把四維點對特征映射到具有相似特征向量的點對(mi,mj)∈M2上。圖2顯示了全局模型描述構建的過程，具有相似特征的模型點對會被存儲在哈希表的同一個槽中，場景特征Fs(sτ,si)作為哈希表的鑰匙可以把與它相似的所有模型特征Fm(mi,mj)在一定的時間內搜索出來。

圖2 全局模型描述

2 基于快速投票方案的局部曲面匹配

2.1 基于投票方案的目標姿態生成

對于場景上的任意一個參考點sτ∈S，如果該參考點處在要檢測的目標物體之上，則一定會存在一個來自模型上的點mτ∈M與之對應。只要將這兩個點以及其法線對齊，再圍繞場景參考點sτ的法線旋轉一定的角度即可讓模型和場景對齊，從而生成目標物體的姿態。模型到場景的剛性變換由模型上的一個參考點mτ和一個旋轉角α來表示，(mτ,α)即為模型相對于場景參考點sτ的局部坐標為

(2)

圖3為投票方案的具體過程：1)把場景參考點sτ和場景中的任意其它點si組成點對，并計算特征向量Fs(sτ,si)；2)將具有相似特征向量的模型點對(mτ,mi)∈M2存儲在哈希表的同一個槽中，并把場景點對的特征向量Fs(sτ,si)作為哈希表的鑰匙對哈希表進行檢索，返回具有相似特征向量的模型點對；3)對于上述返回的每一個模型點對，通過求解式(2)計算旋轉角α；4)旋轉角α計算出來之后，在二維累加器上給局部坐標(mτ,α)投上一票。

圖3 投票方案流程

上述過程都完成后，投票數最高的局部坐標即為最優局部坐標。一般來說，最優局部坐標對應的姿態就是目標物體在場景中的真實姿態，但出于穩定性的考慮，那些投票數較高的局部坐標也在本文作者考慮范圍之內。

2.2 基于聚類和迭代最近點的目標姿態優化

采樣生成的目標姿態并不完全等于目標物體在場景中的真實姿態，需要通過聚類來提高目標姿態的準確性。

姿態聚類即把平移和旋轉的差異都不超過設定閾值的姿態聚在一起，然后再對這些姿態取平均值作為最終的姿態。聚類的投票數為該聚類中所有姿態投票數的總和，對投票數最高的聚類中的姿態求平均值就可以得到最終的姿態。同上一節，出于穩定性的考慮，那些投票數較高的聚類也在本文考慮范圍之內。

經過聚類之后，目標姿態的準確性得到了提高，但與真實的姿態相比仍然存在一些差距，需要通過迭代最近點(ICP)對目標姿態做進一步的優化，即實現目標姿態點云和場景點云的配準。

2.3 基于Kd-Tree算法的目標姿態篩選

由于投票數較高的姿態都有可能是目標物體在場景中真實的姿態，因此需要對這些姿態進行篩選，從而把真實的目標姿態判斷出來?？紤]到真實的目標姿態點云與場景點云部分重合，即匹配點數目較多；而虛假的目標姿態點云則相反。因此，利用Kd-Tree最近鄰搜索統計目標姿態點云與場景點云匹配點的個數，當大于某一閾值時就可以認為該姿態是真實的姿態。值得注意的是，這里提到的匹配點指的是相對距離以及法線夾角都比較小的點對。

Kd-Tree有半徑查詢以及K近鄰查詢兩種查詢方式，下面以半徑查詢為例對目標姿態篩選算法的流程進行介紹。距離閾值表示為DistanceThreshold，法線夾角的閾值表示為AngleThreshold，匹配點數目的閾值表示為NumThreshold。

基于Kd-Tree的目標姿態篩選算法的具體實現步驟如下：

1)讀取目標姿態點云Ptarget和場景點云Pscene；

2)將Ptarget中的任意一個點pi作為查詢點，Pscene作為被查詢的對象；

3)在Pscene中找出滿足‖dist(pi,si)‖2

5)遍歷Ptarget上的點，統計匹配點的總數，記為num,判斷num≥NumThreshold是否成立，若成立，則該姿態是目標物體在場景中真實的姿態。

3 實驗驗證

本文采用華中科技大學快速制造中心研發的PowerScan面結構光三維測量設備獲取點云數據進行實驗驗證。所用設備由2個工業相機和1個數字光柵投影儀組成，單次測量范圍為500 mm×400 mm，單次測量誤差為±0.03 mm。

3.1 實驗方案設計

設計了無遮擋和混疊以及有遮擋和混疊兩類場景進行對比。目標物體選為三通管，如圖4所示。

圖4 三通管

3.2 實驗結果與分析

本文算法的識別效果如圖5所示。

圖5 識別效果

對于不同復雜程度的場景，本文算法的識別率和識別時間如表1所示。

表1 不同場景的識別率和識別時間

表1可知，本文算法在無遮擋和混疊的場景中識別率很高，在有遮擋和混疊的場景中識別率略有降低，但依然處在一個較高的水平；此外，本文算法的識別時間均小于4 s，識別速度較快，如果不通過ICP進行配準那么識別時間均小于1 s，識別速度就很快。

綜上，本文的算法在有遮擋和混疊的場景中識別效果較為理想，具備一定的抗遮擋和混疊性能。

4 結 論

提出了一種基于點對特征的三維點云匹配算法。該算法融合了基于點對特征的全局模型描述和基于快速投票方案的局部曲面匹配方法，從而有效規避了全局方法和局部方法各自的不足。實驗結果表明，所提算法對于有遮擋和混疊的場景識別效果較為理想。