一種高效的點云去噪聚類方法

鐘文彬，肖振遠，劉光帥

（1.中國電子科技集團公司第十研究所，四川 成都 610036；2.西南交通大學機械工程學院，四川 成都 610031）

1 引言

在逆向工程中，使用激光掃描設備獲取點云數據時，由于受到操作設備的精度、操作人員的經驗、環境因素、物體表面特性等影響，使得采集得到的點云數據會引入與目標點云無關的噪聲點云，這些噪聲點云嚴重影響后期的處理，如特征提取、特征匹配、三維重建的精度等［1-3］。因此，對獲取的包含噪聲的點云數據進行預處理顯得至關重要。

近年來，研究者針對點云的預處理進行了大量的研究［4-9］。文獻［4］提出基于方法庫的點云去噪方法，利用統計濾波結合半徑濾波可以去除大尺度噪聲，但對于距離目標點云類較近的噪聲點，該方法無法有效去噪。文獻［5］提出擬合二次曲面實現點云的去噪，該方法依賴于魯棒的法向估計和基于投影的局部曲率，可很好的保持特征，但法向估計易受偏差的干擾。文獻［6］提出基于特征選擇的雙邊濾波點云去噪算法，該方法較好的保留了點云的細節特征，當存在大尺度噪聲時，雙邊濾波會產生過光順的問題，因此不適合對離群點云噪聲濾波。文獻［9］用K-means聚類算法對點云進行聚類，根據點到聚類中心的歐式距離和臨近點曲率變化判斷每個類中的點是否為噪聲點，去除外部噪聲點云，由于Kmeans聚類算法對初始值較敏感，因此去噪效果難以把控。

以上濾波算法在點云去噪時不能較好的將離體噪聲點云去除，嚴重影響后期點云三維重建的精度。針對上述問題，在密度聚類點云去噪算法基礎之上，提出一種高效的點云去噪聚類方法。該方法摒棄密度聚類算法使用歐氏距離逐點遍歷判斷的思想，采用KD-tree［10］對點云數據進行搜尋，將點云數據按某一維度進行排序，在確定的核心點云鄰域外選擇未標記的最近點云進行擴展密度類，最后分離出點云數量最大的點云類以完成點云去噪。

2 方法框架

該方法以手持激光掃描儀獲取的有序點云為對象，提出一種高效的點云去噪聚類算法。算法去噪的整體框架流程，如圖1所示。首先，對原始點云建立KD-tree空間索引結構；接著，選擇點云的某一維度，找出該維度最小索引核心點云；然后，沿該維度方向按方法提出的聚類方法擴展密度類；最后，分離最大點云數量的密度類，得到目標點云。

圖1 文章方法框架Fig.1 The Framework of this Paper

3 高效的點云去噪聚類方法

對獲得的點云數據分析可知，原始的點云數據分布存在一定的規律，即目標點云中相鄰兩個點的間距保持在激光掃描設備設定的采樣間距范圍之內上下波動，連續布滿整個空間位置。而噪聲點云是隨機誤差造成的，其相鄰點之間的間距不確定、位置不固定。密度聚類是一種無監督聚類算法，能在“噪聲”數據中識別出任意形狀的聚類［11-15］，在點云應用鄰域較其他聚類算法有著獨特的優勢。但由于密度聚類在去除點云噪聲時需要對點云進行逐個遍歷，利用歐式距離進行鄰域點判斷，內存要求較高，收斂時間較長，降低了點云去噪的效率，不適合海量點云的去噪處理。為克服以上密度聚類去除點云噪聲時的缺點，提出一種高效的點云去噪聚類方法。

3.1 KD-tree建立空間索引

密度聚類算法點云去噪時使用歐氏距離逐點遍歷的思想。因此，為加快點云查找的速度，該方法采用KD-tree空間索引結構。KD-tree是一種k維數據結構，能快速搜尋近鄰點。該結構選擇點云的某一維度，以該維度的中位數將數據分為兩部分，然后對其他維度重復該過程，直至將點云數目分割成單個點。點云KD-tree結構（為便于描述，所有點云描述圖均為二維表示），點a和點g是以半徑為r、鄰域點數為3確定的核心點云，如圖2所示。

