郭子選，謝曉堯，劉　嵩

(貴州師范大學(xué) 貴州省信息與計(jì)算科學(xué)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽　550001)

?

基于特征恢復(fù)的離群點(diǎn)移除算法的研究

郭子選，謝曉堯*，劉嵩

(貴州師范大學(xué) 貴州省信息與計(jì)算科學(xué)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽550001)

摘要：點(diǎn)云預(yù)處理是點(diǎn)云處理很重要的一個環(huán)節(jié)，在移除稀疏離群點(diǎn)的過程中，點(diǎn)云密度不均會造成有用信息的過度刪除。針對這個問題，提出了一種基于特征恢復(fù)的離群點(diǎn)移除算法。首先使用傳統(tǒng)基于統(tǒng)計(jì)的k鄰域稀疏離群點(diǎn)移除算法移除稀疏離群點(diǎn)，然后針對過度刪除的情況采用RANSAC算法對點(diǎn)云特征進(jìn)行恢復(fù)。實(shí)驗(yàn)結(jié)果表明，經(jīng)過恢復(fù)的點(diǎn)云數(shù)據(jù)，相對于單純依靠傳統(tǒng)離群點(diǎn)移除算法處理后的點(diǎn)云數(shù)據(jù)，過度刪除現(xiàn)象有明顯改善。由此得出，基于特征恢復(fù)的離群點(diǎn)移除算法可以有效刪除稀疏離群點(diǎn)，減小對噪聲閾值的依賴，同時有效抑制了由于密度不均勻?qū)е碌狞c(diǎn)云數(shù)據(jù)的過度刪除。

關(guān)鍵詞：三維激光掃描儀；稀疏離群點(diǎn)；kd-tree算法；k鄰域；隨機(jī)采樣一致性算法

0引言

三維激光掃描儀可以快速獲取高精度的物體表面點(diǎn)云數(shù)據(jù)。獲取的激光點(diǎn)云不僅具有完整的三維空間信息，而且包含豐富的激光反射強(qiáng)度信息[1]。在文物保護(hù)與修復(fù)、建筑物變形檢測、地形監(jiān)測、影視制作等諸多領(lǐng)域均有廣泛的應(yīng)用。三維激光點(diǎn)云需要處理的工作包括: 點(diǎn)云去噪、點(diǎn)云平滑、點(diǎn)云編輯、點(diǎn)云分類、點(diǎn)云著色、目標(biāo)識別、地物表面重構(gòu)、影像與點(diǎn)云配準(zhǔn)、基于影像與點(diǎn)云的單點(diǎn)測量、模型貼紋理等[2]。其中點(diǎn)云去噪是點(diǎn)云預(yù)處理階段不可或缺的一步，稀疏離群點(diǎn)的移除是點(diǎn)云去噪的重要方面，移除效果的優(yōu)劣直接影響點(diǎn)云后續(xù)的分析與建模。

激光掃描儀在對實(shí)體進(jìn)行掃描的時候，由于外界因素干擾以及掃描儀本身誤差，或多或少都會產(chǎn)生離群噪聲點(diǎn)。目前關(guān)于離群噪聲的處理前人們進(jìn)行了很多研究。一種是傳統(tǒng)基于k鄰域的離群點(diǎn)移除算法，這種方法是根據(jù)單個點(diǎn)的k鄰域距離，主要是靠人為經(jīng)驗(yàn)設(shè)置閾值來刪除離群點(diǎn)；第二種是R. B. Rusu, Z. C. Marton等人于2008年提出的基于統(tǒng)計(jì)的離群點(diǎn)刪除算法[3]，這種算法對點(diǎn)云中所有的k鄰域距離進(jìn)行統(tǒng)計(jì)分析，計(jì)算所有點(diǎn)的k鄰域平均距離的標(biāo)準(zhǔn)差，根據(jù)標(biāo)準(zhǔn)差設(shè)定合理閾值，進(jìn)而刪除稀疏離群點(diǎn)；第三種是基于密度的離群點(diǎn)去噪算法，通過計(jì)算離群程度，從而限制噪聲并剔除離群點(diǎn)[4]，這種算法對于緊挨邊界的離群點(diǎn)移除算法效果較好。第四種方法是朱俊峰等人提出的多尺度點(diǎn)云噪聲監(jiān)測的密度分析法[5]，對孤立噪聲和簇狀噪聲都有較為效。

