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

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

1 引 言

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

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

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

2 原理與方法

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

圖1 原始的點(diǎn)云

2.1 特征空間

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

圖2 空間投影

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

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

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

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

2.2 最小二乘密度聚類算法

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

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

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

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

第5步：由密度空間的離散情況,截?cái)嚅撝颠x擇保留2倍中誤差的有效數(shù)據(jù)作為所需的研究對(duì)象,其中2δ=95.44 %;

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

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

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

圖3 鄰域10個(gè)點(diǎn)的特征密度分布

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

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

圖4 鄰域40個(gè)點(diǎn)的特征密度分布

圖5 提取效果

本文算法實(shí)驗(yàn)結(jié)果如圖5所示,選擇A/B/C/D四處被認(rèn)定為噪聲點(diǎn)云的區(qū)域,如圖可知,A區(qū)域?yàn)殛幱罢趽醯南∈椟c(diǎn)云區(qū)域,由于陰影的影響,其實(shí)物屬性無(wú)法體現(xiàn),被作為噪聲剔除也屬正常；B區(qū)域?yàn)榭罩须x群點(diǎn),該算法能準(zhǔn)確的找出并剔除；C區(qū)域?yàn)楸芾揍?由于其細(xì)而長(zhǎng)的特性,在密度空間中很難被表現(xiàn)出來(lái),這就屬于錯(cuò)誤區(qū)分的點(diǎn)云,但其點(diǎn)云個(gè)數(shù)極少,對(duì)總體精度影響不大；D區(qū)域透過(guò)玻璃隨機(jī)產(chǎn)生的隨機(jī)噪聲點(diǎn),相對(duì)于較為稀疏的主體墻體而言,也能將隨機(jī)噪聲與墻體分離開(kāi),但同時(shí)也有少許邊緣點(diǎn)被錯(cuò)誤區(qū)分,可通過(guò)調(diào)節(jié)截?cái)嚅撝?提高精度。

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

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

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

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

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

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

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

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

4 結(jié) 論

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