黃際瑋，陸安江*，趙麒，彭熙舜，陳伯云

(1.貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，貴陽(yáng) 550025；2.貴州民族大學(xué)機(jī)械電子工程學(xué)院，貴陽(yáng) 550025)

點(diǎn)云分割[1]是根據(jù)點(diǎn)云的一些特征信息，如位置信息、法向量信息等，將具有共同特征信息的點(diǎn)云劃分到同一類(lèi)，從而方便對(duì)點(diǎn)云進(jìn)行處理。點(diǎn)云分割是點(diǎn)云數(shù)據(jù)處理中重要的步驟之一，點(diǎn)云分割結(jié)果的好壞將會(huì)直接影響到之后特征提取、曲面重建等過(guò)程，因此，點(diǎn)云分割為實(shí)現(xiàn)物體識(shí)別與定位創(chuàng)造了條件。

目前常用的點(diǎn)云分割方法包括：基于聚類(lèi)分割的方法[2]、基于區(qū)域分割的方法[3]、基于模型的方法以及基于邊緣的方法。在基于聚類(lèi)分割的方法中，歐式聚類(lèi)分割的方法[4]最為常用，其分割步驟為：先選取種子點(diǎn)，對(duì)種子點(diǎn)進(jìn)行鄰域搜索，如果在鄰域內(nèi)發(fā)現(xiàn)了其他的點(diǎn)，就將它們與種子點(diǎn)劃分為同一聚類(lèi)簇，然后在聚類(lèi)簇中選擇新的種子點(diǎn)進(jìn)行搜索，若聚類(lèi)簇中的點(diǎn)不再增加，那么就完成了一次聚類(lèi)，之后在剩余的點(diǎn)云中選取新的種子點(diǎn)，重復(fù)執(zhí)行之前的步驟，直到遍歷點(diǎn)云中所有的點(diǎn)。歐式聚類(lèi)分割方法因其分割效率高、穩(wěn)健性好等優(yōu)點(diǎn)，在實(shí)際應(yīng)用中常常受到青睞。徐濤等[5]通過(guò)利用歐式聚類(lèi)分割加上對(duì)Z軸的約束實(shí)現(xiàn)了蔬菜大棚雜草識(shí)別。田青華等[6]提出先去出邊緣點(diǎn)，再聚類(lèi)分割，最后補(bǔ)齊邊緣點(diǎn)的思想，相較于傳統(tǒng)歐式聚類(lèi)算法，準(zhǔn)確性提高了64.26%，速度提高了24.5%。梁雪[7]提出了基于超體素的散亂零件點(diǎn)云分割方法，將零件點(diǎn)云分割為超體素過(guò)分割和超體素區(qū)域增長(zhǎng)兩個(gè)過(guò)程，成功實(shí)現(xiàn)散亂堆放零件的分割過(guò)程。在基于區(qū)域分割的方法中，劉瑋等[8]提出一種改進(jìn)的區(qū)域生長(zhǎng)算法用于解決重疊分割問(wèn)題，相較于傳統(tǒng)區(qū)域生長(zhǎng)算法，分割正確率提高了24.9%。薛婧雅等[9]提出一種基于超體素與區(qū)域生長(zhǎng)的機(jī)載點(diǎn)云屋頂平面分割方法，通過(guò)超體素方法將點(diǎn)云分為初始平面片集合，然后通過(guò)區(qū)域生長(zhǎng)算法對(duì)平面片進(jìn)行聚類(lèi)得到初始平面。史洪云等[10]提出一種基于空間約束的區(qū)域增長(zhǎng)算法，對(duì)電力線點(diǎn)云2個(gè)空間約束條件進(jìn)行公式化表達(dá)后,以此作為生長(zhǎng)準(zhǔn)則對(duì)電力線點(diǎn)云進(jìn)行區(qū)域生長(zhǎng),實(shí)現(xiàn)單根電力線分割。

