基于改進歐式聚類的工件分割方法

姜立豪，劉星橋，李長峰，陳 輝，馬 騰，趙德安

（1.江蘇大學(xué) 電氣信息工程學(xué)院，江蘇 鎮(zhèn)江 212013；2.常州銘賽機器人科技股份有限公司，江蘇 常州 213164）

0 引言

目前，線激光三維測量技術(shù)［1-2］廣泛應(yīng)用于非接觸式工業(yè)測量領(lǐng)域，具有測量精度高、速度快，能適應(yīng)各種復(fù)雜工業(yè)環(huán)境等優(yōu)點。點云分割技術(shù)［3］有助于進一步分析場景，例如定位、識別、分類物體或特征提取等。

常用的分割方法包括基于邊緣、基于區(qū)域增長、基于模型擬合和基于聚類4 種，其中聚類分割應(yīng)用最廣泛。劉繼忠等［4］利用物體的對稱性優(yōu)化聚類分割，并通過生活場景進行驗證，得到了更完整的分割結(jié)果。

歐式聚類在速度和效果方面均具有不錯的表現(xiàn)，但距離閾值難以確定，通常會導(dǎo)致欠分割和過分割問題。Rodrí-guez 等［5］對城市街區(qū)進行分類，提出一種新的基于自適應(yīng)歐式距離和城市塊距離的區(qū)間值數(shù)據(jù)分區(qū)聚類算法，通過在子空間中識別不同形狀、大小的聚類來優(yōu)化全局聚類。田青華等［6］利用工件形態(tài)的確定性，將單個工件離線檢測的數(shù)據(jù)轉(zhuǎn)化為特征，作為自適應(yīng)確定歐式聚類閾值的參考?；鸾y(tǒng)樂［7］通過研究非接觸邊緣點的幾何特征，提出基于點云區(qū)域特征的非接觸邊緣點判定方法，在去除接觸邊緣點的基礎(chǔ)上避免了分割現(xiàn)象發(fā)生。王瑞豐等［8］在判據(jù)中加入超像素的法向量夾角信息，以改進局部凸連接生長算法的欠分割問題。黃際瑋等［9］以小型電容為研究對象，通過歐式聚類結(jié)合區(qū)域生長，改善了傳統(tǒng)歐式聚類欠分割的問題。李仁忠等［10］以最小曲率為種子點，加入基于局部特征的生長準則，解決了傳統(tǒng)區(qū)域生長分割不穩(wěn)定的問題。宋柱等［11］提出一種分區(qū)、有噪聲的基于密度的聚類方法（DBSCAN）聚類算法，解決了密度變化導(dǎo)致行人檢測準確率較低的問題。蔡懷宇等［12］根據(jù)目標(biāo)距離調(diào)整DBSCAN 算法的距離閾值，對不同距離物體的聚類效果良好。此外，三維點云神經(jīng)網(wǎng)絡(luò)分割法［13-15］對點云具有較高的分割精度和自適應(yīng)能力，但需要預(yù)先進行一定量的訓(xùn)練，在沒有足夠多樣本的情況下無法順利實現(xiàn)。

雖然，歐式聚類在大多數(shù)場景下效果較好，但在特殊場景下需根據(jù)各自場景特點，改進歐式聚類才能取得較好的效果。本文研究多個攝像模組場景的點云分割發(fā)現(xiàn)，此類場景工件內(nèi)部面與面的交界處密度較低，且工件擺放空間有限，容易相互靠近。針對歐式聚類在點云密度不均勻時或工件相距較近時表現(xiàn)不佳的問題，提出一種基于相鄰工件區(qū)域識別的改進歐式聚類分割方法，該方法在分割環(huán)節(jié)中解決了上述問題，為后續(xù)檢測工件缺陷奠定了良好基礎(chǔ)。主要工作為：①濾波采集的點云，獲得去噪后的感興趣區(qū)域；②研究兩類相鄰工件的點云分布特征識別算法；③改進歐式聚類，根據(jù)目標(biāo)區(qū)域識別結(jié)果自適應(yīng)確定目標(biāo)區(qū)域的聚類方法。

