袁 華，龐建鏗，莫建文

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

基于體素化網(wǎng)格下采樣的點(diǎn)云簡(jiǎn)化算法研究

袁 華，龐建鏗，莫建文

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

針對(duì)三維點(diǎn)云數(shù)據(jù)冗余量大、重建時(shí)間長(zhǎng)、效率低等問題，提出一種基于體素化網(wǎng)格下采樣的點(diǎn)云簡(jiǎn)化算法。該算法首先求出點(diǎn)云數(shù)據(jù)集的最小三維長(zhǎng)方體包圍盒，把點(diǎn)云數(shù)據(jù)劃分進(jìn)三維體素柵格中去；其次計(jì)算點(diǎn)云的k鄰域，進(jìn)行曲面法向量估計(jì)；然后，在三維體素柵格中選擇滿足要求的數(shù)據(jù)點(diǎn)，實(shí)現(xiàn)點(diǎn)云下采樣；最后，調(diào)用Power Crust對(duì)下采樣點(diǎn)云數(shù)據(jù)進(jìn)行曲面重建，在三維可視化類庫(kù)Visualization Toolkit(VTK)進(jìn)行顯示。實(shí)驗(yàn)結(jié)果表明，該算法能夠加快三維點(diǎn)云數(shù)據(jù)的重建速度，較好地保持了點(diǎn)云特征，提高曲面重建的效率和魯棒性，適合實(shí)時(shí)處理。

三維點(diǎn)云；體素化柵格；點(diǎn)云簡(jiǎn)化；Power Crust；曲面重建

隨著激光掃描儀測(cè)量精度的不斷提高，點(diǎn)云數(shù)據(jù)正以驚人的速度增長(zhǎng)，產(chǎn)生大量冗余數(shù)據(jù)，存儲(chǔ)、處理、顯示這些點(diǎn)云數(shù)據(jù)會(huì)增加計(jì)算機(jī)處理的負(fù)擔(dān)，占用較多的計(jì)算機(jī)資源，導(dǎo)致降低點(diǎn)云數(shù)據(jù)存儲(chǔ)、操作的效率，尤其會(huì)影響到后續(xù)曲面重建的效率。因此，在保證能為曲面重建提供必要信息的條件下，簡(jiǎn)化采集得到的點(diǎn)云數(shù)據(jù)是十分必要的，已經(jīng)成為了一項(xiàng)具有挑戰(zhàn)性的問題。

