基于移動最小二乘法的點云數(shù)據(jù)孔洞修補算法

張予民

摘 要： 由于受到多種因素的綜合作用，點云數(shù)據(jù)不完整，曲面上出現(xiàn)了一些孔洞，為了提高點云數(shù)據(jù)的孔洞修補精度，解決目前一些方法的局限性，提出基于移動最小二乘法的點云數(shù)據(jù)孔洞修補算法。首先對當前點云數(shù)據(jù)孔洞修補研究現(xiàn)狀進行分析，并得到點云數(shù)據(jù)曲面上的孔洞數(shù)據(jù)，采用移動最小二乘法對點云數(shù)據(jù)孔洞進行修補，最后通過具體應(yīng)用實例對其可行性進行測試。結(jié)果表明該方法可以對點云數(shù)據(jù)孔洞進行有效修補，能夠獲得比較理想的點云數(shù)據(jù)曲面重建效果。

關(guān)鍵詞： 點云數(shù)據(jù)； 孔洞修補； 移動最小二乘法； 數(shù)據(jù)處理

中圖分類號： TN911.1?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2017）21?0031?04

Point cloud data hole?filling algorithm based on moving least square method

ZHANG Yumin

（Jiangxi Institute of Economic Administrators， Nanchang 330088， China）

Abstract： In order to improve the hole?filling precision of point cloud data and solve some limitations of the current methods， a point cloud data hole?filling algorithm based on moving least square method is proposed. The research status of hole filling of point cloud data is analyzed to get the hole data on the curved surface of the point cloud data. The moving least square method is used to repair the holes of the point cloud data. Its feasibility was tested with a specific application example. The results show that the method can repair the hole of the point cloud data effectively， and get the ideal curved surface reconstruction effect of point cloud data.

Keywords： point cloud data； hole filling； moving least square method； data processing

0 引 言

在點云數(shù)據(jù)采集過程中，由于設(shè)備自身原因、外界環(huán)境的影響，原始點云數(shù)據(jù)存在一些誤差和噪聲，出現(xiàn)大量的孔洞，直接影響后續(xù)的點云數(shù)據(jù)曲面建模，為了獲得更優(yōu)的點云數(shù)據(jù)重建效果，需要對點云數(shù)據(jù)的孔洞進行修補處理[1?2]。

為了提高點云數(shù)據(jù)孔洞修補精度，提出基于移動最小二乘法的點云數(shù)據(jù)孔洞修補算法。首先采集點云數(shù)據(jù)曲面上的孔洞數(shù)據(jù)，然后采用移動最小二乘法對點云數(shù)據(jù)曲面進行擬合和孔洞修補，最后通過具體應(yīng)用實例對本文方法進行驗證，結(jié)果表明，本文方法能夠獲得理想的點云數(shù)據(jù)孔洞修補效果。

1 點云數(shù)據(jù)處理與孔洞修補的研究現(xiàn)狀

為了解決點云數(shù)據(jù)處理中存在的問題，學(xué)者們一直致力于該問題的研究，當前出現(xiàn)了一些點云數(shù)據(jù)處理和孔洞修補算法[3?4]。點云數(shù)據(jù)處理包括數(shù)據(jù)配準、數(shù)據(jù)分割、數(shù)據(jù)去噪、數(shù)據(jù)簡化等方法，這些方法均存在各自的優(yōu)缺點[5?6]。采集點云數(shù)據(jù)時，有時不能一次提取目標的完整信息，需要進行多個節(jié)點的描述，這樣需要將多個節(jié)點數(shù)據(jù)轉(zhuǎn)換到同場景中，實現(xiàn)點云數(shù)據(jù)配準，提高數(shù)據(jù)的完整性[7]。點云數(shù)據(jù)的配準分為兩類：基于有特征的點云數(shù)據(jù)配準和基于無特征的點云數(shù)據(jù)配準，有特征的點云數(shù)據(jù)配準過度依賴特征點的提取精度，而無特征的點云數(shù)據(jù)配準工作時間長，配準效率低[8?9]。點云數(shù)據(jù)分割將點云數(shù)據(jù)劃分為多個小區(qū)域，對每一個區(qū)域建立自然曲面；點云數(shù)據(jù)去噪采用不同的去噪算法消除點云數(shù)據(jù)中的噪聲，如有傅里葉變換的點云數(shù)據(jù)去噪算法，但這種算法去噪效率低[10]。點云數(shù)據(jù)簡化主要是去除點云數(shù)據(jù)中的冗余信息，但有時會去除一些有用的特征信息[11]。當前點云數(shù)據(jù)孔洞修補方法分為體積元素和三角網(wǎng)格兩種。體積元素采用體積元素描述點云數(shù)據(jù)目標孔洞修補模型，該類方法簡單、執(zhí)行速度快，但當點云數(shù)據(jù)量大時，孔洞修補效率低[12]；三角網(wǎng)格采用三角網(wǎng)格對點云數(shù)據(jù)目標進行孔洞修補，當點云數(shù)據(jù)分布均勻，數(shù)據(jù)規(guī)模小時，點云數(shù)據(jù)曲面孔洞修補效果好，但當數(shù)據(jù)規(guī)模大時，孔洞修補時間長。

