基于RBF和POU的曲面重建方法

鄧珍榮，彭希為，黃文明

（1.桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西桂林541004；2.中國農(nóng)業(yè)銀行吉安分行，江西吉安343000）

0 引 言

曲面重建是逆向工程中最重要的關(guān)鍵技術(shù)，目前已經(jīng)取得了不少研究成果。在諸多曲面重建方法中，隱式曲面重建方法引起了各國學(xué)者越來越多的關(guān)注。1982年，F(xiàn)ranke率先使用徑向基函數(shù)解決點(diǎn)云數(shù)據(jù)的插值問題。1999年，Turk提出了變分隱式曲面重建方法，該方法的時間復(fù)雜度和空間復(fù)雜度分別為O（N3）和O（N2）。此后，Carr使用貪婪算法對點(diǎn)云數(shù)據(jù)進(jìn)行快速曲面重建，使得時間復(fù)雜度由O（N3）降為O（Nlog N），空間復(fù)雜度也由O（N2）降為O（N），實(shí)現(xiàn)了大規(guī)模點(diǎn)云數(shù)據(jù)的隱式曲面重建。但是，該方法使用的徑向基函數(shù)仍然是全局支撐函數(shù)，并且需要為每個插值中心增加兩個離面約束點(diǎn)。這使得該方法的效率受到一定程度的影響，導(dǎo)致該方法難以被廣泛應(yīng)用。除此之外，Morse、Ohtake、Tobor等人也分別提出了不同的基于徑向基函數(shù)的曲面重建方法。隨著該方法不斷的改進(jìn)，已從最初只能對幾千個數(shù)據(jù)點(diǎn)進(jìn)行曲面重建發(fā)展到現(xiàn)在可以實(shí)現(xiàn)大規(guī)模點(diǎn)云數(shù)據(jù)的多尺度曲面重建。無論是重建曲面的品質(zhì)，還是重建效率都有了大幅度提高。

在文獻(xiàn)［6－8］的方法基礎(chǔ)上，本文提出了一種基于RBF和POU的曲面重建方法，根據(jù)點(diǎn)云模型的形狀和分布密度，采用二叉樹遞歸分解點(diǎn)云空間，能夠有效控制點(diǎn)云空間的分解程度，確保重建曲面的連續(xù)性和光滑性。

1 理論基礎(chǔ)

1.1 徑向基函數(shù)插值理論

給定三維空間中的一個點(diǎn)集P＝｛pj∈R3｜j＝1，2，…，N｝，實(shí)數(shù)集H＝｛hj∈R｜j＝1，2，…，N｝是P對應(yīng)的約束值。如果可以構(gòu)造一個標(biāo)量函數(shù)f:R3→R，使得

則由方程f（p）＝0可以定義一個隱式曲面。

對于方程f（p）＝0所描述的曲面，其光滑性可以通過能量函數(shù)E來衡量

如果該曲面不存在曲率變化較大的區(qū)域，則能量函數(shù)E的值較小。文獻(xiàn)［2］指出使用徑向基函數(shù)建立的隱式曲面方程可以使能量函數(shù)E取得最小值，這就保證了隱式曲面的連續(xù)性和光滑性。其表達(dá)形式為

其中，p表示隱式曲面上的任意一點(diǎn)；pj表示用于定義隱式曲面方程的數(shù)據(jù)點(diǎn)，稱為約束點(diǎn)或者插值中心；是徑向基函數(shù)；為歐幾里德范數(shù)；ωi是的權(quán)系數(shù)；R（p）是一個一階多項(xiàng)式，用于確保隱式曲面的連續(xù)性。對于隱式曲面上的任意一點(diǎn)（x，y，z），R（p）的表達(dá)形式為R（p）＝r0＋r1x＋r2y＋r3z。

根據(jù)約束值的不同，用于定義隱式曲面方程的約束點(diǎn)可以分為兩類。一類稱為插值約束點(diǎn)，即點(diǎn)云中的數(shù)據(jù)點(diǎn)，它們位于隱式曲面上，對應(yīng)的約束值為0；另一類稱為離面約束點(diǎn)，必須額外獲取，它們不位于隱式曲面上，對應(yīng)的約束值不為0。文獻(xiàn)［2］定義了3種不同類型的離面約束點(diǎn)，包括:內(nèi)部約束點(diǎn)、外部約束點(diǎn)和法矢約束點(diǎn)。

為了求解權(quán)系數(shù)ωi和多項(xiàng)式R（p）的系數(shù)r0，r1，r2，r3，f（p）必須滿足兩類約束點(diǎn)給定的約束條件

和正交條件

線性方程組的左邊是一個半正定的矩陣，因而存在唯一的一組解（ω1，ω2，…，ωN，r1，r2，r3，r4）。將其代入式（3），即可得到隱式曲面方程。

1.2 單元分解原理

單元分解（partition of unity，POU）的主要思想是“分而治之”，即將全局問題分解成局部問題求解，然后對局部解加權(quán)求和得到全局解［8］。