目前，點(diǎn)云簡(jiǎn)化受到了國(guó)內(nèi)外諸多學(xué)者的重視，提出了一些優(yōu)秀的點(diǎn)云簡(jiǎn)化算法。Su等[1]提出了一種基于采樣點(diǎn)云模型曲率感知的快速簡(jiǎn)化算法，該算法對(duì)點(diǎn)云進(jìn)行特征區(qū)與非特征區(qū)的劃分，可以較好保留曲面特征，對(duì)點(diǎn)云簡(jiǎn)化采取自適應(yīng)調(diào)整，但對(duì)噪聲和異常值比較敏感。Shi等[2]對(duì)點(diǎn)云數(shù)據(jù)使用k均值聚類，自適應(yīng)調(diào)整點(diǎn)云簡(jiǎn)化，能夠使得點(diǎn)云數(shù)據(jù)模型邊界保持完整，但重建時(shí)間效率比較低。張飛飛等[3]提出了一種基于B樣條曲線的簡(jiǎn)化算法，可以簡(jiǎn)化復(fù)雜的模型和大型點(diǎn)云數(shù)據(jù)，曲面擬合穩(wěn)定，但曲率計(jì)算需要復(fù)雜的矩陣運(yùn)算，隨著點(diǎn)云數(shù)據(jù)規(guī)模的增多，重建運(yùn)行時(shí)間增長(zhǎng)。Wang等[4]將特征參數(shù)和均勻球面采樣結(jié)合起來(lái)，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行大規(guī)模簡(jiǎn)化，可以較好地保留原始數(shù)據(jù)模型的尖銳特征，但大規(guī)模精簡(jiǎn)容易使得點(diǎn)云模型出現(xiàn)空洞，導(dǎo)致點(diǎn)云數(shù)據(jù)模型重建質(zhì)量變差。Lee等[5]將離散形態(tài)算子引入點(diǎn)云簡(jiǎn)化，進(jìn)行點(diǎn)云數(shù)據(jù)模型特征提取，能夠較好地保留點(diǎn)云數(shù)據(jù)模型的幾何特征，但容易受到噪聲的干擾。陳璋雯等[6]在點(diǎn)云簡(jiǎn)化中使用模糊熵迭代，保留點(diǎn)云數(shù)據(jù)模型較多的細(xì)節(jié)特征，從而可以更好地保持點(diǎn)云數(shù)據(jù)邊界的完整性，但需要計(jì)算所有數(shù)據(jù)點(diǎn)的曲率，計(jì)算量比較大。史寶全等[7]提出了基于聚類的點(diǎn)云精簡(jiǎn)算法，該算法對(duì)點(diǎn)云進(jìn)行柵格劃分，選取代表點(diǎn)，進(jìn)行聚類并依據(jù)法向量的變化對(duì)各類進(jìn)行細(xì)分，最后進(jìn)行均值漂移，生成模態(tài)點(diǎn)，能夠保持點(diǎn)云特征。Zhao等[8]提出了采用均勻網(wǎng)格進(jìn)行點(diǎn)云簡(jiǎn)化，該算法能夠保留較多的點(diǎn)云特征，避免曲率估計(jì)，但對(duì)捕獲模型的形狀不夠敏感。

通過對(duì)上述提及的簡(jiǎn)化算法進(jìn)行分析，可以將它們分為兩類：一類是計(jì)算反映曲面特征的參數(shù)值[1-6]，通過對(duì)點(diǎn)云數(shù)據(jù)的每個(gè)點(diǎn)的k近鄰變化，計(jì)算反映曲面特征的參數(shù)值，從而達(dá)到點(diǎn)云簡(jiǎn)化的目的，能夠保留較多的細(xì)節(jié)，但計(jì)算量大，耗費(fèi)時(shí)間長(zhǎng)；另一類是基于拆分[7-8]，將所有點(diǎn)云數(shù)據(jù)拆分到相應(yīng)的單元中去，每個(gè)單元保留一個(gè)點(diǎn)來(lái)代表所在單元所有點(diǎn)，比較簡(jiǎn)單、有效，但使用尺寸網(wǎng)格等，對(duì)捕獲模型的形狀不夠敏感，重建質(zhì)量不是很好。為了克服以前的方法的限制，提出一種將兩種相結(jié)合的體素柵格化下采樣的點(diǎn)云簡(jiǎn)化算法：通過求出輸入的三維點(diǎn)云數(shù)據(jù)的最小三維長(zhǎng)方體包圍盒，根據(jù)設(shè)定的邊長(zhǎng)將長(zhǎng)方體空間劃分成一系列小立方體(稱為柵格)，把所有點(diǎn)云數(shù)據(jù)劃分到柵格中去，求出每個(gè)點(diǎn)的k近鄰，進(jìn)行法向量估計(jì)，然后在此基礎(chǔ)上選擇靠近三維柵格中心集重心的最近點(diǎn)來(lái)代表體素柵格中其他點(diǎn)，從而實(shí)現(xiàn)點(diǎn)云簡(jiǎn)化。對(duì)簡(jiǎn)化后的點(diǎn)云調(diào)用Power Crust算法進(jìn)行曲面重建，接著對(duì)曲面網(wǎng)格進(jìn)行簡(jiǎn)化、平滑等處理，通過局部形狀校正基礎(chǔ)上獲得三維可視化模型，并顯示、實(shí)時(shí)交互。應(yīng)用實(shí)例結(jié)果表明此算法有利于減少渲染時(shí)間和提高重建效率，重建曲面較為準(zhǔn)確、光滑，可以很好防止點(diǎn)云特征信息的丟失，適合實(shí)時(shí)處理。