2 點云數(shù)據(jù)技術(shù)

點云數(shù)據(jù)技術(shù)是一種高精度的測量技術(shù)，根據(jù)脈沖測距得到距離值[S，]根據(jù)精密時鐘測量每個點的橫向和縱向掃描角度觀測值[α]和[θ，]收集反射強度為[I，]掃描點[P（x，y，z）]的三維坐標為：

[x=Scosαcosθy=Ssinαcosθz=Ssinθ] （1）

掃描點的反射強度和顏色信息主要用于后續(xù)數(shù)據(jù)處理，點云數(shù)據(jù)系統(tǒng)內(nèi)部坐標系如圖1所示。

相對于傳統(tǒng)測量技術(shù)，點云數(shù)據(jù)技術(shù)的精度更高，具有良好的非接觸性和高效率，可應(yīng)用于許多人無法觸及的環(huán)境。采用點云數(shù)據(jù)技術(shù)對目標進行處理，可以得到大量數(shù)據(jù)，即點云數(shù)據(jù)（Point Cloud），從而可以用孔洞修補一些實體表面模型，被廣泛應(yīng)用于醫(yī)學(xué)、文物保護、市政建設(shè)等領(lǐng)域。點云數(shù)據(jù)技術(shù)的工作流程如圖2所示。endprint

3 點云數(shù)據(jù)的去噪處理

由于受到采集設(shè)備和其他因素的作用，原始點云數(shù)據(jù)存在一些噪聲，它們降低了曲面重建質(zhì)量，因此本文采用小波變換去除原始點云數(shù)據(jù)中的噪聲，以提高點云數(shù)據(jù)孔洞修補效果。設(shè)[ψt∈L2（R），][ψt]的傅里葉變換為[ψ（t）]，如果[ψ（t）]滿足式（2）的條件，那么就可以進行小波變換操作：

[Cψ=Rψ（t）2tdt<∞] （2）

式中[ψ（t）]為母小波。

對[ψ（t）]進行伸縮和平移操作可得：

[ψa，bt=1aψt-ba， a，b∈R，a≠0] （3）

式中：[ψa，bt]為小波序列；[a]和[b]分別為伸縮和平移因子。

設(shè)含有噪聲的原始點云數(shù)據(jù)為：

[s（t）=x（t）+n（t）] （4）

式中[s（t）]和[n（t）]分別為真實信號和噪聲。

對[s（t）]實現(xiàn)離散變換產(chǎn)生[s（n），][n=0，1，2，…，N-1，]小波變換可以描述為：

[W2jsk=12jn=0N-1snψ*（2-jn-k）， j，k∈Z] （5）

[xf（j，k）]和[Wf（j，k）]分別表示尺度系數(shù)和小波系數(shù)，通過式（6）的遞歸操作，進行多次小波細分：

[xf（j+1，k）=xf（j，k）*h（j，k）Wf（j+1，k）=Wf（j，k）*g（j，k）] （6）

式中：[xf（0，k）]為真實信號；[h]和[g]為低通和高通濾波器。

通過設(shè)置一定的閾值去除原始點云數(shù)據(jù)中的噪聲，最后通過小波重構(gòu)得到高質(zhì)量的原始點云數(shù)據(jù)，重構(gòu)公式具體為：

[xf（j-1，k）=xf（j，k）*h0（j，k）+Wf（j，k）*g0（j，k）] （7）

式中[h0]和[g0]為重構(gòu)低通和高通濾波器。

采用小波變換對含有噪聲的原始點云數(shù)據(jù)進行去噪，結(jié)果如圖3所示。

4 點云數(shù)據(jù)曲面孔洞修補

4.1 孔洞的檢測和修復(fù)

點云數(shù)據(jù)重建過程中，會產(chǎn)生一些孔洞，需要對這些孔洞進行修補，而孔洞的檢測是孔洞修補的基礎(chǔ)。設(shè)點[P]存在于邊界上，根據(jù)K?鄰近點得到曲面邊界的所有特征點。根據(jù)邊界特征點的定義，可以得到兩類孔洞：封閉孔洞和非封閉孔洞。為了全面地修補點云數(shù)據(jù)的孔洞，首先將非封閉孔洞轉(zhuǎn)化為封閉孔洞，然后進行修補，非封閉孔洞轉(zhuǎn)化為封閉孔洞的步驟為：

