一種結(jié)合邊緣點和特征點的點云精簡方法及其效果評價

楊森,花向紅,李丞,水浩奇,高金彬,張澗栗

(1.武漢大學(xué)測繪學(xué)院,湖北 武漢 430079; 2.武漢大學(xué)災(zāi)害監(jiān)測與防治研究中心,湖北 武漢 430079)

0 引 言

相比傳統(tǒng)測量技術(shù),三維激光技術(shù)在數(shù)據(jù)獲取方面具有快速、精確等特點[1],被廣泛應(yīng)用于變形監(jiān)測[2,3]、地形測繪[4]、文物保護[5]等領(lǐng)域。隨著三維激光掃描技術(shù)的快速發(fā)展,設(shè)備采集的數(shù)據(jù)精度和速度都有了很大提升,數(shù)據(jù)量十分巨大,為后續(xù)點云處理帶來了很大的困擾[6]。如何合理進行點云精簡,減少無效特征點云,保證點云特征不受破壞成為點云數(shù)據(jù)預(yù)處理中一個重要研究內(nèi)容。

國內(nèi)外學(xué)者針對點云精簡做了大量研究,根據(jù)精簡思路主要分為三種:包圍盒法、隨機采樣法和曲率采樣法[7]。文獻[8]通過構(gòu)建點云法向量特征和點云曲率特征約束,結(jié)合體素包圍盒算法,能夠在不損失點云特征的情況下,實現(xiàn)點云的快速精簡。文獻[9]提出基于快速點特征直方圖(FPFH)特征提取的點云精簡算法,算法首先提取出點云邊緣點,計算非邊緣點的FPFH值得到點云特征點,利用特征值將點云分為特征區(qū)域和非特征區(qū)域,利用最遠點采樣算法對非特征區(qū)域進行采樣,結(jié)果表明算法既能保留精簡模型的完整性也能較好地保留點云的大部分特征信息。文獻[10]先對點云進行k均值聚類,類內(nèi)法方向差值大于閾值時拆分為兩類,迭代得到分類結(jié)果,在平坦區(qū)域保留聚類中心,在非平坦區(qū)域保留法向量差值最大的點,得到的精簡點云誤差更小。文獻[11]利用主成分分析(principal component analysis,PCA)方法估計點云法向量及其夾角,然后利用最近鄰點獲取法向量夾角的信息熵,根據(jù)熵的大小實現(xiàn)點云精簡。文獻[12]提出保留點云屬性的點云精簡方法,對點云X,Y軸方向進行分割運算,提取X-Y邊界,對提取邊界后的散亂點云數(shù)據(jù)構(gòu)建K鄰域,通過鄰域計算模糊熵和曲率,剔除曲率小于閾值的點實現(xiàn)點云的精簡。為此,本文針對獲得的點云原始數(shù)據(jù)十分龐大和原始點云數(shù)據(jù)中存在大量冗余的問題,提出一種結(jié)合邊緣點和特征點提取的點云精簡方法。通過實驗,采用精簡率、豪斯多夫距離和幾何失真指數(shù)三個評價指標,將本文方法與隨機采樣、均勻采樣和法向空間采樣三種方法精簡結(jié)果進行了對比分析,得出了有益結(jié)論。

1 基本原理

針對獲得的點云原始數(shù)據(jù)十分龐大和原始點云數(shù)據(jù)中存在大量冗余的問題,本文提出了一種結(jié)合邊緣特征點和內(nèi)部特征點提取,在非特征區(qū)域進行最遠點采樣的點云精簡方法。該方法的基本思想如下:首先建立點云的K領(lǐng)域關(guān)系,根據(jù)PCA算法求得點云的邊緣點;然后通過點云的K領(lǐng)域關(guān)系,計算點云的ISS特征點,對點云構(gòu)造尺度空間求得點云的SIFT3D特征點,從而提取點云特征點;之后將邊緣點和特征點的重心作為最遠點采樣的起始點,對空洞區(qū)域進行點云增補;最后將邊緣點、特征點和最遠點采樣得到的三類點云合并,設(shè)置閾值去除重復(fù)點,實現(xiàn)點云精簡。其方法流程如圖1所示。

圖1 本文方法流程圖

1.1 基于PCA法矢估計的點云邊界提取

對點云來說,邊界輪廓是一種重要的特征,對點云邊緣的提取可以最大限度地保留點云的邊界特征,因此在精簡點云數(shù)據(jù)前需要先將點云的邊界提取出來。

