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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

trunc—截斷取整；其余符號表示的意義與公式中的相同。

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

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

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

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

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

Algorithm.1 A Novel Voxel Grid Downsampling Method

3 實驗

3.1 實驗環(huán)境和實驗點云

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

表1 實驗點云和軸向包圍盒邊長（mm）Tab.1 Experimental Point Clouds and the Side Length of the Axis-Aligned Bounding Box（mm）

圖2 實驗點云Fig.2 Experimental Point Clouds

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

3.2 實驗結(jié)果和分析

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

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

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

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

表4 體素網(wǎng)格法和新方法降采樣的結(jié)果對比，長度單位mm，時間單位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)格和新方法降采樣后的點在原始點云中的實際效果，其中降采樣后的點用粗點顯示，原始點云用細點顯示。從圖4 中可見，對點云一，在降采樣點數(shù)量接近的情況下，直觀上看，體素網(wǎng)格方法和新方法降采樣效果的差異不明顯；對點云二來說，在降采樣點數(shù)量接近的情況下，體素網(wǎng)格方法和新方法降采樣效果有非常明顯的差異。差異主要體現(xiàn)在三個L形的零件在z軸方向的采樣點分布，體素網(wǎng)格方法得到的采樣點在z軸方向分布非常密集，而新方法得到的采樣點在z軸方向分布非常均勻。

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

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

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

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

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

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

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

4 結(jié)論

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