不規(guī)則體體積計算三維激光點云切片法

李 斌，魏俊博，馬博超，王 璐,徐明霞

1. 長安大學地質(zhì)工程與測繪學院，陜西 西安 710054； 2. 西部礦產(chǎn)資源與地質(zhì)工程教育部重點實驗室，陜西 西安 710054； 3. 陜西國防工業(yè)職業(yè)技術(shù)學院，陜西 西安 710300

體積是空間體對象形態(tài)分析的重要參數(shù)[1]，各種形體的體積計算，既是一個久遠又新穎的命題[2-4],也是空間體對象形態(tài)分析的基本內(nèi)容[5-6]。體積計算涉及規(guī)則幾何體和不規(guī)則幾何體兩種類型。其中，規(guī)則幾何體的體積計算有現(xiàn)成的公式甚至算法可用，操作簡便、精度高且應(yīng)用廣泛[7]。相對而言，不規(guī)則幾何體因形態(tài)各異，體積計算并無普適、統(tǒng)一的方法，甚至無章可循[8-13]，因此，仍是普遍面臨和亟待解決的現(xiàn)實難題[14-17]。三維激光掃描技術(shù)的興起和運用，客觀上為不規(guī)則體的體積計算提供了新模式[18-19]。例如，基于三維激光掃描點云的不規(guī)則樹冠體積[10]、商品包裝的點云體積[20]、船舶排水量的點云體積[21]等的估算。由此可見，只要能用三維激光掃描方式完成空間體對象掃描并獲取其整體外型輪廓的點云數(shù)據(jù)，不管其形態(tài)是否規(guī)則，都有可能求解其體積。另一方面，若三維激光掃描的空間體對象是規(guī)則的，則可用來檢驗所提計算方法的正確性和有效性。

探索激光掃描技術(shù)方法計算不規(guī)則體的點云體積，在很多領(lǐng)域已有應(yīng)用且成效顯著,但精度有待精化、適用性尚需提升[22-24]。目前，較為直接且簡單的點云體積計算方法是“點云切段法[25]”(后簡稱“切段法”)。該方法的基本思想和流程可概括為“空間體對象激光掃描→點云數(shù)據(jù)切段→分段點云投影→點云片輪廓邊界確定→點云片面積計算→點云體積計算”等6個步驟，而其中的“點云片輪廓邊界確定”和“點云片面積計算”是該法求解三維激光掃描空間體對象點云體積的兩個關(guān)鍵環(huán)節(jié)。由于存在可能的點云片外輪廓多邊形“形態(tài)畸變”、固有的計算系統(tǒng)性“放大效應(yīng)”和“三角形累加法”面積算法適用性不足等問題，造成該法不僅計算環(huán)節(jié)過多，而且計算結(jié)果偏差大，甚至可能錯誤等不良后果。因此，有必要提出適用三維激光掃描空間不規(guī)則體對象的點云體積計算得更為簡潔、有效的方法。

本文從簡化“切段法”計算環(huán)節(jié)、避免出現(xiàn)“放大效應(yīng)”、防止產(chǎn)生點云片輪廓多邊形“形態(tài)畸變”和選用更有效的面積算法4個方向入手，提出“點云切片法”(后簡稱“切片法”)。該法采用雙向最近點搜索法取代可能引起平面點云外輪廓多邊形“形態(tài)畸變”的掃描法，從算法層面消除了切片外輪廓多邊形點云散點搜索出錯的可能性；通過切片而非切段的技術(shù)路線，規(guī)避了“切段法”的投影環(huán)節(jié)，從而避免了由投影帶來的系統(tǒng)性的三重“放大效應(yīng)”，并有效減少了中間步驟；選用行列式模型法計算點云切片面積，從計算層面解決面積算法適用性的問題；用可靠的柱體體積計算方法計算點云分段體積，最終求和得到三維激光掃描空間體對象的整體體積，又確保了實體對象體積計算的精準。因此，從簡化、改進、完善流程和算法等核心環(huán)節(jié)入手的“切片法”有望解決三維激光掃描前提下的不規(guī)則體的點云體積計算問題。

1 點云切片法

以水平方向切割點云為例，建立在算法與編程計算基礎(chǔ)上的“切片法”的基本思想和流程可概括為“空間體對象激光掃描→點云數(shù)據(jù)切片→輪廓邊界確定→切片面積計算→點云體積計算”5個步驟，具體為：

