面向點云數(shù)據(jù)的復(fù)雜幾何模型對象優(yōu)化方法研究

曹 垚，王宗敏，2，李 健*

(1.鄭州大學(xué)水利與環(huán)境學(xué)院，鄭州 450001; 2.中原工學(xué)院，鄭州 450007)

隨著三維激光掃描點云精度的不斷提高，點云數(shù)據(jù)被廣泛用于鐵軌變形監(jiān)測、零件模具和醫(yī)療等對數(shù)據(jù)具有較高要求的行業(yè)[1].隨著精度的提高，所獲取的點云數(shù)據(jù)量也在激增，需要對點云數(shù)據(jù)進(jìn)行精簡才能夠進(jìn)行應(yīng)用.通過對學(xué)者[2-4]精簡數(shù)據(jù)重構(gòu)網(wǎng)格進(jìn)行分析，點云精簡之后點云數(shù)據(jù)尤其是重建網(wǎng)格的精度降低，精簡率越大精度損失越多，從而確實原始物體的細(xì)節(jié)信息.尤其特征突出、曲面結(jié)構(gòu)復(fù)雜的幾何模型，精簡之后點云重建會損失更多精度.如何降低網(wǎng)格精度損失成為主要問題之一.

針對網(wǎng)格精度提升和質(zhì)量優(yōu)化，主要集中在兩個方面：1)一類是幾何優(yōu)化，通過增加點法和移動點法來提升三維點云重構(gòu)網(wǎng)格質(zhì)量，Leif Kobbelt[5]等人將拉普拉斯算子應(yīng)用到網(wǎng)格優(yōu)化中，該方法具有高效高精度的優(yōu)點，但是對于復(fù)雜模型支持較差；丁慧[6]改進(jìn)拉普拉斯算法在網(wǎng)格優(yōu)化的應(yīng)用，該方法能有效提升網(wǎng)格質(zhì)量；章雅娟[7]提出了一種自適應(yīng)網(wǎng)格優(yōu)化方法，該方法根據(jù)不同權(quán)重對定點進(jìn)行調(diào)整，能有效降低網(wǎng)格噪聲.2)另一類是拓?fù)鋬?yōu)化，通過調(diào)整點與點的連接關(guān)系來提高網(wǎng)格質(zhì)量.Hoppe等[8]通過調(diào)整網(wǎng)格拓?fù)潢P(guān)系提升網(wǎng)格質(zhì)量；Canann等[9]針對網(wǎng)格幾何形狀問題進(jìn)行優(yōu)化，該方法去除了大量不符合幾何要求的三角網(wǎng)格；上述方法均能對網(wǎng)格進(jìn)行優(yōu)化，第一種方法主要是提升網(wǎng)格的精度，但是該方法不適用復(fù)雜的幾何模型；第二種方法能有效提升網(wǎng)格拓?fù)洌菍W(wǎng)格的精度提升較小.

本文針對基于精簡后點云數(shù)據(jù)重構(gòu)網(wǎng)格精度缺失問題，結(jié)合三角網(wǎng)格中重新還原點使得網(wǎng)格誤差減少思想[10]提出了一種面向點云數(shù)據(jù)的復(fù)雜幾何模型對象優(yōu)化方法.其基本思路是根據(jù)距離度量方法計算精簡后點云重構(gòu)網(wǎng)格誤差，然后以目標(biāo)精度確定需要優(yōu)化的區(qū)域，最后利用增點法和插入點點算法定位插入點位置，還原網(wǎng)格細(xì)節(jié)，提升網(wǎng)格質(zhì)量.

1點云重建網(wǎng)格的局部優(yōu)化

1.1重建網(wǎng)格誤差分析

1.1.1構(gòu)建拓?fù)湫畔?由于原始點云散亂無序的特性，并且與所構(gòu)建的三角網(wǎng)格也無索引和拓?fù)潢P(guān)系，為了準(zhǔn)確的評估點云所構(gòu)建三角格網(wǎng)的精度，需要構(gòu)建點云的索引以及建立點云與格網(wǎng)的拓?fù)潢P(guān)系.

本文采用八叉樹的方法，首先計算原始點云和重建模型的外包圍盒，然后對外包圍盒進(jìn)行剖分并對剖分結(jié)果進(jìn)行編碼，最后確定原始點云的點和三角面片對應(yīng)的位置并進(jìn)行相應(yīng)的編碼.

