基于變半徑球的數據壓縮

劉　晶,　WONG Edward K

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

?

基于變半徑球的數據壓縮

劉晶1,WONG Edward K2

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

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

數據壓縮; 離散點云; 逆向工程; 曲度

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

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

對于三維點云,存在著壞點和對形狀影響很小的數據點。因此需要移除這些壞點和對形狀影響很小的數據點。本文基于曲度和點密度進行數據縮減。為了滿足逆向工程中模型重構和配準的需要,提出了一種數據縮減算法。首先通過法向量間的關系移除壞點,然后計算每一點處的曲度。建立一個移動球,用戶自定義半徑。基于點云密度,點云被分割到移動變半徑球中。球中的點形成局部區域。最終通過所有球中的局部最大曲度檢測出控制點。提出的算法原理簡單,易于實現,可以應用在包含壞點的任何數據集中。

1　曲　度

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

(1)

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

(2)

曲度是正數或0,對于平面上的點曲度是0。

2　數據縮減

2.1去除壞點

密集的點云由壞點、控制點和一般點構成。壞點和近似位于平面區域的一般點都應該去除。

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

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

(3)

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

(4)

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

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

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

(5)

2.2控制點檢測

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

圖2　提取控制點流程圖Fig.2　Flow chart of extracting dominant points

2.3縮減率

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

(6)

其中：N表示原始點云的數目；Nd表示控制點的數目,縮減率能顯示出點云是否有效地進行了縮減。

3　實驗結果

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

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

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

圖3　馬Fig.3　Horse

圖4　稀疏部分Fig.4　Sparse part

圖5　馬的數據壓縮對比圖Fig.5　Reduction comparison of horse表1　馬的縮減結果Table 1　Reduction result of horse

算法初始點云的點數控制點點數縮減率/%文獻[12]484851615766.68本文算法48485380992.14

表2　腳的縮減結果Table 2　Reduction result of foot

圖6　腳Fig.6　Foot

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

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

算法初始點云的點數控制點點數縮減率/%文獻[12]5429387128.70本文算法5429275749.22

為了客觀評估數據縮減后的網格質量,本文采用均方根誤差來評定數據縮減后的網格與原始網格的接近程度。以圖7中青蛙為例,縮減率與均方根誤差的對應圖見圖8。從圖8可以看出當縮減率很大時,能夠很好地保持原有形狀。對本文算法和文獻[12]算法的效率進行了比較,比較結果見圖9,可以看出本文算法提取控制點花費時間較少。

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

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

4　結　論

基于移動球,針對點云縮減提出了一種有效的縮減算法。首先根據數據點及其鄰近點的法向量點積關系移除壞點,再通過移動球結合點云密集程度檢測出控制點,實驗結果表明本文算法在保持原有形狀的基礎上,具有很好的縮減率。

[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]王麗輝,袁保宗.三維散亂點云模型的特征點檢測[J].信號處理,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

國家留學基金委資助

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

TP391

A