(1) 空間體對象激光掃描。用地面三維激光掃描儀掃描空間體對象，獲得其點云數(shù)據(jù)D(如圖1(a)所示)。

(2) 點云數(shù)據(jù)切片。在點云縱向最小值0與最大值H之間，用一組(設(shè)為n+1個)等間距(間距為h，如式(1)所示)的水平面自上而下順序切割點云，依次得到系列水平點云切片Si(如圖1(b)、式(2)所示)。

(3) 輪廓邊界確定。使用雙向最近點搜索法[26]取代掃描法對亂序的各平面點云Si進行排序，生成各點云切片散點外輪廓邊界多邊形Pi(i=0,1,…,m)。

(4) 切片面積計算。分別計算Pi圍成的面積，即Si的面積Ai(i=0,1,…,n)(如式(4)所示)。

(5) 點云體積計算。累加Ai并乘以h得到點云體，也就是三維激光掃描物體的體積V(如式(3)所示)

(1)

i=0,1,…,n}

(2)

(3)

式中，n是切片數(shù)減1；x、y、z是點云點坐標。

在“切片法”中，切片平面點云外輪廓邊界多邊形正確確定與切片面積正確計算是“切片法”計算點云體積并確保正確的兩個關(guān)鍵環(huán)節(jié)。

1.1 輪廓邊界確定

點云切片外輪廓邊界多邊形的正確生成是“切片法”切片面積能否正確計算的基礎(chǔ)。相對而言，“切段法”中采用的射線360°掃描法雖然思路簡單、計算復雜度低，且在特定的平面點云外輪廓多邊形中可得到極佳的形態(tài)效果(如圖2(a)所示)，但當平面點云輪廓為極端凹多邊形時，“切段法”就難以規(guī)避“形態(tài)畸變”的致命缺陷，即當平面點云外接矩形的重心落在平面點云外面時，搜索得到的平面點云外輪廓邊界不能保證不走樣、不變形(如圖2(b)所示)，因此，這就有可能引起平面點云面積計算錯誤，進而導致體積計算畸變。

由此可見，為避免“切段法”點云片的“形態(tài)畸變”出現(xiàn)，“切片法”的雙向最近點搜索法就成為正確生成點云切片外輪廓邊界多邊形的關(guān)鍵舉措,其核心思想如下：

(1) 選擇邊界起點。在切片點中任選一點(如y坐標值最小)PS作為起點，以其最近點PE為終點生成多邊線。

(2) 確定最近點。取多邊線一端PS(PE)，在剩余點中找到距PS(PE)點最近的點P。

(3) 生成邊界邊。分別計算PS和PE到P的距離dS和dE，并比較dS和dE的大小，若dS

(4) 搜索并判斷進程。判斷切片上的點是否搜索完成。若是，結(jié)束搜索，生成點云切片外輪廓多邊形邊界；否則轉(zhuǎn)到步驟(2)。

當切片這種點云片外接矩形重心落在切片外時，取代射線360°掃描法的雙向最近點搜索法就能確保對平面點云散點數(shù)據(jù)進行正確的排序(如圖2(c)所示)。

1.2 切片面積計算

作為激光掃描對象點云體積計算的早期算法，“放大效應(yīng)”是“切段法”的又一痼疾。在“切段法”中，因投影而生的點云環(huán)帶的外輪廓邊界就成為相應(yīng)點云段塊投影后的最大外延，這樣，有賴“點云分段投影”的“切段法”就無形之中放大了平面點云外輪廓的邊界，從而造成“放大輪廓邊界”的第一重放大效應(yīng)；由于面狀物體是以其輪廓邊界構(gòu)成的多邊形來表示的[1]，因此，平面點云輪廓邊界多邊形放大的實質(zhì)，就是投影面面積的放大，由此導致“切片面積放大”的第二重放大效應(yīng)；而事實上，點云切段的柱體體積由切片面積Ai和段距h兩個因素決定，Ai放大而h一定，則必然引起“點云體積放大”的第三重放大效應(yīng)。由此可見，連鎖出現(xiàn)的三重“放大效應(yīng)”，就使激光點云對象的體積呈現(xiàn)單邊放大的系統(tǒng)性后果。

若規(guī)定m個頂點p0，p1，…，pm=p0，按逆時針回路首尾相接構(gòu)成多邊形并設(shè)為Pi，則Pi的面積Ai可由行列式(如式(4)所示)計算得到[1]

(4)

