基于法向量特征的點云配準方法

崔水軍++李榮

摘 要：在工程實踐中，三維激光掃描技術越來越多地得到應用，在多站點三維激光掃描觀測時，不同站點間的點云配準是數據應用的關鍵。在不借助站點信息的情況下，根據點云數據中的法向量特征，通過搜索匹配點對，利用同名點對實現點云之間的自動配準。實驗表明自動配準的方式提高了點云配準的速度和精度，為點云數據的后續應用提供前提。

關鍵詞：點云 配準 法向量特征

中圖分類號：P258 文獻標識碼：A 文章編號：1674-098X（2017）01（c）-0134-03

三維激光點云數據的自動配準是解決多站點下對同一目標掃描所得的三維激光掃描數據的拼接問題。點云配準按是否有人工干預可分為手動配準和自動配準，手動配準效率較低其精度也不穩定，目前研究較多的是自動配準方法[1]。點云自動配準一般可概述為4個步驟：（1）匹配基元的選取；（2）相似性測度；（3）對應關系確定；（4）坐標轉換。在點云自動配準中，配準的關鍵在于匹配基元的選取，匹配基元反應的是點云的特征點或者屬性，它應該具有單一性、穩定性和可區分性。

目前點云自動配準算法研究中，用到的匹配基元有特殊點，如，角點、曲率最大點等；還有使用線特征或者面特征等[2]。這些方法有些過程需要人工干預或者最終精度不太理想。該文研究一種基于點云法向量特征的配準方法，該方法可實現點云的全自動配準，且配準結果具有較高的精度。

1 特征提取

法向量特征是利用目標點p在半徑為r的鄰域內的點構建一個協方差矩陣，通過求取協方差矩陣的特征值和特征向量，取最小的特征值對應的特征向量作為p點在該鄰域下的法向量。

在每一幅點云數據當中特征點的數量只占很小的一部分，提取特征點后點的數量將大大減少，對于后續匹配點對的搜索、轉換矩陣的求解等操作將大大提高效率。因此，需要對待配準的點云數據進行處理，獲得其特征點集。根據目標點p的鄰域法向量設計一個關鍵點獲取方法。首先構建目標點及其鄰域內點的協方差矩陣，即：

（1）

（2）

其中，k為目標點p在半徑為r的鄰域內點的數量；pi為鄰域內的點；為該鄰域的質心；λi為所構建的協方差矩陣的特征值；υi為λi對應的特征向量。以最小的特征值所對應的特征向量為p點在該鄰域下的法向量n。

計算點p在不同半徑r1、r2（r1≠r2）的鄰域下的方向量，然后根據方向量之間的夾角約束選擇。由于在不同的半徑下鄰域曲面的變化程度不同，因此兩個方向量之間必然存在角度偏差，且角度偏差越大，表示曲面變化越劇烈。通過計算兩個法向量之間的夾角余弦，并根據設定的閾值提取特征點，即：

（3）

設待配準的兩個點云數據分別為源點集P和目標點集Q，利用上述特征點提取方法對兩點集中的特征點進行提取，構成特征點集Pt和Qt。

2 拼接方法

2.1 匹配點對獲取

點的特征描述是尋找特征點、集中點的對應關系的重要依據，豐富的幾何特征描述不僅可以提高特征點之間的區分度，同時也提高算法的穩健性。該文設計3種幾何特征的描述方法，實現特征點集中的點的初始匹配。以點集Pt為例設計如下特征描述方法。

（1）以點集Pt中每個點pti的兩鄰域內法向量夾角的余弦值作為第一種特征量，記為：

（4）

（2）計算點集Pt中每一個點pti在源點集P中，以pti為原點r為半徑的球形鄰域內所有點的質心pti，以該點到其鄰域質心的距離作為第二種特征量，記為：

（5）

（3）以點集Pt中每個點pti與該點鄰域質心之間連線和其法向量ni的夾角余弦作為第三種特征量，記為：

（6）

對于特征點集Pt中的每個點pti，根據3個特征量搜索其在特征點集Qt中的對應點。設置如下3個條件，當兩點滿足這3個條件時，則將其判定為同名點，即：

≤ （7）

≤ （8）

≤ （9）