1 點(diǎn)云簡(jiǎn)化算法

體素化網(wǎng)格下采樣[9-14]主要思路是：根據(jù)點(diǎn)云數(shù)據(jù)創(chuàng)建一個(gè)最小三維體素柵格，然后計(jì)算出需要?jiǎng)澐值男×⒎綎鸥竦倪呴L(zhǎng)L，根據(jù)L的大小將三維體素柵格分解成m×n×l個(gè)小柵格，柵格劃分完畢后將點(diǎn)云數(shù)據(jù)放到相應(yīng)的小柵格中，同時(shí)刪除那些不包含數(shù)據(jù)點(diǎn)的小柵格，在每個(gè)小柵格中，將離小柵格重心最近的數(shù)據(jù)點(diǎn)保留下來(lái)，刪除其余的數(shù)據(jù)點(diǎn)。該方法簡(jiǎn)單高效，容易實(shí)現(xiàn)，不需要建立復(fù)雜的拓?fù)浣Y(jié)構(gòu)，從整體上對(duì)點(diǎn)云數(shù)量進(jìn)行簡(jiǎn)化，實(shí)現(xiàn)了簡(jiǎn)化點(diǎn)云，從而達(dá)到快速三維點(diǎn)云曲面重建的目的。其計(jì)算步驟如下：

1)小立方柵格的邊長(zhǎng)L的確定[9-10]。在體素化柵格下采樣點(diǎn)云簡(jiǎn)化算法中，小立方體柵格邊長(zhǎng)L的選取十分重要：過大的柵格會(huì)降低搜索效率，過小的柵格則會(huì)出現(xiàn)空的柵格。小立方柵格的邊長(zhǎng)與鄰近點(diǎn)個(gè)數(shù)k成正比，與點(diǎn)云的平均密度成反比，當(dāng)點(diǎn)云的平均密度小時(shí)，表示在固定空間內(nèi)的點(diǎn)云數(shù)量少，那么應(yīng)將L取大些來(lái)提高k鄰近搜索的范圍，以保證有足夠多點(diǎn)云進(jìn)行k近鄰的計(jì)算；當(dāng)點(diǎn)云的平均密度大時(shí)，則表示在固定空間內(nèi)的點(diǎn)云數(shù)量較多，應(yīng)將L取小些，以保證在最適當(dāng)?shù)姆秶鷥?nèi)搜索，降低搜索的時(shí)間。

小立方體柵格邊長(zhǎng)為

(1)

式中：α是比例因子，用來(lái)調(diào)節(jié)小立方體柵格的邊長(zhǎng)；s是比例系數(shù)；g是小柵格中點(diǎn)云數(shù)據(jù)的數(shù)目。

單位小柵格中包含的點(diǎn)云數(shù)據(jù)個(gè)數(shù)

n=N/V

(2)

式中：N表示點(diǎn)云數(shù)據(jù)中點(diǎn)的總數(shù)；V表示三維體素柵格的體積。

三維體素柵格的體積

V=LxLyLz

(3)

式中：Lx表示點(diǎn)云X軸方向最大范圍；Ly表示點(diǎn)云Y軸方向最大范圍；Lz表示點(diǎn)云Z軸方向最大范圍。而為了方便后續(xù)的統(tǒng)計(jì)，應(yīng)確保數(shù)據(jù)點(diǎn)不會(huì)出現(xiàn)在外接三維體素柵格的角、邊和面上。因此，適當(dāng)?shù)膶㈤L(zhǎng)方體向外擴(kuò)大，增加距離λ對(duì)其修正。所以，三維體素柵格三邊的長(zhǎng)度應(yīng)該是

(4)

將式(2)、(3)代入式(1)可得

