一種基于體素網(wǎng)格的三維點(diǎn)云均勻降采樣方法

肖正濤，高 健，吳東慶，張攬宇

（1.廣東工業(yè)大學(xué)省部共建精密電子制造技術(shù)與裝備國家重點(diǎn)實(shí)驗(yàn)室，廣東廣州 510006；2.廣東工貿(mào)職業(yè)技術(shù)學(xué)院機(jī)電工程學(xué)院，廣東廣州 510510；3.仲愷農(nóng)業(yè)工程學(xué)院計(jì)算科學(xué)學(xué)院，廣東廣州 510220）

1 引言

隨著三維激光掃描技術(shù)的快速發(fā)展和普及，三維點(diǎn)云的獲取變得越來越容易。由于三維激光掃描技術(shù)具有非接觸、高效率、高精度等優(yōu)點(diǎn)，已被廣泛應(yīng)用在自動化加工生產(chǎn)線、虛擬現(xiàn)實(shí)、無人駕駛汽車等領(lǐng)域。由于實(shí)際得到的三維點(diǎn)云數(shù)據(jù)往往包含有大量的冗余數(shù)據(jù)，在使用點(diǎn)云數(shù)據(jù)前通常要進(jìn)行降采樣（Downs?Ampling［1］）處理，以提升點(diǎn)云的最終處理效率和效果。

降采樣，也稱下采樣，簡而言之就是對點(diǎn)云進(jìn)行精簡［2?3］。點(diǎn)云降采樣的方法有很多，通常分為不考慮點(diǎn)云細(xì)節(jié)特征和考慮點(diǎn)云細(xì)節(jié)特征兩大類。不考慮點(diǎn)云細(xì)節(jié)特征的降采樣方法有體素網(wǎng)格（Voxel Grid［4］）、系統(tǒng)采樣（Systematic Sampling［5］）、隨機(jī)采樣（Random Sampling［6］）、最遠(yuǎn)點(diǎn)采樣（Farthest Point Sampling［7］）等。考慮點(diǎn)云細(xì)節(jié)特征的算法一般會將點(diǎn)云的法向、曲率、是否位于邊緣等信息結(jié)合在內(nèi)。文獻(xiàn)［8］提出了一種基于柵格動態(tài)劃分的點(diǎn)云精簡方法，對不同的區(qū)域采取不同精簡策略，該方法能較好地保持模型的細(xì)微特征。文獻(xiàn)［9］提出了一種能夠保留邊緣點(diǎn)的點(diǎn)云簡化算法，通過八叉樹建立k鄰域，以法向量為依據(jù)檢測并保留邊緣特征點(diǎn)，該算法保留的邊緣點(diǎn)大部分為模型的尖銳點(diǎn)。文獻(xiàn)［10］提出了一種自適應(yīng)下采樣深度學(xué)習(xí)網(wǎng)絡(luò)，該方法能根據(jù)應(yīng)用、任務(wù)和訓(xùn)練數(shù)據(jù)的不同，減少無序點(diǎn)云中的點(diǎn)數(shù)，同時(shí)保留重要點(diǎn)。文獻(xiàn)［11］提出了一種基于曲率泊松碟采樣的散亂點(diǎn)云精簡方法，該方法通過計(jì)算點(diǎn)云的曲率特征將點(diǎn)云劃分為平坦區(qū)域和特征區(qū)域，然后對不同的區(qū)域使用不同的降采樣策略，使得平坦區(qū)域能夠均勻精簡的同時(shí)最大化地保留點(diǎn)云的細(xì)節(jié)特征。這些不同的降采樣方法通常有各自適合的應(yīng)用場景。

體素網(wǎng)格法是一種常用的降采樣方法。該方法先對三維點(diǎn)云建立軸向包圍盒（Axis?Aligned Bounding Box，簡稱AABB［12］），然后沿各個(gè)坐標(biāo)軸方向?qū)鼑蟹殖蒼等份，接著計(jì)算每一個(gè)體素中所有點(diǎn)的重心，并將其作為該體素的采樣值。體素網(wǎng)格法計(jì)算效率高，當(dāng)軸向包圍盒在x，y，z軸三個(gè)方向的邊長相差不是太過懸殊的情況下，得到的采樣點(diǎn)分布均勻，因而該方法被廣泛使用。

