李繞波,袁希平,甘 淑,2,畢 瑞,胡 琳

(1.昆明理工大學(xué)國土資源工程學(xué)院,云南 昆明 650093；2.昆明理工大學(xué) 云南省高校高原山區(qū)空間信息測繪技術(shù)應(yīng)用工程研究中心,云南 昆明 650093；3.滇西應(yīng)用技術(shù)大學(xué)工程學(xué)院,云南 大理 671009)

1 引 言

三維激光掃描技術(shù)利用激光測距的原理迅速獲取掃描對象的三維坐標點云數(shù)據(jù),是一種新型的建立物體模型技術(shù)。雖然該技術(shù)可以快速獲取掃描對象的高密度數(shù)據(jù),但點云數(shù)據(jù)的海量特性,為后續(xù)存儲、處理點云數(shù)據(jù)帶來了很多問題,還直接影響到后續(xù)模型重建的精度和效率[1-2]。因此,在保證目標對象模型精度的前提下,有必要對點云數(shù)據(jù)進行壓縮處理,使點云數(shù)據(jù)量與模型精度相適應(yīng)。

目前,點云壓縮受到了很多學(xué)者的重視,并進行了一系列的實驗探究,提出了多種壓縮方法,在很大程度上改善了點云數(shù)據(jù)量過大的問題。點云數(shù)據(jù)壓縮應(yīng)用較為廣泛的方法有基于曲率的采樣法、基于網(wǎng)格拓撲信息的簡化法、基于法矢夾角的簡化法等。李金濤等[3]提出基于曲率分級的點云數(shù)據(jù)壓縮方法,該方法對分級后的曲率等級依照一定的準則進行數(shù)據(jù)壓縮,雖然能保留一部分的細節(jié)特征點,但在曲率變化緩慢的區(qū)域保留的不一點是關(guān)鍵點。賀一波等[4]引入k均值(k-means)聚類方法,首先對點云數(shù)據(jù)進行分類,通過比較每個點的曲率值和所有點的平均曲率值,實現(xiàn)點云數(shù)據(jù)的壓縮處理。該方法由于不需要建立格網(wǎng),有一定的速度優(yōu)勢,但點云數(shù)據(jù)壓縮的質(zhì)量與點云的分類質(zhì)量和分類組數(shù)有關(guān)。姚頑強等[5]利用八叉樹的樹型結(jié)構(gòu)在空間分解上的優(yōu)勢,結(jié)合點云的包圍盒簡化算法,實現(xiàn)點云數(shù)據(jù)的精簡,該算法雖然具有一定的速度優(yōu)勢,但細節(jié)特征點保留的較少。李仁忠等[6]對點云建立三維體素柵格,根據(jù)估計的法向量,完成對每個三維體素柵格的精簡,該方法能實現(xiàn)點云的均勻壓縮,但在特征變化較大區(qū)域卻不能保留較多的特征點。陳西江等[7]提出一種基于法向量夾角信息熵的點云壓縮方法,針對不同區(qū)域局部熵大小,實現(xiàn)不同程度的點云簡化,在特征豐富的區(qū)域保留較多的點,信息熵較小的區(qū)域保留少部分點。

經(jīng)過分析上述算法的局限性,本文提出一種基于特征點提取的點云數(shù)據(jù)壓縮方法。該方法首先根據(jù)每個點的k鄰域估計該點的法向量和曲率值,然后針對曲率值和法向量夾角變化較大的區(qū)域提取特征點,在平緩的區(qū)域則提取尺度不變特征轉(zhuǎn)換(Scale-invariant feature transform,SIFT)關(guān)鍵點,最后融合特征點和SIFT關(guān)鍵點,并刪除重復(fù)數(shù)據(jù),達到點云精簡的目的。該方法既能保留點云的絕大部分特征點,細節(jié)信息不易丟失,又能實現(xiàn)冗余數(shù)據(jù)的去除,最大化的提高了點云數(shù)據(jù)的質(zhì)量。

2 壓縮方法描述

2.1 基本思路

