結(jié)合密度閾值和三角形組逼近的點(diǎn)云壓縮方法

鐘文彬，孫 思，李旭瑞，劉光帥

（1.中國電子科技集團(tuán)公司第十研究所，成都 610036；2.西南交通大學(xué)機(jī)械工程學(xué)院，成都 610031）

（*通信作者電子郵箱912505671@qq.com）

0 引言

近些年來三維掃描技術(shù)迅速發(fā)展，逆向工程中可以獲取的三維點(diǎn)云數(shù)據(jù)精度越來越高。隨之而來的是點(diǎn)云數(shù)據(jù)規(guī)模也日益龐大。一旦數(shù)據(jù)量大的點(diǎn)云需要存儲或通過速率受限制的通信通道進(jìn)行傳輸，壓縮操作就變得必不可少。壓縮可以降低點(diǎn)云的冗余度，并用較少數(shù)量的點(diǎn)云表達(dá)模型的特征。

現(xiàn)有的點(diǎn)云數(shù)據(jù)壓縮方法可以分為三類：基于網(wǎng)格拓?fù)湫畔⒌膲嚎s、基于曲面擬合的壓縮和基于點(diǎn)數(shù)據(jù)的壓縮［1］。

基于網(wǎng)格拓?fù)湫畔⒌膲嚎s一般是先預(yù)處理點(diǎn)云，獲得網(wǎng)格模型，建立網(wǎng)格之間的拓?fù)潢P(guān)系，再對其進(jìn)行壓縮。Hur等［2］針對光固化立體造型（STereo Lithography，STL）文件，提出基于Delaunay 三角剖分的壓縮方法，該方法在保證模型的精度上控制了時間成本；Kammerl等［3］提出用八叉樹空間分解點(diǎn)云，通過構(gòu)建點(diǎn)云的拓?fù)潢P(guān)系，編碼無序點(diǎn)云流的八叉樹結(jié)構(gòu)的差異性來減少時空冗余度；方芳等［4］對點(diǎn)云先進(jìn)行分層切片處理，然后對每層切片點(diǎn)云使用弦高差進(jìn)行壓縮；Houshiar等［5］提出將點(diǎn)云投影成全景圖像，之后采用基于圖像的方式壓縮點(diǎn)云。這類方法壓縮效果好，但是需要建立和維護(hù)大量的拓?fù)湫畔ⅲ嬎懔看?，效率較低。

基于曲面擬合的壓縮需要根據(jù)數(shù)據(jù)點(diǎn)集擬合一個曲面，利用曲面特性（曲率、法向量等）進(jìn)行重采樣。陳朋等［6］提出點(diǎn)到平面距離的無序點(diǎn)云壓縮方法，該方法計算點(diǎn)到最近的三個鄰域點(diǎn)組成平面的距離，通過距離的閾值來判斷壓縮對象表面的復(fù)雜程度；李金濤等［7］采用對數(shù)函數(shù)對歸一化后的曲率值進(jìn)行分級，對不同等級的點(diǎn)進(jìn)行空間網(wǎng)格劃分后分級壓縮點(diǎn)云；宋敏峰等［8］根據(jù)點(diǎn)云的法向量構(gòu)建K近鄰（KNearest Neighbor，KNN）長方體，根據(jù)長方體扁平程度將點(diǎn)云分為非特征點(diǎn)云和特征點(diǎn)云，結(jié)合分段壓縮去除大量冗余點(diǎn)和少量密集特征點(diǎn)。這類方法更易保留特征點(diǎn)，精度高，但由于需要求取采樣點(diǎn)的隱式表達(dá)式，壓縮速度較慢。

直接基于點(diǎn)數(shù)據(jù)的壓縮，不需要建立拓?fù)潢P(guān)系和重建曲面，操作簡單，壓縮速度快?；舅惴ㄓ斜壤龎嚎s法、包圍盒法、均勻網(wǎng)格法；但這些算法不能很好地表達(dá)細(xì)節(jié)特征，許多學(xué)者在此基礎(chǔ)上提出改進(jìn)。樊琦［9］改進(jìn)了區(qū)域重心法，不僅保留柵格的重心點(diǎn)，還保留一個符合閾值范圍的最遠(yuǎn)點(diǎn)；成煜鈐等［10］通過設(shè)定不同的權(quán)閾值，進(jìn)行點(diǎn)云的自適應(yīng)壓縮，但模型棱角特征遭到了破壞；Schwarz 等［11］針對靜態(tài)點(diǎn)云，采用三角形組表達(dá)體素內(nèi)點(diǎn)云表面信息，但不適用于非均勻采集點(diǎn)云。