圖2 點云KD-tree結構Fig.2 The Structure of Point Cloud KD-tree

3.2 點云去噪聚類方法

獲取的點云數據大多數為幾十萬量級點云，對于較大的精密的對象，獲取的點云數量為百萬級至千萬級點云，使用密度聚類需要對逐個點云遍歷判斷，需要根據設定的ε和m遍歷計算每個點云數據，其時間復雜度為是O（N*找出ε鄰域中的點所需要的時間），N為點云的個數，最壞的情況下時間復雜度可能是O(N2)，降低了點云噪聲的效率且對內存要求較高。該方法在去除噪聲點時，由于加入KD-tree進行索引，可以將復雜度降到O(NlogN)。通過點云分析發現：若點云中某個點為核心點云，則該點鄰域內所有點與該點屬于同一類，則下一點選擇的對象不應在該點確定的鄰域內，從該點鄰域外選擇下一點，從而可以大量降低了點云遍歷的次數，其查詢點的個數小于N，故時間的復雜度小于O(NlogN)，從而提高了點云去噪的效率。該方法在點云去噪時涉及以下相關概念：

概念1 直接密度可達（Directly Density-Reachable）

給定一片點云D，點q是一個核心點云，點p是在以點q為球心、ε為球半徑的鄰域內，則稱對象p從對象q出發是直接密度可達的。如圖2所示，其為點云數據的一部分，點a是以球的半徑為r、鄰域點云數量為m= 3確定的核心點云，其鄰域內的所有點云均為從點a出發是直接密度可達的。

概念2 密度可達（Density-Reachable）

如果存在一個點云對象鏈p1，p2，p3，...，pn，p1=q，pn=p，對pi∈D(1 ≤i≤n)，pi+1是從pi關于ε和m直接密度可達的，則對象p是從對象q關于ε和m密度可達的，如圖3（a）所示，p到q是密度可達的。

圖3 點云數據描述Fig.3 Point Cloud Data Description

概念3 密度相連（Density Connection）

如果點云D中存在一個對象o，存在對象p和q均是從對象o關于ε和m密度可達的，那么稱對象p和q是關于ε和m密度相連，如圖3（b）所示，o為核心點云，p和q由于距離點云邊界較近，未構成核心點云，但構成密度相連。

該方法的基本思想為：采用KD-tree對點云數據建立空間索引結構，將點云數據按某一維度進行排序，從排序最小的索引號確定核心點云，如果為核心點云，將鄰域內的點與之歸為同類。接著從排序的點云中選取距離上一核心點云最近的鄰域外未標記的點云，判斷是否為核心點云，如果為核心點云，且與上一核心點云的鄰域有重疊點且重疊點存在核心點云，則將該核心點云及其鄰域點與上一核心點云歸為同類，否則為新類。如圖4（a）所示，設定的球半徑為ε和m= 6，p和q為核心點云，其鄰域的重疊區域內存在點o是核心點云，故p、q及其鄰域點云均為同類點云；如圖4（b）所示，p和q為核心點云，其鄰域的重疊區域o不是核心點云，故p和q為兩類點云。依次遍歷整個點云進行密度相連，最后分離點云數量最大的點云類以完成點云去噪。

圖3中第一個峰為氣體產物CO2，其相對含量最高(64.97%)，CO2主要是由于羧酸類物質中羧基的斷裂以及醛酸等物質的一次裂解產生。其后出現的色譜峰峰形較為復雜，主要為各種異構體。

圖4 點云數據說明Fig.4 Point Cloud Data Explanation

3.3 方法步驟

該方法整體實現過程步驟如下：（1）根據激光掃描儀設定的采樣間距選擇方法所需的鄰域半徑和鄰域點云個數；（2）對點云使用KD-tree建立空間索引結構；（3）選擇某一維度對點云進行排序；（4）從最小索引點判斷是否為核心點云，如果為核心點云，從核心點云鄰域外選擇最近點擴展密度相連，具體過程流程圖，如圖5所示；（5）統計各類點云的數量，提取最大數量點云，完成去噪。

圖5 聚類流程圖Fig.5 The Chart of Clustering Flow

4 實驗結果與分析

4.1 實驗數據

