基于特征點和關鍵點提取的點云數據壓縮方法

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

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

1 引 言

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

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

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

2 壓縮方法描述

2.1 基本思路

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

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

2.2 法向量和曲率計算

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

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

ax+by+cz-d=0

(1)

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

(2)

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

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

(3)

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

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

(4)

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

(5)

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

Hi=a+c

(6)

2.3 特征點提取

2.3.1 邊界點提取

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

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

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

(3)以逆時針為方向,分別計算出兩相鄰投影向量的夾角βj(j+1)(j=k時,j+1=1),對夾角βj(j+1)升序排序,計算出兩相鄰夾角的最大差值Lmax；

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

2.3.2 尖銳點提取

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

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

(7)

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

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

(8)

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

(9)

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

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

2.4 SIFT關鍵點提取

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

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

(10)

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

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

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

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

(11)

(12)

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

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

(13)

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

(14)

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

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

(15)

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

3 實驗設計及方法運用對比分析

3.1 實驗設計及數據壓縮處理

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

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

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

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

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

為了驗證本文壓縮算法的可靠性,采用文獻[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#雕像在壓縮后屬于特征區域點的顏色較深,而在非特征區(參考圖2(c1))的點云數量較少且顏色較淺,整個點云模型的輪廓顯示的比較清晰。圖5(c1)是基于曲率分級壓縮的結果,曲率值越大曲率等級越高,被保留的可能性就越大,所以模型的特征點也能保留一部分,點云模型的輪廓也相對較清晰。由于實驗是基于相同的壓縮率進行的,圖3(c1)在非特征區的顏色比圖3(b1)深,說明在非特征區比圖3(b1)保留了較多的非特征點,那么特征點保留的數量就會相對的減少,因此會導致點云模型的特征比圖3(b1)丟失的較多。圖3(d1)是Geomagic studio軟件中的曲率采樣結果,在點云模型特征變化較大的地方也能夠保留一部分特征點,但點云模型的特征相較于圖3(b1)已經出現較大的丟失,比如模型中的輪子邊緣已相對較模糊,輪子中的幾何特征模糊不清,特征點丟失嚴重。圖3(a2)～(d2)與(a3)～(d3)是另外兩個模型的壓縮對比結果,顯示效果與圖3(a1)～(d1)基本相同。綜上,通過與另外兩種基于曲率壓縮方法壓縮結果的對比,本文所提方法壓縮質量更高。

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

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

(16)

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

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

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

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

4 結 論

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