0 引言

    近年,，在逆向工程,、地質(zhì)地形建模、智慧城市,、生物醫(yī)學(xué)等領(lǐng)域,，點云的曲面重構(gòu)技術(shù)得到了大量研究和廣泛應(yīng)用^[1]。點云曲面重構(gòu)的本質(zhì)是實現(xiàn)數(shù)據(jù)點模型到曲面模型的轉(zhuǎn)變,。隱式曲面重構(gòu)因能夠較好地重建出形狀復(fù)雜的點云模型的表面,，使得許多學(xué)者進行了大量研究。

    文獻[2]提出的徑向基函數(shù)曲面重構(gòu)方法重構(gòu)的曲面細節(jié)特征較好,，但在重構(gòu)數(shù)據(jù)量大的點云時,，將迅速增大計算量，且降低曲面重構(gòu)效果,，也存在重構(gòu)曲面不夠光滑的問題,。文獻[3]提出的基于元球造型技術(shù)的隱式曲面重建算法能很好地逼近沒有尖銳特征的物體，但對非封閉模型會出現(xiàn)變形,。文獻[4]提出的基于橢球約束的隱式曲面重構(gòu)方法對小規(guī)模封閉模型點云效果較好,，但對于大規(guī)模散亂點云，其效率低下且有突出冗余,。文獻[5]提出的保特征的隱式曲面重構(gòu)方法先對點云數(shù)據(jù)建立八叉樹拓撲結(jié)構(gòu),，再進行局部二次曲面求解，最后求解全局未知參數(shù),，對小規(guī)模的散亂點云通過調(diào)節(jié)采樣點的鄰近點數(shù)量能得到較優(yōu)的重構(gòu)效果,，但在未知量的求取過程中，人為參與過多,，求解繁瑣且效率不高,。文獻[6]通過對原始點云進行八叉樹劃分，建立粗,、細層數(shù)據(jù),，再進行徑向基隱式曲面重構(gòu)，對非封閉模型可能存在失真的情況,，對閉合點云數(shù)據(jù)質(zhì)量較好,，但設(shè)定參數(shù)是通過多次實驗人為選取，不能達到智能計算,。

    基于以上分析,，本文提出一種基于隱式函數(shù)的大規(guī)模散亂點云自適應(yīng)重構(gòu)方法，首先利用自適應(yīng)八叉樹提供與模型密度相關(guān)的分割區(qū)域點云數(shù)據(jù),，以分解處理含數(shù)萬個點的點云,；然后在各子區(qū)域建立基于徑向基函數(shù)的隱式元球模型,，以保證局部曲面的光滑性,，利用自適應(yīng)差分進化算法智能求解元球模型隱式函數(shù),；最后利用改進的對數(shù)指數(shù)加權(quán)拼接算法對局部曲面進行光滑拼接，以生成一個高質(zhì)的整體曲面模型,。

1 散亂點云的分割

    為了在微機上實現(xiàn)數(shù)據(jù)量龐大的散亂點云數(shù)據(jù)的曲面重構(gòu),，利用分而自治的思想^[7]，建立點云模型的三維空間八叉樹結(jié)構(gòu),。本文是以采樣點數(shù)據(jù)為輸入來求取擬合曲面,，以遞歸深度或邊長小于設(shè)定閾值為分割終結(jié)條件的傳統(tǒng)八叉樹分割法將增加計算量和降低算法效率。因此本文采用以節(jié)點包含的點的數(shù)量為劃分終結(jié)條件的自適應(yīng)八叉樹,，詳細步驟見文獻^[8],。

2 點云的隱式曲面重構(gòu)

2.1 徑向基函數(shù)隱式曲面表示

    本文由于是將大規(guī)模的散亂點云先分割再進行曲面重構(gòu)的，因此采用一種緊支撐徑向基隱式函數(shù)來表示重構(gòu)曲面,，即metaball模型函數(shù)^[9-10],，直接對采樣點進行曲面擬合，無需點的法向量等信息,。其一般形式為：

2.2 基于差分進化算法的隱式曲面求解

    差分進化(Differential Evolution,，DE)算法是模仿自然界生物進化發(fā)展規(guī)律形成的一種隨機啟發(fā)式搜索和群體智能優(yōu)化方法，借鑒了“優(yōu)勝劣汰,、適者生存”的原則,。本文將大規(guī)模的散亂點云進行分割后，在分割的子區(qū)域建立隱式曲面函數(shù),，再運用差分進化算法自適應(yīng)求解metaball中心C={c_k(c_kx,，c_ky，c_kz)|k=1,，2,，…，m},、metaball半徑ek和形狀參數(shù)?姿k,，最后得到最佳逼近的隱式曲面函數(shù)f(x)。首先確定目標函數(shù)和適應(yīng)度函數(shù),，并進行種群的初始化,；然后根據(jù)差分進化算法的變異、交叉,、選擇操作不斷迭代,；最后找出最優(yōu)的metaball中心、metaball半徑和形狀參數(shù),。

