不規(guī)則物體點(diǎn)云切片中的多輪廓分割算法

張瑾，徐文，周宇喬，劉凱*

不規(guī)則物體點(diǎn)云切片中的多輪廓分割算法

張瑾1，徐文1，周宇喬2，劉凱1*

（1.四川大學(xué) 電氣工程學(xué)院，成都 610065； 2.綠色化學(xué)與技術(shù)教育部重點(diǎn)實驗室（四川大學(xué)），成都 610064）（ ? 通信作者電子郵箱kailiu@scu.edu.cn）

使用切片法進(jìn)行不規(guī)則物體點(diǎn)云體積測量時，現(xiàn)有的多邊形拆分再重組（PSR）算法難以正確拆分較近的輪廓，進(jìn)而導(dǎo)致計算精度較低。針對這一問題，提出一種多輪廓分割算法——改進(jìn)最近點(diǎn)搜索（INPS）算法。首先，通過局部點(diǎn)的單次使用原則分割多輪廓；其次，使用多邊形內(nèi)點(diǎn)判定（PIP）算法判斷輪廓的包含關(guān)系，以確認(rèn)輪廓面積的正負(fù)；最后，采用切片面積乘以厚度并累加的方式獲取不規(guī)則物體點(diǎn)云的體積。實驗結(jié)果表明，在兩個公開點(diǎn)云數(shù)據(jù)集和一個化學(xué)電子密度等值面點(diǎn)云數(shù)據(jù)集上，所提算法都能實現(xiàn)高正確率的邊界分割，具有一定的普適性；且該算法體積測量的平均相對誤差為0.043 6%，低于PSR算法的0.062 7%，可見所提算法實現(xiàn)了高正確率的邊界分割。

點(diǎn)云體積測量；點(diǎn)云切片；多輪廓分割；多邊形內(nèi)點(diǎn)判定算法；最近點(diǎn)搜索法

0 引言

體積是三維空間中物體的重要屬性參數(shù)［1］，體積計算是空間中對象形態(tài)分析的基本內(nèi)容［2］，涉及規(guī)則幾何體和不規(guī)則幾何體。其中，不規(guī)則幾何體的體積測量，因為它的形態(tài)各異，無法歸納普適的計算方法，仍是普遍面臨且亟待解決的現(xiàn)實難題［3］。三維激光掃描的方式可以快速獲取包含物體表面結(jié)構(gòu)信息的點(diǎn)云數(shù)據(jù)，由此得到對象的三維封閉曲面模型或者多層二維輪廓邊界，這兩種方法均可計算不規(guī)則物體體積，即逆向建模法和切片法技術(shù)路線。前者體積計算準(zhǔn)確可靠，但需要經(jīng)過掃描階段、點(diǎn)云階段和曲面擬合階段才能生成目標(biāo)模型［4］，而且需要進(jìn)行拓?fù)錂z查和孔洞填充等操作［5］，計算過程耗費(fèi)資源和時間；后者將一個三維曲面問題簡化成了多個二維曲線問題，降低了空間復(fù)雜度，以犧牲小部分精度的代價大幅減少了計算時間。因此，切片法因具有直觀和易于編程實現(xiàn)的優(yōu)勢，被廣泛地應(yīng)用于工程項目中，如不規(guī)則樹冠體積測量［6］、商品包裝體積測量［7］、油罐和洞庫容量計量［8］和船舶排水量計量［9］等諸多領(lǐng)域。此外，在計算化學(xué)理論研究領(lǐng)域，針對分子范德瓦爾表面上靜電勢的研究可以用于預(yù)測反應(yīng)位點(diǎn)，預(yù)測分子性質(zhì)，解釋分子間弱相互作用；而分子范德瓦爾表面（后文稱為分子電子密度等值面）的體積是一個重要參數(shù)，本文中使用Multiwfn［10］得到分子電子密度格點(diǎn)數(shù)據(jù)和靜電勢格點(diǎn)數(shù)據(jù)，經(jīng)過處理得到相應(yīng)點(diǎn)云［10-11］。

