朱昂帆， 楊佳琪， 王 立

0 引 言

由激光雷達(dá)生成的點云可以精確表示真實對象的三維信息，并且這種表示方式已廣泛用于許多領(lǐng)域[1-2]，例如計算機視覺、計算機圖形學(xué).從點云進(jìn)行三維重建的一般過程涉及網(wǎng)格生成和表面渲染.但是，三維重建的精度通常受點分布不均勻的影響，這通常是由于設(shè)備缺陷，人為和環(huán)境干擾所造成的.尤其是在掃描結(jié)構(gòu)復(fù)雜的物體時，這種現(xiàn)象更加明顯.此外，原始點云中的冗余點可能會導(dǎo)致重建的表面上產(chǎn)生孔洞并帶來更高的計算量.因此，對于高質(zhì)量的點云三維重建，處理這種分布不規(guī)則的點集是非常有必要的.

目前，已經(jīng)有許多針對點云采樣點的研究.早期的研究主要是簡單地移除重疊區(qū)域的點.在文獻(xiàn)[3]中，作者用一個新的點來替換點云中原有的兩個點從而保證均勻的采樣分布.這類方法用新的點來替代原始點云中的冗余點或者直接將其去掉.另外一種策略是將點云劃分為許多網(wǎng)格單元，并用一種統(tǒng)一的表達(dá)形式來替代網(wǎng)格單元中的所有點，例如文獻(xiàn)[4].這類方法大多是基于八叉樹.這種通過空間分解的采樣方法可以更加方便快捷地控制采樣規(guī)模.

基于上述考慮，本文提出了一種新穎的基于全局約束的局部層次聚類的點云采樣方法.該方法用于處理非均勻點云數(shù)據(jù)，從而實現(xiàn)高質(zhì)量的三維重建.該方法同樣也是基于八叉樹.與先前的工作主要區(qū)別在于：該方法僅對網(wǎng)格單元中的冗余點進(jìn)行重新采樣，并且綜合考慮點云的全局約束條件，使采樣比例適應(yīng)于點云的整體尺寸大小.為了降低傳統(tǒng)聚類算法的計算復(fù)雜度，使用了三維空間分解的方法，隨后對局部點集(即空間分解后每個網(wǎng)格單元中的點)進(jìn)行分層聚類，以提高圖像的一致性.圖1比較了本文所使用的方法處理之前和之后的三維重建質(zhì)量.

圖1 采用層次聚類算法前后的點云分布對比結(jié)果Fig.1 Comparison results of point cloud distribution before andafter using hierarchical clustering algorithm

文章的剩余部分由以下章節(jié)構(gòu)成.第2節(jié)詳細(xì)介紹了本文所提出的方法，包括3D空間分解和層次聚類.第三部分介紹了本文所使用的方法在真實世界掃描點云上的驗證實驗.第四部分得出本文的結(jié)論.

1 方 法

本章節(jié)將詳細(xì)講解本文所采用的局部層次聚類方法.該方法由兩部分構(gòu)成：1.基于自適應(yīng)八叉樹的三維空間分解，2.層次聚類.前者將整個點云分解為一系列體素，從而加速整個計算過程；后者則對每個體素內(nèi)的點進(jìn)行處理，完成點云重構(gòu).

1.1 基于自適應(yīng)八叉樹的三維空間分解

基于八叉樹的空間分解的概念如下.令C為輸入點云，O為其三維邊界框.本文將O分解為許多小的網(wǎng)格單元，并稱之為體素[5].八叉樹由這些體素構(gòu)成并且點云C中的點被均勻的拆分到這n×n×n個體素當(dāng)中.八叉樹的構(gòu)建過程如圖2所示，其中l(wèi)代表每個體素v的邊長.

圖2 基于八叉樹的三維空間分解Fig.2 3D space decomposition based on octree

對于一給定的點云C，首先計算出其外接框的最大坐標(biāo)ptmax=[xmaxymaxzmax]與最小坐標(biāo)ptmin=[xminyminzmin],然后求出最大最小坐標(biāo)之間的距離D：

(1)

l=φ×D

(2)

其中φ是一個可變的參數(shù)，在本文中φ設(shè)為0.01為一個比較合適的范圍.

通過這樣一種自適應(yīng)的方式，使得每個體素的邊長可以隨著目標(biāo)尺寸的變化而變化，并且不會受到點云密度的影響.這在一定程度上也提高了算法的魯棒性.

