基于迭代最小二乘的點(diǎn)云法向量估計(jì)方法

馬學(xué)磊,薛河儒

(內(nèi)蒙古農(nóng)業(yè)大學(xué),內(nèi)蒙古 呼和浩特 010018)

1 引言

點(diǎn)云法向量的計(jì)算是點(diǎn)云數(shù)據(jù)處理中的重要環(huán)節(jié)。許多曲面重建算法需要精確的法向量信息才能生成高質(zhì)量曲面。法向量估計(jì)可以應(yīng)用在很多場合,如點(diǎn)云分割、點(diǎn)云精簡、模型建模、特征檢測和提取等。點(diǎn)云法向量可通過分析鄰域點(diǎn)集的幾何結(jié)構(gòu)近似獲取。目前,常用的點(diǎn)云法向量估計(jì)方法有兩種。

第一種方法利用待估計(jì)點(diǎn)的鄰域點(diǎn)集計(jì)算法向量。Hoppe等利用局部鄰域擬合平面的方法估計(jì)法向量[1]。這種方法計(jì)算速度快,而且對(duì)光滑曲面性能較好。然而對(duì)于分片光滑的曲面,在細(xì)節(jié)特征處法向量估計(jì)結(jié)果不準(zhǔn)確。Guennebaud等和Cazals等在回歸中使用二次曲面或球體代替平面。然而球體和二次曲面仍然是光滑曲面,這些方法在尖銳特征處估計(jì)效果不理想[2,3]。Pauly等在平面擬合過程中對(duì)鄰域點(diǎn)賦予高斯權(quán),以達(dá)到削弱某些點(diǎn)在平面擬合中的作用[4]。Niloy等提出一種方法自適應(yīng)改變鄰域大小,然而該方法對(duì)位于特征線上或接近特征線上的點(diǎn)會(huì)產(chǎn)生各向異性的鄰域集[5]。上述方法均在以待估計(jì)點(diǎn)為中心的鄰域集上做回歸以實(shí)現(xiàn)法向量估計(jì)。當(dāng)待估計(jì)點(diǎn)位于邊緣或尖銳特征區(qū)域,以上方法的法向量估計(jì)結(jié)果不準(zhǔn)確。近年來,許多學(xué)者提出了特征保持的法向量估計(jì)方法。Huang等人提出了一種將點(diǎn)云重采樣和法向量估計(jì)相結(jié)合的方法[6]。它能夠?qū)哂性肼暫彤惓Ｖ档狞c(diǎn)云模型準(zhǔn)確地估計(jì)法向量。然而,這種方法的輸出為新的合并點(diǎn)云,原始點(diǎn)云的法向量并沒有被計(jì)算。通過基于核密度估計(jì)的方法最大化目標(biāo)函數(shù),Li等人減少了位于不同表面上的鄰域點(diǎn)的影響[7]。它僅對(duì)采樣均勻的點(diǎn)云數(shù)據(jù)會(huì)產(chǎn)生較好的法線估計(jì)結(jié)果。

第二種方法利用Voronoi圖計(jì)算點(diǎn)云法向量。Amenta 等提出在每個(gè)點(diǎn)的Voronoi晶格中,利用每個(gè)點(diǎn)與離其最遠(yuǎn)的Voronoi頂點(diǎn)的連線方向估計(jì)點(diǎn)云法向量[8]。QuYang等對(duì)每個(gè)點(diǎn)找到其局部Voronoi鄰域,通過對(duì)這些鄰域點(diǎn)構(gòu)建二次曲面估計(jì)點(diǎn)云法向量[9]。以上兩種方法的缺點(diǎn)是當(dāng)點(diǎn)云噪聲率較高時(shí),法向量估計(jì)結(jié)果不準(zhǔn)確。Alliez等人提出了一種更加穩(wěn)定的法向量估計(jì)方法,該方法結(jié)合了PCA和Voronoi圖的優(yōu)點(diǎn)[10]。但是這種方法對(duì)具有尖銳特征的點(diǎn)云數(shù)據(jù)沒有效果。

本文提出一種新的點(diǎn)云法向量估計(jì)方法,可對(duì)具有邊緣或細(xì)節(jié)特征的點(diǎn)云法向量進(jìn)行有效估計(jì),且在外點(diǎn)噪聲存在的情況下也能獲得較好的效果。首先,使用主成分分析(Principal Component Analysis, PCA)估計(jì)點(diǎn)云的初始法向量;其次,針對(duì)PCA在邊緣和細(xì)節(jié)特征處估計(jì)結(jié)果不準(zhǔn)確的問題,使用層次聚類和迭代最小二乘法對(duì)PCA估計(jì)的法向量進(jìn)行調(diào)整。在迭代過程中引入三個(gè)權(quán)函數(shù)控制鄰域點(diǎn)對(duì)平面擬合的作用,各權(quán)函數(shù)帶寬利用特征系數(shù)自適應(yīng)計(jì)算獲得。

2 主成分分析計(jì)算點(diǎn)云法向量