通過上述分析，使用拓?fù)潢P(guān)系、法向量或曲率等信息決定壓縮參數(shù)，計算時間較長，而基于點(diǎn)的壓縮方法，多適用于特征簡單的均勻點(diǎn)云。針對非均勻點(diǎn)云的壓縮中壓縮精度和壓縮時間較難權(quán)衡的問題，本文提出一種結(jié)合密度閾值和三角形組逼近的點(diǎn)云壓縮方法。結(jié)合點(diǎn)云分布，分別確定密集區(qū)域和稀疏區(qū)域內(nèi)三角形組的頂點(diǎn)和細(xì)分點(diǎn)，再利用三角形組模擬原始體素內(nèi)點(diǎn)云表面。

1 三角形組逼近

因?yàn)槿瞧史帜転榍嬷亟ㄌ峁┳钚〉男螤顔挝?，故常用于點(diǎn)云曲面重建。實(shí)際情況下，運(yùn)用最多的是Delaunay 三角剖分。Delaunay 三角剖分旨在尋找到一個最優(yōu)的三角剖分，滿足空外接圓和最大-最小角特性?？胀饨訄A指的是每個三角形的外接圓內(nèi)部沒有其他點(diǎn)；最大-最小角指的是所有三角形的最小角達(dá)到最大。

點(diǎn)云庫（Point Cloud Library，PCL）中的貪婪投影三角化算法在二維上使用了基于Delaunay 的空間區(qū)域增長算法，先建立初始三角形，再擴(kuò)展三角形網(wǎng)格［12］。如圖1 所示，ΔABO是已經(jīng)確定的三角形，C和D是備選頂點(diǎn)，分別連接對角線BC和AD，可以得到對應(yīng)兩個三角形的角度序列：

比較可以得到AD＞BC，所以，選擇D作與AB組成三角形的頂點(diǎn)。

圖1 三角形擴(kuò)展Fig.1 Extension of triangle

本文使用三角逼近的思想，先將點(diǎn)云劃分為大小統(tǒng)一的體素；然后，將體素內(nèi)點(diǎn)云投影到某一平面上進(jìn)行三角形組構(gòu)造。在三角形組逼近點(diǎn)云表面的基礎(chǔ)上，用三角形組的頂點(diǎn)和細(xì)分點(diǎn)代替三角形網(wǎng)格信息。這樣不僅可以節(jié)省構(gòu)建網(wǎng)格的時間，還可以有效地壓縮點(diǎn)云數(shù)據(jù)。

2 算法描述

2.1 坐標(biāo)轉(zhuǎn)換

如圖2 所示，通過掃描儀獲得的點(diǎn)云數(shù)據(jù)表示為浮點(diǎn)數(shù)類型，既有正數(shù)也有負(fù)數(shù)。因?yàn)楹罄m(xù)計算細(xì)分點(diǎn)的坐標(biāo)時，需要的數(shù)據(jù)類型是正數(shù)，所以壓縮之前需先轉(zhuǎn)換坐標(biāo)。

圖2 坐標(biāo)轉(zhuǎn)換Fig.2 Coordinate transformation

2.2 建立八叉樹

利用PCL中的pcl：：octree：：OctreePointCloud函數(shù)初始化八叉樹，以便存儲和遍歷點(diǎn)云數(shù)據(jù)。八叉樹通過人為指定分辨率初始化，分辨率描述的是最低一級八叉樹的最小體素的實(shí)際尺寸。通過分析可以找到合適的分辨率，以達(dá)到合適的壓縮效果。對本文實(shí)驗(yàn)對象，dragon 點(diǎn)云選取0.002 作為最小體素尺寸；horse點(diǎn)云選取0.003作為最小體素尺寸；skull點(diǎn)云選取0.3作為最小體素尺寸；radome點(diǎn)云選取0.002 8作為最小體素尺寸；dog 點(diǎn)云選取1.5 作為最小體素尺寸；印制電路板（Printed Circuit Board，PCB）點(diǎn)云選取0.0025作為最小體素尺寸。

2.3 八叉樹體素內(nèi)點(diǎn)云壓縮

點(diǎn)云使用八叉樹進(jìn)行空間分割，其中，八叉樹葉節(jié)點(diǎn)的個數(shù)即是體素的個數(shù)。體素內(nèi)無復(fù)雜特征時，體素內(nèi)點(diǎn)可以投影到一個與坐標(biāo)軸垂直的平面上，保持鄰接關(guān)系不變。投影點(diǎn)云與原始點(diǎn)云得一一對應(yīng)，保證了二維各點(diǎn)的連接關(guān)系對應(yīng)三維各點(diǎn)的連接關(guān)系。如圖3 所示，體素內(nèi)部壓縮具體步驟分為確定三角形頂點(diǎn)、確定頂點(diǎn)分布信息、頂點(diǎn)排序、三角形構(gòu)造和細(xì)分點(diǎn)構(gòu)造。同時對應(yīng)算法流程如算法1 所示，其中輸入包括體素內(nèi)所有三維點(diǎn)的坐標(biāo)集合Pint、密度閾值(thr1與thr2)和體素的幾何信息Voxel；輸出為壓縮后三維點(diǎn)的坐標(biāo)集合。

