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

張予民

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

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

中圖分類號： TN911.1?34； TP391 文獻(xiàn)標(biāo)識碼： 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 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

對[ψ（t）]進(jìn)行伸縮和平移操作可得：

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

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

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

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

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

對[s（t）]實(shí)現(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）的遞歸操作，進(jìn)行多次小波細(xì)分：

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

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

通過設(shè)置一定的閾值去除原始點(diǎn)云數(shù)據(jù)中的噪聲，最后通過小波重構(gòu)得到高質(zhì)量的原始點(diǎn)云數(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)低通和高通濾波器。

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

4 點(diǎn)云數(shù)據(jù)曲面孔洞修補(bǔ)

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

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

Step1：在非封閉孔洞邊上選擇多個(gè)非噪音點(diǎn)作為控制頂點(diǎn)。

Step2：對控制頂點(diǎn)進(jìn)行曲線邊界擬合操作。

Step3：對邊界曲線進(jìn)行重新采樣，得到新的采樣點(diǎn)。

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

若兩個(gè)相鄰點(diǎn)[Pi，][Pj]的間距[Δ>λ×Δmin，]那么[Pi，][Pj]間需要增加采樣點(diǎn)，[Δ=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]間新增的采樣點(diǎn)數(shù)；[u*i]為新增采樣點(diǎn)的參數(shù)值。

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

為了更加準(zhǔn)確地修補(bǔ)孔洞，提取孔洞區(qū)域的特征面?？锥春椭車畔榭锥脆徑?，厚度可以描述孔洞附近點(diǎn)的多少。設(shè)孔洞和鄰近域間的點(diǎn)為[P1，P2，…，Pn，]如果這些點(diǎn)的平方和最小，那么表示它們構(gòu)成了特征面，設(shè)[P1，P2，…，Pn]的形心為[O，]特征面可采用空間點(diǎn)[O]和單位法向量[n]描述，有：

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

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

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

4.3 計(jì)算孔洞的坐標(biāo)系

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

4.4 移動最小二乘法的點(diǎn)云數(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é)點(diǎn)值；[w（p-pi）]為[pi]的權(quán)函數(shù)。

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

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

式中[B]值表示矩陣。

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)及結(jié)果分析

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

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

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

6 結(jié) 語

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

參考文獻(xiàn)

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

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

[3] 張舜德，朱東波，盧秉恒.反求工程中三維幾何形狀測量及數(shù)據(jù)預(yù)處理[J].機(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] 鐘毅，林德靜.基于移動最小二乘法的點(diǎn)云空洞曲面重建算法[J].北京服裝學(xué)院學(xué)報(bào)，2007，28（3）：9?13.

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

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

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

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

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

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

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

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

[14] 蔣剛.基于SVM和空間投影的點(diǎn)云空洞修補(bǔ)方法[J].計(jì)算機(jī)工程，2012，35（12）：269?271.endprint