2.2.1 目標函數(shù)的建立

    點云的曲面重構(gòu)是為了盡可能擬合原始點云數(shù)據(jù)的最佳逼近曲面,，所以本文將平均殘差平方和(Residual Mean Squares,，RMS)最小作為差分進化算法的目標，采用的目標函數(shù)為：

式中,，p_i∈P是原始點云數(shù)據(jù)中的點,，n為點云中點的數(shù)量。

2.2.2 適應(yīng)度函數(shù)

    在差分進化算法中,，本文需要制定一個衡量解的優(yōu)劣并增加解的辨識度的標準,，即建立適應(yīng)度函數(shù)。本文的目標函數(shù)是平均殘差平方和最小,，RMS值越小的個體,，其適應(yīng)度值f_fit應(yīng)越大，說明個體越優(yōu)良,，被選擇的概率就越大,。差分進化算法是對適應(yīng)度函數(shù)值的最大化進行尋優(yōu)，而本文metaball模型參數(shù)的優(yōu)化選擇則是最小化尋優(yōu)問題,，因此需要將適應(yīng)度函數(shù)作如下轉(zhuǎn)換：

2.2.3 種群實數(shù)編碼和初始化

    本文需利用差分進化算法智能優(yōu)化求解使目標函數(shù)最小的metaball中心,、半徑和形狀參數(shù)(共5個變量)，可描述為(c_kx,，c_ky,，c_kz，e_k,，λ_k),。

    (1)編碼

    差分進化算法采用的是實數(shù)編碼，如果編碼范圍(搜索空間)過大,，DE收斂慢或早熟(收斂至局部最優(yōu)),，或退化為隨機搜索。編碼范圍越小,，DE收斂速度越快,，配準效率越高。因此,，確定一個有限且盡可能小的編碼范圍是必要的,。本文需求解的變量c_kx∈[x_min，x_max],，c_ky∈[y_min,，y_max]，c_kz∈[z_min,，z_max],，e_k∈(0，d],，λ_k∈(0,，100],，其中x_min，x_max,、y_min,，y_max、z_min,，z_max分別為點云P在X,、Y,、Z三個坐標方向上的最小值和最大值,，d為構(gòu)造的包含點云P的立方體包圍盒的對角線長度值。

    (2)初始化

    在搜索空間中隨機產(chǎn)生I個個體,，每個個體由J維向量組成,。

式中，J=5,；T_MAX,、T_MIN分別為第j個變量在搜索空間的最大值、最小值,；r為0～1之間的隨機數(shù),。

2.2.4 差分進化操作

    (1)變異

    在第g代從種群中隨機選擇3個個體T_p1、T_p2和T_p3,，且i≠p₁≠p₂≠p₃,，則變異操作為：

式中，CF為變異因子,，T_{p2 j(g})-T_{p3 j(g)}為差異化變量,；p₁、p₂和p₃為隨機整數(shù),，表示個體在種群中的序號,，為加快收斂速度個體，p₁可選擇為當代種群的最好個體,。

    針對傳統(tǒng)差分進化算法在整個求解過程中變異因子CF始終不變可能導(dǎo)致算法效率下降與過早收斂的問題,，本文采用了自適應(yīng)的變異因子公式^[12]。

    (2)交叉

    交叉操作是為了增加種群的多樣性,，具體操作為：

式中,，r為0～1之間的隨機數(shù)，CR為交叉因子,。

    針對傳統(tǒng)差分進化算法在整個求解過程中交叉因子CR始終不變可能導(dǎo)致過早收斂和收斂變慢的問題,，本文采用了自適應(yīng)的交叉因子公式^[12]。

    (3)選擇

    選擇操作是為了確定進入下一代種群的個體,，具體為：

式中,，f_fit(v_i)為個體v_i的適應(yīng)度值,，f_fit(T_i)為個體T_i的適應(yīng)度值。

3 隱式曲面光滑拼接

    本文選用文獻[13]提出的對數(shù)指數(shù)加權(quán)拼接算法并加以改進,，對局部隱式曲面進行光滑拼接,，以得到一張原始點云模型所描述的完整曲面。該方法是對各分割區(qū)域兩兩相鄰拼接,，通過不斷遞歸,，實現(xiàn)所有局部曲面的光滑拼接，最終得到完整的曲面模型,。拼接函數(shù)為：

