改進(jìn)的分層曲率海量點(diǎn)云精簡算法

陳新河 龐俊亭 周 波

改進(jìn)的分層曲率海量點(diǎn)云精簡算法

陳新河1龐俊亭2周 波3

1(巢湖學(xué)院電子工程與電氣自動(dòng)化學(xué)院 安徽 巢湖 238000)

2(湖南第一師范學(xué)院商學(xué)院 湖南 長沙 410205)

3(黑龍江科技大學(xué)計(jì)算機(jī)與信息工程學(xué)院 黑龍江 哈爾濱 150022)

海量點(diǎn)云精簡既要考慮算法的復(fù)雜度，又要考慮精簡結(jié)果的效果。根據(jù)三維掃描儀形成的點(diǎn)云特點(diǎn)，提出將空間點(diǎn)云劃分為掃描層平面點(diǎn)云，從而將空間問題轉(zhuǎn)化為平面問題。通過平面內(nèi)Angl的簡單計(jì)算獲得點(diǎn)曲率，從而簡化算法復(fù)雜度；通過引進(jìn)距離參數(shù)Dis防止精簡“大孔洞“的出現(xiàn)；通過綜合考慮點(diǎn)的曲率和點(diǎn)間的距離，形成一個(gè)判別點(diǎn)是否被刪除的標(biāo)準(zhǔn)，修改該判別標(biāo)準(zhǔn)公式中的系數(shù)，可以得到不同的精簡效果。試驗(yàn)結(jié)果證明，該算法對海量點(diǎn)云的精簡實(shí)踐可行，具有復(fù)雜度低、數(shù)據(jù)精簡率高等特點(diǎn)。

海量點(diǎn)云 數(shù)據(jù)精簡 曲率 分割切面

0 引 言

點(diǎn)云三角化在計(jì)算機(jī)視覺、逆向工程、自由曲面設(shè)計(jì)、計(jì)算機(jī)輔助制造設(shè)計(jì)(CAGD/CAD)和地球信息系統(tǒng)(GIS)等許多領(lǐng)域廣泛應(yīng)用。但隨著生產(chǎn)實(shí)踐的增長要求，當(dāng)前處理的點(diǎn)云每每超過十萬、百萬、甚至千萬點(diǎn)的規(guī)模。如何對這些海量點(diǎn)云進(jìn)行三角化處理是一個(gè)問題，如果直接對海量點(diǎn)云數(shù)據(jù)進(jìn)行三維曲面的重構(gòu)，會造成數(shù)據(jù)存儲結(jié)構(gòu)龐大、計(jì)算機(jī)操作困難、顯示和數(shù)據(jù)交換緩慢等問題。因此，在保證一定的三維重建的精度前提下對海量點(diǎn)云進(jìn)行精簡是一個(gè)值得研究的課題。

近年來，國內(nèi)外許多學(xué)者就數(shù)據(jù)精簡發(fā)表了一系列的研究成果：文獻(xiàn)[1]中研究了自適應(yīng)最小率的變化而影響精簡精度距離精簡算法，還討論了按距離精簡的算法，它們都沒有充分考慮空間點(diǎn)曲；文獻(xiàn)[2]中提出了一種自適應(yīng)的三維點(diǎn)云數(shù)據(jù)精簡算法，但該算法實(shí)現(xiàn)起來有一定的困難；文獻(xiàn)[3]中分析CMS采集數(shù)據(jù)的特點(diǎn)的基礎(chǔ)上提出了改進(jìn)的角度偏差法，但這題算法的實(shí)效性不太好；文獻(xiàn)[4]中也提出了基于三維掃描儀的點(diǎn)云數(shù)據(jù)特點(diǎn)的數(shù)據(jù)精簡算法，但算法中是人為的控制分層層數(shù)，這就很難控制分層正好處于掃描位置，而且文中僅僅認(rèn)為三維掃描儀中XOY平面內(nèi)掃描，Z軸為掃描層增加方向；文獻(xiàn)[5]中提出了基于點(diǎn)的空間主曲率的數(shù)據(jù)精簡算法，雖然這種精簡效果較好，但每個(gè)點(diǎn)都需要二次曲面的擬合獲得其主曲率，這是個(gè)非常費(fèi)時(shí)的操作，對于海量點(diǎn)云幾乎是不可能；文獻(xiàn)[6]中提出了基于法向量夾角的數(shù)據(jù)精簡算法，這種算法也可以得到比較好的精簡效果，但同文獻(xiàn)[5]中一樣，也要對點(diǎn)云中每個(gè)點(diǎn)進(jìn)行最小二乘擬合，計(jì)算相當(dāng)費(fèi)時(shí)，對海量點(diǎn)云不切實(shí)際。