圖3 壓縮流程Fig.3 Compression flowchart

2.3.1 確定三角形頂點(diǎn)

計算投影點(diǎn)的平均值qk。原始點(diǎn)云中距離qk最近的點(diǎn)即是lk對應(yīng)的頂點(diǎn)vk。遍歷體素的每一條邊，如圖3（c）所示，確定體素內(nèi)三角形的所有頂點(diǎn)。

圖4 計算頂點(diǎn)Fig.4 Calculation of vertices

2.3.2 確定頂點(diǎn)分布信息

確定頂點(diǎn)分布信息的第一步是根據(jù)頂點(diǎn)向量V計算頂點(diǎn)質(zhì)心μ=(μx，μy，μz)，并進(jìn)行主導(dǎo)軸判斷。確定主導(dǎo)軸，即是確定投影方向。如圖5 所示，分別將體素邊緣上的頂點(diǎn)沿x軸、y軸和z軸投影。結(jié)果顯示，沿x軸和z軸得到的投影圖出現(xiàn)了多個點(diǎn)投影到同一個位置的現(xiàn)象（圖5中空心點(diǎn)），為使得投影面上各點(diǎn)分散開，故選擇方差分量最小的軸作為主導(dǎo)軸［12］。根據(jù)

計算頂點(diǎn)到質(zhì)心的方差。其中：n是頂點(diǎn)的數(shù)量；對應(yīng)軸即是主導(dǎo)軸。

圖5 投影頂點(diǎn)Fig.5 Projection of vertices

第二步是將每個頂點(diǎn)投影到主導(dǎo)軸上，計算頂點(diǎn)分布信息vk.infor。如圖3（d）所示，頂點(diǎn)分布信息包含位置參數(shù)ai、bi和ci。其中，ci表示在主導(dǎo)軸方向上頂點(diǎn)與體素中心的距離；ai和bi表示其他兩軸上頂點(diǎn)與體素中心的距離。例如，則z是主導(dǎo)軸，則有ci=zi-mz、ai=xi-mx和bi=yi-my，其中m=(mx，my，mz)是體素的幾何中心。

最后一步是根據(jù)頂點(diǎn)的分布信息vk.infor計算頂點(diǎn)的角度vk.θ，即：

2.3.3 頂點(diǎn)排序

頂點(diǎn)角度vk.θ是頂點(diǎn)排序的依據(jù)。如圖6所示，將頂點(diǎn)投影到與主導(dǎo)軸垂直的平面上，降序排列頂點(diǎn)角度vk.θ。

圖6 頂點(diǎn)角度Fig.6 Angles of vertices

排序不僅有利于頂點(diǎn)的快速提取，還指定了三角形組逼近中遍歷頂點(diǎn)的順序。如圖3（e）所示，將散亂分布的頂點(diǎn)根據(jù)角度vk.θ的順序進(jìn)行編號。

2.3.4 三角形構(gòu)造

本文方法利用排序后的頂點(diǎn)列表對每個非空體素進(jìn)行三角形組的構(gòu)造。由于點(diǎn)云的表面是連續(xù)的，故在三角形組構(gòu)造時，應(yīng)避免體素內(nèi)模擬的三角形表面與鄰近體素內(nèi)的表面不連貫。因此，三角形組的邊緣線，即點(diǎn)云與體素表面的相交線，一定位于體素表面上。如圖7（a）和圖7（b）所示，邊緣線（虛線）懸空于體素內(nèi)部，不與鄰近體素接觸，正確的邊緣線如圖7（c）所示。

由于體素每條邊上最多一個頂點(diǎn)，故排序后的頂點(diǎn)列表中，相鄰兩個點(diǎn)在體素同一個表面內(nèi)，但連續(xù)的三個點(diǎn)不在同一個表面內(nèi)，如圖8 所示。Mammou 等［13］利用這一特性，直接連接頂點(diǎn)列表中的相鄰點(diǎn)作為三角形組的邊緣線，而相鄰邊緣線對應(yīng)的三個頂點(diǎn)將構(gòu)成一個三角形，如表1 所示。這樣構(gòu)造出的三角形組，其邊緣線一定在體素表面上，保證了相鄰體素三角形組的連貫性。圖8 顯示表1中具有5 個頂點(diǎn)的體素構(gòu)造三角形組的過程。在投影面上得到降序排列的頂點(diǎn)列表后，前三個頂點(diǎn)（1、2 和3）組成一個三角形。每組成一個三角形，就將該三角形中間頂點(diǎn)（2）從列表刪除，第一個頂點(diǎn)（1）移至列表末尾，重復(fù)取列表的前3 個點(diǎn)構(gòu)造三角形直至列表為空。

