基于移動最小二乘法法矢估計的建筑物點云特征提取

裴書玉，杜 寧，王 莉，張春亢，劉繼庚，徐光禹

(貴州大學(xué)礦業(yè)學(xué)院，貴州 貴陽 550025)

隨著數(shù)字城市概念的提出和快速發(fā)展，大比例尺的三維城市模型成為近年來重建技術(shù)的研究熱點[1-3]。三維激光掃描作為一種快速獲取建筑物表面三維模型的新技術(shù)，能夠提供豐富的關(guān)于建筑物立面的三維空間信息，如高精度的點云、RGB信息、反射強(qiáng)度及同軸相機(jī)拍攝的高清影像，從而為建筑物的重建研究提供了新的數(shù)據(jù)支持[4-6]。然而現(xiàn)實中建筑物結(jié)構(gòu)的高度復(fù)雜性，給模型的重建工作特別是特征要素的提取工作帶來了很大的麻煩。在整個建模周期中，特征要素的提取是最耗時的階段，也是重建工作的靈魂，能否恢復(fù)具有高度真實感的模型，很大程度上取決于特征要素的恢復(fù)效果。因此，快速且準(zhǔn)確地提取建筑物的特征要素顯得極為重要。

在建筑物點云特征提取的研究中，針對不同的建筑物模型，相關(guān)學(xué)者提出了不同的特征提取算法。詹慶明等利用Hough變換和最小二乘法從古建筑點云中提取直線和圓，雖然精度較高，但提取的特征不夠完整[7]。于海霞等針對立面基本垂直于地面、表面基本平滑、轉(zhuǎn)角基本為直角的規(guī)則建筑物采用平面擬合算法提取特征點的方法，但對于結(jié)構(gòu)復(fù)雜的建筑物模型并不適用[8]。楊林等提出影像輔助下的建筑物點云特征精細(xì)提取方法，該方法受影像與點云數(shù)據(jù)的配準(zhǔn)誤差、投影視差等誤差的影響，且無法提取特征邊緣存在曲線的特征[9]。陳朋等以點到其3個相鄰鄰域點所構(gòu)成平面的距離平均值進(jìn)行特征點的提取，點到平面的距離只能表征部分點的顯著性而使得一些特征點不能被識別出來[10]。

針對上述問題，本文基于地面三維掃描的建筑物點云數(shù)據(jù)，提出一種建筑物點云特征提取方法，該方法首先采用移動最小二乘法進(jìn)行法矢估計，然后將K鄰域法矢夾角的均值作為點的顯著性指標(biāo)進(jìn)行特征點判別，最后對特征點進(jìn)行下采樣得到清晰完整的特征線。

1 算法原理

1.1 移動最小二乘曲面

移動最小二乘法(moving-least square，MLS)是一種離散數(shù)據(jù)插值的方法，用其進(jìn)行曲面擬合精度高，曲面表達(dá)簡單[11]?；谝苿幼钚《怂惴ㄟM(jìn)行曲面擬合較傳統(tǒng)最小二乘有兩大改進(jìn)：一是擬合函數(shù)的構(gòu)建不同；二是引入緊支(compact support)概念。研究表明，最小二乘曲面擬合充分考慮了中心點的K鄰域信息，且鄰域大小可以根據(jù)不同模型進(jìn)行調(diào)整，使散亂點云數(shù)據(jù)法矢估計更加準(zhǔn)確和穩(wěn)健[12]。故本文以基于投影的移動最小二乘曲面為基礎(chǔ)進(jìn)行法矢估計，將點的K近鄰點擬合成局部二次曲面后得到該點的估計法矢。

1.1.1 擬合函數(shù)的建立

在局部區(qū)域內(nèi)移動最小二乘擬合函數(shù)表示為

(1)

式中，α(x)=[α1(x)α2(x) …αm(x)]T為待求系數(shù)，它是坐標(biāo)x的函數(shù)；p(x)=[p1(x)p2(x) …pm(x)]T，稱為基函數(shù)，基函數(shù)p(x)是個k階多項式，m為基函數(shù)的項數(shù)。線性和二次基的基函數(shù)分別為p(x)=[1xy]T和p(x)=[1xyx2xyy2]T。本文采用二次基以提高曲面擬合及法矢估計的精度。加權(quán)殘差方程的表達(dá)式為

(2)

