呂 繁，郭曉銳，李紅軍

（武漢紡織大學(xué) 機械工程與自動化學(xué)院，湖北 武漢 430073）

隨著計算機技術(shù)的快速發(fā)展，3D模型應(yīng)用在數(shù)據(jù)處理與可視化上得到了技術(shù)支撐。相較于平面，3D模型能夠直觀地呈現(xiàn)物體多角度下視圖和空間結(jié)構(gòu)信息，在此基礎(chǔ)上能更快速準(zhǔn)確的計算被測物體的體積。目前獲取3D模型主要信息的方式有：對物體進行超聲波掃描；攝像機多視角獲得照片序列，通過圖像拼接生成全景圖，計算目標(biāo)物體的空間坐標(biāo)；激光掃描儀對被測物體進行表面掃描，獲得掃描范圍內(nèi)的點云數(shù)據(jù)等[1]。激光掃描儀具有采集速度快、掃描精度高、抗干擾性強等優(yōu)勢，常用的基于散亂點云計算體積的算法有：切片法，將物體的散亂點云按特定方向順序進行等間距切片處理，利用切片面積及相鄰切片間距求解每段點云片的體積，求和即得到物體整體體積[2]；投影法，計算三角剖分后每個三角面片及其在指定投影平面上的投影所形成的凸五面體的體積和[3]。投影法的優(yōu)勢在于無論被測物體的形狀是否規(guī)則，通過掃描儀獲取其整體外形表面的點云數(shù)據(jù)，經(jīng)三角剖分和體積分割處理后積分求其體積。由于激光掃描儀的掃描精度、光照的反射干涉以及掃描環(huán)境的電磁干擾等因素會導(dǎo)致在實際掃描獲取點云數(shù)據(jù)時出現(xiàn)視覺盲區(qū)和數(shù)據(jù)躍遷，從而導(dǎo)致本應(yīng)相同的斷面點云數(shù)據(jù)量數(shù)據(jù)不對稱和數(shù)據(jù)缺失進而尋找疵點并去除，修正法向量偏差等[4]。

根據(jù)以上提出的問題和不足，本文提出基于空間三角剖分投影改進體積積分算法。三角剖分投影法的基本原理是：將掃描儀掃描出的斷面點云數(shù)據(jù)進行三角剖分，由于掃描斷面具有一定的空間順序性和規(guī)律性，通過迭代的方式將斷面數(shù)據(jù)一層層根據(jù)一定的拓?fù)浣Y(jié)構(gòu)劃分空間三角面片，通過計算所有三角形相對于地面平面的投影體積來計算待測物體體積。在大型工業(yè)現(xiàn)場進行的物料體積計算和不同掃描精度下的點云數(shù)據(jù)體積計算測試結(jié)果都表明此體積算法能夠簡化、改進從三角剖分投影入手的點云斷面數(shù)據(jù)的體積計算問題。

1 點云數(shù)據(jù)疵點去除處理

1.1 基于點云數(shù)據(jù)的三角剖分

三角剖分算法首先將凸包集合點U(k)的凸包分割成(k-2)個以凸包頂點為三角形頂點的三角形[5]，之后再對凸包三角形進行逐個迭代分割。將散亂點S(n)基于Lawson算法的逐點插入方式形成新的三角形。此算法的時間復(fù)雜度為O(N2)[6]。由于本文的點云數(shù)據(jù)是有一定拓?fù)浣Y(jié)構(gòu)的斷面數(shù)據(jù)，在傳統(tǒng)的三角剖分系統(tǒng)中由于退化現(xiàn)象而導(dǎo)致魯棒性不強，故本文使用改進的層遞式三角剖分算法對斷面點云數(shù)據(jù)進行三角剖分。要求每個三角形均能夠滿足空圓特性，即任意三角面片的外接圓內(nèi)均不包含散亂點云集中其他點[7]。

1.2 法向量調(diào)整及疵點去除

1.2.1 k鄰域搜索

常用的搜索k鄰域方法主要有八義樹、空間單元格和kd-tree法。本文首先通過kd-tree建立空間拓?fù)潢P(guān)系，從而進行各數(shù)據(jù)點的最近鄰域搜索，得到臨近點的位置和各數(shù)據(jù)點的結(jié)構(gòu)信息，同時能夠減少處理時間，提高效率。在這個基礎(chǔ)上，從密度較大的地方開始對數(shù)據(jù)點進行K鄰域搜索（本文處理的數(shù)據(jù)有一定的范圍），然后進行法向量計算，隨之對其進行方向調(diào)整，這樣就可以獲得每個點以及臨近點的法向量，去除掉每個點鄰域外或者平均法向量相關(guān)性小于一定范圍（與掃描儀的測量精度與每個斷面之間的精度相關(guān)）的點，從而較有效的去除散亂點中疵點和離群點，避免出現(xiàn)因為個別點導(dǎo)致物體拓?fù)湫畔l(fā)生畸變的情況出現(xiàn)。

1.2.2 法向量的計算

