唐民麗，王 偉

（海南軟件職業(yè)技術(shù)學(xué)院 海南 瓊海 571400）

三維信息獲取技術(shù)的高速發(fā)展使得我們能方便地獲得物體表面三維點(diǎn)云數(shù)據(jù)。點(diǎn)云數(shù)據(jù)在三維建模和可視化，以及反求工程中的應(yīng)用日益廣泛。這使得點(diǎn)云數(shù)據(jù)的幾何元素提取和分析受到越來(lái)越多的重視。其中，三維點(diǎn)云模型表面曲率估算是點(diǎn)云數(shù)據(jù)應(yīng)用的關(guān)鍵技術(shù)之一。

點(diǎn)云曲率估算的方法，國(guó)內(nèi)外已經(jīng)有了一定的研究[1-4]。在三角網(wǎng)格模型上進(jìn)行曲率估算。這些用其他模型代替原三維點(diǎn)云模型方法的不足在于：1）建立起來(lái)的模型表面粗糙，含有很多的噪聲點(diǎn)；2）不能保證點(diǎn)與點(diǎn)之間的拓?fù)潢P(guān)系；3）模型建立過(guò)程太復(fù)雜。

Levin[5]提出了移動(dòng)最小二乘法（MLS）構(gòu)建原始三維表面的投影表面，該方法及相應(yīng)改進(jìn)的該方法已經(jīng)成功地應(yīng)用在三維建模和繪制中[6]。

文中通過(guò)給出具體的移動(dòng)最小二乘法表面的建立過(guò)程，并嘗試直接在MLS表面計(jì)算點(diǎn)云曲率，將該方法應(yīng)用在一段隧道掃描三維點(diǎn)云數(shù)據(jù)的壓縮中。

Amenta 和 Kil[8-9]用一個(gè)內(nèi)積函數(shù) e（y，a）沿向量場(chǎng) n（x）方向的局部最小值具體的定義了MLS表面這里y為一個(gè)位置向量，a為一個(gè)方向向量。根據(jù)該方法，MLS表面建立的兩個(gè)關(guān)鍵步驟為向量場(chǎng)n（x）的確定以及搜尋內(nèi)積函數(shù)e（y，n（x））的最小極值點(diǎn)。

步驟一：n（x）的確定

假定輸入點(diǎn)云為 Q，qi∈Q且 R3，vi為 qi對(duì)應(yīng)的法向量，則向量場(chǎng)n（x）可以由下式給出：

1 MLS表面的建立

如果輸入數(shù)據(jù)沒(méi)有給出vi，可以通過(guò)qi與臨近的點(diǎn)來(lái)估計(jì)qi對(duì)應(yīng)的法向量vi。具體方法如下：

對(duì)于給定的采樣點(diǎn)q，假定與q臨近的采樣點(diǎn)的集合為Q，且qi∈Q，則點(diǎn)q的臨近點(diǎn)的加權(quán)質(zhì)心c為：

Levin最早提出了MLS表面S的定義[7]：它是原三維模型表面的一個(gè)映射。假設(shè)映射函數(shù)為ψp，則S定義如下：

這里，θ（x，qi）=e-‖q-qi‖2/h2為高斯加權(quán)函數(shù)，h 為高斯尺度參數(shù)，它決定了高斯內(nèi)核的寬度。文獻(xiàn)[10]給出了h的詳細(xì)說(shuō)明和選取準(zhǔn)則。在文中，選取h為一個(gè)常數(shù)，這已經(jīng)能夠滿足大多數(shù)應(yīng)用的需要。點(diǎn)q的3×3相關(guān)矩陣由下式給出：

這里，C為對(duì)稱陣和正半定矩陣，它的3個(gè)特征值λ0，λ1，λ2為實(shí)數(shù)。 假設(shè) λ0＜λ1＜λ2，用 λ0的特征向量 v0的單位法向量來(lái)估計(jì)點(diǎn)q的法向量v。

步驟二：MLS表面的投影過(guò)程

為了計(jì)算MLS表面的曲率，首先我們考慮用一個(gè)隱函數(shù)來(lái)表示MLS曲面。根據(jù)文獻(xiàn)[4-6]，該隱函數(shù)可以表示如下：

對(duì)e（y，n（x））函數(shù)的局部最小值的搜索等價(jià)于對(duì)函數(shù)求偏導(dǎo)數(shù)，并尋找其最小極值點(diǎn)。則MLS表面可以由下式確定：

這里 x∈R3，n（x）由（2）式確定，e（s，n（x））由（5）式確定。

2 曲率計(jì)算