(5)

2)將點(diǎn)云數(shù)據(jù)劃分到小立方體柵格中。根據(jù)小立方體柵格的邊長(zhǎng)L，將點(diǎn)云數(shù)據(jù)劃分為m×n×l個(gè)小立方體柵格，其中，m=ceil(Lx/L)，n=ceil(Ly/L)，l=ceil(Lz/L)。ceil(x)為取整函數(shù)，表示不小于x的最小整數(shù)。對(duì)于任一點(diǎn)pi，其所屬小立方體柵格號(hào)為

(6)

在整個(gè)柵格編碼中，點(diǎn)pi的柵格編碼為(mpi,npi,lpi)，如果轉(zhuǎn)換為一維編碼的話，點(diǎn)pi的柵格編碼為

Vpi=mpi×n×l+npi×l+lpi

(7)

3)根據(jù)式(6)或式(7)求出點(diǎn)云數(shù)據(jù)模型的每個(gè)數(shù)據(jù)點(diǎn)的柵格編碼，且將編碼放進(jìn)哈希鏈表，建立點(diǎn)云數(shù)據(jù)間的空間拓?fù)潢P(guān)系后，確定出每個(gè)數(shù)據(jù)點(diǎn)pi的鄰近點(diǎn)。數(shù)據(jù)點(diǎn)pi的鄰近點(diǎn)是在它本身所在的小柵格和相鄰小柵格中的數(shù)據(jù)點(diǎn)。而k鄰域的確定是計(jì)算這些數(shù)據(jù)點(diǎn)到點(diǎn)pi的距離，并將按距離的遠(yuǎn)近，取出離點(diǎn)pi最近的前k個(gè)數(shù)據(jù)點(diǎn)，存入到哈希鏈表中，作為數(shù)據(jù)點(diǎn)pi的k鄰域點(diǎn)。k的取值，要綜合考慮物體表面的凹凸性和點(diǎn)云數(shù)據(jù)模型的密度，并且要確保重建得到的曲面在每個(gè)數(shù)據(jù)點(diǎn)的鄰近范圍內(nèi)是單凸性或者單凹性的，故k取值范圍一般為8～20。

4)散亂點(diǎn)云法向量的估算。利用最小二乘平面法來(lái)估計(jì)數(shù)據(jù)點(diǎn)的法向量，假設(shè)物體的采樣表面是足夠光滑的，則采樣得到的物體表面的數(shù)據(jù)點(diǎn)就可以用最小二乘平面法來(lái)實(shí)現(xiàn)曲面擬合。根據(jù)點(diǎn)云數(shù)據(jù)模型中的每個(gè)數(shù)據(jù)點(diǎn)pi及其k近鄰點(diǎn)，計(jì)算出每個(gè)數(shù)據(jù)點(diǎn)pi及其k近鄰點(diǎn)的最小二乘局部平面H

(8)

(9)

5)代表點(diǎn)的選取及下采樣實(shí)現(xiàn)。根據(jù)步驟3)求出的點(diǎn)云數(shù)據(jù)模型中每個(gè)點(diǎn)pi的鄰域和步驟4)求出的點(diǎn)云數(shù)據(jù)模型中每個(gè)數(shù)據(jù)點(diǎn)pi的法向量，求出每個(gè)數(shù)據(jù)點(diǎn)pi的法向量與其鄰近點(diǎn)法向之間的夾角。若法向量之間的夾角越大，則說(shuō)明數(shù)據(jù)點(diǎn)pi在其k近鄰附近的曲率變化比較大，存在尖銳的幾何特征。相反，若法向量之間的夾角越小，則說(shuō)明數(shù)據(jù)點(diǎn)pi在其k近鄰附近的曲率變化比較小，存在稀疏的幾何特征。因此，可以預(yù)先設(shè)定一個(gè)閾值，當(dāng)數(shù)據(jù)點(diǎn)pi的法向量與其鄰近點(diǎn)法向量之間的夾角大于閾值，則將該數(shù)據(jù)點(diǎn)視為特征點(diǎn)，調(diào)整邊長(zhǎng)比例因子α，使得立方體柵格邊長(zhǎng)變小，每個(gè)柵格點(diǎn)云數(shù)量變少，這樣可以保留較多特征數(shù)據(jù)點(diǎn)。夾角小于閾值的點(diǎn)作為非特征點(diǎn)，調(diào)整邊長(zhǎng)比例因子α，使得立方體柵格變大，每個(gè)柵格點(diǎn)云數(shù)量變多，保留較少非特征數(shù)據(jù)點(diǎn)。每個(gè)小立方體柵格中，三維柵格中心集重心為