1 基本原理

基于改進歐式聚類的相鄰工件點云分割方法的流程包括點云預(yù)處理和改進歐式聚類分割，如圖1所示。

Fig.1 Algorithm flow圖1 算法流程

1.1 點云預(yù)處理

圖2（b）為使用線掃相機得到的含有較多噪聲的點云圖，需要先采用直通濾波［16］進行去噪處理，才能得到可用于檢測缺陷的工件表面，如圖2（c）所示。直通濾波是一種簡單的濾波器，能對某個指定維度實行濾波，即去掉指定范圍內(nèi)的點。為了對后續(xù)的改進歐式聚類作數(shù)據(jù)準備，采用K 維樹（k-tree）鄰近點搜索算法［17］建立三維點云空間中的拓撲關(guān)系，并利用主成分分析法［18］以鄰近數(shù)量kn為尺度，求得每個點的法向量。

Fig.2 Preprocessing results圖2 預(yù)處理結(jié)果

1.2 改進歐式聚類分割

1.2.1 相鄰工件區(qū)域識別算法

當(dāng)歐式聚類時的搜索區(qū)域同時包含不同工件的點，此時區(qū)域為相鄰工件區(qū)域。本文算法通過識別相鄰工件區(qū)域的激光點分布特征，以正確判定歐式聚類的搜索區(qū)域是否屬于工件相鄰區(qū)域。本文以平面二維點為例，對兩種不同分布特征的相鄰工件區(qū)域識別算法的主要思想和步驟進行說明。

（1）相鄰工件區(qū)域1。相鄰工件區(qū)域存在明顯離群點（見圖3（a）），在搜索區(qū)域內(nèi)的分布特征如圖3（b）所示，在A 工件的邊緣搜索時，由于搜索半徑過大將導(dǎo)致B 類邊緣也進入搜索范圍，離群點判定的具體步驟如下：

Fig.3 Adjacent workpiece area 1圖3 相鄰工件區(qū)域1

步驟1：計算搜索區(qū)域的內(nèi)點中心以判斷搜索更傾向哪個目標(biāo)，如圖3（c）所示。求解搜索范圍內(nèi)點的坐標(biāo)的質(zhì)點，越接近搜索中心點的占比越大。內(nèi)點中心C的計算公式為：

式中：C.x、C.y為內(nèi)點中心C的x軸、y軸坐標(biāo)；D(pi，p0)為搜索范圍內(nèi)點到搜索中心的距離；n為搜索范圍內(nèi)點的數(shù)量；p0.x、p0.y為搜索中心的x軸、y軸坐標(biāo)；pi.x、pi.y為搜索范圍內(nèi)點的x軸、y軸坐標(biāo)。

步驟2：為了表示區(qū)域內(nèi)每點距內(nèi)點中心的偏移程度，求解每個點的離群值L。

式中：r為搜索區(qū)域R的半徑；Lth為離群值的閾值，當(dāng)某點L≥Lth時，判定該點為離群點。

步驟3：由于工件內(nèi)部兩個面的交界處同樣存在離群點（見圖4（a）），搜索區(qū)域A 為工件A 兩個面的交界處，搜索區(qū)域B 為兩工件相鄰區(qū)域（見圖4（b））。為了防止內(nèi)部的高曲率區(qū)域被判定為離群點，導(dǎo)致欠分割現(xiàn)象發(fā)生，本文利用搜索中心和離群點的法向量夾角對算法判定進行約束，如圖4（c）所示。

Fig.4 Constraint for determining the angle between normal vectors圖4 法向量夾角判定約束

由于區(qū)域A 的法向量夾角遠大于區(qū)域B，可通過夾角閾值θth區(qū)分工件邊緣和內(nèi)部交界處，當(dāng)θ≤θth時判定為相鄰工件區(qū)域1。具體計算公式為：

