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

(1.長(zhǎng)春工業(yè)大學(xué)電氣與電子工程學(xué)院， 長(zhǎng)春 130012; 2.長(zhǎng)春一汽國(guó)際物流有限公司， 長(zhǎng)春 130000)

近年來(lái)，點(diǎn)云處理技術(shù)逐漸應(yīng)用在非結(jié)構(gòu)環(huán)境下的目標(biāo)零件識(shí)別領(lǐng)域[1]。非結(jié)構(gòu)環(huán)境，即環(huán)境信息未知、不固定，且存在零件雜亂擺放相互堆疊、連接的情況。如何將單個(gè)零件從復(fù)雜背景中準(zhǔn)確地分割出來(lái)，依舊是點(diǎn)云處理過(guò)程中待解決的難題。點(diǎn)云分割結(jié)果的好壞，將直接影響后續(xù)目標(biāo)識(shí)別的精確度[2]。

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

根據(jù)環(huán)境中存在零件無(wú)序擺放的情況，選擇基于區(qū)域的分割算法進(jìn)行點(diǎn)云分割。在傳統(tǒng)區(qū)域生長(zhǎng)中通常采用隨機(jī)抽樣一致性算法獲取初始種子點(diǎn)，但該方法只有一定概率能夠獲得可信的模型，容易出現(xiàn)分割不穩(wěn)定的現(xiàn)象[11]。因此，針對(duì)傳統(tǒng)算法的不足進(jìn)行改進(jìn)，通過(guò)計(jì)算點(diǎn)云曲率，將曲率最小點(diǎn)設(shè)置為初始種子點(diǎn)，再根據(jù)位置信息設(shè)定空間閾值范圍進(jìn)行區(qū)域生長(zhǎng)，提高了點(diǎn)云分割的穩(wěn)定性和準(zhǔn)確性，同時(shí)兼顧了分割效率，為后續(xù)的目標(biāo)識(shí)別過(guò)程奠定基礎(chǔ)。

1 算法原理

非結(jié)構(gòu)環(huán)境下，改進(jìn)的區(qū)域生長(zhǎng)點(diǎn)云分割方法主要流程包括：點(diǎn)云預(yù)處理、建立點(diǎn)云拓?fù)潢P(guān)系以及改進(jìn)區(qū)域生長(zhǎng)算法，如圖1所示。

圖1 改進(jìn)的區(qū)域生長(zhǎng)點(diǎn)云分割算法流程圖Fig.1 A flow chart of the improved segmentation algorithm for regional growing point cloud

1.1 數(shù)據(jù)獲取

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

點(diǎn)云預(yù)處理步驟如下。

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

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

(3)使用Statistical Outlier Removal濾波器來(lái)剔除離群點(diǎn)或拍攝導(dǎo)致的誤差點(diǎn)。

通過(guò)以上點(diǎn)云預(yù)處理過(guò)程進(jìn)行噪聲去除，以圖2(b)初始點(diǎn)云(共661 522個(gè)點(diǎn))為例進(jìn)行實(shí)驗(yàn)，圖2(f)為預(yù)處理完成后的點(diǎn)云(共113 708個(gè)點(diǎn))。點(diǎn)云精簡(jiǎn)率高達(dá)82.8%，實(shí)驗(yàn)結(jié)果如圖2所示。由此可見(jiàn)，該預(yù)處理過(guò)程能夠有效去除冗余點(diǎn)及離散點(diǎn)。

圖2 預(yù)處理示意圖Fig.2 Preprocessing schematic

1.2 建立點(diǎn)云拓?fù)潢P(guān)系

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

圖3 八叉樹(shù)層級(jí)結(jié)構(gòu)圖Fig.3 Octree hierarchy diagram

圖4 八叉樹(shù)空間結(jié)構(gòu)圖Fig.4 Octree space structure diagram

(1)首先，依據(jù)點(diǎn)云數(shù)據(jù)模型的最小空間包圍盒確立八叉樹(shù)根節(jié)點(diǎn)。

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

(3)最后，對(duì)所有根節(jié)點(diǎn)以及子節(jié)點(diǎn)進(jìn)行遞歸劃分，直到小立方體邊長(zhǎng)滿足所設(shè)置的閾值時(shí)停止劃分。

通過(guò)以上步驟能夠?qū)c(diǎn)云進(jìn)行區(qū)域劃分，為后續(xù)的點(diǎn)云分割提供了便利。