切片法測量體積的流程可以概括為獲取點(diǎn)云數(shù)據(jù)、點(diǎn)云數(shù)據(jù)切片、切片上點(diǎn)云投影、多輪廓分割及包含關(guān)系判斷、點(diǎn)云片面積計算和點(diǎn)云體積計算這6個步驟。其中，切片面積計算需要正確排序截面上無規(guī)則的點(diǎn)，生成輪廓邊界，是得到正確體積值的關(guān)鍵。現(xiàn)有的邊界排序算法中，極坐標(biāo)排序法［9］不適用于極端凹多邊形，點(diǎn)云輪廓提取法易擴(kuò)大輪廓體積［12］，依據(jù)最小夾角原則的輪廓排序法［13］和凹包點(diǎn)內(nèi)插法［14］在面對復(fù)雜輪廓情況時仍會出錯，雙向最近點(diǎn)搜索法［3，15］表現(xiàn)較好，但仍然和前兩者一樣局限于如墩臺、儲油罐和船舶等單一輪廓邊界排序。使用先分類后排序思想時，-means聚類［16］、譜聚類［17］等需要事先已知分類個數(shù)的算法不適用于此類情況。使用數(shù)字圖像方法可以分割多個輪廓，但它們對格柵大小的要求嚴(yán)格，且兩次矢柵轉(zhuǎn)換會引入新的誤差［18］。多邊形拆分再重組（Polygon Splitting and Recombination， PSR）算法［19］雖然可以區(qū)分多個輪廓，但當(dāng)切片上存在較多輪廓隨機(jī)分布時，基于統(tǒng)計學(xué)方法對異常邊拆分的方式的可靠性會較低。

針對以上不足，本文提出改進(jìn)最近點(diǎn)搜索（Improved Nearest Point Search， INPS）算法。首先，通過局部點(diǎn)的單次使用原則分割多輪廓；其次，使用多邊形內(nèi)點(diǎn)判定（Point Inclusion in Polygon， PIP）算法［20］判斷輪廓的包含關(guān)系，確認(rèn)輪廓面積的正負(fù)；最后，采用切片乘以厚度并累加的方式得到點(diǎn)云的體積，即不規(guī)則物體體積。

1 基本原理

本文算法最初針對分子電子密度等值面點(diǎn)云，該類點(diǎn)云的形狀輪廓相對簡單，但在實際的分層中，截面上會出現(xiàn)數(shù)量偏多且隨機(jī)分布的輪廓邊界。本文選擇手性雙氮氧金屬配合物催化劑與底物結(jié)合模型電子密度等值面點(diǎn)云（簡稱Cat6點(diǎn)云）作為實驗對象，它的表面變化大，分層情況復(fù)雜，如圖1所示。

圖1　實驗點(diǎn)云Cat6

圖2　分子電勢點(diǎn)云生成流程

點(diǎn)云數(shù)據(jù)是計算的基礎(chǔ)，它的獲取途徑通常是三維激光掃描，本文數(shù)據(jù)和激光掃描得到的數(shù)據(jù)的分層方式不同。

對于激光掃描數(shù)據(jù)，它的分層數(shù)為：

對于分子電子密度等值面點(diǎn)云，它的分層數(shù)為：

1.1　點(diǎn)云數(shù)據(jù)切片

MC算法的基本思想如下：遍歷格點(diǎn)數(shù)據(jù)中所有的體素（由8個點(diǎn)構(gòu)成的長方體），根據(jù)它的頂點(diǎn)值與等值面閾值的關(guān)系，將它歸類到15種關(guān)系之一［21］，通過插入三角形重建物體的表面。取圖2（b）中分子等值面點(diǎn)云頂部兩層，通過觀察電子密度格點(diǎn)點(diǎn)云中等值面內(nèi)部的點(diǎn)與重建后等值面上的點(diǎn)之間的位置關(guān)系，歸納針對此類點(diǎn)云的一種切片上投影點(diǎn)的預(yù)處理方法，可以有效去除非輪廓上的點(diǎn)，流程如圖3所示。

