程杰

摘要：一直以來，離群點檢測在數(shù)據(jù)挖掘的研究中都是熱點問題。本文在對具有代表性的算法進(jìn)行回顧的基礎(chǔ)上，提出了一種基于歐式平均距離的離群點檢測的改進(jìn)算法，并將改進(jìn)算法應(yīng)用到了三維激光掃描所獲得的織物原始點云的檢測中。實驗表明，本算法能夠有效地剔出散亂點云中的離群點。

關(guān)鍵詞：歐式距離平均值；離群點；自動檢測

中圖分類號：TP37 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）07-0240-03

三維激光掃描技術(shù)能夠在短時間內(nèi)獲得密集的空間點云，并具有測量精度高，采樣不受曲面復(fù)雜度影響、能夠在一定程度上克服周圍光線條件和采樣樣品光學(xué)條件影響等優(yōu)勢。作為一種高效精確的非接觸式測量方法，已經(jīng)被應(yīng)用到考古、反向工程等許多工程領(lǐng)域。然而，掃描原始點云呈現(xiàn)出大規(guī)模散亂的特征。這表現(xiàn)在：點云中存在大量孔洞和噪聲數(shù)據(jù)，區(qū)域細(xì)節(jié)難以辨認(rèn)，重建十分困難；點之間沒有明顯的拓?fù)潢P(guān)系。這種掃描原始點云無法直接被用于后續(xù)分析，為了建立更為準(zhǔn)確的三維模型，還原模型表面細(xì)節(jié)，剔除不同產(chǎn)生原因和表現(xiàn)形態(tài)的點數(shù)據(jù)噪聲必不可少。

在噪聲數(shù)據(jù)中，一類點明顯原理整體點云，或密度明顯小于整體點云密度，分布更加無規(guī)律和散亂，被稱為“離群點”或“孤立點”。這部分?jǐn)?shù)據(jù)對刻畫織物表面沒有任何益處，重建階段可能會形成顯著的假面，檢測到以后應(yīng)當(dāng)被立即剔除。離面點的產(chǎn)生是由掃描設(shè)備在掃描過程中設(shè)備的計算錯誤造成的。在三維激光掃描過程中，激光掃描儀通過發(fā)射器向被測物表面投射激光條紋，反射條紋被CCD相機接收，并通過圖像處理方法，利用攝像機模型參數(shù)和光平面參數(shù)計算空間點坐標(biāo)。此外，激光線在存在大量微塵的環(huán)境中多次反射以及碳布表面“起毛”也是導(dǎo)致這些雜點產(chǎn)生的重要原因。

關(guān)于離群點檢測的算法在數(shù)據(jù)挖掘領(lǐng)域一直受到研究人員的關(guān)注。本文在對具有代表性的算法進(jìn)行回顧的基礎(chǔ)上，提出了一種基于歐式平均距離的離群點檢測的改進(jìn)算法，并將改進(jìn)算法應(yīng)用到了三維激光掃描所獲得的織物原始點云的檢測中。實驗表明，本算法能夠有效地剔出散亂點云中的離群點。

1 離群點檢測相關(guān)算法分析

根據(jù)離群點的分布特點，檢測方法主要分為以下五種：

（1）基于統(tǒng)計（分布）的檢測方法。假定數(shù)據(jù)集在整體上基本服從一個分布模型，如正態(tài)分布、泊松分布等，然后將那些偏離于該分布模型的數(shù)據(jù)標(biāo)記為離群點[1]。這種方法的缺陷是單變的，并不適合多維數(shù)據(jù)集（如三維）。而且數(shù)據(jù)集的分布通常是未知的，要使用基于統(tǒng)計的方法還需要先擬合出數(shù)據(jù)集的分布模型，難度非常大。

（2）基于深度的檢測方法?；谏疃鹊臋z測方法是針對第（1）類方法存在的兩個問題而提出的。這種方法給每個數(shù)據(jù)點分配一個深度值?；谶@個深度值，數(shù)據(jù)對象在數(shù)據(jù)空間的層里被組織起來。深度小的數(shù)據(jù)比深度大的數(shù)據(jù)更可能是離群點。這種方法的關(guān)鍵在于數(shù)據(jù)點的局部深度是尺度恒定的。比如Turkey的等深線方法，Ruts和Ronsseeuw的ISODEPTH算法，Ted Johnson對于ISODEPTH的改進(jìn)算法都屬于這類方法。

（3）基于聚類的檢測方法。基于聚類的檢測方法將數(shù)據(jù)集劃分成若干個類或簇，沒有被任何簇包含在內(nèi)的數(shù)據(jù)對象就是離群點。這類算法的核心是對類或簇的挖掘，離群點的發(fā)現(xiàn)只是挖掘簇的副產(chǎn)品。

（5）基于密度的檢測方法?；诿芏鹊臋z測是建立在基于距離的檢測定義基礎(chǔ)之上的，它將點之間的距離和給定范圍內(nèi)點的個數(shù)結(jié)合給出“密度”的概念。將離群點與局部鄰域的偏離程度作為局部離群系數(shù)（LOF）。LOF通過對象鄰域的平均可達(dá)密度與自身可達(dá)密度的比值來表示。為每個數(shù)據(jù)點定義一個LOF，其中，對象的鄰域根據(jù)用戶給定的最少鄰域參數(shù)與最近鄰域距離來確定[3]。

2 基于歐式距離平均值的離群點檢測改進(jìn)算法

實驗結(jié)果表明：運用本算法去除離群點后，平紋織物點云減少25，124個，占原始點云的1.75%；斜紋織物點云減少39，200個，占原始點云的2.04%。從圖 2中可以看出，去除離群點前后織物在正面外觀上差別不大，側(cè)面外觀來看只有一些距離織物表面較遠(yuǎn)的雜點能夠被有效去除，但是距離織物表面較近的雜點仍然保留下來了。如果需要進(jìn)一步改善點云質(zhì)量還可以采取Laplacian、雙邊濾波等濾波算法進(jìn)行處理。

在實踐中，閾值的設(shè)定應(yīng)當(dāng)兼顧剔除效率和微小特征保持效果。

4 結(jié)論

本文對比分析了已有的離群點檢測算法；對已有的基于歐式距離的檢測算法進(jìn)行了改進(jìn)，將