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

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

(1.武漢大學測繪學院,湖北 武漢 430079; 2.武漢大學災害監測與防治研究中心,湖北 武漢 430079)

0 引 言

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

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

1 基本原理

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

圖1 本文方法流程圖

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

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

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

(1)

(2)

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

(3)

(4)

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

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

1.2 特征點提取

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

(1)ISS3D算法

(2)SIFT3D特征點

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

1.3 點云增補與刪除

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

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

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

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

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

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

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

1.4 評價指標

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

(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)幾何失真指數

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

(9)

(10)

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

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

(11)

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

2 實驗與分析

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

2.1 測試數據實驗分析

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

圖3 閾值θ與提取到的邊緣點數目關系

圖4 設置不同閾值邊緣點提取效果

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

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

圖5 四種方法提取特征點結果

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

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

表1 兔子點云不同方法精簡結果的評價指標統計

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

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

2.2 實采數據實驗分析

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

表2 獅子點云不同方法精簡結果的評價指標統計

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

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

3 結 論

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