劉　晶,　WONG Edward K

(1.華東理工大學(xué)機(jī)械與動(dòng)力工程學(xué)院, 上海 200237;2.紐約大學(xué)理工學(xué)院計(jì)算機(jī)科學(xué)與工程系,美國 紐約 11201)

?

基于變半徑球的數(shù)據(jù)壓縮

劉晶1,WONG Edward K2

(1.華東理工大學(xué)機(jī)械與動(dòng)力工程學(xué)院, 上海 200237;2.紐約大學(xué)理工學(xué)院計(jì)算機(jī)科學(xué)與工程系,美國 紐約 11201)

逆向工程中的點(diǎn)云數(shù)據(jù)壓縮正受到越來越多的關(guān)注。它是模型重構(gòu)和配準(zhǔn)的基礎(chǔ)。點(diǎn)云數(shù)據(jù)壓縮后,可以改善重構(gòu)以及配準(zhǔn)的速度。在保持原始點(diǎn)云形狀的基礎(chǔ)上,提出了一種數(shù)據(jù)壓縮算法。首先計(jì)算每一點(diǎn)處的法向量并且通過相鄰點(diǎn)法向量間的關(guān)系去除壞點(diǎn),然后計(jì)算每一點(diǎn)的曲度,最后通過移動(dòng)球檢測控制點(diǎn)并且簡化點(diǎn)云。實(shí)驗(yàn)表明該算法在保持點(diǎn)云幾何形狀的同時(shí),能夠有效地降低點(diǎn)云數(shù)量。

數(shù)據(jù)壓縮; 離散點(diǎn)云; 逆向工程; 曲度

隨著三維掃描技術(shù)的發(fā)展,點(diǎn)云有著密集的采樣點(diǎn)[1],同時(shí)在點(diǎn)云中也包含了很多冗余點(diǎn)。這對(duì)于模型重構(gòu)和配準(zhǔn)是十分費(fèi)時(shí)的,也消耗很多內(nèi)存。因此點(diǎn)云需要被處理[2]。點(diǎn)云中包含體現(xiàn)形狀特征的控制點(diǎn)、一般點(diǎn)以及壞點(diǎn)。數(shù)據(jù)壓縮就是提取出控制點(diǎn),將一般點(diǎn)和壞點(diǎn)剔除的過程。

最近很多學(xué)者提出了數(shù)據(jù)壓縮算法。這些算法大部分基于曲率、擬合誤差以及法向量偏差[3]。Song等[3]基于幾何數(shù)據(jù)分析提出一種在數(shù)據(jù)點(diǎn)鄰域區(qū)分平滑點(diǎn)和邊界點(diǎn)的方法,但是需要進(jìn)行數(shù)據(jù)平滑預(yù)處理。王麗輝等[4]基于曲率和密度提出了一種特征點(diǎn)檢測方法,該方法需要使用八叉樹分割來獲取密度參數(shù)。Ho等[5]在不同尺度下,基于表面曲率提出了一個(gè)提取三維模型局部特征的框架。使用尺度越多,將會(huì)提取越多的特征,也將消耗更多計(jì)算時(shí)間。Wang等[6]應(yīng)用摩爾斯理論來檢測關(guān)鍵的曲面點(diǎn),但是該方法需要使用幾何性質(zhì)和加工特征。Lü等[7]利用曲率估計(jì)和多邊形逼近來提取工業(yè)CT圖像輪廓的特征點(diǎn)。Du等[8]利用平均曲率作為數(shù)據(jù)壓縮的基本準(zhǔn)則。Benhabiles等[9]基于聚類和由粗到精算法提出了點(diǎn)云簡化算法。Sareen等[10]對(duì)多截面輪廓的點(diǎn)云數(shù)據(jù)壓縮提出了一種算法,該算法包括兩個(gè)階段,第一階段是基于數(shù)據(jù)簡化的投影,第二階段是合成曲線數(shù)據(jù)簡化。Wang等[11]基于平方距離最小值對(duì)二次曲線和曲面采用了擬合的方法。Lan等[12]基于均一網(wǎng)格提出了一種方法,該方法將原始點(diǎn)云分配到立方網(wǎng)格中。對(duì)于任意一個(gè)立方網(wǎng)格,確定并且保存中心點(diǎn),立方網(wǎng)格的曲率閾值是基于平均曲率設(shè)置的。如果立方網(wǎng)格中的一個(gè)點(diǎn)與中心點(diǎn)的曲率差值大于曲率閾值,那么保留這個(gè)點(diǎn)。