圖7 三角形組的邊緣線Fig.7 Edge lines of triangle groups

圖8 體素內(nèi)三角形組的構(gòu)成Fig.8 Formation of triangle groups in voxel

表1 三角形組的構(gòu)成Tab.1 Formation of triangle groups

2.3.5 細(xì)分點(diǎn)構(gòu)造

細(xì)分點(diǎn)指的是三角形內(nèi)部的點(diǎn)，其作用是避免三角形重構(gòu)時發(fā)生混淆。如算法1中RaysParallelToCoordinateAxi函數(shù)所示，細(xì)分點(diǎn)構(gòu)造需要在每個三角形內(nèi)構(gòu)造平行坐標(biāo)軸6個方向的射線，即(1，0，0)、(0，1，0)、(0，0，1)、(-1，0，0)、(0，-1，0)、（0，0，-1）。射線的起點(diǎn)取決于三角形三個頂點(diǎn)分別在x軸、y軸和z軸上的最小值和最大值(xmin，xmax，ymin，ymax，zmin，zmax)，構(gòu)造起點(diǎn)的步長受體素密度控制，如getStepSize函數(shù)所示。在體素尺寸固定的情況下，體素密度是體素內(nèi)點(diǎn)數(shù)的一元函數(shù)。本文方法以體素內(nèi)點(diǎn)云點(diǎn)數(shù)作為密度指標(biāo)，密度小使用大步長，密度大使用小步長。例如，構(gòu)造沿x軸正方向的射線時，如圖3（g）所示，射線起點(diǎn)的坐標(biāo)在x軸上的分量等于xmin，y軸上的分量在范圍(ymin，ymax)內(nèi)，z軸上的分量在范圍(zmin，zmax)內(nèi)。每條射線與三角形的交點(diǎn)，即是新的細(xì)分點(diǎn)。

算法1 體素內(nèi)壓縮算法。

3 實(shí)驗(yàn)與分析

選擇dragon 點(diǎn)云、horse 點(diǎn)云、skull 點(diǎn)云、radome 點(diǎn)云、dog點(diǎn)云和PCB 點(diǎn)云，對本文方法進(jìn)行實(shí)驗(yàn)、分析和評價。其中，dragon 點(diǎn)云、horse 點(diǎn)云、skull 點(diǎn)云和dog 點(diǎn)云取自斯坦福經(jīng)典點(diǎn)云數(shù)據(jù)庫，而radome點(diǎn)云和PCB點(diǎn)云是通過FreeScan X5激光手持三維掃描儀掃描得到的點(diǎn)云數(shù)據(jù)。各點(diǎn)云相關(guān)信息如表2所示，原始點(diǎn)云可視化如圖9所示。

表2 原始點(diǎn)云信息Tab.2 Information of original point cloud data

圖9 原始點(diǎn)云Fig.9 Original point clouds

dragon點(diǎn)云分布比較不均勻，細(xì)小特征多；horse點(diǎn)云分布較均勻，密度較小，特征少，多為大區(qū)域曲面；skull點(diǎn)云分布極其不均勻，面部區(qū)域細(xì)小特征多且密度大，后腦勺區(qū)域特征少且密度?。籸adome 點(diǎn)云分布較均勻，密度最大，特征少；dog 點(diǎn)云分布極不均勻，復(fù)雜特征集中在面部，同時具有尾巴等細(xì)長特征；PCB點(diǎn)云分布較不均勻，直角特征多。

實(shí)驗(yàn)使用系統(tǒng)Windows 7，CPU 為Inter Core i5-4590 CPU，內(nèi)存為16.0 GB。

3.1 體素尺寸

因?yàn)樯儆? 個頂點(diǎn)的體素不構(gòu)造三角形，所以，為了避免次特征部位（例如dragon 點(diǎn)云龍鱗部位和skull 點(diǎn)云臉頰部位）體素內(nèi)點(diǎn)過少，細(xì)分三角形效果不佳，體素的實(shí)際大小不宜過小；同時，為了避免密集部位特征不能完整表達(dá)，體素實(shí)際大小亦不宜過大。