體素網(wǎng)格法存在著一個(gè)不足之處：當(dāng)點(diǎn)云的軸向包圍盒在x，y，z軸三個(gè)方向的邊長相差較大的時(shí)候，體素網(wǎng)格法得到的點(diǎn)云就變得不均勻，在長邊方向點(diǎn)的分布較稀，在短邊方向點(diǎn)的分布變得密集。不均勻點(diǎn)云會影響點(diǎn)云的法向和曲率計(jì)算，進(jìn)而影響點(diǎn)云的后續(xù)處理，如配準(zhǔn)、特征計(jì)算等的效果。因而，確保降采樣后的點(diǎn)云在空間分布均勻是一項(xiàng)非常重要的工作。

針對傳統(tǒng)體素網(wǎng)格法存在的不足，提出了一種新的體素網(wǎng)格法。該方法將點(diǎn)云軸向包圍盒沿x，y，z軸三個(gè)方向的邊分成不同的份數(shù)，使得每一個(gè)體素近似是正方體而不是與包圍盒相似的長方體，然后計(jì)算每一個(gè)體素內(nèi)所有點(diǎn)的重心，并將其作為該體素的采樣值。這樣，無論軸向包圍盒x，y，z軸三個(gè)方向的邊長是否相差懸殊，新的體素網(wǎng)格降采樣方法皆可得到均勻分布的降采樣點(diǎn)云。

2 一種新的體素網(wǎng)格法

當(dāng)點(diǎn)云軸向包圍盒在x，y，z軸三個(gè)方向的邊長相差不是太過懸殊的情況下，傳統(tǒng)體素網(wǎng)格法表現(xiàn)優(yōu)異，不僅計(jì)算效率高，而且得到的采樣點(diǎn)在空間分布也非常均勻。但當(dāng)點(diǎn)云軸向包圍盒在x，y，z軸三個(gè)方向的邊長相差非常懸殊的時(shí)候，由于x，y，z軸三個(gè)方向的邊都分成同樣的份數(shù)，每一個(gè)體素皆是一個(gè)與包圍盒相似的小長方體，因而每一個(gè)體素的邊長同樣也會相差懸殊，最終會導(dǎo)致包圍盒最短邊所在方向的采樣點(diǎn)分布比最長邊所在方向的點(diǎn)分布要密集得多，也即采樣點(diǎn)在空間分布不均勻。

針對傳統(tǒng)體素網(wǎng)格法存在的問題，提出了一種新的體素網(wǎng)格降采樣方法。該方法將點(diǎn)云軸向包圍盒x，y，z軸三個(gè)方向的邊分成不同的份數(shù)，使得每一個(gè)體素是正方體而不是與包圍盒相似的長方體。假設(shè)正方體體素的邊長是dLen，則點(diǎn)云軸向包圍盒x，y，z軸三個(gè)方向的邊分成的份數(shù)如下：

式中：Lx、Ly、Lz—軸向包圍盒沿x，y，z軸方向的邊長；nx、ny、nz—軸向包圍盒x，y，z軸三個(gè)方向的邊分成的份數(shù)；round—四舍五入運(yùn)算。

從公式可知，最終得到的每一個(gè)體素近似是一個(gè)正方體，如圖1（a）所示。任意點(diǎn)所在體素的三維索引( )

圖1 一種新的體素網(wǎng)格降采樣方法Fig.1 A Novel Voxel Grid Downsampling Method

i，j，k的計(jì)算公式，如式（2）所示。

式中：dx、dy、dz—點(diǎn)到包圍盒左側(cè)面、前表面和下表面的距離；

trunc—截?cái)嗳≌?；其余符號表示的意義與公式中的相同。

將所有體素的三維索引轉(zhuǎn)換為一維索引，如圖1（b）所示。如果按照先x軸方向，然后y軸方向，最后z軸方向的順序，從三維索引到一維索引的轉(zhuǎn)換公式如下：

式中：idx—體素的一維索引，i∈[0，nx]，j∈[0，ny]，k∈[0，nz]。

這樣，每一個(gè)三維索引(i，j，k) 就唯一對應(yīng)著一個(gè)一維索引idx。每一個(gè)一維索引idx也同樣唯一對應(yīng)著一個(gè)三維索引(i，j，k)，從公式可推知一維索引到三維索引的計(jì)算公式如下：