式中，xj、yj為切片平面點云外輪廓多邊形Pi(i=0,1，…,n)的頂點pj(j=0,1,…,m)的坐標；j為點云切片外輪廓邊界多邊形的頂點編號；i為點云切片的編號；n為點云切片個數(shù)減1。

“切片法”采用的雙向最近點搜索法，聚焦點云切片排序問題，從算法層面有效規(guī)避了外輪廓邊界多邊形生成時出錯的可能性，為點云切片面積正確計算創(chuàng)造了有利條件；而在計算點云切片面積時，“切段法”采用的“三角形累加法”是以投影切片外接矩形的重心為起點，依次與投影面上的兩個相鄰點構(gòu)造三角形，并將三角形面積累加得到投影切片的面積；同樣，由于外接矩形重心位置的不確定，該法也不能適用于極端凹多邊形時的面積計算。為解決面積計算方法適用性的問題，本文采用了上述行列式的面積計算模型用于點云切片面積的計算，不僅克服了“三角形累加法”適應(yīng)性不強、局限性大的缺點，且計算流程清晰、易于編程、結(jié)果可靠，從計算層面保證了點云體積的計算建立在面積計算準確無憂的基礎(chǔ)之上。

1.3 要點與優(yōu)勢

對不同物體而言，點云切片的外輪廓邊界形態(tài)雖然各異，但因“雙向最近點搜索”算法的普適性，繞開了與中心位置關(guān)系密切的掃描法的排序陷阱，從而既確保了外輪廓邊界多邊形的計算與點云切片的凹或凸的形態(tài)無關(guān)，也保證了點云切片面積計算的正確性，從而為后續(xù)體積計算結(jié)果的準確無誤奠定了基礎(chǔ)。事實上，“雙向最近點搜索”算法也可用在傳統(tǒng)的“切段法”中，以解決由“射線360°掃描”算法引起的“形態(tài)畸變”的可能，使“切段法”有所改進——不至于因點云片外輪廓多邊形的計算錯誤而導致后續(xù)面積計算乃至體積計算出錯的嚴重后果。

2 點云體積計算

本文選用規(guī)則的圓錐體模型(如圖3(a)—3(c)所示)和不規(guī)則的墩臺柱體實物(如圖4(a)—4(c)所示)兩種對象，使用三維激光掃描儀獲取研究對象的點云數(shù)據(jù)，并對其進行拼接、去噪[27-29]等處理后(其流程詳見圖5)，通過圓錐模型計算、圓錐墩臺點云計算及其結(jié)果對比，驗證“切片法”點云體積計算算法的可行性、正確性、高效性和適用性。其中，點云體積算法可行性、正確性的判斷，源于對圓錐體的計算與分析。圓錐體是規(guī)則幾何形體，其模型尺寸可以量算得到(如表1、表2及圖6所示)，體積可直接根據(jù)模型尺寸用圓錐體體積公式(如式5所示)計算獲得(詳見表3)，并可作為似真值使用

(5)

式中，r是圓錐模型底半徑；h是圓錐模型高度；V是圓錐模型體積。

圖1 點云數(shù)據(jù)及其切片示意圖Fig.1 Diagram of the point cloud data and its slicing

圖2 平面點云外輪廓多邊形形態(tài)示意圖Fig.2 The shape of the contour polygon of the slice point cloud

圖3 圓錐模型、尺寸及點云數(shù)據(jù)Fig.3 Conical model, size and its point cloud data

圖4 石獅實物圖及其整體與墩臺點云數(shù)據(jù)Fig.4 Physical map and point cloud data of stone lion, and the point cloud data of the stone lion base

因為模型尺寸可以精確量算，因此，由模型尺寸和式(5)計算所得的圓錐體模型體積值真實、可靠，可作為圓錐的體積真值看待和使用。而通過與圓錐體體積近似值，即點云方式體積計算值的比較，則既能對形態(tài)規(guī)則的圓錐體點云體積計算方法可行性進行判斷，也能對體積計算算法正確性進行驗證。墩臺是不規(guī)則的幾何形體，其精確幾何尺寸未知，但當墩臺切割間距為最小分辨率時，用驗證過并證明為正確的“切片法”算法計算求得的墩臺點云體積值就可以作為近似真值看待；當然，用“切段法”也能計算墩臺點云的體積，并可與“切片法”進行比較以進一步判斷和驗證兩種點云體積計算算法的效率優(yōu)劣和適用情況。

圖5 三維激光掃描對象點云數(shù)據(jù)處理流程Fig.5 Flow charts of 3D laser scanning point cloud data processing