式中,，f₁和f₂分別為需拼接的兩相鄰分割區(qū)域的隱式曲面函數(shù)，α為拼接控制參數(shù),。α的取值關(guān)系到拼接的光滑程度,，在文獻[13]中給出的是0.1～10之間的取值范圍，需根據(jù)多次實驗的效果來人為確定α的取值,。在此基礎(chǔ)上,，本文利用差分進化算法來自適應(yīng)地得到控制參數(shù)α的最優(yōu)值。

3.1 建立目標函數(shù)和適應(yīng)度函數(shù)

    為保證原始點云盡可能在拼接后的曲面上,，建立的目標函數(shù)為：

式中,， p_i為兩相鄰區(qū)域的原始點云中的點，n為兩相鄰區(qū)域的原始點云數(shù)量,。

    則相應(yīng)的適應(yīng)度函數(shù)為：

3.2 算法步驟

    本文提出的自適應(yīng)隱式曲面光滑拼接算法進化操作與文中2.2節(jié)類似,，則算法步驟為：

    (1)在變量域[0.1，10]初始化隨機種群M,；

    (2)依次進行變異,、交叉和選擇操作，直到滿足進化終止條件,，得到最優(yōu)α值的拼接函數(shù),；

    (3)在分割區(qū)域遞歸進行基于自適應(yīng)差分進化算法的拼接函數(shù)求解，并進行隱式曲面拼接操作,；

    (4)輸出完整曲面模型,，算法結(jié)束。

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

    本文提出了一種對大規(guī)模散亂點云數(shù)據(jù)實現(xiàn)快速,、高質(zhì)地曲面重構(gòu)的方法,，所提出的算法采用C++和MATLAB語言編寫，在主頻3.20 GHz,、內(nèi)存8 GB的Intel Core i5-6500的計算機上實現(xiàn),。隱式曲面繪制是利用Marching Cube算法^[14]提取零等值面。實驗中所有原始點云模型均來自斯坦福大學(xué)計算機圖形學(xué)實驗室。

4.1 不同類型點云的重構(gòu)效果

    為驗證本文算法的有效性,，將其應(yīng)用于2種不同規(guī)模點云進行重構(gòu),，以體現(xiàn)本文算法在不同規(guī)模點云模型的魯棒性。如圖1所示,，圖1(a)為bunny點云,，該模型規(guī)模較小,；圖1(b)為bunny曲面模型,，可見本文算法對規(guī)模較小的模型能較好地重構(gòu)出曲面，表面光滑且細節(jié)特征較好,；圖1(c)為dragon點云,，該模型規(guī)模較大且特征較復(fù)雜；圖1(d)為重構(gòu)出的dragon曲面模型,，可以看出重構(gòu)曲面細節(jié)特征還原度好,，表面也非常光滑,。

    表1給出了本文算法處理以上2種模型的統(tǒng)計信息,，包括原始點云的點數(shù)、重構(gòu)時間和擬合誤差,。將每一個原始點坐標代入拼接函數(shù),，進而計算出所有點的殘差平方和，選取全局殘差平方和的最大值為最大擬合誤差,，計算出所有點的殘差平方和的平均值為平均擬合誤差,。從表1可以得出，本文算法對不同規(guī)模的點云都具有很好的適應(yīng)性,，重構(gòu)效果好,，耗時也在可接受范圍內(nèi)。

4.2 不同重構(gòu)算法重構(gòu)結(jié)果對比

    為驗證本文算法的有效性,，將本文算法與文獻[3],、文獻[6]的算法進行對比分析。在模型的選取上為了體現(xiàn)算法的適應(yīng)性,，選擇兩種不同的模型：一種為封閉的點云模型horse,；另一種為未封閉的點云模型hand。兩類模型的重構(gòu)效果圖如圖2,、圖3所示,。

    圖2(a)為horse原始點云；圖2(b)為采用文獻[3]算法重構(gòu)出的曲面,，可見表面光滑但細節(jié)特征有所丟失,；圖2(c)為采用文獻[6]算法重構(gòu)出的曲面，可見細節(jié)特征有所體現(xiàn)，但表面不夠光滑,；圖2(d)為采用本文算法重構(gòu)出的曲面,，可見表面光滑且細節(jié)特征較明顯。從表2對horse模型重構(gòu)的統(tǒng)計信息也可得出本文算法的重構(gòu)效果最好,，但時間上因為需要對原始點云先分割再拼接,，所以不夠理想。

    圖3(a)為hand原始點云,；圖3(b)重構(gòu)出的曲面較明顯的問題是在手腕處因為沒有點數(shù)據(jù)控制形狀所以嚴重走樣,；圖3(c)重構(gòu)出的曲面因為在重構(gòu)過程中產(chǎn)生了額外的零水平集所以部分失真；圖3(d)采用本文算法重構(gòu)出的曲面表面光滑,，在未封閉的手腕處無冗余突出,，效果最好。從表2對hand模型重構(gòu)的統(tǒng)計信息也可得出本文算法的重構(gòu)曲面平均擬合誤差最小,，雖然用時不是最少的,，但算法性能比是最高的。