由于每個三角面片的法向量的方向都不一致，需為每個三角形面片確定具有相同特征的法向量。為獲得每個三角面片法向量，取一定半徑內(nèi)的點進行曲面擬合，在擬合曲面的基礎(chǔ)上求對應(yīng)三角面片的法向量。當(dāng)鄰域k值較小，而點云數(shù)據(jù)量龐大時，為減少曲面擬合時間，采用點 p ( xi, yi, zi)，p∈S(n)的k鄰域中各點進行平面擬合，再計算點p的法向量的大小，代表此鄰域中曲面在p點的法向量。本文使用最小二乘法來計算平面參數(shù)。設(shè)擬合平面為： a x + b y+cz ? d =0,需要滿足k鄰域中的點到平面的距離最小，即滿足a2+ b2+c2=1，在此限制下點p的最佳擬合平面為

由拉格朗日原理可知，F(xiàn)取極小值時有：d =ax + b y +cz ，(x,y,z)是k鄰域點的重心坐標(biāo)，，將d帶入F中消去d，并對a、b、c求偏導(dǎo)數(shù)作協(xié)方差分析，得

可以得出：

將e→帶入式（3）消去后得出

1.2.3 法向量調(diào)整

由上述方式獲得點云數(shù)據(jù)的法向量集合后，將鄰域內(nèi)部選擇該點的法向量進行判斷，鄰域內(nèi)的其他點若與此點的法向量方向不同，則進行疵點調(diào)整，將反向的法向量進行反向調(diào)整，使其與此點的法向量方向一致。根據(jù)前面獲得的各點的鄰域及法向量，用此方式將每個點的k鄰域內(nèi)的點進行計算并調(diào)整和k鄰域外疵點去除。

2 三角剖分投影體積積分算法

一般將目標(biāo)所在的地面設(shè)置為投影面，那么在測量之前就需要獲得掃描中心到地面的距離H，掃描左右兩邊是Y軸，前后是X軸，上下是Z軸。由此，每個掃描斷面都是基于YOZ平面。由于三角面片是連續(xù)無間隔的，故每個三角面片在投影面上形成的凸五面體之間是緊湊的，單個的凸五面體體積之和就是所有三角面片在投影面上進行投影形成的多面體體積，即物體的三角網(wǎng)格模型體積可以由每個三角面片投影形成的凸五面體的體積之和表示。設(shè)每個三角面片的三個頂點為分別為設(shè)三個頂點按照Z的大小排序為： z3＞ z2＞ z1。為簡化計算，將每個五面體分割為上半部分的小凸五面體和下半部分的三棱柱，由于小凸五面體三個側(cè)面與投影平面是空間平面垂直，故部分無投影體積，因此上半部分凸五面體體積可由上下底面的三角面片△ABC和△AB'C'決定，且兩個三角面片共用z值最小的點，即z1。

由圖1可知，△A"B"C"是三角面片△ABC在地面的投影三角形，△AB'C'是以z1為高度的切割三角形，△AB'C'與△A"B"C"全等且在Z軸上平行。三棱柱體積是由三角面片的投影到XOY平面的△A"B"C"為底和高z1共同決定。故三棱柱的體積為

圖1 三角面片投影體

點A到四邊形BB'C'C的高度為OA，由單個投影三角形△A"B"C"的面積可以得到OA的長度為

由于側(cè)面都是投影面，有BB'∥CC'，BB'⊥B'C'，得出四邊形BB'C'C是梯形。小凸五面體又可以分割為兩個四面體vABCC'和vABB'C'。由四面體體積計算公式v=1 3·Sh可得到其體積：

由于SBCC'和SBB'C'在同一平面上，由式（7）、（8）可以得到小凸五面體的體積為：

將式（6）帶入消去B'C'和OA，則凸五面體的體積是

故每個三角面片投影形成的凸五面體的體積為

將式（5）和式（9）帶入式（10）中可得到單個三角形投影體的體積

三角面片的集合和在投影平面上的投影三角形圍成的凸多面體就是物體的體積。每個三角面片投影形成的凸五面體（形如圖1所示）的體積為v。故被測物體的體積和為

3 實驗與結(jié)果分析

基于上述算法，利用掃描儀SICK LMS511獲取得到點云數(shù)據(jù)，掃描儀掃描儀精度為0.5°, 斷面掃描精度為200mm，對大型沙堆進行點云數(shù)據(jù)獲取，點云數(shù)據(jù)疵點去除和法向量調(diào)整后，采用此體積算法進行模型體積計算并三維可視化顯示。

圖2左是點云相對空間位置圖，可以看出每個斷面數(shù)據(jù)間隔相同，每個斷面數(shù)據(jù)量也基本相同，此沙堆共含有14 581個點，經(jīng)三角剖分處理后生成圖2右所示模型圖。

圖2 沙堆點云及三維重建生成圖

表1 體積算法驗證

由圖2和表1可知，采用本文算法計算體積偏差率小于1%，可符合工業(yè)要求。

4 結(jié)束語

本算法針對傳統(tǒng)體積算法曲面擬合效率低下的問題，設(shè)計了一種基于掃描儀點云數(shù)據(jù)三角剖分快速計算體積的方法，將點云數(shù)據(jù)進行疵點去除和法向量矢量調(diào)整后，直接對三角面片投影進行了體積計算，物體表面是一個個小三角面拼接構(gòu)成。算法體積計算的準(zhǔn)確性，體積偏差率經(jīng)計算小于1%。但未考慮到物體的曲面體積部分，需要進一步的提高算法的適用性和自修正性。