基于移動最小二乘法的點云平滑及重采樣

吳曉慶，黃玉清

(西南科技大學 信息工程學院，四川 綿陽 621010)

?

基于移動最小二乘法的點云平滑及重采樣

吳曉慶，黃玉清

(西南科技大學 信息工程學院，四川 綿陽 621010)

將點云進行三維重建符合人們的視覺習慣，可以逼真地反映場景的立體效果，并且可以方便地進行多角度顯示。針對貪婪投影三角化重建結果中存在的曲面不光滑且存在孔洞等問題，提出了使用移動最小二乘法來進行點云的平滑、重采樣處理。實驗表明，通過移動最小二乘法進行先平滑后采樣的方法比直接使用貪婪投影三角化算法或僅平滑處理、采樣處理再重建的效果都要好。

三維重建；移動最小二乘法；點云平滑；重采樣；貪婪投影三角化算法

0 引言

曲面重建技術在逆向工程、數字可視化、機器視覺、虛擬現實、醫療技術等領域中得到了廣泛的應用。除了上述傳統行業，隨著新興的廉價RGBD獲取設備在數字娛樂行業的病毒式擴展，使得更多人開始使用點云來處理對象并進行工程應用。PCL中目前實現了基于點云的曲面重建模塊框架，在此基礎上實現了比較基礎的泊松重建[1]、MC重建、EarClipping、貪婪投影三角化重建[2]等算法。但是由于測量技術的原因，造成一些誤差，通過基本的重建算法無法達到目標效果。本文通過對輸入點云進行移動最小二乘法(Moving Least Squares,MLS)的先平滑后采樣的處理，并將點云作為貪婪投影三角化重建算法(Greedy Projection Algorithm)的輸入，最終實現較好的重建結果。

1 貪婪投影三角化算法

貪婪算法是一種把復雜問題進行精簡的算法[2]，在對問題求解時，不從整體最優上加以考慮，它所得的是在某種意義上的局部最優解。也就是說，它把所有的步驟進行細化，形成一個接一個的小問題，之后按照問題的復雜度來對它們進行排序，這在當時被認為是最好的解決辦法，然后逐漸地接近最后的問題，最后求解得到解答[3]。

將三維點通過發現投影到某一平面，然后對投影得到的點云做平面內的三角化，從而得到各點的連接關系。在平面區域三角化的過程中用到了基于Delaunay的空間區域增長算法，該方法通過選取一個樣本三角片作為初始曲面，不斷擴張曲面邊界，形成一張完整的三角網格曲面。最后根據投影點云的連接關系確定各原始三維點間的拓撲連接，所得三角網格即為重建得到的曲面模型[4]。

該算法基于增量表面生長規律[5]，遵循貪婪類型方法。算法通過創建一個起始的三角形啟動，并不斷添加新的三角形直到所有點云中的點被包含或沒有更有效的三角形。算法如下[6]：

(1)最近鄰域搜索：對于點云中的每一個點p，選擇一個k鄰域。這個鄰域是由搜索參考點k-近鄰的范圍內創建的，半徑為r。半徑定義為μ×d，其中d是p點以及最接近鄰域的距離，μ是用戶指定的常數，以計算點云密度。Kdtree鄰域算法經常被用來計算給定點云的臨近點。

點云中的點被分配各種狀態：沒有限制的、邊緣、邊界和完成，這取決于算法。

①最初，點云中的所有點都是沒有限制的，即這些點沒有入射的三角形。

②當一個點的所有可能三角形被確定，那么點被定義為完成狀態。

③當點被選做一個參考點，但是由于最大允許角度參數的限制而缺失一些三角形，點被定義為邊界點。

④邊緣點是那些未被選做參考點的點。

(2)使用切平面的鄰域投影：鄰域投影在一個表面上，該表面相切于p點周圍且有序形成的曲面。

(3)修剪：根據可見度和距離標準修剪點，并連接p和靠近邊緣的連續點，形成具有最大角度標準和可選最小角度標準的三角形。點云中的點被修剪取決于很多標準。例如：

①通過距離標準修剪。

②位于以參考點為中心的影響范圍之外的其他點是被刪除。所選擇的點被稱為候選點。

③投影平面的選擇：在應用距離標準后的候選點集合投影到近似切面上。

④角度指定：以參考點作為初始點定義新的局部坐標，并且上一步的平面投影作為xy平面。所有在候選集中的點被映射到這個面上。基于局部坐標系統的x軸和從原點到映射的坐標之間的角度θ，選擇周圍的參考點。

⑤可視化：潛在形成的自相關網格的點被丟棄。

使用參考點、候選點集合邊界邊緣方法，投影平面。在這種情況下，從參考點到候選頂點的視線被邊緣阻塞，則該點被遮擋。

2 MLS平滑、重采樣