(10)

式中：g為小立方體柵格中點(diǎn)云數(shù)據(jù)個(gè)數(shù)。選取最靠近重心數(shù)據(jù)點(diǎn)保留下來(lái)，代表這個(gè)小立方體柵格所有數(shù)據(jù)點(diǎn)，實(shí)現(xiàn)點(diǎn)云下采樣。

整個(gè)基于體素化柵格下采樣的點(diǎn)云簡(jiǎn)化算法流程圖如圖1所示。

圖1 基于體素化柵格下采樣的點(diǎn)云簡(jiǎn)化算法流程圖

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

為驗(yàn)證算法的有效性和健壯性，實(shí)例選用兔子、貓、馬3組三維點(diǎn)云數(shù)據(jù)模型來(lái)進(jìn)行測(cè)試。圖2是3種三維點(diǎn)云數(shù)據(jù)模型的原始點(diǎn)云圖，對(duì)應(yīng)的調(diào)用Power Crust算法重建的效果圖見圖3；圖4～圖6是3種點(diǎn)云數(shù)據(jù)模型經(jīng)過單位統(tǒng)一化為厘米后的柵格邊長(zhǎng)分別為(2 cm×2 cm×2 cm)、(3 cm×3 cm×3 cm)、(4 cm×4 cm×4 cm)3種體素柵格下采樣后三維點(diǎn)云圖，對(duì)應(yīng)的調(diào)用Power Crust算法重建的效果圖是圖7～圖9。表1～表3是3組點(diǎn)云數(shù)據(jù)的點(diǎn)云簡(jiǎn)化參數(shù)表。

圖2 三維點(diǎn)云數(shù)據(jù)原始點(diǎn)云圖

圖3 三維點(diǎn)云Power Crust曲面重建效果圖

圖4 點(diǎn)云體素柵格(2 cm×2 cm×2 cm)下采樣點(diǎn)云圖

圖5 點(diǎn)云體素柵格(3 cm×3 cm×3 cm)下采樣點(diǎn)云圖

圖6 點(diǎn)云體素柵格(4 cm×4 cm×4 cm)下采樣點(diǎn)云圖

圖7 點(diǎn)云體素柵格(2 cm×2 cm×2 cm)下采樣后曲面重建效果圖

圖8 點(diǎn)云體素柵格(3 cm×3 cm×3 cm)下采樣后曲面重建效果圖

圖9 點(diǎn)云體素柵格(4 cm×4 cm×4 cm)下采樣后曲面重建效果圖

點(diǎn)云名稱對(duì)應(yīng)柵格調(diào)節(jié)系數(shù)α近鄰系數(shù)k點(diǎn)云個(gè)數(shù)三角形個(gè)數(shù)點(diǎn)數(shù)的簡(jiǎn)化率/%簡(jiǎn)化時(shí)間/s兔子原始點(diǎn)云100203593971858054299(2cm×2cm×2cm)下采樣點(diǎn)云07520159033180044223599(3cm×3cm×3cm)下采樣點(diǎn)云0552078561570421912754(4cm×4cm×4cm)下采樣點(diǎn)云030204619922412907356

表2 貓點(diǎn)云點(diǎn)云簡(jiǎn)化參數(shù)表

