非結構環境下一種改進的區域生長點云分割方法

劉 瑋， 李 巖， 賈 科， 劉克平*

(1.長春工業大學電氣與電子工程學院， 長春 130012; 2.長春一汽國際物流有限公司， 長春 130000)

近年來，點云處理技術逐漸應用在非結構環境下的目標零件識別領域[1]。非結構環境，即環境信息未知、不固定，且存在零件雜亂擺放相互堆疊、連接的情況。如何將單個零件從復雜背景中準確地分割出來，依舊是點云處理過程中待解決的難題。點云分割結果的好壞，將直接影響后續目標識別的精確度[2]。

目前，常用的點云分割方法有：基于聚類的分割、基于區域的分割、基于邊緣的分割以及基于模型的分割。第一類是基于聚類的分割方法。Wang等[3]提出了一種基于距離的聚類方法來解決物體重疊放置的問題，根據高斯映射的特性和點的幾何信息，可以識別出平面、圓柱體、球體等原始形狀，從而避免了點云的過分割。Sansoni等[4]提出了一種對歐式聚類進行優化的算法，用于識別有噪聲和遮擋情況下自由形狀的物體，使用定制開發的分割算法集成商業軟件庫并通過相同掃描系統創建的模型云數據庫來執行對象識別。上述方法在處理點云分割問題時，僅限于識別固定形狀的物體，在解決其他場景問題時具有一定的局限性。第二類是基于區域的分割方法。楊琳等[5]提出了一種結合超體素和區域生長的點云分割算法，首先獲得點云的空間位置信息，其次利用超體素的中心合并成均勻分布的點云，再依據其點云特征得到點云子集，最終進行區域生長聚類。Bab等[6]在傳統區域生長算法的基礎上進行相關改進。首先，為了解決模型選擇問題，引入了一種基于最小化擬合曲面應變能力的新準則。根據該準則，提出了一種穩健的數據分割算法用于分割復雜的平面與曲面對象。上述方法在進行區域生長過程中，對于初始種子點位置的選取要求較高，并且容易受到噪聲點的影響。第三類方法是基于邊緣的分割，Bao等[7]提出了一種基于三維點云的邊緣檢測方法，所采用的是Canny算子提取二維圖像中的邊緣，再根據映射算法得到三維數據的邊緣點。王宗躍等[8]使用少量時間對點云數據進行網格劃分，對非邊緣網格進行快速去除，節省了Alpha Shapes做條件判斷的時間。但上述方法僅適用于密度較小的點云數據，不具有普遍性。第四類方法是基于模型的分割。朱軍桃等[9]提出一種將三角面作為基元，并搭建Delaunay三角網格的連接關系，對區域生長算法進行簡化，解決了屋頂交界處存在采樣點異常的問題。Chen等[10]為了提取每個基元邊界，引入了一種新的基于Voronoi圖的建筑物內外邊界約束下的基元邊界提取算法。上述算法對于處理建筑物以外的物體，效果不佳，極易出現過分割或欠分割的情況。

根據環境中存在零件無序擺放的情況，選擇基于區域的分割算法進行點云分割。在傳統區域生長中通常采用隨機抽樣一致性算法獲取初始種子點，但該方法只有一定概率能夠獲得可信的模型，容易出現分割不穩定的現象[11]。因此，針對傳統算法的不足進行改進，通過計算點云曲率，將曲率最小點設置為初始種子點，再根據位置信息設定空間閾值范圍進行區域生長，提高了點云分割的穩定性和準確性，同時兼顧了分割效率，為后續的目標識別過程奠定基礎。

1 算法原理

非結構環境下，改進的區域生長點云分割方法主要流程包括：點云預處理、建立點云拓撲關系以及改進區域生長算法，如圖1所示。

圖1 改進的區域生長點云分割算法流程圖Fig.1 A flow chart of the improved segmentation algorithm for regional growing point cloud

1.1 數據獲取

使用視覺測量裝置CCD(charge-coupled device)工業相機、一臺DLP(digital light procession)投影儀來獲得點云數據，但采集點云數據時會受到周圍復雜環境的影響，容易出現大量的冗余點、離散點且會出現點云密度過大的現象。其中，冗余點來自周圍的多余背景，屬于非感興趣區域；離散點是指遠離感興趣區域的點，來源于未完全去除的冗余點和實際拍攝中存在的誤差點，其點云密度遠小于感興趣區域。這二者均會對點云數據的后期處理速度和效率造成一定影響。因此，需要對采集的冗余數據進行合理的精簡，加快后期數據的計算速度。

點云預處理步驟如下。

(1)采用直通濾波器對多余的背景信息進行去除。

(2)采用基于平面模型的分割方法對采集的平面進行去除。

(3)使用Statistical Outlier Removal濾波器來剔除離群點或拍攝導致的誤差點。