給定三維空間中的一個點(diǎn)集P＝｛pj∈R3｜j＝1，2，…，N｝，Ω是P所在空間域。首先，將Ω分解成M個相互重疊的子域｛Ωi｜i＝1，2，…，M｝，并使得Ω∪Ωi；然后，分別對這些子域中的點(diǎn)集｛Pi｜PiP∩i＝1，2，…，M｝進(jìn)行曲面重建，得到相應(yīng)的局部重構(gòu)函數(shù)｛fi（p）｜p∈Pi∩i＝1，2，…，M｝；最后，構(gòu)造一組非負(fù)的緊支撐函數(shù)｛wi（p）｜∑wi＝1∩i＝1，2，…，M｝作為權(quán)重系數(shù)，對所有局部重構(gòu)函數(shù)加權(quán)求和得到全局重構(gòu)函數(shù)

約束條件∑wi＝1由加權(quán)函數(shù)｛Wi（p）｜i＝1，2，…，M｝經(jīng)過正則化處理

加以滿足；其中，加權(quán)函數(shù)Wi（p）必須保證全局重構(gòu)函數(shù)F （P）的連續(xù)性，即在子域Ωi的邊界處必須是連續(xù)的。

2 方法描述

2.1 點(diǎn)云空間自適應(yīng)分解

運(yùn)用單元分解原理進(jìn)行曲面重建時，首先必須將點(diǎn)云空間分解成若干個相互重疊的子域。子域可以是任意形狀，實(shí)際應(yīng)用時通常選用包圍盒形、球形和橢球形。由于局部重構(gòu)函數(shù)的計(jì)算僅取決于子域中的數(shù)據(jù)點(diǎn)，因此子域中的點(diǎn)數(shù)將對曲面重建的品質(zhì)和效率產(chǎn)生直接的影響。如果子域中的點(diǎn)數(shù)過多，則曲面重建的效率不高；如果子域中的點(diǎn)數(shù)過少，則重建曲面的精度難以保證。有鑒于此，本文采用二叉樹遞歸分解點(diǎn)云空間，通過調(diào)節(jié)事先設(shè)置的四個參數(shù)來控制點(diǎn)云空間的分解程度。這4個參數(shù)分別為Tleaf、Tmin、Tmax和q。其中，Tleaf用于控制二叉樹葉子結(jié)點(diǎn)中的點(diǎn)數(shù)；Tmin、Tmax和q用于設(shè)定重疊區(qū)域中的最少點(diǎn)數(shù)。

以下是二叉樹及其結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu):

讀取點(diǎn)云數(shù)據(jù)，查找點(diǎn)云中數(shù)據(jù)點(diǎn)在X、Y、Z軸上的最大坐標(biāo)值和最小坐標(biāo)值，進(jìn)而構(gòu)造一個棱邊與坐標(biāo)軸平行并且包含所有數(shù)據(jù)點(diǎn)的長方體包圍盒作為二叉樹的根結(jié)點(diǎn)。對根結(jié)點(diǎn)進(jìn)行遞歸分解，使二叉樹結(jié)點(diǎn)中的點(diǎn)數(shù)逐層減少，所有葉子結(jié)點(diǎn)中的點(diǎn)數(shù)介于Tleaf/2和Tleaf之間。如圖1所示，Ωl是二叉樹的某個結(jié)點(diǎn)。如果Ωl中的點(diǎn)數(shù)nl小于等于Tleaf，則將Ωl標(biāo)記為“葉子結(jié)點(diǎn)”，不再對其進(jìn)行分解；否則，將Ωl標(biāo)記為“非葉子結(jié)點(diǎn)”，繼續(xù)對其進(jìn)行分解。具體步驟如下所述:

步驟1 確定Ωl的最長軸，用垂直于該軸的平面將Ωl分割成兩個大小相同的子域C1、C2。其中，C2中的點(diǎn)數(shù)大于等于C1中的點(diǎn)數(shù)。由于nl＞Tleaf，因此C2中的點(diǎn)數(shù)大于Tleaf/2。

步驟2 擴(kuò)大C1，使之與C2重疊。如果重疊區(qū)域中的點(diǎn)數(shù)大于等于Toverlap并且C1中的點(diǎn)數(shù)大于等于Tleaf/2，則執(zhí)行下一步驟；否則，繼續(xù)擴(kuò)大C1，直到滿足上述兩個條件。其中

圖1 二叉樹結(jié)點(diǎn)的分解

以下是點(diǎn)云空間自適應(yīng)分解的偽代碼:

2.2 局部曲面重建

使用徑向基函數(shù)建立各個子域的隱式曲面方程時，如果僅由插值約束點(diǎn)來定義隱式曲面，則線性方程組（6）會產(chǎn)生平凡解。因此，必須額外增加離面約束點(diǎn)以解決上述問題。