點(diǎn)云名稱對(duì)應(yīng)柵格調(diào)節(jié)系數(shù)α近鄰系數(shù)k點(diǎn)云個(gè)數(shù)三角形個(gè)數(shù)點(diǎn)數(shù)的簡(jiǎn)化率/%簡(jiǎn)化時(shí)間/s貓?jiān)键c(diǎn)云100201000019998016289(2cm×2cm×2cm)下采樣點(diǎn)云065202934548829305262(3cm×3cm×3cm)下采樣點(diǎn)云050201753351417503086(4cm×4cm×4cm)下采樣點(diǎn)云0252080616088102241

表3 馬點(diǎn)云點(diǎn)云簡(jiǎn)化參數(shù)表

點(diǎn)云名稱對(duì)應(yīng)柵格調(diào)節(jié)系數(shù)α近鄰系數(shù)k點(diǎn)云個(gè)數(shù)三角形個(gè)數(shù)點(diǎn)數(shù)的簡(jiǎn)化率/%簡(jiǎn)化時(shí)間/s馬原始點(diǎn)云100204848596938089008(2cm×2cm×2cm)下采樣點(diǎn)云07020147562947630419272(3cm×3cm×3cm)下采樣點(diǎn)云0552099461987020509868(4cm×4cm×4cm)下采樣點(diǎn)云0352059461123212205846

體素柵格下采樣點(diǎn)集的密度隨著表面的細(xì)節(jié)變化而不同，所有的采樣點(diǎn)都有很多的局部特征。從圖7中兔子點(diǎn)云的曲面重建圖中可以看出：兔子點(diǎn)云體素柵格下采樣后點(diǎn)云依然密集的背部、后腿上部，這些地方特征點(diǎn)比較多，點(diǎn)云曲率變化明顯；而在特征點(diǎn)比較少的地方，如腹部，與原始點(diǎn)云相比非常稀疏。從簡(jiǎn)化效果來(lái)看，在實(shí)現(xiàn)點(diǎn)云體素柵格下采樣點(diǎn)云簡(jiǎn)化的同時(shí)，可以很好地保留點(diǎn)云的特征，防止特征信息的丟失。

柵格邊長(zhǎng)的調(diào)節(jié)系數(shù)α影響點(diǎn)云簡(jiǎn)化算法的效率，α取得越大時(shí)，柵格的邊長(zhǎng)就越長(zhǎng)，對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行搜索耗費(fèi)的時(shí)間就越長(zhǎng)，同時(shí)由于柵格的邊長(zhǎng)越長(zhǎng)，柵格內(nèi)的點(diǎn)云的數(shù)目越多，每個(gè)點(diǎn)的法向量估算時(shí)間就越長(zhǎng)，自然簡(jiǎn)化的時(shí)間就變長(zhǎng)。

從三維點(diǎn)云曲面重建的效果圖來(lái)看，圖7和圖8基本能夠很好地反映了三維點(diǎn)云的立體效果，保持原始點(diǎn)云的曲面特征和拓?fù)浣Y(jié)構(gòu)沒有太大變化。而圖9點(diǎn)云曲面重建存在空洞，部分細(xì)節(jié)缺失。很明顯，體素柵格邊長(zhǎng)選的過大，去除的點(diǎn)云過多，剩余點(diǎn)云不能體現(xiàn)原始點(diǎn)云的特征，重建曲面質(zhì)量變差。