總的來說，點(diǎn)云的精簡算法總體分為三類：網(wǎng)格精簡、分層精簡和基于最小二乘的精簡。網(wǎng)格精簡速度快但精簡效果差，基于最小二乘法的精簡精度好但運(yùn)算耗時(shí)，不符合海量點(diǎn)云的要求，分層精簡的速度和精度都比較適中。本文對此提出一種基于自動(dòng)分層的海量點(diǎn)云的精簡算法。

1 算 法

三維掃描儀取點(diǎn)時(shí)一般是將某個(gè)軸向坐標(biāo)暫時(shí)固定[7]，在該軸向的垂直平面內(nèi)獲取物體表面的點(diǎn)，然后沿該軸向進(jìn)行微小移動(dòng)進(jìn)行下次的取點(diǎn)，直到整個(gè)物體表面的點(diǎn)全部取完。因此三維掃描儀獲取的點(diǎn)云是分層的點(diǎn)云數(shù)據(jù)。基于此類點(diǎn)云數(shù)據(jù)的特點(diǎn)，本文算法的基本思路是：首先找到點(diǎn)云的分層方向，將點(diǎn)云按照自然分層分成各個(gè)小的點(diǎn)云切面，其次中各個(gè)切片點(diǎn)云中對各點(diǎn)的相互位置關(guān)系進(jìn)行確定；然后通過相鄰點(diǎn)計(jì)算出各點(diǎn)的曲率等參數(shù)的大小，對這些參數(shù)的綜合值小于用戶指定閾值的點(diǎn)進(jìn)行刪除；最后將所有分層點(diǎn)云合并成一個(gè)整體點(diǎn)云進(jìn)行顯示，以確定本次精簡結(jié)果是否達(dá)到要求而進(jìn)行保存或者重新精簡。

1.1 相關(guān)數(shù)據(jù)結(jié)構(gòu)

點(diǎn)及點(diǎn)云數(shù)值

class C3DPoint

{public:

//point coordinate in 3-dimensiom

float x,y,z;

//to sign the specialcharacteristic index of the point such as angle or position in three-dimension

float mark;

//the constructors of this class

C3DPoint(){ mark=x=y=z=0;}

C3DPoint(float xx,float yy,float zz,float mm=0) {… }

……};

typedef CArray C3DPtArray; //define 3D point array

分層點(diǎn)云數(shù)值鏈表

//this struct can let you create many point-arrays dynamically and assemble them as a whole like list.

typedef struct C3DPtArrayList

{ int index;

C3DPtArray ptArr;

C3DptArrayList *nextPtArr;

}C3DPtArrayList;

1.2 算法過程

讀入點(diǎn)云：將點(diǎn)云數(shù)據(jù)從文件中讀入，同時(shí)統(tǒng)計(jì)點(diǎn)云的相關(guān)參數(shù)，如點(diǎn)云的中心，各個(gè)方向的軸長，各個(gè)方向的最小、最大值等。

尋找分層方向：將點(diǎn)云沿某一軸向進(jìn)行快速排序，對排序好的數(shù)組預(yù)取前邊的一些點(diǎn)，比較它們的排序方向的坐標(biāo)值是否相等。如果相等，說明他們是同一分層的點(diǎn)，該排序方向也是正確的分層方向；否則就沿其他方向排序并尋找點(diǎn)云分層方向，直到分層方向找到。

