0 引言

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

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

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

1 散亂點(diǎn)云的分割

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

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

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

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

2.2 基于差分進(jìn)化算法的隱式曲面求解

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

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

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

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

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

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

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

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

    (1)編碼

    差分進(jìn)化算法采用的是實(shí)數(shù)編碼，如果編碼范圍(搜索空間)過(guò)大，DE收斂慢或早熟(收斂至局部最優(yōu))，或退化為隨機(jī)搜索。編碼范圍越小，DE收斂速度越快，配準(zhǔn)效率越高。因此，確定一個(gè)有限且盡可能小的編碼范圍是必要的。本文需求解的變量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分別為點(diǎn)云P在X、Y、Z三個(gè)坐標(biāo)方向上的最小值和最大值，d為構(gòu)造的包含點(diǎn)云P的立方體包圍盒的對(duì)角線長(zhǎng)度值。

    (2)初始化

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

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

2.2.4 差分進(jìn)化操作

    (1)變異

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

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

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

    (2)交叉

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

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

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

    (3)選擇

    選擇操作是為了確定進(jìn)入下一代種群的個(gè)體，具體為：

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

3 隱式曲面光滑拼接

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

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

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

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

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

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

3.2 算法步驟

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

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

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

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

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

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

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

4.1 不同類(lèi)型點(diǎn)云的重構(gòu)效果

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

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

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

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

[8] 陳龍.散亂點(diǎn)云特征提取和聚類(lèi)精簡(jiǎn)技術(shù)研究[D].綿陽(yáng)：西南科技大學(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] 楊從銳，錢(qián)謙，王鋒，等.改進(jìn)的自適應(yīng)遺傳算法在函數(shù)優(yōu)化中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2018，35(4)：1042-1045.

[13] 武敬民.三維點(diǎn)云處理及隱式曲面三維重構(gòu)技術(shù)的研究與實(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é)院，四川 綿陽(yáng)621010；

2.制造過(guò)程測(cè)試技術(shù)省部共建教育部重點(diǎn)實(shí)驗(yàn)室，四川 綿陽(yáng)621010)