層次化點(diǎn)云去噪算法

趙夫群，周明全

(1.西安財(cái)經(jīng)大學(xué) 信息學(xué)院，陜西 西安 710010；2.西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院，陜西 西安 710127)

1 引 言

三維激光掃描技術(shù)是獲取物體空間點(diǎn)云數(shù)據(jù)信息的重要手段之一，并在多種領(lǐng)域發(fā)揮著重要的作用[1-4]。但是受儀器測量誤差、物體反射、遮擋、光照以及環(huán)境變化等因素的影響，掃描獲取的初始點(diǎn)云數(shù)據(jù)模型中往往含有大量的噪聲點(diǎn)。這些噪聲點(diǎn)的數(shù)量越多，密度越大，對點(diǎn)云質(zhì)量的影響也就越大，因此需要采取合適的去噪算法將其加以刪除。

近年來，國內(nèi)外學(xué)者對點(diǎn)云去噪算法進(jìn)行了較為深入地研究。Polat N等[5]提出一種LiDAR數(shù)據(jù)去噪算法，該算法性能可以根據(jù)地區(qū)地形特征的變化而變化，可以有效濾除非地面點(diǎn)，是一種有效的點(diǎn)云去噪算法；徐少平等[6]提出一種基于卷積神經(jīng)網(wǎng)絡(luò)的去噪算法，該算法首先通過訓(xùn)練卷積神經(jīng)網(wǎng)絡(luò)模型構(gòu)成NLAF特征矢量，然后利用增強(qiáng)的BP(Back Propagation)神經(jīng)網(wǎng)絡(luò)預(yù)測模型將NLAF特征矢量映射為噪聲水平值，最后以估計(jì)值的中值作為噪聲水平值的最終估計(jì)結(jié)果，該去噪算法具有較高的準(zhǔn)確性和執(zhí)行效率；Xu Z等[7]提出一種基于局部坐標(biāo)系下多個(gè)各向異性估計(jì)的點(diǎn)云去噪算法，該估計(jì)對點(diǎn)云表面的形狀保持具有自適應(yīng)性，既可保持點(diǎn)云尖銳的特征點(diǎn)，也可以保留點(diǎn)云中的光滑區(qū)域；趙凱等[8]提出一種基于柵格劃分的點(diǎn)云離群噪聲點(diǎn)去除算法，該算法通過對點(diǎn)云進(jìn)行體素柵格劃分降低了點(diǎn)在鄰域中的搜索范圍，有效分離了目標(biāo)點(diǎn)云和離群點(diǎn)，加快了點(diǎn)云處理的效率。

為了在去噪同時(shí)有效保持點(diǎn)云的幾何特征信息，進(jìn)一步提高點(diǎn)云去噪的精度和速度，本文提出一種層次化的點(diǎn)云去噪算法。首先計(jì)算點(diǎn)云中的點(diǎn)及其鄰域點(diǎn)的張量投票矩陣，并計(jì)算該矩陣的特征值和特征向量；然后利用各向異性濾波方程對點(diǎn)云進(jìn)行光順處理，實(shí)現(xiàn)點(diǎn)云初始去噪；最后計(jì)算點(diǎn)云的曲率特征，根據(jù)曲率值進(jìn)一步刪除點(diǎn)云中的噪聲點(diǎn)，并通過計(jì)算點(diǎn)云熵值對算法定量評價(jià)。

2 基于張量投票的初始去噪

點(diǎn)云P={pi}(i=1，2，…，NP，NP表為點(diǎn)云P中點(diǎn)的數(shù)目)上任意一點(diǎn)pi都可以表示為一個(gè)3×3的對稱半正定矩陣。假設(shè)Nk(pi)為點(diǎn)pi的k個(gè)鄰域點(diǎn)集，那么點(diǎn)pi及其鄰域點(diǎn)集Nk(pi)的張量投票矩陣T為[9]：

(1)

本文通過建立張量矩陣T和點(diǎn)云中點(diǎn)的幾何特征的關(guān)系來實(shí)現(xiàn)點(diǎn)云初始粗去噪。 假設(shè)λ1，λ2，λ3表示張量矩陣T的三個(gè)特征值，并且滿足λ1≥λ2≥λ3，e1，e2，e3表示三個(gè)特征值λ1，λ2，λ3對應(yīng)的特征向量。那么，由點(diǎn)的幾何特征與張量投票矩陣特征值的分布的關(guān)系可知：當(dāng)λ1≥λ2≈λ3≈0時(shí)，點(diǎn)pi為點(diǎn)云中的點(diǎn)；當(dāng)λ1≈λ2≥λ3≈0時(shí)，點(diǎn)pi為點(diǎn)云邊界上的點(diǎn)；當(dāng)λ1≈λ2≈λ3≥0時(shí)，點(diǎn)為點(diǎn)云上的角點(diǎn)或孤立點(diǎn)。