利用局部平面擬合的方法可計(jì)算點(diǎn)云法向量。對(duì)于點(diǎn)云中的每個(gè)點(diǎn)pi,獲取pi的k近鄰點(diǎn)集P,本文使用KD樹存儲(chǔ)點(diǎn)云數(shù)據(jù)以提高搜索的效率。通過近鄰點(diǎn)集計(jì)算一個(gè)最小二乘意義上的局部平面,該問題可表示為

(1)

(2)

Cp為3×3實(shí)對(duì)稱矩陣。對(duì)協(xié)方差矩陣Cp進(jìn)行奇異值分解(SVD)得到特征值λi(i=0,1,2),其中λ2≥λ1≥λ0。特征值λ2,λ1,λ0對(duì)應(yīng)的特征向量分別為v2,v1,v0,最小特征值λ0的特征向量v0即為平面的法向量。

3 迭代最小二乘的平面擬合

(3)

其中ε是一個(gè)對(duì)稱、正定函數(shù),在零處有唯一的最小值。平面擬合問題如下

(4)

(5)

(6)

圖1是使用迭代最小二乘擬合平面的結(jié)果圖。從圖1可以看出,與標(biāo)準(zhǔn)最小二乘相比,迭代最小二乘受外點(diǎn)影響很小。算法1是具體的迭代最小二乘平面擬合算法。

圖1 迭代最小二乘的平面擬合結(jié)果圖

算法1:迭代最小二乘平面擬合算法

輸入:P待檢測平面的點(diǎn),It最大迭代次數(shù),γ迭代終止閾值。

初始化:nold←Φ;∥ 上一次計(jì)算的法線

對(duì)C進(jìn)行奇異值分解得到特征值λ0≤λ1≤λ2,對(duì)應(yīng)特征向量v0,v1,v2;

n=v0;∥v0為平面的法向量

fork=1toIt

nold=n

計(jì)算權(quán)函數(shù)w

對(duì)C進(jìn)行奇異值分解,最小特征值對(duì)應(yīng)的特征向量為平面法向量n;

convg=max(abs(nold-n)/abs(nold));

if convg<γ then

迭代終止;

end if

end for

4 使用迭代最小二乘計(jì)算點(diǎn)云法向量

4.1 點(diǎn)云特征系數(shù)

點(diǎn)云高斯映射是將非平坦聚類細(xì)分為多個(gè)子類,使特征點(diǎn)和平坦區(qū)域的點(diǎn)形成不同的聚類。設(shè)S=S(u,v)是三維空間一正則曲面,該曲面的法向量方向一致,將點(diǎn)q∈S處曲面的單位法矢量的始端平移到單位球S2={(x,y,z)?R3|x2+y2+z2=1}的中心,使曲面上的點(diǎn)與球面上的點(diǎn)相對(duì)應(yīng),這種對(duì)應(yīng)被稱為曲面S上的高斯隱射G:S→S2。曲面S的高斯隱射的像記為G(S),稱G(S)為S的高斯圖,單位球S2稱為高斯球。

高斯映射可以把幾何空間中曲面的法向量映射到單位球上。曲面法向量在平滑區(qū)域內(nèi)變化平緩;在細(xì)節(jié)或尖銳特征區(qū)域內(nèi),法向量會(huì)發(fā)生顯著變化。因此,利用法向量的高斯映射可以確定曲面的細(xì)節(jié)和尖銳特征區(qū)域。曲面平滑區(qū)域內(nèi)的點(diǎn)及其相鄰點(diǎn)的高斯映射在單位球上形成一個(gè)聚類簇;而細(xì)節(jié)或尖銳特征區(qū)域的點(diǎn)經(jīng)高斯隱射后則可能產(chǎn)生多個(gè)聚類簇,每個(gè)聚類簇分別對(duì)應(yīng)曲面上的不同的區(qū)域。平面和柱形曲面的高斯映射分別對(duì)應(yīng)高斯球上一個(gè)點(diǎn)和圓。

曲面點(diǎn)云的高斯映射如圖2所示。圖2(a)為兩個(gè)相交平面,其中綠色點(diǎn)是位于兩相交平面邊緣上的點(diǎn),紅色點(diǎn)和藍(lán)色點(diǎn)是綠色點(diǎn)的鄰域點(diǎn),分別位于不同平面上。圖2(b)為圖2(a)中紅色點(diǎn)和藍(lán)色點(diǎn)的法向量經(jīng)高斯映射后的結(jié)果。綠色點(diǎn)位于兩相交平面的邊緣處,所以它的鄰域點(diǎn)經(jīng)高斯隱射后在單位球上會(huì)形成兩個(gè)聚類簇(對(duì)應(yīng)圖2(b)單位球上的藍(lán)色和紅色點(diǎn))。

圖2 曲面點(diǎn)云的高斯映射結(jié)果圖

曲面點(diǎn)云的法向量經(jīng)高斯隱射后,單位球上兩點(diǎn)a和b的測地距離為法向量na和nb之間的夾角,即

d(a,b)=arccos(na,nb)

(7)

測地距離d描述了兩個(gè)法向量的相似程度。利用層次聚類算法對(duì)單位球上的點(diǎn)進(jìn)行聚類。層次聚類的基本思想是:首先把每個(gè)點(diǎn)當(dāng)作一類;其次逐次合并兩個(gè)類形成一個(gè)大類,至到任意兩個(gè)類之間的距離大于給定的閾值。使用平均距離D度量兩類A和B之間的距離