式中，w(x-xi)為節(jié)點xi的權(quán)函數(shù)。

為了求式(2)的系數(shù)α(x)，必須使其取極小值，即對α進(jìn)行求導(dǎo)運算。求導(dǎo)后的計算結(jié)果為

(3)

式(3)經(jīng)整理后可表示為

(4)

于是求得的擬合方程的系數(shù)為

α(x)=A-1(x)B(x)y

(5)

(6)

式中，φk(x)為形函數(shù)；k為基函數(shù)的階次。

1.1.2 權(quán)函數(shù)

權(quán)函數(shù)作為控制移動最小二乘曲面特征擬合尺度的重要參數(shù)，其選取對擬合精度非常重要。移動最小二乘法中的權(quán)函數(shù)w(x-xi)應(yīng)該具有緊支性，即權(quán)函數(shù)只受x周圍一定區(qū)域內(nèi)的影響，超出該區(qū)域后其權(quán)值很小，影響可以忽略，該區(qū)域稱為權(quán)函數(shù)的影響區(qū)域。一般來說選擇圓形作為權(quán)函數(shù)的支持域，其半徑記為smax，如圖1(a)所示。

(7)

圖1 影響區(qū)域和三次樣條權(quán)函數(shù)

1.2 法矢計算及重定向

定義局部二次曲面為S(u,v)=S(u,v,h(u,v))則曲面在該點的一階偏導(dǎo)計算公式為

(8)

其中，h(u,v)=au2+buv+cv2+du+ev+f。

故曲面在該點的法矢向量計算公式如下

(9)

式中，a、b、c、d、e、f為曲面方程系數(shù)。

移動最小二乘法計算出的法矢具有二義性，即只得到了法矢所在的直線，而沒有確定以直線的哪個方向為法向量的最終方向。因此，需要為模型中點的法矢規(guī)定一個統(tǒng)一的方向，如所有法矢都指向模型的外部，即進(jìn)行法矢方向一致化處理，以保證特征提取結(jié)果的準(zhǔn)確。本文采用MST(minimum spanning tree)進(jìn)行法矢方向的一致化調(diào)整[16]，算法首先為模型中點云定義一個成本函數(shù)

cost(p·q)=|d·np+d·nq|

(10)

式中，d為從點p指向點q的單位向量；np、nq分別為點p、q的法矢，p、q是鄰接點。

首先從點云模型中選擇z值最大的點，作為廣度優(yōu)先遍歷的種子點，調(diào)整種子點的法矢方向，使得其與向量(0,0,1)的夾角余弦大于0，這樣可以保證調(diào)整后所有點的法矢指向模型的外側(cè)；接著以成本函數(shù)為權(quán)值，按廣度優(yōu)先遍歷點云數(shù)據(jù)，由i點遍歷到其鄰接點j時，如果ni·nj<0，那么將j點的法矢乘以-1；否則nj方向不需要調(diào)整。

1.3 顯著性指標(biāo)計算

分析發(fā)現(xiàn)，在建筑物點云模型中，墻面等平坦區(qū)域點的法矢變化平緩，而起伏較大的區(qū)域如墻角等法向量變化劇烈?；诖?，本文引入一個顯著性指標(biāo)f(vi)作為特征點判別的依據(jù)，f(vi)為中心點K近鄰點法矢改變量的均值。即首先計算當(dāng)前點P的法矢分別與其最近鄰的K個點P1,P2,…,PK的法矢之間的夾角，然后計算這K個夾角的平均值作為點P的顯著性度量指標(biāo)。

定義θij為兩個點P1和P2的法矢夾角，兩個點的法向量分別記為n1(x1,y1,z1)和n2(x2,y2,z2)，則兩點法矢夾角計算公式為

(11)

則對于當(dāng)前點vi，與其K近鄰點法矢夾角的平均值的計算方法按式(13)計算，結(jié)果即為該點的顯著性度量指標(biāo)值。

(12)

式中，K為以vi為中心點的鄰點個數(shù)。

2 實例分析

本文試驗的硬件環(huán)境為英特爾Xeon E3-1241處理器、8 GB內(nèi)存，軟件環(huán)境為Windows 7 64位操作系統(tǒng)、VS2013 C++、PCL1.8.0(Point cloud library，點云庫)，試驗所用數(shù)據(jù)清華大學(xué)校門模型的點云來自徠卡官網(wǎng)的示例數(shù)據(jù)庫，在對數(shù)據(jù)進(jìn)行濾波、去噪和對頂部等掃描不到而產(chǎn)生孔洞的地方進(jìn)行填充等預(yù)處理后得到的完整模型點云數(shù)量約為90萬。