對(duì)于三維點(diǎn)云,存在著壞點(diǎn)和對(duì)形狀影響很小的數(shù)據(jù)點(diǎn)。因此需要移除這些壞點(diǎn)和對(duì)形狀影響很小的數(shù)據(jù)點(diǎn)。本文基于曲度和點(diǎn)密度進(jìn)行數(shù)據(jù)縮減。為了滿足逆向工程中模型重構(gòu)和配準(zhǔn)的需要,提出了一種數(shù)據(jù)縮減算法。首先通過法向量間的關(guān)系移除壞點(diǎn),然后計(jì)算每一點(diǎn)處的曲度。建立一個(gè)移動(dòng)球,用戶自定義半徑?；邳c(diǎn)云密度,點(diǎn)云被分割到移動(dòng)變半徑球中。球中的點(diǎn)形成局部區(qū)域。最終通過所有球中的局部最大曲度檢測出控制點(diǎn)。提出的算法原理簡單,易于實(shí)現(xiàn),可以應(yīng)用在包含壞點(diǎn)的任何數(shù)據(jù)集中。

1　曲　度

本文中,曲度用來描述曲面的彎曲程度。在點(diǎn)p處的曲度定義如下[5,13-15]:

(1)

k1(p)和k2(p) 可以通過高斯曲率K(p)和平均曲率H(p)定義。

(2)

曲度是正數(shù)或0,對(duì)于平面上的點(diǎn)曲度是0。

2　數(shù)據(jù)縮減

2.1去除壞點(diǎn)

密集的點(diǎn)云由壞點(diǎn)、控制點(diǎn)和一般點(diǎn)構(gòu)成。壞點(diǎn)和近似位于平面區(qū)域的一般點(diǎn)都應(yīng)該去除。

點(diǎn)云是一個(gè)三維點(diǎn)的集合,點(diǎn)云表示為P={pi|i=1,2,…,n}。點(diǎn)云沒有任何向量或連接信息。因此需要建立數(shù)據(jù)點(diǎn)和鄰接點(diǎn)的連接信息。對(duì)于三維點(diǎn)云P中任意一點(diǎn)pi,可以得到它的k個(gè)鄰近點(diǎn)。pi和其鄰近點(diǎn)可以擬合為一個(gè)局部曲面來獲取pi的法向量。曲面公式定義為

z=F(x,y)=a0+a1x+a2y+a3x2+a4y2

(3)

pi(xi,yi,zi)處的法向量定義為

(4)

圖1中,ni是點(diǎn)pi的法向量,ni1,ni2,ni3以及ni4是點(diǎn)pi鄰近點(diǎn)的法向量。

圖1　壞點(diǎn)及其鄰近點(diǎn)的法向量Fig.1　Normal vectors of outlier and its neighbor points

如果法向量ni和其鄰近點(diǎn)的法向量nit的點(diǎn)積小于0,那么點(diǎn)pi就是壞點(diǎn)。公式如下：

(5)

2.2控制點(diǎn)檢測

在壞點(diǎn)被移除后,其余的點(diǎn)是控制點(diǎn)和一般點(diǎn)。控制點(diǎn)是那些體現(xiàn)主要形狀的代表性點(diǎn),需要識(shí)別出來。一般點(diǎn)對(duì)幾何形狀影響很小,需要移除。本文先將點(diǎn)云數(shù)據(jù)點(diǎn)分割到移動(dòng)球中,然后查找局部最大曲度值,檢測出控制點(diǎn)。

圖2　提取控制點(diǎn)流程圖Fig.2　Flow chart of extracting dominant points

2.3縮減率

本文中,縮減率R是用點(diǎn)云中去除點(diǎn)的數(shù)目與點(diǎn)云總數(shù)目的比值來表示的,公式如下:

(6)

其中：N表示原始點(diǎn)云的數(shù)目；Nd表示控制點(diǎn)的數(shù)目,縮減率能顯示出點(diǎn)云是否有效地進(jìn)行了縮減。

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

