基于八叉樹(shù)編碼的鑄件點(diǎn)云融合簡(jiǎn)化方法*

翟 巍,馬 行,,穆春陽(yáng),王曉強(qiáng)

(1.北方民族大學(xué) a.電氣信息工程學(xué)院;b.機(jī)電工程學(xué)院,銀川 750021;2.寧夏智能信息與大數(shù)據(jù)處理重點(diǎn)實(shí)驗(yàn)室,銀川 750021)

0 引言

自動(dòng)化工業(yè)生產(chǎn)中鑄件的澆冒口切割通常是由工人們手工切割,這樣不僅耗費(fèi)大量人力資源,且人工切割的品控也難以得到保證。近些年,選擇三維激光掃描技術(shù)對(duì)要切割的鑄件進(jìn)行點(diǎn)云數(shù)據(jù)采集,再使用機(jī)械臂進(jìn)行切割,是目前工業(yè)生產(chǎn)中發(fā)展的方向之一。實(shí)際應(yīng)用生產(chǎn)中,所采用得高精度的點(diǎn)云設(shè)備采集的點(diǎn)云數(shù)據(jù)量龐大,可能還包含了一些冗余點(diǎn),在后續(xù)三維重建過(guò)程中必然會(huì)消耗大量的時(shí)間和計(jì)算機(jī)資源[1]。因此,盡可能地減少原始數(shù)據(jù),消除冗余數(shù)據(jù)點(diǎn)和噪聲,同時(shí)保證點(diǎn)云數(shù)據(jù)的準(zhǔn)確率在一個(gè)合適的水平,是基于點(diǎn)云簡(jiǎn)化實(shí)現(xiàn)三維重構(gòu)的重要步驟。

目前,點(diǎn)云簡(jiǎn)化方法主要有兩類(lèi):基于點(diǎn)云數(shù)據(jù)點(diǎn)的簡(jiǎn)化方法和基于網(wǎng)格的簡(jiǎn)化方法[2-4]?；诰W(wǎng)格的點(diǎn)云簡(jiǎn)化方法主要思想是為三維點(diǎn)云構(gòu)造一個(gè)三角形或者是多邊形網(wǎng)格,其中的節(jié)點(diǎn)是三維的點(diǎn)(不一定是點(diǎn)云原始的數(shù)據(jù)點(diǎn)),邊則為點(diǎn)之間的連線。通過(guò)減少節(jié)點(diǎn)或邊的數(shù)量來(lái)簡(jiǎn)化網(wǎng)格,例如將幾個(gè)節(jié)點(diǎn)合并,同時(shí)保留局部的結(jié)構(gòu)特征。在HOPPE、ECK等[5-6]的研究中,當(dāng)被測(cè)量表面的點(diǎn)的子區(qū)域連續(xù)時(shí),可以通過(guò)漸進(jìn)網(wǎng)格算法簡(jiǎn)化點(diǎn)云。DEY等[7]提出了一種利用樣本抽取來(lái)消除過(guò)采樣的算法,這可以保證剩余的點(diǎn)足以重建曲面。此外更多關(guān)于基于網(wǎng)格的點(diǎn)云簡(jiǎn)化方法則可以在ALLIEZ、PENG、MAGLO等[8-10]的綜述中找到。正如ZHANG等[11]所指出的,這類(lèi)方法的缺點(diǎn)是網(wǎng)格構(gòu)造需要耗費(fèi)大量的運(yùn)算,并且網(wǎng)格簡(jiǎn)化改變了原始點(diǎn)的位置,從而導(dǎo)致原數(shù)據(jù)失真。