算法的基本思路如下:1)讀取點云,為點云建立拓撲結(jié)構(gòu)；2)計算點云的法向量和曲率；3)提取點云的特征點；4)提取點云的SIFT關(guān)鍵點；5)融合點云數(shù)據(jù),刪除相同點；6)；保存壓縮后的點云。算法流程如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flowchart

2.2 法向量和曲率計算

點云數(shù)據(jù)的法向量、曲率值等是點云數(shù)據(jù)的幾何屬性信息,在特征點提取過程中,為了能較多的保留特征點,需要計算點云的法向量和曲率值。為了快速對點云的鄰域搜索,本文采用k-d tree建立點云數(shù)據(jù)之間的拓撲關(guān)系[8],利用k-d tree根據(jù)查詢點與周圍點的歐式距離最小的k個點建立k鄰域。

完成所有點的k鄰域搜索后,可在此基礎(chǔ)上利用主成分分析法(PCA)計算點云的法向量。對于查詢點Pi的法向量,近似于估計查詢點Pi表面一個相切面的法向量,其k鄰域中的點擬合的空間平面方程為:

ax+by+cz-d=0

(1)

式中,a、b、c是平面方程的系數(shù),也是查詢點Pi的法向量;x、y、z是k鄰域中點的三維坐標值;d是原點到平面的距離。從查詢點Pi的k鄰域元素創(chuàng)建協(xié)方差矩陣A為:

(2)

然后進行k鄰域曲面擬合計算查詢點Pi的曲率值。二次曲面函數(shù)具有普遍的適用性,且便于后續(xù)的曲率計算,因此本文采用擬合二次曲面方法計算曲率值,二次曲面的初始擬合函數(shù)一般為:

z=f(x,y)=ax2+bxy+cy2+ex+fy

(3)

式中,a、b、c、e和f為二次曲面擬合系數(shù)。(3)式是(x,y)的單值函數(shù),一組(x,y)值對應(yīng)唯一的z值,而采集到的數(shù)據(jù)中有大量非單值映射的問題[9],因此有必要以查詢點Pi為原點建立局部坐標系(μ,υ,ω)。ω軸與Pi處法向量方向一致,μ軸與υ軸相互正交于切平面內(nèi),與ω軸共同構(gòu)成直角坐標系。經(jīng)過上述一系列的平移與旋轉(zhuǎn)后局部坐標系已建立完成。將(3)式改為局部坐標下的參數(shù)表達為:

S(μ,υ)=(μ,υ,ω(μ,υ))

(4)

ω(μ,υ)=aμ2+bμυ+cυ2+eμ+fυ

(5)

式中,a、b、c、e和f為二次曲面擬合參數(shù)。由于k鄰域的點數(shù)一般都大于5,因此依據(jù)最小二乘原理,可以求解曲面方程的系數(shù),再根據(jù)曲面方程與曲率的關(guān)系計算出Pi點的曲率值為:

Hi=a+c

(6)

2.3 特征點提取

2.3.1 邊界點提取

對于散亂點云,一般可劃分為平坦處點和特征點,而特征點又分為邊界點和尖銳點。點云邊界點是點云模型幾何形狀最基礎(chǔ)的保證,但在點云數(shù)據(jù)的壓縮過程中,外邊界點很容易丟失,導(dǎo)致壓縮后的點云模型的邊界并不完整,同時也影響到點云的壓縮質(zhì)量,為了避免此問題,本文在壓縮過程中先提取點云的邊界點,以保證點云模型邊界點的完整性。對于散亂點云數(shù)據(jù),若Pi點為邊界點,則Pi點k鄰域中的點則在三維坐標系中會偏向一側(cè),反之Pi為內(nèi)部點。利用邊界點的這一特性可以根據(jù)k鄰域的點與查詢點Pi構(gòu)成的法向量夾角的大小識別出邊界點,具體實現(xiàn)步驟如下:

(1)查詢點Pi為原點建立局部坐標系(μ,υ,ω),該坐標系ω軸與Pi處法向量方向一致,μ軸與υ軸相互正交于切平面內(nèi),與ω軸共同構(gòu)成直角坐標系；

(2)以Pi點為基準點,k鄰域中的點Pj為指向點,建立向量vij(j=1,2……k),并將向量投影到上一步建立的局部坐標上形成投影向量vj；

