基于歐式距離平均值的離群點(diǎn)自動(dòng)檢測(cè)算法

程杰

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

關(guān)鍵詞：歐式距離平均值；離群點(diǎn)；自動(dòng)檢測(cè)

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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