基于特征提取的點云自動配準優化研究

楊高朝

YANG Gaozhao

國家測繪地理信息局 海南基礎地理信息中心，海口 570203

Hainan Geomatics Center,National Administration of Surveying,Mapping and Geoinformation,Haikou 570203,China

1 引言

地面三維激光掃描技術在測繪領域的應用越來越廣泛[1-4]，打破了傳統測量數據獲取與處理模式，推動了點云數據處理理論的發展。由于受到測量設備和環境的限制，物體表面完整數據的獲得往往需要通過多站掃描才能完成。因此，為了得到物體完整的點云數據，需要對這些局部點云數據進行坐標轉換，最終拼接到同一個坐標系里。商業中應用最廣泛最成熟的方法就是通過在重建物體上貼標志點[5]來實現點集的配準，但有些文物古跡的恢復和逆向工程存在無法貼標簽甚至無法接觸的問題，因此研究點云自動配準算法不但具備重要的實用價值，還具有重要的商業價值。

目前，許多國內外學者提出了多種點云配準算法。到20世紀90年代中后期比較流行的基于幾何特征的匹配算法，如幾何Hush[6]算法、Spine image等，其中最常見的就是基于迭代最近點（Iterative Closest Point，ICP）的方法[7]。但ICP算法可能存在局部最優缺陷，如果兩站點云沒有較高的重疊度或沒有很好的初姿，很可能陷入局部最優，最后得到錯誤的匹配結果。Blais等對點云進行隨機采樣以提高速度，算法精度受到影響。Okatani提出了通過考慮平移和旋轉錯位的特性來獲得最佳矩陣的方法，該方法易陷入局部收斂。朱延娟等[8]提出了基于點云曲率和鄰域曲率相似度的粗配準。張廣鵬等[9]提出了主元素貼合法的全局配準。劉艷豐[10]提出了基于四點算法的全局配準。

本文在總結分析國內外學者專家理論研究的基礎上，針對上述點云數據配準中所存在的問題，從研究初始匹配入手，結合改進的ICP算法，設計出一種利用點云法向量夾角變化度及特征曲率相結合的自動配準方法。

2 自動配準的主要流程

點云自動配準一般分兩個過程：粗配準、精配準[11-14]。粗配準是通過特征提取[15]、信號濾波等手段，來獲得不同視角數據集間相對應的控制點，從而估計出配準變換參數。精確配準采用迭代方式逐漸逼近最佳結果，由于迭代方式不能保證得到最佳收斂結果，精確配準需要粗配準為其提供一個迭代的起始位置，來增大收斂到最佳結果的概率。具體步驟如圖1。

圖1 點云配準流程圖

首先P、Q兩站點云有一定的重疊度[16]（一般特征比較明顯的點云超過60%即可得到正確的配準結果），根據每個點云的法矢量大小重采樣點云，為每個點云定義一個N維向量，向量值為點云與鄰近點云的法向量夾角。然后根據這些法向量夾角進行對應點搜索，進行粗配準，再進行精匹配，求取轉換參數。具體詳細步驟見下文。

2.1 粗配準

為了縮小點云之間的旋轉和平移錯位，使得精確配準不致得到錯誤的結果，需要進行點云粗配準。在研究上述算法的基礎上，提出了法向量鄰域夾角搜索的粗配準算法。首先對每個點構造一個不變特征向量，即每個點的法向量與其K-近鄰點法向量[17]的夾角組成的向量，以此向量作為輸入量構建k[θ1,θ2,…,θk]T，其中θk為弧度值，在兩點集中搜索最近點。法向量夾角如圖2、圖3。

圖2 模型點云法向量夾角

圖3 目標點云法向量夾角

在計算法向量夾角的過程中，法向量的估計是比較重要的一步。由于采集到的原始數據往往很龐大，為了加快速度，先對原始數據進行點云抽希[18]，然后采用基于局部表面擬合的方法進行法向量估計[19]（為了使配準速度更快，本文選擇平面擬合方案，但曲面擬合可能效果更優，但費時較多）。為此，對于點云中的每個掃描點pi，搜索與其最相近的K個相鄰點，然后計算這些點最小二乘意義上的局部平面P，此平面可以表述如下：

式中，n為平面P的法向量；d為P到坐標原點的距離。

計算該點與最近點的法向量夾角余弦值，如圖2和圖3所示。當法向量夾角值越大時，余弦值就越小，說明該點所在區域起伏變化較大，特征較為明顯，反之則較為平坦。因為平坦部分的點的幾何特征較為接近，不適合作為特征點集進行配準，所以選取適當的閾值ε=0.99（經過實驗求得），保留法向量夾角余弦值小于ε的點。

設待配準的兩個點云數據分別為P和Q，利用上述特征點的提取方法，分別對兩個點云進行特征點提取，得到P的特征點集為Q的特征點集為，其中m和n分別為P和Q的特征點的個數。

2.2 獲取匹配點對

2.2.1 對應點對的初步獲取