文中使用天遠設備的Freescan X5手持激光掃描設備獲取的電路板的有序點云數據作為實驗樣本，如圖6、圖7所示。點云的格式為asc。截取局部右上角和局部右下角細節特征進行實驗對比觀察，原始點云中矩形、圓形、三角形標記處的噪聲點云很明顯。圖中的黑色圓塊為掃描時加入的標志點，左下方散亂區域是夾具夾持造成，忽略不計。使用C++程序語言在VS2015平臺上擴展點云PCL模塊實現算法，計算機配置為Intel（R）Core（TM）i5-9400F CPU@2.9 GHz、內存為16 GB、64 位的Windows10 操作系統、GTX1060顯卡。

圖6 右上角原始點云數據Fig.6 Raw Point Cloud Data in the Upper Right Corner

圖7 右下角原始點云數據Fig.7 Raw Point Cloud Data in the lower Right Corner

4.2 去噪對比實驗與分析

將本方法與主流點云庫中的統計濾波、半徑濾波和密度聚類去噪算法進行對比實驗結果，如圖8、圖9所示。相關數據，如表1、表2所示。實驗所取參數是經多次試驗后，盡可能去除離體噪聲點取得的最好效果對應的參數值，統計濾波標準差乘數為0.3，查詢的近鄰點數為300；半徑濾波采用半徑為0.0003m，半徑內的近鄰點數為8；密度聚類和本方法均采用半徑為0.0003m，半徑內的近鄰點數為8。從圖8和圖9中可以看出：（1）圖8（a）的三角形標注處和圖9（a）的矩形標記處仍存在離體聚集的噪聲點，圖8（a）的圓形標記處內圓的輪廓被模糊，圖9（a）的圓形標記處的特征圓銜接處被斷開，原因是統計濾波在處理點云數據時，對每個點的鄰域進行統計分析建立高斯分布，將距離處于標準差倍數范圍之外的點判定為噪聲點云去除，而目標點云體外的聚集的噪聲點云也存在此種性質，故不能將體外聚集的噪聲點完全去除，另外，當邊界點云較少時，邊界被模糊，如圖8（a）右上角的邊緣輪廓和圖9（a）的三角形標注的右下角斜邊輪廓；（2）圖8（b）和圖9（b）中的完整平面被稀疏模糊出現孔洞，原因是半徑濾波將稀疏部分的目標點云當成噪聲點云；（3）標記處的噪聲點云經密度聚類算法和本方法處理后的效果如圖8（c）和圖8（d），不存在前述統計濾波和半徑濾波問題，明顯優于統計濾波和半徑濾波。

圖8 右上角去噪算法對比圖Fig.8 Denoising Algorithm Comparison Diagram in Upper Right Corner

圖9 右下角去噪算法對比圖Fig.9 Denoising Algorithm Comparison Diagram in Lower Right Corner

表1 右上角去噪算法對比Tab.1 Comparison of Denoising Algorithms in the Upper Right Corner

表2 右下角去噪算法對比Tab.2 Comparison of Denoising Algorithms in the Lower Right Corner

從表1、表2中可以看出：

（1）統計濾波和半徑濾波速度較快，去除了大量的點云，但其存在缺陷，如圖8（a）和圖8（b）的三角形標記和圖9（b）中的矩形標記仍然存在離體噪聲點云；

（3）本方法的速度明顯快于密度聚類算法，僅次于半徑濾波。這是由于本方法在去噪時，加入KD-tree進行索引，從鄰域外進行遍歷，依據重疊點判斷密度相連，提高了聚類的速度。

5 結論

針對點云數據在曲率較大處及邊界存在較多的噪聲問題，提出一種高效的點云去噪聚類方法。通過對點云數據建立KD-tree空間索引結構，將點云按某一維度，從核心點云鄰域外選擇最近的未標記的樣本點擴展密度類，最后分離出密度相連最大的目標點云類。實驗針對手持激光掃描設備獲取的電路板點云數據，對統計濾波、半徑濾波、密度聚類和本方法去噪結果進行了對比，結果表明本方法能在去除孤立的或聚集的離體噪聲點的同時可以較完整地保留目標點云，降低了對內存的依賴性，提高了點云去噪的質量。