DBSCAN聚類和改進的雙邊濾波算法在點云去噪中的應用

曲金博，王 巖，趙 琪

(沈陽建筑大學交通工程學院，遼寧 沈陽 110168)

隨著測繪技術的發(fā)展，三維模型在各方面都有著廣闊的應用前景。三維激光點云數(shù)據(jù)獲取時，由于儀器本身的精度，以及人為、環(huán)境因素等的影響，采集到的三維激光點云數(shù)據(jù)總存在噪聲。近些年，國內外學者提出了一些點云去噪的方法，如文獻[1]基于特征選擇的雙邊濾波去噪，首先判斷鄰域點屬于特征點還是非特征點，然后根據(jù)不同的點云范圍進行濾波因子去噪，該算法在光順上有所改進，但時間較長。文獻[2]根據(jù)自適應密度聚類的結果進行雙邊濾波去噪，有效地去除了模型中的噪聲點，但耗時太長。文獻[3]引入雙邊濾子進行雙邊濾波自適應運算，選取自適應灰度方差S1，從而實現(xiàn)雙邊濾波算法的自適應，該算法自適應選取存在偏差，噪聲去除有待加強。文獻[4]針對噪聲點尺度的問題，提出噪聲尺度分類的雙邊濾波點云去噪算法，該算法將噪聲分為大尺度和小尺度噪聲進行去除，使用統(tǒng)計濾波和曲率估計對點云雙邊濾波進行改進，最后運用改進的雙邊濾波對小尺度噪聲進行處理，該算法對不同尺度的噪聲均有較好的去除效果，但是算法效率較低。文獻[5]提出了一種改進的基于三維幾何雙邊濾波的網(wǎng)格去噪方法，該方法保存了物體的特征，同時降低了噪聲，達到不錯的效果。

為了更好地識別噪聲類型，對噪聲點進行去除，保留點云特征，筆者提出將基于密度的DBSCAN聚類算法和改進的雙邊濾波方法相結合進行點云去噪。針對點云數(shù)據(jù)的特征，采用基于密度的DBSCAN聚類算法，通過設定密度參數(shù)來排除噪聲點，對于其他點云采用改進的雙邊濾波方法進行光順去噪，以提高去除噪聲點的效率；并以沈陽民國時期代表性的建筑——沈陽金融博物館為試驗模型，對建筑實體進行去噪和光順處理。

1 三維點云去噪算法

1.1 DBSCAN聚類算法原理

DBSCAN是一種經(jīng)典的基于密度的聚類算法，不僅可以發(fā)現(xiàn)數(shù)據(jù)集中任意形狀的類，且可以發(fā)現(xiàn)噪聲點[6-8]。

DBSCAN算法有幾個基本概念，引入記號表示概念，其中設數(shù)據(jù)集合D={x1,x2,…,xn}。

領域(Eps)：設x∈D，稱DX={y∈D：d(y,x)≤Eps}為x的鄰域，顯然x∈Dx。

密度(density)：設x∈D，稱ρ(x)=|Nx|為x的密度。本文的密度是一個整數(shù)值，且依賴于半徑。

邊界點(border point)：若x∈Dnc，且?y∈D，滿足y∈D，滿足y∈Nx∩Dc，即x的領域中存在核心點，則稱X為D的邊界點，記由D中所有邊界點構成的集合為Dbd。此外，邊界點也可以這么定義，若x∈Dnc，且x落在某個核心點的領域內，則稱x為D的一個邊界點。一個邊界點可能同時落入一個或多個核心點的領域。

核心點就是區(qū)域內部較稠密的點，邊界點就是稠密區(qū)域邊緣的點，而噪聲點就是沒有被區(qū)域覆蓋的點。

直接密度可達(directly density-reachable)：設x，y∈D，若滿足x∈Dc，y∈N(x)，則稱y是從x直接密度可達的。

密度可達(density-reachable)：設p1，p2，…，pm∈D，其中m≥2。若滿足pi+1是從pi直接密度可達的，i=1，2，…，m-1，則稱pm是從p1密度可達的。

密度相連(density-connected)：設x，y，z∈D，若y和z均是從x密度可達的，則稱y和z是密度相連的，顯然密度相連具有對稱性。

類(cluster)：稱非空集合C?D是D的一個類，如果它滿足對于x，y∈D，則：

(1) 最大化原則(maximality)，若x∈C，且y是從x密度可達的，則y∈C。

(2) 連通性原則(connectivity)，若x∈C，y∈C，則x、y是密度相連的。

1.2 雙邊濾波算法原理

1.2.1 雙邊濾波方法

雙邊濾波是一種濾波器，它是能夠保持邊界特征、去除噪聲點和光順的一種方法。雙邊濾波最重要的是權重，通過計算權重，使數(shù)據(jù)點向法向方向聚集，達到光順去噪。

在雙邊濾波中，定義如下

p=pi+αn

(1)

式中，p為濾波后的點云數(shù)據(jù)；pi為原始點云數(shù)據(jù)；α為雙邊濾波權因子；n為數(shù)據(jù)點pi的法向量[7]。點云數(shù)據(jù)中α的定義為

(2)

式中，N(pi)為數(shù)據(jù)點pi的鄰域點。

1.2.2 雙邊濾波方法改進

本文對雙邊濾波因子進行改進，提高其穩(wěn)健性與保特征性，改進后的雙邊濾波因子定義為

(3)

光順濾波權函數(shù)是標準高斯濾波,定義為

(4)

特征保持權函數(shù)與光順濾波權函數(shù)類似，也是標準高斯濾波，定義為

(5)