圖3(a)示出了馬的原始點(diǎn)云,具有48 485個(gè)點(diǎn)；圖3(b)示出了基于本文算法提取的3 809個(gè)控制點(diǎn)；圖3(c)示出了通過Meshlab對(duì)圖3(b)中數(shù)據(jù)進(jìn)行重構(gòu)的三角網(wǎng)格模型。在圖3(a)中,大部分點(diǎn)都是很密集的,圖中圓圈處是稀疏的,這顯示在圖4(a)中。圖4(b)示出了采用本文算法進(jìn)行數(shù)據(jù)縮減后重構(gòu)的三角網(wǎng)格。通過圖4(b)可以看出在數(shù)據(jù)縮減后,不僅密集部分的控制點(diǎn)保留下來,稀疏部分的控制點(diǎn)也保留得很好。從圖4(a)和圖4(b)中可以看出本文算法無論針對(duì)密集點(diǎn)或稀疏點(diǎn),都能有效地提取控制點(diǎn)。

對(duì)于圖3(a)的點(diǎn)云,分別采用本文提出的算法和文獻(xiàn)[12]進(jìn)行簡化。采用本文算法,當(dāng)初始球半徑越大時(shí),數(shù)據(jù)壓縮就越明顯;采用文獻(xiàn)[12]算法,當(dāng)立方體網(wǎng)格邊長(L)越大時(shí),數(shù)據(jù)壓縮就越明顯。圖5顯示了隨著初始球半徑和立方體網(wǎng)格邊長的改變,數(shù)據(jù)縮減的對(duì)比情況。當(dāng)初始球半徑和立方體網(wǎng)格邊長都取0.005 6時(shí),比較結(jié)果列在表1中。從表1可以看出本文算法具有更好的縮減率。

圖6(a)示出了腳的原始點(diǎn)云,具有5 092個(gè)點(diǎn)。圖6(b)示出了基于本文算法提取的2 344個(gè)控制點(diǎn),圖6(c)是通過Meshlab對(duì)圖6(b)中數(shù)據(jù)進(jìn)行重構(gòu)的三角網(wǎng)格模型。當(dāng)初始球半徑和立方體網(wǎng)格邊長都取8時(shí),比較結(jié)果列在表2中。從表2可以看出本文算法具有更好的縮減率。

圖3　馬Fig.3　Horse

圖4　稀疏部分Fig.4　Sparse part

圖5　馬的數(shù)據(jù)壓縮對(duì)比圖Fig.5　Reduction comparison of horse表1　馬的縮減結(jié)果Table 1　Reduction result of horse

算法初始點(diǎn)云的點(diǎn)數(shù)控制點(diǎn)點(diǎn)數(shù)縮減率/%文獻(xiàn)[12]484851615766.68本文算法48485380992.14

表2　腳的縮減結(jié)果Table 2　Reduction result of foot

圖6　腳Fig.6　Foot

圖7(a)示出了青蛙的原始點(diǎn)云,具有5 429個(gè)點(diǎn)。圖7(b)示出了基于本文算法提取的2 758個(gè)控制點(diǎn),圖7(c)示出了通過Meshlab對(duì)圖7(b)中數(shù)據(jù)進(jìn)行重構(gòu)的三角網(wǎng)格模型。當(dāng)初始球半徑和立方體網(wǎng)格邊長都取0.084時(shí),比較結(jié)果列在表3中。從表3可以看出本文算法具有更好的縮減率。

圖7　青蛙Fig.7　Frog表3　青蛙的縮減結(jié)果Table 3　Reduction result of frog

算法初始點(diǎn)云的點(diǎn)數(shù)控制點(diǎn)點(diǎn)數(shù)縮減率/%文獻(xiàn)[12]5429387128.70本文算法5429275749.22

為了客觀評(píng)估數(shù)據(jù)縮減后的網(wǎng)格質(zhì)量,本文采用均方根誤差來評(píng)定數(shù)據(jù)縮減后的網(wǎng)格與原始網(wǎng)格的接近程度。以圖7中青蛙為例,縮減率與均方根誤差的對(duì)應(yīng)圖見圖8。從圖8可以看出當(dāng)縮減率很大時(shí),能夠很好地保持原有形狀。對(duì)本文算法和文獻(xiàn)[12]算法的效率進(jìn)行了比較,比較結(jié)果見圖9,可以看出本文算法提取控制點(diǎn)花費(fèi)時(shí)間較少。

圖8　均方根誤差圖Fig.8　Root-mean-square error

圖9　效率比較圖Fig.9　Efficiency comparison

4　結(jié)　論