1.1.2重建網(wǎng)格誤差控制 通過距離度量的方法計算重建網(wǎng)格法誤差，確定網(wǎng)格精度.首先通過已經(jīng)構(gòu)建好的拓?fù)潢P(guān)系確定原始點云點P(x，y，z)的鄰域進(jìn)而確定相鄰網(wǎng)格，然后將點P(x，y，z)投影到鄰近網(wǎng)格上，最后計算點P(x，y，z)到網(wǎng)格距離.該距離就是原始點云到重建網(wǎng)格的誤差.計算網(wǎng)格的法向n，原始點云數(shù)據(jù)點P(x，y，z)到重構(gòu)網(wǎng)格歐式距離為[11-12]：

(1)

(2)

其中，P1、P2、P3為網(wǎng)格點坐標(biāo)，d代表原始點云點到網(wǎng)格的歐式距離.

由于原始點云中存在一個或者多個點投影到同一個三角網(wǎng)格中，則將點到三角網(wǎng)格距離的最大值作為網(wǎng)格誤差，公式如下所示：

δj=max(dj(P，Δi)).

(3)

由上述公式計算每個三角網(wǎng)格誤差，進(jìn)而確定重構(gòu)網(wǎng)格最大誤差.本文計算和分析了不同精簡率點云網(wǎng)格的誤差.如圖1所示，點云的誤差逐漸增大，并且誤差損失的速度變大.

需要說明的是，在數(shù)據(jù)選取過程中，不同的三維激光掃描儀獲取的數(shù)據(jù)精度不同，以及根據(jù)數(shù)據(jù)使用用途的不同，數(shù)據(jù)精度要求也存在差異.所以本文網(wǎng)格預(yù)期精度需要根據(jù)原始數(shù)據(jù)的精度和網(wǎng)格模型精度要求進(jìn)行調(diào)整.

1.2局部網(wǎng)格細(xì)分方法

本文通過上述誤差計算方法以及目標(biāo)精度對誤差較大網(wǎng)格進(jìn)行網(wǎng)格細(xì)分.網(wǎng)格細(xì)分[10，13]方法包括：

1-2劃分法：將一個三角網(wǎng)格劃分成兩個三角網(wǎng)格；

1-3劃分法：將一個三角網(wǎng)格劃分成三個三角網(wǎng)格；

1-4劃分法：將一個三角網(wǎng)格劃分成四個三角網(wǎng)格.

通過對上述網(wǎng)格細(xì)分方法分析：如圖2(c)所示，1-3劃分法核心思路是將一個三角形劃分成三個，該方法不引發(fā)其它三角面變化，但是容易產(chǎn)生小角度三角面；如圖2(d)所示，由于1-4劃分法是在每邊的中心增加點，能很好的保留三角形形狀，但是會影響周圍三角形連接方式.因此本文將利用兩次1-2劃分法，如圖2(b)所示.

圖1 不同精簡度的重構(gòu)網(wǎng)格誤差Fig.1 Reconstructedmesh errors with different simplification degrees

圖2 局部劃分方法Fig.2 Local division method

在數(shù)學(xué)幾何原理基礎(chǔ)上，以最長邊中點和包含最長邊的兩個三角的法向所構(gòu)成的平面為約束平面，然后構(gòu)建搜索圓，為了提升精度降低誤差搜索半徑為三角網(wǎng)格最大誤差.

(4)

其中，a、b的取值范圍為-δi到δi，step為?/10，Pai為增加點坐標(biāo).

通過公式(4)確定插入點，接著利用增點將該點插入到三角網(wǎng)格中，然后重新計算該區(qū)域的誤差，依次計算所有插入點構(gòu)成的新區(qū)域的誤差，最后將誤差最小的點作為最終插入點.

1.3方法流程

綜上所述，本文方法的流程圖如圖3所示，步驟如下.

Step1：將原始點云數(shù)據(jù)點、精簡后點云和重建網(wǎng)格分別存入到r_Points、s_Points和s_Mesh中.

Step2：根據(jù)空間八叉樹構(gòu)建的拓?fù)潢P(guān)系，計算原始點對應(yīng)的網(wǎng)格，利用上述方法計算每個三角網(wǎng)格的誤差.