層內(nèi)點(diǎn)間關(guān)系的確定：對于已經(jīng)確定好分層方向的點(diǎn)云(設(shè)分層方向?yàn)閄方向)，按照分層方向坐標(biāo)值的變化將點(diǎn)云中的各點(diǎn)存入不同的分層數(shù)組鏈表對象的點(diǎn)數(shù)組對象ptArr中，在各個(gè)分層點(diǎn)的加入過程中同時(shí)統(tǒng)計(jì)該分層點(diǎn)云的重心PCent和分層面內(nèi)坐標(biāo)的極值點(diǎn)(YMin/YMax/ZMin/ZMax)。然后以點(diǎn)PCent為坐標(biāo)原點(diǎn)，計(jì)算各點(diǎn)在極坐標(biāo)下的極角并保存在對應(yīng)的mark參數(shù)中，同時(shí)檢查同一分層中點(diǎn)的mark值是否在0、1.57、3.14和4.71的4個(gè)特征值附近存在。如有2個(gè)特征值附近沒有對應(yīng)的mark值存在，說明此層中的點(diǎn)云并不是一個(gè)完成封閉的點(diǎn)云圈，而是一個(gè)開口的點(diǎn)云線(如圖1所示)；否則該層中的點(diǎn)云是封閉點(diǎn)云圈(如圖2所示)。對點(diǎn)云線只要按照點(diǎn)云線的主要排布方向(即由4個(gè)極值點(diǎn)計(jì)算出的在Y、Z方向上是最長排布方向)的坐標(biāo)值進(jìn)行排序就可以確定他們的相互關(guān)系了。對于封閉點(diǎn)云圈只要按照各點(diǎn)的mark值的大小排序就可以確定他們之間的關(guān)系。

圖1 開口點(diǎn)云線(單層內(nèi)) 圖2 封閉點(diǎn)云圈(單層內(nèi))

數(shù)據(jù)點(diǎn)刪減：對于分層點(diǎn)云中的任意點(diǎn)P，其前相鄰點(diǎn)U和后相鄰點(diǎn)Q已經(jīng)確定，通過式(1)求得參數(shù)Angl，用1/Angl來反映該點(diǎn)的曲率大小。如果直接將Angl參數(shù)作為數(shù)據(jù)點(diǎn)是刪減的依據(jù)，結(jié)果會造成一些曲率變化不大的平面點(diǎn)云精簡后出現(xiàn)“大孔洞”只有邊界上有少數(shù)數(shù)據(jù)點(diǎn),因此本文引進(jìn)另外一個(gè)與點(diǎn)間距離有關(guān)的參數(shù)Dis與Angl共同決定數(shù)據(jù)點(diǎn)的刪留。Dis參數(shù)由式(2)求得，考慮到當(dāng)前點(diǎn)P與前相鄰點(diǎn)U之間的距離以及當(dāng)前分層點(diǎn)云的幾何尺寸大小，其中K是一個(gè)刪減“孔洞”的影響因子，本文選為0.1。當(dāng)某個(gè)數(shù)據(jù)點(diǎn)的相關(guān)參數(shù)滿足式(3)，該數(shù)據(jù)點(diǎn)就會被保留，否則就被刪除。式(3)中的α和β分別是點(diǎn)的曲率影響因子和點(diǎn)的距離影響因子，它們的值越大，相關(guān)的參數(shù)在數(shù)據(jù)點(diǎn)刪留決策上影響也就越大中。本文選取α為0.85，β為0.15，Selector是決定這個(gè)點(diǎn)云精簡比例的參數(shù)，其值越大，刪去的點(diǎn)越多，點(diǎn)云數(shù)據(jù)壓縮比越大，一般推薦使用0.3～0.4范圍內(nèi)選取。

(1)

(2)

(3)

整合點(diǎn)云并顯示：將完成刪減過程的所有分層點(diǎn)云加入一個(gè)完整的點(diǎn)云數(shù)組中并顯示出來，以供用戶決策觀察。如用戶滿意就將精簡后的數(shù)據(jù)保存，本釋放相關(guān)數(shù)量空間；否則，釋放精簡數(shù)據(jù)結(jié)果，按照用戶重新輸入的參數(shù)再次進(jìn)行數(shù)據(jù)精簡操作。整個(gè)算法的流程圖如圖3所示。

圖3 算法流程圖

1.3 算法時(shí)間復(fù)雜度