法向量估計是提取物體邊界特征的一個關(guān)鍵過程,估計點云表面法線可以轉(zhuǎn)化為求點切面的問題,假設(shè)給定點p(xi,yi,zi),i=1,2,…,n,擬合的平面方程為zi=axi+byi+c,估計值和實際值之間的總誤差方程式如下:

(1)

(2)

要擬合出這個平面可以轉(zhuǎn)化為求出平面上某一點和此平面的法向量,這一點就是目標點p和它的k個鄰近點的平均點c,首先對整個點云構(gòu)建k-d樹,然后根據(jù)k-d樹搜索目標點p的k個鄰近點,通過最小化目標函數(shù)(1)來求法向量,其中n為待求法向量,根據(jù)PCA算法就可以求出該點對應(yīng)的法向量。

(3)

(4)

在以最小二乘法擬合出切平面后,將采樣點p和k個近鄰點投影到切平面上,以采樣點p的投影點為起點,近鄰點的投影點為終點定義k個向量,選定任一向量作為起始向量,按照(順時針或逆時針)順序計算相鄰兩向量之間的角度,得到夾角的集合A={α1,α2,…,αk},計算這些角度中的最大值αi,若最大值αi大于閾值θ,則該點被判定為邊界點,保留該點為邊緣點,否則刪除該點(如圖2所示)。逐點對點云數(shù)據(jù)進行計算,從而完成邊界特征點提取。

圖2 邊緣點和非邊緣點示意圖

1.2 特征點提取

常見的三維點云特征點提取算法主要有Harris3D、NARF、ISS3D、SIFT3D等,其中,Harris3D算法利用點云的法向量提取出點云的角點和邊緣點;NARF算法在深度圖像中進行關(guān)鍵點提取,降低了關(guān)鍵點提取的計算量,但是需要花費較長時間將點云轉(zhuǎn)換為深度圖像,轉(zhuǎn)換過程中存在精度損失,NARF算法和Harris3D提取出的關(guān)鍵點主要是邊緣點;根據(jù)文獻[13]知,ISS3D算法和SIFT3D算法在點云存在旋轉(zhuǎn)、平移和縮放的情況下仍具有良好的穩(wěn)健性,ISS3D算法和SIFT3D算法可以很好地提取點云的內(nèi)部特征點。因此,本文采用ISS3D和SIFT3D兩種方法提取點云內(nèi)部的特征點。

(1)ISS3D算法

(2)SIFT3D特征點

SIFT3D是對2D圖像SIFT[15]的擴充,被應(yīng)用于點云的處理中,對點云視角變化、平移變換具有很好的穩(wěn)定性。SIFT3D關(guān)鍵點提取主要分為三部分:在點云尺度空間中檢測極值點、確定關(guān)鍵點方向、關(guān)鍵點描述子的表示。首先對點云進行濾波,構(gòu)造點云金字塔,對金字塔中每個點云構(gòu)建高斯尺度空間,然后使用尺度空間構(gòu)建高斯差分空間(DoG),通過比較點pi與鄰域點的大小來判斷pi點是否為極值點,鄰域點包括同一層相鄰的8個點以及上下兩層各9個點;之后對極值點進行篩選得到穩(wěn)定的極值點即特征點,根據(jù)特征點的局部特性來確定方向,每個特征點可以使用(x,y,z,σ,θ,Φ)來表示,其中(x,y,z)為空間坐標,σ為尺度信息;在確定特征點的方向后,建立包含尺度、位置和方向信息的描述符來對特征點進行描述。

1.3 點云增補與刪除

在提取出點云邊緣點和點云內(nèi)部的特征點后,在點云平坦區(qū)域可能會存在空洞,需要對平坦區(qū)域進行適當?shù)狞c云增補。本文采用改進的最遠點采樣算法對空洞進行修補,最遠點采樣算法[16](Fast point sampling,FPS)是3D點云深度學(xué)習(xí)框架PointNet++中的采樣算法,算法主要步驟如下:

(1)設(shè)原始點云有n個點,需要采樣出k個點,使用集合A代表采樣點,集合B代表剩余點。初始情況下,集合A為空,集合B包括所有點。

(2)從原始數(shù)據(jù)中隨機選取一個點P0作為起始點,將P0移入集合A,計算P0與剩余(n-1)個點的距離,選擇距離最大的點移入集合A,此時集合A中有2個點,集合B有(n-2)個點。

(3)假設(shè)PB是集合B中的一個點,分別計算出PB到集合A中兩個點的距離值,選擇最小的距離值作為PB到集合A的距離;對于集合B中的所有點計算出到集合A的距離值,選擇最大的距離對應(yīng)的點作為第3個點,移動到集合A中。

