散貨料堆快速點(diǎn)云分割和降噪算法研究

韓曉龍 王為民 金 鑫 楊志遠(yuǎn) 王貢獻(xiàn)

1 青島港口裝備制造有限公司 2 武漢理工大學(xué)交通與物流工程學(xué)院

1 引言

自經(jīng)濟(jì)全球化以來，我國進(jìn)出口貿(mào)易日益繁榮，散裝貨物的運(yùn)輸量也逐年遞增，加強(qiáng)散貨碼頭堆取料作業(yè)自動(dòng)化建設(shè)，提高散貨碼頭運(yùn)輸效率迫在眉睫。三維重構(gòu)技術(shù)可獲取料堆表面位置信息，以位置信息作為自動(dòng)控制指令依據(jù)是實(shí)現(xiàn)散貨堆場(chǎng)自動(dòng)化的關(guān)鍵。散貨料堆的三維重構(gòu)通常是通過傳感設(shè)備采集料堆表面點(diǎn)云，然后對(duì)點(diǎn)云進(jìn)行三維建模來實(shí)現(xiàn)，但在點(diǎn)云采集中會(huì)由于設(shè)備、工作環(huán)境等因素引入一些噪聲點(diǎn)和地面干擾點(diǎn)云，因此需要對(duì)散貨料堆點(diǎn)云進(jìn)行降噪和分割地面處理。

目前針對(duì)點(diǎn)云分割和降噪的研究有很多，其中點(diǎn)云分割方法可分為基于邊緣分割[1-2]、基于特征聚類分割[3-4]和基于隨機(jī)采樣一致性(RANSAC)分割[5-7]。Woo等用法向量偏差細(xì)分網(wǎng)格作為特征描述，提取物體邊緣相鄰點(diǎn)[1]。莫堃等通過構(gòu)造符號(hào)距離函數(shù)估算點(diǎn)云的平均曲率值，實(shí)現(xiàn)點(diǎn)云模型快速分割[2]。Yamauchi等采用均值平移法對(duì)網(wǎng)格法線進(jìn)行聚類分割[3]。吳燕雄等在歐式聚類算法基礎(chǔ)上增加平滑度約束，加快了算法分割速度[4]。RANSAC(Random Sample Consensus)算法于1981年由Fischler和Bolles提出[5]。Awwad等基于隨機(jī)采樣一致性算法提出Seq-NV-RANSAC分割算法，解決隨機(jī)采樣一致性算法可能檢測(cè)到虛假平面的問題[6]。劉闖等用法向量夾角為約束條件對(duì)點(diǎn)云進(jìn)行分類，再結(jié)合RANSAC分割算法完成點(diǎn)云的分割[7]。

在點(diǎn)云降噪研究方面，Zhang等通過對(duì)空間域和特征域的權(quán)值調(diào)整控制點(diǎn)云的平滑程度和特征保持程度，具有較好的降噪效果，但是不能很好地去除離散點(diǎn)[8]。肖國新等在雙邊濾波基礎(chǔ)上提出自適應(yīng)空間方差和灰度方差參數(shù)的濾波算法，保留了更多的邊緣特征[9]。Taubin等首次將Laplacian算法應(yīng)用到網(wǎng)格處理中[10]。Lange等在前者的基礎(chǔ)上提出各向異性幾何平均曲率流降噪方法[11]。孫正林等改進(jìn)Mean Shift算法，提高移動(dòng)到核密度估計(jì)函數(shù)的最大值點(diǎn)的速度[12]。Alexa等運(yùn)用移動(dòng)最小二乘法(Moving Least Squares,MLS)擬合曲面，光滑點(diǎn)云[13]。Jia等針對(duì)目前市場(chǎng)流行的RGB-D相機(jī)，提出一種將彩色圖像與深度圖像對(duì)齊去除離散噪聲點(diǎn)的方法[14]。

2 散貨料堆地面分割和降噪算法

算法框架見圖1。首先利用下采樣算法精簡散貨料堆點(diǎn)云數(shù)目，加快點(diǎn)云后續(xù)處理速度；再結(jié)合基于采樣一致性(RANSAC)分割算法與歐式聚類分割算法彌補(bǔ)了前者分割不徹底、后者速度慢的問題；最后結(jié)合統(tǒng)計(jì)分析法和移動(dòng)最小二乘法去除離散點(diǎn)和點(diǎn)云表面細(xì)小噪聲點(diǎn)。

圖1 散貨料堆提取與濾波算法過程

2.1 地面分割

下采樣算法原理如下：首先對(duì)整幅點(diǎn)云進(jìn)行柵格劃分，劃分后的每個(gè)小立方體稱為體素，將體素中所有的點(diǎn)由重心點(diǎn)代替，刪除其他點(diǎn)完成點(diǎn)云精簡。

隨機(jī)采樣一致性算法(RANSAC)將點(diǎn)云看作一個(gè)樣本集合，并設(shè)定一個(gè)判斷準(zhǔn)則，根據(jù)判斷準(zhǔn)則將整個(gè)點(diǎn)集合分為局內(nèi)點(diǎn)(inliers)和局外點(diǎn)(outliers)。其分割地面的具體步驟如下：