式中：n0為搜索中心的法向量；nlj(j=1，2，…，m)為離群點的法向量分別；m為區(qū)域內(nèi)離群點的個數(shù)。

（2）相鄰工件區(qū)域2。相鄰工件區(qū)域存在噪點和兩塊不相連的高密度區(qū)域（見圖5（a）），在搜索區(qū)域內(nèi)的分布特征如圖5（b）所示。

Fig.5 Adjacent workpiece area 2圖5 相鄰工件區(qū)域2

由于工件距離過近，間隙中可能會產(chǎn)生噪點，當(dāng)兩塊工件邊緣的密度較高時噪點密度較低，此時離群點判定可能無法適用?？紤]到DBSCAN 復(fù)雜度較高，當(dāng)離群點判定算法無法識別噪點時，引入DBSCAN 算法根據(jù)密度對點云進行聚類，以此識別分布特征。密度聚類的具體步驟如下：

步驟1：初始化密度聚類閾值e、nth。

步驟2：選取搜索區(qū)域R內(nèi)一點p，以參數(shù)e進行半徑搜索，若n≥nth，將搜索到的點歸入集合Q。

步驟3：在集合Q中選取p以外的點重復(fù)步驟2，直至Q不在滿足條件，保存Q作為相鄰工件區(qū)域1 類的高密度點并清空。

步驟4：在剩余點中重復(fù)步驟2、3。

如圖5（c）所示，密度聚類去除了低密度點云，得到了不同類別不相連的高密度點云，若個數(shù)不少于2，則判定為相鄰工件區(qū)域2。一旦出現(xiàn)如圖5（d）所示情況，搜索區(qū)域R將屬于相鄰工件區(qū)域，由于范圍限制只存在局部信息，只計算相鄰工件區(qū)域1 的高密度點，因此考慮擴展搜索區(qū)域以獲得足夠多的尺度判別特征。當(dāng)搜索區(qū)域R經(jīng)過密度聚類后只存在相鄰工件區(qū)域1 類的高密度點時，擴展搜索區(qū)域的步驟如下：

步驟1：分別求得高密度點云質(zhì)心hc、低密度點云lc。

步驟2：作hc對lc的對稱點kc，并對kc進行半徑為R的鄰近搜索，與區(qū)域R合并得到搜索區(qū)域Rex（見圖5（e））。擴展完成后，對搜索區(qū)域Rex進行密度聚類，獲得正確結(jié)果。

1.2.2 基于相鄰工件區(qū)域識別算法的歐式聚類分割

圖6 為使用傳統(tǒng)歐式聚類方法產(chǎn)生的欠分割和過分割現(xiàn)象。

Fig.6 Results of traditional Euclidean clustering with different distance thresholds圖6 不同距離閾值下傳統(tǒng)歐式聚類結(jié)果

為此，本文對歐式聚類分割進行改進，具體思路為：在點云歐式聚類過程中，使用K 鄰近點確定足夠大的搜索半徑，防止過分割現(xiàn)象發(fā)生；為了使相鄰工件區(qū)域能被正確分割，對每次迭代產(chǎn)生的搜索區(qū)域，通過判定相鄰工件區(qū)域的種類來執(zhí)行不同的聚類方案。當(dāng)識別為相鄰工件區(qū)域1 時，對搜索中心點選擇較小的搜索半徑并聚類；當(dāng)識別為相鄰工件區(qū)域2 時，聚合經(jīng)DBSCAN 分割后搜索中心所在的類。具體步驟如下：

步驟1：對輸入點云Pin建立k-tree 索引。

步驟2：創(chuàng)建點云索引向量S存儲聚類結(jié)果，創(chuàng)建點云索引向量Sdbscan存儲欠分割點云，創(chuàng)建整型向量q存儲單次聚類結(jié)果；新建一個bool 型向量Pprocessed與點云Pin大小數(shù)量相同，以記錄點云是否被處理過。