以上研究均對稀疏離群點(diǎn)的移除算法的發(fā)展起到了推動作用，但是對于密度分布不均的情況，均未找到較好的方法解決。研究采用目前廣泛在點(diǎn)云去噪領(lǐng)域使用的基于統(tǒng)計(jì)的稀疏離群點(diǎn)對稀疏離群點(diǎn)移除，之后對移除的離群點(diǎn)進(jìn)行二次處理，獲得有特征的區(qū)域，對處理后的點(diǎn)云進(jìn)行恢復(fù)，減小點(diǎn)云過度刪除對后續(xù)處理帶來的不利影響。

1稀疏離群點(diǎn)

在掃描海龍囤石質(zhì)建筑時，由于關(guān)口年代久遠(yuǎn)，石質(zhì)建筑已經(jīng)風(fēng)化，石頭與石頭之間存在較多的不規(guī)則縫隙，在縫隙之間會由稀疏的離群點(diǎn)噪聲組成一條條的拖影。由于掃描角度、遮擋、掃描表面反射材質(zhì)的不同，造成采集的點(diǎn)云密度總是不均勻的。因此拖影和掃描實(shí)體表面低密度區(qū)域的點(diǎn)云均呈現(xiàn)稀疏的狀態(tài)。

通過觀察點(diǎn)云，發(fā)現(xiàn)掃描得到的海龍囤點(diǎn)云數(shù)據(jù)中，拖影部分點(diǎn)云分布在墻體裂縫的后方，這些拖影點(diǎn)明顯偏離了墻體表面，與掃描實(shí)體明顯呈現(xiàn)不一致的狀態(tài)。根據(jù)Hawkins的定義“一個離群點(diǎn)是一個觀察點(diǎn),它偏離其它觀察點(diǎn)如此之大以至于引起懷疑是由不同機(jī)制生成的”[6]。因此這部分點(diǎn)云屬于稀疏的離群點(diǎn)。這些點(diǎn)的存在不利于后期的點(diǎn)云處理和建模。而掃描實(shí)體表面的稀疏點(diǎn)云大部分是含有有用信息的稀疏點(diǎn)，不能刪除。

這種稀疏離群點(diǎn)產(chǎn)生的原因是多方面的。首先，當(dāng)激光照射到鏡面和較濕的的表面時，會使激光掃描儀發(fā)射出去的激光經(jīng)過一次或多次反射才被激光掃描儀接收到，由于激光反射時間的延長，會使點(diǎn)偏離物體的表面。其次，當(dāng)激光打到物體邊緣時，激光掃描儀的點(diǎn)會沿著物體表面的邊緣延伸出去，形成一個拖尾，這種現(xiàn)象在使用相位式掃描儀掃描時會更加明顯[7]。最后，激光掃描儀的精度以及穩(wěn)定性會隨著反射物表面的材質(zhì)與粗糙度、空氣濕度、儀器內(nèi)部時間計(jì)器以及反射強(qiáng)度等的不同而受到不同程度的影響[8]。因海龍囤墻體處于野外，周圍環(huán)境復(fù)雜多變，墻體易受周圍環(huán)境的影響，而且墻面粗糙程度以及濕度不均勻，再加上裂縫較多，造成了這種現(xiàn)象在海龍囤石質(zhì)建筑掃描的過程中是不可避免的。圖1為海龍囤飛鳳關(guān)墻面照片與點(diǎn)云俯視圖，可以很明顯的看出墻面后方有一段很長的拖尾。

圖1　飛鳳關(guān)墻面照片與點(diǎn)云俯視圖Fig.1　Photo of Feifeng and the top-view of its point cloud

2基于特征恢復(fù)的離群點(diǎn)移除算法實(shí)現(xiàn)

2.1算法實(shí)現(xiàn)流程

算法實(shí)現(xiàn)的流程如圖2所示：

圖2　算法流程Fig.2　Algorithm flow

該算法主要分為兩個部分，第一個部分是對原始點(diǎn)云進(jìn)行稀疏離群點(diǎn)的刪除；第二部分是針對過濾點(diǎn)云的特征對有信息區(qū)域進(jìn)行恢復(fù)。

2.2基于統(tǒng)計(jì)的離群點(diǎn)移除算法

假設(shè)一個點(diǎn)云文件所包含的點(diǎn)云數(shù)量為m個?；诮y(tǒng)計(jì)的離群點(diǎn)移除算法步驟如下：