表1 圓錐模型直徑d兩種方法的量測結(jié)果

表2 圓錐體模型高度h的量算結(jié)果

圖6 圓錐模型尺寸與體積Fig.6 Geometric size measurement of conical model

表3 圓錐模型尺寸與體積

2.1 圓錐體體積計算

2.1.1 圓錐體點云數(shù)據(jù)體積計算

以正軸、橫軸和斜軸(如圖7(a)—7(c)所示)3種方式檢驗點云“切片法”和“切段法”的正確性和效能。首先，在點云縱向最小值0與最大值H之間，進行對象點云切片，依次得到系列水平點云切片Si；其次，使用雙向最近點搜索法確定點云外輪廓邊界多邊形Pi；再次，分別計算Pi圍成的面積，即點云切片Si的面積Ai；最后，累加Ai并乘以h得到三維激光掃描的圓錐的體積。

圖7 圓錐體三軸體積計算示意圖 Fig.7 Diagram of conical volume calculation in three directions

2.1.2 圓錐體體積計算結(jié)果分析

分別用“切片法”與“切段法”計算正軸、橫軸與斜軸3種工況下的圓錐體點云的體積(詳見表4—6)。

表4 正軸圓錐體切片(切段)計算結(jié)果對比分析

由表4數(shù)據(jù)可知：①兩種方法的兩種誤差與切距大小均成正比；②計算用時切片法與切距成反比，切段法與切距成正比，而在最小切距時，兩者用時相當。

表5 橫軸圓錐體切片(切段)計算結(jié)果對比分析

由表5數(shù)據(jù)可知：①兩種方法都保持間距小、精度高的基本趨勢；②雖然當切距最小時，切片法計算用時最長，切段法計算用時最短，但任何情況下切片法效率都優(yōu)于切段法；③對規(guī)則圓錐模型而言，誤差較正軸時均大幅減少，說明橫軸是更好的切割姿態(tài)。

表6 斜軸(α=50°)圓錐體切片(切段)計算結(jié)果對比分析

由表6數(shù)據(jù)可知：①兩種方法都保持了間距小、精度高的特點；②間距越小，切片法計算用時越長，切段法計算用時反而越短，任何情況下切片法效率都高于切段法；③誤差大小與橫軸時大致相當，說明斜軸(50°)是可以接受的切割姿態(tài)。

對比分析可知：因圓錐模型體積似真值(即公式計算值，如表3所示)與點云體積計算值(如表4—6所示)足夠接近，再結(jié)合算法分析與精度效率試驗結(jié)果(詳見表4—6,圖8)，可以認定“切片法”算法可行、結(jié)果正確且計算高效。

2.2 墩臺柱體體積計算

2.2.1 墩臺柱體點云數(shù)據(jù)體積計算

用激光掃描儀獲取墩臺柱體三維點云坐標數(shù)據(jù)；分別用“切片法”與“切段法”計算正軸、橫軸與斜軸(如圖9(a)—9(c)所示)3種工況下的墩臺柱體點云體積。

2.2.2 墩臺柱體體積計算結(jié)果分析

以正軸、橫軸和斜軸(見表7—9，圖10)3種方式檢驗點云“切片法”和“切段法”的計算效率與適用性(表中墩臺皆以“切片法”正軸1 mm切距時的點云體積計算結(jié)果473 142 270 mm3為似真值進行計算和比對分析)。

由表7數(shù)據(jù)可知：①兩種方法的兩種誤差與切距大小都成正比；②計算用時切片法與切距成反比，切段法與切距成正比，而在最小切距時，用時兩者相當。

由表8數(shù)據(jù)可知：①間距變化與切片(切段)數(shù)變化相反；②間距變化與絕對誤差和相對誤差變化紊亂；③間距與切片法用時成反比，與切段法用時成正比。

圖8 兩種方法圓錐體積計算精度與效率走勢圖Fig.8 Calculation accuracy and efficiency charts of cone volume in two methods

圖9 墩臺三軸體積計算示意圖Fig.9 Diagram of stone lion base volume calculation in three directions

表7 正軸墩臺切片(切段)計算結(jié)果對比分析

表8 橫軸墩臺切片(切段)計算結(jié)果對比分析

表9 斜軸(α=50°)墩臺切片(切段)計算結(jié)果對比分析

由表9中數(shù)據(jù)可見：①間距變化與絕對誤差和相對誤差變化一致；②間距變化與切片法用時成反比，與切段法用時成正比；③誤差與軸向的關(guān)系：誤差均勻，各軸向均適宜。