Step3：以目標(biāo)精度作為閾值，對誤差大于閾值的三角網(wǎng)格進(jìn)行局部細(xì)分，直到三角網(wǎng)格誤差小于閾值.

Step4：根據(jù)最長邊確定約束平面和搜索圓，然后利用插入點公式確定所有預(yù)插入點，最后將誤差最小的點作為最終插入點.

圖3 方法流程圖Fig.3 Flow chart of the method

2實驗結(jié)果與分析

為了驗證本文方法的可行性和有效性，采用經(jīng)典的兔子點云和若干來源于斯坦福大學(xué)的高保真數(shù)據(jù)，原始數(shù)據(jù)精度為± 0.025 mm.分別利用Geomagic Studio軟件和Crust算法對上述數(shù)據(jù)進(jìn)行精簡和三維重建.基于上述處理，計算了精簡后點云重構(gòu)網(wǎng)格的誤差，并利用增點法對三角形進(jìn)行細(xì)分，本文不僅計算了細(xì)分之后的誤差，還計算了三角面片的正則度.

根據(jù)目標(biāo)精度要求，以兔子點云目標(biāo)精度0.15 mm和龍點云目標(biāo)精度0.10 mm作為閾值，分別對兔子和龍的精簡后點云重構(gòu)網(wǎng)格進(jìn)行網(wǎng)格細(xì)分.圖4和表1是點云精簡率為90%的網(wǎng)格局部細(xì)分結(jié)果，以及細(xì)分前后誤差和正則度對比.圖4(a)和(b)分別為細(xì)分區(qū)域在整體位置以及局部細(xì)分放大圖.由圖所示細(xì)分區(qū)域在幾何結(jié)構(gòu)復(fù)雜的腳上.分析圖4和表1可以得出，該局部網(wǎng)格誤差由0.81 mm降低到0.32 mm，正則度則分別為0.888 3和0.888 7，正則度基本保持不變.表2則是選取了誤差較大的七組細(xì)分前后的數(shù)據(jù)，通過表2可以看出細(xì)分后誤差減少，部分三角面片正則度提升.

表1 子網(wǎng)格誤差最大的三角面片優(yōu)化前后數(shù)據(jù)

表2 兔子網(wǎng)格優(yōu)化前后數(shù)據(jù)Tab.2 Data before and after rabbit mesh optimization

表3是分別利用本文方法對目標(biāo)精度為0.15 mm的兔子網(wǎng)格和目標(biāo)精度為0.10 mm的龍點云優(yōu)化前后的對比數(shù)據(jù).分析可得，一次劃分后龍的三角網(wǎng)格增加140，點數(shù)增加了70，最大誤差由0.36降低到0.11；兔子的三角網(wǎng)格增加262，點數(shù)增加131，誤差由0.81降低到0.47，網(wǎng)格精度提升.

表3 精簡后點云數(shù)據(jù)重構(gòu)網(wǎng)格優(yōu)化前后對比Tab.3 Comparisons before and after mesh optimization for simplifing point cloud datareconstruction

3結(jié)論

針對高精簡率點云重構(gòu)網(wǎng)格仿真度低誤差降低的問題，在高保真和高精度原始點云數(shù)據(jù)的基礎(chǔ)上，結(jié)合三角網(wǎng)格中重新還原點使網(wǎng)格誤差減少思想，提出了一種面向點云數(shù)據(jù)的復(fù)雜幾何模型對象優(yōu)化方法.首先構(gòu)建點云的索引以及建立點云與格網(wǎng)的拓?fù)潢P(guān)系，用原始點云到重構(gòu)網(wǎng)格的距離確定網(wǎng)格的誤差，以目標(biāo)精度為閾值，然后利用增點法對面片進(jìn)行劃分，最后根據(jù)插入點算法重新定位插入點.實驗驗證表明：通過該方法對部分三角面進(jìn)行一次優(yōu)化，誤差降低明顯，仿真精度得到了提升.需要注意的是，本文方法在優(yōu)化過程中會產(chǎn)生少量狹長三角面片，為了保證三角網(wǎng)格質(zhì)量，下一步需要探究狹長三角面片產(chǎn)生的原因和消除的方法.