基于張量投票和點(diǎn)的幾何特征的關(guān)系，該點(diǎn)云初始粗去噪算法的基本步驟描述如下：

Step 1：對于噪聲點(diǎn)云P={pi}，首先利用KD tree算法搜索點(diǎn)pi的k個(gè)最近鄰域點(diǎn)集Nk(pi)；

Step 2：利用式(1)計(jì)算點(diǎn)pi及其鄰域點(diǎn)集Nk(pi) 的張量投票矩陣T，并求解T的特征值λ1，λ2，λ3和特征向量e1，e2，e3；

Step 3：根據(jù)λ1，λ2，λ3和e1，e2，e3構(gòu)造擴(kuò)散張量矩陣D，D定義為：

(2)

式中Dij(1≤i，j≤3)定義為：

(3)

式中參數(shù)μ1，μ2，μ3分別定義為：

μ1=α，

(4)

(5)

(6)

Step 4：基于擴(kuò)散張量D，利用各向異性擴(kuò)散方程[10]對點(diǎn)云進(jìn)行循環(huán)濾波去噪，直到濾波次數(shù)的值大于給定閾值時(shí)為止。各向異性濾波方程的定義式為：

(7)

式中：Jp是點(diǎn)云的結(jié)構(gòu)張量，其表示點(diǎn)云的局部信息特征；D是擴(kuò)散張量，其特征值代表點(diǎn)云在三個(gè)主特征方向上的擴(kuò)散速率，I0(x，y，z)是初始輸入的點(diǎn)云數(shù)據(jù)。

從上述基于張量投票的點(diǎn)云去噪算法可見，結(jié)構(gòu)張量可以保留點(diǎn)云的局部信息特征，尤其是點(diǎn)云的尖銳幾何特征，有效剔除點(diǎn)云中的大尺度噪聲(距離主體點(diǎn)云較遠(yuǎn)的噪聲)和部分混雜在主體點(diǎn)云中的小尺度噪聲，從而實(shí)現(xiàn)點(diǎn)云的初始粗去噪。接下來采用基于曲率特征的去噪算法進(jìn)一步去除混在主體點(diǎn)云中的其余的噪聲。

3 基于曲率特征的精確去噪

在對點(diǎn)云進(jìn)行進(jìn)一步精確去噪時(shí)，主要是去除點(diǎn)云主體中混雜的小尺度噪聲，本文通過提取曲率幾何特征來實(shí)現(xiàn)點(diǎn)云小尺度噪聲的精確去噪。點(diǎn)云的曲率能夠較好地反映點(diǎn)云的表面特征，它可以通過在離散點(diǎn)集拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上進(jìn)行曲面擬合計(jì)算得到。本文通過搜索點(diǎn)云中各離散點(diǎn)的k鄰域點(diǎn)來建立點(diǎn)云的拓?fù)浣Y(jié)構(gòu)，可以有效提高空間分布不均勻的海量離散點(diǎn)集的空間搜索效率。

3.1 計(jì)算曲率

BY=D，

(8)

(9)

式中h是一個(gè)距離常數(shù)。

建立如式(10)所示的約束準(zhǔn)則，即：

(10)

由式(10)約束準(zhǔn)則可得：

BTQBY=0，

(11)

(12)

3.2 精確去噪算法

由于點(diǎn)云表面不同點(diǎn)的曲率各不相同，結(jié)合以上點(diǎn)云中點(diǎn)的曲率和法向量計(jì)算方法，基于曲率特征的點(diǎn)云精確去噪步驟具體描述如下：

Step 3：判斷每點(diǎn)曲率，若大于給定閾值ε，則判斷該點(diǎn)為噪聲點(diǎn)，將其刪除。

通過上述步驟即可實(shí)現(xiàn)點(diǎn)云噪聲的最終精確刪除。

目前已有點(diǎn)云去噪算法大多缺少對去噪結(jié)果的定量評價(jià)，為了描述去噪算法對點(diǎn)云特征的保持程度，本文采用信息熵理論[13]對點(diǎn)云去噪結(jié)果進(jìn)行定量評價(jià)。信息熵理論可以描述去噪后點(diǎn)云的特征信息，點(diǎn)云中某點(diǎn)的熵值越大，表明該點(diǎn)的信息量越大，細(xì)節(jié)表現(xiàn)越精確。

定義點(diǎn)云中某點(diǎn)的信息熵Hi為：

(13)

那么，點(diǎn)云P′的熵H為：

(14)

通常，點(diǎn)云熵值H越大，其所包含的特征信息量就越大，對點(diǎn)云的細(xì)節(jié)表現(xiàn)就越精確。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 公共點(diǎn)云去噪