如圖10 所示，dragon 點(diǎn)云、horse 點(diǎn)云和radome 點(diǎn)云隨著體素大小的增加，頂點(diǎn)少于3 個的體素占總非空體素的比例趨向于0。

圖10 dragon、horse、radome和PCB點(diǎn)云中頂點(diǎn)少于3個的體素占總非空體素的比例Fig.10 Proportion of the number of voxels with fewer than 3 vertices to total number of non-empty voxels in dragon，horse，radome and PCB point clouds

而針對skull 和dog 點(diǎn)云，從圖11 可以得到頂點(diǎn)少于3 個的體素占總非空體素的比例沒有趨向穩(wěn)定，這是因?yàn)樵紨?shù)據(jù)分布極不均勻，skull 點(diǎn)云后腦勺部位和dog 點(diǎn)云身體部位點(diǎn)云密度小，大多不能構(gòu)造三角形。

圖11 skull和dog點(diǎn)云中頂點(diǎn)少于3個的體素占總非空體素的比例Fig.11 Proportion of the number of voxels with fewer than 3 vertices to total number of non-empty voxels in skull and dog point clouds

結(jié)合圖12（a）和12（b），dragon點(diǎn)云的龍身部位，在體素大小達(dá)到0.003 2時，體素內(nèi)的彎曲特征不能通過構(gòu)造三角形組表達(dá)出來，而體素大小是0.001 6時，體素內(nèi)點(diǎn)分布無彎曲。所以，將體素大小控制在0.001 6 附近，以壓縮后所建模型的表面積變化率為指標(biāo)，進(jìn)一步分析最優(yōu)尺寸，結(jié)果如表3 所示。表面積變化率是將壓縮前和壓縮后的點(diǎn)云生成三角面片模型，并計算和比較兩個模型之間的表面積差異。為保證壓縮后模型與原始模型最接近，選取0.002 作為dragon 點(diǎn)云后續(xù)實(shí)驗(yàn)的體素尺寸。

同理，為保證三角形順利構(gòu)造的同時不丟失明顯特征信息，根據(jù)圖10、圖12（c）、圖12（d）和表3，選擇0.003作為horse點(diǎn)云后續(xù)實(shí)驗(yàn)的體素尺寸；根據(jù)圖10、圖12（g）、圖12（h）和表3，選擇0.002 8作為radome點(diǎn)云后續(xù)實(shí)驗(yàn)的體素尺寸。

而PCB 點(diǎn)云對應(yīng)曲線在體素大小等于0.001 2 和0.002時具有兩個凸脊，這是因?yàn)樵键c(diǎn)云在邊緣處具有少量孔洞，如圖9（i）所示。但體素大小大于0.002 后，隨著體素大小的繼續(xù)增加，頂點(diǎn)少于3 個的體素占總非空體素的比例開始收斂。結(jié)合圖10、圖12（k）、圖12（l）和表3，選擇0.002 5 作為PCB點(diǎn)云后續(xù)實(shí)驗(yàn)的體素尺寸。

圖13 為skull 點(diǎn)云臉頰部位和dog 點(diǎn)云身體部位不同尺寸體素內(nèi)點(diǎn)的分布。

表3 使用不同尺寸體素壓縮后的表面積變化率（不考慮細(xì)分點(diǎn)）Tab.3 Change rate of surface area after compression using voxels with different sizes（subdivision points are not considered）

圖12 原始點(diǎn)云特征部位不同尺寸體素內(nèi)點(diǎn)的分布Fig.12 Distribution of points in voxels with different sizes of feature regions of original point clouds

圖13 skull點(diǎn)云臉頰部位和dog點(diǎn)云身體部位不同尺寸體素內(nèi)點(diǎn)的分布Fig.13 Distribution of points in voxels with different sizes of cheek region of skull point cloud and the body region of dog point cloud

根據(jù)圖13（a～d）觀察到，skull 點(diǎn)云臉頰凹陷部位，在體素大小為0.08和0.16時不能構(gòu)造三角形；而圖12（e）和圖12（f）顯示，體素大小為0.64時，點(diǎn)云額頭符號處特征不能較好表達(dá)，所以，將體素大小控制在［0.16，0.64］內(nèi)，以壓縮后所建模型的表面積變化率為指標(biāo)，進(jìn)一步分析最優(yōu)尺寸，結(jié)果如表3所示。最終，選擇0.3 作為skull 點(diǎn)云后續(xù)實(shí)驗(yàn)的體素尺寸。同理，根據(jù)圖13（e～h）、圖12（i～j）和表3，選擇1.5 作為dog 點(diǎn)云后續(xù)實(shí)驗(yàn)的體素尺寸。

