轉載請說明出處：

http://blog.csdn.net/zhubaohua_bupt/article/details/70194047

基于密度的點云聚類算法可以識別三維點云物體，也可以對三維點云去噪處理。

本文研究了兩種基于密度的點云聚類方法，先簡單介紹一下兩種算法，后面會詳細的介紹算法原理以及效果。
第一種方法叫做密度減法聚類
功能：能識別特定尺寸的點云簇集合，通過參數(shù)設置期望形狀的大小。
輸入：一片點云
輸出：是幾個聚類完成的點簇和聚類中心點
類別不需要提前設定，最終聚成幾類由初始參數(shù)決定。
論文 ?3D Candidate Selection Method for Pedestrian Detection on Non-Planar Roads 用其來提取行人的ROI。
第二種方法叫做自適應密度聚類
功能：可以尋找出每個點云的三維連通域，不需要設置形狀和大小參數(shù)。
輸入：一片點云
輸出：每個點云所在的連通域以及此點云集合一共有多少連通域。
類別不需要提前設定，最終聚成幾類由連通規(guī)則中參數(shù)決定。

論文 一種聚類與濾波融合的點云去噪平滑方法 ?和 ?密度聚類算法在連續(xù)分布點云去噪中的應用 用這種聚類方法來對點云去噪。

?

下面來分別詳細介紹一下兩種方法。

一：第一種方法 ?密度減法聚類

先看一下流程，這里說明一下，為了提高速度，我們在聚類的時候沒有直接對稠密的處理，而是先采樣生產稀疏點云，旨在提速。

圖一 ? ? ?本方法流程圖

1 此方法對密度定義為

公式9中rax，ray和raz就是那個你想要設置的聚類形狀參數(shù)。可以看出

<1> 對于一個特定的三維點，離其越近的點對它的密度加成越大。

<2>從求和符號可以看出，它是遍歷所有三維點。

2 再看公式(10),這個公式是這個算法的核心。

Di表示檢測出的一定聚類中心和一定不是聚類中心的其他三維點的密度，xi，yi，zi為其坐標，rbx,rby,rbz為用于跟更新Di密度的半徑參數(shù)。Dcl為上一次聚類中心的密度。xcl，ycl，zcl為其坐標。

為什么要搞這么一個公式呢？

因為聚類的目的是想得到幾個密度比較大的點簇，是為了避免多個聚類中心集中在一起。舉個例子，你面前有幾個人而且你有他們的點云，你想通過聚類把這幾個人分出來，他們體型相差很大比如，這些人中有人身寬體胖的人，有人身材比較瘦小，你的本意是想把這幾個人都識別出來。回到算法中，看流程圖，如果我們每此檢測下一次聚類中心的時候去掉了更新所有點云這一步驟，那么那個胖的人身上一定會被聚類成好多個聚類中心。

說白了，公式10起到這樣一個作用：凡是離上次剛得到的聚類中心近的點，它們的密度都會被削減，削減影響的范圍由rbx,rby,rbz控制。rb參數(shù)的選取一般要大于ra參數(shù)，論文中取rbm=1.5ram ?m=x,y,z;

3 最終聚類點簇的大小差異控制

這部分參數(shù)也是本方法的一個重要的參數(shù)，因為它們控制著最終聚類結果中每個點簇的大小，以及最大點簇和最小點簇的密度差異有多大。

具體參數(shù)有：Thmax,Thmin，ra，cnt和公式9中的半徑參數(shù)。

其中，公式中的半徑參數(shù)控制著聚類物體的大概三維尺寸（橢球）

Thmax：當一個候選聚類中心的密度大于第一個聚類中心密度的Thmax倍，直接就接納此聚類中心。

Thmin：當一個候選聚類中心的密度小于第一個聚類中心密度的Thmin倍,直接把對應三維點拉黑，以后再也不用，并認為它不會是聚類中心。

ra:此參數(shù)控制相鄰聚類中心的距離，選取的越大，生成的聚類中心間隔越大。

最后，流程圖還剩一個參數(shù)dmin，這個參數(shù)的含義是：本候選聚類中心到其他聚類中心距離中的最小值。

原理部分就說這么多，下面來看一下效果，我暫用它來檢測一個桶:參數(shù)設置好后，效果如下（當然，這種方法還是有缺陷的，即只能檢測形狀，其他和桶三維大小差不多的物體也會被檢測出來）：