在用移動最小二乘法進(jìn)行法矢估計時，計算得到的法矢具有二義性會使后續(xù)顯著性指標(biāo)的計算出現(xiàn)錯誤，從而影響特征點的判別，故在計算顯著性指標(biāo)前需先進(jìn)行法矢方向的調(diào)整。如圖2所示為移動最小二乘法估計出的初始法矢，從圖中可以看出法矢方向比較混亂，有的指向模型外部，有的指向模型內(nèi)部。按本文方法進(jìn)行法矢調(diào)整后的法矢一致朝向模型的外部，如圖3所示。

圖2 調(diào)整前的法矢

圖3 調(diào)整后的法矢

分析發(fā)現(xiàn)，近鄰點個數(shù)的選取對計算顯著性指標(biāo)f(vi)有很大影響，鄰點個數(shù)選取不足或過多都會影響顯著性指標(biāo)計算的準(zhǔn)確性，從而影響特征點的判斷。如圖4所示，本文選取建筑物模型中棱角、圓柱、墻面3個具有代表性位置的點來分析鄰點個數(shù)的選取對顯著性指標(biāo)的影響。

圖4 點的位置

如圖5所示，隨著鄰近點數(shù)量的增加，墻面上點的顯著性指標(biāo)一直接近于0，但圓柱和棱角上的點隨著鄰點數(shù)的增多顯著性指標(biāo)呈增大的趨勢。在鄰點數(shù)較少時，圓柱和棱角上點的顯著性指標(biāo)隨鄰點數(shù)的增加出現(xiàn)跳躍，此時計算出的顯著性指標(biāo)不穩(wěn)定，不適合作為判斷特征點的依據(jù)；在鄰點數(shù)為11時，二者顯著性指標(biāo)最為接近，此時，其顯著性指標(biāo)分別為0.254 98和0.267 02；在鄰點個數(shù)大于11后，二者顯著性指標(biāo)增大的趨勢就比較穩(wěn)定，且棱角點的顯著性指標(biāo)一直高于圓柱點。由上述分析可知，鄰點個數(shù)選為11時顯著性指標(biāo)已趨于穩(wěn)定，且作為建筑物特征的圓柱點和棱角點顯著性指標(biāo)相差不大，故本文選取11作為本次試驗的鄰點個數(shù)。

圖5 鄰點個數(shù)對顯著性指標(biāo)的影響

鄰點數(shù)為11時，計算得到的模型顯著性指標(biāo)如圖6所示，從圖中可以看出，顯著性指標(biāo)較大的點都分布在建筑物的輪廓及曲率變化較大的位置。

圖6 顯著性指標(biāo)分布

用本文算法對原始點云模型進(jìn)行特征提取，不同閾值下簡化點數(shù)及簡化率見表1。從表中可以看出，提取的特征點數(shù)隨著簡化閾值的變大迅速減少，簡化率不斷提高，試驗結(jié)果表明在閾值設(shè)為0.30時簡化率很高，雖仍能提取出模型的輪廓，但細(xì)小的特征已被刪除。在閾值為0.25時提取特征點數(shù)為96 313，簡化率為89.24%，提取的特征比較清晰、完整，如圖7(a)、(b)所示，但此時仍有冗余數(shù)據(jù)存在。

圖7 本文算法與傳統(tǒng)算法提取的初始特征

考慮提取的特征點比較密集，為進(jìn)一步減少冗余數(shù)據(jù)，采用按距離下采樣的方法繼續(xù)對其簡化，在距離設(shè)為0.088 4時保留特征點數(shù)為6219，下采樣后簡化率為99.31%，如圖8(a)、(b)所示，提取出的特征線依然清晰完整。

表1 簡化閾值和簡化率的關(guān)系

為了驗證本文算法的優(yōu)越性，在簡化率基本相同的情況下，與采用傳統(tǒng)的法向量估計方法進(jìn)行對比試驗，提取特征點數(shù)為98 769，簡化率為88.96%，試驗結(jié)果如圖7(c)、(d)所示，對其進(jìn)行下采樣后點數(shù)為6352，簡化率為99.29%，結(jié)果如圖8(c)、(d)所示。