因為貪婪投影三角化算法的輸入是具有估計的表面法線和曲率數據的點云。現有程序是通過PCA(主成分分析)的方法來求取表面法線的。有時，測量較小的對象時會產生一些誤差，這些誤差所造成的不規則數據如果直接用來曲面重建會使重建的曲面不光滑或者有漏洞。這些不規則數據很難用統計分析消除，所以為了建立完整的模型必須對表面進行平滑處理和漏洞修復。

在此部分，在現有數據的基礎上，利用移動最小二乘方法(Moving Least Squares,MLS)解決數據重采樣這一問題，重采樣算法通過對周圍數據點進行高階多項式插值來重建表面缺失的部分。

2.1 擬合函數的建立

在擬合區域的一個局域子域U上，擬合函數表示為：

(1)

式中，a(x)=[a1(x),a2(x)…am(x)]T為待求系數，它是坐標x的函數，p(x)=[p1(x),p2(x)…pm(x)]T稱為基函數，它是一個階完備的多項式，是基函數的項式[7]，常用的二次基為[1,u,v,u2,v2,uv]T，所以式(1)中的擬合函數通常表示為[8]：

f(x)=a0(x)+a1(x)u+a2(x)v+a3(x)u2+a4(x)v2+a5(x)uv

考慮下面的加權離散L2范式[9]：

a1(x)u+a2(x)v+a3(x)u2+a4(x)v2+a5(x)uv)-yi]2

(2)

式中：n是影響區域節點的數目，f(x)是擬合函數，yi是x=xi處的節點值。yi=y(xi);w(x-xi)是節點xi的權函數。為了確定系數a(x)，式(2)中[(a0(x)+a1(x)u+a2(x)v+a3(x)u2+a4(x)v2+a5(x)uv)-yi]2應取極小值，從而得：

a=(BWBT)-1BWy

但是以上的權函數只能用于描述低等級的表面，因此在某些情況下會產生不足的近似值，為了反映現實情況，重新估計點較近的采樣點應該比估算較遠的采樣點有更大的影響，所以應該重新考慮權函數。

2.2 權函數的確定

權函數是移動最小二乘法的核心。在移動最小二乘法中，權函數w(x-xi)應該具有緊支性，即權函數在x的一個子域內不等于0，在這個子域外全是0，這個子域稱為權函數的支持域(即x的影響域)，其半徑記為smax。由于權函數的緊支性，所以只有屬于影響區域內的點才會對點x的取值有影響[7]。

(1)點云平滑處理

1.1 研究對象 2014年1月-2014年12月南京市胸科醫院的門診及住院呼吸系統疾病患者6 984例，男性4 681例，女性2 303例，年齡11～99歲，平均年齡（55.24±18.62）歲；按年齡分為五組，≤20歲組258例，20～40歲組1 322例，40～60歲組2 337例，60～80歲組2 626例，≥80歲組441例；按不同季節分組，春季（3-5月）1 931例，夏季（6-8月）1 742例，秋季（9-11月）1 650例，冬季（12-2月）1 661例；所有病例均存在呼吸道感染的臨床表現：持續性咳嗽、發熱、呼吸急促或呼吸困難；肺部聽診可聞及細濕啰音等。所有患者均知情同意。

由于擬合函數會繼承權函數的連續性，所以權函數還應具有一定的光滑性：如果權函數w(x-xi)是C1階連續的，則擬合函數也是C1連續的。常用的權函數為立方樣條權函數：

(2)點云重采樣進行孔洞修補

為了體現離重新估算點較近的采樣點對擬合函數的影響大于較遠的采樣點，權因子w(x-xi)應隨著估算點的不同而進行“移動”[11-12]。針對這種情況，本文使用如下權函數[8]：

(3)

其中di(x)為新的采樣位置p與第i個初始采樣位置pi之間的距離。當對一個輸入點云進行正確評估時，這個權函數變得無窮大。為了避免這一問題，此種情況被單獨處理。參數α控制區域鄰近特征對重采樣的影響。因為權函數與重采樣的位置有關，對于每一個采樣點，單獨計算新的系數為：

a(x)=(BW(x)BT)-1BW(x)y

其中，W(x)為由式(3)計算的對角矩陣。

①對于一個點云，創建一個三角網格。

②重復以下過程：

a.KD樹查找邊緣和它的鄰域；

b.對于一個孔鄰域計算投影平面；

c.判定平面上的重采樣位置；

d.擬合曲面且重新采樣。

③直到沒有孔洞存在。

3 實驗結果

實驗中，方案平臺硬件環境為：深度攝像頭微軟kinect；軟件開發工具為Windows 7操作系統、vs2012、pcl 1.7.2。在同一個平臺下，對比了幾種算法：普遍使用的貪婪三角形算法進行重建；使用MLS算法進行曲面平滑、重采樣及兩者結合后，采用貪婪三角形算法進行重建。實驗結果及分析如下。