本算法包括4個(gè)主要的步驟，假設(shè)點(diǎn)云中點(diǎn)的數(shù)量為N，點(diǎn)云讀入和點(diǎn)云參數(shù)統(tǒng)計(jì)步驟中要經(jīng)過取點(diǎn)、比較等操作，大概要經(jīng)5N次操作；點(diǎn)云分層方向?qū)ふ也襟E要進(jìn)行快速排數(shù)和坐標(biāo)值比較等操作，最壞情況要進(jìn)行3NlogN+3n次操作，n是每次坐標(biāo)值比較的次數(shù)，一般為幾十次；數(shù)據(jù)點(diǎn)刪減大概要經(jīng)分層操作和分層點(diǎn)云參數(shù)統(tǒng)計(jì)、層內(nèi)點(diǎn)云Angl參數(shù)計(jì)算、分層內(nèi)點(diǎn)云的快速排序、Dis參數(shù)的計(jì)算和點(diǎn)刪留條件的判斷等操作，大概要經(jīng)過的操作次數(shù)為4N+N+K(N/Klog(N/K))+N+N+N，其中K為分層層數(shù)；整合點(diǎn)云和顯示也要經(jīng)過2N次操作。整體算法大概要經(jīng)15N+3NlogN+Nlog(N/K)+3n次操作，所有本文算法的時(shí)間復(fù)雜度為O(NlogN)，保證了算法精簡的速度。

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

為了驗(yàn)證算法的實(shí)際效果，在圖4-圖7中給出了高爾夫球頭數(shù)據(jù)點(diǎn)云精簡前后的對比視圖。圖4中顯示的是原始的點(diǎn)云數(shù)據(jù)，該點(diǎn)云中包含了38 777個(gè)數(shù)據(jù)點(diǎn)，其他的相關(guān)參數(shù)在該截圖上也有顯示。圖5中的截圖是當(dāng)曲率影響系數(shù)α取0.85、距離影響系數(shù)β取0.15、保留選點(diǎn)參數(shù)Selector取0.33的精簡結(jié)果，精簡后點(diǎn)云中刪除了31 105個(gè)點(diǎn)，剩余7672個(gè)點(diǎn)，整體數(shù)據(jù)精簡率為505.44%，從圖中可以看到，曲率變化平坦的地方點(diǎn)很少，點(diǎn)主要集中的輪廓邊緣，整體運(yùn)行時(shí)間1389 ms；在圖6中的截圖的精簡中，曲率影響系數(shù)α和距離影響系數(shù)β仍然取0.85和0.15，保留選點(diǎn)參數(shù)Selector變?yōu)?.31，精簡后點(diǎn)云中刪除了24 875個(gè)點(diǎn)，剩余13 902個(gè)點(diǎn)，整體數(shù)據(jù)精簡率為278.93%。該圖中因?yàn)楸Ａ暨x點(diǎn)閾值選小了，選擇條件寬松了，留下的點(diǎn)多了，但仍然集中在曲率變化劇烈的邊緣處，這次運(yùn)行時(shí)間1061 ms。為了檢測精簡后的數(shù)據(jù)是否破壞了物體表面形狀和表面光滑度，本文對圖6中精簡的點(diǎn)云進(jìn)行了三角剖分，剖分的結(jié)果展示在圖7中，該圖說明精簡后沒有改變物體的形狀，形成的表面光順度較好。

圖4 原始點(diǎn)云數(shù)據(jù)

圖5 α=0.85 β=0.15 Selector=0.33精簡結(jié)果

圖6 α=0.85 β=0.15 Selector=0.31精簡結(jié)果

圖7 α=0.85 β=0.15 Selector=0.31精簡剖分結(jié)果

3 結(jié) 語