(4)重復(fù)第(3)步,直到選出k個點為止。

傳統(tǒng)的最遠點采樣中如果隨機選擇初始點,則每次采樣結(jié)果都不同,本文中先將邊緣點和特征點合并,計算其重心點,在去除邊緣點和特征點后的點云中選擇距離重心點最遠的一點作為初始點進行最遠點采樣。

將邊緣點、特征點和改進的最遠點采樣得到的三類點云合并,但是邊緣點和特征點可能會存在重復(fù),此時利用原始點云的平均距離作為閾值來刪除合并結(jié)果中距離過近的點,即得到最終的精簡點云。

1.4 評價指標

本文采用精簡率、豪斯多夫距離和幾何失真指數(shù)三個指標來評價本文的精簡算法,具體定義如下:

(1)精簡率

點云精簡率的定義如下式:

(5)

(2)豪斯多夫距離

豪斯多夫距離(Hausdorff Distance,HD)是衡量兩個點集之間距離的公式,給定歐氏空間兩個點集A={p1,p2,…,pn}和B={q1,q2,…,qn},點集A,B的HD距離定義如下:

HD(A,B)=max(h(A,B),h(B,A))

(6)

(7)

(8)

當點集A是點集B的子集時,h(A,B)=0,HD(A,B)=h(B,A),HD越小,說明精簡后點云分布越均勻,理論上反映出精簡后點云與原始點云更相似[17]。

(3)幾何失真指數(shù)

在二維圖像壓縮中,峰值信噪比(Peaksignal-to-noise ratio,PSNR)反映了壓縮后圖片質(zhì)量,其定義如下:

(9)

(10)

式中,I,K為大小為H×W的單色圖像,其中I是未壓縮的原始圖像,K是壓縮后的圖像,如果PSNR越大,說明壓縮后圖像的失真程度越小,如果是無損壓縮,PSNR的值應(yīng)該是無窮大。

同理,將類似定義引入到評價三維點云精簡,定義幾何失真指數(shù)(Geometric distortion index,GDI)作為點云精簡評價指標,公式如下:

(11)

其中,p為信號峰值,代表誤差的最大值。根據(jù)點云的數(shù)據(jù)類型設(shè)置為 1 023,在三維點云精簡中,若GDI的值越大,代表失真越少,說明精簡算法對原點云的描述能力越強。

2 實驗與分析

為了驗證本文點云精簡方法的有效性,本文采取兩組數(shù)據(jù)進行實驗,第一組數(shù)據(jù)為測試數(shù)據(jù),為斯坦福的兔子bunny數(shù)據(jù)集,第二組數(shù)據(jù)為實采數(shù)據(jù),使用FARO的掃描儀獲得武漢大學(xué)南門的石獅子點云數(shù)據(jù)。分別采用隨機采樣法、均勻采樣法、法線空間采樣法和本文方法對點云數(shù)據(jù)進行精簡,進行結(jié)果效果分析。

2.1 測試數(shù)據(jù)實驗分析

考慮到在邊緣點提取過程中,閾值θ的選擇對邊緣點的數(shù)目和提取效果影響很大,因此本文為了確定最適合兔子點云的閾值,將閾值θ設(shè)置為0.1π～π之間,步距設(shè)為0.01π,提取出的邊緣點數(shù)與閾值θ的關(guān)系如圖3所示,圖4是不同閾值提取出的邊緣點結(jié)果。

圖3 閾值θ與提取到的邊緣點數(shù)目關(guān)系

圖4 設(shè)置不同閾值邊緣點提取效果

由圖3和圖4可以看出,隨著閾值θ的增大,邊緣點的數(shù)目在逐漸減小,但是在Π/2后隨著閾值的增大,邊緣點提取會出現(xiàn)比較多的缺失,邊緣點數(shù)目減少的速度也明顯減慢,因此在提取兔子點云邊緣時,將閾值θ設(shè)置為Π/2。

在提取出點云的邊緣點后,進行點云特征點提取,圖5給出了ISS3D、SIFT3D,Harris3D、NARF四種特征點提取的結(jié)果,其中紅色點為ISS3D,藍色點為SIFT3D,綠色點為Harris3D,白色點為NARF。

圖5 四種方法提取特征點結(jié)果

