吳曉慶，黃玉清

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

?

基于移動最小二乘法的點(diǎn)云平滑及重采樣

吳曉慶，黃玉清

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

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

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

0 引言

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

1 貪婪投影三角化算法

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

將三維點(diǎn)通過發(fā)現(xiàn)投影到某一平面，然后對投影得到的點(diǎn)云做平面內(nèi)的三角化，從而得到各點(diǎn)的連接關(guān)系。在平面區(qū)域三角化的過程中用到了基于Delaunay的空間區(qū)域增長算法，該方法通過選取一個(gè)樣本三角片作為初始曲面，不斷擴(kuò)張曲面邊界，形成一張完整的三角網(wǎng)格曲面。最后根據(jù)投影點(diǎn)云的連接關(guān)系確定各原始三維點(diǎn)間的拓?fù)溥B接，所得三角網(wǎng)格即為重建得到的曲面模型[4]。

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

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

點(diǎn)云中的點(diǎn)被分配各種狀態(tài)：沒有限制的、邊緣、邊界和完成，這取決于算法。

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

②當(dāng)一個(gè)點(diǎn)的所有可能三角形被確定，那么點(diǎn)被定義為完成狀態(tài)。

③當(dāng)點(diǎn)被選做一個(gè)參考點(diǎn)，但是由于最大允許角度參數(shù)的限制而缺失一些三角形，點(diǎn)被定義為邊界點(diǎn)。

④邊緣點(diǎn)是那些未被選做參考點(diǎn)的點(diǎn)。

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

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

①通過距離標(biāo)準(zhǔn)修剪。

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

③投影平面的選擇：在應(yīng)用距離標(biāo)準(zhǔn)后的候選點(diǎn)集合投影到近似切面上。

④角度指定：以參考點(diǎn)作為初始點(diǎn)定義新的局部坐標(biāo)，并且上一步的平面投影作為xy平面。所有在候選集中的點(diǎn)被映射到這個(gè)面上?；诰植孔鴺?biāo)系統(tǒng)的x軸和從原點(diǎn)到映射的坐標(biāo)之間的角度θ，選擇周圍的參考點(diǎn)。

⑤可視化：潛在形成的自相關(guān)網(wǎng)格的點(diǎn)被丟棄。

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

2 MLS平滑、重采樣

因?yàn)樨澙吠队叭腔惴ǖ妮斎胧蔷哂泄烙?jì)的表面法線和曲率數(shù)據(jù)的點(diǎn)云。現(xiàn)有程序是通過PCA(主成分分析)的方法來求取表面法線的。有時(shí)，測量較小的對象時(shí)會產(chǎn)生一些誤差，這些誤差所造成的不規(guī)則數(shù)據(jù)如果直接用來曲面重建會使重建的曲面不光滑或者有漏洞。這些不規(guī)則數(shù)據(jù)很難用統(tǒng)計(jì)分析消除，所以為了建立完整的模型必須對表面進(jìn)行平滑處理和漏洞修復(fù)。

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

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

在擬合區(qū)域的一個(gè)局域子域U上，擬合函數(shù)表示為：

(1)

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

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

考慮下面的加權(quán)離散L2范式[9]：

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

(2)

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

a=(BWBT)-1BWy

但是以上的權(quán)函數(shù)只能用于描述低等級的表面，因此在某些情況下會產(chǎn)生不足的近似值，為了反映現(xiàn)實(shí)情況，重新估計(jì)點(diǎn)較近的采樣點(diǎn)應(yīng)該比估算較遠(yuǎn)的采樣點(diǎn)有更大的影響，所以應(yīng)該重新考慮權(quán)函數(shù)。

2.2 權(quán)函數(shù)的確定

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

(1)點(diǎn)云平滑處理

1.1 研究對象 2014年1月-2014年12月南京市胸科醫(yī)院的門診及住院呼吸系統(tǒng)疾病患者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例；按不同季節(jié)分組，春季（3-5月）1 931例，夏季（6-8月）1 742例，秋季（9-11月）1 650例，冬季（12-2月）1 661例；所有病例均存在呼吸道感染的臨床表現(xiàn)：持續(xù)性咳嗽、發(fā)熱、呼吸急促或呼吸困難；肺部聽診可聞及細(xì)濕啰音等。所有患者均知情同意。

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

(2)點(diǎn)云重采樣進(jìn)行孔洞修補(bǔ)

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

(3)

其中di(x)為新的采樣位置p與第i個(gè)初始采樣位置pi之間的距離。當(dāng)對一個(gè)輸入點(diǎn)云進(jìn)行正確評估時(shí)，這個(gè)權(quán)函數(shù)變得無窮大。為了避免這一問題，此種情況被單獨(dú)處理。參數(shù)α控制區(qū)域鄰近特征對重采樣的影響。因?yàn)闄?quán)函數(shù)與重采樣的位置有關(guān)，對于每一個(gè)采樣點(diǎn)，單獨(dú)計(jì)算新的系數(shù)為：

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

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

①對于一個(gè)點(diǎn)云，創(chuàng)建一個(gè)三角網(wǎng)格。

②重復(fù)以下過程：

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

b.對于一個(gè)孔鄰域計(jì)算投影平面；

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

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

③直到?jīng)]有孔洞存在。

3 實(shí)驗(yàn)結(jié)果

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

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

圖1 貪婪投影三角化算法重建前后點(diǎn)云

圖2 MLS平滑后做重建效果

圖3 MLS重采樣后重建效果

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

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

(2)效率分析

表1記錄了幾種算法程序運(yùn)行的時(shí)間?？梢钥闯鰞?yōu)化后的算法時(shí)間上均有所減少，在重建效果上，圖3與圖4的孔洞進(jìn)行了修補(bǔ)，且兩者相比，圖4的效果更好，運(yùn)行時(shí)間上也比圖3的要少。

表1 幾種算法對比

4 結(jié)論

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

[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] 劉為宏.點(diǎn)云數(shù)據(jù)曲面重建算法及研究[D].秦皇島:燕山大學(xué)，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] 張崇軍,鄭德華,孟慶年.基于移動最小二乘法的點(diǎn)云數(shù)據(jù)擬合方法[J].勘察科學(xué)技術(shù),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的最小二乘配點(diǎn)法[J].強(qiáng)度與環(huán)境, 2000, 15(5):65- 69.

[10] 劉欣.無網(wǎng)格方法[M].北京:科學(xué)出版社,2011.

[11] 谷利國,候振杰.基于三維重建技術(shù)的三角剖分[J].微型機(jī)與應(yīng)用,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

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

2017-01-13)

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

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