在一般場(chǎng)景下，歐式聚類(lèi)分割方法能達(dá)到理想的效果，但是對(duì)于一些特殊場(chǎng)景，如工件之間靠得太近甚至緊貼在一起，僅僅利用歐式聚類(lèi)分割的方法不能把這些工件有效地分割出來(lái)。因此，針對(duì)實(shí)際場(chǎng)景中出現(xiàn)的工件粘連的情況，現(xiàn)提出一種結(jié)合歐式聚類(lèi)和自適應(yīng)法向量約束的工件分割方法。首先對(duì)點(diǎn)云進(jìn)行預(yù)處理，去除環(huán)境噪聲與背景，接著采用歐式聚類(lèi)分割算法將工件分割成點(diǎn)云簇，對(duì)于點(diǎn)云簇中工件粘連的情況，利用區(qū)域生長(zhǎng)算法設(shè)置不同的法向量閾值并進(jìn)行分割，最終完成工件點(diǎn)云的分割，以期為后續(xù)的工件點(diǎn)云識(shí)別奠定基礎(chǔ)。

1 數(shù)據(jù)處理流程

實(shí)驗(yàn)數(shù)據(jù)選用無(wú)錫微視傳感科技有限公司研制的型號(hào)PCA-P/S600的3D相機(jī)獲取，如圖1所示，該相機(jī)采用微機(jī)電系統(tǒng)(micro-electro-mechanical system，MEMS)編碼光柵結(jié)構(gòu)光進(jìn)行掃描，可以根據(jù)圖像恢復(fù)算法重建出物體的真實(shí)三維點(diǎn)云數(shù)據(jù)，光源為近紅外激光，采用單目結(jié)構(gòu)光原理，工作距離為300～600 mm，可應(yīng)用于生物識(shí)別、工業(yè)自動(dòng)化、機(jī)器人、三維重建等場(chǎng)景。其規(guī)格參數(shù)如表1所示。

表1 PCA-P/S600 3D相機(jī)參數(shù)

圖1 PCA-P/S600 3D相機(jī)

結(jié)合歐式聚類(lèi)和自適應(yīng)法向量約束的工件分割方法的流程如圖2所示，主要包含點(diǎn)云預(yù)處理、生成點(diǎn)云簇和自適應(yīng)法向量約束三個(gè)步驟。首先通過(guò)點(diǎn)云預(yù)處理去除噪聲與試驗(yàn)臺(tái)背景，保留工件點(diǎn)云。然后利用歐式聚類(lèi)分割方法把工件劃分成點(diǎn)云簇。最后針對(duì)點(diǎn)云簇中存在多個(gè)工件的情況，求出其平均法向量，將平均法向量結(jié)果代入?yún)^(qū)域生長(zhǎng)算法進(jìn)行分割，完成最終的工件分割。

圖2 總體分割流程

2 分割原理

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

通過(guò)3D相機(jī)得到包含試驗(yàn)臺(tái)在內(nèi)的大量點(diǎn)云，且受到實(shí)際環(huán)境因素的影響，不可避免地會(huì)產(chǎn)生噪聲[11]，所以在對(duì)點(diǎn)云進(jìn)行分割之前，需要對(duì)采集到的點(diǎn)云進(jìn)行預(yù)處理。為了提高后續(xù)對(duì)點(diǎn)云分割的效率，需要先利用體素濾波器對(duì)相機(jī)采集到的點(diǎn)云進(jìn)行下采樣，該方法能夠在保持點(diǎn)云特征的前提下對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行精簡(jiǎn)，提高后續(xù)對(duì)點(diǎn)云的處理速度。隨機(jī)采樣一致性(RANSAC)算法[12]采用迭代的方式從一組包含離群的被觀測(cè)數(shù)據(jù)中估算出數(shù)學(xué)模型的參數(shù)，由于采集到的點(diǎn)云包含了試驗(yàn)臺(tái)背景，這會(huì)影響到后續(xù)對(duì)工件的分割效果，所以采用隨機(jī)采樣一致性算法濾除試驗(yàn)臺(tái)背景。經(jīng)過(guò)前兩步的處理，大量的無(wú)關(guān)點(diǎn)云已經(jīng)被濾除，但是仍然存在一些稀疏點(diǎn)云，原因是無(wú)法完全地去除背景且采集數(shù)據(jù)時(shí)不可避免地存在噪聲，對(duì)于這些離散的點(diǎn)云，根據(jù)噪點(diǎn)的特征可以通過(guò)統(tǒng)計(jì)濾波器[13]對(duì)它們進(jìn)行濾波處理。預(yù)處理前后得到的點(diǎn)云如圖3所示，預(yù)處理前后的點(diǎn)云數(shù)量如表2所示，可以看到，大量的無(wú)關(guān)點(diǎn)云已經(jīng)被濾除，只剩下工件點(diǎn)云。