因此，應(yīng)根據(jù)不同的三維點(diǎn)云數(shù)據(jù)模型，并考慮到點(diǎn)云數(shù)據(jù)模型的平均密度和實(shí)際情況的要求，選取合適的體素柵格邊長(zhǎng)。圖7與圖8的曲面重建質(zhì)量較好，但圖7對(duì)應(yīng)的3種點(diǎn)云數(shù)據(jù)平均簡(jiǎn)化率為34.64%，圖8對(duì)應(yīng)的3種點(diǎn)云數(shù)據(jù)平均簡(jiǎn)化率為19.97%，相應(yīng)的圖7的曲面重建時(shí)間比圖8的長(zhǎng)。根據(jù)簡(jiǎn)化率、復(fù)雜度、曲面重建時(shí)間和曲面重建效果圖等因素綜合考慮，在這3種模型中選擇(3 cm×3 cm×3 cm)作為體素柵格邊長(zhǎng)較為合適，在保持重建質(zhì)量下，重建效率有較好的提高。

3 結(jié)語(yǔ)

在分析了現(xiàn)有的點(diǎn)云簡(jiǎn)化技術(shù)基礎(chǔ)上，基于對(duì)點(diǎn)云數(shù)據(jù)的柵格化，結(jié)合每個(gè)點(diǎn)的法向量信息實(shí)現(xiàn)了體素柵格下采樣。應(yīng)用實(shí)例結(jié)果表明，該方法可以加快了基于Voronoi圖和Delaunay三角剖分的Power Crust曲面重建效率，同時(shí)可以很好地保留的點(diǎn)云數(shù)據(jù)的特征信息，實(shí)現(xiàn)了快速三維點(diǎn)云曲面重建，具有較強(qiáng)魯棒性，適合實(shí)時(shí)交互處理。這一方法在一定程度上提高了點(diǎn)云簡(jiǎn)化的效率和實(shí)時(shí)處理能力，可以很方便地應(yīng)用在各個(gè)需要獲取物體近似表面模型的領(lǐng)域，節(jié)約了后續(xù)曲面重建的執(zhí)行時(shí)間和降低計(jì)算機(jī)的負(fù)擔(dān)。相信在不久的將來(lái)，隨著計(jì)算機(jī)技術(shù)的發(fā)展以及圖像處理技術(shù)的深入研究，三維點(diǎn)云曲面重建將會(huì)擁有廣泛的應(yīng)用空間。

[1] SU Z，LI Z，CAO J. Curvature-aware simplification for point-sampled geometry[J]. Journal of Zhejiang University Science C，2011，12(3)： 184-194.

[2] SHI B Q， LIANG J， LIU Q. Adaptive simplification of point cloud using k-means clustering[J]. Computer-Aided Design， 2011， 43(8)： 910-922.

[3] FEIFEI Z， CHE X， ZUO W. A simplification algorithm for point cloud data based on B-spline curve[J]. Journal of Computational Information Systems， 2012， 8(5)： 1821-1828.

[4] WANG L， CHEN J， YUAN B. Simplified representation for 3D point cloud data[C]//Proc. 2010 IEEE 10th International Conference on Signal Processing(ICSP 2010). Beijing，China：IEEE Press，2010：1271-1274.

[5] LEE P F，HUANG C P. The DSO feature based point cloud simplification[C]//Proc. 2011 Eighth International Conference on Computer Graphics，Imaging and Visualization (ICCGIV 2011). Singapore，Singapore：IEEE Press， 2011：1-6.

[6] 陳璋雯，達(dá)飛鵬.基于模糊熵迭代的三維點(diǎn)云精簡(jiǎn)算法[J].光學(xué)學(xué)報(bào)，2013，33(8)：153-159.

[7] 史寶全，梁晉，張曉強(qiáng)，等.特征保持的點(diǎn)云精簡(jiǎn)技術(shù)研究[J].西安交通大學(xué)學(xué)報(bào)，2010，44(11)：37-40.

[8] ZHAO Y，LIU Y，SONG R，et al. A saliency detection based method for 3D surface simplification[C]//Proc. 2012 IEEE International Conference on Acoustics，Speech and Signal Processing(ICASSP 2012). Kyoto，Japan：IEEE Press，2012：889-892.

[9] YU H， WANG R， CHEN J， et al. Saliency computation and simplification of point cloud data[C]//Proc. 2012 2nd International Conference on Computer Science and Network Technology(ICCSNT 2012). Changchun，China：IEEE Press，2012：1350-1353.