圖3（a）中紅色點(diǎn)表示格點(diǎn)點(diǎn)云在曲面內(nèi)的點(diǎn)，藍(lán)色點(diǎn)表示重建后的電子密度等值面點(diǎn)云，圖3（b）為圖3（a）中黑框所示的頂部兩層的點(diǎn)云，重建后的藍(lán)色點(diǎn)與紅色點(diǎn)重合或者在紅色點(diǎn)外部。兩層紅點(diǎn)之間散落著一些藍(lán)色點(diǎn)，這是通過MC算法插值得到的三角形的頂點(diǎn)。圖3（c）是連接這些三角形后的示意圖。圖3（d）是俯視視角示意圖，其中綠色線段是觀察子圖3（c）畫出的輪廓線。可以看出，輪廓線上的點(diǎn)均沒有落在棋盤格點(diǎn)上（沿軸方向投影，格點(diǎn)文件某一層的點(diǎn)呈現(xiàn)類似于圍棋棋盤格點(diǎn)的分布），圖3（e）中列出的幾種邊界處體素的情況可用于解釋。其中，綠色點(diǎn)表示格點(diǎn)點(diǎn)云在等值面外的點(diǎn)，根據(jù)它們的分布，在體素內(nèi)插入不同數(shù)量和位置的三角形，并將三角形沿軸方向投影，落在棋盤格點(diǎn)上的點(diǎn)均處于體素上下兩層間的棱上，而構(gòu)成輪廓線的點(diǎn)正是那些在體素上下兩層面上的點(diǎn)。

圖3　MC算法處理后的輪廓線示意圖

因此，針對由MC算法得到的點(diǎn)云，按照式（4）分層后，再將落在棋盤格點(diǎn)上的點(diǎn)剔除，從而得到高質(zhì)量的輪廓線，從上述點(diǎn)云中選取其中3層，展示輪廓分布情況，如圖4所示。

圖4　具有代表性的兩層切片點(diǎn)云投影

1.2　多輪廓分割

最近點(diǎn)搜索法和雙向最近搜索法的搜索策略是連接平面上所有的點(diǎn)，因此這兩種方法都無法區(qū)分多個輪廓。本文提出的INPS是基于局部點(diǎn)單次使用原則區(qū)分不同輪廓：對于一個理想的輪廓點(diǎn)集，每一個點(diǎn)只需和距離自身最近的兩個點(diǎn)連接，得到一個閉合的輪廓線。因此，當(dāng)一個點(diǎn)附近的所有點(diǎn)均已被使用（即進(jìn)行過連接），則判斷已經(jīng)完成一次輪廓連接，并從下一個未使用過的點(diǎn)開始連線。具體步驟如下：

4）判斷是否完成所有輪廓搜索。若還有未使用點(diǎn)，重復(fù)步驟1），否則輪廓搜索結(jié)束。

圖5　INPS算法進(jìn)行點(diǎn)集分割

圖6　經(jīng)INPS算法處理后的輪廓線

1.3　截面面積計算

精確的截面面積計算決定了不規(guī)則物體體積計算的準(zhǔn)確度，而輪廓之間包含關(guān)系的正確判斷，是截面面積精確計算的關(guān)鍵。點(diǎn)云切片中的輪廓只應(yīng)存在包含和相離兩種位置關(guān)系，判斷方法如圖7所示，常見的分布情況如圖8所示。INPS算法的判斷思路是：首先，使用高斯面積公式［1］計算各個輪廓的面積；其次，使用PIP算法判斷輪廓間的位置狀態(tài)，判斷每個輪廓和除自己以外的輪廓之間的包含關(guān)系，若該輪廓被其他輪廓包含，則記錄該輪廓被包含數(shù)加1；最后通過式（12）判斷輪廓面積正負(fù)。

其中表示輪廓被包含的次數(shù)。

圖8　多輪廓位置關(guān)系

在圖7中，使用INPS算法將點(diǎn)集分為3個輪廓點(diǎn)集，分別用圓形、三角形和正方形表示。判斷三角形點(diǎn)集和正方形點(diǎn)集是否被圓形點(diǎn)集包含，只需要從每個點(diǎn)集中任選一個點(diǎn)，找到圓形輪廓線中與該點(diǎn)相交的線段，確定線段的方向（例如從軸方向小值指向大值），然后計算點(diǎn)與線段法向量的乘積。若所有值的乘積為負(fù)數(shù)，則被包含；反之則不包含。圖8中輪廓2只被輪廓1包含，因此面積為負(fù)數(shù)，而輪廓3被包含2次，面積仍為正。

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