步驟3：初始化i=0、最小聚類數(shù)nmin、最大聚類數(shù)nmax，對pi∈Pin執(zhí)行以下步驟。

步驟3.1：初始化c=0，將pi的索引放入q，Pprocessed[i]=ture，代表該點已處理。

步驟3.2：取隊列q中的第c個位置儲存點索引，此點在Pin中對于Pc。在k-tree 中，對此點進行k近鄰搜索得到搜索區(qū)域R，將其中k個點放入向量qindice_k，距中心點的距離放入向量qdistence_k。對qindece_k的點云，通過相鄰工件區(qū)域1的識別算法判定區(qū)域R是否為工件相鄰區(qū)域，若判定成功則自適應(yīng)搜索半徑表示為：

反之，自適應(yīng)搜索半徑表示為：

步驟3.3：根據(jù)Rada將點Pc半徑近鄰搜索得到索引放入向量qindece_k，對每一個索引若Pprocessed[qindice_k[i]]=false，將qindice_k[i]放入q并標(biāo)記為已分類，c=c+1。重復(fù)步驟3.2、3.3，直至q中所有點都已分類。q的索引數(shù)為nq，若nq≤nmin則舍棄并清空隊列；若nq≥nmax，將其復(fù)制到Sdbscan并清空隊列；若nmin＜n＜nmax，將q推入S，i=i+1。

步驟4：重復(fù)步驟3，直至Pin中所有點已被處理。

步驟5：創(chuàng)建一個整型向量qdbscan并初始化為空，將Sdbscan中的每組點云索引保存為nm組點云的輸出，記作Cdbm，m=1，2，…，nm。

步驟6：初始化i=0、m=1、數(shù)組q，對pi∈Cdbm執(zhí)行以下步驟。

步驟6.1：初始化d=0，將pi的索引放入qdbscan，Pprocessed[i]=ture，標(biāo)記該點已處理。

步驟6.2：取隊列qdbscan中第d個位置儲存的點索引，此點在Cdbm中對應(yīng)于Pd。在k-tree 中，對此點進行kdb近鄰搜索，得到搜索區(qū)域R，將其中kdb個點放入向量q中，根據(jù)密度聚類算法聚類區(qū)域R，獲得聚類個數(shù)mdb，并將高密度點云聚類結(jié)果放入向量qdbcluster。

步驟6.3：若Pd在qdbcluster中，將qdbcluster保留含有Pd的相鄰工件區(qū)域1 的點云，并放入向量qindice_k。反之，判斷聚類個數(shù)mdb，若mdb=1，獲得擴展后的搜索區(qū)域Rex。對區(qū)域Rex進行密度聚類得到聚類個數(shù)mdb′，當(dāng)mdb′＞1 時清空qindice_k；若mdb＞1 清空qindice_k。對每一個索引，若Pprocessed[qindice_k[i]]=false，將qindice_k放入qdbscan并標(biāo)記為已分類，d=d+1。

步驟6.4：重復(fù)步驟6.2、6.3，直至qdbscan中所有點已分類，將qdbscan推入S，i=i+1。

步驟7：重復(fù)步驟6，直至Cdbm中所有點均已處理，m=m+1。

步驟8：重復(fù)步驟7，直至m＞nm代表歐式聚類完成，將S中每組點云索引保存成z個工件點云進行輸出，記作{P1，P2，…，Pz}。

2 實驗結(jié)果與分析

2.1 工件點云分割結(jié)果

為驗證分割算法的有效性，本文以一組攝像頭模組工件為實驗對象，由于相機視野受限，需要靠近擺放才能容下更多工件。實驗PC 機為64 位的Windows 11 操作系統(tǒng)，CPU 為Intel（R）Core（TM）i7-7950 2.6 GHz，內(nèi)存為16 GB，平臺為64 位的VS 2019，編程語言為C++，涉及庫文件為點云庫PCL1.11.0。預(yù)處理后的點云如圖7（a）所示，然后按照多組工件點云分割方法進行分割，相關(guān)參數(shù)閾值如表1所示。