(1)結果顯示如圖1～圖4所示。

圖1 貪婪投影三角化算法重建前后點云

圖2 MLS平滑后做重建效果

圖3 MLS重采樣后重建效果

圖4 MLS先平滑后采樣后重建效果

從圖2可以看出，平滑后的點云重建效果明顯好于圖1，曲面更加光滑且細紋被平滑了。通過圖(3)可以看出，經過重采樣后，將圖2中區域內的孔洞進行了修補。最終使用先平滑后采樣的方法，使得孔洞更加細微。經過比較可以看出，圖4的這種方法是最好的。

(2)效率分析

表1記錄了幾種算法程序運行的時間。可以看出優化后的算法時間上均有所減少，在重建效果上，圖3與圖4的孔洞進行了修補，且兩者相比，圖4的效果更好，運行時間上也比圖3的要少。

表1 幾種算法對比

4 結論

針對目前點云重建算法——貪婪投影三角形存在的測量誤差所造成的不規則數據使得重建的曲面不光滑且存在孔洞的情況，使用MLS算法進行曲面平滑，并通過重采樣實現孔洞的修補，最終實現較好的重建效果。并在此重建基礎上，使用八叉樹來代替KD搜索算法，在不影響重建結果的情況下，使運行效率在每一種算法原來的基礎上得到優化。實驗總體表明，對原始點云進行平滑、重采樣，運行效率相對于原始算法而言衰減了，但是重建結果得到了優化。

[1] CHAND A K B, NAVASCUES M A. Natural bicubic spline fractal interpolation[J].Nonlinear Analysis:Theory,Methods & Applications,2008,69(11):3679-3697.

[2] DEY T K, GOOSWAMI S. Tight coeone: a water-tight surface reconstructor[A]. In Proceedings of 8th ACM Symposium on Solid Modeling and Applications[C]. Washington: ACM Press, 2003: 127-134.

[3] 劉為宏.點云數據曲面重建算法及研究[D].秦皇島:燕山大學，2015.

[4] MARTON Z C, RUSU R B, BEETZ M. On fast surface reconstruction methods for large and noisy datasets[C].Proceedings of the IEEE International Conference on Robotics and Automation(ICRA), Kobe, Japan,2009.

[5] MENCL R, MULLER H. Interpolation and approximation of surfaces from three-dimensional scattered data points[C]. In: State of the Art Reports, Eurographics’98, 1998: 51-67.

[6] Navpreet Kaur Pawar.Surface reconstruction from point clouds[D].Bournemouth University, 2013.

[7] 張崇軍,鄭德華,孟慶年.基于移動最小二乘法的點云數據擬合方法[J].勘察科學技術,2016(4):26-28.

[8] LANCASTER P,SALKAUSKAS K.Curve and surface fitting[M]. The NVRBS, Book. Springer Berlin Heidelberg,1986: 361-453.

[9] 劉小虎,張雄,陸明萬.基于MLS的最小二乘配點法[J].強度與環境, 2000, 15(5):65- 69.

[10] 劉欣.無網格方法[M].北京:科學出版社,2011.

[11] 谷利國,候振杰.基于三維重建技術的三角剖分[J].微型機與應用,2010,29(18):44-47.

[12] Wang Jianning, OLIVEIRA M M. A hole-filling strategy for reconstruction of smooth surface in range images[C].SIBGRAPI’03:1530-1834.

Smoothing and resampling of point cloud based on moving least squares

Wu Xiaoqing, Huang Yuqing

(School of Information Engineering, Southwest University of Science and Technology, Mianyang 621010, China)

The three-dimensional reconstruction of the point cloud is in line with people’s visual habits, it can be realistic to reflect the three-dimensional effect of the scene, and can be easily displayed in multi-angle. Aiming at the problem that the surface is not smooth and the holes exist in the reconstructed result of the greedy projection triangulation, the moving least squares(MLS) method is proposed to smooth and resample the point cloud. Experimental results show that the method of smoothing and sampling by moving least squares method is better than that of using greedy projection triangulation algorithm or only smoothing, sampling processing, and then reconstruction.

three-dimensional reconstruction; Moving Least Squares (MLS); point cloud smoothing; resample; greedy projection triangulation

TP391.41

A

10.19358/j.issn.1674- 7720.2017.11.014

吳曉慶，黃玉清.基于移動最小二乘法的點云平滑及重采樣[J].微型機與應用，2017,36(11)：47-49，53.

2017-01-13)

吳曉慶(1991-)，女，碩士研究生，主要研究方向：圖象處理與機器視覺。

黃玉清(1962-)，通信作者，女，碩士，教授，主要研究方向：無線控制及無線通信技術、圖象處理與機器視覺、智能技術應用。E-mail:hyq3053061@163.com。