圖3 預(yù)處理示意圖

表2 點(diǎn)云預(yù)處理階段點(diǎn)云數(shù)量

2.2 生成點(diǎn)云簇

原始點(diǎn)云經(jīng)過(guò)預(yù)處理之后，大量的無(wú)關(guān)的點(diǎn)云已經(jīng)基本被濾除，只留下了工件點(diǎn)云，此時(shí)可以使用歐式聚類(lèi)分割算法將工件點(diǎn)云劃分成點(diǎn)云簇。歐式聚類(lèi)分割算法是一種基于歐式距離度量的聚類(lèi)方法[14]，在三維空間中的兩點(diǎn)(x1,y1,z1)與(x2,y2,z2)的歐式距離定義為

(1)

歐式聚類(lèi)分割算法的步驟如圖4所示，主要經(jīng)過(guò)以下幾個(gè)步驟。

圖4 歐式聚類(lèi)分割算法流程

步驟1對(duì)于空間中的某一點(diǎn)M，通過(guò)KD-Tree近鄰搜索算法找到k個(gè)離點(diǎn)M最近的點(diǎn){m1,m2,…,mk}，判斷這k個(gè)點(diǎn)到點(diǎn)M的距離，將距離小于閾值r的點(diǎn)m1,m2,…,m10,…,存放在集合Q中。

步驟2在集合Q中尋找除M外的另一點(diǎn)，重復(fù)步驟1。

步驟3依次遍歷集合Q中所有的點(diǎn)，重復(fù)上述步驟，直到Q中沒(méi)有新的點(diǎn)加入，則完成一次聚類(lèi)。

2.3 自適應(yīng)法向量約束

經(jīng)過(guò)歐式聚類(lèi)分割后的點(diǎn)云簇中會(huì)出現(xiàn)包含多個(gè)工件的情況，這是因?yàn)楣ぜg距離太近甚至貼合在一起，僅僅使用歐式聚類(lèi)分割算法無(wú)法將它們完全分割，為了解決這個(gè)問(wèn)題，引入自適應(yīng)法向量約束的方法，先求出點(diǎn)云簇的平均法向量，然后使用區(qū)域生長(zhǎng)算法[15]對(duì)不同的點(diǎn)云簇設(shè)置不同的法向量進(jìn)行約束并分割，主要過(guò)程如下。

步驟1對(duì)于某一個(gè)點(diǎn)云簇，根據(jù)近鄰關(guān)系與法向量求出其平均法向量V。

步驟2依據(jù)曲率對(duì)點(diǎn)云簇中的點(diǎn)進(jìn)行排序，并設(shè)置一空的種子點(diǎn)序列Z與一空的聚類(lèi)數(shù)組L。

步驟3將曲率最小的點(diǎn)加入種子點(diǎn)序列Z，從種子點(diǎn)序列Z中拿出一個(gè)種子點(diǎn)并搜索其鄰域。