(3)以逆時針為方向,分別計算出兩相鄰?fù)队跋蛄康膴A角βj(j+1)(j=k時,j+1=1),對夾角βj(j+1)升序排序,計算出兩相鄰夾角的最大差值Lmax；

(4)通過比較給定的角度閾值Lstd與Lmax的大小,判斷Pi是否為邊界點。若Lmax>Lstd,則Pi為邊界點,反之為內(nèi)部點。

2.3.2 尖銳點提取

尖銳點通常在點云模型的構(gòu)建中有著至關(guān)重要的作用,尖銳點能直接反應(yīng)點云模型的幾何特征。點云的曲率值與相鄰法向量之間的夾角值作為點云數(shù)據(jù)幾何形狀的剛性特征能直接體現(xiàn)點云模型表面的凹凸性,因此可以將這兩個值作為尖銳點識別的重要參數(shù)。

(1)在Pi的k鄰域中,局部曲率的權(quán)值可以根據(jù)曲率值進行計算,表達式定義如下:

(7)

局部曲率權(quán)值參數(shù)是基于k鄰域中的曲率值計算而得,是多個點共同貢獻的結(jié)果,對單個噪聲點并不敏感,因此具有一定的魯棒性和較強的穩(wěn)健性。在δi相對較小的地方,說明該區(qū)域的幾何特征相對較平緩；在δi相對較大的地方,說明該區(qū)域曲率值變化較大,點Pi在該區(qū)域具有較多的幾何信息,成為尖銳點的可能性就越大。

(2)查詢點Pi與其k鄰域中法向量夾角的平均值可由表達式(8)計算得到:

(8)

式中,αj為點Pi法向量ni與其鄰域中點Pj法向量nj的夾角。

(9)

(4)為了避免尖銳檢測閾值F難以確定,同時因為尖銳點參數(shù)fi受到控制系數(shù)λ和τ的共同影響,因此將特征點識別閾值定義為：

式中，Hmax為曲率的最大值;t為所有尖銳點的距離值。若fi>F,則點Pi為尖銳點；反之為平坦處點。

2.4 SIFT關(guān)鍵點提取

點云模型曲率變化緩慢區(qū)域的數(shù)據(jù)壓縮通常的做法是進行均勻抽?；蚪y(tǒng)一采樣去除鄰近點,雖然能實現(xiàn)冗余數(shù)據(jù)的去除,但這些區(qū)域可能也存在一些關(guān)鍵點,容易造成平緩處關(guān)鍵點的丟失,導(dǎo)致壓縮效果不盡理想。尺度不變特征轉(zhuǎn)換是一種計算機視覺處理的算法,此算法在1999年由David L所提出并于2004年進行了改善[10-11]。2007年Flint 等[12]人將此算法應(yīng)用到三維圖像數(shù)據(jù)處理上。該算法基于高斯尺度空間的特征點檢測,特征點提取效率高,且可檢測的出大量的特征點[13-14],因此本文采用SIFT 算法對曲率變化緩慢的區(qū)域進行數(shù)據(jù)壓縮。

二維圖像的的方向梯度和角度如下定義[15]:

(10)

式中,Lx和Ly分別使用有限差分來計算:

因此在三維空間中的空間梯度(Lx,L-y,L-t)同樣可以計算出,其中:

Lt=L(x,y,t+1)-L(x,y,t-1)

現(xiàn)在將公式(10)擴展到三維空間上,可得到方向梯度和角度

(11)

(12)

下一步需要在給定關(guān)鍵點周圍建立加權(quán)直方圖。利用經(jīng)線和緯線將θ和φ分成大小相等的柱并創(chuàng)建二維直方圖,但從二維擴展到三維由于維度的問題會造成數(shù)據(jù)偏差,因此在劃分的過程中利用方位角將柱歸一化處理。方位角的計算公式如下:

=Δφ(cosθ-cos(θ+Δθ))

(13)

添加到直方圖中的實際值是較低的且可由公式(14)計算出,直方圖的峰值代表了關(guān)鍵點的主方向,可用于創(chuàng)建旋轉(zhuǎn)不變特征。

(14)