Step1：在非封閉孔洞邊上選擇多個非噪音點作為控制頂點。

Step2：對控制頂點進行曲線邊界擬合操作。

Step3：對邊界曲線進行重新采樣，得到新的采樣點。

Step4：根據(jù)原始邊界點與新樣點建立新的孔洞邊界。

若兩個相鄰點[Pi，][Pj]的間距[Δ>λ×Δmin，]那么[Pi，][Pj]間需要增加采樣點，[Δ=ui-uj，][ui]和[uj]分別為[Pi]和[Pj]的關(guān)聯(lián)參數(shù)值，有：

[n=IntΔ（λ×Δmin）] （8）

[u*i=ui+Δn×i， i=1，2，…，n-1] （9）

式中：[n]表示[Pi，][Pj]間新增的采樣點數(shù)；[u*i]為新增采樣點的參數(shù)值。

4.2 提取孔洞鄰近域的特征面

為了更加準確地修補孔洞，提取孔洞區(qū)域的特征面。孔洞和周圍信息為孔洞鄰近域，厚度可以描述孔洞附近點的多少。設(shè)孔洞和鄰近域間的點為[P1，P2，…，Pn，]如果這些點的平方和最小，那么表示它們構(gòu)成了特征面，設(shè)[P1，P2，…，Pn]的形心為[O，]特征面可采用空間點[O]和單位法向量[n]描述，有：

[O=1ni=0nPi] （10）

那么相應(yīng)的構(gòu)造矩陣為：

[M=P1-OP2-O?Pn-O] （11）

4.3 計算孔洞的坐標系

設(shè)[d（Pi，O）≥d（Pj，O），][?j≠i，]那么[Pd]表示[P1，P2，…，Pn]的最遠點，[d（x，y）]表示[x]和[y]間的距離，[（Pd-O）×n，][n×（Pd-O）×n，][n]為孔洞坐標系的[u，][v，][s]軸。

4.4 移動最小二乘法的點云數(shù)據(jù)曲面重建

設(shè)[U]為擬合區(qū)域的子域，那么移動最小二乘法的擬合函數(shù)為：

[s（p）=i=0mai（p）Mi（p）=MT（p）a（p）] （12）

式中：[p∈U；][a（p）=a1（p），a2（p），…，am（p）T]為待求系數(shù)；[M（p）]為基函數(shù)，擬合函數(shù)變?yōu)椋?/p>

[s（p）=a0（p）+a1（p）u+a2（p）v+a3（p）u2+a4（p）uv+a5（p）v2] （13）

加權(quán)離散[L2]范式定義如下：

[J=i=1Nw（p-pi）s（p）-fi=i=1Nw（p-pi）a0（p）+a1（p）u+a2（p）v+a3（p）u2+a4（p）uv+a5（p）v2-fi] （14）

式中：[fi]為[P=Pi]處的節(jié)點值；[w（p-pi）]為[pi]的權(quán)函數(shù)。

為了對系數(shù)[a（p）]進行求解，對[a]進行求導(dǎo)，且[?J?a=0]，那么有：

[a=（BWBT）-1BWf] （15）

式中[B]值表示矩陣。

在移動最小二乘法中，權(quán)函數(shù)[wi（p）]與[p-pi]之間是一種單調(diào)遞減的關(guān)系，因此[wi（p）]隨著估算點變化而變化，權(quán)函數(shù)的計算公式為：

[wi（p）=e-μd2i（p）d2i（p）] （16）

權(quán)函數(shù)與重新采樣點密切相關(guān)，對系數(shù)[a（p）]要進行重新計算，即：endprint

[a（p）=BW（p）BT-1BW（p）f] （17）

式中[W（p）]為一個對角線的取值。

隱含曲面的函數(shù)方程計算步驟如下：

Step1：把[P1，P2，…，Pn]投影到特征面上，得到孔洞坐標系下的[s1，s2，…，sn，]計算[f]向量值。

Step2：把[P1，P2，…，Pn]投影到[u，v]軸上，計算坐標值[u1，u2，…，un，][v1，v2，…，vn，]得到[B]的值。

Step3：根據(jù)重新采樣點和[P1，P2，…，Pn]在特征面上的投影點得到每一個點的權(quán)值。

Step4：根據(jù)[B，W]和[f]計算求解擬合曲面的系數(shù)[a0，a1，a2，a3，a4，a5，]然后計算重新采樣點的曲面函數(shù)方程，實現(xiàn)點云數(shù)據(jù)描述的曲面孔洞修補。

