基于法向量特征的點(diǎn)云配準(zhǔn)方法

崔水軍++李榮

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

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

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

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

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

1 特征提取

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

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

（1）

（2）

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

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

（3）

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

2 拼接方法

2.1 匹配點(diǎn)對(duì)獲取

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

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

（4）

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

（5）

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

（6）

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

≤ （7）

≤ （8）

≤ （9）

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

2.2 精確拼接

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

（10）

改進(jìn)ICP算法的基本步驟如下。

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

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

（11）

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

（12）

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

3 實(shí)驗(yàn)

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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