一種基于特征提取和匹配的點云自動配準算法

摘 要：針對三維激光點云數據配準問題，提出一種基于特征提取和匹配的點云自動配準算法。算法依據點云中每個點的鄰域點集到該點切平面的平均距離信息來提取特征點。利用點云中四種基本幾何特征形成特征描述算子，根據特征描述算子的相似性初步搜索匹配點對，然后采用距離約束條件得到精確的匹配點對集合，運用四元數算法計算初始配準參數，最后通過改進的迭代最近點（ICP）算法對點云進行精確配準。實驗結果證明了該算法的有效性和可行性。

關鍵詞：點云配準；距離約束；特征提取；最近點迭代

三維激光掃描技術作為一種目前新興的空間信息獲取技術，已經廣泛應用于文物古跡保護、建筑、數字城市、土木工程、礦山監測等領域，通過對三維激光掃描儀所獲得的多個視角掃描得到的點云數據進行坐標轉換，最終拼接到同一個坐標系里[1-2]，這即是點云的配準問題。目前，很多國內外專家學者提出了多種點云配準方法，其中最為常見并且應用最為普遍的是迭代最近點（ICP）算法。但ICP算法有其自身的缺陷：首先兩片點云之間必須是包含與被包含的關系，其次兩片點云必須具有良好的初始位置，否則可能會陷入局部最優，得到錯誤的配準結果。針對ICP算法的局限性，國內外很多學者提出采用兩階段配準方法，首先對點云進行初始配準獲得良好的初值，然后再采用改進的迭代最近點算法[3-4]進行精確配準。文獻[5]通過計算點云中各點的法向量和曲率，利用幾何哈希方法找出匹配點對進行初始配準；盧章平等[6]提出了一種基于共面4點集的RANSAC初始配準算法； 利用點的法向量與其鄰近點的法向量的點積來描述點的特征并形成特征描述算子，進行初始配準。

1 算法介紹

文章利用點云法向量幾何信息研究點云自動配準算法。計算點云法向量并進行方向一致化。根據各點的法向量獲得每個點的切平面，利用每個點的鄰域點集到切平面的距離來判斷該點是否為特征點，得到特征點集，然后對特征點集中的每個點基于四種幾何特征的點云描述算子，根據點云描述算子的相似性，得到初始匹配點對，然后再采用距離約束條件得到精確匹配點對，采用四元數方法計算初始配準參數，精確配準方面，采用改進的ICP算法提高了算法配準精度。實驗采用經典兔子數據，得到了比較理想的效果。

2 初始配準

2.1 提取特征點

對于待配準的兩片點云，如果對整個點云搜索匹配點對，將會消耗大量的時間，同時也會出現大量錯誤匹配點對，為了快速精確的配準，需要對點云進行預處理，獲得特征點集。通過對點的切平面觀察很容易發現，如果點云局部區域鄰域點集到切平面的距離較小時，說明該區域比較平坦，特征性不明顯；相反，如果鄰域點集到切平面的距離較大則表明該區域起伏變化較大，特征性較為明顯。

根據以上觀察，定義點云中某一點Pi處其K-鄰域內點到該點切平面的平均距離即特征距離gi作為判定Pi點是否為特征點的依據。計算公式為：

（1）

式中dij指點Pi鄰域某點到Pi點切平面的距離，gi為點Pi的鄰域點到Pi點切平面的平均距離。

根據該定義，特征距離越大的點表示該區域起伏變化大，因此可利用此特征距離來提取點云中的特征點。選擇適當的閾值？滓1，去掉點云中較為平坦的點，保留gi>？滓1的點，對于保留的點中任意一個點Pn，若其滿足

則將Pn作為特征點，其中g（Pn1），g（Pn2），…，g（Pnk）為點Pn的k-鄰近點的特征距離，假設兩片點云分別為P和Q，其中P為目標點集，Q為參考點集，利用文章提出的點云特征提取方法，分別對兩片點云進行特征提取，得到P的特征點集為Pt={Pt1，Pt2，…Ptm'}，Q的特征點集為Qt={qt1，qt2，…qtn'}，其中m'和n'分別為P和Q的特征點個數。本實驗采用經典的斯坦福大學兔子點云數據，提取的特征點如圖1所示。

2.2 尋找匹配點對

2.2.1 初步獲取匹配點對

文章選擇四種基本幾何特征作為特征描述算子，初步搜索特征點集中的匹配點對。采用多種幾何特征信息不僅可以更加細致精確的描述鄰域特征信息，同時也可以避免大量錯誤匹配點對的出現，以目標點集Pt為例，四種幾何特征描述如下：

（1）根據點集Pt中的每一個點Pti，以其K-鄰近點的特征距離作為第一種特征量，公式如下

f1（Pti）=g（Pti） （3）

（2）根據點集Pt中的每一個點Pti，計算該點的k-鄰近點重心O（Pti），以該點與其K鄰近點重心O（Pti）之間的距離值作為第二種特征量，公式入下

f2（Pti）=Pti-O（Pti） （4）

（3）根據點集Pt中的每一個點Pti，計算該點法向量的變化程度即該點法向量與K-鄰近點法向量之間夾角余弦的算術平均值作為第三種特征量，公式如下

（5）

其中cos（？茲ij）為點Pti的法向量與其鄰近點Pti法向量的夾角的余弦值。

（4）根據點集Pt中的每一個點Pti，以該點法向量 ni和該點與其K-鄰近點重心之間連線的夾角余弦值作為該點的第四種特征量，公式如下

（6）

通過以上四種特征量的求解，我們得到Pti和qti的特征向量，最后分別得到Pt和Qt的特征向量點集L1和L2，對于點集Pt中每一個點，在點集Qt中搜索其匹配點，如果Pti與qti是匹配點對，那么它們會有相同或者相似的幾何特征，特征向量也應該是相同或者相似的。特征點的相似性，采用特征向量間的歐氏距離作為比較準則，對于點集Pt中的Pti點與點集Qt中的一點qti同時滿足以下四個條件則認為他們是一對匹配點對，四個條件分別是：