由表7—9和圖10可知：“切片法”在精度和效率上均優(yōu)于“切段法”，且隨著切距的增大，優(yōu)勢持續(xù)擴大。

3 討 論

3.1 試驗綜述

圓錐、墩臺兩種對象，3種工況下的點云體積算例計算結(jié)果(如表4—表9、圖8、圖10所示)表明：

(1) “切片法”的計算結(jié)果更接近真值，算法正確性和可靠性不僅與前述理論分析一致，而且得到了試驗數(shù)據(jù)的有效驗證；

(2) 從時間上看，相同切距條件下，“切片法”的計算用時更短，說明計算流程簡約的“切片法”算法效率更高、更有效；

(3) 點云切距大小可控，又與精度有關(guān)的事實說明，點云體積計算的精度可由切距大小控制，即切距越小精度越高，切距越大精度越低。

因此，計算正確、流程簡潔、結(jié)果可靠、算法高效、精度可控的“切片法”，不僅全面優(yōu)于“切段法”，而且適用性更強，能夠解決不規(guī)則體體積計算的難題，當然前提是該不規(guī)則體對象可用三維激光掃描儀進行整體掃描，且在點云數(shù)據(jù)處理時應(yīng)顧及并選擇多個方向切割、計算并相互印證為好。

3.2 誤差分析

“切片法”在切片間距之間出現(xiàn)點云形態(tài)極端變化時，體積計算可能因補償性(即某種不確定的隨機性差異互補性)或其他不確定性，而造成切距小、誤差反倒大的反常情況出現(xiàn)(如表5“切片法”中1 mm切距的誤差反倒比2 mm的誤差大，表6中也有類似反?，F(xiàn)象，且更為明顯)，因而誤差小即精度高不足以說明準確度高，但在沒有補償或補償?shù)炔淮_定性因素影響不明顯情況下間距小準確度高則基本是可以肯定的，即無論切段間距還是切片間距越小，體積計算精度越高，結(jié)果也越可靠。

對規(guī)則圓錐體而言，正軸時“放大效應(yīng)”這種系統(tǒng)性偏差會更大(1 mm間距都能差到5%以上)，產(chǎn)生此情形的原因是圓錐體出現(xiàn)了圓柱化現(xiàn)象，且可能在圓錐體正軸時達到極點，這說明切割方向很重要。

另外，墩臺體點云體積橫軸切片或切段計算可能出現(xiàn)誤差的原因是由于沿橫軸切割會出現(xiàn)一個切片(切段)上有兩個或以上多邊形切片(或段塊)單元即所謂“多環(huán)[30]”的情況，從而導致前述切片(或段塊)面積偏離實際甚至錯誤的結(jié)果(如圖1(b)中S7、圖10(c)及圖11所示)。

4 結(jié) 論

本文提出的“切片法”用雙向最近點搜索的方式，消除了平面點云“形態(tài)畸變”的隱患；用切片計算體積的技術(shù)路線，根除了三重“放大效應(yīng)”的弊端；用行列式模型法計算點云切片面積的辦法，解決了面積算法適用性不足的問題；用柱體體積計算方式計算點云體積的方式，確保了對象體積計算的正確。因此，從流程算法入手的“切片法”，不僅使高效、精確計算不規(guī)則體的體積成為可能，而且能夠解決特定條件下不規(guī)則體的點云體積計算問題。

理論分析和算例結(jié)果一致表明，點云體積計算是不規(guī)則體體積計算的有效方式，“切片法”易于編程實現(xiàn)、推廣應(yīng)用前景廣闊，整體優(yōu)于“切段法”。但所遺留的多環(huán)問題尚有待繼續(xù)探索，可以預見的基本思路是：首先，進行聚類分析[1]以區(qū)分多環(huán)；其次，待截面多環(huán)個數(shù)及各環(huán)切片邊界依次正確確定后，逐一進行截面各環(huán)切片面積的計算；最后，依據(jù)切割順序逐環(huán)理清各環(huán)切片縱向?qū)?yīng)關(guān)系，再設(shè)法解決三維激光掃描對象點云體積先分部、后整體的計算問題。此過程較為復雜，既需要前述工作成果作為基礎(chǔ)，也需要破解許多新問題，這些都有待跟進并可望解決。

點云體積計算方法從“切段法”演進到“切片法”，標志著基于三維激光掃描的不規(guī)則體對象體積計算的方式方法從有到好、走向成熟。