[10] ZHAO X， WEN M H. Kd-tree based nonuniform simplification of 3D point cloud[C]//Proc.2009 3rd International Conference on Genetic and Evolutionary Computing(ICGEC 2009).Guilin，China：IEEE Press，2009：339-342.

[11] ORTS-ESCOLANO S， MORELL V， GARCIA-RODRIGUEZ J， et al. Point cloud data filtering and downsampling using growing neural gas[C]//Proc. 2013 International Joint Conference on Neural Networks(IJCNN 2013). Dallas，TX，USA：IEEE Press，2013：1-8.

[12] 邱春麗，許宏麗.一種散亂點(diǎn)云空間直接剖分算法[J].計(jì)算機(jī)科學(xué)，2014，41(2)：157-160.

[13] SANYUAN Z， FENGXIA L， YONGMEI L， et al. A new method for cloud data reduction using uniform grids[C]//Proc. 2013 International Conference on Advanced Computer Science and Electronics Information(ICACSEI 2013).Beijing，China：IEEE Press，2013：64-67.

[14] BENHABILES H， AUBRETON O， BARKI H， et al. Fast simplification with sharp feature preserving for 3D point clouds[C]//Proc. 2013 11th International Symposium on Programming and Systems(ISPS 2013). Algiers，Algeria：IEEE Press，2013：47-52.

[15] 應(yīng)申，毛政元，李霖，等.利用3D Voronoi 圖的兔子點(diǎn)云聚類分割[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2013，38(3)：358-361.

[16] MENG X H， LI J G， YANG Q， et al. Complex conforming delaunay triangulation[J]. Science China Information Sciences，2010，53(6)：1130-1140.

袁 華(1975— )，講師，碩士，主要研究方向?yàn)閳D像處理、智能圖像處理；

龐建鏗(1989— )，碩士研究生，主要研究方向?yàn)閳D像處理，本文通訊作者；

莫建文(1972— )，副教授，博士，碩士生導(dǎo)師，主要研究方向?yàn)槟Ｊ阶R(shí)別、智能信息處理、圖像處理。

責(zé)任編輯：時(shí) 雯

Research on Simplification Algorithm of Point Cloud Based on Voxel Grid

YUAN Hua，PANG Jiankeng，MO Jianwen

(SchoolofElectronicandTechnology，GuilinUniversityofElectronicTechnology，GuangxiGuilin541004，China)

Focus on the issue that high data redundancy， long reconstruction time and low efficiency exist in three-dimensional point cloud data，a simplification algorithm of point cloud based on 3D voxel grid is proposed. Firstly， the minimum three-dimensional rectangular bounding box is calculated， and point cloud are divided into the 3D voxel grid. Secondly， the k-nearest neighbors of point cloud is searched， and the surface normal vector is estimated. And then， sample points by using uniform 3D voxel grids to select the points that satisfy the requirement. Finally， using Power Crust algorithm reconstructing surface， and displaying in the three-dimensional visualization library VTK(Visualization Toolkit). The experimental results show that the proposed method can speed up the reconstructing rate of three-dimensional point cloud， retain geometric characteristics of original dates， improve the surface reconstructing efficiency and robustness， and be able to real time processing.

3D point cloud；voxel grid；point cloud simplification；Power Crust；surface reconstruction

廣西自然科學(xué)基金項(xiàng)目(2013GXNSFAA019331；2014GXNSFDA118035)；桂林電子科技大學(xué)研究生教育創(chuàng)新計(jì)劃資助項(xiàng)目(GDYCSZ201453)

TN919.85

A

10.16280/j.videoe.2015.17.011

2015-03-15

【本文獻(xiàn)信息】袁華，龐建鏗，莫建文.基于體素化網(wǎng)格下采樣的點(diǎn)云簡(jiǎn)化算法研究[J].電視技術(shù),2015，39(17).