程杰

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

關鍵詞：歐式距離平均值；離群點；自動檢測

中圖分類號：TP37 文獻標識碼：A 文章編號：1009-3044（2015）07-0240-03

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

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

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

1 離群點檢測相關算法分析

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

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

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

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

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

2 基于歐式距離平均值的離群點檢測改進算法

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

在實踐中，閾值的設定應當兼顧剔除效率和微小特征保持效果。

4 結論

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