本文采用法矢約束方式［2］為子域中的每個插值約束點(diǎn)構(gòu)造一個離面約束點(diǎn)。給定子域中的某一插值約束點(diǎn)pi，ni是點(diǎn)pi的法向量。將點(diǎn)pi沿其法矢方向偏移一段距離d即可得到與之對應(yīng)的離面約束點(diǎn)pi′＝pi＋dni。如果點(diǎn)pi′位于點(diǎn)云模型的內(nèi)部，則其約束值hi′＞0；如果點(diǎn)pi′位于點(diǎn)云模型的外部，則其約束值hi′＜0。對子域中的兩類約束點(diǎn)進(jìn)行插值即可得到局部重構(gòu)函數(shù)fi（p）。

2.3 構(gòu)造全局重構(gòu)函數(shù)

對局部重構(gòu)函數(shù)｛fi（p）｜i＝1，2，…，M｝加權(quán)求和得到全局重構(gòu)函數(shù)F （P）。其表達(dá)形式為

函數(shù)Wi（p）必須保證全局重構(gòu)函數(shù)F （P）的連續(xù)性。本文采用文獻(xiàn)［6］中的方法將函數(shù)Wi（p）定義為距離函數(shù)與衰減函數(shù)的組合Wi（p）＝V Di（p）；其中，距離函數(shù)Di（p）在子域Ωi邊界處的值為1。對于棱邊與坐標(biāo)軸平行的包圍盒形子域，選用距離函數(shù)

受V（0）＝1，V（1）＝0，V′（0）＝V′（1）＝0等條件的約束，衰減函數(shù)V可以從以下公式中選擇

根據(jù)所選衰減函數(shù)V的不同，函數(shù)Wi（p）能夠滿足不同的連續(xù)性要求。

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

在配有Pentium IV 3.0 GHz和2GB內(nèi)存的計(jì)算機(jī)上使用VC＋＋6.0和OpenGL實(shí)現(xiàn)了本文方法，然后使用Bloomenthal方法［9］對隱式曲面進(jìn)行繪制。圖2為bunny、igea、dragon和lucy的原始點(diǎn)云。圖3為本文方法的曲面重建效果。

4 結(jié)束語

在現(xiàn)有研究成果的基礎(chǔ)上，本文提出了一種基于RBF和POU的曲面重建方法。實(shí)驗(yàn)結(jié)果表明:該方法能夠根據(jù)點(diǎn)云模型的形狀和分布密度，自適應(yīng)地分解點(diǎn)云空間，確保重建曲面的連續(xù)性和光滑性。

當(dāng)然本文算法也有需要進(jìn)一步改進(jìn)的地方，比如，僅由插值約束點(diǎn)來定義隱式曲面會產(chǎn)生平凡解，是否有一個方法不需要額外增加離面約束點(diǎn)來解決上述問題，這是值得研究的。

圖2 原始點(diǎn)云

圖3 曲面重建效果

［1］Beatson R K，Levesley J，Mouat C T.Better bases for radial basis function interpolation problems［J］.Journal of Computational and Applied Mathematics，2011（4）:434－446.

［2］PAN Rongjiang，MENG Xiangxu，TaegKeun Whangbo.Hermite variational implicit surface reconstruction［J］.Science in China Series F:Information Sciences February，2009，52（2）:308－315.

［3］Arnaud Gelas，Sébastien Valette，Rémy Prost，et al.Variational implicit surface meshing［J］.Computers ＆Graphics，2009，33:312－320.

［4］Du Xinwei，Yang Xiaoying，Liang Xuezhang.Surface reconstruction of 3D scattered data with radial basis functions［J］.Communications in Mathematical Research，2010（2）:183－192.

［5］LIU Li，ZHAO Fengqun.ENO scheme based oil interpolation of radial basis function［J］.Computer Engineering and Applications，2013，49（2）:53－56.

［6］Yutaka Ohtake，Alexander Belyaev，Hans－Peter Seidel.Sparse surface reconstruction with adaptive partition of unity and radial basis functions［J］.Graphical Models，2006，68（1）:15－24.

［7］ZHAO Jiandong，KANG Baosheng，KANG Jianchao，et al.An improved surface reconstruction algorithm based on RBF［J］.Journal of Northwest University（Natural Science Edition），2012，42（5）:744－748.

［8］Lu Fangmei，Xi Juntong，Ma Dengzhe.Fast reconstruction of large scattered point clouds using adaptive partition of unity and radial basis functions［J］.Mechanical Science and Technology for Aerospace Engineering，2007，26（10）:1300－1303.

［9］Park Changsoo，Min Chohong，Kang Myungjoo.Surface reconstruction from scattered point data on octree［J］.Journal of the Korean Society for Industrial and Applied Mathematics，2012，16（1）:31－49.

［10］Zagorchev L G，Goshtasby A A.A curvature－adaptive implicit surface reconstruction for irregularly spaced points［J］.Visualization and Computer Graphics，2012，18（9）:1460－1473.