本文通過分析三維掃描儀形成的點(diǎn)云數(shù)據(jù)的特點(diǎn)，提出了一種改進(jìn)的分層曲率數(shù)據(jù)精簡算法。該算法通過將空間立體點(diǎn)云按照點(diǎn)云的特點(diǎn)轉(zhuǎn)化為平面內(nèi)的點(diǎn)云。通過簡單的平面內(nèi)Angl參數(shù)的計(jì)算代替了多數(shù)文獻(xiàn)中需要二次曲面擬合才能求得的點(diǎn)曲率，簡化了算法過程，降低了算法的復(fù)雜度。同時(shí)為了防止點(diǎn)云面因過于平坦，造成精簡后平面出現(xiàn)“大孔洞”的現(xiàn)象，算法中也引進(jìn)了距離參數(shù)Dis。通過綜合考慮點(diǎn)的曲率和點(diǎn)間的距離，形成了一個(gè)判別點(diǎn)是否被刪除的標(biāo)準(zhǔn)。通過修改該判別標(biāo)準(zhǔn)公式中的系數(shù)，可以得到不同的精簡效果。試驗(yàn)結(jié)果

證明，該算法不但算法復(fù)雜度低、運(yùn)算速度快，而且精簡效果好、數(shù)據(jù)精簡率高，對物體形狀和表面光順度影響小。

[1] 劉德平,陳建軍．逆向工程中數(shù)據(jù)精簡技術(shù)的研究[J]．西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2008,35(2):334-339．

[2] Yu Z W,Wong H S．ASM：an Adaptive Simplification Method for 3D Point-based Models[J]．Computer Aided Design,2010，42(7)：598-612．

[3] 方源敏，夏永華.基于改進(jìn)的角度偏差法的采空區(qū)點(diǎn)云數(shù)據(jù)精簡[J].地球科學(xué)與環(huán)境學(xué)報(bào),2012,34(2):106-111.

[4] 王茹,周明全.基于聚類平面特征的三維點(diǎn)云數(shù)據(jù)精簡算法[J].計(jì)算機(jī)工程,2011,37(10):249-254.

[5] 朱煜,康寶生.一種改進(jìn)的點(diǎn)云數(shù)據(jù)精簡方法[J]. 計(jì)算機(jī)應(yīng)用，2012,32(2)：521-523.

[6] 李鳳霞,饒永輝,劉陳,等.基于法向夾角的點(diǎn)云數(shù)據(jù)精簡算法[J].計(jì)算機(jī)仿真學(xué)報(bào),2012,24(9):1980-1984.

[7] 趙柳,馬禮,楊銀剛,等．逆向工程中散亂點(diǎn)云數(shù)據(jù)精簡研究[J]．光電技術(shù)應(yīng)用,2010,25(1)：60-63．

[8] Huang M C,Tai C C.The Pre-processing of Data Points for Curve Fitting in Reverse Engineering[J]．The International Journal of Advanced Manufacturing Technology,2010,16(9)：635-642．

IMPROVED MASSIVE POINT CLOUD REDUCING ALGORITHM BASED ON STRATIFIED CURVATURE

Chen Xinhe1Pang Junting2Zhou Bo3

1(SchoolofElectronicEngineeringandElectricAutomation,ChaohuUniversity,Chaohu238000,Anhui,China)2(SchoolofBusiness,HunanFirstNormalUniversity,Changsha410205,Hunan,China)3(SchoolofComputerandImformationEngineering,HeilongjiangUniversityofScienceandTechnology,Harbin150022,Heilongjiang,China)

Massive point cloud reduction shall consider both the complexity of the algorithm and the effect of reducing result. According to the characteristics of point cloud formed by 3-D scanner, we proposed to divide the spatial point cloud to the planar point cloud on scanning level, so that converted the space problem to the plane problem. Through simple calculation of Angl within the plane we got the point curvature, thus simplified the complexity of the algorithm. By introducing distance parameter Dis we avoided the emergence of “big hole” in reduction. By comprehensively considering the curvature of points and the distance between points, we formed a criterion determining whether to delete the points or not, and by modifying the coefficients in formula of determination criterion we could obtain different reduction effects. Test result proved that this algorithm was feasible in reducing practice of massive cloud point, and had the features of low complexity and high data reducing rate.

Massive point cloud Data reduction Curvature Segmented facets

2014-09-14。安徽高校省級科學(xué)研究2012年度項(xiàng)目(KJ2012B113)。陳新河，講師，主研領(lǐng)域：三維重建。龐俊亭，副教授。周波,教授。

TP391

A

10.3969/j.issn.1000-386x.2016.04.062