式中，參數(shù)σc和σs均為高斯濾波參數(shù)，參數(shù)σc為數(shù)據(jù)點Pi到鄰域點的距離對Pi點的影響因子，參數(shù)σs為數(shù)據(jù)點Pi到鄰近點的距離在其法向量上的投影對Pi點的影響因子。其中，參數(shù)σc越大，三維點云數(shù)據(jù)模型的光滑性就越好；參數(shù)σs越大，三維點云數(shù)據(jù)模型的特征保持性就越好[9-12]。

2 本文方法

本文利用密度DBSCAN聚類算法對三維點云數(shù)據(jù)進行聚類，在聚類結果中選擇建模所需的主體點云，去除噪聲點云。

在DBSCAN聚類算法中初始半徑和最小鄰域都是自定義參數(shù)，要得到最優(yōu)的結果必須反復設置兩個參數(shù)。筆者針對反復設置參數(shù)的問題，提出自動計算初始半徑和最小鄰域的方法，用來降低算法的復雜度，提高計算速度[8]。

DBSCAN聚類算法在實際應用中比較耗時，為了得到良好的效果就需要設定好參數(shù)，初始半徑和最小鄰域屬于自定義參數(shù)，要得到最優(yōu)的結果必須反復設置兩個參數(shù)。本文針對上述問題采用自動計算初始半徑和最小鄰域的方法，代替人工調整參數(shù)，該方法能有效提高計算速度。計算步驟如下：

(1) 計算間隔距離。根據(jù)式(6)—式(9)分別計算出i、j兩點的歐氏距離、最大值、最小值和距離間距。

(6)

maxdist=Max{dist(i,j|0≤i≤n,0≤j≤D)}

(7)

mindist=Min{dist(i,j)|0≤i≤n,0≤j≤D}

(8)

distance=maxdist-mindist

(9)

式中，(xi，yi，zi)、(xj，yj，zj)分別為點i和點j的坐標；dist(i，j)為點i和點j之間的歐氏距離；maxdist為i、j兩點間距離最大值；mindist為i、j兩個點間距離最小值。

(2) 計算初始半徑。把任意兩點間的距離均勻分割成m段，并檢測每段中dist(i，j)的頻數(shù)pk，初始半徑就是最大頻數(shù)(rang)所在分段的中值，最大頻數(shù)的計算公式為

rang=Max{pk|0≤k≤m}

(10)

(3) 計算最小鄰域點數(shù)量。在確定初始半徑后，增加最小鄰域數(shù)，計算出鄰域超過最小鄰域數(shù)量的點的數(shù)量pN，對于任意點pi的鄰域點數(shù)量pN1的計算公式如下

pN=count{dist(i,j)

(11)

pN1=count{pN1≥minpts|0≤i≤D}

(12)

豎軸是點云數(shù)量，橫軸是最小鄰域點數(shù)。從圖2可以看出，在計算最小鄰域點數(shù)中，隨著最小鄰域數(shù)量的增大，其中pN先大幅下降，然后趨于穩(wěn)定。當minpts的值為9時，曲線基本穩(wěn)定，因此最小鄰域數(shù)目的取值為9。針對選取部分點云數(shù)據(jù)，pN的變化過程如圖2所示。

DBSCAN聚類的步驟如圖3所示。

利用DBSCAN聚類算法去除噪聲點后，繼續(xù)對點云數(shù)據(jù)進行濾波。本文用改進后的雙邊濾波方法對點云數(shù)據(jù)進行光順[13-15]。

雙邊濾波去噪具體流程如下：

(1) 對每個點云數(shù)據(jù)Pi，求出它的k個最近鄰點。

(3) 根據(jù)式(4)與式(5)計算出光順濾波權函數(shù)Ws(x)和特征保持權函數(shù)Ws(y)。

(4) 將Ws(x)和Ws(y)代入，求出改進雙邊濾波因子α′的值。

(5) 將采樣點Pi移動到濾波后的新數(shù)據(jù)點p的位置，建立新的點位信息。

(6) 更新點云數(shù)據(jù)，輸出數(shù)據(jù)。

3 試驗結果及分析

為驗證本文算法的有效性，以沈陽民國時期代表性的建筑——沈陽金融博物館為試驗模型，運用DBSCAN聚類算法和改進后的雙邊濾波方法對其進行處理試驗，結果如表1、圖4—圖6所示。

表1 點云數(shù)據(jù)量

從表1可以看出，本文方法處理所得的點云數(shù)據(jù)量要遠遠少于未經(jīng)DBSCAN聚類算法處理直接濾波的點云數(shù)據(jù)量，說明筆者對于兩種算法的結合是有效的，能夠大幅去除數(shù)據(jù)點和噪聲點。

圖4中可以清晰看到存在大量的噪聲點，圖5為采用雙邊濾波方法處理后的數(shù)據(jù)，可以看出已經(jīng)去除了部分噪聲點，去噪效果一般，但保持了建筑物實體的特征。圖6為文本方法處理之后的數(shù)據(jù)，可以清晰地看出圖中噪聲點幾乎全部清除干凈，去噪效果也比較明顯，相對于圖5不僅去除了大量點云噪聲點，同時也保持了建筑物實體的特征，進一步驗證了本文算法的有效性。

4 結 語

本文以沈陽金融博物館為試驗模型，提出了基于密度的DBSCAN聚類算法和改進的雙邊濾波方法相結合的點云去噪算法，針對噪聲點先采用DBSCAN聚類算法，然后使用改進的雙邊濾波算法，在去除大量噪聲點的同時又能很好地保持點云數(shù)據(jù)的特征，相比直接運用雙邊濾波算法可以有效地提高點云去噪效率。