基于最小二乘密度聚類的城市點云去噪算法

楊 鵬,劉德兒,劉靖鈺,鄒紀(jì)偉,張荷苑,陳增輝

(1.江西理工大學(xué)建筑與測繪工程學(xué)院,江西 贛州 341000; 2.成都大學(xué)中國東盟藝術(shù)學(xué)院,四川 成都 610106)

1 引 言

3D點云表達(dá),作為對象表面的表達(dá)方式之一,在對象識別和三維重構(gòu)等領(lǐng)域越發(fā)重要。目前3D點云數(shù)據(jù)獲取主要通過三維激光掃描的方式。受益于三維激光掃描技術(shù)的發(fā)展,3D點云密度越來越密,精度也越來越高。但是實際操作環(huán)境的復(fù)雜性,造成獲取到的點云數(shù)據(jù)中不可避免的存在噪音點和錯誤點。而點云數(shù)據(jù)的質(zhì)量對于最終三維重構(gòu)成果的質(zhì)量的影響十分巨大。因此,去除點云數(shù)據(jù)中的噪音點具有很高的實用和研究價值[1-15]。

目前,在點云去噪方面,已經(jīng)成為近年來的一個研究熱點。同時,國內(nèi)外專家都做出了許多重要的研究成果,出現(xiàn)了一大批優(yōu)秀的理論和算法,蘇本躍等[16]基于K-means聚類對RGBD點云進(jìn)行外部噪聲去噪和精簡,首先計算各點在局部曲面的曲率值,通過K-means對其進(jìn)行聚類,在根據(jù)鄰近點的曲率變化和該點到聚類中心的距離判斷是否為噪聲點,該算法可保留點云的原始特征；張巧英、田青華等[17-18]均運用了聚類算法,但是其算法中的鄰域搜索普遍耗時較長,未凸顯統(tǒng)計特性。馮東恒等[19]提出用共面法向量特征去除離群面的RANSAC算法,與傳統(tǒng)PCL算法相比,該算法去噪效果好且執(zhí)行效率高,但若地表復(fù)雜且包含較多樹木,則影響較大；林萬譽等[20]提出基于最小截取二乘法的分段擬合的濾波算法,在去除點云的同時能較好的保留局部細(xì)節(jié)特征,但僅局限于多曲面三維點云；趙凱等[21]提出的基于體素柵格的快速密度聚類算法,將點云進(jìn)行體素柵格劃分,縮小各個對象在空間上的搜索范圍,再結(jié)合DBSCAN進(jìn)行去噪,大幅度提高了運行效率。李明磊等[22]通過對平均點間距附加權(quán)重再作閾值判斷,降低了對遠(yuǎn)距離離散點的誤判,且通過八叉樹格網(wǎng)結(jié)構(gòu)提高了生長探測法的運行效率；李仁忠等[23]提出的基于方法庫的點云模型去噪與精簡算法,通過結(jié)合PCL中的直通濾波、統(tǒng)計濾波、半徑濾波、雙邊濾波等,可有效對大尺度噪聲點進(jìn)行去除,但在該算法中統(tǒng)計濾波和半徑濾波閾值設(shè)置決定運行效率。林洪彬等[6]提出基于參數(shù)自適應(yīng)各向異性高斯核的散亂點云保特征去噪算法,利用切平面的投影和采樣點構(gòu)建相似度函數(shù),從而確定有效領(lǐng)域,通過研究采用點的特征值和特征向量分布確定參數(shù)自適應(yīng)的高斯核函數(shù),從而完成點云去噪,該算法雖然較好地實現(xiàn)了點云去噪,但仍無法達(dá)到完全自適應(yīng)。許龍等[7]提出了基于模糊C均值和均值濾波的點云去噪算法,首先用C均值去除大尺度噪聲,再結(jié)合均值濾波對小尺度噪聲進(jìn)行光順,該算法在去噪的同時較好地保留了邊界特征。