Table 1 Related parameter thresholds表1 相關(guān)參數(shù)閾值

Fig.7 Recognition and classification results using different algorithms圖7 不同算法識別分類結(jié)果

圖7（彩圖掃OSID 可見，下同）中每種顏色代表不同的類別。圖7（b）中相鄰工件區(qū)域1 判定后的結(jié)果依然存在欠分割現(xiàn)象，圖7（c）為單獨提取出的欠分割部分，圖7（d）為對剩下欠分割部分進行相鄰工件區(qū)域2 判別所得到的聚類結(jié)果，圖7（e）為最終分割結(jié)果。

對相同點云進行預(yù)處理操作后，設(shè)置距離閾值r=0.4進行歐式聚類、曲率閾值為0.1 進行區(qū)域生長聚類、凹面閾值為10 和平滑閾值為0.1 進行局部凸連接生長算法獲得的結(jié)果分別為圖7（f）、圖7（g）、圖7（h）所示。

為定量分析各種方法的分割效果，將分割情況統(tǒng)計匯總為表2。其中，Ideal result 表示理想情況下的分割效果，得到的點數(shù)為nideal；ninliers表示實際分割部分與理想分割的交集點數(shù)；noutliers表示實際分割不在理想分割的部分點數(shù)。

Table 2 Statistics of segmentation results of four methods for single group workpiece point cloud表2 單組工件點云的4種方法的分割結(jié)果統(tǒng)計

2.2 多組工件點云分割

為進一步驗證本文分割算法的有效性，進行多次重復(fù)實驗。實驗對象分別為塑料和金屬材質(zhì)的攝像模組，每種對象獲取3組不同場景下的三維點云數(shù)據(jù)，實驗結(jié)果如表3 所示。其中，2 種實驗對象分別對應(yīng)目標(biāo)1、2，通過A/B/C/D 形式的數(shù)據(jù)記錄4種分割方法的結(jié)果，A 為歐氏聚類分割結(jié)果，B 為區(qū)域生長分割，C 為局部凸連接生長算法，D為本文算法。

Table 3 Comparison of segmentation effect of four methods for multiple groups workpiece point cloud表3 多組工件點云4種方法的分割效果比較

在目標(biāo)數(shù)量相同的條件下，分別記錄4 種算法正確分割的子集個數(shù)、分割正確率AP 和交并比（IoU），用于分析算法性能。當(dāng)某個目標(biāo)交并比大于95%時，判斷為正確分割，IoU 計算公式為：

為了更直觀地展現(xiàn)實驗結(jié)果，圖8 給出2 種實驗對象在場景2中，通過不同算法輸出的圖像。

Fig.8 Classification result of two experimental objects using different algorithms in scenario 2圖8 兩種實驗對象在場景2下不同算法的分類結(jié)果

2.3 實驗結(jié)果

從定性角度而言，對于一些貼合不緊密的工件，使用傳統(tǒng)歐式聚類就能得到較好的分割精度，例如第二種工件的第1、2、3、4、7、8 個工件（見圖7（a）），5、6、9、10 個工件在歐式聚類時存在工件粘連現(xiàn)象，使用局部凸連接生長算法雖然避免了該問題，但工件完整性較差。本文分割方法在工件靠近時，能避免粘連現(xiàn)象且工件完整性較好。從定量角度而言，本文方法的正確率、穩(wěn)定性相較于其他3 種方法更優(yōu)。

3 結(jié)語

本文算法較好地解決了在攝像模組場景下，工件分割發(fā)生的欠分割和過分割問題。在兩種攝像模組的多場景實驗中，本文方法均未出現(xiàn)因工件密度變化而引起過分割，或因多工件靠近引起欠分割現(xiàn)象。

結(jié)果表明，本文算法能準確分割單個工件，精確度高于95%，相較于歐式聚類算法、區(qū)域生長算法、局部凸連接生長算法分別提升54%、41%、33%。