5 結(jié)論

    本文提出了一種自適應(yīng)重構(gòu)大規(guī)模散亂點云的方法,，采用自適應(yīng)八叉樹分割出局部點云,，以自適應(yīng)差分進化算法智能求解局部點云的隱式曲面函數(shù)，采用改進的拼接算法以得到完整的曲面模型,。將本文方法與文獻[3],、文獻[6]方法的重構(gòu)效果進行了對比，結(jié)果顯示,，采用本文方法重構(gòu)出的曲面表面光滑,，細節(jié)特征清晰準確，在未封閉區(qū)域無突出冗余,。雖然本文方法對大規(guī)模點云的重構(gòu)是非常有效的,，但是為保證較好的細節(jié)特征，是以增大分割量為代價的,，導(dǎo)致了重構(gòu)時間的增加,。因此，如何平衡好重構(gòu)效果和耗時的關(guān)系是下一步的研究內(nèi)容,。

參考文獻

[1] 莫建文,，龐建鏗，袁華.基于VTK的三維點云曲面重建研究[J].電子技術(shù)應(yīng)用,，2015,，41(4)：156-158.

[2] 符艷青.基于改進的徑向基函數(shù)網(wǎng)絡(luò)的3D隱式曲面重構(gòu)算法研究[D].杭州：中國計量學(xué)院，2014.

[3] 劉圣軍,，韓旭里,，金小剛.空間采樣點的隱式曲面表示與優(yōu)化[J].中國圖象圖形學(xué)報,，2011，16(3)：480-487.

[4] 韓燮,，武敬民,，韓慧妍，等.基于橢球約束的徑向基函數(shù)隱式曲面重建[J].圖學(xué)學(xué)報,，2014,，35(4)：504-510.

[5] 田建磊.一種保特征的隱式曲面算法[J].計算機工程與應(yīng)用，2011,，47(1)：208-210.

[6] 張娟,，侯進，吳婷婷,，等.三維散亂點云模型的快速曲面重建算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,，2018，30(2)：235-243.

[7] 劉恩江,，宋云勝,，梁吉業(yè).基于數(shù)據(jù)劃分的核嶺回歸加速算法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報，2018,，48(4)：284-289.

[8] 陳龍.散亂點云特征提取和聚類精簡技術(shù)研究[D].綿陽：西南科技大學(xué),，2017.

[9] BLINN J.A generalization of algebraic surface drawing[C].Conference on Computer Graphics & Interactive Techniques.ACM，1982.

[10] NISHIMURA H,，HIRAI M,，KAWAI T，et al.Object modeling by distribution function and a method of image generation[J].The Transactions of the Institute of Electronics and Communication Engineers of Japan,，1985，J68-D(4)：718-825.

[11] MURAKAMI S,，ICHIHARA H.On a 3D display method by metaball technique[J].Journal of the Electronics Communication,，1987，70(8)：1607-1615.

[12] 楊從銳,，錢謙,，王鋒，等.改進的自適應(yīng)遺傳算法在函數(shù)優(yōu)化中的應(yīng)用[J].計算機應(yīng)用研究,，2018,，35(4)：1042-1045.

[13] 武敬民.三維點云處理及隱式曲面三維重構(gòu)技術(shù)的研究與實現(xiàn)[D].太原：中北大學(xué)，2014.

[14] LORENSEN W E,，CLINE H E.Marching cubes：a high resolution 3D surface construction algorithm[J].ACM Siggraph Computer Graphics,，1987，21(4)：163-169.

作者信息:

江  盟1,，2,，蔡  勇1，2，張建生1,，2

(1.西南科技大學(xué) 制造科學(xué)與工程學(xué)院,，四川 綿陽621010；

2.制造過程測試技術(shù)省部共建教育部重點實驗室,，四川 綿陽621010)