式（3）和式（4）建立起了體素三維索引與體素一維索引的一一對應(yīng)關(guān)系。新的體素網(wǎng)格降采樣方法的算法過程是：首先對點(diǎn)云建立軸向包圍盒，然后以某一個(gè)等分距離對包圍盒沿x，y，z軸三個(gè)方向的邊進(jìn)行等分，使得每一個(gè)體素近似為一個(gè)正方體，然后計(jì)算每一個(gè)體素內(nèi)所有點(diǎn)的重心，并將其作為該體素的采樣值。整個(gè)算法，如算法1所示。

算法1 一種新的體素網(wǎng)格下采樣方法

Algorithm.1 A Novel Voxel Grid Downsampling Method

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)點(diǎn)云

實(shí)驗(yàn)點(diǎn)云數(shù)據(jù)是用CREAFORM HandySCAN 700手持式三維激光掃描儀獲得，以O(shè)penCV和PCL（Point Cloud Library）為計(jì)算平臺，計(jì)算機(jī)配置是Intel 酷睿I5?7200U，12GB內(nèi)存。分別使用傳統(tǒng)的體素網(wǎng)格降采樣方法和新的體素網(wǎng)格降采樣方法對三維點(diǎn)云進(jìn)行降采樣，從降采樣的直觀效果和數(shù)據(jù)分析對兩種方法進(jìn)行了比較和討論。實(shí)驗(yàn)用的點(diǎn)云，如圖2所示。從兩個(gè)場景掃描獲得兩個(gè)點(diǎn)云，兩個(gè)場景中的物體主要是機(jī)加工零件。圖2（a）中的零件包含有凸起和凹陷的平面、階梯圓柱面、球冠面，還包含有凸起的文字和復(fù)雜曲面，其對應(yīng)的點(diǎn)云，如圖2（c）所示。圖2（b）中有3個(gè)散亂放置的L形零件，其對應(yīng)的點(diǎn)云，如圖2（d）所示。圖2（c）、圖2（d）在展示各個(gè)點(diǎn)云的同時(shí)，也展示出了各個(gè)點(diǎn)云的軸向包圍盒。表1展示了兩個(gè)實(shí)驗(yàn)點(diǎn)云各自包含的點(diǎn)數(shù)和尺寸，其中尺寸是指各個(gè)點(diǎn)云軸向包圍盒在x，y，z軸三個(gè)方向的邊長。結(jié)合圖2（c）、圖2（d）和表1，可知兩個(gè)點(diǎn)云軸向包圍盒的邊長比例皆不相同，其中點(diǎn)云二的包圍盒在z軸方向的邊長與在x，y軸方向的邊長差異非常懸殊。

表1 實(shí)驗(yàn)點(diǎn)云和軸向包圍盒邊長（mm）Tab.1 Experimental Point Clouds and the Side Length of the Axis-Aligned Bounding Box（mm）

圖2 實(shí)驗(yàn)點(diǎn)云Fig.2 Experimental Point Clouds

圖3 體素總數(shù)和計(jì)算時(shí)間Fig.3 Total Voxels and Computation Time

3.2 實(shí)驗(yàn)結(jié)果和分析

使用新方法，等分距離取10mm和15mm時(shí)，各個(gè)點(diǎn)云軸向包圍盒在x，y，z軸方向等分的份數(shù)和降采樣后的點(diǎn)數(shù)，如表2所示。結(jié)合表1、表2可知，由于各個(gè)點(diǎn)云軸向包圍盒在x，y，z軸方向的邊長各不相等，因而用新方法對點(diǎn)云進(jìn)行體素劃分時(shí)，x，y，z方向的等分?jǐn)?shù)也各不相同。

表2 新方法降采樣的結(jié)果（mm）Tab.2 Downsampling Results of the Proposed Method（mm）