在公共點(diǎn)云數(shù)據(jù)去噪實(shí)驗(yàn)中，采用網(wǎng)絡(luò)上公開的Bunny和Dragon點(diǎn)云數(shù)據(jù)模型，通過對其進(jìn)行加噪來驗(yàn)證本文去噪算法，加噪的公共點(diǎn)云模型如圖1所示。對于圖1的公共點(diǎn)云噪聲模型，采用本文提出的層次化點(diǎn)云去噪算法進(jìn)行去噪，首先采用基于張量投票的去噪算法進(jìn)行初始粗去噪，粗去噪結(jié)果如圖2所示；然后采用基于曲率的去噪算法進(jìn)行精確去噪，最終去噪結(jié)果如圖3 所示。實(shí)驗(yàn)中，參數(shù)k的值取16，具體取值跟點(diǎn)云類型和密度等有一定的關(guān)系，密度越大，取值越小，通常建議取值在8～28之間。

(a)加噪Bunny(a)Noisy Bunny

(b)加噪Dragon(b)Noisy Dragon圖1 待去噪公共點(diǎn)云模型Fig.1 Common point cloud model to be denoised

(a)Bunny去噪結(jié)果(a)Bunny denoising result

(b)Dragon去噪結(jié)果(b)Dragon denoising result圖2 本文算法對公共點(diǎn)云的粗去噪結(jié)果Fig.2 Coarse denoising results of public point clouds with proposed algorithm

(a)Bunny去噪結(jié)果(a)Bunny denoising result

(b)Dragon去噪結(jié)果(b)Dragon denoising result圖3 本文算法對公共點(diǎn)云的精確去噪結(jié)果Fig.3 Fine denoising results of public point clouds with proposed algorithm

從圖2和圖3的去噪結(jié)果可見，基于張量投票的去噪算法可以有效剔除公共點(diǎn)云中的大尺度噪聲和部分小尺度噪聲，實(shí)現(xiàn)點(diǎn)云的初始粗去噪。而基于曲率的去噪算法可以對點(diǎn)云中的小尺度噪聲進(jìn)行進(jìn)一步地精確提出。同時(shí)，本文算法可以較好地保留公共點(diǎn)云模型的原始幾何特征，是一種有效的點(diǎn)云去噪算法。

為了進(jìn)一步驗(yàn)證本文去噪算法的性能，對圖1的公共點(diǎn)云噪聲模型再分別采用文獻(xiàn)[14]、文獻(xiàn)[15]和文獻(xiàn)[7]的算法進(jìn)行去噪，去噪結(jié)果分別如圖4、圖5、圖6和表1所示。

(a)Bunny去噪結(jié)果(a)Bunny denoising result

(b)Dragon去噪結(jié)果(b)Dragon denoising result圖4 文獻(xiàn)[14]算法對公共點(diǎn)云的去噪結(jié)果Fig.4 Denoising results of public point clouds with reference [14] algorithm

(a)Bunny去噪結(jié)果(a)Bunny denoising result

(b)Dragon去噪結(jié)果(b)Dragon denoising result圖5 文獻(xiàn)[15] 算法對公共點(diǎn)云的去噪結(jié)果Fig.5 Denoising results of public point clouds with reference [15] algorithm

(a)Bunny去噪結(jié)果(a)Bunny denoising result

(b)Dragon去噪結(jié)果(b)Dragon denoising result圖6 文獻(xiàn)[7]算法對公共點(diǎn)云的去噪結(jié)果Fig.6 Denoising results of public point clouds with reference [7] algorithm

從圖3、圖4、圖5和圖6的去噪結(jié)果可見，本文算法在對點(diǎn)云數(shù)據(jù)去噪的同時(shí)能夠更好地保留原始細(xì)節(jié)特征，算法具有更高的可行性。從表1算法的運(yùn)行參數(shù)可見，本文算法的誤差最小，耗時(shí)最短，而且熵值較文獻(xiàn)[14]算法、文獻(xiàn)[15]算法和文獻(xiàn)[7]算法都要大，因此本文算法是一種更加精確快速的點(diǎn)云模型去噪算法。

表1 不同算法對公共點(diǎn)云的去噪結(jié)果Tab.1 Denoising results of different algorithms forpublic point clouds

4.2 文物點(diǎn)云去噪

在文物點(diǎn)云模型的去噪實(shí)驗(yàn)中，采用了5個(gè)含噪聲的陶質(zhì)文物碎塊的點(diǎn)云數(shù)據(jù)模型來驗(yàn)證本文算法，如圖7所示。利用本文提出的層次化點(diǎn)云去噪算法，首先采用基于張量投票的去噪算法對文物碎塊的點(diǎn)云模型進(jìn)行初始粗去噪，粗去噪結(jié)果如圖8所示；然后基于粗去噪的結(jié)果，采用基于曲率的去噪算法進(jìn)行精確去噪，最終去噪結(jié)果如圖9所示。實(shí)驗(yàn)中，參數(shù)k的值取16。