(1)從樣本集合中隨機(jī)選取1個(gè)子集，把子集中的點(diǎn)設(shè)為局內(nèi)點(diǎn)。

(2)使用估計(jì)算法計(jì)算此局內(nèi)點(diǎn)的模型參數(shù)，然后計(jì)算其他子集與這個(gè)數(shù)學(xué)模型的偏差。三維空間中的地面模型可由式(1)表示：

axw+byw+czw+d=0

(1)

偏差用點(diǎn)q(xw,yw,zw)到平面的歐式距離D表示。根據(jù)實(shí)際需求設(shè)定1個(gè)偏差閾值σ，當(dāng)偏差D小于閾值σ時(shí)，將該樣本點(diǎn)歸于局內(nèi)點(diǎn)，否則歸于局外點(diǎn)。

(3)記錄當(dāng)前局內(nèi)點(diǎn)的個(gè)數(shù)，如果個(gè)數(shù)足夠多就認(rèn)為模型足夠合理；把當(dāng)前局內(nèi)點(diǎn)作為初始選取的子集，重復(fù)上述步驟不斷擴(kuò)充模型。

(4)最后，通過估計(jì)局內(nèi)點(diǎn)個(gè)數(shù)與模型的錯(cuò)誤率來評(píng)估模型。整個(gè)過程記作一次迭代，每次迭代都選擇更優(yōu)的模型。算法迭代次數(shù)k可以根據(jù)式(2)計(jì)算獲得：

1-p=(1-wn)k

(2)

對(duì)式(2)兩邊取對(duì)數(shù)，得

(3)

式中，p為算法產(chǎn)生有用結(jié)果的概率，取值0.99；w為每次從數(shù)據(jù)集中選取1個(gè)局內(nèi)點(diǎn)的概率，取0.5；n為估計(jì)模型需要的最小數(shù)據(jù)量，平面需要至少3個(gè)點(diǎn)確定，假設(shè)這n個(gè)點(diǎn)的選取是相互獨(dú)立的，選中的點(diǎn)可能被后續(xù)迭代重新選擇，這樣求得的k值一定是迭代次數(shù)的上限值。

由于料堆地面不平整，RANSAC分割算法會(huì)將料堆和地面分割成多個(gè)分離的點(diǎn)云塊，結(jié)合歐式聚類算法可完成散貨料堆點(diǎn)云提取，歐式聚類算法的過程如下：

(1)確定某一采樣點(diǎn)qi，創(chuàng)建一個(gè)空集Q*，設(shè)定閾值t。

(2)用k-d樹算法搜索qi最近鄰的k個(gè)點(diǎn)，計(jì)算這k個(gè)點(diǎn)到qi的距離，將采樣點(diǎn)qi和距離小于t的點(diǎn)qi1，qi2，qi3…放在Q*中。

(3)在Q*/qi(集合Q*中除qi點(diǎn)外的其他點(diǎn))里找到qi1，重復(fù)操作(2)。

(4)在Q*/qi,qi1中找一點(diǎn)，重復(fù)操作(2)。

(5)當(dāng)Q*中不在加入新的點(diǎn)時(shí)，完成一次聚類搜索。

2.2 點(diǎn)云降噪

采用近鄰統(tǒng)計(jì)分析法去除離散點(diǎn)，算法的步驟如下：

(1)利用k-d樹法搜索集合Q中每一個(gè)點(diǎn)qi的k鄰域。

(4)

(5)

濾除離散點(diǎn)后的點(diǎn)云還存在細(xì)微的噪聲點(diǎn)，通過曲面擬合可以將這些噪聲點(diǎn)濾除。曲面擬合常用的方法有多項(xiàng)式擬合和分段擬合，多項(xiàng)式擬合需要較高次數(shù)才能達(dá)到較好效果，計(jì)算復(fù)雜；分段擬合影響擬合的光滑性。為了解決這2種方法的不足，運(yùn)用移動(dòng)最小二乘法(Moving Least Square，MLS)引入緊支撐權(quán)函數(shù)和基函數(shù)。緊支撐權(quán)函數(shù)決定擬合曲線、曲面的光滑度，基函數(shù)決定擬合曲線、曲面的誤差大小。

在待擬合的區(qū)域里，擬合函數(shù)φ(x)表示為

(6)

式中，η(x)=[η1(x),η2(x),…,ηm(x)]T稱為基函數(shù)，它是n次完全多項(xiàng)式，m是基函數(shù)的項(xiàng)數(shù)；a(x)=[a1(x),a2(x),…,am(x)]T為待求的系數(shù)，它是坐標(biāo)x的函數(shù)。點(diǎn)云的線性基和二次基分別為：

線性基：η(x)=[1,x,y]T，m=3。

二次基：η(x)=[1,x,y,x2,xy,y2]T，m=6。

(7)