為了便于比較新方法和傳統(tǒng)體素網(wǎng)格方法的降采樣效果，使用傳統(tǒng)體素網(wǎng)格降采樣方法，選取不同的等分?jǐn)?shù)對點(diǎn)云進(jìn)行降采樣，記錄各個(gè)點(diǎn)云不同等分?jǐn)?shù)對應(yīng)的降采樣后的點(diǎn)數(shù)，如表3所示。在表3中，無論等分?jǐn)?shù)為多少，降采樣后的點(diǎn)數(shù)量與表2中新方法降采樣后的點(diǎn)數(shù)量都不相同。因而，我們從表3中選取降采樣后的點(diǎn)數(shù)量與表2中降采樣后的點(diǎn)數(shù)量接近的值，并在表3中加粗顯示。同時(shí)，將表3中的這些數(shù)據(jù)摘抄出來，結(jié)合表2，并加上每種降采樣方法所用的計(jì)算時(shí)間，如表4所示。

表3 不同等分?jǐn)?shù)對應(yīng)的降采樣后的點(diǎn)數(shù)Tab.3 The Number of Points After Downsampling Corresponding to Different Subdivision

表4 體素網(wǎng)格法和新方法降采樣的結(jié)果對比，長度單位mm，時(shí)間單位sTab.4 Comparison of the Results of the Voxe Grid and Proposed Methods，Length Unit in mm and Time Unit in Seconds

圖4展示了用體素網(wǎng)格和新方法降采樣后的點(diǎn)在原始點(diǎn)云中的實(shí)際效果，其中降采樣后的點(diǎn)用粗點(diǎn)顯示，原始點(diǎn)云用細(xì)點(diǎn)顯示。從圖4 中可見，對點(diǎn)云一，在降采樣點(diǎn)數(shù)量接近的情況下，直觀上看，體素網(wǎng)格方法和新方法降采樣效果的差異不明顯；對點(diǎn)云二來說，在降采樣點(diǎn)數(shù)量接近的情況下，體素網(wǎng)格方法和新方法降采樣效果有非常明顯的差異。差異主要體現(xiàn)在三個(gè)L形的零件在z軸方向的采樣點(diǎn)分布，體素網(wǎng)格方法得到的采樣點(diǎn)在z軸方向分布非常密集，而新方法得到的采樣點(diǎn)在z軸方向分布非常均勻。

圖4 體素網(wǎng)格法和新方法降采樣后的實(shí)際效果對比Fig.4 Comparison of the Actual Effects of the Voxel Grid and Proposed Methods

計(jì)算降采樣后的點(diǎn)云各個(gè)點(diǎn)到其最近點(diǎn)的距離，并繪制相應(yīng)的頻數(shù)分布圖，如圖5所示。圖5中水平軸表示各點(diǎn)間的最近距離值，縱軸表示距離值在某個(gè)區(qū)間內(nèi)的點(diǎn)的數(shù)量。為了便于比較分析，當(dāng)降采樣點(diǎn)云的點(diǎn)數(shù)接近時(shí)，對應(yīng)的水平軸和縱軸的最大刻度和間隔皆取為相同。在圖5（a）、圖5（b）、圖5（e）、圖5（f）中，也即點(diǎn)云一，當(dāng)降采樣點(diǎn)云的點(diǎn)數(shù)接近時(shí)，靠近水平刻度0的幾個(gè)頻數(shù)分布無明顯差異，且頻數(shù)都比較小，這表明體素網(wǎng)格方法和新方法得到的采樣點(diǎn)都沒有出現(xiàn)過于密集的問題，這與圖4中的實(shí)際效果是一致的。在圖5（c）、圖5（d）、圖5（g）、圖5（h）中，也即點(diǎn)云二，靠近水平刻度0的幾個(gè)頻數(shù)分布有顯著差異，體素網(wǎng)格方法得到的靠近水平0刻度的幾個(gè)頻數(shù)分布直方圖較高，而新方法對應(yīng)的那幾個(gè)頻數(shù)直方圖則非常低，這表明體素網(wǎng)格方法得到的采樣點(diǎn)有相當(dāng)一部分靠得非常近，而新方法則沒有出現(xiàn)這個(gè)問題，這與圖4中的實(shí)際效果也是一致的。

圖5 頻數(shù)分布圖Fig.5 Frequency Distribution

