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

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

1. 長安大學地質工程與測繪學院，陜西 西安 710054； 2. 西部礦產資源與地質工程教育部重點實驗室，陜西 西安 710054； 3. 陜西國防工業職業技術學院，陜西 西安 710300

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

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

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

1 點云切片法

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

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

(2) 點云數據切片。在點云縱向最小值0與最大值H之間，用一組(設為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是切片數減1；x、y、z是點云點坐標。

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

1.1 輪廓邊界確定

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

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

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

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

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

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

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

1.2 切片面積計算

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

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

(4)

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

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

1.3 要點與優勢

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

2 點云體積計算

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

(5)

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

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

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

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

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

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

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

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

表2 圓錐體模型高度h的量算結果

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

表3 圓錐模型尺寸與體積

2.1 圓錐體體積計算

2.1.1 圓錐體點云數據體積計算

以正軸、橫軸和斜軸(如圖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 圓錐體體積計算結果分析

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

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

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

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

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

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

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

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

2.2 墩臺柱體體積計算

2.2.1 墩臺柱體點云數據體積計算

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

2.2.2 墩臺柱體體積計算結果分析

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

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

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

圖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 正軸墩臺切片(切段)計算結果對比分析

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

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

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

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

3 討 論

3.1 試驗綜述

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

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

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

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

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

3.2 誤差分析

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

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

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

4 結 論

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

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

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