幾何特征信息種類越多，計算就越復雜，但是特征信息量少，特征識別度低，就很難收斂。經過多種特征點云的實驗，最終決定選取兩種基本幾何特征搜索匹配點[20]。下面詳細介紹點云幾何特征的建立過程。

（1）對于點集Pt中的每個點pti，以該點鄰域法向量夾角加權值k[θ1,θ2,…,θk]T的特征距離作為該點的特征量：

（2）對于點集Pt中的每個點pti，利用鄰域點集中k個最近點，求出鄰域的重心O(pti)，以該點到其鄰域重心的距離值作為該點的特征量：

對于點集Pt中的每個點pti，為其在點集Qt中搜索對應點qtj，若qtj是pti的對應點或近似對應點，則對兩點來說，以上提出的兩種幾何特征應該相同或近似相同。因此對于點集Pt中的一點pti和點集Qt中的一點qtj，只要滿足以下4個條件則認為它們具有對應關系：

閾值ε1、ε2取值過大，會導致產生很多錯誤的匹配點對，取值過小，無法獲取足夠的匹配點對，根據其他學者的經驗以及本人反復試驗，式中取ε1=ε2=0.01，使用以上關系進行過濾并初步建立點對應關系。由于點云中本身就存在很多特征相似區域，使用多個特征關系進行對應點的建立可以很好地避免出現大量一對多的情形，再通過合理閾值的選擇可以為點集Pt中的每個點pti初步找到其在Qt上的對應點。最后建立初始匹配點對數組并記為：

式中，N為匹配點對的數量。

2.2.2 錯誤對應點對的剔除

采用上述方法確立的對應點集中會存在錯誤對應點對（或稱為不可靠、不兼容點對），或者會產生多對互相矛盾的點對。為此，必須引入評價標準或約束準則去除錯誤對應點對，這是許多ICP改進算法的關鍵，也是國內外諸多學者研究的重點。區別于深度圖像可利用圖像自身的灰度、顏色、紋理等輔助信息[21-23]，對于點云，能夠利用的信息主要是點云自身的曲面幾何特征。

如果以上獲取的初始匹配點對都是正確匹配點對，依據幾何剛性變換原理可知，對于任意兩對匹配點對和應滿足點對間距離的偏差在極小的允許范圍之內，即可表示選取閾值ε=0.02，對每個點對計算P中除其以外與其符合剛性距離約束條件的點的數目Qi，若P中一個點對滿足：

2.2.3 匹配點對搜索精度檢驗

為了檢驗匹配點搜索精度，引入度量ε5：

2.2.4 計算初始匹配參數

在求得目標點集P和Q匹配點對后，需要計算兩點云之間的平移變換矩陣，比較典型的方法有最小二乘法、四元數法[24]、矩陣的奇異值分解法（SVD）[25]等。經過對比發現，最小二乘法求解收斂速度更快。根據旋轉矩陣和平移向量對目標點云進行初步轉換。

2.3 精配準

2.3.1 改進后的ICP算法

進行初始配準后，兩站點云的初始姿態基本上接近，可以作為ICP算法的初值進行精匹配。

根據經典的ICP算法，本文在以下方面對ICP算法進行改進，以提高算法的效率：

（1）使用基于法向夾角的點云重采樣[26]；

（2）應用法向投影選取對應點，該搜索過程中使用kd-tree或八叉樹可以提高速度；

（3）權重設置選取距離的平方加權平均值；

（4）誤匹配點剔除選取距離和法向夾角相兼容的原則；

（5）目標函數選取點到面的誤差最小。

法向投影-鄰域搜索將源數據投影到目標點云上，然后在目標點云上進行最近點搜索（點周圍的幾何特征信息也作為判斷的標準如曲率等）。

誤差準則函數選擇：

（1）如圖4，對應點對直接距離的平方和最小[27]，這一形式是最常用的誤差準則。

其中，pi是目標點云的坐標向量；qki是模型點云的坐標向量；R是變換矩陣；t是平移矩陣；ε是對應點對直接距離的平方和。當ε達到極值最小時，此時的R和t就是要求的值。

圖4 最近點搜索算法

（2）如圖5，每個源數據點到以其對應點法向量建立的局部平面的距離平方和最小。

其中，ni是pi的法向量。其他變量的含義同上。表示R?qki+t投影到pi點的切平面的距離的平方。采用此目標函數，只要兩個點在與切平面平行的方向上滑動，距離都不變，因此在優化過程中允許滑動，這是此目標函數獲得較快收斂速度的直觀原因。

圖5 法向量垂直搜索算法

根據圖6實驗結果，可知第二種方案無論是收斂速度上還是精度上都優于第一種方案，本文選取第二種方案作為誤差準則函數。

圖6 精配準誤差圖（比較點到點與點到面的差別）

2.3.2 精匹配實現步驟

運用改進的ICP算法進行精細配準步驟如下：

步驟1構造參與算法的兩個初始點集，分別記作P和X；設定閾值Δ＞0，把點云的特征加入到配準策略上來，比如點云的曲率、法向量夾角等。

