DBSCAN 對點云障礙物聚類

（感謝前輩）轉自：https://zhuanlan.zhihu.com/p/72121128

---

點云數據去除地面后，地面上的點很自然的都成了障礙物，但是要進行目標分類，還需要把每個目標的一堆障礙物的點聚集到一起，然后才好進行后續的分析，因為每個點都是空間上離的很近的點，那么很自然的，就想到了可以使用基于密度的聚類 DBSCAN ；

為了更好的適應我的需求，使用的是自己寫的DBSCAN方法；

整個過程如下：

1 先做降采樣，降低點云數量；

2 然后地面去除，得到障礙物的點；

3 然后把剩余的地表障礙物點送入 DBSCAN 進行聚類；

4 最后進行可視化；

---

聚類核心代碼如下：

def vector_distance_v2(v):"""把單個向量內部的每個元素兩兩相減，得到一個差值矩陣，矩陣是上三角和下三角剛好相反的結果:param v: 可以是一個一維數組，或者一個一維的列表:return:"""if type(v) is list:v = np.array(v)# result = []# for i in range(len(v)):# result.append(v[i] - v) # 可以改為列表推導式result = [v[i] - v for i in range(len(v))]return np.vstack(result) def point_distance(points):"""計算所有 points 兩兩之間的距離:param points: 地面分割之后檢測出來的點 n * 4:return: n * n 的距離矩陣"""d2 = vector_distance_v2(points[:,0])**2 + \vector_distance_v2(points[:,1])**2 + \vector_distance_v2(points[:,2])**2return np.sqrt(d2)# @profile def DBSCAN_points(points, eps=2., Minpts=15):"""基于密度的點云聚類:param d_bbox: 點與點之間的距離矩陣:param eps: 最大搜索直徑閾值:param Minpts: 最小包含其他對象數量閾值:return: 返回聚類結果，是一個嵌套列表,每個子列表就是這個區域的對象的序號"""# 先求距離print('DBSCAN clustering:',points.shape)d_bbox = point_distance(points)#初始化核心對象集合T,聚類個數k,聚類集合C, 未訪問集合P,T = set()k = 0C = []P = set(range(d_bbox.shape[0]))# print('P',P)for d in range(d_bbox.shape[0]):# print(np.sum( d_bbox[d,:] <= eps))if np.sum( d_bbox[d,:] <= eps) >= Minpts:T.add(d) # 最初的核心對象print('Len T: ',len(T))#開始聚類while len(T):P_old = P #o = list(T)[np.random.randint(0, len(T))] # 從T中隨機選取一個核心元素# o = list(T)[random.randint(0, len(T)-1)] # 從T中隨機選取一個核心元素# print('o: ',o)P = P - set([o])Q = []Q.append(o)# print('Q: ',Q)while len(Q):q = Q[0]# print('q: ', q)# Nq = [i for i in range(d_bbox.shape[0]) if d_bbox[q,i] <= eps] #q的領域密度Nq = np.where(d_bbox[q,:] <= eps)[0]if len(Nq) >= Minpts:S = P & set(Nq) # 這個核心對象的密度可達對象與未訪問對象的交集Q += (list(S)) # 把這個核心對象以及它的密度可達對象都包含進來，對所有的對象再做多次密度可達檢測P = P - S # 未訪問集合P 減去 這個核心對象的密度可達對象# print('S: ', S)# print('Nq: ', Nq)# print('P: ', P)Q.remove(q) # q 已經做過密度可達檢測了，去掉它# print('------')k += 1Ck = P_old - P # 原有的P和去掉了該核心對象的密度可達對象的P就是該類的所有對象T = T - Ck # 去掉該類對象里面包含的核心對象C.append(Ck) # 把該類的對象加入列表# print('noise points:', P) # 最后沒有被歸類的數據點就是噪音點return C

存在的問題：

1 耗時久，計算量大；主要是由于 DBSCAN 需要計算每兩個點兩兩之間的距離，超過5萬個點就是25萬的距離矩陣，就直接報內存錯誤了，查看任務管理器發現內存占用達到了5-9G；盡管后續極力壓縮，還是需要5-6秒的時間，這顯然是不可接受的；

2 它對同一個物體聚類的效果比較好，不會存在同一個物體聚類分割成了2部分的情況；但是！ 它會把多個離的比較近的物體聚類為一個；

效果如下圖：

因為經過了降采樣，圖片中的點可能不是那么亮，但是其實效果還可以；并且這個里面的地面還存在一些，因為沒有使用最新的地面分割方法；

總結

以上是生活随笔為你收集整理的DBSCAN 对点云障碍物聚类的全部內容，希望文章能夠幫你解決所遇到的問題。

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