與此相對(duì)的,基于點(diǎn)的簡(jiǎn)化方法已經(jīng)成為目前點(diǎn)云簡(jiǎn)化研究的熱點(diǎn)。尹星翔等[12]提出了一種基于曲率和均勻精簡(jiǎn)的點(diǎn)云簡(jiǎn)化方法。所提方法首先利用包圍盒法建立k-鄰域集然后根據(jù)曲率對(duì)點(diǎn)云區(qū)域進(jìn)行分類(lèi)簡(jiǎn)化。ECKART等[13]提出了一個(gè)概率生成模型來(lái)模擬點(diǎn)云的分布,通過(guò)一種分層的期望最大化算法,在簡(jiǎn)化率和模型結(jié)構(gòu)的完整性上取得一個(gè)很好的平衡。在鑄件澆冒口切割方面,SONG等[14]提出了一種基于八叉樹(shù)編碼和表面曲率特征閾值相結(jié)合的點(diǎn)云簡(jiǎn)化方法。該方法可以保持目標(biāo)點(diǎn)云的特征,同時(shí)也保證了點(diǎn)云簡(jiǎn)化的處理速度。HAN等[15]提出了一種基于法向量的邊的點(diǎn)云簡(jiǎn)化方法,因此邊緣特征被很好的保留下來(lái)?；谘芯繉?duì)象的數(shù)據(jù)屬性,上述基于點(diǎn)的簡(jiǎn)化方法可以進(jìn)一步細(xì)分為:空間分割、幾何特征和額外屬性[16-17]。

針對(duì)工業(yè)中鑄件澆冒口切割自動(dòng)化的需求,本文提出了一種基于八叉樹(shù)編碼分區(qū)選取不同簡(jiǎn)化算法的點(diǎn)云簡(jiǎn)化方法。該方法包含了空間分割和幾何特征,首先利用八叉樹(shù)編碼將點(diǎn)云分割,然后采集不同分割區(qū)域的曲率特征,利用兩種不同的簡(jiǎn)化算法對(duì)3種鑄件進(jìn)行測(cè)試,在不損失點(diǎn)云特征的情況下,實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)簡(jiǎn)化的易操作、高效率和高精度要求。

1 本文所用方法

本文的點(diǎn)云簡(jiǎn)化方法的主要步驟如圖1所示。為了將點(diǎn)云劃分為多個(gè)區(qū)域,本文首先采用了八叉樹(shù)編碼的方法。在這一步驟中構(gòu)造了原始數(shù)據(jù)點(diǎn)的包圍框,并將其劃分為具有相同邊長(zhǎng)的多個(gè)子立方體,以此建立了原始數(shù)據(jù)點(diǎn)云的拓?fù)淠Ｐ?接著,對(duì)每個(gè)子立方體中的點(diǎn)進(jìn)行k-鄰域搜索,并計(jì)算出作為點(diǎn)云特征的曲率;然后,在設(shè)置可調(diào)的曲率閾值后,根據(jù)曲率閾值和所有子立方體的平均曲率識(shí)別曲率較大或較小的區(qū)域。其中,曲率較小的區(qū)域?yàn)殍T件的平坦區(qū)域,曲率較大的區(qū)域?yàn)殍T件的切割區(qū)域。

圖1 點(diǎn)云數(shù)據(jù)簡(jiǎn)化方法步驟圖

接下來(lái)對(duì)曲率較小或較大的區(qū)域使用兩種不同的簡(jiǎn)化算法:對(duì)于鑄件的平坦區(qū)域,采用隨機(jī)抽樣的方法,對(duì)減少數(shù)據(jù)量非常有效,而且處理速度也有保障。對(duì)于鑄件的切割區(qū)域,選擇了基于區(qū)域重心的簡(jiǎn)化算法。這種方法的處理速度相對(duì)較慢,但是用這種方法減少數(shù)據(jù)量后,點(diǎn)云的結(jié)構(gòu)得以最大程度保留,確保有用信息能夠留存。

上述簡(jiǎn)化方法結(jié)合了隨機(jī)抽樣和基于區(qū)域重心兩種簡(jiǎn)化算法的優(yōu)點(diǎn),并考慮了鑄件的點(diǎn)云曲率分布狀況。對(duì)于鑄件來(lái)說(shuō),曲率較大的區(qū)域數(shù)量明顯遠(yuǎn)小于曲率較小的區(qū)域數(shù)量。因此,所提出的鑄件點(diǎn)云簡(jiǎn)化方法在保證了簡(jiǎn)化速度的同時(shí)也使大部分特征信息得以留存。

2 基于鄰域搜索的八叉樹(shù)編碼