由圖5可以看出:ISS3D提取到的特征點數(shù)目最多且分布均勻,兔子的嘴巴、腹部和尾巴處都存在特征點;NARF需要先將點云轉(zhuǎn)換為深度圖像,要求關(guān)鍵點的位置穩(wěn)定且在不同的視角可以被重復(fù)探測,對點云的要求較高且提取速度最慢,其提取出的特征點主要集中在兔子的脖子區(qū)域,分布不均勻且數(shù)量少;Harris3D算法是從二維的角點提取算法擴展到三維點云,其利用點云的表面法向量信息檢測特征點,領(lǐng)域半徑r控制特征點的數(shù)目,r越小,對噪聲越敏感,提取的角點越尖銳,r越大,會導(dǎo)致在平緩區(qū)域也檢測出角點,本文采用點云的平均距離來控制r,減少人為設(shè)定r對檢測結(jié)果的影響;SIFT3D方法在點云存在旋轉(zhuǎn)、平移、縮放的情況下具有良好的穩(wěn)健性,提取出的特征點分布在點云的內(nèi)部特征區(qū)域和點云邊緣。四種方法提取出的特征點的重復(fù)度均低于10%,其中SIFT3D和NARF方法重復(fù)點最多,僅為24個點,僅占NARF特征點的7%。為了提高特征點提取的速度和均勻性,本文采用ISS3D和SIFT3D提取特征點。

經(jīng)過上面實驗分析后,采用Π/2作為邊緣點提取的閾值,采用SIFT3D和ISS3D提取特征點,并通過點云增補和刪除后,所得到的點云結(jié)果(本文方法)和另外3種方法的精簡結(jié)果,采用三種精簡指標,進行比較分析,其結(jié)果如表1所示,精簡后的效果如圖6所示。

表1 兔子點云不同方法精簡結(jié)果的評價指標統(tǒng)計

圖6 兔子點云精簡后的效果圖

由圖6可以看出:均勻采樣得到的點云比較規(guī)則,在特征區(qū)域和平坦區(qū)域的采樣點數(shù)相同,保留圖5四種方法提取特征點結(jié)果細節(jié)特征的能力不如本文方法;隨機采樣法不考慮點云的特征值和曲率,細節(jié)特征損失較大,可能剔除點云的關(guān)鍵數(shù)據(jù);法線空間采樣法雖然能保留點云內(nèi)部的特征,但點云邊界特征損失較大,在點云平坦區(qū)域可能存在空洞;而本文方法可以很好地保存邊緣點云和內(nèi)部特征點,在平坦區(qū)域的點云也比較均勻,能夠在相同的精簡率下最大化地保留點云的特征和細節(jié),與其他3種方法相比,本文方法精簡結(jié)果的HD和GDI也是最優(yōu)的,說明本文方法可以很好地描述原始點云。

2.2 實采數(shù)據(jù)實驗分析

對使用FARO的掃描儀獲得武漢大學(xué)南門的石獅子點云,使用本文方法和其他3種方法對點云進行精簡,采集到的原始點云包括 294 726個數(shù)據(jù)點,由于只采用了單站掃描數(shù)據(jù),獅子頭部存在掃描盲區(qū)導(dǎo)致出現(xiàn)空洞,后續(xù)可以采用三角網(wǎng)格化方法或徑向基函數(shù)法或GA-BP神經(jīng)網(wǎng)絡(luò)方法進行空洞修補。其精簡結(jié)果如圖7所示,采用三種精簡指標,進行比較分析,其結(jié)果如表2所示。

表2 獅子點云不同方法精簡結(jié)果的評價指標統(tǒng)計

圖7 獅子點云精簡后效果圖

由圖7可以看出:隨機采樣法和法線空間采樣法的精簡結(jié)果整體比較雜亂,在獅子墩部位存在點云空洞;均勻采樣法的精簡結(jié)果邊界區(qū)域比較雜亂,特征區(qū)域和平坦區(qū)域的采樣數(shù)一致,不能反映出點云的細節(jié)特征;本文方法的精簡結(jié)果點云邊界清晰,點云平坦區(qū)域沒有空洞,還保留了點云的細節(jié)特征。由表2可知,本文方法得到的精簡點云的HD和GDI均為最優(yōu),說明本文方法對大規(guī)模點云精簡后的結(jié)果仍能很好地表達點云的整體特征。

3 結(jié) 論

本文針對獲得的點云原始數(shù)據(jù)龐大和大量冗余的問題,提出了一種結(jié)合邊緣點提取和特征點提取的點云精簡方法,通過精簡率、豪斯多夫距離和幾何失真指數(shù)三個指標來評價本文的精簡方法。實驗結(jié)果表明,本文方法得到的精簡結(jié)果失真程度更小,既保留了點云的細節(jié)特征,又減少了點云平坦區(qū)域的空洞,對大規(guī)模點云也有很好的適用性。