逆向建模法計算得到的體積準(zhǔn)確可靠，可以作為本文點(diǎn)云體積的真值，作為改進(jìn)算法的檢驗依據(jù)。因此，本文使用Geomagic Wrap 2017軟件計算點(diǎn)云體積真值和截面面積真值。實驗基于Matlab語言實現(xiàn)了INPS算法和多邊形拆分再重組（PSR）算法［19］，并對比分析了使用場景和計算精度。

2.1　分子電子密度點(diǎn)云

針對分子電子密度等值面點(diǎn)云，對比INPS算法和PSR算法［19］的結(jié)果。表1為Cat6點(diǎn)云數(shù)據(jù)信息，使用兩種算法時，PSR算法和INPS算法的輪廓分割系數(shù)分別為2.5、3.0。使用PSR算法時，6個位置數(shù)據(jù)下的標(biāo)準(zhǔn)差與分割閾值見表2。選取Cat6點(diǎn)云在3個方向上具有代表性的3個位置進(jìn)行展示，沿3個方向投影的平面均命名為，結(jié)果如圖9～11所示。通過觀察發(fā)現(xiàn)沿軸切片時，輪廓的情況最復(fù)雜，數(shù)量多且隨機(jī)分布，因此重點(diǎn)分析該方向。針對Cat6點(diǎn)云的6個切片位置，使用Geomagic Wrap計算得到的面積作為真值，誤差分析結(jié)果見表3。

表1　Cat6點(diǎn)云數(shù)據(jù)信息

表2　PSR算法中的標(biāo)準(zhǔn)差與分割閾值

表3　Cat6點(diǎn)云不同切片位置處截面面積計算結(jié)果對比（Z軸）

圖9　Cat6點(diǎn)云在不同切片位置（Z軸）的輪廓分割結(jié)果對比

圖10　Cat6點(diǎn)云在不同切片位置（Y軸）的輪廓分割結(jié)果對比

圖11　Cat6點(diǎn)云不同切片位置（X軸）的輪廓分割結(jié)果對比

2.2　公開點(diǎn)云數(shù)據(jù)集

為驗證算法的有效性和魯棒性，使用三維激光掃描公開數(shù)據(jù)集（由斯坦福大學(xué)計算機(jī)圖形學(xué)實驗室公布）中Stanford Bunny和Happy Buddha（如圖12所示）進(jìn)行實驗。

圖12　實物和三維曲面模型

由于原始點(diǎn)云密度較低，造成切片質(zhì)量差，因此對原始點(diǎn)云上采樣。先使用移動最小二乘法（Moving Least Squares， MLS）對三維點(diǎn)云進(jìn)行平滑擬合，然后重采樣。與分子點(diǎn)云相比，Stanford Bunny和Happy Buddha這兩組數(shù)據(jù)單一輪廓的邊界形狀更復(fù)雜，但切片上的輪廓數(shù)較少。

兩組點(diǎn)云的數(shù)據(jù)信息、分層間隔和輪廓分割系數(shù)取值如表4所示，處理后的結(jié)果如圖13～14所示（其中PSR算法的效果圖可參考文獻(xiàn)［19］），3個切片位置處面積的相對誤差結(jié)果如表5所示。

圖13　Stanford Bunny點(diǎn)云在不同切片位置（Z軸）的輪廓分割結(jié)果對比

表4　兩組點(diǎn)云數(shù)據(jù)處理中的參數(shù)

表5　PSR和INPS算法對Stanford Bunny 和Happy Buddha點(diǎn)云中6個截面的面積誤差對比

圖14　Happy Buddha點(diǎn)云在不同切片位置（Z軸）的輪廓分割結(jié)果對比

2.3　切片多輪廓分割

根據(jù)上述實驗結(jié)果，可以得出以下結(jié)論。

1）適用性。無論是針對MC算法處理后的點(diǎn)云，還是針對激光掃描得到的點(diǎn)云，INPS算法均表現(xiàn)了良好的輪廓分割效果，截面面積的誤差也大致相同。從圖9（a）可知，在針對分子電勢點(diǎn)云時，與PSR算法相比，INPS算法的誤連情況更少。在公開數(shù)據(jù)集上，INPS算法的效果和PSR算法的效果相當(dāng)。

