姜立豪，劉星橋，李長(zhǎng)峰，陳 輝，馬 騰，趙德安

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

0 引言

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

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

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

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

1 基本原理

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

Fig.1 Algorithm flow圖1 算法流程

1.1 點(diǎn)云預(yù)處理

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

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

1.2 改進(jìn)歐式聚類分割

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟1：對(duì)輸入點(diǎn)云Pin建立k-tree 索引。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

2.2 多組工件點(diǎn)云分割

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

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

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

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

Fig.8 Classification result of two experimental objects using different algorithms in scenario 2圖8 兩種實(shí)驗(yàn)對(duì)象在場(chǎng)景2下不同算法的分類結(jié)果

2.3 實(shí)驗(yàn)結(jié)果

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

3 結(jié)語

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

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