根據(jù)計(jì)算得到的降采樣后的點(diǎn)云中各個(gè)點(diǎn)到其最近點(diǎn)的距離，接著計(jì)算出這些距離的平均值和標(biāo)準(zhǔn)差，并找出這些距離中的最小值、最大值，這些數(shù)值，如表5所示。從表5可知，對點(diǎn)云一，體素網(wǎng)格和新方法得到的降采樣后的點(diǎn)云的距離平均值和標(biāo)準(zhǔn)差都非常接近，這說明兩種方法得到的點(diǎn)云總體沒有明顯差異；對點(diǎn)云二，距離平均值則有顯著差異，新方法得到的點(diǎn)云的距離平均值明顯大于對應(yīng)的體素網(wǎng)格法，而新方法的距離標(biāo)準(zhǔn)差皆小于對應(yīng)的體素網(wǎng)格法，這說明新方法得到的點(diǎn)云在原始點(diǎn)云中的分布更均勻。

表5 體素網(wǎng)格法和新方法得到的點(diǎn)云中各個(gè)點(diǎn)之間的最近距離，長度單位mmTab.5 Nearest Distances Between Downsampling Points Obtained by the Voxel Grid and Proposed Methods，Length Unit in mm

從上面的實(shí)驗(yàn)數(shù)據(jù)和分析可見，當(dāng)點(diǎn)云軸向包圍盒在x，y，z軸方向的最長邊與最短邊的比值較小，比如點(diǎn)云一最長邊與最短邊比值為2.4，體素網(wǎng)格法和新方法降采樣的效果差別較?。划?dāng)點(diǎn)云軸向包圍盒在x，y，z軸方向的最長邊與最短邊的比值較大，比如點(diǎn)云二最長邊與最短邊比值為5.6，體素網(wǎng)格法和新方法降采樣的效果差別非常明顯，此時(shí)新方法優(yōu)于體素網(wǎng)格法。

將表4中的體素總數(shù)和計(jì)算時(shí)間數(shù)據(jù)分別繪制出來，如圖3所示。從圖3明顯可見，降采樣的計(jì)算時(shí)間折線走勢與體素總數(shù)曲線走勢一致，可見降采樣的計(jì)算時(shí)間與體素總數(shù)大致成線性關(guān)系，也即體素越多，降采樣所需要的計(jì)算時(shí)間也越長。從圖3我們還可看到，對同一個(gè)點(diǎn)云，當(dāng)降采樣后的點(diǎn)數(shù)相當(dāng)時(shí)，新方法得到體素?cái)?shù)量通常比體素網(wǎng)格法要少，因而新方法通常比體素網(wǎng)格法的計(jì)算速度更快。

4 結(jié)論

當(dāng)點(diǎn)云軸向包圍盒在x，y，z軸三個(gè)方向的邊長相差非常懸殊的時(shí)候，傳統(tǒng)的體素網(wǎng)格降采樣方法就存在著采樣點(diǎn)分布不均勻的問題。這是因?yàn)閭鹘y(tǒng)的體素網(wǎng)格法不考慮軸向包圍盒的邊長差異，直接將點(diǎn)云的軸向包圍盒沿各個(gè)坐標(biāo)軸方向皆分成n等份，最終導(dǎo)致包圍盒最短邊所在方向的采樣點(diǎn)分布比最長邊所在方向的采樣點(diǎn)分布要密集得多，也即采樣點(diǎn)在空間分布不均勻。針對這一問題，提出了一種新的體素網(wǎng)格降采樣方法。該方法首先對點(diǎn)云建立軸向包圍盒，然后以某一個(gè)等分距離對包圍盒沿x，y，z軸三個(gè)方向的邊進(jìn)行等分，使得每一個(gè)體素近似為一個(gè)正方體，然后計(jì)算每一個(gè)體素內(nèi)所有點(diǎn)的重心，并將其作為該體素的采樣值。從實(shí)驗(yàn)結(jié)果可見，當(dāng)降采樣后的點(diǎn)數(shù)大致相同時(shí)，若點(diǎn)云包圍盒在x，y，z軸三個(gè)方向的邊長相差不大，新方法和傳統(tǒng)體素網(wǎng)格法獲取的點(diǎn)云分布均勻程度相當(dāng)，但若點(diǎn)云包圍盒在x，y，z軸三個(gè)方向的邊長相差非常懸殊，新方法比傳統(tǒng)體素網(wǎng)格法獲取的點(diǎn)云分布更均勻。而且，新方法的計(jì)算效率高于傳統(tǒng)的體素網(wǎng)格法。