通過以上點云預處理過程進行噪聲去除，以圖2(b)初始點云(共661 522個點)為例進行實驗，圖2(f)為預處理完成后的點云(共113 708個點)。點云精簡率高達82.8%，實驗結果如圖2所示。由此可見，該預處理過程能夠有效去除冗余點及離散點。

圖2 預處理示意圖Fig.2 Preprocessing schematic

1.2 建立點云拓撲關系

在進行點云預處理過程之后，數據通常還會存在無規則分布的情況[12]。因此，在對點云進行分割之前，需要建立點云之間的拓撲關系，加快鄰近點的搜索，提高點云分割的效率。采用八叉樹建立點云之間的拓撲關系，八叉樹(Octree)即一種自上而下、逐級劃分的三維空間樹狀結構[13-14]，該層級結構如圖3所示。首先選取任意一個空間作為根節點，如果需要把空間進行細分時，將該節點劃分為八個子節點。當其中某個子節點需要繼續劃分時，則持續劃分為八個子節點，再將圖中所示的根節點與子節點相互連接，該樹狀結構稱為八叉樹。空間結構如圖4所示，空間遞歸劃分，建立點云之間的拓撲關系如以下步驟。

圖3 八叉樹層級結構圖Fig.3 Octree hierarchy diagram

圖4 八叉樹空間結構圖Fig.4 Octree space structure diagram

(1)首先，依據點云數據模型的最小空間包圍盒確立八叉樹根節點。

(2)其次，將八叉樹的根節點分別沿X、Y、Z軸方向采取均等劃分，將立方體逐步等分為8個小立方體，每個小立方體即為根節點的子節點。

(3)最后，對所有根節點以及子節點進行遞歸劃分，直到小立方體邊長滿足所設置的閾值時停止劃分。

通過以上步驟能夠對點云進行區域劃分，為后續的點云分割提供了便利。

1.3 改進區域生長算法

在完成點云拓撲關系建立后，使用區域生長算法進行點云分割。首先，設定有效的生長準則。其次，選定某一個數據點作為生長的初始種子點，將點集中具有相似幾何特征的數據點劃分到一個區域，再判斷該區域中鄰近點的選取是否符合設定的生長準則。最終，在所有滿足閾值條件的鄰近點都加入到種子區域后，停止生長。

該算法的分割結果在很大程度上取決于初始種子點的選取。當前，傳統區域生長算法在進行點云分割時通常采用RANSAC(random sample consensus)算法[15]獲取初始種子點，但容易出現分割不穩定的現象。為了克服該缺陷，提出一種改進的區域生長算法來進行點云分割。該算法用于解決重疊分割問題，通過減少區段總數，從而提高點云分割效率。將曲率最小點設置為初始種子點，即選擇所在平面最平滑的部分開始生長。

在進行點云曲率計算時，常見的方法有主成分分析(principal component analysis，PCA)法以及最小二乘法等。由于PCA方法對點云曲率的計算較為粗略，而最小二乘法計算曲率較為煩瑣。綜上考慮，選取一種基于局部徑向基函數(radical basis function，RBF)的點云曲率計算方法，構建完整的隱式曲面，再根據曲率的微分幾何性質來進行計算。基于RBF構建的隱式曲面光滑性、延續性較好，且該方法穩定性高，魯棒性強。

首先，將所獲得點云的采樣點定義為pi，將其k鄰域定義為Nk(pi)，使用1.2節的方法對k鄰域進行加速搜尋。根據反復試驗，k會有相應的取值范圍。選擇差異較大的k進行對比：當k較小時，所構造的局部曲面擬合程度較小；當k較大時，局部曲面擬合程度較大。其次，定義某一平面區域的n個目標點為{p1,p2,…,pi,…,pn}，且分別對應的約束值為{h1,h2,…,hi,…,hn}。需要構造一個隱式曲面來計算點云的曲率，即構造函數f(r)中各目標點均符合方程f(pi)=hi，則方程f(pi)=0就滿足構造的隱式曲面，該方程為

(1)

式(1)中：r為插值約束點，即構造隱式曲面的隨意雜亂點；pj為構造隱式曲面時的目標點；ωj為對應目標點的徑向基權值；P(r)即一次多項式，對隨機一點(x,y,z)，P(r)=a0+a1x+a2y+a3z；φ(r-pj)為徑向基函數，通常的表示方式為φ(x)=|x|3。

由給定的n個散亂點確定約束條件為

i=1,2,…,n

(2)

其次，使式(2)取得最小值需要符合的正交關系為

(3)

由式(2)、式(3)可以構建線性方程組為

(4)

對式(4)進行求解，獲得僅有的一組解(ω1,ω2,…,ωn,a0,a1,a2,a3)。將求得的解代入式(1)中，得到該隱式曲面方程為

f(x,y,z)=

(5)

由隱式曲面的曲率性質計算其曲率，并將其近似為目標點的曲率值。并從中選擇曲率最小的點進行生長。對需要進行分割每個點的曲率進行計算并排序，隱式曲面任一點Q的曲率K為