5 實驗及結(jié)果分析

為了測試本文方法的有效性，采用VC++ 6.0進行點云數(shù)據(jù)孔洞修補實驗，以兔子作為實驗對象，點云數(shù)據(jù)孔洞修補和曲面重建實驗結(jié)果如圖4所示。

從圖4可以看出，本文方法獲得了較理想的點云數(shù)據(jù)孔洞修補效果，實驗結(jié)果驗證了本文方法的有效性。

為了分析本文方法的優(yōu)越性，選擇文獻[13?14]的點云數(shù)據(jù)孔洞修補方法進行對比實驗，各方法的孔洞修補精度和孔洞修補速度如表1所示，從表1可以看出，與其他點云數(shù)據(jù)曲面孔洞修補方法相比，本文方法的曲面孔洞修補精度有所提高，孔洞修補速度有所加快，具有比較明顯的優(yōu)越性。

6 結(jié) 語

點云數(shù)據(jù)技術(shù)可以快速獲得目標對象的三維數(shù)據(jù)和信息，是當前研究中的熱點。在點云數(shù)據(jù)采集過程中，受到外界環(huán)境的影響，數(shù)據(jù)中存在一定的錯誤和噪聲，對后續(xù)曲面重建產(chǎn)生了負面影響，為了提高點云數(shù)據(jù)孔洞修補的精度，提出基于移動最小二乘法的點云數(shù)據(jù)孔洞修補算法。通過具體應(yīng)用實例對方法的性能進行測試，結(jié)果表明，本文方法可以有效去除點云數(shù)據(jù)中的噪聲，減少誤差，采用最小二乘法得到了點云數(shù)據(jù)曲面孔洞修補最優(yōu)平面，在提高點云數(shù)據(jù)孔洞修補速度的同時，提高了孔洞修補精度，具有一定的實際應(yīng)用價值。

參考文獻

[1] 宋宏.三維激光掃描測量技術(shù)及其應(yīng)用分析[J].測繪技術(shù)裝備，2008，10（2）：40?43.

[2] 劉大峰，廖文和.散亂點云去噪算法的研究與實現(xiàn)[J].東南大學(xué)學(xué)報（自然科學(xué)版），2007，37（6）：1109?1111.

[3] 張舜德，朱東波，盧秉恒.反求工程中三維幾何形狀測量及數(shù)據(jù)預(yù)處理[J].機電工程技術(shù)，2001（1）：7?10.

[4] XU Yuanchun， JIA Jianhua. Adaptive spectral clustering ensemble selection via re?sampling and population?based incremental learning algorithm [J]. Wuhan University journal of natural sciences， 2011， 16（3）： 228?238.

[5] 鐘毅，林德靜.基于移動最小二乘法的點云空洞曲面重建算法[J].北京服裝學(xué)院學(xué)報，2007，28（3）：9?13.

[6] 馬淑梅，張海波，李愛平.基于覆蓋二元Lagrange插值的三維激光掃描數(shù)據(jù)切片技術(shù)[J].機械設(shè)計與研究，2010，26（6）：91?94.

[7] 馬騰，龍翔，馮路，等.點云模型的譜聚類分割[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2012，24（12）：1549?1558.

[8] 李元旺，黃文明，溫佩芝，等.空間超限鄰域點云去噪算法的研究與實現(xiàn)[J].計算機系統(tǒng)應(yīng)用，2010，19（3）：35?38.

[9] 鄭海峰.基于多尺度Retinex的超聲圖像去噪及增強技術(shù)[J].激光雜志，2016，37（2）：71?73.

[10] 田青，梁榮華，毛劍飛.面向非勻點云擬合的RSR移動最小二乘法[J].計算機工程與應(yīng)用，2009，43（35）：153?156.

[11] 羅先波，鐘約先，李仁舉.三維掃描系統(tǒng)中的數(shù)據(jù)配準技術(shù)[J].清華大學(xué)學(xué)報（自然科學(xué)版），2004，44（8）：1104?1106.

[12] 韓江，江本赤，夏鏈，等.基于輪廓關(guān)鍵點的B樣條曲線擬合算法[J].應(yīng)用數(shù)學(xué)和力學(xué)，2015，36（4）：423?431.

[13] 袁紅星，吳少群，朱仁祥，等.散亂三維激光掃描數(shù)據(jù)的高階平滑隱式曲面重建[J].計算機應(yīng)用研究，2013，30（5）：1593?1595.

[14] 蔣剛.基于SVM和空間投影的點云空洞修補方法[J].計算機工程，2012，35（12）：269?271.endprint