1.3 改進(jìn)區(qū)域生長(zhǎng)算法

在完成點(diǎn)云拓?fù)潢P(guān)系建立后，使用區(qū)域生長(zhǎng)算法進(jìn)行點(diǎn)云分割。首先，設(shè)定有效的生長(zhǎng)準(zhǔn)則。其次，選定某一個(gè)數(shù)據(jù)點(diǎn)作為生長(zhǎng)的初始種子點(diǎn)，將點(diǎn)集中具有相似幾何特征的數(shù)據(jù)點(diǎn)劃分到一個(gè)區(qū)域，再判斷該區(qū)域中鄰近點(diǎn)的選取是否符合設(shè)定的生長(zhǎng)準(zhǔn)則。最終，在所有滿足閾值條件的鄰近點(diǎn)都加入到種子區(qū)域后，停止生長(zhǎng)。

該算法的分割結(jié)果在很大程度上取決于初始種子點(diǎn)的選取。當(dāng)前，傳統(tǒng)區(qū)域生長(zhǎng)算法在進(jìn)行點(diǎn)云分割時(shí)通常采用RANSAC(random sample consensus)算法[15]獲取初始種子點(diǎn)，但容易出現(xiàn)分割不穩(wěn)定的現(xiàn)象。為了克服該缺陷，提出一種改進(jìn)的區(qū)域生長(zhǎng)算法來(lái)進(jìn)行點(diǎn)云分割。該算法用于解決重疊分割問(wèn)題，通過(guò)減少區(qū)段總數(shù)，從而提高點(diǎn)云分割效率。將曲率最小點(diǎn)設(shè)置為初始種子點(diǎn)，即選擇所在平面最平滑的部分開(kāi)始生長(zhǎng)。

在進(jìn)行點(diǎn)云曲率計(jì)算時(shí)，常見(jiàn)的方法有主成分分析(principal component analysis，PCA)法以及最小二乘法等。由于PCA方法對(duì)點(diǎn)云曲率的計(jì)算較為粗略，而最小二乘法計(jì)算曲率較為煩瑣。綜上考慮，選取一種基于局部徑向基函數(shù)(radical basis function，RBF)的點(diǎn)云曲率計(jì)算方法，構(gòu)建完整的隱式曲面，再根據(jù)曲率的微分幾何性質(zhì)來(lái)進(jìn)行計(jì)算?；赗BF構(gòu)建的隱式曲面光滑性、延續(xù)性較好，且該方法穩(wěn)定性高，魯棒性強(qiáng)。

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

(1)

式(1)中：r為插值約束點(diǎn)，即構(gòu)造隱式曲面的隨意雜亂點(diǎn)；pj為構(gòu)造隱式曲面時(shí)的目標(biāo)點(diǎn)；ωj為對(duì)應(yīng)目標(biāo)點(diǎn)的徑向基權(quán)值；P(r)即一次多項(xiàng)式，對(duì)隨機(jī)一點(diǎn)(x,y,z)，P(r)=a0+a1x+a2y+a3z；φ(r-pj)為徑向基函數(shù)，通常的表示方式為φ(x)=|x|3。

由給定的n個(gè)散亂點(diǎn)確定約束條件為

i=1,2,…,n

(2)

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

(3)

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

(4)

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

f(x,y,z)=

(5)

由隱式曲面的曲率性質(zhì)計(jì)算其曲率，并將其近似為目標(biāo)點(diǎn)的曲率值。并從中選擇曲率最小的點(diǎn)進(jìn)行生長(zhǎng)。對(duì)需要進(jìn)行分割每個(gè)點(diǎn)的曲率進(jìn)行計(jì)算并排序，隱式曲面任一點(diǎn)Q的曲率K為

(6)

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

(7)

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

改進(jìn)區(qū)域生長(zhǎng)算法的具體步驟如下。

(1)首先對(duì)每個(gè)點(diǎn)的曲率進(jìn)行計(jì)算，再依據(jù)大小值排列順序，選擇曲率最小點(diǎn)為初始種子點(diǎn)進(jìn)行生長(zhǎng)。

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

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

(4)刪除當(dāng)前種子點(diǎn)，利用新加入的種子點(diǎn)繼續(xù)生長(zhǎng)，循環(huán)執(zhí)行步驟(2)和(3)，直到種子集合為空。

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