圖8 本文算法與傳統(tǒng)算法重采樣后的特征

由圖7—圖8的對比可知，采用傳統(tǒng)的法向量估計方法進(jìn)行特征提取對于小的特征不敏感且提取出來的特征不夠完整，而本文算法得到的特征清晰、完整，特別是在對其下采樣后冗余數(shù)據(jù)大大減少的情況下，提取出的特征線更加清晰、簡潔、美觀。

3 結(jié) 語

本文對建筑物點云特征提取和法矢計算的移動最小二乘方法進(jìn)行了研究，提出了一種基于移動最小二乘法矢估計的建筑物點云特征提取方法。算法采用移動最小二乘法進(jìn)行法矢估計，然后將鄰域法矢夾角的均值作為點的顯著性指標(biāo)進(jìn)行特征點判別，最后對提取出的特征點集進(jìn)行下采樣。試驗中討論了鄰點個數(shù)對顯著性指標(biāo)的影響并選出了最佳取值，試驗結(jié)果表明移動最小二乘估計法矢能顯著提高顯著性指標(biāo)的計算精度，從而可以刪除絕大多數(shù)墻面點，提取出棱角、輪廓和圓柱等上的特征點，對特征點集進(jìn)行下采樣大大減少了冗余數(shù)據(jù)，從而提取出清晰、簡潔、完整的特征線。

參考文獻(xiàn)：

[1] 關(guān)麗,丁燕杰,張輝,等.面向數(shù)字城市建設(shè)的三維建模關(guān)鍵技術(shù)研究與應(yīng)用[J].測繪通報,2017(2):90-94.

[2] 馮梅.基于LiDAR和航空影像的三維建模方法探討[J].測繪通報,2011(12):12-14.

[3] KEDZIERSKI M,FRYSKOWSKA A.Methods of Laser Scanning Point Clouds Integration in Precise 3D Building Modelling[J].Measurement,2015,74:221-232.

[4] 高陽,王留召,李明.車載激光彩色點云的道路標(biāo)志線提取方法[J].測繪通報,2016(4):28-32.

[5] 李天爍,王晏民,胡春梅.基于激光反射強(qiáng)度的點云自動配準(zhǔn)研究[J].測繪通報,2014(S2):143-145.

[6] 王瑞巖,姜光,高全學(xué).結(jié)合圖像信息的快速點云拼接算法[J].測繪學(xué)報,2016,45(1):96-102.

[7] 詹慶明,周新剛,肖映輝,等.從激光點云中提取古建筑線性和圓形特征的比較[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2011,36(6):674-677.

[8] 于海霞,吳侃,敖建鋒,等.地面3維激光掃描技術(shù)建筑物特征線提取[J].激光技術(shù),2012,36(4):553-556.

[9] 楊林,盛業(yè)華,王波.影像輔助下基于地面LiDAR的建筑物特征精細(xì)提取方法[J].應(yīng)用基礎(chǔ)與工程科學(xué)學(xué)報,2015,23(2):299-307.

[10] 陳朋,譚曄汶,李亮.地面三維激光掃描建筑物點云特征線提取[J].激光雜志,2016,37(3):9-11.

[11] 邱彥杰.反向工程中自動精確模型重建的關(guān)鍵技術(shù)研究[D].上海:上海交通大學(xué),2011.

[12] 曾清紅,盧德唐.基于移動最小二乘法的曲線曲面擬合[J].工程圖學(xué)學(xué)報,2004,25(1):84-89.

[13] 周玉蓮.基于法矢信息的點云特征提取技術(shù)的研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2012.

[14] DEY T K，SUN J.An Adaptive MLS Surface for Reconstruction with Guarantees[C]∥Proceedings of The Third Eurographics Symposium on Geometry Processing.Vienna：[s.n.],2005:43-52.

[15] WANG H，SCHEIDEGGER C E，SILVA C T.Bandwidth Selection and Reconstruction Quality in Point-based Surface[J].IEEE Transactions on Visualization and Computer Graphics，2009，15(4): 572-582.

[16] 孫金虎,周來水,安魯陵.點云模型法矢調(diào)整優(yōu)化算法[J].中國圖象圖形學(xué)報,2013,18(7):844-851.