步驟1在對點(diǎn)云處理之前，首先需要采用3d kd-tree來對無序點(diǎn)云進(jìn)行組織。kd-tree是計(jì)算機(jī)科學(xué)中使用的一種數(shù)據(jù)結(jié)構(gòu)，用來組織表示k維空間中的點(diǎn)的集合。它是一種帶有其他約束條件的二分查找樹，kd-tree對于區(qū)間和近鄰搜索十分有用[9]。kd-tree是接下來對點(diǎn)云進(jìn)行離群點(diǎn)移除與特征恢復(fù)的基礎(chǔ)，其利用垂直于各個坐標(biāo)軸的平面來逐級劃分區(qū)域。經(jīng)過組織后的點(diǎn)云，每個點(diǎn)都對應(yīng)二叉樹的一個結(jié)點(diǎn)。

步驟2然后計(jì)算每個點(diǎn)的k鄰域平均距離。k鄰域是指距離參考點(diǎn)歐式距離最近的k個點(diǎn)的集合。 由于點(diǎn)云中的每個點(diǎn)都變成了二叉樹中的一個節(jié)點(diǎn)，通過遍歷這棵二叉樹可以很方便的查找點(diǎn)與點(diǎn)之間的歐氏距離以及k鄰域。如公式(1)所示，(x0,y0,z0)為參考點(diǎn)，(xn,yn,zn)為參考點(diǎn)周圍k鄰域中的點(diǎn)。n為k鄰域中的任一點(diǎn)索引，n∈[1,k]。μ為參考點(diǎn)的k鄰域平均距離。

(1)

步驟3通過將每個點(diǎn)的k鄰域平均距離相加再求平均值。如公式(2)所示，m為點(diǎn)云總個數(shù)，μi為當(dāng)前參考點(diǎn)的k鄰域平均距離。計(jì)算所有點(diǎn)的平均k鄰域距離。

(2)

步驟4 計(jì)算所有點(diǎn)的k鄰域距離標(biāo)準(zhǔn)差。如公式(3)所示，σ表示k鄰域距離標(biāo)準(zhǔn)差。

(3)

2.3基于特征對有信息點(diǎn)云進(jìn)行恢復(fù)

在基于統(tǒng)計(jì)的稀疏離群點(diǎn)移除算法的基礎(chǔ)之上，采用RANSAC算法對刪除點(diǎn)云的特征進(jìn)行提取并恢復(fù)。RANSAC算法最早由Fischler和 Bolles于1981年提出，該算法是根據(jù)一組包含異常數(shù)據(jù)的樣本數(shù)據(jù)集計(jì)算出數(shù)據(jù)的模型參數(shù)，從而得到有效樣本[10]。經(jīng)過使用RANSAC算法后的點(diǎn)云，可以為后續(xù)處理提供更為可靠的數(shù)據(jù)基礎(chǔ)。

在點(diǎn)云處理的過程中，RANSAC算法可以提取出點(diǎn)云的平面、球面、圓柱面、錐面等特征信息。對于激光掃描儀掃描得到的無序點(diǎn)云而言，并不是點(diǎn)云所有部分都包含可恢復(fù)的特征信息，RANSAC算法作為移除稀疏離群點(diǎn)之后的輔助手段可以有效抑制有用點(diǎn)云數(shù)據(jù)的過度刪除。

有特征的墻面信息因?yàn)槊芏容^小，超出了正常閾值的范圍，于是被刪除了，致使墻面的信息遭到了破壞。在刪除的離群點(diǎn)中，有特征區(qū)域相對于無特征區(qū)域的點(diǎn)云相對集中，密度相對較大。RANSAC算法是根據(jù)局內(nèi)點(diǎn)數(shù)量的多少來確定擬合平面的，因其可以在密度大的區(qū)域獲得較多的內(nèi)點(diǎn)，于是密度大的區(qū)域就會有更大的概率優(yōu)先擬合。被刪除的特征區(qū)域正好符合以上條件，因此就可以利用RANSAC算法提取特征區(qū)域進(jìn)行恢復(fù)。

以下是RANSAC算法提取平面特征的步驟：

步驟1首先是對平面進(jìn)行建模， 平面方程的一般形式為ax+by+cz+d=0。共有4個參數(shù)。其中(a,b,c)為平面的法向量，d為一個常數(shù)。

步驟2在樣本中選擇一個子集，計(jì)算模型的參數(shù)，從而建立代表這個子集的具體的平面模型。

步驟3設(shè)置其他點(diǎn)到平面模型的距離閾值。點(diǎn)到平面模型的距離小于該閾值即設(shè)為局內(nèi)點(diǎn)，大于該閾值設(shè)為局外點(diǎn)。由于海龍囤石質(zhì)建筑風(fēng)化嚴(yán)重，此處選用了0.1 m作為閾值，如果點(diǎn)云面比較平整，閾值在0.05 m以下較為合適。

步驟4計(jì)算局內(nèi)點(diǎn)與局外點(diǎn)的比值，并與之前計(jì)算結(jié)果對比，如果比值大于之前計(jì)算結(jié)果，則將其保留。