由于本研究所針對(duì)的高精度鑄件點(diǎn)云數(shù)據(jù)量較大,如果使用k-d樹(shù)(k-維樹(shù))對(duì)區(qū)域進(jìn)行劃分,往往需要的時(shí)間較長(zhǎng),并且搜索效率較低。所以考慮到將k-d樹(shù)應(yīng)用于鑄件點(diǎn)云的鄰域搜索的不足,本文采用了八叉樹(shù)編碼算法。這種算法更適合于本研究中鑄件點(diǎn)云的三維空間劃分。該算法結(jié)構(gòu)簡(jiǎn)單,搜索效率高。

如圖2所示,在本研究中,我們基于目標(biāo)對(duì)象的點(diǎn)云的拓?fù)潢P(guān)系建立了一個(gè)根模型。首先,在構(gòu)造包圍框時(shí),將所有的點(diǎn)數(shù)據(jù)分成8個(gè)大小相同的子立方體;其次,用遞歸方法將每個(gè)子立方體均分;最后,重復(fù)前面的步驟直到子立方體的最小邊長(zhǎng)小于指定的點(diǎn)間距?？紤]到研究對(duì)象的數(shù)據(jù)點(diǎn)近百萬(wàn)這一因素,因此指定的距離設(shè)置為4 mm,以便允許50～100點(diǎn)云數(shù)據(jù)包含在最小的子立方體中。與此同時(shí),由八叉樹(shù)編碼算法得到的每個(gè)子立方體都根據(jù)其位置進(jìn)行編碼。

圖2 八叉樹(shù)分區(qū)模型

每個(gè)子立方體用一個(gè)代碼表示,該代碼對(duì)應(yīng)于八叉樹(shù)下的根節(jié)點(diǎn)。根模型中的子立方體位置可以用八叉樹(shù)代碼Q表示,如式(1)所示:

Q=qn-1…qm…q1q0

(1)

式中:qm是在這一層級(jí)節(jié)點(diǎn)的數(shù)量,m∈{0,1,…,n-1},qm+1是qm父級(jí)的節(jié)點(diǎn)數(shù)。因此從每個(gè)子節(jié)點(diǎn)到八叉樹(shù)中根的路徑可以用q0到qn-1來(lái)表示。

具體的流程如下:

步驟1:確定點(diǎn)云八叉樹(shù)劃分的編號(hào)。

d0*2n≥dmax

(2)

式中:d0為點(diǎn)云已知點(diǎn)的距離,dmax為包圍框的最長(zhǎng)邊長(zhǎng),n為八叉樹(shù)的劃分編號(hào),為式(2)中的最小整數(shù)。

步驟2:確定點(diǎn)云數(shù)據(jù)點(diǎn)所在位置的子立方體的編碼。假設(shè)數(shù)據(jù)點(diǎn)為P(x,y,z),子立方體的空間索引為(i,j,k),Q為對(duì)應(yīng)節(jié)點(diǎn)的八叉樹(shù)編碼。它們之間的關(guān)系如式(3)～式(5)所示:

(3)

式中:(xmin,ymin,zmin)是與根節(jié)點(diǎn)對(duì)應(yīng)的包圍框的最小頂點(diǎn)坐標(biāo)。將子立方體的空間索引(i,j,k)轉(zhuǎn)換為二進(jìn)制表示的過(guò)程如式(4)所示:

(4)

式中:

im,jm,km∈{0,1},m∈{0,1,…,n-1}
qm=im+jm21+km22

(5)

因此,該立方體對(duì)應(yīng)的八叉樹(shù)編碼可以用式(1)來(lái)表示。

如果我們假設(shè)經(jīng)過(guò)劃分后的一個(gè)子立方體的索引是(i,j,k),那么圍繞它的26個(gè)子立方體的索引可以用(i±δ,j±δ,k±δ)(δ∈{0,1})來(lái)表示。

在點(diǎn)云中找到距離子立方體重心最近的點(diǎn)pi后,在子立方體當(dāng)中均勻選取30個(gè)點(diǎn),確保點(diǎn)pi是這30個(gè)點(diǎn)的重心。這30個(gè)點(diǎn)也需要盡可能多地覆蓋子立方體內(nèi)的空間。最后,用最小二乘法通過(guò)30個(gè)點(diǎn)擬合二次曲面。二次曲面擬合公式如式(6)所示:

(6)

式中:ci,j-1為曲面參數(shù)。

3 基于曲率特征的點(diǎn)云簡(jiǎn)化

3.1 曲率特征計(jì)算方法

在本文當(dāng)中,采用了最小二乘法計(jì)算擬合表面系數(shù)如式(7)所示:

(7)

式中:xk、yk、zk是子立方體中各點(diǎn)的坐標(biāo)。

為了在式(7)中分別計(jì)算系數(shù),使其偏微分為0:

(8)

通過(guò)求解方程從而確定了擬合曲面的二次方程。在得到擬合曲面方程后,根據(jù)以下一階和二階偏微分推導(dǎo)出各點(diǎn)的平均曲率:

(9)

緊接著,曲面的平均曲率就可以表示為:

(10)

(11)

3.2 基于隨機(jī)采樣的簡(jiǎn)化方法

由于鑄件平緩區(qū)域的點(diǎn)云數(shù)據(jù)需要保留相對(duì)完整的輪廓特征,對(duì)詳細(xì)特征的要求不是很高。因此,在平緩區(qū)域內(nèi)采用了隨機(jī)采樣的方法進(jìn)行簡(jiǎn)化[18]。

第一步先建立一個(gè)隨機(jī)函數(shù),該函數(shù)覆蓋了原始的點(diǎn)云數(shù)據(jù),然后根據(jù)隨機(jī)函數(shù)生成隨機(jī)數(shù),刪除相應(yīng)的點(diǎn),直到剩余的點(diǎn)云數(shù)據(jù)量的減少率達(dá)到確定的預(yù)設(shè)值。該隨機(jī)采樣算法操作簡(jiǎn)單,易于實(shí)現(xiàn),處理速度也很高。然而,隨機(jī)函數(shù)的隨機(jī)性非常大。在減少原始點(diǎn)云的數(shù)據(jù)后,可能會(huì)丟失一些重要的幾何特征。

3.3 基于區(qū)域重心的簡(jiǎn)化方法

當(dāng)曲率大于給定的閾值時(shí),對(duì)于這類(lèi)區(qū)域采用了基于區(qū)域重心的簡(jiǎn)化算法。相對(duì)于隨機(jī)采樣的簡(jiǎn)化算法,基于區(qū)域重心的簡(jiǎn)化方法可以保留更多的信息特征。

首先,當(dāng)曲率大于閾值時(shí),該區(qū)域內(nèi)的所有點(diǎn)都由一個(gè)立方體所包含;其次,將立方體劃分成若干個(gè)相同大小的小立方體;最后,計(jì)算每個(gè)小立方體中的平均點(diǎn)(區(qū)域重心),并計(jì)算離該平均值最近的點(diǎn)。

假設(shè)在所選的立方體中有N個(gè)點(diǎn){p1,p2,…,pN},并且有坐標(biāo)為(pix,piy,piz),i=1,2,…,N,然后將平均點(diǎn)標(biāo)記為p,其坐標(biāo)為(px,py,pz),如式(12)所示:

(12)

緊接著,可以計(jì)算出子立方體中的點(diǎn)pi(pix,piy,piz)與平均點(diǎn)p之間的距離di,(i=1,2,…,N),如式(13)所示:

(13)

上式同時(shí)也計(jì)算了其他點(diǎn)與平均點(diǎn)之間的距離。最后,在刪除子立方體中的其他點(diǎn)時(shí)將保留此點(diǎn),可確定在子立方體之中離均值點(diǎn)最近的點(diǎn)。具體簡(jiǎn)化過(guò)程如圖3所示。

圖3 基于區(qū)域重新簡(jiǎn)化方法的過(guò)程

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