式中，J是選定節(jié)點(diǎn)鄰域點(diǎn)數(shù)目；φ(x)是擬合函數(shù)；f(xI)是x=xI處的節(jié)點(diǎn)值，w(x-xI)是節(jié)點(diǎn)xI的權(quán)函數(shù)。為確定系數(shù)a(x)，計(jì)算式(7)的極小值，并對(duì)a求導(dǎo)得

(8)

其中

(9)

Q(x)=[w(x-x1)η(x1),w(x-x2)η(x2),

…,w(x-xk)η(xk)]

(10)

f=[f(x1),f(x2),…,f(xk)]T

(11)

令(8)式為0，得

a(x)=P-1(x)Q(x)f

(12)

將式(12)代入(6)，就可以得到MLS擬合函數(shù)

φ(x)=ηT(x)P-1(x)Q(x)f

(13)

緊支撐權(quán)函數(shù)是移動(dòng)最小二乘法的核心，權(quán)函數(shù)只影響支撐域內(nèi)的數(shù)據(jù)，因此，權(quán)值在支撐域內(nèi)大于零，并且隨‖x-xI‖的增大而減小，在支撐域邊界和外界處等于零。另外，權(quán)函數(shù)應(yīng)該光滑連續(xù)，這樣可以使得繼承權(quán)函數(shù)特性的擬合函數(shù)也光滑連續(xù)。常用的權(quán)函數(shù)是多次樣條函數(shù)，如式(14)所示。

(14)

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

用白色塑料顆粒模擬散貨，用Kinect深度相機(jī)采集點(diǎn)云，獲取的料堆點(diǎn)云見圖2。體素柵格下采樣精簡算法耗時(shí)1.64s，精簡后點(diǎn)的數(shù)目為32 672(精簡前為216 237)，精簡程度為84.9%，結(jié)果見圖3。

圖2 散貨料堆初始點(diǎn)云圖 圖3 精簡后點(diǎn)云圖

RANSAC算法分割地面后的效果見圖4。平面偏離閾值σ影響局內(nèi)點(diǎn)的選取，當(dāng)σ值過小時(shí)，大量地面點(diǎn)被錯(cuò)誤當(dāng)作外點(diǎn)，地面和散貨料堆分離模糊，(見圖4a)；當(dāng)σ值過大時(shí)，部分料堆點(diǎn)被錯(cuò)誤當(dāng)作局內(nèi)點(diǎn)，散貨料堆被過度分割，(見圖4c)所示。根據(jù)實(shí)驗(yàn)結(jié)果，σ取0.008 m到0.012 m之間的值的效果較好，為保證精度σ值取0.008，分割結(jié)果(見圖4b)。

圖4 不同分割閾值下的分割效果

去除地面點(diǎn)云后的點(diǎn)云中仍然存在大量的離散點(diǎn)，采用鄰域統(tǒng)計(jì)分析法去除離散點(diǎn)云。取標(biāo)準(zhǔn)差倍數(shù)ξ為1，鄰域k越大，算法的魯棒性越好，但是算法使用的時(shí)間也越長。為了針對(duì)散貨料堆選擇合適的k值，設(shè)計(jì)了k=2,4…24共12組實(shí)驗(yàn)，得出算法計(jì)算時(shí)間T和濾除點(diǎn)數(shù)目M與k的對(duì)應(yīng)關(guān)系(見圖5)。從圖5中可以看出k值為8時(shí)，濾波時(shí)間和濾除點(diǎn)數(shù)目綜合效果最佳，因此，鄰域大小取為8。

圖5 算法用時(shí)、濾除效果與鄰域大小關(guān)系圖

離散點(diǎn)去除后，點(diǎn)云大致分為4個(gè)集群(見圖6a)，用歐式聚類將4個(gè)集群劃分出來，再提取點(diǎn)數(shù)最多(13109個(gè)點(diǎn))的散貨料堆點(diǎn)云(見圖6b)。

圖6 歐式聚類分割示意圖

采用MLS光滑點(diǎn)云，用k-d樹搜索法加速鄰域搜索，取二次基函數(shù)η(x)=[1,x,y,x2,xy,y2]T。根據(jù)實(shí)驗(yàn)結(jié)果，支撐域半徑r值取0.012 m以上平滑效果達(dá)到最好，但是隨著r值增大，算法處理時(shí)間增大，因此，取r=0.012 m為本算法研究參數(shù)，最終實(shí)驗(yàn)結(jié)果見圖7。

圖7 點(diǎn)云MLS光滑處理效果對(duì)比圖

4 結(jié)語

提出一種應(yīng)用在散貨料堆點(diǎn)云的高效率預(yù)處理算法框架，該算法主要完成散貨料堆的地面分割和降噪。在經(jīng)典RANSAC分割算法前增加點(diǎn)云精簡處理，提高地面分割速度，并通過歐式聚類分割算法解決RANSAC分割算法分割不徹底問題。結(jié)合統(tǒng)計(jì)分析法和移動(dòng)最小二乘法去除離散點(diǎn)和點(diǎn)云表面細(xì)小噪聲點(diǎn)，并在歐式聚類前完成離散點(diǎn)去除，提高料堆點(diǎn)云分割提取的穩(wěn)定性。