步驟5查看是否超過最大迭代次數(shù)，則返回2重新計(jì)算。迭代次數(shù)計(jì)k由以下公式(4)得到：

1-p=(1-wn)k

(4)

其中p為迭代過程中隨機(jī)選取數(shù)據(jù)集中的點(diǎn)為局內(nèi)點(diǎn)的概率，w表示局內(nèi)點(diǎn)數(shù)據(jù)與數(shù)據(jù)集數(shù)目的比值。wn是所有n個點(diǎn)均為局內(nèi)點(diǎn)的概率，1-wn是n個點(diǎn)中至少有一個點(diǎn)為局外點(diǎn)的概率。由公式(4)可知p越大迭代次數(shù)越高。對上式兩邊取對數(shù)，得到計(jì)算迭代次數(shù)k的公式(5)：

(5)

一般情況下，為了避免迭代次數(shù)過少，導(dǎo)致擬合平面不理想，往往需要在k的基礎(chǔ)上乘以一個系數(shù)，來增加擬合成功的概率。

步驟6將得到的擬合平面與經(jīng)過基于統(tǒng)計(jì)的離群點(diǎn)刪除算法處理后的點(diǎn)云合并，并輸出最終點(diǎn)云。

2.4實(shí)例分析與算法比較

2.4.1實(shí)例分析

掃描數(shù)據(jù)來源于海龍囤飛鳳關(guān)墻面的一部分，實(shí)際照片與點(diǎn)云如圖3所示。

圖3　飛鳳關(guān)墻面Fig.3　Part of the wall of Feifeng

海龍屯石質(zhì)建筑存在較多的稀疏離群點(diǎn)，以此墻面為例，首先運(yùn)用基于統(tǒng)計(jì)的稀疏離群點(diǎn)移除算法對原始數(shù)據(jù)進(jìn)行處理。表1為計(jì)算所得到的關(guān)鍵數(shù)據(jù)。圖4為飛鳳關(guān)墻面點(diǎn)云數(shù)據(jù)使用該算法處理后的點(diǎn)云效果圖。

表1　算法關(guān)鍵參數(shù)

圖4　稀疏離群點(diǎn)移除后點(diǎn)云效果Fig.4　Rusult of removing sparse outliers

由圖4可知，由于墻面數(shù)據(jù)密度不均，導(dǎo)致墻面有用信息被誤刪除，所有刪除的點(diǎn)如圖5所示。

圖5　刪除的點(diǎn)云Fig.5　Point cloud of removed

對圖5中的點(diǎn)使用RANSAC算法提取平面特征，并將提取出的特征點(diǎn)恢復(fù)至之前的點(diǎn)云中。最終結(jié)果如圖5所示。將圖6與圖4對比可知，最終點(diǎn)云的墻面信息較之前有了很大的改善，同時墻面后的稀疏離群點(diǎn)也得到了有效的抑制。

圖6　最終點(diǎn)云數(shù)據(jù)的正面與側(cè)面圖Fig.6　Front view and top view of final point cloud

2.4.2算法比較

為了驗(yàn)證基于特征恢復(fù)的稀疏離群點(diǎn)在點(diǎn)云稀疏離群點(diǎn)移除方面的優(yōu)勢，對點(diǎn)云使用基于統(tǒng)計(jì)的稀疏離群點(diǎn)移除算法，同時使用基于特征恢復(fù)的稀疏離群點(diǎn)移除算法處理點(diǎn)云，對比兩種算法處理效果。

如圖7所示，分別取閾值為σ、1.5σ、2σ，其中σ為k鄰域平均距離的標(biāo)準(zhǔn)差。左側(cè)為經(jīng)過基于統(tǒng)計(jì)的稀疏離群點(diǎn)移除算法處理后的點(diǎn)云正面圖像，右側(cè)為經(jīng)RANSAC算法對點(diǎn)云進(jìn)行恢復(fù)后的點(diǎn)云正面圖像。通過對比可得，基于特征恢復(fù)的離群點(diǎn)移除算法減小了對先驗(yàn)知識的依賴，在表面信息移除較多的情況下，恢復(fù)的效果也比較好。

圖7　算法效果對比Fig.7　Comparative effects of two algorithms

3結(jié)束語