1.2 層次聚類

當(dāng)八叉樹構(gòu)建完成后，點云C中的點就會分布在不同的體素當(dāng)中.給定一個具有m個點的體素v，本文希望的是將這些點分配到c個簇當(dāng)中.首先，將所有的m個點分為m個簇(即一個簇包含一個點).然后，以迭代的方式將兩個選定的點組合為一個簇.令ci為體素v在第i次迭代中簇的數(shù)量，如果沒有任何預(yù)設(shè)的迭代停止條件，則整個迭代過程將一直持續(xù)到ci=1為止，即所有點已經(jīng)合并到一個簇當(dāng)中.通常，可以使用一個距離約束來控制每個體素中的簇數(shù).令D1和D2構(gòu)成了體素v中的一個簇對，則簇對之間的距離定義為：

(3)

其中，wi是簇Di的中心.然后通過如下公式來獲得當(dāng)前迭代過程中距離最近的簇對D′和D″:

(D′,D″)=argmindist(Di,Dj)

(4)

圖3 二維空間中的局部層次聚類示意圖.Fig.3 Illustration of local hierarchical clustering in 2D space.

dc的大小決定了分層聚類后體素v的密度.為了克服點云密度的影響，采用如下公式來計算dc

dc=β×D

(5)

其中，β是一個常數(shù)，本文中，β設(shè)為0.005.

在通過上述方式對點云進(jìn)行層次聚類后，使用文獻(xiàn)[7]所提出的方法來完成后續(xù)的點云重建.

2 實 驗

在本節(jié)中，本文進(jìn)行了一系列實驗來驗證局部層次聚類方法在非合作目標(biāo)上的有效性.接下來，本文將分別展示實驗數(shù)據(jù)、評價指標(biāo)、比較方法、視覺效果以及定量結(jié)果.本文所采用的方法在VS2015、OpenGL和PCL[8]的基礎(chǔ)上實現(xiàn).所有實驗均在具有8 GB RAM的3.5 GHz Intel(R)Core 3處理器上進(jìn)行.

2.1 實驗數(shù)據(jù)與評價指標(biāo)

本文將三個非合作目標(biāo)的點云模型做為實驗數(shù)據(jù).初始的模型不含任何噪聲，本文將其作為實驗真值.然后，通過人為干預(yù)的方式使其點分布不均勻，從而作為本實驗的測試數(shù)據(jù).重構(gòu)誤差err(C,Cgt)的定義如下:

(6)

本文的評價準(zhǔn)則是計算采樣所得到的點云模型C與真值模型Cgt之間的重構(gòu)誤差.然而，點云的密度會對重構(gòu)誤差的計算產(chǎn)生較大的影響.因此，在文獻(xiàn)[9]的基礎(chǔ)上，本文使用重構(gòu)誤差除以點云的平均密度作為最終的評價指標(biāo)，從而保證能夠公平地比較不同密度的點云.

2.2 性能比較

本文使用文獻(xiàn)[4]所提出的采樣方法(US)和文獻(xiàn)[6]所提出的采樣方法(LHC)作為比較的基準(zhǔn).圖4和表1展示了兩種方法在非合作目標(biāo)數(shù)據(jù)集上的重建結(jié)果.從實驗結(jié)果中可以看到，無論是視覺感受還是定量比較，本文所提出的方法要優(yōu)于文獻(xiàn)[4]和文獻(xiàn)[6]所提出的方法.可以在測試數(shù)據(jù)上發(fā)現(xiàn)很多孔洞，這些孔洞則是由于點的不均勻分布導(dǎo)致的.我們所采用的方法則可以得到更多均勻分布的三角表面并保留更多的幾何特征.本文的重建誤差也更小，這表明了基于全局約束的局部層次聚類方法的有效性.

圖4 性能比較示意圖Fig.4 Visualization of performance comparison.

表1 3種方法的定量化性能比較Tab.1 Quantitative performance comparison of three methods

3 結(jié) 論

本文提出了一種基于全局約束的局部層次聚類的非均勻點云三維重建方法.這種方法主要包括兩個部分：1)基于自適應(yīng)八叉樹的空間分解；2)層次聚類.本文在非合作目標(biāo)點云數(shù)據(jù)上驗證了該方法的有效性.同時，與其他方法進(jìn)行了比較，進(jìn)一步顯示了該方法的優(yōu)越性.