2.1 實(shí)驗(yàn)平臺(tái)設(shè)計(jì)

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

圖5 實(shí)驗(yàn)平臺(tái)裝置圖Fig.5 Device diagram of experimental platform

數(shù)字表示點(diǎn)云子集圖6 三種算法不同場(chǎng)景下分割結(jié)果圖Fig.6 Segmentation results of the three algorithms in different scenes

2.2 對(duì)比實(shí)驗(yàn)

區(qū)域生長(zhǎng)算法的原理是將符合約束條件并具有類似特征的點(diǎn)聚在一起。因此，分割的結(jié)果為一系列點(diǎn)云子集，具有相同顏色的點(diǎn)云子集表示為一類。圖6中對(duì)場(chǎng)景一和場(chǎng)景二，分別使用DBSCAN聚類算法、傳統(tǒng)區(qū)域生長(zhǎng)算法以及改進(jìn)的區(qū)域生長(zhǎng)算法，對(duì)完成預(yù)處理以及拓?fù)浣Y(jié)構(gòu)建立的點(diǎn)云數(shù)據(jù)進(jìn)行分割。

在給定目標(biāo)子集個(gè)數(shù)相同的情況下，分別記錄三種算法分割出的子集個(gè)數(shù)、正確分割的子集個(gè)數(shù)。如表1所示。

表1 三種算法分割效果對(duì)比表

其次，為了評(píng)估算法的效果，采用以下定量指標(biāo)進(jìn)行分析：分割正確率Rs以及算法耗時(shí)，用于本文算法的性能分析。在理想分割中，屬于一個(gè)類別的點(diǎn)將在同一點(diǎn)云子集中，但由于噪聲和其他環(huán)境因素影響，一些點(diǎn)集沒(méi)有被正確分割。

第一個(gè)評(píng)價(jià)指標(biāo)Rs，即分割正確率計(jì)算公式為

(8)

式(8)中：Ns為正確分割的點(diǎn)云子集個(gè)數(shù)；N為分割子集個(gè)數(shù)。

第二個(gè)評(píng)價(jià)指標(biāo)為算法耗時(shí)，通過(guò)記錄各算法運(yùn)行時(shí)間表示該指標(biāo)。如表2所示。

表2 三種算法分割效果對(duì)比表

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

(1)在目標(biāo)零件個(gè)數(shù)相同的情況下，相比于傳統(tǒng)的區(qū)域生長(zhǎng)算法，本文算法能更加準(zhǔn)確地分割出目標(biāo)零件子集。表1中對(duì)場(chǎng)景一的結(jié)果進(jìn)行顯示，傳統(tǒng)區(qū)域生長(zhǎng)算法共分割出6個(gè)點(diǎn)云子集，其中4個(gè)點(diǎn)云子集為正確的子集，出現(xiàn)了欠分割現(xiàn)象。而本文算法共分割出12個(gè)子集，其中11個(gè)為正確分割子集，未出現(xiàn)明顯的欠分割現(xiàn)象。本文相較于傳統(tǒng)區(qū)域生長(zhǎng)算法，分割正確率提高了24.9%。

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

3 結(jié)論

提出了一種非結(jié)構(gòu)環(huán)境下改進(jìn)區(qū)域生長(zhǎng)的點(diǎn)云分割方法，用來(lái)解決點(diǎn)云分割中零件相互堆疊的情況。首先，采用直通濾波和統(tǒng)計(jì)濾波的方法進(jìn)行離散點(diǎn)以及冗余點(diǎn)的去除，方便后續(xù)數(shù)據(jù)的處理；其次，使用八叉樹(shù)建立點(diǎn)云之間的拓?fù)浣Y(jié)構(gòu)，提高點(diǎn)云分割的效率；最后，通過(guò)改進(jìn)的區(qū)域生長(zhǎng)算法，選擇基于局部徑向基函數(shù)的曲率計(jì)算方法，選取曲率最小點(diǎn)為初始種子點(diǎn)，并設(shè)定空間閾值范圍進(jìn)行區(qū)域生長(zhǎng)。由此提高了無(wú)序環(huán)境下點(diǎn)云分割的正確性和效率。實(shí)驗(yàn)結(jié)果表明，本文提出的算法對(duì)于相互堆疊的零件點(diǎn)云，分割正確率提高了24.9%，速度提高了12.5%。