2）魯棒性。在圖9中，相較于PSR算法，INPS算法更加穩(wěn)定。如圖9（b）所示，PSR算法都出現(xiàn)了不同程度的誤連，這是因為在這3幅圖中，輪廓數(shù)量多，輪廓之間誤連的線段也相應(yīng)增多，計算得到的標(biāo)準(zhǔn)差偏大，導(dǎo)致一些距離較近的輪廓之間的誤連線段難以被剔除，此時對式（9）中系數(shù)的選擇條件較為苛刻。INPS算法的優(yōu)勢是，在輪廓中一點(diǎn)的搜索范圍內(nèi)，只要距離仍在該輪廓中一點(diǎn)的距離小于到其他輪廓任意點(diǎn)的距離，就不會出現(xiàn)誤連，即使是在截面投影點(diǎn)質(zhì)量較差的情況，也幾乎不存在誤連的情況，如圖13～14所示。同時，INPS算法對于一個輪廓搜索完成的判定條件，使得對于系數(shù)的選擇也更寬松。

2.4　點(diǎn)云體積計算

1）準(zhǔn)確性。

PSR和INPS算法針對3組點(diǎn)云的誤差都在0.1%內(nèi)，并且本文算法的誤差均低于PSR算法，其中，INPS算法的平均相對誤差為0.043 6%，低于PSR算法的0.062 7%。如在圖9中，PSR算法針對個別距離較近的輪廓沒有糾正誤連線段，導(dǎo)致該截面處輪廓的面積計算偏大。從表6可知，針對Cat6點(diǎn)云體積計算，INPS算法得到的體積小于PSR算法得到的體積，這也和實際情況符合。

2）高效性。

從算法的流程分析，由于PSR算法是基于雙向最近點(diǎn)搜索法的改進(jìn)算法，在最開始需要使用雙向最近點(diǎn)搜索法排序截面中所有的點(diǎn)，而INPS算法在同樣的排序過程中已經(jīng)將點(diǎn)分類。這是因為INPS算法在對點(diǎn)排序的同時，根據(jù)伴隨該點(diǎn)排序得到的數(shù)據(jù)也對點(diǎn)分類；而PSR算法更關(guān)注根據(jù)統(tǒng)計學(xué)數(shù)據(jù)拆分長度異常邊，然后重組。因此，INPS算法在復(fù)雜度上低于PSR算法，并且實驗結(jié)果也驗證了INPS算法正確率略高于PSR算法。

表6　PSR和INPS算法對3組數(shù)據(jù)體積測量結(jié)果的對比

2.5　誤差分析

1）輪廓線不正確。針對公開點(diǎn)云數(shù)據(jù)集，使用投影的方法得到輪廓點(diǎn)時，難免出現(xiàn)局部點(diǎn)密度過大或過小的情況，導(dǎo)致無法反映真實的輪廓線，引入誤差；而使用MC算法處理的點(diǎn)云，由于它的數(shù)據(jù)特征，與投影的方法相比，可以很大程度避免此類誤差。

2）自相交。一個正確的輪廓線不存在其中某兩條線段交叉的情況，但在點(diǎn)分布不規(guī)則的局部，可能會出現(xiàn)輪廓線相交的情況［25］。

3）使用截面面積乘以厚度模擬不規(guī)則物體在該處體積本身就存在一定的誤差，并且該誤差具有不確定性，可能會隨機(jī)地互補(bǔ)，并且沿著切片的累加積累。

3 結(jié)語