3.2 密度閾值

在確定體素大小后，如圖14 所示，以二分之一體素尺寸為半徑，觀察原始數(shù)據(jù)點(diǎn)的鄰域點(diǎn)信息。該鄰域信息可以大致反映出整體點(diǎn)云的密度情況，有助于密度閾值的選取。密度閾值不僅可以區(qū)分稀疏區(qū)域、較密集區(qū)域和密集區(qū)域，也可以區(qū)分特征程度。密集區(qū)域特征復(fù)雜，稀疏區(qū)域特征簡單。稀疏區(qū)域用最大的步長構(gòu)造射線，密集區(qū)域用最小的步長構(gòu)造射線。射線的構(gòu)造影響細(xì)分點(diǎn)的數(shù)量，使得壓縮后稀疏區(qū)域依舊比密集區(qū)域密度小，用較少的點(diǎn)表達(dá)較少的特征。

dragon 點(diǎn)云在龍身藍(lán)色部位特征少，鄰域點(diǎn)數(shù)不多于7個；在大面積的綠色部位，特征信息明顯增加，鄰域點(diǎn)數(shù)不多于28；在黃色或紅色區(qū)域，特征最復(fù)雜，鄰域點(diǎn)個數(shù)最多，甚至有的區(qū)域達(dá)到了40 個鄰域點(diǎn)。為將稀疏區(qū)域（藍(lán)色）和密集區(qū)域（黃色和紅色）區(qū)分開，選取［8，12］作為區(qū)分稀疏區(qū)域和較密集區(qū)域的閾值1（threshold1，thr1）范圍，同時選?。?3，27］作為區(qū)分較密集區(qū)域和密集區(qū)域的閾值2（threshold2，thr2）范圍。分析thr1時，以固定thr1 的情況下使用不同thr2壓縮后所得模型的平均表面積變化率為指標(biāo)。同理，分析thr2時，以固定thr2的情況下使用不同thr1壓縮后所得模型的平均表面積變化率為指標(biāo)，結(jié)果如表4 所示。為使壓縮后所得模型與原模型更接近，根據(jù)表4，選取10 和25 作為區(qū)分稀疏區(qū)域、較密集區(qū)域和密集區(qū)域的閾值。

horse點(diǎn)云藍(lán)色部位較少，鄰域點(diǎn)數(shù)不多于7個；大部分點(diǎn)位于綠色區(qū)域，其鄰域點(diǎn)數(shù)在9 個以下；黃色或紅色特征區(qū)域鄰域點(diǎn)數(shù)在10 個左右。所以，選取［6，8］作為區(qū)分稀疏區(qū)域和較密集區(qū)域的閾值范圍，同時選取［9，11］作為區(qū)分較密集區(qū)域和密集區(qū)域的閾值范圍。根據(jù)表4，選取7 和11 作為密度閾值。

同理，skull 點(diǎn)云根據(jù)圖14（c）中的鄰域信息和表4 的平均表面積變化率，選取4 和8 作為密度閾值；radome 點(diǎn)云根據(jù)圖14（d）中的鄰域信息和表4 的平均表面積變化率，選取18和28作為密度閾值；PCB點(diǎn)云根據(jù)圖14（f）中的鄰域信息和表4的平均表面積變化率，選取15和25作為密度閾值。

同時，從圖14（e）中的鄰域信息可以得到，dog 點(diǎn)云大部分處于藍(lán)色區(qū)域（身體部位），鄰域點(diǎn)個數(shù)不超過7 個；只有少量點(diǎn)位于黃綠色區(qū)域（面部和腳掌）和紅色區(qū)域（眼睛），但鄰域點(diǎn)個數(shù)較多。所以，只選擇［7，11］作為區(qū)分密集區(qū)域和稀疏區(qū)域的閾值范圍。根據(jù)表4，選擇7作為密度閾值。

圖14 原始數(shù)據(jù)鄰域點(diǎn)個數(shù)Fig.14 Number of neighborhood points of original data

表4 原始點(diǎn)云使用不同閾值壓縮后所得模型的平均表面積變化率Tab.4 Mean value of surface area change rate of the models obtained by original point clouds compressed with different threshold values

3.3 結(jié)果分析

分別用改進(jìn)區(qū)域重心法［9］、曲率壓縮法［14］、改進(jìn)曲率分級法［7］、K近鄰長方體法［8］和本文方法對原始數(shù)據(jù)進(jìn)行處理。區(qū)域重心法的柵格大小和3.1 節(jié)提到的各點(diǎn)云體素大小一致；曲率壓縮的方法，保證壓縮率與本文方法大體一致；改進(jìn)曲率分級壓縮中特征區(qū)域尺寸與3.1 節(jié)提到的各點(diǎn)云體素大小一致，保證分析點(diǎn)云特征時最小單元一致；K近鄰長方體法取α=0.8，同時控制壓縮率與本文一致。