式中,(x,y,t)為特征點的位置;(x′,y′,t′)為要添加到方向直方圖像素的位置;σ為最小尺度標準偏差。

通過以上步驟,已得到每個關(guān)鍵點的必要信息。接下來為每個關(guān)鍵點建立一個SIFT描述符,使其具有旋轉(zhuǎn)不變性。以關(guān)鍵點為中心,旋轉(zhuǎn)坐標軸使其主方向指向θ=φ=0的方向,旋轉(zhuǎn)矩陣C為:

(15)

最后將關(guān)鍵點的區(qū)域劃分為4×4的單位小格子,將鄰域內(nèi)的采樣點分配到相應(yīng)的子區(qū)域中,并把每個小區(qū)域8個方向梯度值累加到直方圖中,因此,特征點描述子為4×4×8=128維度的特征向量。

3 實驗設(shè)計及方法運用對比分析

3.1 實驗設(shè)計及數(shù)據(jù)壓縮處理

采用3座(1#、2#、3#)雕像作為實驗對象。這類點云包含了豐富的特征信息,既有曲率變化緩慢的平坦處點,也有視覺效果特別明顯的特征點。首先計算點云的法向量和曲率,其次提取邊界線和尖銳點點,然后針對平坦區(qū)域提取SIFT關(guān)鍵點,接下來融合邊界點、尖銳點和SIFT關(guān)鍵點,并刪除相同數(shù)據(jù),最后保存壓縮結(jié)果,完成整個實驗。

圖2為采用本文算法對3座雕像模型的壓縮過程,第一行為第一個雕像的壓縮過程,第二行為第二個雕像的壓縮過程,第三行為第三個雕像的壓縮過程。表1為使用本文算法對3座雕像測試過程中點云數(shù)量變化情況。

圖2 使用本文算法分別測試3座雕像的過程Fig.2 Using the algorithm of this paper to test the process of three statues separately

表1 使用本文算法測試3座雕像每個過程中點云數(shù)量變量情況

在圖2(b1)～(b3)中,可以看到點云模型的邊界點已被完整的提取出來,保證了(e1)～(e3)邊界的完整性。圖2(c1)～(c3)是相應(yīng)的尖銳點提取結(jié)果,與原始點云模型相比已提取了模型中絕大數(shù)的尖銳點。圖2(d1)～(d3)顯示提取出的SIFT關(guān)鍵點,雖然已經(jīng)能呈現(xiàn)了大概的點云的模型,但細節(jié)不夠完善,因此針對平坦處提取SIFT關(guān)鍵點。表1展示了每個過程點云數(shù)量變化情況及最終的壓縮率,從表1可知邊界點在點云模型中所占的數(shù)量最少；由于本文測試的點云模型表面特征較多,因此提取出的尖銳點數(shù)量也較多,提取這些尖銳點能保證點云在實現(xiàn)高壓縮率的同時點云的幾何特征不易丟失。

為了驗證本文壓縮算法的可靠性,采用文獻[3]中基于曲率分級的壓縮方法和Geomagic Studio軟件中的曲率采樣法進行相同壓縮率的對比實驗分析,1#、2#、3#雕像實驗中采用的壓縮率分別為:37.00 %、50.40 %和36.40 %。

圖3為3種不同的方法壓縮3座雕像點云的壓縮效果,第一行為第一個雕像不同方法的壓縮效果,第二行為第二個雕像不同方法的壓縮效果,第三行為第三個雕像不同方法的壓縮效果。

圖3 3座雕像的原始點云模型與3種壓縮方法的壓縮效果Fig.3 The original point cloud model of 3 statues and the compression effect of 3 compression methods

3.2 實驗視覺效果評價對比分析

由圖3可知,三種方法都能達到達到點云壓縮的目的,且都能保留一部分的特征點。由于本文的壓縮方法是先把特征點提取出來,能對整個點云模型中的特征點做到最大程度的保留,因此在圖3(b1)中可以看到1#雕像在壓縮后屬于特征區(qū)域點的顏色較深,而在非特征區(qū)(參考圖2(c1))的點云數(shù)量較少且顏色較淺,整個點云模型的輪廓顯示的比較清晰。圖5(c1)是基于曲率分級壓縮的結(jié)果,曲率值越大曲率等級越高,被保留的可能性就越大,所以模型的特征點也能保留一部分,點云模型的輪廓也相對較清晰。由于實驗是基于相同的壓縮率進行的,圖3(c1)在非特征區(qū)的顏色比圖3(b1)深,說明在非特征區(qū)比圖3(b1)保留了較多的非特征點,那么特征點保留的數(shù)量就會相對的減少,因此會導(dǎo)致點云模型的特征比圖3(b1)丟失的較多。圖3(d1)是Geomagic studio軟件中的曲率采樣結(jié)果,在點云模型特征變化較大的地方也能夠保留一部分特征點,但點云模型的特征相較于圖3(b1)已經(jīng)出現(xiàn)較大的丟失,比如模型中的輪子邊緣已相對較模糊,輪子中的幾何特征模糊不清,特征點丟失嚴重。圖3(a2)～(d2)與(a3)～(d3)是另外兩個模型的壓縮對比結(jié)果,顯示效果與圖3(a1)～(d1)基本相同。綜上,通過與另外兩種基于曲率壓縮方法壓縮結(jié)果的對比,本文所提方法壓縮質(zhì)量更高。

3.3 實驗表面積評價對比分析

計算壓縮前后點云構(gòu)建的三角網(wǎng)的面積和,求出總面積變化情況,從而判斷壓縮前后點云模型特征的變化情況。變化率較大,說明壓縮過程中刪除了較多的特征點,反之,刪除的大部分是冗余數(shù)據(jù),對模型的特征改變較小。設(shè)第i個三角形(頂點為P1、P2、P3)的面積為Si,則:

(16)

式中,a、b、c分別是ΔP1P2P3三邊的邊長,p是ΔP1P2P3周長的一半:p=(a+b+c)/2。

對圖3中的點云數(shù)據(jù)進行面積計算,1#雕像壓縮前的面積為:26615.77cm2,2#雕像壓縮前的面積為:50338.29cm2,3#雕像壓縮前的面積為:62130.08cm2。表2列出了面積的變化情況。

表2 3個實驗對象應(yīng)用3種方法壓縮后的面積變化情況Tab.2 Changes in area of 3 experimental subjects after applying 3 methods of compression

通過比較分析表2發(fā)現(xiàn),壓縮率相同時,在3種壓縮方法中本文壓縮算法壓縮后的點云表面積變化率最小,且數(shù)值本身也相對較小,實現(xiàn)了高壓縮率而精度損失較小的目的。在壓縮過程中并沒有刪除過多的特征點,點云模型的幾何特征保留的較好。

4 結(jié) 論

采集到的點云數(shù)據(jù)中會存在大量的冗余數(shù)據(jù),這些數(shù)據(jù)會降低后續(xù)點云模型重建的效率和質(zhì)量,而現(xiàn)有壓縮方法并不能在實現(xiàn)高壓縮率的同時,保證壓縮后點云模型的精度損失較小。針對此問題,本文提出一種基于特征點和SIFT關(guān)鍵點提取的點云數(shù)據(jù)壓縮方法,該方法在特征區(qū)域提取邊界點和尖銳點,在平坦處提取SIFT關(guān)鍵點,以確保在特征區(qū)或非特征區(qū)提取的都是特征點。采用3座雕像的點云數(shù)據(jù)為實驗對象進行分析測試,最終實驗結(jié)果表明該方法能確保壓縮后的點云數(shù)據(jù)中保留大量的特征點。通過與曲率分級壓縮法Geomagic Studio軟件中的曲率采樣進行對比實驗,分析結(jié)果同樣表明了本文所提方法的可靠性。需要注意的是,在尖銳點的提取過程中,需要設(shè)置局部曲率權(quán)值控制系數(shù)和夾角平均控制系數(shù),由于尖銳點的判斷閾值是曲率的最大值,導(dǎo)致這兩個系數(shù)可選范圍較大,為了提高該方法的簡潔性,如何自動確定尖銳點提取閾值與局部曲率權(quán)值控制系數(shù)和夾角平均控制系數(shù)將是下一步的研究重點。