本次實(shí)驗(yàn)基于某公司的gocator3200三維激光掃描儀對(duì)三種鑄件掃描獲得,同時(shí)通過(guò)MATLAB對(duì)所提出的簡(jiǎn)化方法進(jìn)行了驗(yàn)證。在實(shí)驗(yàn)中,數(shù)據(jù)的簡(jiǎn)化率定義為剩余點(diǎn)云數(shù)據(jù)量與總點(diǎn)云數(shù)據(jù)量的比值。切割區(qū)域特征點(diǎn)的保留率定義為切割區(qū)域保留點(diǎn)的數(shù)據(jù)量與切割區(qū)域點(diǎn)云數(shù)據(jù)總量的比值。如圖4所示,圖4a部分為工件原始圖像,圖4b部分點(diǎn)云的灰線部分的點(diǎn)云呈現(xiàn)相對(duì)陡峭的分布,而其余白色點(diǎn)云的分布則較為平緩。

(a) 點(diǎn)云原始數(shù)據(jù) (b) 區(qū)域劃分后的點(diǎn)云圖4 鑄件模型點(diǎn)云的區(qū)域分布

通過(guò)對(duì)比圖5中原始點(diǎn)云的數(shù)據(jù)和簡(jiǎn)化過(guò)后可以看出,隨著簡(jiǎn)化率的提高,依然可以觀察到整個(gè)被測(cè)物體的形狀。該算法可以保留帶切割鑄件的重要特征。本實(shí)驗(yàn)將原始的點(diǎn)云數(shù)據(jù)劃分為點(diǎn)云特征較為平坦的區(qū)域,并且采用隨機(jī)抽樣的方法進(jìn)行簡(jiǎn)化。實(shí)驗(yàn)結(jié)果如圖5所示。

(a) 平坦區(qū)域點(diǎn)云原始數(shù)據(jù) (b) 80%簡(jiǎn)化率

(c) 60%簡(jiǎn)化率 (d) 40%簡(jiǎn)化率

(e) 20%簡(jiǎn)化率 (f) 5%簡(jiǎn)化率圖5 使用不同簡(jiǎn)化率的簡(jiǎn)化結(jié)果

可以看出,簡(jiǎn)化率越小,剩下的點(diǎn)云數(shù)據(jù)點(diǎn)就越少。在較為平坦的區(qū)域,只需要保留原始點(diǎn)云完整的輪廓特征即可?？紤]到精簡(jiǎn)所需要的時(shí)間及其效果,采用隨機(jī)抽樣的方法,選取了20%的簡(jiǎn)化率,相應(yīng)的整體的減少率為77.80%。

對(duì)于點(diǎn)云分布較陡的區(qū)域,對(duì)區(qū)域重心法進(jìn)行了簡(jiǎn)化。如圖6所示,利用區(qū)域重心法進(jìn)行簡(jiǎn)化后,區(qū)域點(diǎn)云數(shù)據(jù)得到較好的保存,實(shí)驗(yàn)結(jié)果如表1所示。

(a) 切割區(qū)域原始點(diǎn)云 (b) 設(shè)置邊長(zhǎng)為2 mm

(c) 設(shè)置邊長(zhǎng)為3 mm (d) 設(shè)置邊長(zhǎng)為4 mm圖6 設(shè)置不同邊長(zhǎng)的邊框下具有不同簡(jiǎn)化效果

表1 不同邊長(zhǎng)下的簡(jiǎn)化效果

從圖6和表1中可以看出,所設(shè)置的子立方體網(wǎng)格的邊長(zhǎng)越小,保留的細(xì)節(jié)特征就越多,但處理速度就越低。

所以綜合考慮到簡(jiǎn)化時(shí)間和焊接區(qū)特征點(diǎn)的簡(jiǎn)化率,在采用區(qū)域重心簡(jiǎn)化法時(shí),將子立方體網(wǎng)格的邊長(zhǎng)設(shè)置為3 mm。從圖7中可以看出,采用基于八叉樹(shù)編碼和表面特征曲率閾值相結(jié)合的點(diǎn)云簡(jiǎn)化方法,為鑄件模型的切割區(qū)域保留了重要的特征點(diǎn)。同時(shí),外觀輪廓仍然保持良好,對(duì)下一步提取關(guān)鍵的幾何特征位置有很大幫助。

圖7 使用該算法后點(diǎn)云簡(jiǎn)化的效果