本文提出了一種改進(jìn)的基于最近點(diǎn)搜索法的多輪廓分割算法，并與多邊形拆分再重組算法進(jìn)行實驗對比。實驗結(jié)果表明，本文算法針對特定數(shù)據(jù)和公開數(shù)據(jù)集均能出色地完成多輪廓的分割，具有普適性和良好的抗干擾性；并且當(dāng)存在多個輪廓隨機(jī)分布時，本文算法的分割效果優(yōu)于多邊形拆分再重組算法。因為此時根據(jù)統(tǒng)計學(xué)分割異常邊的可靠性較低，而本文算法的判斷方式（局部點(diǎn)單次使用原則）更加貼合人為分割輪廓時的思維方式，故抗干擾能力更強(qiáng)。相較于多邊形拆分再重組法，采用本文算法計算體積的正確率略高（針對3組數(shù)據(jù)的相對誤差分別是0.075 3%、0.033 0%和0.022 6%），且具有更強(qiáng)的魯棒性和更小的算法復(fù)雜度。但是本文算法仍存在不足，針對公開數(shù)據(jù)集，沒有可靠的投影方案，若使用點(diǎn)云密度相關(guān)的投影厚度，則無法自適應(yīng)地選取合適的投影厚度。在后續(xù)工作中，針對不同密度的點(diǎn)云，為了得到更高質(zhì)量的輪廓點(diǎn)，我們將研究如何實現(xiàn)普適性更強(qiáng)的自適應(yīng)截面點(diǎn)投影算法。

[1] 郭仁忠. 空間分析［M］. 2版. 北京：高等教育出版社， 2001： 143-145.（GUO R Z. Spatial Analysis［M］. 2nd ed. Beijing： Higher Education Press， 2001： 143-145.）

[2] ANDERSEN H E. Estimation of critical forest structure metrics through the spatial analysis of airborne laser scanner data［D］. Seattle， WA： University of Washington， 2003： 197-202.

[3] 劉明學(xué)，崔進(jìn)業(yè). 基于點(diǎn)云三維坐標(biāo)數(shù)據(jù)計算復(fù)雜物體體積［J］. 測繪地理信息， 2018， 43（3）： 96-98.（LI M X， CUI J Y. Calculate volume of complex objects based on 3D coordinates of points cloud data［J］. Journal of Geomatics， 2018， 43（3）： 96-98.）

[4] 魏言標(biāo)，鄭磊，薛少兵，等. 基于三坐標(biāo)測量和3D掃描的凸輪逆向建模設(shè)計［J］. 機(jī)械設(shè)計， 2021， 38（9）： 71-74.（WEI Y B， ZHENG L， XUE S B， et al. Reverse modeling design of the cam based on three-coordinate measurement and 3D scanning［J］. Journal of Machine Design， 2021， 38（9）： 71-74.）

[5] 王鑫龍，孫文磊，張建杰，等. 基于點(diǎn)云數(shù)據(jù)的逆向工程技術(shù)研究綜述［J］. 制造技術(shù)與機(jī)床， 2018（2）： 49-53.（WANG X L， SUN W L， ZHANG J J， et al. Review on reverse engineering research based on point cloud data［J］. Manufacturing Technology and Machine Tool， 2018（2）： 49-53.）

[6] 董亞涵，李永強(qiáng)，李鵬鵬，等. 基于改進(jìn)凸包算法的樹冠輪廓點(diǎn)提取與體積計算［J］. 測繪工程， 2018， 27（8）： 66-71.（DONG Y H， LI Y Q， LI P P， et al. Tree crown outline points extracting and volume calculation based on improved convex hull algorithm［J］. Engineering of Surveying and Mapping， 2018， 27（8）： 66-71.）

[7] 陳琛，李寶順，包亞萍. 基于光柵投影和點(diǎn)云體積計算的過度包裝檢測系統(tǒng)［J］. 計算機(jī)測量與控制， 2014， 22（12）： 3919-3922.（CHEN C， LI B S， BAO Y P. Excessive packaging detection system based on point set volume calculation method and grating projection［J］. Computer Measurement and Control， 2014， 22（12）： 3919-3922.）

[8] 呂小寧，劉曉麗，段云嶺，等. 地下能源儲庫群容積激光測量方法及現(xiàn)場實驗［J］. 中國激光， 2016， 43（10）： No.1004002.（LYU X N， LIU X L， DUAN Y L， et al. Laser measurement method and in-situ experiment of underground energy storage caverns volume［J］. Chinese Journal of Lasers， 2016， 43（10）： No.1004002.）

[9] 張吉星，程效軍，程小龍. 三維激光掃描技術(shù)在船舶排水量計量中的應(yīng)用［J］. 中國激光， 2016， 43（12）： No.1204003.（ZHANG J X， CHENG X J， CHENG X L. Application of three-dimensional laser scanning technology in measurement of ship displacement［J］. Chinese Journal of Lasers， 2016， 43（12）： No.1204003.）