步驟4比較鄰域點(diǎn)的法線與當(dāng)前種子點(diǎn)之間的夾角θ，若小于法向量角度閾值，將鄰域點(diǎn)加入聚類(lèi)數(shù)組L，其中閾值設(shè)置為平均法向量V。

步驟5從聚類(lèi)數(shù)組中檢查是否存在小于曲率閾值的點(diǎn)，若存在，則加入種子點(diǎn)序列。

步驟6刪除用過(guò)的種子點(diǎn)，用下一個(gè)種子點(diǎn)重復(fù)步驟3、步驟4，直到種子點(diǎn)被清空。

步驟7從曲率排序的點(diǎn)中，即曲率從小到大的順序選取聚類(lèi)數(shù)組中沒(méi)有的點(diǎn)作為種子點(diǎn)，重復(fù)步驟2～步驟6。

其中，法向量的估計(jì)[16]流程如圖5所示。

圖5 法向量估計(jì)流程

對(duì)于點(diǎn)云中的每一個(gè)數(shù)據(jù)點(diǎn)pi通過(guò)K鄰域算法計(jì)算出與其相鄰的k個(gè)鄰近點(diǎn)，針對(duì)這些點(diǎn)計(jì)算出一個(gè)最小二乘意義上的局部平面，計(jì)算公式為

(2)

式(2)中：n為局部平面P的法向量；d為局部平面P到坐標(biāo)原點(diǎn)的距離。

通過(guò)式(2)可知，局部平面P經(jīng)過(guò)k個(gè)鄰域點(diǎn)的質(zhì)心，法向量n滿(mǎn)足‖n‖2=1，所以上述問(wèn)題可以轉(zhuǎn)化為求解方差矩陣的特征值，分析協(xié)方差矩陣A的最小特征值所對(duì)于的特征向量，此小特征向量即為平面P的法向量。其中，協(xié)方差矩陣A的計(jì)算公式為

(3)

擬合平面P在滿(mǎn)足鄰域點(diǎn)到平面距離平方和最小的條件下，依據(jù)拉格朗日定理，解算出協(xié)方差矩陣A和平面法向量n滿(mǎn)足如下關(guān)系:

An=λn

(4)

式(4)中：λ為矩陣A的特征值；當(dāng)λ取最小值時(shí)，對(duì)應(yīng)的向量n就是擬合平面P的法向量，即pi點(diǎn)的法向量。

平均法向量的計(jì)算方法為：首先計(jì)算出對(duì)于點(diǎn)云簇中某點(diǎn)q鄰域內(nèi)的所有鄰近點(diǎn)法線夾角的均值αi：

(5)

式(5)中：k為鄰近點(diǎn)數(shù)目；vi為點(diǎn)q的法線；q點(diǎn)的鄰近點(diǎn)對(duì)應(yīng)法線分別為{vi1,vi2,…,vij}。

接著遍歷點(diǎn)云中所有的點(diǎn)得到N個(gè)鄰近點(diǎn)數(shù)目，求出整個(gè)點(diǎn)云簇中的平均法向量α：

(6)

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)數(shù)據(jù)包含工件與試驗(yàn)臺(tái)背景，其中工件是尺寸為6.0 mm×8.0 mm×4.0 mm的電容，如圖6所示，實(shí)驗(yàn)所用的計(jì)算機(jī)為64位的Windows10操作系統(tǒng)，配置為AMD Ryzen 54600H CPU@3.0GHz，16.00 GB內(nèi)存，應(yīng)用Visual Studio 2017編程環(huán)境，配合點(diǎn)云庫(kù)(PCL)1.8.1使用。

圖6 電容實(shí)物

經(jīng)過(guò)歐式聚類(lèi)分割后的工件點(diǎn)云簇中，含有多個(gè)工件的點(diǎn)云簇如圖7所示。對(duì)以上點(diǎn)云簇進(jìn)行法向量自適應(yīng)約束，計(jì)算出每一個(gè)點(diǎn)云簇的平均法向量，如表3所示。