圖2 輸入： 選取的一定高度的稀疏點云（上方也會有幾個，是因為我們點云數(shù)據(jù)不太準確，會有一些噪點）

圖3 ? ? ? ?聚類輸出（不同顏色表示不同點簇，聚類中心用大圓點表示）

第二種：自適應密度聚類

這種方法就是實際上就是三維連通域檢測。聚類最后的輸出是若干塊三維連通域。和上一種方法不一樣，這種聚類方法不需要設置新裝參數(shù)，輸出的每塊連通域的大小不一定相等。下面給出這種 方法的流程圖：

圖 4 ?自適應密度聚類算法流程

此算法尋找連通域的步驟對應于流程圖的第二至第三個判斷條件組成的循環(huán)體。每循環(huán)一次，生成一個新的三維連通域。

密度定義 ：此方法沒有對密度定義，而是定義了一個類似密度的核心對象：是在點云空間范圍內，如果離點p的歐式距離小于e的其他點云數(shù)大于一個值Minpts，就認為點p是核心對象。

那么為什么稱這種方法叫自適應密度聚類呢？

答案是，聚類它可以根據(jù)點云自適應求出半徑參數(shù)e和點數(shù)Minpts，不需要自己提前設定，當然自己也可以提前設定。

怎么求參數(shù)e和Minpts呢？

引用原文的話：

?

?

在上述密度聚類步驟中，初始半徑e 和最小鄰域數(shù)MinPts均為自定義參數(shù)。參數(shù)初始值設置好后，需要根據(jù)聚類效果不斷調整這兩個參數(shù)以獲得最好的聚類效果，比較耗時。為了解決這一問題，本文提出一種自適應參數(shù)計算方法。

(1)

首先，根據(jù)式(1) 計算任意兩點之間的歐式距離1。

然后根據(jù)式( 2)－式( 3) 求得dist(i,j ) 的最大值maxdist 和最小值mindist，maxdist = Max{dist( i，j)| 0 ≤ i ＜ n，0 ≤ j ＜ n} ( 2)

mindist = Min{dist( i，j )| 0 ≤ i ＜ n，0 ≤ j ＜ n} ( 3)

進而根據(jù)式( 4) 求得距離間隔distrange。

distrange = maxdist －mindist??????????????????? ( 4)

其中，n 表示點的數(shù)目。將距離間隔等距分為十段，統(tǒng)計dist(i，j)在每段范圍內的頻數(shù)，初始半徑e 的值即為erang 所在分段的中值。erang 的計算公式如式( 5)所示。

erang = Max{pk | 0 ≤ k ＜ 10}???????????? (5)

初始半徑e 確定后，根據(jù)e 逐步增大最小鄰域數(shù)目MinPts，計算鄰域超過最小鄰域數(shù)目的點的數(shù)目pNum(計算公式如式( 7)所示) 。隨著最小鄰域數(shù)目的增加，pNum 會逐漸減少并趨于穩(wěn)定，選擇拐點所在的最小鄰域數(shù)目作為MinPts。其中，對于任意給定點p 的鄰域點數(shù)目pNumi的計算如式( 6)所示。

pNumi = count{dist( i，j)＜ e | 0 ≤ j ＜ n} ( 6)

那么:

pNum = count{ pNumi ≥ MinPts |0 ≤ i ＜ n} ( 7)

通過該方法可以實現(xiàn)初始半徑和最小鄰域數(shù)的自動選擇，進而避免這兩個參數(shù)的反復設置。

?

下面給出這種方法的效果：

測試說明：

輸入：用深度相機獲得的半稠密點云，如圖3

輸出：聚類結果圖，如圖4，圖5，去噪圖，如圖6。

圖 5帶有噪聲的點云圖

圖6 聚類結果圖（所有的核心對象，顏色不同，所屬類別不同）

圖7?聚類結果圖（聚類后的非核心對象密度小，認為是噪聲）

圖8 點云經過聚類去噪圖

可以看出，這種去噪方法還不錯，缺點是計算量較大，實時性難以滿足。i7-6700的筆記本上一秒3幀左右。

?

轉載于:https://www.cnblogs.com/zhubaohua-bupt/p/7182794.html

總結

以上是生活随笔為你收集整理的两种三维点云密度聚类方法的研究与对比的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。