上述去噪算法能夠在一定程度上解決了目前的工程所需,但是現(xiàn)有的點云去噪算法的復(fù)雜度、自適應(yīng)性、穩(wěn)定性、快速性以及通用性等仍然有待提升,尤其是在一些極其苛刻、復(fù)雜的場景之下,錯分率非常高。例如:林業(yè)園區(qū)、城市街區(qū)以及不規(guī)則、不平整地區(qū)等,對于這些地區(qū)的點云數(shù)據(jù)運用去噪算法,一定需要在某些閾值選取時加以限制。

2 原理與方法

本文基于三維激光掃描儀RIEGL VZ-1000收集的城市點云數(shù)據(jù),該數(shù)據(jù)的角度分辨率為0.0005°,100米的掃描精度為5mm,圖1為2019年4月的部分城市點云數(shù)據(jù),共820025個點,橫縱方向掃描角設(shè)置為0.02°,受掃描角度的限制、陰影遮擋與隨機(jī)誤差的影響,其中存在大量的噪聲和空洞,且噪聲點表現(xiàn)較為雜亂、規(guī)律不明顯,因而對該場景下的噪聲剔除需要更多的考慮內(nèi)在隨機(jī)噪聲特性。通常城市點云的噪聲主要來自于孤立噪聲點、非地面的隨機(jī)噪聲點以及掃描稀疏邊界等。因此,首先,建立近鄰點特征空間；其次,確定噪聲點與實體點的分界線；最后,基于特征空間的特征表達(dá)原則,再結(jié)合特征密度的分布進(jìn)行聚類求交,最終可消除隨機(jī)誤差的影響。

圖1 原始的點云

2.1 特征空間

城市點云本身所具有的復(fù)雜性,增加了噪聲點去除的難度,而去噪精度嚴(yán)重影響后期的實物提取與建模。城市點云噪聲空間的分布規(guī)律具有不穩(wěn)定的變化,運用簡單的密度聚類將無法達(dá)到滿意精度。由于各單獨點沒有空間特征及實體屬性,因此不能以點為對象進(jìn)行密度聚類,而需要對空間描述算子的密度聚類。然而,描述一群空間散亂點所需要的特征算子可以有很多個,因此,用于聚類的特征空間將會被提升到更高維度的空間中。

圖2 空間投影

如圖2所示,不同的三維空間實體,在二維空間中的投影具有很大的差異性,有的是三維空間物體相同或相似的,在二維空間中完全不同,也有的是在二維空間投影相似的,其三維空間中的特性卻完全不同。同理,更高維度空間向二維平面投影時,也會出現(xiàn)這種現(xiàn)象,因此不能單獨在一個維度上對特征算子空間進(jìn)行描述,這樣會使得結(jié)果陷入局部最優(yōu)解,使去噪精度變得不滿足工程所需。

本文首要研究的著重點就是:在點云特征算子中,如何快速有效的解決高維空間密度聚類。經(jīng)驗表明:單一的一個特征值只能算是特征空間在某一特定方向的投影,其在一定程度上表現(xiàn)了原始數(shù)據(jù)的特性,但是這個過程并非一一映射,也會有其他方向的投影與該特征值相同或相似,這也就是點云特征空間聚類出現(xiàn)錯分類的主要決定性原因。在復(fù)雜的點云空間中,每一個點都是獨立的、附有特殊空間意義的存在,從本質(zhì)上講,每一個點都有屬于它自己的特別屬性,而我們要做的就是盡可能的將不同屬性區(qū)分出來。

一個高維空間在低維空間上的投影可以有無數(shù)個,這些投影可以由一個集合表示,每一個投影都是這個集合中的一個元素,理論上投影元素越多精度越高。雖然用投影集合去分辨點云的屬性在數(shù)學(xué)理論上是準(zhǔn)確且可行的,但是在效率上確實無法估計。由于高維度的計算量很大,使得其效率低；低維度的計算量隨少,使得其準(zhǔn)確率低；因此,需要在效率和準(zhǔn)確性之間進(jìn)行平衡。