為了分析所提出的鑄件切割點(diǎn)云簡(jiǎn)化方法的性能,并與其他3種簡(jiǎn)化方法進(jìn)行了比較。本文的簡(jiǎn)化方法和3種傳統(tǒng)簡(jiǎn)化算法的實(shí)驗(yàn)結(jié)果如表2所示,各算法的簡(jiǎn)化效果如圖8所示。

表2 鑄件點(diǎn)云數(shù)據(jù)的4種簡(jiǎn)化方法的比較結(jié)果

(a) 原始點(diǎn)云數(shù)據(jù) (b) 本文提出的方法

(c) 隨機(jī)采樣法 (d) 包圍盒法

(e) 區(qū)域重心法圖8 切割鑄件的簡(jiǎn)化方法對(duì)比結(jié)果圖

結(jié)果如表2和圖8所示,其中這些方法的還原率近似相等。從表2可以看出,當(dāng)點(diǎn)云的減少率約為20%時(shí),4種方法的處理速度差異很大。隨機(jī)抽樣處理是處理速度最快的方法。然而盡管它所需的處理時(shí)間最短,但是由于隨機(jī)抽樣的隨機(jī)性,該方法可能會(huì)丟失許多特征點(diǎn)。

通過(guò)表2可知,本文所提出的簡(jiǎn)化方法的處理速度低于現(xiàn)有的隨機(jī)采樣方法,但特征點(diǎn)的保留效果更好。這是因?yàn)樵摲椒ú捎昧嘶卩徲螯c(diǎn)搜索的八叉樹(shù)編碼算法,并針對(duì)不同曲率的區(qū)域選擇了兩種不同的簡(jiǎn)化算法。結(jié)果表明,該方法可以結(jié)合隨機(jī)抽樣算法和區(qū)域重心簡(jiǎn)化算法的優(yōu)點(diǎn)。將本方法推廣至采集的另外兩種鑄件模型上,簡(jiǎn)化后效果如圖9所示。

(a) 第一組

(b) 第二組圖9 其他兩種模型使用本方法后的簡(jiǎn)化效果

可以看到,被簡(jiǎn)化后的鑄件模型在被簡(jiǎn)化的同時(shí)切割區(qū)域的特征點(diǎn)也很好的被留存,說(shuō)明該算法具有較為寬泛的應(yīng)用場(chǎng)景。

5 結(jié)論

考慮到在工業(yè)生產(chǎn)過(guò)程中采用了機(jī)械臂對(duì)鑄件澆冒口自動(dòng)切割,有必要減少由激光掃描儀獲得的鑄件點(diǎn)云的數(shù)據(jù)量用以增加處理速度。本文提出了一種基于八叉樹(shù)編碼和表面曲率特征閾值的點(diǎn)云簡(jiǎn)化方法,以減少工業(yè)制造中鑄件的點(diǎn)云。本研究基于鑄件澆冒口的點(diǎn)云特征,采用八叉樹(shù)編碼方法將點(diǎn)云劃分為子立方體,然后通過(guò)k鄰域搜索和曲率計(jì)算得到曲率特征。最后通過(guò)結(jié)合這兩種簡(jiǎn)化算法,用以簡(jiǎn)化鑄件的點(diǎn)云數(shù)據(jù)。通過(guò)本次研究發(fā)現(xiàn),本文所提出的簡(jiǎn)化方法相對(duì)于其他3種傳統(tǒng)的簡(jiǎn)化方法包括包圍盒法、區(qū)域重心簡(jiǎn)化方法和曲率抽樣方法都要快。當(dāng)選取的簡(jiǎn)化率相近時(shí),本文提出的簡(jiǎn)化方法相對(duì)于這3種可以保留更多的特征點(diǎn)。該方法能夠很好的結(jié)合隨機(jī)采樣與區(qū)域重心簡(jiǎn)化法在不同曲率區(qū)域的優(yōu)點(diǎn),對(duì)保持鑄件的表面特征起到良好的作用。本文所提出的簡(jiǎn)化方法有利于機(jī)械廠的自動(dòng)切割系統(tǒng)的開(kāi)發(fā)。此外,還需要更多具有不同輪廓的鑄件的點(diǎn)云數(shù)據(jù)集來(lái)驗(yàn)證所提出的方法。