從圖8和圖9的去噪結(jié)果可見，基于張量投票的去噪算法可以有效剔除公共點(diǎn)云中的大尺度噪聲和部分小尺度噪聲，實(shí)現(xiàn)點(diǎn)云的初始粗去噪。而基于曲率的去噪算法可以對點(diǎn)云中的小尺度噪聲進(jìn)行進(jìn)一步的精確提出。同時(shí)，本文去噪算法在對文物點(diǎn)云數(shù)據(jù)模型去噪的同時(shí)，能夠較好地保留模型的原始幾何特征信息，是一種有效的文物點(diǎn)云模型去噪算法。

為了進(jìn)一步驗(yàn)證本文去噪算法的性能，對圖7 所示的文物碎塊點(diǎn)云模型再分別采用文獻(xiàn)[14]算法、文獻(xiàn)[15]算法和文獻(xiàn)[7]算法分別進(jìn)行去噪處理，其去噪結(jié)果分別如圖10、圖11、圖12和表2所示。

(a)碎塊1(a)Fragment 1

(b)碎塊2(b)Fragment 2

(c)碎塊3(c)Fragment 3

(d)碎塊4(d)Fragment 4

(e)碎塊5(e)Fragment 5

(a)碎塊1(a)Fragment 1

(b)碎塊2(b)Fragment 2

(c)碎塊3(c)Fragment 3

(d)碎塊4(d)Fragment 4

(e)碎塊5(e)Fragment 5圖8 本文算法對文物點(diǎn)云的初始去噪結(jié)果Fig.8 Initial denoising results of cultural relics point clouds with the proposed algorithm

(a)碎塊1(a)Fragment 1

(b)碎塊2(b)Fragment 2

(c)碎塊3(c)Fragment 3

(d)碎塊4(d)Fragment 4

(e)碎塊5(e)Fragment 5圖9 本文算法對文物點(diǎn)云的精確去噪結(jié)果Fig.9 Accurate denoising results of cultural relics point clouds with the proposed algorithm

(a)碎塊1(a)Fragment 1

(b)碎塊2(b)Fragment 2

(c)碎塊3(c)Fragment 3

(d)碎塊4(d)Fragment 4

(a)碎塊1(a)Fragment 1

(b)碎塊2(b)Fragment 2

(c)碎塊3(c)Fragment 3

(d)碎塊4(d)Fragment 4

(e)碎塊5(e)Fragment 5圖11 文獻(xiàn)[15]算法對文物點(diǎn)云的去噪結(jié)果Fig.11 Denoising results of cultural relics point clouds with reference [15] algorithm

(a)碎塊1(a)Fragment 1

(b)碎塊2(b)Fragment 2

(c)碎塊3(c)Fragment 3

(d)碎塊4(d)Fragment 4

(e)碎塊5(e)Fragment 5圖12 文獻(xiàn)[7]算法對文物點(diǎn)云的去噪結(jié)果Fig.12 Denoising results of cultural relics point clouds with reference [7] algorithm

表2 不同算法對文物點(diǎn)云的去噪結(jié)果Tab.2 Denoising results of different algorithms for cultural relic point clouds

從圖9、圖10、圖11、圖12的去噪結(jié)果可見，本文算法在對點(diǎn)云數(shù)據(jù)去噪的同時(shí)能夠更好地保留原始細(xì)節(jié)特征，算法具有更高的可行性。從表2的算法運(yùn)行參數(shù)同樣可見，本文算法的去噪平均誤差最低，耗時(shí)最短，而且熵值較文獻(xiàn)[14]算法、文獻(xiàn)[15]算法和文獻(xiàn)[7]算法都要大，包含的特征信息量更大，對點(diǎn)云的細(xì)節(jié)表現(xiàn)更加精確。因此說，本文算法是一種精度高、速度快，且能有效保持點(diǎn)云幾何特征信息的有效點(diǎn)云去噪算法。

5 結(jié) 論

點(diǎn)云去噪是點(diǎn)云預(yù)處理的一個(gè)重要環(huán)節(jié)，有效的點(diǎn)云去噪算法應(yīng)該在去噪的同時(shí)能夠保持原始點(diǎn)云數(shù)據(jù)的幾何特征信息，并且算法具有較低的復(fù)雜度和較高的執(zhí)行效率。本文提出一種層次化的點(diǎn)云去噪算法，首先采用基于張量投票的去噪算法對點(diǎn)云進(jìn)行初始粗去噪，然后采用基于曲率特征的去噪算法對點(diǎn)云進(jìn)行精確去噪，該算法對公共點(diǎn)云和文物點(diǎn)云數(shù)據(jù)模型均具有良好的去噪效果，是一種有效的點(diǎn)云去噪算法。