崔水軍++李榮

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

關(guān)鍵詞：點云 配準(zhǔn) 法向量特征

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

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

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

1 特征提取

法向量特征是利用目標(biāo)點p在半徑為r的鄰域內(nèi)的點構(gòu)建一個協(xié)方差矩陣，通過求取協(xié)方差矩陣的特征值和特征向量，取最小的特征值對應(yīng)的特征向量作為p點在該鄰域下的法向量。

在每一幅點云數(shù)據(jù)當(dāng)中特征點的數(shù)量只占很小的一部分，提取特征點后點的數(shù)量將大大減少，對于后續(xù)匹配點對的搜索、轉(zhuǎn)換矩陣的求解等操作將大大提高效率。因此，需要對待配準(zhǔn)的點云數(shù)據(jù)進行處理，獲得其特征點集。根據(jù)目標(biāo)點p的鄰域法向量設(shè)計一個關(guān)鍵點獲取方法。首先構(gòu)建目標(biāo)點及其鄰域內(nèi)點的協(xié)方差矩陣，即：

（1）

（2）

其中，k為目標(biāo)點p在半徑為r的鄰域內(nèi)點的數(shù)量；pi為鄰域內(nèi)的點；為該鄰域的質(zhì)心；λi為所構(gòu)建的協(xié)方差矩陣的特征值；υi為λi對應(yīng)的特征向量。以最小的特征值所對應(yīng)的特征向量為p點在該鄰域下的法向量n。

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

（3）

設(shè)待配準(zhǔn)的兩個點云數(shù)據(jù)分別為源點集P和目標(biāo)點集Q，利用上述特征點提取方法對兩點集中的特征點進行提取，構(gòu)成特征點集Pt和Qt。

2 拼接方法

2.1 匹配點對獲取

點的特征描述是尋找特征點、集中點的對應(yīng)關(guān)系的重要依據(jù)，豐富的幾何特征描述不僅可以提高特征點之間的區(qū)分度，同時也提高算法的穩(wěn)健性。該文設(shè)計3種幾何特征的描述方法，實現(xiàn)特征點集中的點的初始匹配。以點集Pt為例設(shè)計如下特征描述方法。

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

（4）

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

（5）

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

（6）

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

≤ （7）

≤ （8）

≤ （9）

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

2.2 精確拼接

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

（10）

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

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

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

（11）

（3）將得到的參數(shù)應(yīng)用于點集Ps。

（12）

（4）檢測結(jié)果是否滿足設(shè)定條件，不滿足則重復(fù)以上步驟，否則停止迭代。

3 實驗

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

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

4 結(jié)語

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

參考文獻

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

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

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