通過上述3個條件可以初步確定特征點之間的對應關系，構建對應點集。但是由于點云本身存在一些相似區域，因此不可避免地存在一對多的對應關系，為了提高配準的精度和效率需要將錯誤的對應關系剔除。該文利用RANSAC算法剔除錯誤對應關系，具體過程為，首先從得到的對應關系集M中隨機抽取一個大小為n（n≥3）的樣本子集S，根據樣本S求出一個參數模型（在此參數模型指源點集和目標點集之間的轉換矩陣）；然后用該模型去測試總樣本集中所有的對應關系，如果其中源點和目標點經模型變換后的距離偏差小于設定閾值，則認為該對應關系屬于模型內樣本，如果有足夠多的對應關系歸類為模型內樣本，那么估計的模型就足夠合理；再用所得到的模型內樣本重新估計模型；最后通過模型內樣本和模型的錯誤率來評估模型。重復執行以上步驟，每次產生的模型要么因為局內點太少而被舍棄，要么因為比現有的模型更好而被選用。直到迭代次數達到設定值則迭代結束，最后得到的模型內的對應關系則是剔除錯誤后的對應關系。

2.2 精確拼接

在獲得初始匹配參數后就可以對點云進行初始拼接，拼接后的點云已具有滿足ICP算法對初始位置接近的要求。傳統的ICP算法主要是對配準的點云數據使用最小二乘算法進行迭代計算，最后使得拼接誤差滿足要求為止。在選取最近點時，直接選取兩點云中歐式距離最近的兩個點作為最近點，這樣做的后果是一旦出現錯配點則會導致迭代計算不收斂的情況[3]。該文選用改進ICP算法的做法是在選取最近點時，對于點云P中選取的任意一點，先求出在另一點云Q中與其歐式距離最近的4個點，然后計算這4個點構成的鄰域空間的重心，將重心點作為與點云P中所選取點的最近點。例如點集Pt中任意一個點Pti，其在點集Qt中歐式距離最近的4點qt1、qt2、qt3、qt4，這4點所構成的四面體中心qi為：

（10）

改進ICP算法的基本步驟如下。

（1）求取匹配點集Pt上每一點在中的歐氏距離最近的4個點，并計算這四點所構建的四面體的重心。

（2）運用最小二乘法計算配準參數，其中平移矩陣為Rs+1和Ts+1旋轉矩陣為，第ds和ds+1表示第S和s+1次迭代后得到的配準參數。

（11）

（3）將得到的參數應用于點集Ps。

（12）

（4）檢測結果是否滿足設定條件，不滿足則重復以上步驟，否則停止迭代。

3 實驗

該文在Visual Studio 2013平臺上，利用OpenGL函數庫實現算法和顯示界面。實驗采用數據為斯坦福大學的Bunny數據，Bunny數據是包含10個視角的點云數據，如圖1所示，在數據中抽取0°和45°視角的兩個點云數據進行初始配準和精確配準。

圖2所示為0°Bunny數據和45°Bunny數據的配準結果，圖2為利用兩點云的法向量特征進行初始配準的結果，可以看出兩點云的初始配準位置比較精確，可以滿足ICP配準算法的初始位置要求。圖3為兩點云精確配準后的結果，可以看到邊角的分叉消除，兩點云完全重合在一起。

4 結語

該文主要對點云數據的配準技術進行研究。給出了一種基于法向量特征的點云數據自動配準方法。該方法不需要附加任何關于儀器的位置或角度信息，也不需要人工選取特征點，僅利用點云數據自身所具有的幾何信息進行匹配。通過構造特征點局部區域的法向量特征獲得兩點云數據的特征點集合，根據剛體變換下的不變量特點，引入角度約束和距離約束等匹配約束，獲得兩特征點集中的匹配點對與初始配準參數。最后利用鄰域空間的重心作為最近點參與ICP算法的迭代運行，避免了當出現錯配點時則迭代計算不收斂的情況，有效地提高了ICP算法的穩定性。通過實驗證明該方法具有有效性和精確性。

參考文獻

[1] 姜如波.基于三維激光掃描技術的建筑物模型重建[J].測繪通報，2013（S）：80-83.

[2] 鄧非，張祖勛，張劍清，等.一種激光掃描數據與數碼照片的配準方法[J].武漢大學學報：信息科學版，2007，32（4）：290-292，296.

[3] 戴靜蘭，陳志楊，葉修梓.ICP算法在點云配準中的應用[J].中國圖象圖形學報，2007（3）：517-521.