從表5 和表6 知，在體素大小一致的情況下，改進(jìn)區(qū)域重心法比本文方法壓縮更多的點(diǎn)，時間更快。在壓縮率接近的情況下，曲率壓縮法、改進(jìn)曲率分級法和K近鄰長方體法需要比本文更多的時間，這是因?yàn)檫@三種方法在計算曲率或法向量上消耗了大量時間。同時，表5中使用改進(jìn)曲率分級法對skull 和dog 點(diǎn)云壓縮時，剩余點(diǎn)數(shù)高于本文方法，這是因?yàn)槭芴卣鲄^(qū)域尺寸限制，記錄的是壓縮率最大（壓縮因子最?。r剩余點(diǎn)數(shù)。即使如此，由于改進(jìn)曲率分級法中主要耗時在于曲率計算和曲率對數(shù)化，壓縮率變化對耗時影響較小，故表6中skull和dog點(diǎn)云使用改進(jìn)曲率分級法的耗時遠(yuǎn)高于本文方法，也能側(cè)面印證本文方法在時間效率上優(yōu)于改進(jìn)曲率分級法。所以，在時間效率上，本文方法介于改進(jìn)區(qū)域重心法和需要計算曲率或法向量的方法之間。

表5 壓縮后剩余點(diǎn)數(shù)對比Tab.5 Comparison of remaining points after compression

觀察6 種方法結(jié)果，分別對壓縮后的數(shù)據(jù)使用geomagic studio12 軟件封裝顯示，并使用最大偏差、標(biāo)準(zhǔn)偏差和表面積變化率進(jìn)行分析。圖15～16 為6 種點(diǎn)云數(shù)據(jù)的geomagic 封裝示意圖。

圖15 dragon、horse和skull點(diǎn)云geomagic封裝示意圖Fig.15 geomagic package schematic diagrams of dragon，horse and skull point clouds

圖15（a～f）顯示，dragon 點(diǎn)云經(jīng)過改進(jìn)區(qū)域重心法壓縮，模型的頭部、脖子和背鰭部分細(xì)節(jié)丟失，整體效果極差，而通過曲率壓縮、改進(jìn)曲率分級法、K近鄰長方體法和本文方法得到的模型大部分特征保留。同時，本文方法壓縮后的模型相較于曲率壓縮和K近鄰長方體法在細(xì)小特征上（橢圓部分）有較好效果。圖15（g～l）顯示，horse 點(diǎn)云使用改進(jìn)區(qū)域重心法模型頭部失真，并且在模型腳部（圖15（g）黃色部位）因數(shù)據(jù)丟失過多造成相鄰區(qū)域法向量方向不同。同時，K近鄰長方體法壓縮后所建模型在腳部明顯比原始數(shù)據(jù)粗糙，而曲率壓縮、改進(jìn)曲率分級法和本文方法所建模型與原始模型更接近。圖15（m～r）顯示，skull點(diǎn)云通過5種方法得到的模型都出現(xiàn)不同程度的失真，但在整體效果和牙齒等特征部位，本文方法效果最好。

圖16（a～f）顯示，radome點(diǎn)云使用改進(jìn)區(qū)域重心法效果最差，不僅表面粗糙還有大面積孔洞（圖16（a）綠色線條圈出部位）；曲率壓縮后所建模型有少量孔洞和相鄰區(qū)域法向量方向不同現(xiàn)象；改進(jìn)曲率分級法效果稍好，但仍有相鄰區(qū)域法向量方向不同現(xiàn)象；本文方法和K近鄰長方體法效果與原數(shù)據(jù)效果最接近。圖16（g～l）顯示，dog 點(diǎn)云原始數(shù)據(jù)所建模型在尾部因密度小，有斷層情況；曲率壓縮和K近鄰長方體法所建模型出現(xiàn)腹部斷層，這是因?yàn)樵搮^(qū)域過度壓縮，造成點(diǎn)云密度過小，不能成功封裝，如圖17 所示；改進(jìn)區(qū)域重心法和改進(jìn)曲率分級法壓縮后尾部發(fā)生變形；本文方法壓縮后不僅無過度壓縮情況，而且尾部形狀較完整。圖16（m～r）顯示，PCB 點(diǎn)云使用改進(jìn)區(qū)域重心法效果最差，K近鄰長方體法稍好，但在邊緣處出現(xiàn)孔洞，而改進(jìn)曲率分級法和本文方法壓縮后得到的模型與原始模型更接近。