根據(jù)文獻(xiàn)[11]，由（6）式得到的MLS表面表達(dá)式，高斯曲率和平均曲率計(jì)算公式如下：

3 實(shí) 驗(yàn)

為了驗(yàn)證算法的正確性，文中采用標(biāo)準(zhǔn)的合成數(shù)據(jù)做了驗(yàn)證。實(shí)驗(yàn)中=0.025，實(shí)驗(yàn)數(shù)據(jù)中每點(diǎn)的法向量為已知的，實(shí)驗(yàn)結(jié)果如下表：

表1 主曲率和在標(biāo)準(zhǔn)曲面上計(jì)算誤差分析Tab.1 Results of k1and k2errors on synthetic data

3 個(gè)標(biāo)準(zhǔn)幾何體的點(diǎn)云數(shù)據(jù)分別來(lái)至于各自對(duì)應(yīng)的實(shí)際物體的表面等距采樣，采樣點(diǎn)為5 000個(gè)，如圖1所示。

4 數(shù)據(jù)壓縮

以文中曲率算法為基礎(chǔ)，提出了一種海量的點(diǎn)云數(shù)據(jù)壓縮的方法，在大于給定閾值的地方保留該點(diǎn)，在小于給定閾值的地方，刪除相應(yīng)點(diǎn)。

圖1 3個(gè)幾何體的三維點(diǎn)云原始模型Fig.1 Nominal geometry for three primitive surfaces

運(yùn)用文中的數(shù)據(jù)簡(jiǎn)化方案對(duì)三維隧道掃描點(diǎn)云數(shù)據(jù)進(jìn)行了壓縮，點(diǎn)云個(gè)數(shù)為38 645。圖2（b）是簡(jiǎn)化后的數(shù)據(jù)點(diǎn)，可見(jiàn)用較少的點(diǎn)也能很好的反映物體特征信息。由于本簡(jiǎn)化方案是基于散亂點(diǎn)集表示的曲面曲率，曲率計(jì)算與臨近點(diǎn)的個(gè)數(shù)和的值密切相關(guān)。實(shí)踐中，k取10，h取0.06，效果比較好。

5 結(jié)束語(yǔ)

基于MLS表面直接求點(diǎn)云曲率更方便，具有廣闊的應(yīng)用前景，不足之處在于，曲率計(jì)算精度和臨近采樣點(diǎn)個(gè)數(shù)k和高斯內(nèi)核寬度h有密切關(guān)系，后續(xù)的工作中是找到更好的定義k與h的方法，提高曲率計(jì)算精度和計(jì)算速度。

圖2 三維隧道點(diǎn)云模型數(shù)據(jù)壓縮Fig.2 The data compression for 3-d point-cloud model of the tunnel

[1]Amenta N，Bern M，Kamvysselis M.A new voronoi-based surface Reconstruction Algorithm [C]//Proc.SIGGRAPH，1998：415-422.

[2]Bajaj C L，Bernardini F，XU G.Automatic reconstruction of surfacesand scalarfields from 3D Scans.[C]//Proc.SIGGRAPH，1995：109-118.

[3]Bernardini F， Mittleman J， Rushmeier H，et al.The ballpivoting algorithm for surface reconstruction [J].IEEE Transactions Visualization and Computer Graphics，1999，5（4）：349-359.

[4]Boissonnat J D.Geometric structues for three-dimensional shape representation[J].ACM Trans.Graphics，1984，3（4）：266-286.

[5]Levin D.Mesh-independent surfaceinterpolation[J].Geometric Modelling for Scientific Visualization，2003，Springer-Verlag：37-49.

[6]Dey T K，Sun J.An Adaptive MLS surfaces for reconstruction with guarantees[C]//Proc.Eurographics Symposium on Geometry Processing.2005，http：//www.cse.ohio-state.edul%7.Etamaldey/omls.html.

[7]Levin D.The approximation power of moving least-squares[J].Mathematics of Computation.1998，67（224）：1517-1531.

[8]Amenta N，Kil Y J.Defining point-set surfaces[J].ACM Trans.Graph， 2004， 23（3）：264-270.

[9]Amenta N，Kil Y J.The domain of appoint set surface[J].Eurographics Symposium Workshop on Point-Based Graphics，2004：139-147.

[10]Pauly M.Point primitives for interactive modeling and processingof 3d geometry[D].Ph.D.Thesis.Zurich：ETH Zurich，2003.

[11]Goldman R.Curvature formulas for implicit curves and surfaces[J].Computer Aided Geometric Design，2005，22（7）：632-658.