表3 不同點(diǎn)云簇平均的平均法向量

圖7 含多個(gè)工件的點(diǎn)云簇

對(duì)每個(gè)點(diǎn)云簇使用區(qū)域生長(zhǎng)算法進(jìn)行分割，并設(shè)置不同的法向量進(jìn)行約束，得到的分割結(jié)果如圖8所示。分割時(shí)標(biāo)注的顏色是隨機(jī)產(chǎn)生的，每一種顏色代表一類(lèi)點(diǎn)云，在工件的連接處存在著紅色的點(diǎn)云，這代表著連接的工件已經(jīng)被分割出來(lái)。提取出紅色點(diǎn)云后，得到最終分割結(jié)果。每個(gè)點(diǎn)云簇分割前后的點(diǎn)云數(shù)量如表4所示，每個(gè)點(diǎn)云簇分割出的點(diǎn)云類(lèi)型及每個(gè)類(lèi)型的點(diǎn)云數(shù)量如圖9所示。

圖8 法向量自適應(yīng)約束后的點(diǎn)云簇

圖9 最終分割點(diǎn)云數(shù)量

表4 點(diǎn)云簇分割前點(diǎn)云數(shù)量

而使用傳統(tǒng)的區(qū)域生長(zhǎng)算法分割后得到的點(diǎn)云如圖10所示?？梢钥吹剑瑢?duì)于一些貼合不太緊密的工件來(lái)說(shuō)，可以使用傳統(tǒng)的區(qū)域生長(zhǎng)算法分割來(lái)達(dá)到理想的分割效果，但是對(duì)于接觸相對(duì)緊密的工件，該方法就不能將它們完全地分割。為了定量分析本文提出的算法精確度，分別使用歐式聚類(lèi)算法、區(qū)域生長(zhǎng)算法和本文算法對(duì)兩組數(shù)據(jù)進(jìn)行分割對(duì)比，得到的分割精度如表5所示。

表5 不同算法分割精度對(duì)比

圖10 傳統(tǒng)區(qū)域生長(zhǎng)算法分割結(jié)果

利用本文提出的結(jié)合歐式聚類(lèi)與自適應(yīng)法向量約束的分割方法能比較靈活地提取出點(diǎn)云的邊界信息，利用這些信息對(duì)點(diǎn)云實(shí)現(xiàn)更精確地分割，彌補(bǔ)了使用傳統(tǒng)算法出現(xiàn)的過(guò)分割和欠分割的缺陷，從而得到更好的分割效果。

4 結(jié)論

以小型電容為研究對(duì)象，應(yīng)用3D相機(jī)對(duì)其生成的點(diǎn)云進(jìn)行分割研究，得出如下結(jié)論。

(1)相對(duì)于傳統(tǒng)相機(jī)，采用基于MEMS編碼光柵結(jié)構(gòu)光的3D相機(jī)能夠方便快速地采集工件點(diǎn)云數(shù)據(jù)，在提高效率的同時(shí)保證了數(shù)據(jù)的精度。

(2)根據(jù)點(diǎn)云的分布特征，通過(guò)體素濾波、隨機(jī)采樣一致性去平面、統(tǒng)計(jì)濾波去噪聲的濾波順序有效地提取出工件點(diǎn)云，為后續(xù)工件點(diǎn)云分割提供了條件。

(3)針對(duì)工件點(diǎn)云分割提出了分割精度更高的算法，有效解決了傳統(tǒng)的歐式聚類(lèi)算法及區(qū)域生長(zhǎng)算法中出現(xiàn)的過(guò)分割以及欠分割的問(wèn)題。

結(jié)果表明，本文提出的分割算法分割準(zhǔn)確度得到有效提升，分割效果顯著增強(qiáng)。在此基礎(chǔ)上，下一步工作的重點(diǎn)是如何實(shí)現(xiàn)將重疊的工件點(diǎn)云進(jìn)行有效地分割。