[10] LU T， CHEN F W. Multiwfn： a multifunctional wavefunction analyzer［J］. Journal of Computational Chemistry， 2012， 33（5）： 580-592.

[11] LU T， CHEN F. Quantitative analysis of molecular surface based on improved Marching Tetrahedra algorithm［J］. Journal of Molecular Graphics and Modelling， 2012， 38： 314-323.

[12] 連強(qiáng)強(qiáng)，顧敏. 基于α-shape的三維激光點(diǎn)云計算樹冠體積的研究［J］. 青海大學(xué)學(xué)報， 2020， 38（5）： 74-79.（LIAN Q Q， GU M. Research on the calculation of tree crown volume by 3D laser point cloud based on α-shape［J］. Journal of Qinghai University， 2020， 38（5）： 74-79.）

[13] 付敬帥，李斌. 基于點(diǎn)云截面數(shù)據(jù)點(diǎn)的多輪廓排序算法［J］. 河南科學(xué)， 2019， 37（6）： 933-937.（FU J S， LI B. Multi-contour sorting algorithm based on point cloud cross-section data points［J］. Henan Science， 2019， 37（6）： 933-937.）

[14] 程效軍，熊鑫鑫，楊澤鑫，等. 基于地面激光雷達(dá)的洞庫容量計量［J］. 激光與光電子學(xué)進(jìn)展， 2019， 56（23）： No.231201.（CHENG X J， XIONG X X， YANG Z X， et al. Cavern capacity calculation using terrestrial lidar［J］. Laser and Optoelectronics Progress， 2019， 56（23）： No.231201.）

[15] 錢錦鋒，陳志楊，張三元，等. 點(diǎn)云數(shù)據(jù)壓縮中的邊界特征檢測［J］. 中國圖象圖形學(xué)報， 2005， 10（2）： 164-169.（QIAN J F， CHEN Z Y， ZHANG S Y， et al. The detection of boundary point of point cloud compression［J］. Journal of Image and Graphics， 2005， 10（2）： 164-l69.）

[16] JAIN A K. Data clustering： 50 years beyond K-means［J］. Pattern Recognition Letters， 2010， 31（8）： 65l-666.

[17] NG A Y， JORDAN M I， WEISS Y. On spectral clustering analysis and an algorithm［C］// Proceedings of the 14th International Conference on Neural Information Processing Systems： Natural and Synthetic. Cambridge： MIT Press， 2001 ：849-856.

[18] 程效軍，方芳. 基于形態(tài)學(xué)的散亂點(diǎn)云輪廓特征線提取［J］. 同濟(jì)大學(xué)學(xué)報（自然科學(xué)版）， 2014， 42（11）： 1738-1743.（CHENG X J， FANG F. Morphology-based scattered point cloud contour extraction［J］. Journal of Tongji University （Natural Science）， 2014， 42（11）： 1738-1743.）

[19] 劉金錦，李浩軍. 基于點(diǎn)云切片改進(jìn)法的不規(guī)則物體體積測量［J］. 光學(xué)學(xué)報， 2021， 41（23）： No.2312003.（LIU J J， LI H J. Volume measurement of irregular objects based on improved point cloud slicing method［J］. Acta Optica Sinica， 2021， 41（23）： No.2312003.）

[20] HAINES E. Point in polygon strategies［M］// HECKBERT P S. Graphics Gems IV. San Diego， CA： Academic Press， 1994： 24-46.

[21] LORENSEN W E， CLINE H E. Marching cubes： a high resolution 3D surface construction algorithm［J］. ACM SIGGRAPH Computer Graphics， 1987， 21（4）：163-169.

[22] LIU K， RAN X， GONG J， et al. Extending epipolar geometry for real-time structured light illumination Ⅱ： lossless accuracy［J］. Optics Letters， 2021， 46（4）： 837-840.

[23] JIA M， YANG X， LIU K. Automatically detecting rigidly and nonrigidly deformed facial landmarks from coarseness to fineness［J］. Journal of Electronic Imaging， 2019， 28（6）： No.063009.