基于移動(dòng)球,針對(duì)點(diǎn)云縮減提出了一種有效的縮減算法。首先根據(jù)數(shù)據(jù)點(diǎn)及其鄰近點(diǎn)的法向量點(diǎn)積關(guān)系移除壞點(diǎn),再通過移動(dòng)球結(jié)合點(diǎn)云密集程度檢測出控制點(diǎn),實(shí)驗(yàn)結(jié)果表明本文算法在保持原有形狀的基礎(chǔ)上,具有很好的縮減率。

[1]DANIELS II J,OCHOTTA T,HA L,etal.Spline-based feature curves from point-sampled geometry[J].The Visual Computer,2008,24(6):449-462

[2]DILLMANN R,VOGT S,ZILKER A.Data reduction for optical 3D-inspection in automotive application[C]//Proceedings of the IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems.USA:IEEE,1999:159-164.

[3]SONG H,FENG H Y,OUYANG D.Automatic detection of tangential discontinuities in point cloud data[J].ASME Journal of Computing and Information Science in Engineering,2008,8(2):021001-021010.

[4]王麗輝,袁保宗.三維散亂點(diǎn)云模型的特征點(diǎn)檢測[J].信號(hào)處理,2011,27(6):932-938.

[5]HO H T,GIBBINS D.Curvature-based approach for multi-scale feature extraction from 3D meshes and unstructured point clouds[J].IET Computer Vision,2009,3(4):201-212

[6]WANG J,WANG Z,ZHU W,etal.Recognition of freeform surface machining features[J].Journal of Computing and Information Science in Engineering,2010,10(4):041006-041013.

[7]Lü Qiujuan,FANG Suping,ZHANG Zhen.Feature points extraction of different structure for industrial computed tomography image contour[J].Optik,2013,124(22):5313-5317.

[8]DU Xiaolei,ZHUO Yong.A point cloud data reduction method based on curvature[C]//Proceedings of IEEE 10th International Conference on CAID & CD.USA:IEEE,2009:914-918.

[9]BENHABILES H,AUBRETON O,BARKI H,etal.Fast simplification with sharp feature preserving for 3D point clouds[C]//IEEE International Symposium on Programming and Systems.USA:IEEE,2013:47-52.

[10]SAREEN K K,KNOPF G K,CANAS R.Surface reconstruction from sliced point cloud data for designing facial prosthesis[C]//IEEE Toronto International Conference on Science and Technology for Humanity (TIC-STH).USA:IEEE,2009:6-11.

[11]WANG Jun,YU Zeyun.Quadratic curve and surface fitting via squared distance minimization[J].Computers & Graphics,2011,35(6):1035-1050.

[12]LAN Jinhui,LI Jian,LI Jiehui,etal.Data reduction based on dynamic-threshold uniform grid-algorithm[J].Optik,2013,124(23):6461-6468.

[13]KOENDERINK J J,VAN DOORN A J.Surface shape and curvature scales[J].Image and Vision Computing,1992,10(8):557-565.

[14]JAGANNATHAN A,MILLER E L.Three-dimensional surface mesh segmentation using curvedness-based region growing approach[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(12):2195-2204.

[15]DORAI C,JAIN A K.COSMOS:A representation scheme for 3D free-form objects[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(10):1115-1130.

Data Reduction Based on Variable Radius Sphere

LIU Jing1,WONG Edward K2

(1.School of Mechanical and Power Engineering,East China University of Science and Technology,Shanghai 200237,China; 2.Department of Computer Science & Engineering,Polytechnic School of Engineering,New York University,New York 11201,USA)

There is an increasing interest for data reduction of point cloud in reverse engineering.It is the base of model reconstruction and registration.After point cloud data is reduced,the speed of reconstruction and registration can be improved.A data reduction algorithm is proposed to preserve the shape of original point cloud.Firstly,normal vector of every point is calculated and outliers are discarded by normal vectors’ relation of neighbor points.Then curvedness of each point is calculated.Finally,point cloud is simplified and dominant points are detected based on moving variable spheres.Experiments demonstrate the algorithm can reduce points of point cloud effectively when the geometrical shape of point cloud is preserved.

data reduction; discrete point cloud; reverse engineering; curvedness

1006-3080(2016)03-0433-06

10.14135/j.cnki.1006-3080.2016.03.022

2015-11-17

國家留學(xué)基金委資助

劉晶(1977-),女,博士,講師,主要研究方向?yàn)镃AD/CAM,圖形圖像處理,逆向工程等。E-mail:annaliu200077@163.com

TP391

A