利用基于統(tǒng)計(jì)的離群點(diǎn)刪除算法，較好的刪除了稀疏的離群點(diǎn)，并針對密度不均勻的點(diǎn)云，利用點(diǎn)云特征對有信息區(qū)域進(jìn)行恢復(fù)。在刪除稀疏離群點(diǎn)的同時，保留了密度較低的特征區(qū)域點(diǎn)云。目前的研究對象是海龍囤石質(zhì)建筑，相對于現(xiàn)代規(guī)則建筑，其表面較為復(fù)雜。雖然提取特征較為困難，但是實(shí)驗(yàn)結(jié)果表明，該算法可以提取這種石質(zhì)建筑復(fù)雜的表面信息并將其恢復(fù)，并有顯著的效果。為古建筑的后期修復(fù)提供了較為完整可靠的資料，也為其后期分析、建模提供了更為有效的數(shù)據(jù)基礎(chǔ)。

參考文獻(xiàn)：

[1] 張毅,閆利.地面激光點(diǎn)云強(qiáng)度噪聲的三維擴(kuò)散濾波方法[J].測繪學(xué)報,2013，42(4):568-573.

[2] 龔書林.三維激光點(diǎn)云處理軟件的若干關(guān)鍵技術(shù)[J].測繪通報,2014(6):135-136.

[3] RUSU R B,MARTON ZC,BLODOW N,et al.Towards 3D Point Cloud Based Object Maps for Household Environments[J].Robotics and Autonomous Systems,2008,56(1):927-941.

[4] 張毅,劉旭敏,關(guān)永.基于密度的離群噪聲點(diǎn)檢測[J].計(jì)算機(jī)應(yīng)用,2010，30(3):802-805.

[5] 朱俊鋒,胡翔云,張祖勛,等.多尺度點(diǎn)云噪聲檢測的密度分析法[J].測繪學(xué)報,2015，44(3):282-291.

[6] HAWKINS D.Identification of Outliers[M].London:Chapman and Hall,1980.

[7] JACOBS G.Accuracy of scan points[J].Professional Surveyor Magazine,2009,29(8):1-3.

[8] 施貴剛,程效軍,官云蘭,等.地面三維激光掃描點(diǎn)云配準(zhǔn)的最佳距離[J].江蘇大學(xué)學(xué)報(自然科學(xué)版),2009，30(2):197-200.

[9] 朱德海.點(diǎn)云庫PCL學(xué)習(xí)教程[M].北京：北京航空航天大學(xué)出版社,2012：10.

[10]胡偉,盧小平,李珵,等.基于改進(jìn)RANSAC算法的屋頂激光點(diǎn)云面片分割方法[J].測繪通報,2012(11):31-34.

文章編號：1004—5570(2016)01-0088-05

收稿日期：2015-09-24

基金項(xiàng)目：貴州省科技廳工業(yè)攻關(guān)項(xiàng)目(黔科合GZ字[2012]3017)；貴州省科學(xué)技術(shù)基金資助項(xiàng)目(黔科合J字LKS[2011] 9號)；貴州省經(jīng)濟(jì)和信息化委員會資助項(xiàng)目(1158)；貴州省科技廳攻關(guān)項(xiàng)目：海龍屯申報世界文化遺產(chǎn)關(guān)鍵性技術(shù)研究(黔科合SY字[2014]3072號)

作者簡介：郭子選(1989-)，男，碩士研究生，研究方向：計(jì)算視覺，E-mail：313984057@qq.com. *通訊作者：謝曉堯(1952-)，男，教授，博導(dǎo)，博士，研究方向：網(wǎng)絡(luò)與信息安全、計(jì)算數(shù)學(xué)，E-mali：xyx@gznu.edu.cn.

中圖分類號：TP391

文獻(xiàn)標(biāo)識碼：A

Sparse outlier removal algorithm based on resuming features

GUO Zixuan，XIE Xiaoyao*，LIU Song

(Key Laboratory of Information and Computing Science Guizhou Province, Guizhou Normal University, Guiyang， Guizhou 550001, China)

Abstract:The point cloud pre-processing is very important part of point cloud processing. In the process of removing the sparse outliers , the uneven point density of the point cloud can cause excessive deleted of useful information. In order to solve this problem, Sparse outlier removal algorithm based on resuming features is proposed. Firstly, using the traditional k neighborhood sparse outliers removal to processing the original cloud point. For the case of excessive deleted, using the RANSAC algorithm to recovery feature point.The experimental results show that the sparse outlier removal algorithm based on resuming features is better than traditional methods. It makes a significant improvement in sparse outliers removed. The conclusion is that the algorithm can effectively remove the sparse outlier and reduce dependence on the noise threshold. Meanwhile, the algorithm can effectively suppress excessive deleted caused by uneven density.

Key words:3D laser scanner; sparse outliers; k-dimensional tree; k neighborhood; random sample consensus algorithm