[24] ZHANG G， XU B， LAU D L， et al. Correcting projector lens distortion in real time with a scale-offset model for structured light illumination［J］. Optics Express， 2022， 30（14）： 24507-24522.

[25] 柯映林，王青. 反求工程中的點(diǎn)云切片算法研究［J］. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2005， 17（8）： 1798-1802.（KE Y L， WANG Q. Research on point cloud slicing technique in reverse engineering［J］. Journal of Computer-Aided Design and Computer Graphics， 2005， 17（8）： 1798-1802.）

Multi-contour segmentation algorithm for point cloud slices of irregular objects

ZHANG Jin1， XU Wen1， ZHOU Yuqiao2， LIU Kai1*

（1，，610065，；2，（），610064，）

When using the slicing method to measure the point cloud volumes of irregular objects， the existing Polygon Splitting and Recombination （PSR） algorithm cannot split the nearer contours correctly， resulting in low calculation precision. Aiming at this problem， a multi-contour segmentation algorithm — Improved Nearest Point Search （INPS） algorithm was proposed. Firstly， the segmentation of multiple contours was performed through the single-use principle of local points. Then， Point Inclusion in Polygon （PIP） algorithm was adopted to judge the inclusion relationship of contours， thereby determining positive or negative property of the contour area. Finally， the slice area was multiplied by the thickness and the results were accumulated to obtain the volume of irregular object point cloud. Experimental results show that on two public point cloud datasets and one point cloud dataset of chemical electron density isosurface， the proposed algorithm can achieve high-accuracy boundary segmentation and has certain universality. The average relative error of volume measurement of the proposed algorithm is 0.043 6%， which is lower than 0.062 7% of PSR algorithm， verifying that the proposed algorithm achieves high accuracy boundary segmentation.

volume measurement of point cloud; point cloud slicing; multi-contour segmentation; Point Inclusion in Polygon (PIP) algorithm; nearest point search method

This work is partially supported by Key Research and Development Project of Science and Technology Department of Sichuan Province （22ZDYF3012）， Sichuan Higher Education Talent Training Quality and Teaching Reform Project （JG2021-36）， Sichuan University Science Characteristic Direction Cultivation Program （2020SCUNL204）， Sichuan University Postgraduate Education and Teaching Reform Research Project （GSSCU2021020）.

ZHANG Jin， born in 1998， M. S. candidate. His research interests include point cloud analysis， structured light three-dimensional imaging and its applications.

XU Wen， born in 1992， Ph. D. candidate. Her research interests include structured light three-dimensional imaging and its applications， artificial intelligence.

ZHOU Yuqiao， born in 1988， Ph. D. His research interests include X-ray crystallography， structural chemistry， computational chemistry.

LIU Kai， born in 1973， Ph. D.， professor. His research interests include structured light three-dimensional imaging and its applications， computer vision， digital image/signal processing.

1001-9081（2023）10-3209-08

10.11772/j.issn.1001-9081.2022101536

2022?10?13；

2023?01?10；

四川省科技廳重點(diǎn)研發(fā)項目（22ZDYF3012）；四川省高等教育人才培養(yǎng)質(zhì)量和教學(xué)改革項目（JG2021?36）；四川大學(xué)理科特色方向培育計劃項目（2020SCUNL204）；四川大學(xué)研究生教育教學(xué)改革研究項目（GSSCU2021020）。

張瑾（1998—），男，四川南充人，碩士研究生，主要研究方向：點(diǎn)云分析、結(jié)構(gòu)光三維成像及應(yīng)用； 徐文（1992—），女（彝族），四川雅安人，博士研究生，主要研究方向：結(jié)構(gòu)光三維成像及應(yīng)用、人工智能； 周宇喬（1988—），男，浙江紹興人，博士，主要研究方向：X射線晶體學(xué)、結(jié)構(gòu)化學(xué)、計算化學(xué)； 劉凱（1973—），男（壯族），江蘇無錫人，教授，博士生導(dǎo)師，博士，主要研究方向：結(jié)構(gòu)光三維成像及應(yīng)用、機(jī)器視覺、數(shù)字圖像/信號處理。

TP301.6

A

2023?01?11。