基于移動(dòng)最小二乘法法矢估計(jì)的建筑物點(diǎn)云特征提取

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

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

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

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

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

1 算法原理

1.1 移動(dòng)最小二乘曲面

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

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

在局部區(qū)域內(nèi)移動(dòng)最小二乘擬合函數(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)是個(gè)k階多項(xiàng)式，m為基函數(shù)的項(xiàng)數(shù)。線性和二次基的基函數(shù)分別為p(x)=[1xy]T和p(x)=[1xyx2xyy2]T。本文采用二次基以提高曲面擬合及法矢估計(jì)的精度。加權(quán)殘差方程的表達(dá)式為

(2)

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

為了求式(2)的系數(shù)α(x)，必須使其取極小值，即對(duì)α進(jìn)行求導(dǎo)運(yùn)算。求導(dǎo)后的計(jì)算結(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ù)作為控制移動(dòng)最小二乘曲面特征擬合尺度的重要參數(shù)，其選取對(duì)擬合精度非常重要。移動(dòng)最小二乘法中的權(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 法矢計(jì)算及重定向

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

(8)

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

故曲面在該點(diǎn)的法矢向量計(jì)算公式如下

(9)

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

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

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

(10)

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

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

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

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

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

(11)

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

(12)

式中，K為以vi為中心點(diǎn)的鄰點(diǎn)個(gè)數(shù)。

2 實(shí)例分析

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

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

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

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

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

圖4 點(diǎn)的位置

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

圖5 鄰點(diǎn)個(gè)數(shù)對(duì)顯著性指標(biāo)的影響

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

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

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

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

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

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

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

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

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

3 結(jié) 語

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

參考文獻(xiàn)：

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

[2] 馮梅.基于LiDAR和航空影像的三維建模方法探討[J].測(cè)繪通報(bào),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] 高陽,王留召,李明.車載激光彩色點(diǎn)云的道路標(biāo)志線提取方法[J].測(cè)繪通報(bào),2016(4):28-32.

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

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

[7] 詹慶明,周新剛,肖映輝,等.從激光點(diǎn)云中提取古建筑線性和圓形特征的比較[J].武漢大學(xué)學(xué)報(bào)(信息科學(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é)報(bào),2015,23(2):299-307.

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

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

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

[13] 周玉蓮.基于法矢信息的點(diǎn)云特征提取技術(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ǎn)云模型法矢調(diào)整優(yōu)化算法[J].中國(guó)圖象圖形學(xué)報(bào),2013,18(7):844-851.