綜上所述,本文提出一種最小二乘密度聚類去噪算法,旨在從高維特征空間中切分出具有實物屬性的點云。首先,基于KD-Tree搜索各點的k個近鄰點,再計算近鄰點的統(tǒng)計特征；其次,由多個統(tǒng)計特征生成高維度的密度空間,并基于最小二乘解[24]求得密度空間在各維度上的回歸線,并結(jié)合密度分析求得實物與噪聲的分界線；最后,遍歷密度空間,找出噪聲點并剔除。

2.2 最小二乘密度聚類算法

為了從空間特性上描述點云,本文對近鄰點的鄰域特征空間進(jìn)行聚類,由于特征空間維度高于3個維度,可以構(gòu)建高維度信息的聚類,并以任意兩個維度的最小二乘解限制聚類邊界是否超限,因此,本文提出一種基于最小二乘法實現(xiàn)城市點云的最小二乘密度空間聚類方法,并以此為基礎(chǔ)進(jìn)行去噪。

本文算法實現(xiàn)的具體步驟如下:

第1步：確定近鄰點數(shù)N,求得近鄰特征空間,記為PN(x1、x2、x3、x4、x5);

第2步：將均值、方差、斜率、極值、能量進(jìn)行排序,分別記為x1、x2、x3、x4、x5;

第5步：由密度空間的離散情況,截斷閾值選擇保留2倍中誤差的有效數(shù)據(jù)作為所需的研究對象,其中2δ=95.44 %;

第6步：由第5步的標(biāo)準(zhǔn)計算出密度空間各投影方向的截斷閾值ωij,截斷條件為p(Tij≥ωij)=95.44 %,各投影方向的有效數(shù)據(jù)為Dij=Ti(Ti≤ωi),最終將各投影方向的有效數(shù)據(jù)取交集,即為在高維空間中的有效點集Qij=D12∩D13…∩D45。

3 實驗結(jié)果與分析

對特征密度空間進(jìn)行分析,需要充分考慮高維度密度空間的特性,以此分析各投影方向上密度的緊密性,即去噪能力的強弱,分析結(jié)果如下圖3、圖4所示。圖1中的(a)、(b)、(c)、…、(j)依次為各投影面。

圖3 鄰域10個點的特征密度分布

圖3的特征空間所示,去噪前后特征的集聚性對比明顯,去噪之前,受到眾多噪聲的影響,使得密度集聚度散亂,且整體的最小二乘解受噪聲點的影響較大。結(jié)合最小二乘解的密度空間聚類為去噪之后的結(jié)果,盡管有一定的散亂特性,但其縮小了約100倍的密度聚集體中包含了原有的大部分特征信息,即實現(xiàn)了數(shù)據(jù)的特征聚類,并消除了大部分隨機(jī)誤差影響,尤其是在包含能量的投影面上,其擬合度精度最高。然而,這些特征空間密度聚類后的交集包含的就是符合所有特征空間判定的有效點云,對于某些特有屬性的點來說,該結(jié)果的判斷具有一定的不確定性,可以通過調(diào)節(jié)層次權(quán)重的方式或者增加特征維度來進(jìn)行判斷。10個近鄰點的密度特征空間能夠反映出絕大部分噪聲點,再結(jié)合密度閾值,即可獲得到有效點云。

如圖4所示,近鄰點為40時,相較于圖3的密度分布,圖4的特征空間壓縮了近80倍,其噪聲點離散性增強,方差增強,從噪聲的剔除上看,效果優(yōu)于10個近鄰點時的效果。雖然40個近鄰點在特征空間中突出了噪聲點,增加了離散度,但其特征空間范圍也被快速增大了,這有可能將有效地面點也剔除了。

