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

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

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

0 引 言

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

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

1 基本原理

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

圖1 本文方法流程圖

1.1 基于PCA法矢估計(jì)的點(diǎn)云邊界提取

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

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

(1)

(2)

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

(3)

(4)

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

圖2 邊緣點(diǎn)和非邊緣點(diǎn)示意圖

1.2 特征點(diǎn)提取

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

(1)ISS3D算法

(2)SIFT3D特征點(diǎn)

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

1.3 點(diǎn)云增補(bǔ)與刪除

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

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

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

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

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

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

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

1.4 評價(jià)指標(biāo)

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

(1)精簡率

點(diǎn)云精簡率的定義如下式:

(5)

(2)豪斯多夫距離

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

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

(6)

(7)

(8)

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

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

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

(9)

(10)

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

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

(11)

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

2 實(shí)驗(yàn)與分析

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

2.1 測試數(shù)據(jù)實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

表1 兔子點(diǎn)云不同方法精簡結(jié)果的評價(jià)指標(biāo)統(tǒng)計(jì)

圖6 兔子點(diǎn)云精簡后的效果圖

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

2.2 實(shí)采數(shù)據(jù)實(shí)驗(yàn)分析

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

表2 獅子點(diǎn)云不同方法精簡結(jié)果的評價(jià)指標(biāo)統(tǒng)計(jì)

圖7 獅子點(diǎn)云精簡后效果圖

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

3 結(jié) 論

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