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

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

(貴州大學礦業學院，貴州 貴陽 550025)

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

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

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

1 算法原理

1.1 移動最小二乘曲面

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

1.1.1 擬合函數的建立

在局部區域內移動最小二乘擬合函數表示為

(1)

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

(2)

式中，w(x-xi)為節點xi的權函數。

為了求式(2)的系數α(x)，必須使其取極小值，即對α進行求導運算。求導后的計算結果為

(3)

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

(4)

于是求得的擬合方程的系數為

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

(5)

(6)

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

1.1.2 權函數

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

(7)

圖1 影響區域和三次樣條權函數

1.2 法矢計算及重定向

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

(8)

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

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

(9)

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

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

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

(10)

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

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

1.3 顯著性指標計算

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

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

(11)

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

(12)

式中，K為以vi為中心點的鄰點個數。

2 實例分析

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

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

圖2 調整前的法矢

圖3 調整后的法矢

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

圖4 點的位置

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

圖5 鄰點個數對顯著性指標的影響

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

圖6 顯著性指標分布

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

圖7 本文算法與傳統算法提取的初始特征

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

表1 簡化閾值和簡化率的關系

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

圖8 本文算法與傳統算法重采樣后的特征

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

3 結 語

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

參考文獻：

[1] 關麗,丁燕杰,張輝,等.面向數字城市建設的三維建模關鍵技術研究與應用[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] 高陽,王留召,李明.車載激光彩色點云的道路標志線提取方法[J].測繪通報,2016(4):28-32.

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

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

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

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

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

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

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

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

[13] 周玉蓮.基于法矢信息的點云特征提取技術的研究[D].哈爾濱:哈爾濱工業大學,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] 孫金虎,周來水,安魯陵.點云模型法矢調整優化算法[J].中國圖象圖形學報,2013,18(7):844-851.