(8)

使用特征系數(shù)fi表示點(diǎn)pi是否為特征點(diǎn)。若fi=0,則表示pi為非特征點(diǎn);若fi=1,則表示pi為特征點(diǎn);若0

點(diǎn)pi的特征系數(shù)fi的計(jì)算步驟為:

1)首先找到點(diǎn)pi的鄰域點(diǎn)集合,對(duì)各鄰域點(diǎn)利用PCA計(jì)算的法向量進(jìn)行高斯映射。

2)對(duì)高斯球上的點(diǎn)進(jìn)行層次聚類,并統(tǒng)計(jì)聚類簇總數(shù)、主簇和非主簇。對(duì)每個(gè)聚類簇,如果該簇的大小超過τ,則該簇為主簇。τ為鄰域集大小與聚類簇總數(shù)的比值。

3)計(jì)算特征系數(shù)。如果層次聚類后聚類簇個(gè)數(shù)為1,則特征系數(shù)fi=0;若主簇個(gè)數(shù)大于1,則特征系數(shù)fi=1;若主簇個(gè)數(shù)為1,則特征系數(shù)按式(9)計(jì)算:

fi=min([(2*p2)/p1,1])

(9)

其中p1和p2分別為主簇和非主簇內(nèi)各點(diǎn)到離其最近的六個(gè)點(diǎn)的距離均值的平方和。

4.2 法向量的調(diào)整

(10)

5 試驗(yàn)與分析

本文對(duì)迭代最小二乘估計(jì)點(diǎn)云法向量進(jìn)行了驗(yàn)證。圖3為不同方法對(duì)兩種類型點(diǎn)云數(shù)據(jù)的法向量估計(jì)側(cè)面結(jié)果圖。圖3(a)是未添加噪聲的點(diǎn)云數(shù)據(jù),對(duì)點(diǎn)云數(shù)據(jù)圖3(a)添加噪聲如圖3(b)所示。圖3(c)、 (d)和(e)分別為主成分分析(PCA)、隨機(jī)采樣一致性算法(RANSAC)和本文方法對(duì)未添加噪聲的點(diǎn)云數(shù)據(jù)(圖3(a))的法向量估計(jì)結(jié)果。圖3(f)、(g)和(h)是對(duì)添加噪聲的點(diǎn)云數(shù)據(jù)(圖3(b))使用主成分分析(PCA)、RANSAC和本文方法的法向量估計(jì)結(jié)果。

圖3 不同方法對(duì)兩種類型點(diǎn)云數(shù)據(jù)的法向量估計(jì)側(cè)面結(jié)果圖

從圖3(e)和(h)可以看出,對(duì)未添加噪聲和添加噪聲的兩種點(diǎn)云數(shù)據(jù),本文方法比主成分分析(PCA) 和RANSAC對(duì)點(diǎn)云法向量的估計(jì)更加準(zhǔn)確。在圖3(e)和(h)中,邊緣處點(diǎn)的法向量朝向基本一致,其它點(diǎn)處的法向量也更加緊湊,而且本文方法在邊緣處的估計(jì)效果基本不受噪聲影響。從圖3(c)、(d)、(f)、(g)中可以看出,在點(diǎn)云邊緣處,主成分分析法(PCA) 和RANSAC對(duì)法向量的估計(jì)基本失效,PCA的估計(jì)結(jié)果更易受到噪聲的干擾。

為了定量評(píng)價(jià)算法性能,使用根均方誤差(RMS),定義如下

(11)

(12)

表1和表2 分別是不同方法對(duì)未添加噪聲和添加噪聲點(diǎn)云法向量估計(jì)的NBP和RMS。可以看出,對(duì)于兩種不同類型的點(diǎn)云數(shù)據(jù),利用本文方法比主成分分析法(PCA)和隨機(jī)采樣一致性算法(RANSAC)對(duì)法向量的估計(jì)更加接近真實(shí)法向量,而且估計(jì)錯(cuò)誤點(diǎn)數(shù)更少。

表1 各種方法對(duì)法向量估計(jì)的NBP和RMS (不含異常值)

表2 各種方法對(duì)法向量估計(jì)的NBP和 RMS (含異常值)

6 結(jié)束語

本文提出一種基于迭代最小二乘法的法向量估計(jì)方法。通過迭代最小二乘擬合局部平面的方法對(duì)點(diǎn)云初始法向量進(jìn)行調(diào)整,進(jìn)而獲得最終的法向量估計(jì)結(jié)果。本文方法克服了傳統(tǒng)方法在細(xì)節(jié)特征區(qū)域法向量估計(jì)結(jié)果不準(zhǔn)確的缺點(diǎn),同時(shí)不受外點(diǎn)噪聲的影響。使用本文方法得到的比較準(zhǔn)確的法向量估計(jì)結(jié)果,對(duì)后續(xù)三維點(diǎn)云模型的點(diǎn)云分割、特征檢測和提取、曲面重建等具有重要意義。