(6)

式(6)中：t為法向量；A為Q點周邊無窮小的區域，即隱式曲面f(x,y,z)所代表的區域；diam(A)表示為該區域直徑；?為點Q的梯度算子。將式(6)離散化，得到Qi的曲率為

(7)

式(7)中：αij、βij分別為連接Qi和Qj邊的對角。經過迭代計算，求取出點云曲率的最小值。

改進區域生長算法的具體步驟如下。

(1)首先對每個點的曲率進行計算，再依據大小值排列順序，選擇曲率最小點為初始種子點進行生長。

(2)其次，通過設定候選的種子點集合P、聚類區域Q以及空間閾值，進行鄰近點搜索判斷。如果生長半徑以及垂直距離滿足閾值條件，則將該點轉移至聚類區域Q。

(3)再將擬合曲面與種子面法矢量進行對比，如果兩夾角滿足閾值范圍，則將該點添加至種子點集合P中。

(4)刪除當前種子點，利用新加入的種子點繼續生長，循環執行步驟(2)和(3)，直到種子集合為空。

2 實驗與分析

2.1 實驗平臺設計

為了驗證該分割方法的有效性，選擇視覺測量裝置(一個CCD工業相機、一臺DLP投影儀)作為點云數據采集設備，相機到工件的距離為 1.1 m。視覺測量裝置垂直位于工作臺上方，零件隨機擺放在工作臺上，如圖5所示。在本實驗平臺下，進行了兩個場景的實驗，場景一所選取的零件為金屬盤型元件以及塑料三通管，場景二所選取的零件為金屬盤型元件、塑料三通管以及汽車金屬件。分別使用DBSCAN(density-based spatial clustering of applications with noise)聚類算法、傳統區域生長分割算法以及本文算法對場景中的無序點云進行分割。本實驗采用PC(personal computer)機安裝64位的Windows 10操作系統，配置為Intel Core i5-9500CPU、3.0 GHz、16 GB內存，使用的匯編語言為C++，應用平臺為64位的VS2017，開發環境為點云庫PCL1.8.1。

圖5 實驗平臺裝置圖Fig.5 Device diagram of experimental platform

數字表示點云子集圖6 三種算法不同場景下分割結果圖Fig.6 Segmentation results of the three algorithms in different scenes

2.2 對比實驗

區域生長算法的原理是將符合約束條件并具有類似特征的點聚在一起。因此，分割的結果為一系列點云子集，具有相同顏色的點云子集表示為一類。圖6中對場景一和場景二，分別使用DBSCAN聚類算法、傳統區域生長算法以及改進的區域生長算法，對完成預處理以及拓撲結構建立的點云數據進行分割。

在給定目標子集個數相同的情況下，分別記錄三種算法分割出的子集個數、正確分割的子集個數。如表1所示。

表1 三種算法分割效果對比表

其次，為了評估算法的效果，采用以下定量指標進行分析：分割正確率Rs以及算法耗時，用于本文算法的性能分析。在理想分割中，屬于一個類別的點將在同一點云子集中，但由于噪聲和其他環境因素影響，一些點集沒有被正確分割。

第一個評價指標Rs，即分割正確率計算公式為

(8)

式(8)中：Ns為正確分割的點云子集個數；N為分割子集個數。

第二個評價指標為算法耗時，通過記錄各算法運行時間表示該指標。如表2所示。

表2 三種算法分割效果對比表

2.3 實驗結果分析

(1)在目標零件個數相同的情況下，相比于傳統的區域生長算法，本文算法能更加準確地分割出目標零件子集。表1中對場景一的結果進行顯示，傳統區域生長算法共分割出6個點云子集，其中4個點云子集為正確的子集，出現了欠分割現象。而本文算法共分割出12個子集，其中11個為正確分割子集，未出現明顯的欠分割現象。本文相較于傳統區域生長算法，分割正確率提高了24.9%。

(2)相比于DBSCAN聚類算法，本文算法具有更快的分割效率，算法耗時更短。從表2中場景一可以看出，本文算法耗時相較于DBSCAN聚類算法，速度提高了12.5%。

3 結論

提出了一種非結構環境下改進區域生長的點云分割方法，用來解決點云分割中零件相互堆疊的情況。首先，采用直通濾波和統計濾波的方法進行離散點以及冗余點的去除，方便后續數據的處理；其次，使用八叉樹建立點云之間的拓撲結構，提高點云分割的效率；最后，通過改進的區域生長算法，選擇基于局部徑向基函數的曲率計算方法，選取曲率最小點為初始種子點，并設定空間閾值范圍進行區域生長。由此提高了無序環境下點云分割的正確性和效率。實驗結果表明，本文提出的算法對于相互堆疊的零件點云，分割正確率提高了24.9%，速度提高了12.5%。