圖4 鄰域40個點的特征密度分布

圖5 提取效果

本文算法實驗結(jié)果如圖5所示,選擇A/B/C/D四處被認(rèn)定為噪聲點云的區(qū)域,如圖可知,A區(qū)域為陰影遮擋的稀疏點云區(qū)域,由于陰影的影響,其實物屬性無法體現(xiàn),被作為噪聲剔除也屬正常；B區(qū)域為空中離群點,該算法能準(zhǔn)確的找出并剔除；C區(qū)域為避雷針,由于其細(xì)而長的特性,在密度空間中很難被表現(xiàn)出來,這就屬于錯誤區(qū)分的點云,但其點云個數(shù)極少,對總體精度影響不大；D區(qū)域透過玻璃隨機(jī)產(chǎn)生的隨機(jī)噪聲點,相對于較為稀疏的主體墻體而言,也能將隨機(jī)噪聲與墻體分離開,但同時也有少許邊緣點被錯誤區(qū)分,可通過調(diào)節(jié)截斷閾值,提高精度。

同時為了能定性、定量分析本文算法,選用不同鄰域點進(jìn)行實驗,得到結(jié)果如表1所示。帶有均值及斜率的投影特征密度其密度空間的一階偏導(dǎo)Cij均有所提升,帶有能量、極差和方差的投影特征密度空間,其一階偏導(dǎo)Cij隨著近鄰點個數(shù)的增加均有所下降。

如表2所示,在不同的鄰域點時,其中(1)、(3)、(4)、(6)、(7)的特征空間,其提取效果較差,只能去掉1000～3000個隨機(jī)噪聲點；(2)、(5)、(8)、(9)的特征空間,隨著鄰域點的增加,其去噪能力也在增強；(11)為特征空間的最終去噪結(jié)果,其隨著近鄰點的增加,噪聲點剔除個數(shù)也在增加,且總體趨勢與實際理論相符。

表1 不同近鄰點的投影特征最小二乘約束條件

表2 不同近鄰點在各投影面上去噪后的點個數(shù)

采用第一類錯分誤差、第二類錯分誤差以及總錯分誤差驗證算法的有效性,其中總錯分誤差是將有效點錯誤分為噪聲點的數(shù)量和將噪聲點錯誤分為有效點的數(shù)量之和占總和點云的比例,公式為:

式中,a為有效點數(shù)量；b為噪聲點數(shù)量；c為將有效地面點錯誤分為噪聲點的數(shù)量；d為將噪聲點錯誤分為有效地面點的數(shù)量。

由表3可知,選擇的近鄰點數(shù)不同時,其噪聲的剔除能力不同,均方差和分類誤差均有所變動,同時,在選擇近鄰點個數(shù)為30時,雖然其均方差較大,但其分類誤差最小,總的錯分率t為0.000574,滿足工程所需精度。

表3 不同鄰域點個數(shù)下的提取結(jié)果及精度

4 結(jié) 論

本文提出了一種基于最小二乘密度聚類的城市點云去噪算法,計算近鄰點統(tǒng)計特征空間,運用最小二乘約束特征空間在各維度方向的投影密度,以此進(jìn)行密度聚類、剔除噪聲點云。以VZ-1000地面三維激光掃描儀獲取的城市點云數(shù)據(jù),分析復(fù)雜環(huán)境下的城市點云空間結(jié)構(gòu)與鄰域特性,結(jié)果表明當(dāng)近鄰點個數(shù)為30時,該算法總分類誤差最小。同時,實驗也體現(xiàn)出本算法的優(yōu)勢:理論便于實現(xiàn),且能快速、精確地去除噪聲點云,具有一定的實用價值；但仍有不足之處,主要為稀疏點云的邊緣、障礙物的陰影處以及低密度的線性地物等點云,這些是極容易造成錯誤分類的點,因此未來需要更深入地進(jìn)行研究。