步驟2初始化p0=p,k=0。

步驟4計算Rk和Tk,使

最小，ni是目標點云的法向量。

步驟5對p0進行三維變換，得到pk+1=Rkp0+Tk。

步驟6k=k+1,如果k=1,轉到步驟3；如果k≥2,且則終止迭代并轉到步驟7，否則轉到步驟3。

步驟7最后所得到的Rk、Tk即為所要求的精細配準參數，利用所得的參數，對第一片點云進行轉換，配準結束。

2.3.3 誤差評定

為了評價點云自動匹配的精度，由文獻[28]可得：

其中，mp為配準中誤差；pi、p′i為公共點對轉換前后向量值。

3 實驗及結果分析

在Windows平臺下利用MFC和OpenGL軟件實現了算法和配準界面，如圖7。采用MFC單文檔結構，利用分割視圖法，管理3個視圖。第二個視圖顯示model（模型）點集，第三個是data（目標）點集，然后點擊菜單打開配準窗口，可在第一個視圖同時顯示模型點集、目標點集和配準后的點集。提供手動配準，自動配準，Mesh（或點云）旋轉平移、點云刪除、重選、縮放以及點云數據簡化等功能。

圖7 基于MFC和OpenGL實現的配準軟件

3.1 實驗結果

為了驗證算法的有效性，本實驗利用網上下載的不同視角的兩片點云，點云個數29876個。首先對點云進行壓縮，保留一些特征比較明顯的點，壓縮后的點云為7652個，如圖8所示。接著對兩站點云進行粗配準，結果如圖9（a），最后再對點云進行精匹配，結果如圖9（b），配準結束后還可以查看本次實現的配準精度以及配準所花費的時間。為了更能顯示本文方案的可用性，選取一個現今比較成熟的方案，應用同樣的數據同時實驗，以便和本文方案進行比較。經過對比，選取了文獻[20]配準算法對掃描點云進行迭代配準，其配準效果如圖10所示。為更形象地查看迭代過程及結果，根據每次迭代的殘差，結合MATLAB生成線狀圖，如圖11。

圖8 兩組點云初始位置

圖9 本文配準效果

圖10 文獻[20]配準效果

圖11 文獻[20]和本文算法迭代配準誤差圖

為了更直觀地分析問題，對本次實驗進行統計，如表1。

表1 本文算法和文獻[20]算法的比較

3.2 結果分析

為了定量比較上述兩組實驗結果，通過計算多視點云重疊區域的最鄰近點對距離平方和的平均值的平方根，作為整體配準后的距離中誤差，用于評估多視點云間的配準精度，同樣的數據運用式（12）求得本文算法配準后的中誤差為30.4 μm,文獻[20]配準后的中誤差為38.7 μm。已知原始點云的密度為0.15 mm，實驗表明，本文算法要優于文獻[20]的算法。另外從實驗結果還可以看出，本文算法配準中誤差近似為0.3倍點云密度，因此本文配準算法的精度比較理想。

在算法迭代收斂方面，使用本文算法進行配準共迭代9次滿足平差終止條件。其中3個平移參數的改正數收斂較快，3次迭代時已收斂；3個旋轉角參數的改正數迭代后期收斂相對較慢，第5次迭代時3個旋轉角參數的改正數絕對值都小于6×10-5，而本文中設定的限差為4×10-5，直到第9次滿足限差要求，迭代結束。使用文獻[20]算法同樣對兩站點云進行配準，一直迭代13次才滿足迭代終止條件，從收斂效率上可以看出，本文算法要優于文獻[20]的算法。

在算法運行速度方面，本文方案粗配準和精配準一共用了6.04 s，文獻[20]一共用了8.09 s。由于本文方案盡管使用的是基于點云特征的配準方法，但并沒有直接計算擬合曲面曲率，直接通過法向量夾角作為三維點云剛體不變的特征來實現自動配準。因此和傳統利用點云擬合曲率實現點云自動配準的方案相比，本文方案提高了運行速度。

綜上所述，本文算法無論是從配準精度上還是從迭代效率上都優于文獻[20]。實驗配準效果圖和實驗獲得的對比充分說明了本文算法的有效性。

4 結論與展望

本文將利用鄰域法向夾角搜索進行的初始配準作為初始值，并利用改進的ICP算法對提供的初始值進行精配準。實驗結果表明，改進后的ICP算法在對應點的搜索時間和配準精度等方面都優于經典的ICP算法，既解決了傳統的ICP算法進行配準，算法陷入局部最小，從而得到錯誤的配準結果的問題，又提高了點云配準的效率。點云中本身就存在很多特征相似區域，單一的特征匹配識別度低，在實驗中發現，很多特征較少的點云也會陷入局部收斂，但采用多個幾何特征來搜索對應點所花費的時間也會相應增加。因此，如何在兩者間找到一個平衡點并在實際生產中廣泛應用是接下來需要解決的問題。