表7 反映出5 種方法壓縮后的最大偏差和標(biāo)準(zhǔn)偏差。偏差分析可以顯示出測試模型和參考模型之間的空間差異。其中，最大偏差測量的是測試模型到參考模型中任意點(diǎn)的距離的最大值，而標(biāo)準(zhǔn)偏差反映了整體模型的偏差情況，偏差越大則測試模型與參考模型差異越大。其中，dog點(diǎn)云因?yàn)槭褂们蕢嚎s法和K近鄰長方體法壓縮后得不到反映實(shí)際特征的模型，不考慮相應(yīng)偏差。針對6 種點(diǎn)云數(shù)據(jù)，通過本文方法得到的最大偏差皆低于改進(jìn)區(qū)域重心法、曲率壓縮法、改進(jìn)曲率分級法和K近鄰長方體法。在標(biāo)準(zhǔn)偏差上，dragon 和PCB 點(diǎn)云標(biāo)準(zhǔn)偏差都是0；horse 點(diǎn)云基于改進(jìn)區(qū)域重心法標(biāo)準(zhǔn)偏差最高；skull 和dog 點(diǎn)云壓縮前后都有標(biāo)準(zhǔn)偏差，這是因?yàn)槊芏刃〉膮^(qū)域壓縮發(fā)生了變形，但本文方法的標(biāo)準(zhǔn)偏差小于其他方法；radome點(diǎn)云本文方法標(biāo)準(zhǔn)偏差最小。數(shù)據(jù)顯示，本文方法對于密度較大的點(diǎn)云，壓縮后點(diǎn)云更接近原始點(diǎn)云。

圖17 dog點(diǎn)云示意圖Fig.17 Schematic diagrams of dog point cloud

同時，本文使用表面積變化率分析點(diǎn)云壓縮精度。假設(shè)原始點(diǎn)云建模得到的表面積為真值，表面積變化率可以近似反映點(diǎn)云壓縮的精度［8］。表8顯示，壓縮前后表面積變化率是區(qū)域重心法最高，本文方法最低，驗(yàn)證了本文方法比其他方法效果好。

通過對比不同方法可以得到，本文方法在高壓縮率的情況下，可以保留原數(shù)據(jù)點(diǎn)云絕大多數(shù)特征，所建模型與原始點(diǎn)云模型最接近，整體壓縮效果良好。

表6 壓縮時間對比Tab.6 Comparison of compression time

表7 最大偏差和標(biāo)準(zhǔn)偏差對比Tab.7 Comparison of maximum deviation and standard deviation

表8 表面積變化率對比Tab.8 Comparison of surface area change rate

4 結(jié)語

針對非均勻采集點(diǎn)云數(shù)據(jù)壓縮中壓縮精度和壓縮時間較難權(quán)衡的問題，本文提出了一種結(jié)合密度閾值和三角形組逼近的壓縮方法。該方法在八叉樹劃分的基礎(chǔ)上，對每個非空體素構(gòu)造三角形組逼近體素內(nèi)點(diǎn)云表面，并采用密度閾值決定三角形細(xì)分點(diǎn)的步長；通對對點(diǎn)云在不同體素尺寸下能夠構(gòu)造三角形組的體素占總體素的比例和體素內(nèi)部點(diǎn)的分布分析，選擇合適的八叉樹分辨率；通過對點(diǎn)云的鄰域分析，選擇相應(yīng)密度閾值。針對dragon、horse、skull、radome、dog 和PCB點(diǎn)云，分別進(jìn)行改進(jìn)區(qū)域重心法、曲率壓縮法、改進(jìn)曲率分級法、K近鄰長方體法和本文方法的壓縮對比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示，區(qū)域重心法速度最快，壓縮率最高，但特征丟失多，偏差最大，表面積變化率最大；曲率壓縮速度較慢，特征保留較完整，有非特征區(qū)域過度壓縮情況，偏差和表面積變化率較大；改進(jìn)曲率分級法速度較慢，特征保留完整，偏差和表面積變化率小于曲率壓縮；K近鄰長方體法速度最慢，有非特征區(qū)域過度壓縮情況，偏差和表面積變化率小于改進(jìn)區(qū)域重心法；本文方法速度適中，特征保留完整，偏差和表面積變化率最小。實(shí)驗(yàn)驗(yàn)證了本文方法可以在較短的時間內(nèi)較好地保留特征信息。

本文方法是通過數(shù)據(jù)分析后人為選取合適的八叉樹分辨率和密度閾值，下一步將在該方法的基礎(chǔ)上，進(jìn)一步研究參數(shù)的自適應(yīng)設(shè)定。